顺序表和链表的基本操作代码
顺序表和链表是常见的数据结构，本文将分别介绍它们的基本操作代码，并从时间复杂度、空间复杂度和使用场景等多个角度进行分析比较。
一、顺序表的基本操作代码
1.初始化
```c
#define MaxSize 50 // 定义一个顺序表的最大长度
typedef struct {
int data[MaxSize]; // 存放数据元素的数组
int length; // 顺序表的当前长度
} SqList;
void InitList(SqList &L) {
// 初始化一个空的顺序表
for (int i = 0; i < MaxSize; i++) {
L.data[i] = 0; // 将所有元素初始化为0
}
L.length = 0; // 将长度初始化为0
}
```
2.插入数据
```c
bool InsertList(SqList &L, int i, int e) {
// 在第i个位置插入元素e
if (i < 1 || i > L.length + 1 || L.length == MaxSize) {
return false; // 插入位置不合法或者顺序表已满，返回false
}
for (int j = L.length; j >= i; j--) {
L.data[j] = L.data[j - 1]; // 将第i个位置及以后的元素后移一位
}
L.data[i - 1] = e; // 将元素e插入到第i个位置
L.length++; // 长度加1
return true;
}
```
3.删除数据
```c
bool DeleteList(SqList &L, int i) {
// 删除第i个位置的元素
if (i < 1 || i > L.length) {
return false; // 删除位置不合法，返回false
}
for (int j = i; j < L.length; j++) {
L.data[j - 1] = L.data[j]; // 将第i个位置及以后的元素前移一位
}
L.length--; // 长度减1
return true;
}
```
二、链表的基本操作代码
1.初始化
```c
typedef struct LNode {
int data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkList;
void InitList(LinkList &L) {
// 初始化一个空的链表
L = (LinkList)malloc(sizeof(LNode)); // 分配一个头结点的空间
L->next = NULL; // 头结点的指针域置为NULL
}
```
2.插入数据
```c
bool InsertList(LinkList &L, int i, int e) {
// 在第i个位置插入元素e
if (i < 1) {
return false; // 插入位置不合法，返回false
}
LNode *p = L; // p为头结点
int j = 0; // 记录p指针所指向的结点的位置
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL) {
return false; // 插入位置不合法，返回false
}
LNode *s = (LNode *)malloc(sizeof(LNode)); // 分配一个新的结点空间
s->data = e; // 将元素e赋值给新结点的数据域
s->next = p->next; // 将新结点的指针域指向p结点的下一个结点
p->next = s; // 将p结点的指针域指向新结点
return true;
}
```
3.删除数据
```c
bool DeleteList(LinkList &L, int i) {
// 删除第i个位置的元素
if (i < 1) {
return false; // 删除位置不合法，返回false
}
LNode *p = L; // p为头结点
int j = 0; // 记录p指针所指向的结点的位置
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL || p->next == NULL) {
return false; // 删除位置不合法，返回false
}
LNode *q = p->next; // q为要删除的结点
p->next = q->next; // 将p结点的指针域指向q结点的下一个结点
free(q); // 释放q结点的空间
return true;
}
```
三、分析比较
1.时间复杂度
顺序表和链表的时间复杂度不同，插入和删除操作的时间复杂度如下所示。
|操作|顺序表|链表|
|:-:|:-:|:-:|
|插入O(n)|O(n)|O(1)|
|删除O(n)|O(n)|O(1)|
从表格中可以看出，顺序表和链表的插入操作的时间复杂度相同，都是O(n)，但删除操作的时间复杂度则不同，顺序表的删除操作的时间复杂度也是O(n)，而链表的删除操作的时间复杂度是O(1)。
2.空间复杂度
顺序表和链表的空间复杂度也不相同。顺序表需要事先申请一段连续的固定大小的内存空间，而链表的每个结点可以分别在堆内存中分配空间，这意味着链表不需要预留额外的空间，所以链表的空间复杂度比顺序表低。
3.使用场景
顺序表和链表各有其适用的场景。当需要频繁地进行查找操作时，尤其是在有序的情况下，顺序表比较适合。而当频繁进行插入和删除操作时，尤其是在长度变化较大的情况下，链表比较适合。例如，链表常用于存储动态链表或稀疏矩阵等。
总之，顺序表和链表都是重要的基本数据结构，每种数据结构都有其独特的优点和缺点，需要慎重选择使用，根据实际需求进行选择。
