【数据结构】顺序表的定义和实现

顺序表的定义

顺序表是指用顺序存储的方式实现线性表

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

【看到这是否会和我有同样的疑问：顺序表和数组是一样的吗？这个问题可以参考顺序表和数组（易混淆）这篇文章的解释】

顺序表的实现

静态分配

#define MaxSize 10			//定义最大长度
typedef struct{ElemType data[MaxSize];	//用静态的“数组”存放数据元素，ElemType就是顺序表中存放的数据元素类型int length;				//顺序表的当前长度
}SqList;					//顺序表的类型定义（静态分配方式）

具体的代码

#include <stdio.h>
#define MaxSize 10typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList* L){L->length = 0;		//顺序表初始长度为0，不可省略
}int main(){SqList L;InitList(&L);//....return 0;
}

缺点：顺序表的长度刚开始确定后就无法更改（存储空间是静态的）

动态分配

#define InitSize 10			//顺序表的厨师长度
typedef struct{ElemType* data;			//指示动态分配数组的指针（指向顺序表中的第一个数据元素）int MaxSize;			//顺序表的最大容量int length;				//顺序表的当前长度
}SeqList;					//顺序表的类型定义（动态分配方式）

在 C 语言中，malloc 和 free 函数用于动态申请和释放内存空间
（对 malloc 函数还不理解的话，可以阅读【malloc()函数详解(动态内存开辟函数)】这篇文章）

具体的代码

#include <stdio.h>
#define InitSize 10typedef struct{int* data;int MaxSize;int length;
}SeqList;void InitList(SeqList* L){L->data = (int*)malloc(InitSize*sizeof(int)); //用 malloc 函数申请一片连续的存储空间L->length = 0;L->MaxSize = InitSize;
}void IncreaseSize(SeqList* L, int len){int *p = L->data;L->data = (int*)malloc((L->MaxSize+len)*sizeof(int));for(int i = 0; i < L->length; i++){L->data[i] = p[i];			//将数据复制到新区域，时间复杂度大}L->MaxSize = L->MaxSize + len;	//顺序表最大长度增加lenfree(p);		//释放原来的内存空间
}int main(){SeqList L;		//声明一个顺序表InitList(&L);	//初始化顺序表//...往顺序表中插入元素...IncreaseSize(&L,5);return 0;
}