C语言线性表链表

<think>嗯，用户想了解C语言中线性表和链表的实现与操作。首先我需要回忆一下线性表的基本概念。根据引用[1]，线性表是相同类型元素的有序集合，分为顺序存储和链式存储。顺序表用数组实现，元素在内存中连续存放；链表则是通过指针连接的节点，物理位置不一定相邻。 接下来要区分顺序表和链表的实现方法。引用[2]提到链表分为单链表、双向链表等，每个节点包含数据和指针。操作方面，插入和删除在链表中只需修改指针，时间复杂度为O(1)，但查找需要O(n)。顺序表的插入删除需要移动元素，时间复杂度O(n)，但支持随机访问。 用户可能需要具体的代码示例。比如顺序表的结构体定义应该包含数组、长度和容量。引用[3]和[4]给出了C语言的实现步骤，比如初始化时需要分配内存，插入元素时要检查是否越界并移动后续元素。链表的结构体则包含数据域和指向下一个节点的指针。插入节点时要注意指针的修改顺序，避免断链。 还要注意两种结构的优缺点。顺序表适合频繁访问元素，但插入删除效率低；链表适合频繁插入删除，但访问元素需要遍历。用户可能在实际应用中需要根据需求选择合适的结构。 最后，用户可能对基本操作如创建、插入、删除、查找等感兴趣。需要分别给出顺序表和链表的代码示例，并解释关键步骤。比如顺序表插入时从后往前移动元素，链表头插法如何操作指针。同时，要提醒内存管理的注意事项，如动态分配内存后需要释放，避免内存泄漏。 可能还需要补充一些常见问题，比如两种结构的性能比较，应用场景，以及如何优化操作效率。例如，顺序表可以预先分配较大空间减少扩容次数，链表可以添加头结点简化插入删除操作。 总结来说，回答需要结构清晰，先讲概念，再分述两种结构的实现和操作，最后比较优缺点和应用场景。确保代码示例正确，符合C语言语法，并引用相关参考资料。</think>### C语言线性表与链表的实现与操作 #### 一、线性表的基本概念 线性表是由$n(n \geq 0)$个相同类型元素组成的有序集合，支持插入、删除、查找等基本操作[^2]。其存储结构分为： 1. **顺序表**（顺序存储）：元素在内存中连续存放，通过数组实现。 2. **链表**（链式存储）：元素通过指针连接，物理位置不要求相邻。 --- #### 二、顺序表的实现 ##### 1. 结构定义 ```c #define MAXSIZE 100 // 最大容量 typedef struct { int data[MAXSIZE]; // 存储元素的数组 int length; // 当前长度 } SeqList; ``` ##### 2. 核心操作 - **初始化** ```c void InitList(SeqList *L) { L->length = 0; } ``` - **插入元素**（时间复杂度：$O(n)$） ```c int Insert(SeqList *L, int i, int value) { if (L->length == MAXSIZE) return 0; // 表已满 if (i < 1 || i > L->length + 1) return 0; // 位置非法 for (int j = L->length; j >= i; j--) L->data[j] = L->data[j-1]; L->data[i-1] = value; L->length++; return 1; } ``` - **删除元素**（时间复杂度：$O(n)$） ```c int Delete(SeqList *L, int i) { if (i < 1 || i > L->length) return 0; // 位置非法 for (int j = i; j < L->length; j++) L->data[j-1] = L->data[j]; L->length--; return 1; } ``` --- #### 三、链表的实现 ##### 1. 单链表结构定义 ```c typedef struct Node { int data; // 数据域 struct Node *next; // 指针域 } Node, *LinkList; ``` ##### 2. 核心操作 - **头插法建表**（时间复杂度：$O(1)$） ```c void CreateList_Head(LinkList *L, int a[], int n) { *L = (Node *)malloc(sizeof(Node)); (*L)->next = NULL; for (int i = 0; i < n; i++) { Node *p = (Node *)malloc(sizeof(Node)); p->data = a[i]; p->next = (*L)->next; (*L)->next = p; } } ``` - **插入节点**（时间复杂度：$O(1)$） ```c int Insert(LinkList *L, int i, int value) { Node *p = *L; int j = 0; while (p && j < i-1) { // 找到第i-1个节点 p = p->next; j++; } if (!p || j > i-1) return 0; // 位置非法 Node *s = (Node *)malloc(sizeof(Node)); s->data = value; s->next = p->next; p->next = s; return 1; } ``` - **删除节点**（时间复杂度：$O(1)$） ```c int Delete(LinkList *L, int i) { Node *p = *L; int j = 0; while (p->next && j < i-1) { // 找到第i-1个节点 p = p->next; j++; } if (!(p->next) || j > i-1) return 0; // 位置非法 Node *q = p->next; p->next = q->next; free(q); return 1; } ``` --- #### 四、顺序表与链表的对比 | 特性 | 顺序表 | 链表 | |------------|---------------------------|--------------------------| | 存储方式 | 连续内存 | 离散内存（指针连接） | | 访问速度 | $O(1)$（随机访问） | $O(n)$（需遍历） | | 插入/删除 | $O(n)$（需移动元素） | $O(1)$（修改指针） | | 空间扩展 | 需预分配固定大小 | 动态分配（灵活扩展） | --- #### 五、应用场景 1. **顺序表**：适合元素数量固定、频繁访问的场景（如数组遍历）。 2. **链表**：适合频繁插入/删除、元素数量动态变化的场景（如操作系统进程调度队列）[^4]。 ---