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

曾经终败给现在 2024-02-28 07:06 71阅读 0赞

--------------------

#### 线性表-顺序存储-动态分配-王道课后练习 ####

*  代码实现

--------------------

## 代码实现 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #include<string.h>
    
    //线性表元素数据类型
    #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<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
    //为了这个题，先写个排序算法。就用冒泡排序吧。
    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<list2.length;index2++){
        
    //            if (merge.length == merge.MaxSize) {
        
    //                MultipleList(&merge);
    //            }
    //            merge.data[i++] = merge.data[index2];
    //        }
    //        merge.length = i;
    //        return merge;
    //    }
    //    else{
        
    //        for(;index1<list1.length;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;
            }
        }
    }