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

---

---

代码实现

#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;
        }
    }
}