企业官网建设流程全解析

如何模仿网站模板,英文网站建设 潍坊,门户网站的发布特点,网络规划方案计划书【数据结构】栈——超详解#xff01;#xff01;#xff01;#xff08;包含栈的实现#xff09;前言一、栈是什么#xff1f;1. 后进先出#xff08;LIFO#xff09;2. 压栈出栈二、栈的实现1. 用什么来实现#xff1f;2. 实现思路3.注意4. 代码实现…【数据结构】栈——超详解包含栈的实现前言一、栈是什么1. 后进先出LIFO2. 压栈出栈二、栈的实现1. 用什么来实现2. 实现思路3.注意4. 代码实现1创建头文件源文件2定义栈定义3栈的初始化初始化4栈的销毁销毁5插入数据入栈6删除数据出栈7获取栈顶元素8获取栈中有效元素个数9检测栈是否为空三、完整代码实现1. Stack.h2. Stack.c3. Test.c结语前言往期我们的学习中讲到了顺序表以及链表它们可以帮我们解决很多问题而类似的数据结构还有很多今天我们就来聊聊——栈一、栈是什么栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。注意本文我们讲的栈是数据结构里的栈而不是在操作系统中提到的栈二者同名不同理相当与两个不同学科的概念大家不要搞混淆了1. 后进先出LIFO那么什么是后进先出呢如图后进先出故名思意就是先进去的数据后出来而后进去的数据先出来就如同枪上的弹夹一样,先压进去的子弹后打出去而后压进去的子弹先打出去2. 压栈出栈压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶入数据在栈顶,出数据也在栈顶二、栈的实现1. 用什么来实现栈的实现一般可以使用数组或者链表实现而相对而言数组的结构实现更优一些。但前面我们讲顺序表的时候提到在顺序表中进行插入删除数据很麻烦那为什么又要用数组呢这就要看到栈的定义了栈只允许在固定的一端进行插入和删除元素操作而在数组中避免了中间数据的插入与删除就是因为数组在尾上插入删除数据的代价比较小所以使用数组来实现栈2. 实现思路这里可以拿顺序表来做参考往期我们详解了顺序表的实现大家感兴趣的可以去看看链接【C语言】数据结构——顺序表超详解!!!包含顺序表的实现)与顺序表同理栈的实现也应该有三名成员1.指向一个数组的指针2.栈内的总元素3.栈内的总容量3.注意但是要十分注意一个点这个点将贯穿我们整段代码注意栈只允许在固定的一端进行插入和删除元素操作当我们在写实现代码时要注意栈只允许在固定的一端进行插入和删除元素操作不能在两端同时进行操作不然就不是栈了要遵循先进后出的基本原则所以在插入数据时我们选择尾插而在取出数据时我们选择头取4. 代码实现本文以创建一个int类型的栈为例1创建头文件源文件之前在讲解扫雷游戏中我就提到:在写复杂程序时要养成写多个头文件源文件的好习惯这样条理就很清晰也不会乱详见【C语言】扫雷游戏详解包含递归变色记录时间等如图:创建了一个“ Stack.h 头文件用于存放用来放函数的声明和一些库函数的头文件创建了一个“ Stack.c 源文件用于用来放函数的定义(栈的主体)还有一个” Test.c 源文件用于测试实现的栈的运行效果2定义栈定义首先我们要定义一个栈代码演示内有注释在头文件“ Stack.h 中写//重定义方便修改类型typedefintSTDataType;//定义栈typedefstructStack{STDataType*a;//数组指针intsize;//总元素intcapacity;//容量}Stack;在定义栈代码中有两个需要注意的点本文是以int类型为例但如果以后要将顺序表修改成char类型或是其他类型一个一个修改就很麻烦所以我们重定义int类型为STDataType,并将接下来代码中的int类型全部写成STDataType这是为了方便我们以后对类型进行修改仅需将int改为其他类型即可在定义栈的同时重定义栈变量名为Stack方便以后使用3栈的初始化初始化定义完栈后肯定要对栈进行初始化内容全部置0 / NULL代码演示内有注释其中 ps 是一个栈指针类型的指针下同在“ Stack.h 头文件中写到// 初始化栈voidStackInit(Stack*ps);在“ Stack.c 源文件中写到// 初始化栈voidStackInit(Stack*ps){//断言空指针assert(ps);ps-aNULL;ps-capacity0;ps-size0;//全部初始化置 0 / NULL}在写栈代码中有一个很重要的点当我们函数在进行传参时可能会传入空指针而我们知道空指针是不能进行解引用的故为了我们的代码更加健壮可以加入assert 断言来判断是否符合条件在之后的代码中也都有关于更加详细的assert 断言介绍可参见下文【C语言】带你层层深入指针——指针详解3野指针、assert等4栈的销毁销毁在我们的程序运行完毕后当然要对栈进行销毁以免占用内存代码演示内有注释其中 ps 是一个栈指针类型的指针下同在“ Stack.h 头文件中写到// 销毁栈voidStackDestroy(Stack*ps);在“ Stack.c 源文件中写到//栈的销毁voidStackDestroy(Stack*ps){assert(ps);//断言空指针free(ps-a);//释放内存ps-aNULL;ps-capacity0;ps-size0;//全部初始化置 0 / NULL}5插入数据入栈怎么插入在入栈时由于栈只允许在固定的一端进行插入和删除元素操作所以在插入时一定是尾插数据空间不够时咋办栈的空间是动态管理的故当栈的空间不足时可再开辟一些空间使用动态增容但是存在一个问题我们到底要开辟多大的空间来使用呢1. 若一次性开辟的空间过大可能会造成空间的浪费2. 若一次性开辟的空间过小就可能会导频繁的开辟空间这样运行的效率就会大大降低经过科学研究发现每次增容 2 倍 3 倍 空间最为合适当原空间为 100 的空间不足时就增容到 200 空间本文选择的是每次增容 2 倍 代码演示内有注释其中 ps 是一个栈指针类型的指针下同在“ Stack.h 头文件中写到// 入栈voidStackPush(Stack*ps,STDataType data);在“ Stack.c 源文件中写到// 入栈voidStackPush(Stack*ps,STDataType data){assert(ps);//断言空指针if(ps-sizeps-capacity)//当sizecapacity时就表示空间不足此时需要增容故进入if语句{//先设置新变量增容后再赋值intnewcapacityps-capacity0?4:2*ps-capacity;//设置一个三目操作符判断原空间是否为 0//当原空间为0时给空间开辟 4 字节当原空间不为0时给空间增容 2倍STDataType*tmp(STDataType*)realloc(ps-a,newcapacity*sizeof(STDataType));//由于是在原空间的基础上给空间增容故我们这里使用 realloc函数 增容//增容大小为上面的 newcapacity *类型大小if(tmpNULL)//加一个 if语句 防止增容失败{perror(realloc);return;}//没有问题后就赋值ps-atmp;ps-capacitynewcapacity;}ps-a[ps-size]data;ps-size;}6删除数据出栈这个很简单直接用下标进行删除数据再对size–即可但要注意栈只允许在固定的一端进行插入和删除元素操作我们在尾端进行插入数据就也要在尾端进行删除数据代码演示内有注释其中 ps 是一个栈指针类型的指针下同在“ Stack.h 头文件中写到// 出栈voidStackPop(Stack*ps);在“ Stack.c 源文件中写到// 出栈voidStackPop(Stack*ps){assert(psps-size0);//断言空指针//断言顺序表不能为空ps-size--;//将元素个数进行 -1 就行//这样也不会影响到后面的 增、删、查、改}7获取栈顶元素这个很简单直接用下标进行访问数据再返回所对应的值但要注意栈只允许在固定的一端进行插入和删除元素操作之前在尾端进行插入删除数据就也要在尾端获取栈顶元素代码演示内有注释其中 ps 是一个栈指针类型的指针下同在“ Stack.h 头文件中写到// 获取栈顶元素STDataTypeStackTop(Stack*ps);在“ Stack.c 源文件中写到// 获取栈顶元素STDataTypeStackTop(Stack*ps){assert(psps-size0);//断言空指针//断言顺序表不能为空returnps-a[ps-size-1];}8获取栈中有效元素个数这个很简单直接返回所对应的值代码演示内有注释其中 ps 是一个栈指针类型的指针下同在“ Stack.h 头文件中写到// 获取栈中有效元素个数intStackSize(Stack*ps);在“ Stack.c 源文件中写到// 获取栈中有效元素个数intStackSize(Stack*ps){assert(ps);//断言空指针returnps-size;}9检测栈是否为空这个很简单如果栈为空返回非零结果如果不为空返回0代码演示内有注释其中 ps 是一个栈指针类型的指针下同在“ Stack.h 头文件中写到// 检测栈是否为空如果为空返回非零结果如果不为空返回0intStackEmpty(Stack*ps);在“ Stack.c 源文件中写到// 检测栈是否为空如果为空返回非零结果如果不为空返回0intStackEmpty(Stack*ps){assert(ps);//断言空指针returnps-size0;}三、完整代码实现1. Stack.h用于存放用来放函数的声明和一些库函数的头文件#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#includestdio.h#includestdlib.h#includestdbool.h#includeassert.h#includesperror.h//重定义方便修改类型typedefintSTDataType;//定义栈typedefstructStack{STDataType*a;//数组指针intsize;//总元素intcapacity;//容量}Stack;// 初始化栈voidStackInit(Stack*ps);// 入栈voidStackPush(Stack*ps,STDataType data);// 出栈voidStackPop(Stack*ps);// 获取栈顶元素STDataTypeStackTop(Stack*ps);// 获取栈中有效元素个数intStackSize(Stack*ps);// 检测栈是否为空如果为空返回非零结果如果不为空返回0intStackEmpty(Stack*ps);// 销毁栈voidStackDestroy(Stack*ps);2. Stack.c用于用来放函数的定义(栈的主体)#includeStack.h// 初始化栈voidStackInit(Stack*ps){//断言空指针assert(ps);ps-aNULL;ps-capacity0;ps-size0;//全部初始化置 0 / NULL}// 入栈voidStackPush(Stack*ps,STDataType data){assert(ps);//断言空指针if(ps-sizeps-capacity)//当sizecapacity时就表示空间不足此时需要增容故进入if语句{//先设置新变量增容后再赋值intnewcapacityps-capacity0?4:2*ps-capacity;//设置一个三目操作符判断原空间是否为 0//当原空间为0时给空间开辟 4 字节当原空间不为0时给空间增容 2倍STDataType*tmp(STDataType*)realloc(ps-a,newcapacity*sizeof(STDataType));//由于是在原空间的基础上给空间增容故我们这里使用 realloc函数 增容//增容大小为上面的 newcapacity *类型大小if(tmpNULL)//加一个 if语句 防止增容失败{perror(realloc);return;}//没有问题后就赋值ps-atmp;ps-capacitynewcapacity;}ps-a[ps-size]data;ps-size;}// 出栈voidStackPop(Stack*ps){assert(psps-size0);//断言空指针//断言顺序表不能为空ps-size--;//将元素个数进行 -1 就行//这样也不会影响到后面的 增、删、查、改}// 获取栈顶元素STDataTypeStackTop(Stack*ps){assert(psps-size0);//断言空指针//断言顺序表不能为空returnps-a[ps-size-1];}// 获取栈中有效元素个数intStackSize(Stack*ps){assert(ps);//断言空指针returnps-size;}// 检测栈是否为空如果为空返回非零结果如果不为空返回0intStackEmpty(Stack*ps){assert(ps);//断言空指针returnps-size0;}// 销毁栈voidStackDestroy(Stack*ps){assert(ps);//断言空指针free(ps-a);//释放内存ps-aNULL;ps-capacity0;ps-size0;//全部初始化置 0 / NULL}3. Test.c用于测试实现的栈的运行效果这里是小编在写代码时写的测试用例#includeStack.hintmain(){Stack S;StackInit(S);StackPush(S,1);StackPush(S,2);StackPush(S,3);StackPush(S,4);StackPush(S,5);StackPush(S,6);StackPop(S);intret1StackTop(S);StackPop(S);intret2StackTop(S);StackPop(S);intret3StackTop(S);printf(%d %d %d,ret1,ret2,ret3);printf(\n\n);StackDestroy(S);return0;}结语本期资料来自于https://legacy.cplusplus.com/OK本期的栈详解到这里就结束了若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持本文有若有不足之处希望各位兄弟们能给出宝贵的意见。谢谢大家新人本期制作不易希望各位兄弟们能动动小手三连走一走支持一下三连必回QwQ