无锡微信网站建设价格,怎么制作网页推广,网站改版做重定向,网站建设付费项目#x1f407; #x1f525;博客主页#xff1a; 云曦 #x1f4cb;系列专栏#xff1a;数据结构 #x1f4a8;吾生也有涯#xff0c;而知也无涯 #x1f49b; 感谢大家#x1f44d;点赞 #x1f60b;关注#x1f4dd;评论 文章目录 前言一、栈#x1f4d9;1.1 栈… 博客主页 云曦 系列专栏数据结构 吾生也有涯而知也无涯 感谢大家点赞 关注评论 文章目录 前言一、栈1.1 栈的概念及结构1.2 栈的实现1.2.1 栈的结构1.2.2 初始化栈1.2.3 入栈1.2.4 出栈1.2.5 获取栈顶元素1.2.6 获取栈中有效元素个数1.2.7 检测栈是否为空1.2.8 销毁栈1.2.9 栈所有接口的测试 二、队列2.1 队列的概念及结构2.2 队列的实现2.2.1 队列的结构2.2.2 初始化队列2.2.3 队尾入队列2.2.4 检测队列是否为空2.2.5 队头出队列2.2.6 获取队列头部元素2.2.7 获取队列尾部元素2.2.8 获取队列中有效元素个数2.2.9 销毁队列2.2.10 队列所有接口的测试 完整代码**Stack.h****Stack.c****Queue.h****Queue.c****test.c** 前言 在上期中我们把双向链表学完了这期我们要开始新的一章 “栈和队列” 的讲解栈和队列基本都是拿我们之前所学的顺序表或链表来实现可谓是新瓶装旧酒有了对顺序表和链表的认识实现栈和队列并不是难事! 一、栈
1.1 栈的概念及结构 概念栈也是一种特殊的线性表其次栈只允许在固定一端插入删除进行数据插入或删除操作的一端叫作栈顶另一端为栈底。 栈中的数据元素遵守后进先出LIFO的原则。 压栈栈插入数据的操作叫作进栈/入栈/压栈且入数据是在栈顶。出栈栈删除数据的操作叫作出栈出数据也在栈顶。 结构 注意栈如果用链表实现的话要考虑找前一个节点的问题因为栈的插入删除都是在栈顶所以实现栈时推荐用顺序表来实现因为顺序表在尾部插入数据的代价比较小。 1.2 栈的实现
1.2.1 栈的结构 既然用顺序表实现那么栈的结构就是顺序表的结构 typedef int STDataType;typedef struct Stack
{int* arr;int top;//栈顶int capacity;//容量
}ST;1.2.2 初始化栈 因为在栈的结构里插入数据只能在栈顶插入所有只需要实现一个插入的接口即可把malloc改到插入接口(push)里即可. void STInit(ST* ps)
{assert(ps);ps-arr NULL;ps-capacity 0;ps-size 0;
}1.2.3 入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//检测容量if (ps-top ps-capacity){//使用三目操作符来解决扩容问题int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-arr, sizeof(STDataType)*newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-arr tmp;ps-capacity newcapacity;}//入栈ps-arr[ps-top] x;ps-top;
}需要注意的是realloc有一个特性如果传入的参数是NULL则会像malloc一样开辟一个空间出来相当于调用了malloc。 1.2.4 出栈 出栈很简单让栈顶减1即可。 void STPop(ST* ps)
{assert(ps);//栈为空就不能再删了assert(ps-top 0);ps-top--;
}需要注意的是插入的指针有可能为空或者栈有可能为空两个情况都要检查一下 1.2.5 获取栈顶元素 top是有效数据个数后一个的位置减1就为栈顶的元素 STDataType STTop(const ST* ps)
{assert(ps);return ps-arr[ps-top-1];
}1.2.6 获取栈中有效元素个数 top就是有效数据的个数直接返回top即可 int STSize(const ST* ps)
{assert(ps);return ps-top;
}1.2.7 检测栈是否为空 返回top是否等于0,等于返回真不等于返回假 bool STEmpty(const ST* ps)
{assert(ps);return ps-top 0;
}1.2.8 销毁栈 注意这里的销毁指得是把这块空间还给操作系统。 void STDestroy(ST* ps)
{assert(ps);free(ps-arr);ps-arr NULL;ps-capacity 0;ps-top 0;
}1.2.9 栈所有接口的测试
void TestStack()
{ST s;STInit(s);STPush(s, 1);STPush(s, 2);STPush(s, 3);STPush(s, 4);STPush(s, 5);printf(栈的有效元素个数%d\n, STSize(s));while (!STEmpty(s)){printf(%d , STTop(s));STPop(s);}//STPop(s);printf(\n栈的有效元素个数%d\n, STSize(s));STDestroy(s);}当栈为空还在删除时 二、队列
2.1 队列的概念及结构 概念队列也是一种只允许在一端插入数据在另外一端进行删除数据操作的特殊线性表队列具有先进先出FIFO。 入队列进行插入操作的一端称为队尾。出队列进行删除操作的一端称为队头。 结构 注意队列也能用顺序表和链表实现但使用链表的结构实现更优一些因为如果是顺序表的话头删要挪移数据才能完成效率比链表低所以实现队列推荐用链表来实现。 2.2 队列的实现
2.2.1 队列的结构 既然使用队列实现那么结构自然是链表的形式。 typedef int QueDataType;typedef struct QueueNode
{QueDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* tail;int size;
}Que;因为是单链表出队列是头删入队列是尾插导致需要一个头指针和尾指针且单链表计算长度要遍历一遍数组这样下来 要传头和尾的参数计算链表长度要遍历链表复杂度为O(N) 不如直接把头尾指针和定义一个存储链表元素个数的变量整合为一个结构体这样就方便多了 2.2.2 初始化队列
void QueueInit(Que* pq)
{pq-phead NULL;pq-tail NULL;pq-size 0;
}只有一个插入的接口那么就直接在插入接口获取节点就行。 2.2.3 队尾入队列 首先获取并初始化节点然后就是尾插尾插分为两种情况 链表为空特殊处理。链表不为空正常尾插。 void QueuePush(Que* pq, QueDataType x)
{//获取并初始化节点QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(newnode fail);exit(-1);}newnode-data x;newnode-next NULL;//入队列if (pq-phead NULL){//链表为空pq-phead newnode;pq-tail newnode;}else{//链表不为空pq-tail-next newnode;pq-tail newnode;}pq-size;
}2.2.4 检测队列是否为空 直接返回pq-phead NULL等于返回真不等于返回假 bool QueueEmpty(Que* pq)
{assert(pq);return pq-phead NULL;
}2.2.5 队头出队列 单链表头删很简单但要注意链表为空时不能再删了否则会出问题 void QueuePop(Que* pq)
{assert(pq);//检测链表是否为空为空就不能再删了assert(!QueueEmpty(pq));//出队列QNode* Next pq-phead-next;free(pq-phead);pq-phead Next;pq-size--;
}2.2.6 获取队列头部元素 phead指向的就是头节点,返回头节点的元素即可但要注意链表有可能为空所以要检测一下 QueDataType QueueFront(Que* pq)
{assert(pq);//检测链表是否为空assert(!QueueEmpty(pq));return pq-phead-data;
}2.2.7 获取队列尾部元素 tail指向的就是尾节点直接返回尾节点的元素即可但要注意链表有可能为空所以要检测一下 QueDataType QueueBack(Que* pq)
{assert(pq);//检测链表是否为空assert(!QueueEmpty(pq));return pq-tail-data;
}2.2.8 获取队列中有效元素个数 size存储的就是队列的有效元素个数返回size即可。 int QueueSize(Que* pq)
{assert(pq);return pq-size;
}2.2.9 销毁队列 这里的销毁指的也是把这片空间还给操作系统遍历一遍队列记录下一个节点的位置释放掉当前节点最后将头尾指针置空size置为0即可。 void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* Next cur-next;free(cur);cur Next;}pq-phead NULL;pq-tail NULL;pq-size 0;
}2.2.10 队列所有接口的测试
TestQueue()
{Que obj;QueueInit(obj);QueuePush(obj, 1);QueuePush(obj, 2);QueuePush(obj, 3);QueuePush(obj, 4);QueuePush(obj, 5);printf(队尾元素%d\n, QueueBack(obj));printf(队列的有效数据个数%d\n, QueueSize(obj));while (!QueueEmpty(obj)){printf(%d , QueueFront(obj));QueuePop(obj);}//QueuePop(obj);printf(\n队列的有效数据个数%d\n, QueueSize(obj));QueueDestroy(obj);
}当队列为空还在删时 完整代码
* 《栈》 Stack.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//栈
typedef int STDataType;typedef struct Stack
{int* arr;int top;//栈顶int capacity;//容量
}ST;//初始化栈
void STInit(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(const ST* ps);
//获取栈中有效元素的个数
int STSize(const ST* ps);
//检测栈是否为空
bool STEmpty(const ST* ps);
//销毁栈
void STDestroy(ST* ps);Stack.c
#include Stack.hvoid STInit(ST* ps)
{assert(ps);ps-arr NULL;ps-capacity 0;ps-top 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);//检测容量if (ps-top ps-capacity){//使用三目操作符来解决扩容问题int newcapacity ps-capacit0 ? 4 : ps-capacity*2;STDataType* tmp (STDataType*)realloc(ps-arr, sizeof(STDataType)*newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-arr tmp;ps-capacity newcapacity;}//入栈ps-arr[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);//栈为空就不能再删了assert(ps-top 0);ps-top--;
}STDataType STTop(const ST* ps)
{assert(ps);return ps-arr[ps-top-1];
}int STSize(const ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(const ST* ps)
{assert(ps);return ps-top 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps-arr);ps-arr NULL;ps-capacity 0;ps-top 0;
}* 《队列》 Queue.h
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//队列
typedef int QueDataType;typedef struct QueueNode
{QueDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* tail;int size;
}Que;//初始化队列
void QueueInit(Que* pq);
//入队列
void QueuePush(Que* pq, QueDataType x);
//检测队列是否为空
bool QueueEmpty(Que* pq);
//出队列
void QueuePop(Que* pq);
//获取队列头部元素
QueDataType QueueFront(Que* pq);
//获取队列尾部元素
QueDataType QueueBack(Que* pq);
//获取队列中有效元素的个数
int QueueSize(Que* pq);
//销毁队列
void QueueDestroy(Que* pq);Queue.c
#includeQueue.hvoid QueueInit(Que* pq)
{assert(pq);pq-phead NULL;pq-tail NULL;pq-size 0;
}void QueuePush(Que* pq, QueDataType x)
{assert(pq);//获取并初始化节点QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(newnode fail);exit(-1);}newnode-data x;newnode-next NULL;//入队列if (pq-phead NULL){//链表为空pq-phead newnode;pq-tail newnode;}else{//链表不为空pq-tail-next newnode;pq-tail newnode;}pq-size;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq-phead NULL;
}void QueuePop(Que* pq)
{assert(pq);//检测链表是否为空为空就不能再删了assert(!QueueEmpty(pq));//出队列QNode* Next pq-phead-next;free(pq-phead);pq-phead Next;pq-size--;
}QueDataType QueueFront(Que* pq)
{assert(pq);//检测链表是否为空assert(!QueueEmpty(pq));return pq-phead-data;
}QueDataType QueueBack(Que* pq)
{assert(pq);//检测链表是否为空assert(!QueueEmpty(pq));return pq-tail-data;
}int QueueSize(Que* pq)
{assert(pq);return pq-size;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* Next cur-next;free(cur);cur Next;}pq-phead NULL;pq-tail NULL;pq-size 0;
}* 《测试》 test.c
#includeStack.h
#includeQueue.hvoid TestStack()
{ST s;STInit(s);STPush(s, 1);STPush(s, 2);STPush(s, 3);STPush(s, 4);STPush(s, 5);printf(栈的有效元素个数%d\n, STSize(s));while (!STEmpty(s)){printf(%d , STTop(s));STPop(s);}//STPop(s);printf(\n栈的有效元素个数%d\n, STSize(s));STDestroy(s);}TestQueue()
{Que obj;QueueInit(obj);QueuePush(obj, 1);QueuePush(obj, 2);QueuePush(obj, 3);QueuePush(obj, 4);QueuePush(obj, 5);printf(队尾元素%d\n, QueueBack(obj));printf(队列的有效数据个数%d\n, QueueSize(obj));while (!QueueEmpty(obj)){printf(%d , QueueFront(obj));QueuePop(obj);}//QueuePop(obj);printf(\n队列的有效数据个数%d\n, QueueSize(obj));QueueDestroy(obj);
}int main()
{TestStack();TestQueue();return 0;
}
