考研408数据结构(持续更新中...)

目录顺序表基本概念核心特性代码实现动态分配顺序表静态分配顺序表单链表基本概念核心特性代码实现带头结点的单链表不带头结点的单链表顺序栈基本概念核心特性代码实现共享栈基本概念核心特性代码实现链栈基本概念链栈的核心特性代码实现带头结点的链栈不带头结点的链栈顺序表基本概念顺序表是一种线性表的物理存储结构其数据元素按照逻辑顺序依次存储在一组地址连续的存储单元中。通常采用数组实现通过下标直接访问元素逻辑相邻的元素在物理位置上也相邻。核心特性连续存储所有元素存储在内存中的连续空间通过首地址和偏移量可直接定位任意元素支持随机访问时间复杂度为 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个位置插入ei从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. 判断共享栈是否为空 // flag1 判栈1空flag2 判栈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. 入栈操作 // flag1 入栈1flag2 入栈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. 出栈操作 // flag1 出栈1flag2 出栈2e保存出栈元素 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; }