宏基陆通工程建设有限公司网站,网站建设后期服务收费标准,山西省建设厅官网站,网站集约化建设必要性栈
栈是一种后进先出的数据结构#xff0c;可以用数组来模拟实现#xff0c;掌握必要的数据结构是非常的有必要的
一样是先打出头文件
#pragma once#include stdio.h
#include stdlib.h
#include string.h
#include stdbool.h
#include 可以用数组来模拟实现掌握必要的数据结构是非常的有必要的
一样是先打出头文件
#pragma once#include stdio.h
#include stdlib.h
#include string.h
#include stdbool.h
#include assert.htypedef int type;
typedef struct stack
{type* a;int top;//栈顶int capa;
}st;void stinit(st* pst);// 初始化
void stdestroy(st* pst);
void stpush(st* pst, type x);// 入
void stpop(st* pst);// 出
type sttop(st* pst);// 获取栈顶数据
bool stempty(st* pst);
int stsize(st* pst);
因为栈的特性栈对比链表简单了不少
接下来我们来实现它的功能接口
初始化
使用typedef int是因为我们可能要存其他类型的数据这样我们可以很容易的改变存进来的数据类型避免麻烦的替换操作
栈也分数组栈和链式栈但我们很容易发现既然是后进先出那么数组栈会更简单更合理
typedef int type;
typedef struct stack
{type* a;int top;//栈顶int capa;
}st; //数组栈 和 链式栈
//后进先出
#include stack.hvoid stinit(st* pst)// 初始化
{assert(pst);//经典判空pst-a NULL;pst-top 0;//指向栈顶数据pst-capa 0;
}
销毁空间
void stdestroy(st* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capa 0;
}
必要的接口避免内存泄漏
因为是数组实现所以直接对a这块空间释放就可以了
入栈
void stpush(st* pst, type x)// 入栈
{if (pst-top pst-capa){type newcapa pst-capa 0 ? 4 : pst-capa * 2;type* tmp (type*)realloc(pst-a, newcapa * sizeof(type));if (tmp NULL){perror(realloc fail\n);return;}pst-a tmp;pst-capa newcapa;}pst-a[pst-top] x;
}
第一个if是检查栈是否为0需要开辟空间或者是栈是不是已经满了要开辟空间
要是if条件里面判断为真我们就需要用两倍开辟新的空间
开辟完后再把数据入栈同时记得更新a的地址以及容量capa的大小
出栈
void stpop(st* pst)// 出栈
{assert(pst);assert(!stempty(pst));//不为空才可以删pst-top--;
}
出栈很简单判空之后直接top--跟顺序表的尾删一样
获取栈顶数据
type sttop(st* pst)// 获取栈顶数据
{assert(pst);assert(!stempty(pst));//不为空才可以访问return pst-a[pst-top - 1];//避免越界访问
}
一样判空之后直接return top的值就可以提取出来了
判空
bool stempty(st* pst)
{assert(pst);return pst-top 0;
}
检查top的值即可
检查数量
int stsize(st* pst)
{assert(pst);return pst-top;
}
一样检查top的值即可
测试
下面是测试代码大家可以自己修改测试栈的功能
void stacktest1()//测试栈功能
{st s;//使用栈结构初始化stinit(s);stpush(s, 1);stpush(s, 3);stpush(s, 4);stpush(s, 2);stpush(s, 1);sttop(s);stpop(s);sttop(s);while (!stempty(s))//遍历 但是遍历一遍栈的数据就没了{printf(%d , sttop(s));stpop(s);}stdestroy(s);
}
int main()
{stacktest1();return 0;
}队列
队列是一种先进先出的数据结构可以用链表来模拟实现掌握必要的数据结构是非常的有必要的
因为是先进先出的特性数组来模拟头删会特别慢
还是照例给出头文件
/一个是结点好去malloc一个是整体整体是为了方便提高效率
typedef struct quenenode
{struct quenenode* next;type data;
}qnode;typedef struct quene
{qnode* phead;qnode* ptail;int size;
}queue;
//void queueinit(queue* pq);
void queuedestroy(queue* pq);
void queuepush(queue* pq,type x);
void queuepop(queue* pq);
type queuefront(queue* pq);//取头
type queueback(queue* pq);//取尾
int queuesize(queue* pq);
bool queueempty(queue* pq); 和前面的数据结构不同的是队列创建了两个结构体来提高接口的效率
初始化
接口调用的都是queue结构体另一个结构体仅存数据和操作来指向next
//队列
//链式队列
//先进先出
//尾进头出#include quene.hvoid queueinit(queue* pq)//总体的初始化
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}
销毁空间
void queuedestroy(queue* pq)
{assert(pq);qnode* cur pq-phead;//遍历指针while (cur){qnode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
因为队列是链表为基础的所以我们要创建一个结点来专门遍历销毁
最后再将phead和ptail置为空指针size置为0
入队列
void queuepush(queue* pq, type x)
{assert(pq);qnode* newnode (qnode*)malloc(sizeof(qnode));if (newnode NULL){perror(malloc fail\n);return;}newnode-data x;newnode-next NULL;if (pq-ptail NULL){assert(pq-phead NULL);pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;//存数据进结点pq-ptail newnode;//更新尾指针}pq-size;
}
最开始还是经典判空然后建立一个结点来接受新开辟的空间然后将数据存入新建立的节点中然后更新原本最后的结点的next的值最后再将ptail指向新建立的结点然后将描述数量的size
出队列
void queuepop(queue* pq)//对头出数据
{assert(pq);assert(!queueempty(pq));if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{//头删qnode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}
首先判空因为空的话会出现未定义行为
然后判断只有一个结点的情况因为只有一个结点的时候next指向NULL
然后出队列其实就是头删先建立一个结点保存头数据的next然后将phead释放再将phead指向新建立的next处 取头取尾
type queuefront(queue* pq)//取头
{assert(pq);assert(!queueempty(pq));return pq-phead-data;
}
type queueback(queue* pq)//取尾
{assert(pq);assert(!queueempty(pq));return pq-ptail-data;
}
很简单直接取出phead 和 ptail 但是标准官方版的队列有这个接口所以我们也实现一下
检查数量
int queuesize(queue* pq)//数量
{assert(pq);return pq-size;
}
跟上面的取头取尾一样官方版的队列有这个接口我们直接返回size即可
判空
bool queueempty(queue* pq)//判断空
{assert(pq);return pq-phead NULL;//判断ptail跟size都可以
}
判空有很多种写法自习挑选一种即可
测试
下面是测试代码大家可以自己修改测试队列的功能
void testqueue()
{queue q;queueinit(q);queuepush(q, 1);queuepush(q, 3);queuepush(q, 2);queuepush(q, 4);queuefront(q);queueback(q);while (!queueempty(q)){printf(%d , queuefront(q));queuepop(q);}printf(\n);queuedestroy(q);
}int main()
{testqueue();return 0;
}
