在 C 语言中，由于没有内置的集合或列表类型，我们通常使用数组或链表来实现线性表。
下面我将分别介绍这两种实现方式,并给出它们的完整代码示例。
基于数组的线性表（顺序表）
数组在内存中是连续存储的，这使得它实现线性表时具有随机访问速度快的特点，但在插入和删除元素时可能需要移动大量元素,效率较低。
1 定义顺序表结构体
我们需要一个结构体来存储数据数组和当前线性表的长度。
#include <stdio.h>
#include <stdlib.h> // 用于动态内存分配
#define MAXSIZE 100 // 定义顺序表的最大容量
// 定义元素类型，这里假设为 int，可以根据需要修改
typedef int ElemType;
// 顺序表结构体
typedef struct {
ElemType data[MAXSIZE]; // 存储元素的数组
int length; // 当前线性表的长度
} SqList;
2 基本操作实现
初始化顺序表
将顺序表的长度设置为0。
void InitList(SqList *L) {
L->length = 0;
}
插入元素（在第 i 个位置前插入值为 e 的元素）
这是顺序表最复杂的操作之一,步骤如下：
- 检查表是否已满（
length == MAXSIZE）。 - 检查插入位置
i是否合法（1 <= i <= length + 1）。 - 将第
i个位置及之后的所有元素向后移动一位。 - 将新元素
e放入第i个位置。 - 表长
length加 1。
// 在顺序表 L 的第 i 个位置前插入新元素 e
// i 的范围是 1 到 length+1
int ListInsert(SqList *L, int i, ElemType e) {
// 1. 检查表是否已满
if (L->length >= MAXSIZE) {
printf("Error: List is full.\n");
return 0; // 插入失败
}
// 2. 检查插入位置 i 是否合法 (i 从 1 开始计数)
if (i < 1 || i > L->length + 1) {
printf("Error: Invalid position.\n");
return 0; // 插入失败
}
// 3. 将第 i 个位置及之后的所有元素向后移动一位
// 注意：循环要从后往前移动，避免数据覆盖
for (int j = L->length - 1; j >= i - 1; j--) {
L->data[j + 1] = L->data[j];
}
// 4. 将新元素放入第 i 个位置
L->data[i - 1] = e; // C语言数组下标从0开始
// 5. 表长加 1
L->length++;
return 1; // 插入成功
}
删除元素（删除第 i 个位置的元素）
步骤如下：
- 检查表是否为空（
length == 0）。 - 检查删除位置
i是否合法（1 <= i <= length）。 - 将第
i+1个位置及之后的所有元素向前移动一位,覆盖掉被删除的元素。 - 表长
length减 1。
// 删除顺序表 L 中第 i 个位置的元素，并用 e 返回其值
int ListDelete(SqList *L, int i, ElemType *e) {
// 1. 检查表是否为空
if (L->length == 0) {
printf("Error: List is empty.\n");
return 0; // 删除失败
}
// 2. 检查删除位置 i 是否合法
if (i < 1 || i > L->length) {
printf("Error: Invalid position.\n");
return 0; // 删除失败
}
// 3. 将被删除的元素值存入 e
*e = L->data[i - 1];
// 4. 将第 i+1 个位置及之后的所有元素向前移动一位
for (int j = i; j < L->length; j++) {
L->data[j - 1] = L->data[j];
}
// 5. 表长减 1
L->length--;
return 1; // 删除成功
}
按值查找
查找第一个值为 e 的元素，并返回其位置（从1开始计数），如果找不到,返回0。
// 在顺序表 L 中查找第一个值为 e 的元素，并返回其位置
int LocateElem(SqList L, ElemType e) {
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) {
return i + 1; // 返回位置，从1开始计数
}
}
return 0; // 未找到
}
按位查找
获取第 i 个位置的元素值。
// 获取顺序表 L 中第 i 个位置的元素值
int GetElem(SqList L, int i, ElemType *e) {
// 检查位置是否合法
if (i < 1 || i > L.length) {
printf("Error: Invalid position.\n");
return 0; // 获取失败
}
*e = L.data[i - 1];
return 1; // 获取成功
}
打印顺序表
void PrintList(SqList L) {
printf("List elements: ");
for (int i = 0; i < L.length; i++) {
printf("%d ", L.data[i]);
}
printf("\n");
}
3 完整示例代码（顺序表）
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef int ElemType;
typedef struct {
ElemType data[MAXSIZE];
int length;
} SqList;
// ... (这里插入上面定义的所有函数: InitList, ListInsert, ListDelete, LocateElem, GetElem, PrintList)
int main() {
SqList L;
ElemType e;
// 1. 初始化
InitList(&L);
printf("List initialized. Length: %d\n", L.length);
// 2. 插入元素
ListInsert(&L, 1, 10); // 在位置1插入10
ListInsert(&L, 2, 20); // 在位置2插入20
ListInsert(&L, 3, 30); // 在位置3插入30
ListInsert(&L, 2, 15); // 在位置2插入15
PrintList(L); // 预期输出: 10 15 20 30
// 3. 按值查找
int pos = LocateElem(L, 20);
if (pos) {
printf("Element 20 found at position: %d\n", pos);
} else {
printf("Element 20 not found.\n");
}
// 4. 按位查找
if (GetElem(L, 3, &e)) {
printf("Element at position 3 is: %d\n", e);
}
// 5. 删除元素
if (ListDelete(&L, 2, &e)) {
printf("Deleted element: %d\n", e);
PrintList(L); // 预期输出: 10 20 30
}
return 0;
}
基于链表的线性表（单链表）
链表由一系列节点组成，每个节点包含数据域和指向下一个节点的指针，它在内存中不要求连续存储，这使得它的插入和删除操作非常高效，但随机访问（查找第 i 个元素）需要从头遍历,效率较低。
1 定义链表节点结构体
#include <stdio.h>
#include <stdlib.h>
// 定义元素类型
typedef int ElemType;
// 定义链表节点
typedef struct LNode {
ElemType data; // 数据域
struct LNode *next; // 指针域，指向下一个节点
} LNode, *LinkList; // LinkList 是指向 LNode 结构体的指针，代表链表的头指针
2 基本操作实现
初始化链表（创建头节点）
头节点是一个不存储实际数据的节点，它的存在是为了统一处理链表的头操作,使代码更简洁。
// 初始化链表，创建一个头节点
void InitList(LinkList *L) {
*L = (LinkList)malloc(sizeof(LNode));
if (*L == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
(*L)->next = NULL; // 头节点的 next 指针为 NULL，表示空链表
}
在头部插入节点（头插法）
// 在链表头部插入一个值为 e 的新节点
void HeadInsert(LinkList L, ElemType e) {
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = L->next; // 新节点的 next 指向原来的第一个节点
L->next = s; // 头节点的 next 指向新节点
}
在尾部插入节点（尾插法）
// 在链表尾部插入一个值为 e 的新节点
void TailInsert(LinkList L, ElemType e) {
LNode *p = L; // p 指向头节点，从头开始遍历
while (p->next != NULL) { // 找到最后一个节点
p = p->next;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = NULL; // 新节点是最后一个节点
p->next = s; // 将最后一个节点的 next 指向新节点
}
在第 i 个位置前插入节点
步骤：
- 找到第
i-1个位置的节点p。 - 检查
p是否存在（p != NULL）。 - 创建新节点
s。 - 将
s的next指向p的下一个节点。 - 将
p的next指向s。
// 在链表 L 的第 i 个位置前插入值为 e 的新节点
int ListInsert(LinkList L, int i, ElemType e) {
LNode *p = L; // p 指向头节点
int j = 0; // j 从 0 开始，因为头节点是第 0 个节点
// 寻找第 i-1 个节点，p 指向它
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
// p 为 NULL 或 i < 1，则位置不合法
if (p == NULL || i < 1) {
printf("Error: Invalid position.\n");
return 0;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}
删除第 i 个位置的节点
步骤：
- 找到第
i-1个节点p。 - 检查
p的下一个节点是否存在。 - 用指针
q指向要删除的节点（p->next）。 - 将
p的next指向q的下一个节点。 - 释放
q的内存。
// 删除链表 L 中第 i 个位置的节点，并用 e 返回其值
int ListDelete(LinkList L, int i, ElemType *e) {
LNode *p = L; // p 指向头节点
int j = 0;
// 寻找第 i-1 个节点
while (p->next != NULL && j < i - 1) {
p = p->next;
j++;
}
// p->next 为 NULL 或 i < 1，则位置不合法
if (p->next == NULL || i < 1) {
printf("Error: Invalid position.\n");
return 0;
}
LNode *q = p->next; // q 指向要删除的节点
*e = q->data;
p->next = q->next; // 从链表中移除 q
free(q); // 释放 q 的内存
return 1;
}
按值查找
// 在链表 L 中查找第一个值为 e 的节点，并返回其指针
LNode* LocateElem(LinkList L, ElemType e) {
LNode *p = L->next; // 从第一个实际数据节点开始
while (p != NULL) {
if (p->data == e) {
return p;
}
p = p->next;
}
return NULL; // 未找到
}
打印链表
void PrintList(LinkList L) {
LNode *p = L->next; // 从第一个实际数据节点开始
printf("List elements: ");
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
3 完整示例代码（单链表）
#include <stdio.h>
#include <stdlib.h>
// ... (这里插入上面定义的所有结构体和函数: LNode, LinkList, InitList, HeadInsert, TailInsert, ListInsert, ListDelete, LocateElem, PrintList)
int main() {
LinkList L;
ElemType e;
// 1. 初始化
InitList(&L);
printf("List initialized.\n");
// 2. 头插法
HeadInsert(L, 10);
HeadInsert(L, 20);
HeadInsert(L, 30);
PrintList(L); // 预期输出: 30 20 10
// 3. 尾插法
TailInsert(L, 40);
TailInsert(L, 50);
PrintList(L); // 预期输出: 30 20 10 40 50
// 4. 在指定位置插入
ListInsert(L, 3, 25); // 在第3个位置插入25
PrintList(L); // 预期输出: 30 20 25 10 40 50
// 5. 删除指定位置的节点
if (ListDelete(L, 4, &e)) {
printf("Deleted element: %d\n", e); // 预期输出 10
PrintList(L); // 预期输出: 30 20 25 40 50
}
// 6. 按值查找
LNode *found = LocateElem(L, 40);
if (found) {
printf("Element 40 found.\n");
} else {
printf("Element 40 not found.\n");
}
return 0;
}
总结与对比
| 特性 | 顺序表 (数组实现) | 链表 (链式实现) |
|---|---|---|
| 存储空间 | 连续，需要预分配大小（静态）或动态分配（动态数组） | 不连续，按需分配 |
| 访问元素 | O(1)，支持随机访问 | O(n)，需要从头遍历 |
| 插入/删除 | O(n)，平均需要移动一半的元素 | O(1)，只需修改指针（已知插入/删除位置的前驱节点） |
| 内存使用 | 可能存在空间浪费（预分配但未用完） | 每个节点都需要额外的指针域，空间开销稍大 |
| 适用场景 | 元素数量固定或变化不大，频繁进行查找操作 | 元素数量变化频繁，频繁进行插入和删除操作 |
选择哪种实现方式取决于你的具体应用场景，如果数据量不大且需要频繁随机访问，顺序表是更好的选择，如果数据量变化大且插入删除操作频繁,链表则更合适。
