【C语言数据结构】线性表-顺序存储-动态分配-王道课后练习

---

---

代码实现

#include
#include
#include
#include

//线性表元素数据类型
#define ElemType int
//线性表初始长度
#define InitSize 100

//线性表
typedef struct {
    //数据元素
    ElemType *data;
    //线性表名称（最高10个字符）
    char name[10];
    //线性表当前长度和最大长度
    int length, MaxSize;
} SeqList;

//存放线性表的线性表
typedef struct {
    //线性表元素
    SeqList *list;
    //当前线性表的个数，线性表最大长度
    int length, MaxSize;
} ListOfLists;

//函数声明
int GetList(ListOfLists AllList, char name[]);

//初始化线性表(创建线性表)
void InitList(SeqList *list, char name[]) {
    //给线性表数据元素分配内存空间
    list->data = (ElemType *) malloc(InitSize * sizeof(ElemType));
    strcpy(list->name, name);
    list->length = 0;
    list->MaxSize = InitSize;
}

//线性表扩容
bool MultipleList(SeqList *list) {
    if (list->data != NULL) {
        //扩容至原来的两倍
        list->data = (ElemType *) realloc(list->data, list->MaxSize * sizeof(ElemType) * 2);
        list->MaxSize = list->MaxSize * 2;
        return true;
    }
//    printf("扩容失败，线性表已被销毁！\n");
    return false;
}

//初始化存放线性表的线性表
void InitListOfLists(ListOfLists *list) {
    list->list = (SeqList *) malloc(InitSize * sizeof(SeqList));
    list->length = 0;
    list->MaxSize = InitSize;
}

//扩容存放线性表的线性表
bool MultipleListOfLists(ListOfLists *list) {
    //因为总线性表不会被销毁，所以直接扩容即可,无需再判断是否为销毁的线性表
    list->list = (SeqList *) realloc(list->list, list->MaxSize * sizeof(SeqList) * 2);
    //判断扩容是否成功
    if (list->list != NULL) {
        list->MaxSize = list->MaxSize * 2;
        return true;
    }
    return false;
}

//添加线性表插入到存放线性表的线性表中
void AddList(ListOfLists *AllList, SeqList list) {
    if (AllList->length == AllList->MaxSize) {
        //如果总线性表满了，就对总线性表进行扩容
        MultipleListOfLists(AllList);
    }
    AllList->list[AllList->length] = list;
    AllList->length++;
}

//给线性表添加数据元素
void AddElem(ListOfLists *AllList, SeqList *list, ElemType Elem) {
    //如果线性表已满，就先进行扩容
    if (list->length == list->MaxSize) {
        MultipleList(list);
    }
    list->data[list->length] = Elem;
    list->length++;

    //将总线性表里的这个线性表进行更新
    AllList->list[GetList(*AllList, list->name)] = *list;
}

//查找某个指定名称的线性表
SeqList FindList(ListOfLists AllList, char name[]) {
    for (int i = 0; i < AllList.length; i++) {
        if (strcmp(AllList.list[i].name, name) == 0) {
            return AllList.list[i];
        }
    }
    SeqList empty;
    empty.data = NULL;
    strcpy(empty.name, "");
    empty.length = 0;
    empty.MaxSize = 0;
    return empty;
}

//根据线性表名称返回在总线性表中的数组下标
int GetList(ListOfLists AllList, char name[]) {
    for (int i = 0; i < AllList.length; i++) {
        if (strcmp(AllList.list[i].name, name) == 0) {
            return i;
        }
    }
    return -1;
}

//打印所有线性表
void PrintAllList(ListOfLists AllList) {
    if (AllList.length == 0) {
        printf("当前线性表为空！\n");
        return;
    }
    for (int i = 0; i < AllList.length; i++) {
        printf("%d -> %s\n", i, AllList.list[i].name);
    }
}

//打印线性表的数据元素
void PrintList(SeqList list) {
    if (list.length == 0) {
        printf("当前线性表为空！\n");
        return;
    }
    for (int i = 0; i < list.length; i++) {
        printf("%d -> %d\n", i, list.data[i]);
    }
}

/*-----------------------------以上是线性表基础操作，下面是王道课后习题代码-----------------------------------------*/

//P17线性表02题;设计一个高效算法，将顺序表L中的所有元素逆置，要求算法的空间复杂度为o(1)
//采用指针的思想，设计头尾两个指针，通过交换指针所指元素来完成逆置操作。由于没有借助额外的辅助数组，所以空间复杂度为o(1)。
void Reverse(ListOfLists *AllList, SeqList *list) {
    //定义左右指针
    int left = 0, right = list->length - 1;
    //定义临时变量，用于数据交换
    ElemType temp;
    for (; left < right; left++, right--) {
        temp = list->data[left];
        list->data[left] = list->data[right];
        list->data[right] = temp;
    }

    //将逆置后的数组更新在总线性表中
    AllList->list[GetList(*AllList, list->name)] = *list;
}

//P17线性表03题;对长度为n的顺序表L，编写一个时间复杂度为o(n),空间复杂度为o(1)的算法，该算法删除线性表中所有值为x的数据元素。
//空间复杂度为o(1)，说明不准使用辅助数组，但是可以使用辅助变量，辅助变量用多少个都行。时间复杂度为o(n),说明你只能扫一遍顺序表。
void Delete_x(ListOfLists *AllList, SeqList *list, ElemType x) {
    //不等于x的元素个数
    int k = 0;

    //1 2 3 4 x 1 2 3 x 1 2 3 x
    //k
    //i

    //1 2 3 4 x 1 2 3 x 1 2 3 x
    //  k
    //  i

    //1 2 3 4 x 1 2 3 x 1 2 3 x
    //    k
    //    i

    //1 2 3 4 x 1 2 3 x 1 2 3 x
    //      k
    //      i

    //1 2 3 4 x 1 2 3 x 1 2 3 x
    //      k i

    //1 2 3 4 1 1 2 3 x 1 2 3 x
    //        k i

    //1 2 3 4 1 2 2 3 x 1 2 3 x
    //          k i

    //1 2 3 4 1 2 3 3 x 1 2 3 x
    //            k i

    //1 2 3 4 1 2 3 3 x 1 2 3 x
    //            k   i

    //1 2 3 4 1 2 3 1 x 1 2 3 x
    //              k   i

    //1 2 3 4 1 2 3 1 2 1 2 3 x
    //                k   i

    //1 2 3 4 1 2 3 1 2 3 2 3 x
    //                  k   i

    for (int i = 0; i < list->length; i++) {
        //当数据不是x时，k+1
        if (x != list->data[i]) {
            list->data[k] = list->data[i];
            k++;
        }
    }

    //将新的线性表长度设置为k
    list->length = k;

    //更新总线性表
    AllList->list[GetList(*AllList, list->name)] = *list;
}

//P17线性表04题;从有序顺序表中删除其值在给定值s与t之间(要求s
//为了这个题，先写个排序算法。就用冒泡排序吧。
void swap(ElemType *a, ElemType *b) {
    ElemType temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void BubbleSort(SeqList *list) {
    for (int i = 0; i < list->length; i++) {
        for (int j = 0; j < list->length - 1 - i; j++) {
            if (list->data[j] > list->data[j + 1])
                swap(&list->data[j], &list->data[j + 1]);
        }
    }
}

void Delete_s2t(ListOfLists *AllList, SeqList *list, ElemType s, ElemType t) {
    if (s >= t) {
        printf("S与T的值不合法！\n");
        return;
    } else if (list->length == 0) {
        printf("顺序表为空！删除失败\n");
        return;
    }

    //记录s的位置和s到t之间有多少个数据元素
    int num = 0;
    //先把list变成有序表(递增)
    BubbleSort(list);

    for (int i = 0; i < list->length; i++) {
        if (!(list->data[i] >= s && list->data[i] <= t)) {
            list->data[num] = list->data[i];
            num++;
        }
    }
    list->length = num;

    //更新总线性表
    AllList->list[GetList(*AllList, list->name)] = *list;
}

//P17线性表06题;从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
void Delete_Repeat(ListOfLists *AllList, SeqList *list) {
    //先对线性表进行排序
    BubbleSort(list);

    //记录不重复元素的个数
    int num = 0;

    for (int i = 0; i < list->length - 1; i++) {
        if (list->data[i] != list->data[i + 1]) {
            list->data[num] = list->data[i];
            num++;
        }
    }

    list->data[num] = list->data[list->length - 1];
    list->length = ++num;
    PrintList(*list);

    //更新总线性表
    AllList->list[GetList(*AllList, list->name)] = *list;
}

//P17线性表07题;将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表
//采用双指针对比的思想，分别给两个顺序表一个指针，进行对比。
SeqList MergeList(SeqList list1, SeqList list2, char name[]) {
    SeqList merge;
    InitList(&merge, name);

    BubbleSort(&list1);
    BubbleSort(&list2);
    //定义两个指针
    int index1 = 0, index2 = 0;
    int i;
    for (i = 0; index1 < list1.length && index2 < list2.length; i++) {
        if (list1.data[index1] < list2.data[index2]) {
            if (merge.length == merge.MaxSize) {
                MultipleList(&merge);
            }
            merge.data[i] = list1.data[index1++];
        } else {
            if (merge.length == merge.MaxSize) {
                MultipleList(&merge);
            }
            merge.data[i] = list2.data[index2++];
        }
    }
//    if(index1>=list1.length){
//        for(;index2
//            if (merge.length == merge.MaxSize) {
//                MultipleList(&merge);
//            }
//            merge.data[i++] = merge.data[index2];
//        }
//        merge.length = i;
//        return merge;
//    }
//    else{
//        for(;index1
//            if (merge.length == merge.MaxSize) {
//                MultipleList(&merge);
//            }
//            merge.data[i++] = merge.data[index1];
//        }
//        merge.length = i;
//        return merge;
//    }
//上面这种处理方式有错误，但我找不出来
    while (index1 < list1.length) {
        if (merge.length == merge.MaxSize) {
            MultipleList(&merge);
        }
        merge.data[i++] = list1.data[index1++];
    }

    while (index2 < list2.length) {
        if (merge.length == merge.MaxSize) {
            MultipleList(&merge);
        }
        merge.data[i++] = list2.data[index2++];
    }

    merge.length = i;
    return merge;
}

int main() {
    //初始化总线性表
    ListOfLists AllLists;
    InitListOfLists(&AllLists);

    //定义线性表
    SeqList list, list1, list2;

    //定义数据元素(s和t是题目中需要用到的变量)
    ElemType Elem, s, t;

    //定义线性表名称
    char ListName[10], ListName1[10], ListName2[10];

    //定义菜单选择变量和数组下标索引
    int choice, index;

    while (1) {
        printf("\n菜单\n"
               "1.创建线性表\n"
               "2.查看当前所有线性表\n"
               "3.指定线性表添加元素\n"
               "4.查看指定线性表的所有数据元素\n"
               "---------以下是王道题目操作-----------\n"
               "5.逆置指定线性表\n"
               "6.删除指定线性表中所有值为x的元素\n"
               "7.删除指定有序线性表中s到t之间的所有元素\n"
               "8.删除重复元素，使线性表每个元素数据唯一\n"
               "9.指定两个有序顺序表，并将其合并为新的线性表\n"
               "10.退出程序\n"
               "请输入要进行的操作:");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                printf("请输入你要创建的线性表的名称(不超过10个字符):");
                scanf("%s", ListName);
                if (FindList(AllLists, ListName).data != NULL) {
                    printf("线性表已存在!\n");
                    break;
                }
                //创建新线性表
                InitList(&list, ListName);
                //将线性表添加到总线性表中
                AddList(&AllLists, list);
                break;
            case 2:
                PrintAllList(AllLists);
                break;
            case 3:
                printf("请输入你要添加元素的线性表的名称:");
                scanf("%s", ListName);
                if (GetList(AllLists, ListName) == -1) {
                    printf("找不到该线性表!\n");
                    break;
                }
                list = FindList(AllLists, ListName);
                printf("请输入你要添加的数据值:");
                scanf("%d", &Elem);
                AddElem(&AllLists, &list, Elem);
                break;
            case 4:
                printf("请输入你要查看的线性表的名称:");
                scanf("%s", ListName);
                if (GetList(AllLists, ListName) == -1) {
                    printf("找不到该线性表!\n");
                    break;
                }
                list = FindList(AllLists, ListName);
                PrintList(list);
                break;
            case 5:
                printf("请输入你要逆置的线性表的名称:");
                scanf("%s", ListName);
                if (GetList(AllLists, ListName) == -1) {
                    printf("找不到该线性表!\n");
                    break;
                }
                list = FindList(AllLists, ListName);
                Reverse(&AllLists, &list);
                break;
            case 6:
                printf("请输入要删除元素的线性表的名称:");
                scanf("%s", ListName);
                if (GetList(AllLists, ListName) == -1) {
                    printf("找不到该线性表!\n");
                    break;
                }
                printf("请输入要删除的元素数值:");
                scanf("%d", &Elem);
                list = FindList(AllLists, ListName);
                Delete_x(&AllLists, &list, Elem);
                break;
            case 7:
                printf("请输入要删除元素的线性表的名称:");
                scanf("%s", ListName);
                if (GetList(AllLists, ListName) == -1) {
                    printf("找不到该线性表!\n");
                    break;
                }
                printf("请输入要删除的起始数值s:");
                scanf("%d", &s);
                printf("请输入要删除的终止数值t:");
                scanf("%d", &t);
                Delete_s2t(&AllLists, &list, s, t);
                break;
            case 8:
                printf("请输入要删除元素的线性表的名称:");
                scanf("%s", ListName);
                if (GetList(AllLists, ListName) == -1) {
                    printf("找不到该线性表!\n");
                    break;
                }
                Delete_Repeat(&AllLists, &list);
                break;
            case 9:
                printf("请输入要合并的第一个线性表的名称:");
                scanf("%s", ListName1);
                if (GetList(AllLists, ListName1) == -1) {
                    printf("找不到该线性表!\n");
                    break;
                }
                printf("请输入要合并的第二个线性表的名称:");
                scanf("%s", ListName2);
                if (GetList(AllLists, ListName2) == -1) {
                    printf("找不到该线性表!\n");
                    break;
                }
                printf("请输入合并后新线性表的名称:");
                scanf("%s", ListName);
                list = MergeList(FindList(AllLists, ListName1), FindList(AllLists, ListName2), ListName);
                AddList(&AllLists, list);
                break;
            case 10:
                exit(0);
            default:
                printf("输入的操作数有误，请重新输入！\n");
                break;
        }
    }
}
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
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491