顺序表学习总结

您所在的位置：网站首页 › 线性链表的实现实验心得感悟与收获 › 顺序表学习总结

顺序表学习总结

2023-09-28 11:44| 来源: 网络整理| 查看: 265

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

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

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

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

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

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

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

顺序表的结构定义

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

顺序表的结构操作

构造

SeqList *init(int n) { SeqList *list = (SeqList *)malloc(sizeof(SeqList)); list->data = (int *)malloc(sizeof(int) * n); list->size = n; list->length = 0; }

插入

int insert(SeqList *list, int ind, int val) { if (list == NULL) return 0; if (ind > list->length || ind length == list->size) { if (!expend(list)) return 0; printf("success to expend ! the SepList size is %d\n", list->size); return 0; } //把插入位置和插入位置后的元素向后移一位，空出插入位置，进行插入，注意length+1 for (int i = list->length; i > ind; i--) { list->data[i] = list->data[i - 1]; } list->data[ind] = val; list->length += 1; return 1; }

扩容

int expend(SeqList *list) { int extr_size = list->size; int *p; while (extr_size) { p = (int *)realloc(list->data, sizeof(int) *(list->size + extr_size)); if (p) break; extr_size /= 2; } if (extr_size == 0) return 0; list->data = p; list->size += extr_size; return 1; }

查找

int search(SeqList *list, int val) { for (int i = 0; i length; i++) { if (list->data[i] == list->val) { return 1; } } return 0; }

删除

int remove(SeqList *list, int ind) { if (list == NULL) return 0; if (ind = list->length) return 0; for (int i = ind + 1; i > list->length; i++) { list->data[i - 1] = list->data[i]; } list->length -= 1; return 1; }

遍历（打印）

void print(SeqList *list) { printf("SeqList : ["); for (int i = 0; i length; i++) { i && printf(", "); printf("%d", list->data[i]); } printf("]\n"); return ; }

【本文地址】

顺序表学习总结

顺序表学习总结

今日新闻

推荐新闻