C语言实现顺序表的增删改查合并等操作

发表于 更新于 分类于 本文字数： 6.2k 阅读时长 ≈ 6 分钟
C语言实现顺序表的增删改查合并等操作

实验：顺序表的应用

一、实验目的

1．掌握如何将算法转换为程序； 2．熟悉顺序存储结构； 3．熟悉顺序表的操作； 4．熟悉顺序表的应用。

二、实验要求

1.程序要有注释，包括对总体功能、关键句、段的说明； 2.源程序必须调试通过，对每个输入的要求以及输出要有清晰的提示。程序要具有一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等。

三、实验内容

1．实验题目 （1）完成顺序表的基本运算：初始化、显示、求长度、判空、判满、插入、删除、按位置取元素、按值查找等，并编写主函数测试算法。 （2）)设计算法：将一个元素插入到有序的顺序表中，使顺序表仍有序，并编写主函数测试算法。

（3）设 A 和 B 两个顺序表，其元素按从小到大的顺序排列。编写一个算法将 A 和 B 的全部元素合并到有序顺序表 C 中，并编写主函数测试算法。 提示：有序表的合并； 有序表的产生，可以人为输入，也可以调用（2）的算法来实现。

2．数据结构的设计： 所选数据结构为顺序表。 3．算法描述： （2）用循环给顺序表赋初值，将要插入的数据从前往后一个一个和原顺序表元素比较，当该数据比顺序表此该位置的值大，小于或等于原顺序表的后一个值时，记录该位置，然后将数据插入到该位置。 （3）在 A，B 都没合并完的前提下，用 while 循环一个个比较 A 和 B 里边的元素值，谁小，就把谁放到 C 里，以此类推。

四、算法实现

头文件：table.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#ifndef _TABLE_H_
#define _TABLE_H_
#include <stdio.h>
#include <stdlib.h>
#define Size 5

typedef struct Table{
    int * head;
    int length;
    int size;
}table;

table initTable();
int TableLength(table t);
int emptyTable(table t);
int fullTable(table t);
table addTable(table t,int elem,int add);
table insertTable(table t,int elem);
table mergeTable(table t1,table t2,table t3);
table delTable(table t,int add);
int selectTable(table t,int elem);
int getTable(table t,int add);
table amendTable(table t,int elem,int newElem);
void displayTable(table t);

#endif // TABLE_H

主函数：main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
#include "table.h"

int main(){
    int i,add=0,elem=0;
    table t1=initTable();

    //初始化后赋值
    for (i=1; i<=Size; i++) {
        t1.head[i-1]=i;
        t1.length++;
    }
    printf("原顺序表：\n");
    displayTable(t1);
    printf("当前顺序表长度为：%d\n",TableLength(t1));
    if (fullTable(t1)){
        printf("当前顺序表已满\n");
    }
    printf("\n");

    //删除指定元素
    printf("请输入要删除的元素:");
    scanf("%d",&elem);
    t1=delTable(t1, elem);
    printf("删除%d元素后，顺序表为:",elem);
    displayTable(t1);
    printf("\n");

    //按位置插入元素
    printf("请输入要插入元素的位置和元素的值：");
    scanf("%d %d",&add,&elem);
    printf("在第%d的位置插入元素%d后，顺序表为:\n",add,elem);
    t1=addTable(t1, elem, add);
    displayTable(t1);
    printf("\n");

    //查找元素的位置
    printf("请输入要查找元素的值：");
    scanf("%d",&elem);
    printf("查找元素%d的位置为:\n",elem);
    add=selectTable(t1, elem);
    printf("%d\n",add);

    //修改元素的值
    printf("请输入要修改的元素：");
    scanf("%d",&elem);
    printf("请输入修改后的值：");
    scanf("%d",&add);
    printf("将元素%d改为%d:\n",elem,add);
    t1=amendTable(t1, elem, add);
    displayTable(t1);
    printf("\n");

    //按位置查找元素
    printf("请输入要查找元素的位置：\n");
    scanf("%d",&add);
    printf("位置%d的元素为：",add);
    printf("%d\n",getTable(t1,add));

    //有序顺序表的插入
    printf("有序顺序表如下\n");
    t1.length=0;
    for (i=1; i<=Size; i++) {
        t1.head[i-1]=i;
        t1.length++;
    }
    displayTable(t1);
    printf("请输入要插入的元素值：\n");
    scanf("%d",&elem);
    t1=insertTable(t1,elem);
    displayTable(t1);

    //有序顺序表的合并
    t1.length=0;
    for (i=1; i<=t1.size; i++) {
        t1.head[i-1]=i;
        t1.length++;
    }
    printf("顺序表A的值为：\n");
    displayTable(t1);//t1为A顺序表

    table t2=initTable();//t2为B顺序表
    for (i=t1.head[t1.size-1]+1; i<=t1.size+5; i++) {
        t2.head[i-t1.head[t1.size-1]-1]=i;
        t2.length++;
    }
    printf("顺序表B的值为：\n");
    displayTable(t2);
    table t3=initTable(); //t3用来存放合并后的顺序表
    t3=mergeTable(t1,t2,t3);
    printf("合并后的顺序表为：");
    displayTable(t3);
    return 0;
}

//初始化函数
table initTable(){
    table t;
    t.head=(int*)malloc(Size*sizeof(int));
    if (!t.head)
    {
        printf("初始化失败\n");
        exit(0);
    }
    t.length=0;
    t.size=Size;
    return t;
}

//求长度
int TableLength(table t){
    return t.length;
}

//判空函数
int emptyTable(table t){
    if (!t.length)
        return 1;
    return 0;
}

//判满
int fullTable(table t){
    int temp=0;
    if (t.length==t.size)
        temp=1;
    return temp;
}

//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置
table addTable(table t,int elem,int add)
{
    //判断插入本身是否存在问题
    if (add>t.length+1||add<1) {
        printf("插入位置有问题\n");
        return t;
    }
    //判断是否需要申请内存空间
    if (fullTable(t)) {
        t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));
        if (!t.head) {
            printf("存储分配失败\n");
            return t;
        }
        t.size++;
    }
    //后移操作
    for (int i=t.length-1; i>=add-1; i--) {
        t.head[i+1]=t.head[i];
    }
    //将所需插入元素，添加到顺序表的相应位置
    t.head[add-1]=elem;
    t.length++;
    return t;
}

//按顺序插入，找插入位置
table insertTable(table t,int elem){
    int i=0;
    while(i < t.length && elem >= t.head [i])//从小到大排列
    {
        i++;//注意i从0开始的 ，所以后面不用i - 1 ,这里的i即为下标
    }
    t=addTable(t,elem,++i);
    return t;
}

table mergeTable(table t1,table t2,table t3){
    int i=0,j=0,k=0;
    while(i<t1.length || j<t2.length){

        if(j == t2.length || i<t1.length && t1.head[i]<t2.head[j])

            t3.head[k++] = t1.head[i++];
        else
            t3.head[k++] = t2.head[j++];
    }
    t3.length = k;
    return t3;
}

table delTable(table t,int add){
    if (add>t.length || add<1) {
        printf("被删除元素的位置有误\n");
        return t;
    }
    //删除操作
    for (int i=add; i<t.length; i++) {
        t.head[i-1]=t.head[i];
    }
    t.length--;
    return t;
}

//按值查找函数，其中，elem表示要查找的数据元素的值
int selectTable(table t,int elem){
    for (int i=0; i<t.length; i++) {
        if (t.head[i]==elem) {
            return i+1;
        }
    }
    return -1;//如果查找失败，返回-1
}

//按位置取元素
int getTable(table t,int add){
    if (add>t.length || add<1) {
        printf("被查找元素的位置有误\n");
        return 0;
    }
    return t.head[add-1];
}

//更改函数，其中，elem为要更改的元素，newElem为新的数据元素
table amendTable(table t,int elem,int newElem){
    int add=selectTable(t, elem);
    t.head[add-1]=newElem;//由于返回的是元素在顺序表中的位置，所以-1就是该元素在数组中的下标
    return t;
}

void displayTable(table t){
    for (int i=0;i<t.length;i++) {
        printf("%d ",t.head[i]);
    }
    printf("\n");
}

五、实验运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
原顺序表：
1 2 3 4 5
当前顺序表长度为：5
当前顺序表已满

请输入要删除的元素:3
删除3元素后，顺序表为:1 2 4 5

请输入要插入元素的位置和元素的值：4
5
在第4的位置插入元素5后，顺序表为:
1 2 4 5 5

请输入要查找元素的值：5
查找元素5的位置为:
4
请输入要修改的元素：3
请输入修改后的值：4
将元素3改为4:
1 2 4 5 5

请输入要查找元素的位置：
3
位置3的元素为：4
有序顺序表如下
1 2 3 4 5
请输入要插入的元素值：
4
1 2 3 4 4 5
顺序表A的值为：
1 2 3 4 5 6
顺序表B的值为：
7 8 9 10 11
合并后的顺序表为：1 2 3 4 5 6 7 8 9 10 11

Process returned 0 (0x0)   execution time : 18.143 s
Press any key to continue.