【面试必问】数据结构与算法----顺序表
【面试必问】数据结构与算法----顺序表
一、逻辑结构与物理结构
1.1 逻辑结构
逻辑结构，表示数据元素间的相互关系，例如一对一、一对多、多对多。常见的逻辑结构有集合结构、线性结构、树状结构以及图状结构；
集合结构：元素之间没有特定的关系，如下图所示。
线性结构：元素间属于一对一的关系，如图所示。
树状结构：元素间属于一对多的关系，如图所示。
图状结构：元素间属于多对多的关系，如图所示。
1.2 物理结构
物理结构，又叫存储结构，表示的是数据在磁盘中的存储方式，一般分为顺序存储、链式存储、索引存储及散列存储。本文主要探讨顺序结构和链式结构。
顺序存储结构：在磁盘中以一段连续的空间进行存储。
优点：因为地址连续，所以可以随机访问，便于进行查找。
缺点：删除或插入数据时效率较低，且空间在初始化时便已确定，不能动态扩容。
链式存储结构：在磁盘中的存储是不连续的。
优点：插入或删除时，只需要修改节点的指向即可，可以动态扩容，理论上没有空间大小限制。
缺点：查找时需要遍历，效率较低，不能随机访问。
二、顺序表
2.1 顺序表简介
线性表是一种采用线性结构的数据结构，其可以采用链式存储结构进行存储，称为链表；也可以采用顺序存储结构进行存储，被称为顺序表。所以顺序表是一种逻辑结构为线性结构，并采用顺序存储方式的数据结构。
2.2 顺序表的初始化
首先我们需要定义一个表示顺序表的数据项，代码如下：
#define MAXSIZE 30
typedef int ElemType; // 重定义int类型
typedef int Status;
struct SequenceList {
ElemType *data; // 存储顺序表数据的数组
int length; // 顺序表长度
};滑动显示更多
顺序表的空间是一段连续的空间并且大小固定，我们可以在初始化时开辟空间，并将length置为0，代码如下：
Status ListInit(SqList *L) {
L->data = malloc(sizeof(ElemType) * MAXSIZE); // 首先开辟一片大小为30 * sizeof(ElemType)的连续空间
if (!L->data) {
// 容错处理，开辟空间失败返回ERROR
return ERROR;
}
L->length = 0; // 初始化时，没有添加元素，长度为0
return OK;
}滑动显示更多
2.3 顺序表插入数据
插入数据的要求是在顺序表指定下标插入相应的元素，需要考虑以下几点：
1、顺序表是否已满，如果已满则不能插入；
2、下标i是否合法，i<0或者 i>length 则输入不合法，不可插入；
3、线性表的插入，需要将i及i之后的元素都后移一位，再进行插入；如果i位于最后一个元素之后则直接插入，不需要后移；
4、插入元素后，需要将线性表length加1。
具体代码如下：
Status ListInsert(SqList *L, int i, ElemType data) {
// 此处考虑的是插入位置从0开始的情况
if (i < 0 || i > L->length) {
// 若表为空，则length为0，插入从0 开始则可以插入，大于0则超出length不可插入
// 若表不为空，以 0 1 2 3 为例
// i=3 则插在3的位置，3后移一位
// i=4 则可以直接插在表尾，i= 5则超出length,不可插入
return ERROR;
}
if (L->length >= MAXSIZE) {
// 表满，不可插入
return ERROR;
}
if (i <= L->length - 1) {
for (int j = L->length - 1; j >= i; j--) {
// 由表尾数据到i，所有数据向后移一位，此时考虑表满情况已经判断过，不需要考虑
// 后移一位后，空出i的位置
L->data[j+1] = L->data[j];
}
}
L->data[i] = data; // 直接对i赋值
L->length++; // 插入数据后，将length加1即可，注意此时表长加一，开辟的空间大小依然不变
return OK;
}滑动显示更多
2.4 顺序表删除
顺序表的删除操作，需要将待删除位置之后的元素均前移一位即可，需要考虑的事情如下：
1、表空，及length==0，则不允许删除；
2、同插入操作，i<0或者 i>length 则输入不合法，不可插入；
3、i之后的元素均前移一位；
4、元素前移后length减1。
删除的代码如下：
Status ListDelete(SqList *L, int i) {
if (L->length == 0) {
// 表空，不可执行删除操作
return ERROR;
}
if (i < 0 || i >= L->length) {
return ERROR;
}
for (int j = i; j < L->length-1; j++) {
L->data[j] = L->data[j+1];
}
L->length--; // 顺序表的删除后，将length减1即可，删除的位置原数据会被覆盖，也不需要考虑释放空间的问题
return OK;
}
2.5 修改和查询
顺序表的修改和查询操作比较简单，根据下标取出相应元素即可，如果是查找给定值的元素位置，则需要遍历顺序表。遍历顺序表代码如下：
// 遍历顺序表
void Traversal(SqList L) {
if (L.length == 0) {
return;
}
printf("\n");
for (int i = 0; i < L.length; i++) {
printf("%d\n",L.data[i]);
}
printf("\n");
}三、总结
注：本篇中的事例，都是以0开始的下标实现的，也可以采用以1开始，这个有兴趣的朋友可以自己实现。在学习顺序表的过程中，笔者遇到几个问题：
1、顺序表删除为何不需要释放空间？
顺序表的空间一经开辟，不会改变，只需要修改length即可；
2、插入或删除时，对顺序表所占空间是否有影响？
没有影响。问题1中说到顺序表的空间不会改变，改变的只有length。这里可以类比平时开发中对数组的操作，我们插入或删除数组中元素，数组的count会改变，但是数组的空间并没有改变。
本文分享自 HelloCoder全栈小集 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！