引言：
在我的全面信息查找的情况下，并没有找到我想要的二叉树的课程，所以咱们接下来要朝刷有关数据结构的题目这一块进军了，等我题目玩的差不多，我们再开始二叉树的学习
一、栈的完整代码
1.头文件：
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //这边还是不要管你下午睡了多久，现在可以把栈自己实现一遍是最重要的 //首先要理解栈的特性，然后第一步就是定义出它的结构体（并且改进一下结构体而已） typedef int STDataType; typedef struct Stack { STDataType* data; //定义完这两个不要懵，其实答案就在眼前（因为需要使你的栈空间是一个动态的东西，所以这边……） int top; int capacity; }ST; //弄完了结构体我们现在就要弄几个主要的接口函数 //首先第一个应该是 //初始化 void StackInit(ST* ps); //销毁 void StackDestory(ST* ps); //栈顶插入 void StackPush(ST* ps, STDataType x); //栈顶删除 void StackPopt(ST* ps); //寻找栈顶(这个肯定是有返回值的) STDataType StackTop(ST* ps); //还有一个就是计算栈的大小 int StackSize(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps);
2.接口实现文件：
#include"Stack.h" //初始化(错误写法) //void StackInit(ST* ps) //{ // //STDataType* data = NULL; 这边怎么敢这样子写的啊 // ps->data = NULL; // //知道了有初始化这个接口，就成功了三分之一了，所以我们不要怕，现在就只是实现一下而已 // int capacity = 0; // int top = 0;//此时这个top的表示会影响到top的位置（因为我们是使用下标来实现我们的栈，座椅下标是从0开始的） // //} void StackInit(ST* ps)//正确的写法 { assert(ps); ps->data = NULL; //这个位置top给0，表示top此时指向的是栈顶数据的下一个 //这个位置top给-1，表示top此时指向的是栈顶数据（就是下标原理：放一个数据top加1，此时-1加1等于0，此时就是我的数据的第一个数据，下标为0，如果top是0，top加1，下标为1，此时top就是表示第二个数据，所以是栈顶数据的下一个） ps->top = 0;//这个位置也可以把ps->top = -1;看我自己（都可以只是表示的意思不一样而已） ps->capacity = 0; } //销毁 void StackDestory(ST* ps) { //销毁是一个技术活，此时想要销毁就要格外的注意了(好像不要注意) free(ps->data); ps->data = NULL; ps->capacity = 0; ps->top = 0; } //栈顶插入 void StackPush(ST* ps, STDataType x) { assert(ps); //此时想要对栈顶进行一个插入，首先肯定要有一块空间给我，不然我插个屁,并且我在进行插入操作的时候一定要对其进行检查空间是否还有 if (ps->capacity == ps->top)//此时是我的top在往后走，不是我的data，data只是一个存的，所以千万不敢写成if (ps->capacity == ps->data) { /*ST* newcapacity = ps->capacity == 0 ? 4 : newcapacity;*/ //int newCapacity = ps->capacity == 0 ? 4 : newCapacity;//这句已经是写对了百分之90，但是就是有那么一点的细节没有写明白，就是一定能够要理解此时的capacity是一个int类型的数据，所以newcapacity也应该是一个int类型的数据 int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//这步要重点注意，不敢写错掉 /*ST* tmp = (ST*)realloc(ps->data, sizeof(ST)* newCapacity);*/ STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newCapacity);//这句本来也是写对了百分之90，但是也是还有点没有注意到（就是此时你开辟的空间是int类型的空间（这边就千万不敢和链表开辟一个结构体的空间那边弄混掉，所以此时这个写成int的大小就行）） //这边你居然把你最拿手的动态内存的开辟的检查给忘记掉了 if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } //程序来到这里就是表示成功了 ps->data = tmp; ps->capacity = newCapacity; } //有了新空间 /*ps->top = x;*/ ps->data[ps->top] = x;//这步值得表扬一下，首先你是知道是应该要在栈顶存放数据的，但是你不应该忘记了是在那个结构体数据中的栈顶 ps->top++;//这个就是表示我的数据开始向后走，并且我的首个结构体中的那个top就是我最后出的数据，也就是栈底的数据 } //栈顶删除 void StackPopt(ST* ps) { assert(ps); assert(ps->top > 0); /*while*/ //这边不敢想出写while循环了我的爷，这个已经不是链表了，这个是栈，这边进行删数据是最简单的，只需要把栈头给删掉就行了 //free(ps->top); //ps->top = NULL; //这边也不敢这样子写，因为我哪里来的指针，还置成空指针，你那里想出来的高级东西（还是那句话，不敢搞混掉，这个是栈数组不是链表），并且没有指针，这个是一个数组而已 //所以正确的栈的删除的写法应该是，只需要下面这步就行：（前提是栈中有数据） ps->top--;//其实这个就是表示删除数据了 //但是写到了这里，我们不敢太得意，我们一定要再仔细思考一下（特别是在删除数据的时候），所以一定要再这上面加一个判断条件 } //寻找栈顶 STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); //return ps->top - 1;//这边寻找直接写这个肯定是没有任何关系，但是一点要注意top的初始化是0还是-1； //但是还是写错了一点点（这边我们肯定是不能这样写的（因为这样写的意思代表的就只是我后面动态开辟出来的数据）），我因该要按照下面这样写 return ps->data[ps->top - 1];//为什么我要这样写呢？原因是我是用的一个数组来进行对栈的创建，所以当我们要寻找栈的数据时（就要把这个当成一个下标来使用，不敢还是跟链表弄混掉） //注意点就是要把后面创建的数据用下标来联系起来（并且注意top的下标就是0） } //判断栈是否为空 bool StackEmpty(ST* ps) { //if (ps->top == 0) //{ // return true; //} //else //{ // return false; //} //或者可以这样写：直接return return ps->top == 0; } int StackSize(ST* ps) { return ps->top;//这边就要明白此时的这个ps->top,不是ps->data[ps->top],这两个是有区别的，一个表示的是头元素，一个是在加加后得到的，此时这个ps->top,此时通过一直的加加，现在它就是在我的栈底了，所以它就可以代表我的数据的个数 }
3.测试文件：
#include"Stack.h" void Test() { ST p; //初始化 StackInit(&p); //栈顶插 StackPush(&p, 1); StackPush(&p, 2); StackPush(&p, 3); StackPush(&p, 4); StackPush(&p, 5); //栈顶删除 StackPopt(&p); printf("%d ", StackTop(&p)); printf("%d ", StackSize(&p)); printf("%d ", StackEmpty(&p)); //插入删除之后，这边我一定要有一步遍历栈，然后打印出来 while (!StackEmpty(&p)) { /*printf("%d ",p->data[p->top-1]);*/ printf("%d ", StackTop(&p));//一个是调函数一个是不调函数，都一样 //打印完之后，一定要把栈顶给删除掉，我们才可以进行下一个栈顶的打印 StackPopt(&p); } StackDestory(&p); } int main() { Test(); return 0; }
4.测试样列：
二、队列的完整代码
1.头文件：
#pragma once //刚刚在几个的转折之下我们终于是完成了栈的数组实现 //现在我们来看一下什么是队列OK； //首先话不多说，咱结构体走起(使用链表的形式实现我的队列) #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDataType; typedef struct QueueNewnode { struct Newnode* next; STDataType data;//这个数据自然而然是一个类型（怎么可能是一个结构体类型（数据这边千万不敢当傻子，搞一个结构体的类型出来）） }QueueNode; typedef struct Queue { QueueNode* tail; QueueNode* head; }Queue; //结构体创建好了，现在就轮到各个接口的实现了 //初始化 void QueueInist(Queue* ps); //销毁 void QueueDestory(Queue* ps); //插入结点 void QueuePush(Queue* ps,STDataType x); //删除结点 void QueuePopt(Queue* ps); //队列的大小计算 size_t QueueSize(Queue* ps);//这个也是有返回值的 //判断是否为空 bool QueueEmpty(Queue* ps); //但是要注意的是找队列头和找队列尾，一定要有返回值哦 //找队列尾 //void QueueBack(Queue* ps); 找队列头 //void QueueFront(Queue* ps); //你反回的也不是一个结构体啊，你这边怎么敢写成结构体的啊（返回类型直接写int类型不就行了吗，我真的是人才） //QueueNode QueueBack(Queue* ps); //QueueNode QueueFront(Queue* ps); STDataType QueueBack(Queue* ps); STDataType QueueFront(Queue* ps);
2.接口实现文件：
#include"Queue.h" //有了这些 //初始化 void QueueInist(Queue* ps)//正确 { assert(ps); //初始化如果不出意外的话应该是最简单的，只要有两个空指针应该就搞定了吧 ps->head = NULL; ps->tail = NULL; //好像就是这样 } //销毁 void QueueDestory(Queue* ps)//正确 { assert(ps); //我刚刚充分意识到了栈的空间的销毁的简单（因为我是通过数组实现的栈） //然而此时我用的是链表的形式（首先肯定就要知道这个是没有那么简单的，所以我们得仔细思考） while (ps->head != NULL) { Queue* next = ps->head->next; free(ps->head); ps->head = NULL; ps->head = next; } //此时的我新增的结点是倒是全部都销毁了，但是要记得把第二个结构体中的指针给置成空指针（这样是最好的） ps->head = NULL; ps->tail = NULL; } //插入结点 void QueuePush(Queue* ps,STDataType x)//大致正确（判断条件处理的不是很好） { assert(ps); //此时的这个插入一定要结合好队列的特性，不然就不好写（先进先出） //首先我们要有一个新结点 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); //有了这个新结点（就根据特性进行插入）（是在尾的地方进行插入，这点要明白） newnode->data = x; newnode->next = NULL; //if (ps->head == ps->tail) //if (ps->tail == NULL) //判断无的条件，并不需要如上这样写，直接写下面这个就行了 if (ps->head == NULL) { //这个条件就是表示队列中无数据(无数据，我们就只要进行赋值操作就可以完成我想要的) ps->head = newnode; ps->tail = newnode; } else { ps->tail->next = newnode; ps->tail = newnode; newnode->next = NULL; //写完基本的之后就要进行注意点的注意 } } //删除结点 void QueuePopt(Queue* ps)//正确 { assert(ps); assert(!QueueEmpty(ps));//这个断言就是保证队列不为空，我才进行删除操作 if (ps->head != NULL) { Queue* next = ps->head->next; free(ps->head); ps->head = NULL; ps->head = next; } else { ps->tail = NULL;//这步就是表示我已经把队列给删除完了，但是此时的tail并没有置成一个NULL，所以此时的tail就是一个野指针，所以一定要把tail也给释放掉 } } //队列的大小计算 size_t QueueSize(Queue* ps)//错误 { assert(ps); /*return ps->head->data;*/ //这边就小瞧了队列的数据个数计算了 //要区分开来 //因为这个是一个链表，所以只要是你想要遍历数据（就一定要使用循环，不用循环是不可能拿到链表中的所有数据的） int n = 0; QueueNode* cur = ps->head; while (cur != NULL) { n++; cur = cur->next; } //这边完成了上述的所有的步骤，这边不敢忘记掉你写这个函数的目的，目的就是：计算这个队列的大小：所以最后一定还要记得把返回值给返回去 return n; } //判断是否为空 bool QueueEmpty(Queue* ps) { assert(ps); //if (ps->head) //{ // return true; //} //else //{ // return false; //} //这边就不是按照栈的那个写法来判断队列是否为空了，这边是通过下面这个方法：(但是一写完，我发现我的方法好像也还是可以的) return ps->head == NULL; } STDataType QueueBack(Queue* ps)//差一点点就完全正确了 { assert(ps); assert(!QueueEmpty(ps)); return ps->tail->data; } STDataType QueueFront(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); return ps->head->data; }
3.测试文件：
#include"Queue.h" void Test1() { Queue* ps; //初始化 QueueInist(&ps); //插入数据 QueuePush(&ps, 1); QueuePush(&ps, 2); QueuePush(&ps, 3); QueuePush(&ps, 4); QueuePush(&ps, 5); QueuePush(&ps, 6); QueuePush(&ps, 7); QueuePush(&ps, 8); QueuePush(&ps, 9); QueuePush(&ps, 10); //队列大小的计算 printf("%d\n ", QueueSize(&ps)); //判断是否为空 printf("%d\n ", QueueEmpty(&ps)); //队列尾数据 printf("%d\n ", QueueBack(&ps)); //队列头数据 printf("%d\n ", QueueFront(&ps)); //删除 QueuePopt(&ps); QueuePopt(&ps); QueuePopt(&ps); //这边来一个遍历数据，进行打印 //while (cur != NULL) //{ // printf("%d",cur->data);//这边这样写你就是把这个东西给当成是一个链表了，但是这个东西是一个队列，不是链表，所以 这边一定不敢这样写，这样写就是代表从前向后读取数据了，就违背了队列的特性了 // cur = cur->next; //} //QueueNode* cur = ps->head; //while (QueueEmpty(&ps))//这个写法也是有大问题的 //{ // printf("%d ", QueueFront(&ps)); // QueuePopt(&ps);//并且你这边千万不敢把这个删除数据给忘了，不然你就不可能拿到下一个数据了 //} //printf("\n"); while (!QueueEmpty(&ps)) { STDataType front = QueueFront(&ps);//表示先取最头上的数据 printf("%d ", front); QueuePopt(&ps);//取完此时的最头上的这个数据之后就一定还要把它给删掉，这样我就可以拿到下一个数据了，不然就不可以遍历整个队列了 } printf("\n"); //销毁 QueueDestory(&ps); } int main() { Test1(); return 0; }
4.测试样列：
三、总结：
所以我们应该要多写，自己写出来的才是自己的哦！
