叠甲如有侵权请联系内容都是自己学习的总结一定不全面仅当互相交流轻点骂我也只是站在巨人肩膀上的一个小卡拉米已老实求放过一、栈Stack1. 核心概念栈是只允许在一端进行插入和删除操作的线性表。允许操作的一端称为栈顶Top固定的另一端称为栈底Bottom核心特性后进先出LIFO, Last In First Out—— 最后入栈的元素最先被取出空栈不含任何元素的栈2. 基本操作ADT 定义栈的所有操作都围绕栈顶进行单步时间复杂度均为 O(1)操作功能说明InitStack(S)初始化一个空栈Push(S, x)元素 x 入栈插入到栈顶Pop(S, x)栈顶元素出栈用 x 返回其值GetTop(S, x)读取栈顶元素不删除StackEmpty(S)判断栈是否为空StackSize(S)返回栈中元素个数DestroyStack(S)销毁栈释放空间3. 两种存储实现1顺序栈数组实现用连续数组存储元素搭配top变量标记栈顶下标是最常用的实现方式。结构体定义C 语言#define MaxSize 100 // 栈的最大容量 typedef struct { int data[MaxSize]; // 存储栈元素 int top; // 栈顶指针初始值为-1表示空栈 } SqStack;核心操作实现初始化S.top -1;入栈先移动栈顶指针再赋值bool Push(SqStack S, int x) { if (S.top MaxSize - 1) return false; // 栈满上溢 S.data[S.top] x; return true; }出栈先取值再移动栈顶指针bool Pop(SqStack S, int x) { if (S.top -1) return false; // 栈空下溢 x S.data[S.top--]; return true; }读栈顶x S.data[S.top];判空return S.top -1;注意也存在top初始为 0 的实现此时栈顶元素为data[top-1]入栈先赋值再top。考研主流写法为top-1。2链式栈单链表实现用单链表存储链表头部作为栈顶入栈用头插法出栈用头删法天然无栈满限制。结构体定义typedef struct LinkNode { int data; struct LinkNode *next; } LinkNode, *LiStack;核心特点入栈、出栈均为 O(1)无需遍历适合元素数量波动大、无法预估容量的场景缺点每个节点需额外存储指针存在空间开销n 个不同元素依次入栈合法出栈序列的总数为卡特兰数//slist.h #pragma once #includestdio.h #includeassert.h #includestdlib.h typedef int SLTDataType; typedef struct SlitNode { SLTDataType data; struct SLTNode* next; }SLTNode; //初始化 void SLPInit(SLTNode* phead); //打印 void SLTPrint(SLTNode*phead); //头插 void SLPushFront(SLTNode** phead, SLTDataType x); //尾插 void SLPushBack(SLTNode** phead, SLTDataType x); //头删 void DestroyFront(SLTNode** phead); //尾删 void DestroyBack(SLTNode** phead); //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //修改 void SLTChange(SLTNode* phead, SLTDataType x, SLTDataType y); //销毁 void SLTDestroy(SLTNode** phead); //中间位置插入 void SLTIsert(SLTNode* phead, SLTDataType x , SLTDataType y);//slist.c #includeslist.h //初始化 void SLPInit(SLTNode* phead) { phead-data 0; phead-next NULL; } void SLTPrint(SLTNode* phead) { SLTNode* cur phead; while (cur) { printf(%d-, cur-data); cur cur-next; } printf(NULL\n); } SLTNode* newnode(SLTDataType x) { SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); if (newnodeNULL) { perror(malloc faild:); return NULL; } newnode-data x; newnode-next NULL; return newnode; } void SLPushFront(SLTNode** phead, SLTDataType x) { SLTNode* cur newnode(x); if (*phead NULL) { *phead cur; } else { cur-next *phead; *phead cur; } } void SLPushBack(SLTNode** phead, SLTDataType x) { SLTNode* cur newnode(x); if (*phead NULL) { *phead cur; } else { SLTNode* tial *phead; while (tial-next!NULL) { tial tial-next; } tial-next cur; } } void DestroyFront(SLTNode ** phead) { assert(*phead); if ((*phead)-next NULL) { free(*phead); *phead NULL; } else { SLTNode* cur *phead; *phead (*phead)-next; free(cur); cur NULL; } } void DestroyBack(SLTNode** phead) { assert(*phead); if ((*phead)-next NULL) { free(*phead); *phead NULL; } else { SLTNode* tail *phead; SLTNode* cur NULL; while (tail-next) { cur tail; tail tail-next; } free(tail); tail NULL; cur-next NULL; } } //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { assert(phead); SLTNode* cur phead; while (cur) { if (cur-data x) { return cur; } cur cur-next; } return NULL; } void SLTChange(SLTNode* phead, SLTDataType x, SLTDataType y) { assert(phead); SLTNode* node SLTFind(phead, x); node-data y; } void SLTDestroy(SLTNode** phead) { assert(*phead); SLTNode* cur *phead; while (cur) { cur (cur)-next; free(*phead); *phead cur; } free(cur); free(*phead); *phead NULL; } //中间位置插入 void SLTIsert(SLTNode* phead, SLTDataType x, SLTDataType y) { SLTNode* cur NULL; SLTNode* node SLTFind(phead, x); SLTNode* new newnode(y); cur node-next; node-next new; new-next cur; }//test.c #define _CRT_SECURE_NO_WARNINGS 1 #includeslist.h int main() { SLTNode* list NULL; SLPushFront(list,1); SLPushFront(list,2); SLPushFront(list,3); SLPushFront(list,4); //SLPushBack(list, 5); //SLPushBack(list, 6); //SLPushBack(list, 7); /*DestroyFront(list); SLTPrint(list); DestroyFront(list); SLTPrint(list); DestroyFront(list); SLTPrint(list); DestroyFront(list); SLTPrint(list); DestroyFront(list); SLTPrint(list);*/ //DestroyBack(list); //SLTPrint(list); //DestroyBack(list); //SLTPrint(list); //DestroyBack(list); //SLTPrint(list); //DestroyBack(list); /*SLTPrint(list); SLTChange(list,3,6); SLTPrint(list); SLTDestroy(list); SLTPrint(list);*/ SLTPrint(list); SLTIsert(list,4, 5); SLTPrint(list); return 0; }二、队列Queue1. 核心概念队列是只允许在一端插入、另一端删除的线性表。插入端称为队尾Rear删除端称为队头Front核心特性先进先出FIFO, First In First Out—— 最先入队的元素最先被取出空队列不含任何元素的队列2. 基本操作ADT 定义所有单步操作时间复杂度均为 O(1)操作功能说明InitQueue(Q)初始化空队列EnQueue(Q, x)元素 x 入队插入队尾DeQueue(Q, x)队头元素出队用 x 返回GetHead(Q, x)读取队头元素不删除QueueEmpty(Q)判断队列是否为空QueueSize(Q)返回队列元素个数DestroyQueue(Q)销毁队列3. 三种存储实现1普通顺序队列存在缺陷用数组存储front 标记队头rear 标记队尾下一个位置。缺陷随着入队出队两个指针不断后移数组前部空间无法复用产生假溢出。2循环队列顺序存储最优解将数组逻辑上视为环形通过取模运算让指针绕回数组开头彻底解决假溢出问题#define MaxSize 100 typedef struct { int data[MaxSize]; int front; // 队头指针指向队头元素 int rear; // 队尾指针指向队尾元素的下一个位置 } SqQueue;初始化Q.front Q.rear 0;核心操作入队bool EnQueue(SqQueue Q, int x) { if (队满) return false; Q.data[Q.rear] x; Q.rear (Q.rear 1) % MaxSize; // 指针循环后移 return true; }出队bool DeQueue(SqQueue Q, int x) { if (队空) return false; x Q.data[Q.front]; Q.front (Q.front 1) % MaxSize; // 指针循环后移 return true; }判空与判满的三种方案重点由于front rear既可能表示空也可能表示满需通过额外规则区分方案判空条件判满条件元素个数计算牺牲 1 个存储单元最常用front rear(rear 1) % MaxSize front(rear - front MaxSize) % MaxSize增加 size 计数器size 0size MaxSize直接返回 size增加 tag 标记位front rear tag 0front rear tag 1结合 tag 推导3链式队列用带头结点的单链表实现同时保存队头和队尾指针入队尾插、出队头删无队满限制。结构体定义typedef struct LinkNode { int data; struct LinkNode *next; } LinkNode; typedef struct { LinkNode *front; // 队头指针 LinkNode *rear; // 队尾指针 } LinkQueue;4. 队列的常见变种双端队列Deque两端都可以入队和出队。进一步分为输入受限、输出受限双端队列。优先队列每次出队返回优先级最高的元素底层由堆实现不属于普通线性队列。//queue.h #pragma once #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h //队列只允许在一端插入数据操作先入先出进行插入操作的一端被称为队尾进行删除的一端叫做对头 //队列可以由数组与链表结构实现但是使用链表的结构更优因为使用数组出队列在数组头出数据效率会比较低下 //单链表 typedef int QDataType; typedef struct QListNode { struct QListNode* next; QDataType data; }QNode; typedef struct Queue { QNode* front; QNode* rear; }Queue; //初始化队列 void QueueInit(Queue* q); //判断队列是否为空 bool QueueEmpty(Queue* q); //对头出队列 void QueuePop(Queue* q); //获取队头的数据 QDataType QueueFront(Queue* q); //获取队尾的数据 QDataType QueueRear(Queue* q); //获取队列有效个数 int QueueSize(Queue* q); //销毁队列 void QueueDestory(Queue* q);//queue.c #define _CRT_SECURE_NO_WARNINGS 1 #includeQueue.h //队列初始化 void QueueInit(Queue* q) { assert(q); q-front NULL; q-rear NULL; } //队尾入队 void QueuePush(Queue* q, QDataType x) { QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc fail\n); return ; } newnode-data x; newnode-next NULL; if (q-rear NULL) { assert(q-front NULL); q-rear newnode; q-front newnode; } else { q-rear-next newnode; q-rear newnode; } } //判断队列是否为空 bool QueueEmpty(Queue* q) { assert(q); return q-frontNULL; } //对头出队列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); if (q-front-next NULL) { free(q-front); q-front NULL; q-rear NULL; } QNode* next q-front-next; free(q-front); q-front next; } //获取对头的数据 QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q-front-data; } //获取队尾的数据 QDataType QueueRear(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q-rear-data; } //获取队列有效个数 int QueueSize(Queue* q) { assert(q); assert(!QueueEmpty(q)); size_t size 0; QNode* cur q-front; while (cur) { size; cur cur-next; } return size; } void QueueDestory(Queue* q) { while (q-front) { QueuePop(q); } }//test.c #define _CRT_SECURE_NO_WARNINGS 1 #includeQueue.h int main() { Queue q; QueueInit(q); QueuePush(q, 1); QueuePush(q, 2); QueuePush(q, 3); QueuePush(q, 4); QueuePush(q, 5); printf(%d\n, QueueFront(q)); printf(%d\n, QueueSize(q)); QueuePop(q); printf(%d\n, QueueFront(q)); printf(%d\n, QueueSize(q)); QueuePop(q); printf(%d\n, QueueRear(q)); printf(%d\n, QueueSize(q)); QueuePop(q); printf(%d\n, QueueRear(q)); QueuePop(q); printf(%d\n, QueueRear(q)); return 0; }三、栈 vs 队列 核心对比维度栈队列核心规则后进先出LIFO先进先出FIFO操作端仅栈顶一端可插入、删除队尾插入、队头删除两端操作顺序存储普通数组即可普通数组有假溢出需用循环队列典型遍历思想深度优先DFS广度优先BFS基础操作复杂度入栈 / 出栈 O(1)入队 / 出队 O(1)#pragma once一、核心作用与原理C/C 的#include本质是文本级别的原样替换编译器会把被包含的头文件内容完整插入到#include所在的位置。如果一个头文件被多次包含比如 A 包含 BC 同时包含 A 和 B那么 B 就会被间接包含两次头文件里的结构体、全局变量、函数声明、宏定义等就会被重复定义直接触发编译报错典型错误redefinition of xxx。#pragma once的工作逻辑很简单写在头文件的最开头编译器第一次处理这个头文件时会标记该文件后续编译过程中只要再遇到#include这个文件编译器会直接跳过不会再次展开文件内容。二、和传统头文件卫士的对比在#pragma once普及之前标准的头文件保护方式是「条件编译卫士」写法如下// 比如 file.h #ifndef FILE_H // 如果没定义过 FILE_H 这个宏 #define FILE_H // 定义这个宏标记文件已被包含 // 头文件的所有代码内容... #endif // 结束条件编译特性#pragma once#ifndef/#define/#endif卫士标准性非 C/C 官方标准属于编译器扩展C/C 标准语法所有编译器 100% 兼容写法一行代码简洁不易写错需要三行且宏名必须全局唯一编译效率更高编译器直接通过文件身份判断无需重复进入文件预处理稍低每次都要进入文件检查宏是否定义潜在风险极端场景同一份头文件有多个物理副本时会被识别为不同文件仍会重复包含宏名如果和其他头文件冲突会导致头文件内容莫名丢失bug 更隐蔽三、使用注意事项必须写在头文件最顶部位于所有代码、其他预处理指令之前否则可能失效。目前主流编译器GCC、Clang、MSVC、MinGW 等全部支持 #pragma once工业界绝大多数项目都在使用兼容性已不再是实际问题。不建议两种方式混用一个头文件写一次 #pragma once 即可。它只能防护「同一个物理文件」的重复包含不能解决不同文件里的同名定义冲突。简单总结#pragma once 是更现代、更省心的头文件保护方案日常写 C/C 项目优先用它就可以。我们用 4 个文件完整复现这个场景例子完全贴合你正在学习的栈结构一步步拆解「重复包含 → 触发报错 → 加保护后修复」的全过程。一、无保护的错误版本我们先写不带任何头文件保护的代码复现编译错误。4 个文件的代码1. stack.h栈结构定义头文件无保护这个文件定义了顺序栈的结构体和函数声明会被其他文件多次引用。// stack.h —— 没有加任何头文件保护 #include stdbool.h #define MaxSize 100 // 定义顺序栈结构体 typedef struct { int data[MaxSize]; int top; } SqStack; // 栈操作函数声明 void InitStack(SqStack *S); bool Push(SqStack *S, int x);2.func1.h功能模块 1依赖栈// func1.h —— 业务模块1需要用到栈结构 #include stack.h void func1(SqStack *S); // 用栈实现功能13. func2.h功能模块 2也依赖栈// func2.h —— 业务模块2也需要用到栈结构 #include stack.h void func2(SqStack *S); // 用栈实现功能24. main.c主程序同时引用两个模块// main.c —— 主程序同时用到两个业务模块 #include stdio.h #include func1.h #include func2.h int main() { SqStack S; InitStack(S); Push(S, 10); func1(S); func2(S); return 0; }为什么会报错手动模拟展开过程#include的本质是文本原样替换。预编译阶段编译器会把所有#include引用的文件内容原封不动地粘贴到当前位置。我们一步步展开main.c先展开#include func1.h→ 里面又包含stack.h→ 第一次粘贴stack.h的全部内容再展开#include func2.h→ 里面又包含stack.h→ 第二次粘贴stack.h的全部内容展开后main.c里相当于出现了两份完全相同的栈结构体定义简化后如下// 第一次展开 stack.h 的内容 #include stdbool.h #define MaxSize 100 typedef struct { int data[MaxSize]; int top; } SqStack; void InitStack(SqStack *S); bool Push(SqStack *S, int x); void func1(SqStack *S); // 第二次展开 stack.h 的内容 #include stdbool.h #define MaxSize 100 // 宏重复定义警告 typedef struct { // 结构体重复定义直接编译错误 int data[MaxSize]; int top; } SqStack; void InitStack(SqStack *S); bool Push(SqStack *S, int x); void func2(SqStack *S);实际编译报错信息用 GCC 编译时会输出典型的重复定义错误error: redefinition of struct SqStack error: redefinition of typedef SqStack warning: MaxSize redefinedC 语言不允许同一个结构体、typedef、全局变量在同一作用域下被定义多次因此直接编译失败。二、加上 #pragma once 修复只需要修改 stack.h在文件最开头加一行 #pragma once#pragma once // 头文件保护本文件只被包含一次 #include stdbool.h #define MaxSize 100 typedef struct { int data[MaxSize]; int top; } SqStack; void InitStack(SqStack *S); bool Push(SqStack *S, int x);修复原理编译器处理头文件时会做标记第一次遇到 #include stack.h正常展开内容并标记「stack.h 已处理过」第二次再遇到 #include stack.h检测到已标记直接跳过整个文件不再展开内容最终 main.c 里只会保留一份 stack.h 的内容结构体、宏都只定义一次编译顺利通过。三、补充说明不是所有重复包含都会报错只有头文件里包含「定义类内容」时才会报错比如结构体定义、全局变量定义、函数实现、宏定义如果头文件只有函数声明重复包含通常不会报错但会增加预编译耗时依然是不良写法。保护的是同一个物理文件#pragma once 只能防止「同一个文件」被多次包含。如果两份内容相同的头文件放在不同路径下它会识别为两个不同文件仍然会重复定义。传统 #ifndef 卫士效果完全一致老式写法是用条件编译实现同等效果原理是通过宏标记是否已包含#ifndef STACK_H // 如果没定义过STACK_H这个宏 #define STACK_H // 定义宏标记文件已进入 #include stdbool.h // ... 头文件全部内容 #endif#includestdbool.h#include stdbool.h是 C 语言中引入布尔类型支持的标准头文件包含语句它的核心作用是让 C 语言可以像其他语言一样使用bool、true、false来表示布尔逻辑让代码的语义更清晰、可读性更强。一、背景C 语言原本没有布尔类型在 C99 标准1999 年之前C 语言没有原生的布尔类型大家普遍用整数来模拟真假用0表示「假」用非0通常是1表示「真」// 没有 stdbool.h 时只能用 int 返回真假 int Push(SqStack S, int x) { if (栈满) return 0; // 0 代表失败/假 // ... return 1; // 1 代表成功/真 }这种写法的问题是int语义不明确读者无法一眼看出这是个布尔标志还是普通整数。二、stdbool.h 到底提供了什么C99 标准新增了原生布尔关键字 _Bool这是 C 语言真正的布尔类型但名字很反直觉。于是配套推出了 stdbool.h 头文件里面通过宏定义做了一层友好的别名包装宏名展开后等价于含义bool_Bool布尔类型名只能存储 0 或 1true整数常量1逻辑真false整数常量0逻辑假也就是说只要你在代码开头加上 #include stdbool.h就可以直接写 bool、true、false编译器会自动替换成 C 原生支持的语法。之前的栈代码就可以写成更易读的版本#include stdbool.h bool Push(SqStack S, int x) { if (S.top MaxSize - 1) return false; // 语义明确失败 S.data[S.top] x; return true; // 语义明确成功 }三、_Bool 类型的特性_Bool 是 C 语言真正的布尔类型和普通 int 有区别它只能存 0 和 1 两个值。如果你给 bool 变量赋一个非 0 的整数比如 5、-3编译器会自动转换成 1保证值只有真假两种状态。bool flag 100; printf(%d, flag); // 输出 1而不是 100四、关键注意事项标准依赖stdbool.h是 C99 及以后标准才有的现代编译器GCC、Clang、MSVC默认都支持无需额外配置。C 不需要它C 语言本身就把bool、true、false作为内置关键字不需要包含任何头文件。只有纯 C 代码才需要#include stdbool.h。本质是宏bool不是 C 语言的原生关键字C23 之前它是stdbool.h定义的宏底层还是_Bool。简单总结这行代码就是给 C 语言补上「布尔类型」的语法糖让代码里的真假判断更直观、更易维护也是写 C 语言数据结构代码时的常用头文件。
我的数据结构4-栈和队列
叠甲如有侵权请联系内容都是自己学习的总结一定不全面仅当互相交流轻点骂我也只是站在巨人肩膀上的一个小卡拉米已老实求放过一、栈Stack1. 核心概念栈是只允许在一端进行插入和删除操作的线性表。允许操作的一端称为栈顶Top固定的另一端称为栈底Bottom核心特性后进先出LIFO, Last In First Out—— 最后入栈的元素最先被取出空栈不含任何元素的栈2. 基本操作ADT 定义栈的所有操作都围绕栈顶进行单步时间复杂度均为 O(1)操作功能说明InitStack(S)初始化一个空栈Push(S, x)元素 x 入栈插入到栈顶Pop(S, x)栈顶元素出栈用 x 返回其值GetTop(S, x)读取栈顶元素不删除StackEmpty(S)判断栈是否为空StackSize(S)返回栈中元素个数DestroyStack(S)销毁栈释放空间3. 两种存储实现1顺序栈数组实现用连续数组存储元素搭配top变量标记栈顶下标是最常用的实现方式。结构体定义C 语言#define MaxSize 100 // 栈的最大容量 typedef struct { int data[MaxSize]; // 存储栈元素 int top; // 栈顶指针初始值为-1表示空栈 } SqStack;核心操作实现初始化S.top -1;入栈先移动栈顶指针再赋值bool Push(SqStack S, int x) { if (S.top MaxSize - 1) return false; // 栈满上溢 S.data[S.top] x; return true; }出栈先取值再移动栈顶指针bool Pop(SqStack S, int x) { if (S.top -1) return false; // 栈空下溢 x S.data[S.top--]; return true; }读栈顶x S.data[S.top];判空return S.top -1;注意也存在top初始为 0 的实现此时栈顶元素为data[top-1]入栈先赋值再top。考研主流写法为top-1。2链式栈单链表实现用单链表存储链表头部作为栈顶入栈用头插法出栈用头删法天然无栈满限制。结构体定义typedef struct LinkNode { int data; struct LinkNode *next; } LinkNode, *LiStack;核心特点入栈、出栈均为 O(1)无需遍历适合元素数量波动大、无法预估容量的场景缺点每个节点需额外存储指针存在空间开销n 个不同元素依次入栈合法出栈序列的总数为卡特兰数//slist.h #pragma once #includestdio.h #includeassert.h #includestdlib.h typedef int SLTDataType; typedef struct SlitNode { SLTDataType data; struct SLTNode* next; }SLTNode; //初始化 void SLPInit(SLTNode* phead); //打印 void SLTPrint(SLTNode*phead); //头插 void SLPushFront(SLTNode** phead, SLTDataType x); //尾插 void SLPushBack(SLTNode** phead, SLTDataType x); //头删 void DestroyFront(SLTNode** phead); //尾删 void DestroyBack(SLTNode** phead); //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //修改 void SLTChange(SLTNode* phead, SLTDataType x, SLTDataType y); //销毁 void SLTDestroy(SLTNode** phead); //中间位置插入 void SLTIsert(SLTNode* phead, SLTDataType x , SLTDataType y);//slist.c #includeslist.h //初始化 void SLPInit(SLTNode* phead) { phead-data 0; phead-next NULL; } void SLTPrint(SLTNode* phead) { SLTNode* cur phead; while (cur) { printf(%d-, cur-data); cur cur-next; } printf(NULL\n); } SLTNode* newnode(SLTDataType x) { SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); if (newnodeNULL) { perror(malloc faild:); return NULL; } newnode-data x; newnode-next NULL; return newnode; } void SLPushFront(SLTNode** phead, SLTDataType x) { SLTNode* cur newnode(x); if (*phead NULL) { *phead cur; } else { cur-next *phead; *phead cur; } } void SLPushBack(SLTNode** phead, SLTDataType x) { SLTNode* cur newnode(x); if (*phead NULL) { *phead cur; } else { SLTNode* tial *phead; while (tial-next!NULL) { tial tial-next; } tial-next cur; } } void DestroyFront(SLTNode ** phead) { assert(*phead); if ((*phead)-next NULL) { free(*phead); *phead NULL; } else { SLTNode* cur *phead; *phead (*phead)-next; free(cur); cur NULL; } } void DestroyBack(SLTNode** phead) { assert(*phead); if ((*phead)-next NULL) { free(*phead); *phead NULL; } else { SLTNode* tail *phead; SLTNode* cur NULL; while (tail-next) { cur tail; tail tail-next; } free(tail); tail NULL; cur-next NULL; } } //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { assert(phead); SLTNode* cur phead; while (cur) { if (cur-data x) { return cur; } cur cur-next; } return NULL; } void SLTChange(SLTNode* phead, SLTDataType x, SLTDataType y) { assert(phead); SLTNode* node SLTFind(phead, x); node-data y; } void SLTDestroy(SLTNode** phead) { assert(*phead); SLTNode* cur *phead; while (cur) { cur (cur)-next; free(*phead); *phead cur; } free(cur); free(*phead); *phead NULL; } //中间位置插入 void SLTIsert(SLTNode* phead, SLTDataType x, SLTDataType y) { SLTNode* cur NULL; SLTNode* node SLTFind(phead, x); SLTNode* new newnode(y); cur node-next; node-next new; new-next cur; }//test.c #define _CRT_SECURE_NO_WARNINGS 1 #includeslist.h int main() { SLTNode* list NULL; SLPushFront(list,1); SLPushFront(list,2); SLPushFront(list,3); SLPushFront(list,4); //SLPushBack(list, 5); //SLPushBack(list, 6); //SLPushBack(list, 7); /*DestroyFront(list); SLTPrint(list); DestroyFront(list); SLTPrint(list); DestroyFront(list); SLTPrint(list); DestroyFront(list); SLTPrint(list); DestroyFront(list); SLTPrint(list);*/ //DestroyBack(list); //SLTPrint(list); //DestroyBack(list); //SLTPrint(list); //DestroyBack(list); //SLTPrint(list); //DestroyBack(list); /*SLTPrint(list); SLTChange(list,3,6); SLTPrint(list); SLTDestroy(list); SLTPrint(list);*/ SLTPrint(list); SLTIsert(list,4, 5); SLTPrint(list); return 0; }二、队列Queue1. 核心概念队列是只允许在一端插入、另一端删除的线性表。插入端称为队尾Rear删除端称为队头Front核心特性先进先出FIFO, First In First Out—— 最先入队的元素最先被取出空队列不含任何元素的队列2. 基本操作ADT 定义所有单步操作时间复杂度均为 O(1)操作功能说明InitQueue(Q)初始化空队列EnQueue(Q, x)元素 x 入队插入队尾DeQueue(Q, x)队头元素出队用 x 返回GetHead(Q, x)读取队头元素不删除QueueEmpty(Q)判断队列是否为空QueueSize(Q)返回队列元素个数DestroyQueue(Q)销毁队列3. 三种存储实现1普通顺序队列存在缺陷用数组存储front 标记队头rear 标记队尾下一个位置。缺陷随着入队出队两个指针不断后移数组前部空间无法复用产生假溢出。2循环队列顺序存储最优解将数组逻辑上视为环形通过取模运算让指针绕回数组开头彻底解决假溢出问题#define MaxSize 100 typedef struct { int data[MaxSize]; int front; // 队头指针指向队头元素 int rear; // 队尾指针指向队尾元素的下一个位置 } SqQueue;初始化Q.front Q.rear 0;核心操作入队bool EnQueue(SqQueue Q, int x) { if (队满) return false; Q.data[Q.rear] x; Q.rear (Q.rear 1) % MaxSize; // 指针循环后移 return true; }出队bool DeQueue(SqQueue Q, int x) { if (队空) return false; x Q.data[Q.front]; Q.front (Q.front 1) % MaxSize; // 指针循环后移 return true; }判空与判满的三种方案重点由于front rear既可能表示空也可能表示满需通过额外规则区分方案判空条件判满条件元素个数计算牺牲 1 个存储单元最常用front rear(rear 1) % MaxSize front(rear - front MaxSize) % MaxSize增加 size 计数器size 0size MaxSize直接返回 size增加 tag 标记位front rear tag 0front rear tag 1结合 tag 推导3链式队列用带头结点的单链表实现同时保存队头和队尾指针入队尾插、出队头删无队满限制。结构体定义typedef struct LinkNode { int data; struct LinkNode *next; } LinkNode; typedef struct { LinkNode *front; // 队头指针 LinkNode *rear; // 队尾指针 } LinkQueue;4. 队列的常见变种双端队列Deque两端都可以入队和出队。进一步分为输入受限、输出受限双端队列。优先队列每次出队返回优先级最高的元素底层由堆实现不属于普通线性队列。//queue.h #pragma once #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h //队列只允许在一端插入数据操作先入先出进行插入操作的一端被称为队尾进行删除的一端叫做对头 //队列可以由数组与链表结构实现但是使用链表的结构更优因为使用数组出队列在数组头出数据效率会比较低下 //单链表 typedef int QDataType; typedef struct QListNode { struct QListNode* next; QDataType data; }QNode; typedef struct Queue { QNode* front; QNode* rear; }Queue; //初始化队列 void QueueInit(Queue* q); //判断队列是否为空 bool QueueEmpty(Queue* q); //对头出队列 void QueuePop(Queue* q); //获取队头的数据 QDataType QueueFront(Queue* q); //获取队尾的数据 QDataType QueueRear(Queue* q); //获取队列有效个数 int QueueSize(Queue* q); //销毁队列 void QueueDestory(Queue* q);//queue.c #define _CRT_SECURE_NO_WARNINGS 1 #includeQueue.h //队列初始化 void QueueInit(Queue* q) { assert(q); q-front NULL; q-rear NULL; } //队尾入队 void QueuePush(Queue* q, QDataType x) { QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc fail\n); return ; } newnode-data x; newnode-next NULL; if (q-rear NULL) { assert(q-front NULL); q-rear newnode; q-front newnode; } else { q-rear-next newnode; q-rear newnode; } } //判断队列是否为空 bool QueueEmpty(Queue* q) { assert(q); return q-frontNULL; } //对头出队列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); if (q-front-next NULL) { free(q-front); q-front NULL; q-rear NULL; } QNode* next q-front-next; free(q-front); q-front next; } //获取对头的数据 QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q-front-data; } //获取队尾的数据 QDataType QueueRear(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q-rear-data; } //获取队列有效个数 int QueueSize(Queue* q) { assert(q); assert(!QueueEmpty(q)); size_t size 0; QNode* cur q-front; while (cur) { size; cur cur-next; } return size; } void QueueDestory(Queue* q) { while (q-front) { QueuePop(q); } }//test.c #define _CRT_SECURE_NO_WARNINGS 1 #includeQueue.h int main() { Queue q; QueueInit(q); QueuePush(q, 1); QueuePush(q, 2); QueuePush(q, 3); QueuePush(q, 4); QueuePush(q, 5); printf(%d\n, QueueFront(q)); printf(%d\n, QueueSize(q)); QueuePop(q); printf(%d\n, QueueFront(q)); printf(%d\n, QueueSize(q)); QueuePop(q); printf(%d\n, QueueRear(q)); printf(%d\n, QueueSize(q)); QueuePop(q); printf(%d\n, QueueRear(q)); QueuePop(q); printf(%d\n, QueueRear(q)); return 0; }三、栈 vs 队列 核心对比维度栈队列核心规则后进先出LIFO先进先出FIFO操作端仅栈顶一端可插入、删除队尾插入、队头删除两端操作顺序存储普通数组即可普通数组有假溢出需用循环队列典型遍历思想深度优先DFS广度优先BFS基础操作复杂度入栈 / 出栈 O(1)入队 / 出队 O(1)#pragma once一、核心作用与原理C/C 的#include本质是文本级别的原样替换编译器会把被包含的头文件内容完整插入到#include所在的位置。如果一个头文件被多次包含比如 A 包含 BC 同时包含 A 和 B那么 B 就会被间接包含两次头文件里的结构体、全局变量、函数声明、宏定义等就会被重复定义直接触发编译报错典型错误redefinition of xxx。#pragma once的工作逻辑很简单写在头文件的最开头编译器第一次处理这个头文件时会标记该文件后续编译过程中只要再遇到#include这个文件编译器会直接跳过不会再次展开文件内容。二、和传统头文件卫士的对比在#pragma once普及之前标准的头文件保护方式是「条件编译卫士」写法如下// 比如 file.h #ifndef FILE_H // 如果没定义过 FILE_H 这个宏 #define FILE_H // 定义这个宏标记文件已被包含 // 头文件的所有代码内容... #endif // 结束条件编译特性#pragma once#ifndef/#define/#endif卫士标准性非 C/C 官方标准属于编译器扩展C/C 标准语法所有编译器 100% 兼容写法一行代码简洁不易写错需要三行且宏名必须全局唯一编译效率更高编译器直接通过文件身份判断无需重复进入文件预处理稍低每次都要进入文件检查宏是否定义潜在风险极端场景同一份头文件有多个物理副本时会被识别为不同文件仍会重复包含宏名如果和其他头文件冲突会导致头文件内容莫名丢失bug 更隐蔽三、使用注意事项必须写在头文件最顶部位于所有代码、其他预处理指令之前否则可能失效。目前主流编译器GCC、Clang、MSVC、MinGW 等全部支持 #pragma once工业界绝大多数项目都在使用兼容性已不再是实际问题。不建议两种方式混用一个头文件写一次 #pragma once 即可。它只能防护「同一个物理文件」的重复包含不能解决不同文件里的同名定义冲突。简单总结#pragma once 是更现代、更省心的头文件保护方案日常写 C/C 项目优先用它就可以。我们用 4 个文件完整复现这个场景例子完全贴合你正在学习的栈结构一步步拆解「重复包含 → 触发报错 → 加保护后修复」的全过程。一、无保护的错误版本我们先写不带任何头文件保护的代码复现编译错误。4 个文件的代码1. stack.h栈结构定义头文件无保护这个文件定义了顺序栈的结构体和函数声明会被其他文件多次引用。// stack.h —— 没有加任何头文件保护 #include stdbool.h #define MaxSize 100 // 定义顺序栈结构体 typedef struct { int data[MaxSize]; int top; } SqStack; // 栈操作函数声明 void InitStack(SqStack *S); bool Push(SqStack *S, int x);2.func1.h功能模块 1依赖栈// func1.h —— 业务模块1需要用到栈结构 #include stack.h void func1(SqStack *S); // 用栈实现功能13. func2.h功能模块 2也依赖栈// func2.h —— 业务模块2也需要用到栈结构 #include stack.h void func2(SqStack *S); // 用栈实现功能24. main.c主程序同时引用两个模块// main.c —— 主程序同时用到两个业务模块 #include stdio.h #include func1.h #include func2.h int main() { SqStack S; InitStack(S); Push(S, 10); func1(S); func2(S); return 0; }为什么会报错手动模拟展开过程#include的本质是文本原样替换。预编译阶段编译器会把所有#include引用的文件内容原封不动地粘贴到当前位置。我们一步步展开main.c先展开#include func1.h→ 里面又包含stack.h→ 第一次粘贴stack.h的全部内容再展开#include func2.h→ 里面又包含stack.h→ 第二次粘贴stack.h的全部内容展开后main.c里相当于出现了两份完全相同的栈结构体定义简化后如下// 第一次展开 stack.h 的内容 #include stdbool.h #define MaxSize 100 typedef struct { int data[MaxSize]; int top; } SqStack; void InitStack(SqStack *S); bool Push(SqStack *S, int x); void func1(SqStack *S); // 第二次展开 stack.h 的内容 #include stdbool.h #define MaxSize 100 // 宏重复定义警告 typedef struct { // 结构体重复定义直接编译错误 int data[MaxSize]; int top; } SqStack; void InitStack(SqStack *S); bool Push(SqStack *S, int x); void func2(SqStack *S);实际编译报错信息用 GCC 编译时会输出典型的重复定义错误error: redefinition of struct SqStack error: redefinition of typedef SqStack warning: MaxSize redefinedC 语言不允许同一个结构体、typedef、全局变量在同一作用域下被定义多次因此直接编译失败。二、加上 #pragma once 修复只需要修改 stack.h在文件最开头加一行 #pragma once#pragma once // 头文件保护本文件只被包含一次 #include stdbool.h #define MaxSize 100 typedef struct { int data[MaxSize]; int top; } SqStack; void InitStack(SqStack *S); bool Push(SqStack *S, int x);修复原理编译器处理头文件时会做标记第一次遇到 #include stack.h正常展开内容并标记「stack.h 已处理过」第二次再遇到 #include stack.h检测到已标记直接跳过整个文件不再展开内容最终 main.c 里只会保留一份 stack.h 的内容结构体、宏都只定义一次编译顺利通过。三、补充说明不是所有重复包含都会报错只有头文件里包含「定义类内容」时才会报错比如结构体定义、全局变量定义、函数实现、宏定义如果头文件只有函数声明重复包含通常不会报错但会增加预编译耗时依然是不良写法。保护的是同一个物理文件#pragma once 只能防止「同一个文件」被多次包含。如果两份内容相同的头文件放在不同路径下它会识别为两个不同文件仍然会重复定义。传统 #ifndef 卫士效果完全一致老式写法是用条件编译实现同等效果原理是通过宏标记是否已包含#ifndef STACK_H // 如果没定义过STACK_H这个宏 #define STACK_H // 定义宏标记文件已进入 #include stdbool.h // ... 头文件全部内容 #endif#includestdbool.h#include stdbool.h是 C 语言中引入布尔类型支持的标准头文件包含语句它的核心作用是让 C 语言可以像其他语言一样使用bool、true、false来表示布尔逻辑让代码的语义更清晰、可读性更强。一、背景C 语言原本没有布尔类型在 C99 标准1999 年之前C 语言没有原生的布尔类型大家普遍用整数来模拟真假用0表示「假」用非0通常是1表示「真」// 没有 stdbool.h 时只能用 int 返回真假 int Push(SqStack S, int x) { if (栈满) return 0; // 0 代表失败/假 // ... return 1; // 1 代表成功/真 }这种写法的问题是int语义不明确读者无法一眼看出这是个布尔标志还是普通整数。二、stdbool.h 到底提供了什么C99 标准新增了原生布尔关键字 _Bool这是 C 语言真正的布尔类型但名字很反直觉。于是配套推出了 stdbool.h 头文件里面通过宏定义做了一层友好的别名包装宏名展开后等价于含义bool_Bool布尔类型名只能存储 0 或 1true整数常量1逻辑真false整数常量0逻辑假也就是说只要你在代码开头加上 #include stdbool.h就可以直接写 bool、true、false编译器会自动替换成 C 原生支持的语法。之前的栈代码就可以写成更易读的版本#include stdbool.h bool Push(SqStack S, int x) { if (S.top MaxSize - 1) return false; // 语义明确失败 S.data[S.top] x; return true; // 语义明确成功 }三、_Bool 类型的特性_Bool 是 C 语言真正的布尔类型和普通 int 有区别它只能存 0 和 1 两个值。如果你给 bool 变量赋一个非 0 的整数比如 5、-3编译器会自动转换成 1保证值只有真假两种状态。bool flag 100; printf(%d, flag); // 输出 1而不是 100四、关键注意事项标准依赖stdbool.h是 C99 及以后标准才有的现代编译器GCC、Clang、MSVC默认都支持无需额外配置。C 不需要它C 语言本身就把bool、true、false作为内置关键字不需要包含任何头文件。只有纯 C 代码才需要#include stdbool.h。本质是宏bool不是 C 语言的原生关键字C23 之前它是stdbool.h定义的宏底层还是_Bool。简单总结这行代码就是给 C 语言补上「布尔类型」的语法糖让代码里的真假判断更直观、更易维护也是写 C 语言数据结构代码时的常用头文件。
