)
目录
顺序表
基本概念
核心特性
代码实现
动态分配顺序表
静态分配顺序表
单链表
基本概念
核心特性
代码实现
带头结点的单链表
不带头结点的单链表
顺序栈
基本概念
核心特性
代码实现
共享栈
基本概念
核心特性
代码实现
链栈
基本概念
链栈的核心特性
代码实现
带头结点的链栈
不带头结点的链栈
顺序表
基本概念
顺序表是一种线性表的物理存储结构，其数据元素按照逻辑顺序依次存储在一组地址连续的存储单元中。通常采用数组实现，通过下标直接访问元素，逻辑相邻的元素在物理位置上也相邻。
核心特性
连续存储
所有元素存储在内存中的连续空间，通过首地址和偏移量可直接定位任意元素，支持随机访问（时间复杂度为 O(1)）。
预分配空间
需预先分配固定大小的存储空间，可能因容量不足导致扩容操作（需复制全部元素），或因空间闲置造成浪费。
操作效率
- 插入/删除：平均需移动半数元素，时间复杂度为 O(n)。
- 查找：按值查找为 O(n)，按索引查找为 O(1)。
静态与动态
- 静态顺序表：容量固定，如
int data[100]。 - 动态顺序表：支持扩容（如 C++ 的
vector），但扩容可能引发性能开销。
代码实现
动态分配顺序表
#include <stdio.h> #include <stdlib.h> // 初始分配容量 #define InitSize 10 // 动态顺序表结构定义（408 标准写法） typedef struct { // 动态分配数组指针 int *data; // 最大容量 int MaxSize; // 当前长度 int length; } SqList; //--------------------------- // 1. 初始化顺序表 //--------------------------- int InitList(SqList *L) { // 动态申请内存 L->data = (int *)malloc(InitSize * sizeof(int)); // 内存分配失败直接退出（考试可写可不写，写了更严谨） if (L->data == NULL) return 0; L->MaxSize = InitSize; L->length = 0; return 1; } //--------------------------- // 2. 动态扩容（408 必考点） //--------------------------- int IncreaseSize(SqList *L, int len) { // 临时指针保存原数组 int *p = L->data; // 申请更大空间 L->data = (int *)malloc((L->MaxSize + len) * sizeof(int)); if (L->data == NULL) return 0; // 复制原数据 for (int i = 0; i < L->length; i++) L->data[i] = p[i]; L->MaxSize += len; // 释放原空间 free(p); return 1; } //--------------------------- // 3. 插入元素（位序 i，元素 e） //--------------------------- int ListInsert(SqList *L, int i, int e) { // 判断 i 合法性 if (i < 1 || i > L->length + 1) return 0; // 满了就扩容（动态顺序表核心） if (L->length >= L->MaxSize) IncreaseSize(L, InitSize); // 元素后移 for (int j = L->length; j >= i; j--) L->data[j] = L->data[j - 1]; L->data[i - 1] = e; L->length++; return 1; } //--------------------------- // 4. 删除元素（位序 i，用 e 返回） //--------------------------- int ListDelete(SqList *L, int i, int *e) { if (i < 1 || i > L->length) return 0; *e = L->data[i - 1]; // 元素前移 for (int j = i; j < L->length; j++) L->data[j - 1] = L->data[j]; L->length--; return 1; } //--------------------------- // 5. 按位取值（i 位序，e 带回值） //--------------------------- int GetElem(SqList L, int i, int *e) { if (i < 1 || i > L.length) return 0; *e = L.data[i - 1]; return 1; } //--------------------------- // 6. 按值查找（返回位序） //--------------------------- int LocateElem(SqList L, int e) { for (int i = 0; i < L.length; i++) { if (L.data[i] == e) return i + 1; } return 0; } //--------------------------- // 7. 销毁表 //--------------------------- void DestroyList(SqList *L) { free(L->data); L->data = NULL; L->MaxSize = 0; L->length = 0; } //--------------------------- // 8. 打印表（辅助） //--------------------------- void PrintList(SqList L) { for (int i = 0; i < L.length; i++) printf("%d ", L.data[i]); printf("\n"); } //--------------------------- // 测试主函数 //--------------------------- int main() { SqList L; // 1. 初始化 InitList(&L); printf("1. 初始化成功\n"); // 2. 插入元素 ListInsert(&L, 1, 10); ListInsert(&L, 1, 20); ListInsert(&L, 1, 30); ListInsert(&L, 1, 40); printf("2. 插入后："); PrintList(L); // 40 30 20 10 // 3. 按位查找 int e; GetElem(L, 2, &e); printf("3. 第2个元素 = %d\n", e); // 30 // 4. 按值查找 int pos = LocateElem(L, 20); printf("4. 值为20的位序 = %d\n", pos); // 3 // 5. 删除元素 ListDelete(&L, 2, &e); printf("5. 删除的元素 = %d\n", e); // 30 printf(" 删除后："); PrintList(L); // 40 20 10 // 6. 查看长度 printf("6. 当前表长 = %d\n", L.length); // 3 // 7. 销毁表 DestroyList(&L); printf("7. 销毁成功\n"); return 0; }静态分配顺序表
#include <stdio.h> // 静态分配顺序表（408标准定义） #define MaxSize 10 typedef struct { // 固定长度数组，静态分配 int data[MaxSize]; // 当前元素个数 int length; } SqList; // 1. 初始化 void InitList(SqList *L) { // 初始时没有元素 L->length = 0; } // 2. 插入操作：在第i个位置插入e（i从1开始） int ListInsert(SqList *L, int i, int e) { // 判断插入位置是否合法 if (i < 1 || i > L->length + 1) return 0; // 判断表是否已满 if (L->length >= MaxSize) return 0; // 元素后移 for (int j = L->length; j >= i; j--) { L->data[j] = L->data[j - 1]; } // 插入新元素 L->data[i - 1] = e; L->length++; return 1; } // 3. 删除操作：删除第i个元素，用e返回 int ListDelete(SqList *L, int i, int *e) { if (i < 1 || i > L->length) return 0; *e = L->data[i - 1]; // 元素前移 for (int j = i; j < L->length; j++) { L->data[j - 1] = L->data[j]; } L->length--; return 1; } // 4. 按值查找 int LocateElem(SqList L, int e) { for (int i = 0; i < L.length; i++) { if (L.data[i] == e) // 返回位序（从1开始） return i + 1; } return 0; } // 5. 按位查找 int GetElem(SqList L, int i, int *e) { if (i < 1 || i > L.length) return 0; *e = L.data[i - 1]; return 1; } // 6. 打印顺序表 void PrintList(SqList L) { for (int i = 0; i < L.length; i++) { printf("%d ", L.data[i]); } printf("\n"); } // 测试主函数 int main() { SqList L; InitList(&L); ListInsert(&L, 1, 10); ListInsert(&L, 2, 20); ListInsert(&L, 3, 30); printf("插入后："); PrintList(L); int del; ListDelete(&L, 2, &del); printf("删除元素：%d\n", del); printf("删除后："); PrintList(L); printf("元素30的位序：%d\n", LocateElem(L, 30)); int val; GetElem(L, 1, &val); printf("第1个元素：%d\n", val); return 0; }单链表
基本概念
单链表（Singly Linked List）是一种线性数据结构，由一系列节点（Node）通过指针单向连接组成。每个节点包含两部分：
- 数据域：存储实际数据。
- 指针域：存储指向下一个节点的地址（或称为“后继指针”）。
链表的最后一个节点指针域通常指向NULL，表示链表结束。
核心特性
动态内存分配
链表节点在运行时动态分配内存，无需预先确定存储空间大小，可灵活扩展或收缩。非连续存储
节点在内存中的物理分布不连续，通过指针逻辑连接，避免了数组需要连续内存的限制。单向遍历
仅支持从头节点（Head）开始顺序访问，无法直接反向遍历或随机访问任意节点。插入与删除高效
在已知节点位置的情况下，插入或删除操作的时间复杂度为 $O(1)$，仅需修改指针指向。无容量限制
理论上可无限扩展，只要内存允许，但实际受系统资源约束。
代码实现
带头结点的单链表
#include <stdio.h> #include <stdlib.h> // 408 标准单链表结点定义 typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 初始化带头结点的单链表 bool InitList(LinkList &L) { L = (LNode *)malloc(sizeof(LNode)); if (L == NULL) return false; L->next = NULL; return true; } // 尾插法建立单链表 void CreateList_R(LinkList &L, int a[], int n) { LNode *s, *r; InitList(L); r = L; for (int i = 0; i < n; i++) { s = (LNode *)malloc(sizeof(LNode)); s->data = a[i]; r->next = s; r = s; } r->next = NULL; } // 按位查找第 i 个结点 LNode *GetElem(LinkList L, int i) { if (i < 1) return NULL; LNode *p = L->next; int j = 1; while (p != NULL && j < i) { p = p->next; j++; } return p; } // 按值查找 LNode *LocateElem(LinkList L, int e) { LNode *p = L->next; while (p != NULL && p->data != e) { p = p->next; } return p; } // 在第 i 个位置插入 e bool ListInsert(LinkList &L, int i, int e) { LNode *p = GetElem(L, i - 1); if (p == NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return true; } // 删除第 i 个结点，用 e 返回值 bool ListDelete(LinkList &L, int i, int &e) { LNode *p = GetElem(L, i - 1); if (p == NULL || p->next == NULL) return false; LNode *q = p->next; e = q->data; p->next = q->next; free(q); return true; } // 遍历输出链表 void PrintList(LinkList L) { LNode *p = L->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } // 求链表长度 int ListLength(LinkList L) { int len = 0; LNode *p = L->next; while (p != NULL) { len++; p = p->next; } return len; } // 销毁链表 void DestroyList(LinkList &L) { LNode *p = L, *q; while (p != NULL) { q = p->next; free(p); p = q; } L = NULL; } // 主函数测试 int main() { LinkList L; int a[] = {1, 2, 3, 4, 5}; int e; // 尾插法建表 CreateList_R(L, a, 5); printf("初始链表："); PrintList(L); // 插入 ListInsert(L, 3, 66); printf("在第3位插入66："); PrintList(L); // 删除 ListDelete(L, 2, e); printf("删除第2位元素 %d 后：", e); PrintList(L); // 查找 LNode *p = LocateElem(L, 66); if (p) printf("找到元素：%d\n", p->data); // 长度 printf("链表长度：%d\n", ListLength(L)); DestroyList(L); return 0; }不带头结点的单链表
#include <stdio.h> #include <stdlib.h> // 408 标准单链表结点定义 typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 判断链表是否为空 int IsEmpty(LinkList L) { return L == NULL; } // 求表长 int Length(LinkList L) { int len = 0; LNode *p = L; while (p != NULL) { len++; p = p->next; } return len; } // 按序号查找第i个结点 LNode* GetElem(LinkList L, int i) { if (i < 1) return NULL; int j = 1; LNode *p = L; while (p != NULL && j < i) { p = p->next; j++; } return p; } // 按值查找 LNode* LocateElem(LinkList L, int e) { LNode *p = L; while (p != NULL && p->data != e) { p = p->next; } return p; } // 在第i个位置插入元素e int ListInsert(LinkList &L, int i, int e) { if (i < 1) return 0; // 插入到表头 if (i == 1) { LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = e; s->next = L; L = s; return 1; } LNode *p = GetElem(L, i - 1); if (p == NULL) return 0; LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return 1; } // 删除第i个元素，用e返回值 int ListDelete(LinkList &L, int i, int &e) { if (i < 1) return 0; // 删除表头 if (i == 1) { if (L == NULL) return 0; LNode *p = L; e = p->data; L = L->next; free(p); return 1; } LNode *p = GetElem(L, i - 1); if (p == NULL || p->next == NULL) return 0; LNode *q = p->next; e = q->data; p->next = q->next; free(q); return 1; } // 遍历输出 void PrintList(LinkList L) { LNode *p = L; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } // 销毁链表 void DestroyList(LinkList &L) { LNode *p, *q; p = L; while (p != NULL) { q = p->next; free(p); p = q; } L = NULL; } // 主函数测试 int main() { LinkList L; L = NULL; // 不带头结点，初始为空 // 插入 ListInsert(L, 1, 10); ListInsert(L, 2, 20); ListInsert(L, 1, 5); ListInsert(L, 4, 30); printf("链表内容："); PrintList(L); printf("表长：%d\n", Length(L)); // 删除 int e; ListDelete(L, 2, e); printf("删除第2个元素：%d\n", e); printf("删除后链表："); PrintList(L); // 查找 LNode *p = LocateElem(L, 20); if (p) printf("找到元素20\n"); else printf("未找到20\n"); // 销毁 DestroyList(L); printf("销毁后是否为空：%d\n", IsEmpty(L)); return 0; }顺序栈
基本概念
顺序栈是一种基于数组实现的栈结构，利用连续的内存空间存储数据，遵循“后进先出”（LIFO）原则。栈顶指针（通常为top）动态指向当前栈顶元素的位置，支持压栈（push）和弹栈（pop）操作。
核心特性
- 存储结构：通过数组实现，需预先分配固定大小的内存空间。
- 栈顶指针：初始值为
-1（空栈），插入元素时top递增，删除时递减。 - 时间复杂度：压栈和弹栈操作的时间复杂度均为O(1)。
代码实现
#include <stdio.h> // 考研标准：栈的最大容量（可根据题目修改） #define MaxSize 50 // 顺序栈结构体定义（考研必考写法） typedef struct { // 静态数组存放栈元素 int data[MaxSize]; // 栈顶指针：指向栈顶元素（考研最常用定义方式） int top; } SqStack; // 1. 初始化栈（核心） void InitStack(SqStack *S) { // 栈顶指针置为-1，表示空栈 S->top = -1; } // 2. 判断栈是否为空 int StackEmpty(SqStack S) { // 栈顶为-1 → 空栈，返回1；否则返回0 return S.top == -1; } // 3. 判断栈是否为满 int StackFull(SqStack S) { // 栈顶指向最后一个元素 → 栈满，返回1 return S.top == MaxSize - 1; } // 4. 入栈操作（进栈） int Push(SqStack *S, int e) { // 栈满，入栈失败 if (StackFull(*S)) return 0; // 栈顶指针先+1，再赋值 S->data[++S->top] = e; // 入栈成功 return 1; } // 5. 出栈操作（删除栈顶元素，用e返回值） int Pop(SqStack *S, int *e) { // 栈空，出栈失败 if (StackEmpty(*S)) return 0; // 先取栈顶元素，栈顶指针再-1 *e = S->data[S->top--]; // 出栈成功 return 1; } // 6. 取栈顶元素（不删除） int GetTop(SqStack S, int *e) { // 栈空，取元素失败 if (StackEmpty(S)) return 0; *e = S.data[S.top]; // 取元素成功 return 1; } // 7. 销毁栈（静态栈无需free，仅重置指针即可） void DestroyStack(SqStack *S) { S->top = -1; } // 主函数：测试栈的所有操作（考研答题可写可不写，建议写上） int main() { // 定义一个栈 SqStack S; // 初始化栈 InitStack(&S); // 测试入栈 Push(&S, 10); Push(&S, 20); Push(&S, 30); printf("入栈元素：10,20,30\n"); // 测试取栈顶 int topElem; GetTop(S, &topElem); printf("当前栈顶元素：%d\n", topElem); // 测试出栈 int e; Pop(&S, &e); printf("出栈元素：%d\n", e); GetTop(S, &topElem); printf("出栈后栈顶元素：%d\n", topElem); // 测试判空 if (StackEmpty(S)) printf("栈为空\n"); else printf("栈不为空\n"); // 销毁栈 DestroyStack(&S); return 0; }共享栈
基本概念
共享栈是一种利用同一块内存空间实现两个栈的数据结构。两个栈的栈底分别位于共享内存空间的两端，栈顶向中间生长。当两个栈顶相遇时，表示栈空间已满。
核心特性
空间高效利用
共享栈通过让两个栈共享同一块内存区域，避免了单独分配两块内存可能导致的浪费。尤其当两个栈的实际使用空间动态变化时，能更灵活地利用内存。
双向生长
两个栈的栈顶分别从数组的两端向中间延伸。栈A从下标0开始向高位生长，栈B从下标n-1开始向低位生长。
溢出条件
共享栈的溢出条件为两个栈顶相遇（即top1 + 1 >= top2）。此时无论向哪个栈压入元素都会导致栈满。
代码实现
#include <stdio.h> #include <stdlib.h> // 共享栈最大容量（可根据需求修改） #define MaxSize 10 // 共享栈结构体定义（408标准写法） typedef struct { // 共享存储空间 int data[MaxSize]; // 栈1栈顶指针 int top1; // 栈2栈顶指针 int top2; } ShareStack; //==================== 基本操作 ====================// // 1. 初始化共享栈 void InitStack(ShareStack *S) { // 栈1空栈状态 S->top1 = -1; // 栈2空栈状态 S->top2 = MaxSize; } // 2. 判断共享栈是否为空 // flag=1 判栈1空；flag=2 判栈2空 int StackEmpty(ShareStack S, int flag) { if (flag == 1) { // 栈1空返回1 return S.top1 == -1; } else if (flag == 2) { // 栈2空返回1 return S.top2 == MaxSize; } // 非法标记 return -1; } // 3. 判断共享栈是否满 int StackFull(ShareStack S) { // 标准判满条件 return S.top1 + 1 == S.top2; } // 4. 入栈操作 // flag=1 入栈1；flag=2 入栈2 int Push(ShareStack *S, int flag, int e) { // 栈满，入栈失败 if (StackFull(*S)) { printf("共享栈已满，入栈失败！\n"); return 0; } if (flag == 1) { // 栈1：先移动指针，再入栈 S->data[++S->top1] = e; } else if (flag == 2) { // 栈2：先移动指针，再入栈 S->data[--S->top2] = e; } else { printf("栈编号错误！\n"); return 0; } return 1; } // 5. 出栈操作 // flag=1 出栈1；flag=2 出栈2，e保存出栈元素 int Pop(ShareStack *S, int flag, int *e) { if (flag == 1) { // 栈1空 if (S->top1 == -1) { printf("栈1为空，出栈失败！\n"); return 0; } // 先出栈，再移动指针 *e = S->data[S->top1--]; } else if (flag == 2) { // 栈2空 if (S->top2 == MaxSize) { printf("栈2为空，出栈失败！\n"); return 0; } // 先出栈，再移动指针 *e = S->data[S->top2++]; } else { printf("栈编号错误！\n"); return 0; } return 1; } // 6. 获取栈顶元素（不删除） int GetTop(ShareStack S, int flag, int *e) { if (flag == 1) { if (S.top1 == -1) return 0; *e = S.data[S.top1]; } else if (flag == 2) { if (S.top2 == MaxSize) return 0; *e = S.data[S.top2]; } else return 0; return 1; } //==================== 测试主函数 ====================// int main() { ShareStack S; // 初始化 InitStack(&S); int e; // 栈1入栈 Push(&S, 1, 10); Push(&S, 1, 20); Push(&S, 1, 30); // 栈2入栈 Push(&S, 2, 100); Push(&S, 2, 200); // 栈1出栈 Pop(&S, 1, &e); printf("栈1出栈元素：%d\n", e); // 栈2出栈 Pop(&S, 2, &e); printf("栈2出栈元素：%d\n", e); // 获取栈顶 GetTop(S, 1, &e); printf("栈1栈顶元素：%d\n", e); GetTop(S, 2, &e); printf("栈2栈顶元素：%d\n", e); return 0; }链栈
基本概念
链栈是一种基于链表实现的栈结构，采用动态内存分配方式存储数据。与顺序栈不同，链栈无需预先定义固定容量，通过节点间的指针链接实现元素的入栈和出栈操作。链栈的栈顶通常为链表的头节点，操作均在链表头部完成，保证时间复杂度为O(1)。
链栈的核心特性
动态扩展性
链栈的存储空间随需求动态分配，无需担心栈满问题（除非内存耗尽）。
高效操作
入栈和出栈仅需修改头节点指针，无需移动其他元素，操作效率稳定。
内存灵活性
每个节点独立分配内存，可分散存储，但需额外空间存储指针。
实现关键
- 栈顶指针指向链表头节点。
- 空栈时，栈顶指针为
NULL。 - 节点结构包含数据域和指向下一节点的指针域。
代码实现
带头结点的链栈
#include <stdio.h> #include <stdlib.h> // 链栈结点类型定义 typedef struct StackNode { int data; struct StackNode *next; } StackNode, *StackPtr; // 链栈（仅需栈顶指针，指向头结点） typedef struct { StackPtr top; // 栈顶指针，指向头结点 } LinkStack; // 1. 初始化带头结点的链栈 int InitStack(LinkStack *S) { // 创建头结点 S->top = (StackPtr)malloc(sizeof(StackNode)); if (S->top == NULL) return 0; // 内存分配失败 S->top->next = NULL; // 头结点后继为空 return 1; } // 2. 判断栈空 int StackEmpty(LinkStack S) { // 头结点后无元素即为空 return S.top->next == NULL; } // 3. 入栈（头插法） int Push(LinkStack *S, int e) { StackPtr p = (StackPtr)malloc(sizeof(StackNode)); if (p == NULL) return 0; p->data = e; p->next = S->top->next; // 新结点指向原第一个元素 S->top->next = p; // 头结点指向新结点 return 1; } // 4. 出栈 int Pop(LinkStack *S, int *e) { if (StackEmpty(*S)) return 0; // 栈空 StackPtr p = S->top->next; // p指向待删除结点 *e = p->data; S->top->next = p->next; // 摘链 free(p); return 1; } // 5. 取栈顶元素（不删除） int GetTop(LinkStack S, int *e) { if (StackEmpty(S)) return 0; *e = S.top->next->data; return 1; } // 6. 销毁栈 int DestroyStack(LinkStack *S) { StackPtr p, q; p = S->top; while (p != NULL) { q = p->next; free(p); p = q; } S->top = NULL; return 1; } // 测试主函数 int main() { LinkStack S; int e; InitStack(&S); Push(&S, 10); Push(&S, 20); Push(&S, 30); GetTop(S, &e); printf("栈顶元素：%d\n", e); Pop(&S, &e); printf("出栈元素：%d\n", e); GetTop(S, &e); printf("新栈顶：%d\n", e); printf("栈是否为空：%s\n", StackEmpty(S) ? "是" : "否"); DestroyStack(&S); return 0; }不带头结点的链栈
#include <stdio.h> #include <stdlib.h> typedef struct StackNode { int data; struct StackNode *next; } StackNode, *StackPtr; typedef struct { StackPtr top; } LinkStack; // 初始化 void InitStack(LinkStack *S) { S->top = NULL; } // 判空 int StackEmpty(LinkStack S) { return S.top == NULL; } // 入栈 int Push(LinkStack *S, int e) { StackPtr p = (StackPtr)malloc(sizeof(StackNode)); if (!p) return 0; p->data = e; p->next = S->top; S->top = p; return 1; } // 出栈 int Pop(LinkStack *S, int *e) { if (StackEmpty(*S)) return 0; StackPtr p = S->top; *e = p->data; S->top = p->next; free(p); return 1; } // 取栈顶 int GetTop(LinkStack S, int *e) { if (StackEmpty(S)) return 0; *e = S.top->data; return 1; } // 销毁栈 void DestroyStack(LinkStack *S) { StackPtr p, q; p = S->top; while (p != NULL) { q = p->next; free(p); p = q; } S->top = NULL; // 销毁后置空，避免野指针 } // 测试 int main() { LinkStack S; int e; InitStack(&S); Push(&S, 10); Push(&S, 20); Push(&S, 30); GetTop(S, &e); printf("栈顶：%d\n", e); Pop(&S, &e); printf("出栈：%d\n", e); DestroyStack(&S); // 用完销毁 return 0; }
