课题网站建设培训简讯,东方网景做网站怎么样,北京网站建设是什么意思,杨和关键词优化1.前言
栈和队列不是一种语言独有的结构#xff0c;而是一个由代码语言设计的一种数据结构。是由人设计出的一种具有特定意义的结构。
2.栈
什么是栈#xff0c;栈以结构体为节点按要求链接的一种后进先出的一种数据结构#xff08;last in first out#xff09;简称LIF…1.前言
栈和队列不是一种语言独有的结构而是一个由代码语言设计的一种数据结构。是由人设计出的一种具有特定意义的结构。
2.栈
什么是栈栈以结构体为节点按要求链接的一种后进先出的一种数据结构last in first out简称LIFO结构。栈可以由数组实现也可以由链表实现。只不过数组实现出的栈效果更好这里以数组为实现。
每一个进去栈的数据都包含三个数据数组指针空间大小以及栈顶元素的下标为了将三个封装在一起所以我们要用到结构体。分别是int* a数组通过下标来储存数据 int top 栈顶元素的下一个的下标为什么是下一个元素的小标呢因为我们初始化时将top赋值0即 top0但是此时栈中是没有数据的所以是下一个小标。不过也可以赋值为-1那么此时就是栈顶元素的下标了
栈的节点
typedef int DataType;typedef struct Stack
{DataType* a;//顺序表int top;栈顶元素的下一个下标int capacity;空间大小
}ST;
栈的底层代码函数有7个
void STinit(ST* ps);//栈的初始化
void STDstory(ST* ps);//栈的销毁
void STpush(ST* ps,DataType x);//入栈操作
void STpop(ST* ps);//出栈操作
DataType STtop(ST* ps);//获得栈顶的元素
bool STEmpty(ST* ps);//判断栈是否为空
int STSize(ST* ps);//判断栈中的有效元素个数
为什么要有这7个底层函数呢目前而言这七个函数满足了栈的各种需求如果你认为还有更好的函数来满足栈的需求也可以自己增加。不过这7个函数应该是已经足够了。
2.1下列分别介绍7个函数
2.1.1 栈的初始化void STinit(ST* ps)
第一个函数很简单将结构体中的数据全部初始化为“0”就行了
void STinit(ST* ps)//栈的初始化
{ps-aNULL;ps-topps-capacity0;
} 2.1.2 栈的销毁 void STDstory(ST* ps)
栈的销毁也比较简单我们类比顺序表的销毁
void STDestory(ST* ps)//栈的销毁
{free(ps-a);ps-aNULL;ps-topps-capacity0;
} 2.1.3 入栈操作void STpush(ST*psDataType x) 将数据压入栈中类比与顺序表先判断结构体是否为空防止出现空指针访问接着考虑空间是否充足要不要扩容最后再进行压栈操作。
void STpush(ST*psDataType x)
{assert(ps);if(ps-capacityps-top)//说明空间已经到达极限了需要扩容操作{ps-capacity0?2:(2*(pa-capacity));DataType* newa(DataType*)relloc(ps-a,(ps-capacity)*sizeof(DataType))if(newaNULL){perror(relloc fail!);return -1;}}ps-a[ps-top]x;ps-top--;
}
2.1.4 出栈操作STpop(ST* ps)
这实现的是出的操作将栈顶的元素pop出。
void STpop(ST* ps)
{assert(ps);//断言防止出现空指针的访问操作ps-a[top--]0;
}
2.1.5 获取栈顶的元素DataType STtop(ST* ps)
获得栈顶元素
DataType STtop(ST* ps)
{return ps-a[--(ps-top)];
}
2.1.6 判断栈是否为空bool STEmpty(ST* ps)
bool STEmpty(ST* ps)
{return (--ps-top)0;
}
2.1.7 判断栈中的有效元素个数int STSize(ST* ps)
int STSize(ST* ps)
{return ps-top;
} 3.队列
队列是以链表为基础的数据结构实现的是先进先出。但这里需要带头节点和尾结点为什么呢假如我们不带尾节点在我们进行入栈操作时需要遍历一遍链表到达尾节点时间复杂度是O(N)而用带尾结点我们就可以直接进行尾删操作了这样一来时间复杂度可以做到O(1)了。但是我们传参的时候传两个有点不太方便所以我们就想到了用结构体将他们封装起来。
所以队列有两个结构体一个表示一个节点包括的内容包括了DataType val ,struct QueueNode* next。另一个则是包括首尾指针的结构体
代码如下
typedef int DataType;
typedef struct QueueNode//队列的每一个结构体节点
{int val;struct QueueNode* next;
}QNode;typedef struct Queue//头尾指针
{QNode* tail;QNode* head;int size;//队列大小
}Queue;
队列的底层代码有8个如下
//入队列队尾
void Queuepush(Queue* pq, QDataType x);//链表可能为空
//出队列队头
void Queuepop(Queue* pq);//队列的初始化
void QueueInit(Queue* pq,QNode* ps);//队列的销毁
void QueueDestory(Queue* pq);//返回队头的数据
QDataType QueueFront(Queue* pq);//返回队尾的数据
QDataType QueueBack(Queue* pq);//判断队列是否为空
bool QueueEmpty(Queue* pq);//返回队列中的有效元素个数
int QueueSize(Queue* pq);
3.1.1 入队列void Queuepush(Queue*pq,QDataType x)
这里我们入队列用尾插出队列我们用头插。
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail){pq-ptail-next newnode;pq-ptail newnode;}else{pq-phead pq-ptail newnode;}pq-size;
}
3.1.2 出队列void QueuePop(Queue* pq)
void QueuePop(Queue* pq)
{assert(pq);// 0个节点// 温柔检查//if (pq-phead NULL)// return;// 暴力检查 assert(pq-phead ! NULL);// 一个节点// 多个节点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--;
}
3.1.3 队列的初始化void QueueInit(Queue* pq)
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}
3.1.4 队列的销毁void QueueDestroy(Queue* pq)
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;
}
3.1.5 返回对头数据QDataType QueueFront(Queue* pq)
QDataType QueueFront(Queue* pq)
{assert(pq);// 暴力检查 assert(pq-phead ! NULL);return pq-phead-val;
}
3.1.6 返回队尾数据QDataType QueueBack(Queue* pq)
QDataType QueueBack(Queue* pq)
{assert(pq);// 暴力检查 assert(pq-ptail ! NULL);return pq-ptail-val;
}
3.1.7 判断队列是否为空bool QueueEmpty(Queue* pq)
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
3.1.8 返回队列中有效元素个数int QueueSize(Queue* pq)
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
希望这篇博客对你有帮助
