C语言_数据结构总结2：动态分配方式的顺序表

0——静态分配内存的顺序表和动态分配内存的顺序表的相同之处和不同之处

相同之处

• 基本操作逻辑相同：无论是静态分配还是动态分配的顺序表，其核心的操作逻辑是一致的。例如插入操作都需要将插入位置之后的元素依次后移，删除操作都需要将删除位置之后的元素依次前移，查找操作也都是通过遍历或者直接定位来完成。

• 数据元素存储方式相同：两种顺序表都是将数据元素依次存储在连续的内存空间中，都可以通过数组下标来直接访问元素，时间复杂度为 \(O(1)\)。

• 功能用途相同：都用于实现线性表的功能，支持数据的插入、删除、查找等基本操作。

不同之处

• 内存分配方式：

  • 静态分配：在编译时就确定了顺序表的最大容量，使用数组来存储元素，数组的大小在程序运行过程中不能改变。

  • 动态分配：在程序运行时根据需要动态地分配内存空间，可以通过 malloc、realloc 等函数来调整顺序表的容量。

• 内存管理：

  • 静态分配：不需要手动管理内存，数组的内存空间由系统自动分配和释放。

  • 动态分配：需要手动管理内存，使用 malloc 分配内存，使用 free 释放内存，否则会造成内存泄漏。

• 表长限制：

  • 静态分配：顺序表的最大长度是固定的，一旦达到最大长度就无法再插入新的元素。

  • 动态分配：可以根据需要动态地调整顺序表的容量，理论上只要系统有足够的内存，就可以不断地插入新的元素。

   纯C语言代码，不涉及C++   

代码实现

0. 变量声明

#include<stdio.h>
#include<stdlib.h>

#define InitSize 50  //初始容量
#define Increment 10  //每次扩容的增量
typedef int ElemType;

typedef struct SeqList {
    ElemType* data;  //动态分配数组的指针
    int length;      //顺序表当前的长度（元素个数）
    int capacity;    //顺序表当前容量
}SeqList;

1.初始化

void InitSeqList(SeqList* L) {L->data = (ElemType*)malloc(sizeof(ElemType) * InitSize);if (L->data == NULL){printf("内存分配失败!\n");exit(1);  // 退出系统操作}L->length = 0;L->capacity = InitSize;
}

2.扩容

void IncreaseCapacity(SeqList* L) {ElemType* newData = (ElemType*)realloc(L->data,(sizeof(ElemType)) * (InitSize + Increment));if (newData == NULL){printf("内存分配失败!\n");exit(1);  // 退出系统操作}L->data = newData;L->capacity += Increment;
}

3.插入

即：在第pos个位置插入value值，即在数组下标pos-1的位置插入value值

int InsertSeqList(SeqList* L,int pos ,ElemType value) {//1.判断插入位置是否合法if (pos < 1 || pos > L->length + 1){printf("插入位置不合法!\n");return -1;}//2.判断顺序表存储空间是否满了if (L->length >= L->capacity){IncreaseCapacity(L);  //空间不足，进行扩容操作}//3.将第pos个位置及往后的元素都后移一个位置，空出第pos个位置（这里采用逆序遍历）for(int i = L->length; i >= pos; i++){L->data[i] = L->data[i - 1];}//4.插入数据L->data[pos - 1] = value;//5.表长加1L->length++;return 0;  //插入成功
}

4.按位查找

即：返回第pos个位置对应的value值

int findValueByPos(SeqList* L, int pos, ElemType* value) {//1.判断要查找的位置是否合理if (pos < 1 || pos > L->length){printf("查找位置不在当前顺序表范围内!\n");}//2.查找第pos个位置对应的value值*value = L->data[pos - 1];return 0; //查找成功
}

5.按值查找

即：返回value值对应的位序，即第几个，下标是位序减1

int findPosByValue(SeqList* L, ElemType value) {for (int i = 0; i < L->length ; i++){if (L->data[i] == value) {return i + 1;}}return -1;  //未在该顺序表中找到该值
}

6.删除

即：将第pos个的值赋值交给value变量存储后腾开第pos个位置
     然后将第pos个后的数据都往前移动一个位置，填补第pos个位置

int deleteSeqList(SeqList* L, int pos,ElemType* value) {//1. 判断删除位置是否合理，即是否在存有数据的范围内if (pos < 1 || pos > L->length){printf("待删除位置不在合理范围内!\n");return -1; }//2. 判断空间是否为空if (L->length == 0){printf("当前空间未存有数据，无法完成删除操作!\n");}//3.将要被删除的数据赋值（转存于）value变量*value = L->data[pos - 1];//4.将第pos个位置往后的元素都往前挪一个位置for (int i = pos; i < L->length; i++){L->data[i - 1] = L->data[i];}//5.表长减1L->length--;return 0; //删除成功
}

7.注销

void destroySeqList(SeqList* L) {if (L->data != NULL){free(L->data);L->data = NULL;L->length = 0;L->capacity = 0;}
}

8.打印

void printSeqList(SeqList* L) {if (L->length == 0){printf("当前顺序表为空!\n");}else {for (int i = 0; i < L->length ; i++){if (i == L->length - 1) {printf("%d", L->data[i]);}else{printf("%d ", L->data[i]);}}printf("\n");}printf("--------------------------------------------------\n");
}

9.测试代码

int main() {SeqList L;InitSeqList(&L);//插入数据测试if (InsertSeqList(&L,1,18) != 0){printf("插入失败!\n");}if (InsertSeqList(&L,2,7) != 0){printf("插入失败!\n");}if (InsertSeqList(&L,3,34) != 0){printf("插入失败!\n");}printSeqList(&L); // 18 7 34//删除数据测试ElemType value;if (deleteSeqList(&L, 2, &value) != 0){printf("删除失败!\n");}printSeqList(&L); // 18 34//按位查找测试，查找第1位的值是什么ElemType val;if (findValueByPos(&L,1,&val) == 0){printf("第1位的数据为:%d\n", val);  //第1位的数据为:18}else{printf("查找失败!\n");}//按值查找测试，查找18在顺序表的第几个位置int pos = findPosByValue(&L, 18);if (pos != -1){printf("值18在顺序表的第%d个位置\n", pos);  //值18在顺序表的第1个位置}else{printf("查找失败!\n");}//测试完记得执行销毁操作，释放空间内存destroySeqList(&L);return 0;
}

10.完整代码

#include<stdio.h>
#include<stdlib.h>#define InitSize 50  //初始容量
#define Increment 10  //每次扩容的增量
typedef int ElemType;typedef struct SeqList {ElemType* data;  //动态分配数组的指针int length;      //顺序表当前的长度（元素个数）int capacity;    //顺序表当前容量
}SeqList;// 操作1——初始化
void InitSeqList(SeqList* L) {L->data = (ElemType*)malloc(sizeof(ElemType) * InitSize);if (L->data == NULL){printf("内存分配失败!\n");exit(1);  // 退出系统操作}L->length = 0;L->capacity = InitSize;
}// 增加顺序表的容量
void IncreaseCapacity(SeqList* L) {ElemType* newData = (ElemType*)realloc(L->data,(sizeof(ElemType)) * (InitSize + Increment));if (newData == NULL){printf("内存分配失败!\n");exit(1);  // 退出系统操作}L->data = newData;L->capacity += Increment;
}//操作2——插入：在第pos个位置插入value值，即在数组下标pos-1的位置插入value值
int InsertSeqList(SeqList* L,int pos ,ElemType value) {//1.判断插入位置是否合法if (pos < 1 || pos > L->length + 1){printf("插入位置不合法!\n");return -1;}//2.判断顺序表存储空间是否满了if (L->length >= L->capacity){IncreaseCapacity(L);  //空间不足，进行扩容操作}//3.将第pos个位置及往后的元素都后移一个位置，空出第pos个位置（这里采用逆序遍历）for(int i = L->length; i >= pos; i++){L->data[i] = L->data[i - 1];}//4.插入数据L->data[pos - 1] = value;//5.表长加1L->length++;return 0;  //插入成功
}// 操作3——按位查找，即返回第pos个位置对应的value值
int findValueByPos(SeqList* L, int pos, ElemType* value) {//1.判断要查找的位置是否合理if (pos < 1 || pos > L->length){printf("查找位置不在当前顺序表范围内!\n");}//2.查找第pos个位置对应的value值*value = L->data[pos - 1];return 0; //查找成功
}// 操作4——按值查找，即返回value值对应的位序，即第几个，下标是位序减1
int findPosByValue(SeqList* L, ElemType value) {for (int i = 0; i < L->length ; i++){if (L->data[i] == value) {return i + 1;}}return -1;  //未在该顺序表中找到该值
}// 操作5——删除：将第pos个的值赋值交给value变量存储后腾开第pos个位置
// 然后将第pos个后的数据都往前移动一个位置，填补第pos个位置
int deleteSeqList(SeqList* L, int pos,ElemType* value) {//1. 判断删除位置是否合理，即是否在存有数据的范围内if (pos < 1 || pos > L->length){printf("待删除位置不在合理范围内!\n");return -1; }//2. 判断空间是否为空if (L->length == 0){printf("当前空间未存有数据，无法完成删除操作!\n");}//3.将要被删除的数据赋值（转存于）value变量*value = L->data[pos - 1];//4.将第pos个位置往后的元素都往前挪一个位置for (int i = pos; i < L->length; i++){L->data[i - 1] = L->data[i];}//5.表长减1L->length--;return 0; //删除成功
}// 操作6——注销
void destroySeqList(SeqList* L) {if (L->data != NULL){free(L->data);L->data = NULL;L->length = 0;L->capacity = 0;}
}//操作7——打印顺序表中存放的数据
void printSeqList(SeqList* L) {if (L->length == 0){printf("当前顺序表为空!\n");}else {for (int i = 0; i < L->length ; i++){if (i == L->length - 1) {printf("%d", L->data[i]);}else{printf("%d ", L->data[i]);}}printf("\n");}printf("--------------------------------------------------\n");
}int main() {SeqList L;InitSeqList(&L);//插入数据测试if (InsertSeqList(&L,1,18) != 0){printf("插入失败!\n");}if (InsertSeqList(&L,2,7) != 0){printf("插入失败!\n");}if (InsertSeqList(&L,3,34) != 0){printf("插入失败!\n");}printSeqList(&L); // 18 7 34//删除数据测试ElemType value;if (deleteSeqList(&L, 2, &value) != 0){printf("删除失败!\n");}printSeqList(&L); // 18 34//按位查找测试，查找第1位的值是什么ElemType val;if (findValueByPos(&L,1,&val) == 0){printf("第1位的数据为:%d\n", val);  //第1位的数据为:18}else{printf("查找失败!\n");}//按值查找测试，查找18在顺序表的第几个位置int pos = findPosByValue(&L, 18);if (pos != -1){printf("值18在顺序表的第%d个位置\n", pos);  //值18在顺序表的第1个位置}else{printf("查找失败!\n");}//测试完记得执行销毁操作，释放空间内存destroySeqList(&L);return 0;
}

11.运行截图

如有问题，欢迎指出！

谢谢！