顺序表学习总结_数据结构顺序表实验总结

顺序表是线性表的一种顺序存储形式（也可理解为一种高级的数组）。也就是说，线性表是逻辑结构，表示元素之间一对一的相邻关系；而顺序表是存储结构，是指用一组地址连续的存储单位，依次存储线性表中的数据元素，从而使得逻辑相邻的两个元素在物理位置上也相邻。
设顺序表的第一个元素 a0 的存储地址为 Loc(a0) ，每个元素占 d 个存储空间，则第 i 个元素的地址为：

				Loc(a0) = Loc(a0) + (i - 1) * d
1

顺序表在程序中通常用一维数组实现，一维数组可以是静态分配的，也可以是动态分配的。

在静态分配时，由于数组的大小和空间是固定的，一旦空间占满，就无法再新增数据，否则会导致数据溢出。

而在动态分配时，存储数组的空间在程序执行过程中会动态调整大小，当空间占满时，可以另行开辟更大的存储空间来储存数据。
顺序表最主要的特点是可以进行 随机访问，即可以通过表头元素的地址和元素的编号（下标），在 O(1) 的时间复杂度内找到指定的元素。

顺序表的不足之处是插入和删除操作需要移动大量的元素，从而保持逻辑上和物理上的连续性。

我们熟悉的一句话：数据结构 = 结构定义 + 结构操作

顺序表的结构定义

//顺序表其实就相当于高级的数组，例如整形数组arr[20] 在顺序表中20就相当于size，只不过是多一个现有元素个数而已。
typedef struct SeqList {
   
    int *data;
    int size, length;//分别为顺序表的空间长度与现有元素个数
} SeqList;
1
2
3
4
5
6

顺序表的结构操作

构造

SeqList *init(int n) {
   
	SeqList *list = (SeqList *)malloc(sizeof(SeqList));
	list->data = (int *)malloc(sizeof(int) * n);
	list->size = n;
	list->length = 0;
}
1
2
3
4
5
6
7

插入