【C语言数据结构】线性表-顺序存储-动态分配（顺序表）

╰+攻爆jí腚メ 2024-02-29 00:43 68阅读 0赞

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

#### 线性表-顺序存储-动态分配 ####

*  代码实现

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

## 代码实现 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    //线性表初始分配的长度
    #define InitSize 3
    
    //线性表元素的数据类型
    #define ElemType int
    
    typedef struct {
        
        //定义线性表的元素数据，虽然是指针，实际上物理内存也是连续出存储的
        ElemType *data;
    
        //MaxSize是当前线性表的最大长度，这个数值也有可能改变，因为后续操作中线性表有可能扩容，因为是动态分配。
        //length是线性表的当前长度，也就是实际上里面有多少个数据
        int MaxSize, length;
    } SeqList;
    
    //函数声明
    bool Empty(SeqList list);
    
    //初始化线性表，也就是创建一个新的线性表。
    void InitList(SeqList *list) {
        
        list->data = (ElemType *) malloc(InitSize * sizeof(ElemType));
        list->MaxSize = InitSize;
        list->length = 0;
    }
    
    //扩容线性表
    bool MultipleList(SeqList *list) {
        
        //建立临时线性表，用于存储之前的数据元素
    //    SeqList listNew;
    //    InitList(&listNew);
    //    for (int i = 0; i < list->length; i++) {
        
    //        listNew.data[i] = list->data[i];
    //    }
    //    listNew.length = list->length;
    //
    //    list->data = (ElemType *) malloc(list->MaxSize * sizeof(ElemType) * 2);
    //    for (int i = 0; i < listNew.length; i++) {
        
    //        list->data[i] = listNew.data[i];
    //    }
    //    list->MaxSize = list->MaxSize * 2;
    
    //上面是我之前写的愚蠢的代码
    
        if(list->data != NULL){
        
            list->data = (ElemType *) realloc(list->data, list->MaxSize * sizeof(ElemType) * 2);
    
            //如果新内存分配成功，也就是list->data不为空，就把MaxSize设置为原来的两倍
            list->MaxSize = list->MaxSize * 2;
            return true;
        }
        printf("扩容失败！\n");
        return false;
    }
    
    //返回线性表表长
    int Length(SeqList list) {
        
        return list.length;
    }
    
    //添加数据元素
    void AddElem(SeqList *list, ElemType Elem) {
        
        //如果当前线性表已满，就进行内存重新分配
        if (list->length == list->MaxSize) {
        
            if(!MultipleList(list)){
        
                printf("扩容失败，线性表已被销毁！\n");
                return;
            }
        }
        list->data[list->length] = Elem;
        list->length++;
    }
    
    //按值查找操作
    int LocateElem(SeqList list, ElemType Elem) {
        
        if (Empty(list)) {
        
            //线性表为空，则查找失败
            return -1;
        }
        for (int i = 0; i < list.length; i++) {
        
            if (list.data[i] == Elem)
                return i;
        }
        return -1;
    }
    
    //按位查找操作
    bool GetElem(SeqList list, int index, ElemType *Elem) {
        
        if (index >= 0 && index < list.length) {
        
            *Elem = list.data[index];
            return true;
        }
    
        printf("获取失败！\n");
        return false;
    }
    
    //插入操作
    bool ListInsert(SeqList *list, int index, ElemType Elem) {
        
        //如果线性表已满，就先进行扩容
        if (list->length == list->MaxSize) {
        
            MultipleList(list);
        }
    
        //判断输入的数组下标是否在合法范围内
        if (index >= 0 && index < list->length) {
        
    
            for (int i = list->length - 2; i >= index; i--) {
        
                list->data[i + 1] = list->data[i];
            }
            list->data[index] = Elem;
            list->length++;
    
            return true;
        }
    
        return false;
    }
    
    //删除元素
    bool ListDelete(SeqList *list, int index) {
        
        if (index >= 0 && index < list->length) {
        
            for (int i = index; i < list->length - 1; i++) {
        
                list->data[i] = list->data[i+1];
            }
            list->length--;
            return true;
        }
        return false;
    }
    
    //销毁线性表
    void DestroyList(SeqList *list){
        
        //如果list->data依然被分配内存，那么进行释放
        if(list->data != NULL) {
        
            //释放之前分配的内存
            free(list->data);
            //避免悬空指针问题，直接把list->data指针设置为空
            list->data = NULL;
        }
        list->length = 0;
        list->MaxSize = 0;
    }
    
    //打印整个线性表
    void PrintList(SeqList list) {
        
        if (Empty(list)) {
        
            printf("线性表为空！\n");
            return;
        }
        for (int i = 0; i < list.length; i++) {
        
            printf("%d -> %d\n", i, list.data[i]);
        }
    }
    
    //线性表判空，如果线性表为空，返回true。不为空返回false
    bool Empty(SeqList list) {
        
        if (list.length == 0)
            return true;
        return false;
    }
    
    int main() {
        
        //定义线性表a
        SeqList a;
    
        //定义数据元素
        ElemType Elem;
    
        //定义数组下标和菜单选择
        int index, choice;
    
        //初始化线性表a
        InitList(&a);
    
        while (1) {
        
            printf("\n菜单\n"
                   "1.查看线性表\n"
                   "2.获取线性表长度\n"
                   "3.添加线性表元素\n"
                   "4.按值查找操作\n"
                   "5.按位查找操作\n"
                   "6.插入操作\n"
                   "7.删除操作\n"
                   "8.销毁线性表\n"
                   "9.退出程序\n"
                   "10.获取线性表最大长度(测试)\n"
                   "请输入你要进行的操作:");
            scanf("%d", &choice);
            switch (choice) {
        
                case 1:
                    PrintList(a);
                    break;
                case 2:
                    printf("当前线性表长度为%d\n", Length(a));
                    break;
                case 3:
                    printf("请输入要添加的数据数值:");
                    scanf("%d", &Elem);
                    AddElem(&a, Elem);
                    break;
                case 4:
                    printf("请输入要查找的数据元素值：");
                    scanf("%d", &Elem);
                    index = LocateElem(a, Elem);
                    if (index == -1) {
        
                        printf("元素查找失败！\n");
                        break;
                    } else {
        
                        printf("元素%d对应的数组下标为%d\n", Elem, index);
                        break;
                    }
                case 5:
                    printf("请输入要查找的数据元素的数组下标：");
                    scanf("%d", &index);
                    if (GetElem(a, index, &Elem)) {
        
                        printf("数组下标为%d的元素为%d\n", index, Elem);
                        break;
                    } else {
        
                        printf("查找失败！\n");
                        break;
                    }
                case 6:
                    printf("请输入要插入的元素的位置(数组下标):");
                    scanf("%d", &index);
                    printf("请输入要插入的元素的数据值:");
                    scanf("%d", &Elem);
                    if (ListInsert(&a, index, Elem)) {
        
                        printf("插入成功！\n");
                        break;
                    } else {
        
                        printf("插入失败！输入的数组下标不合法\n");
                        break;
                    }
                case 7:
                    printf("请输入要删除的元素的数组下标：");
                    scanf("%d",&index);
                    if(ListDelete(&a,index)){
        
                        printf("元素删除成功！\n");
                        break;
                    }
                    else{
        
                        printf("元素删除失败！输入的下标不合法\n");
                        break;
                    }
                case 8:
                    DestroyList(&a);
                    break;
                case 9:
                    exit(0);
                case 10:
                    printf("当前线性表最大长度为%d\n",a.MaxSize);
                    break;
                default:
                    printf("输入的操作有误，请重新输入！\n");
                    break;
            }
        }
    }