顺序表和链表的基本操作代码

顺序表和链表是常见的数据结构，本文将分别介绍它们的基本操作代码，并从时间复杂度、空间复杂度和使用场景等多个角度进行分析比较。

一、顺序表的基本操作代码

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.使用场景

顺序表和链表各有其适用的场景。当需要频繁地进行查找操作时，尤其是在有序的情况下，顺序表比较适合。而当频繁进行插入和删除操作时，尤其是在长度变化较大的情况下，链表比较适合。例如，链表常用于存储动态链表或稀疏矩阵等。

总之，顺序表和链表都是重要的基本数据结构，每种数据结构都有其独特的优点和缺点，需要慎重选择使用，根据实际需求进行选择。