数据结构与算法笔记（二）
顺序栈、链栈、环形队列、链队
顺序栈
顺序栈采用数组的形式对数据进行存储。
初始化时，需要将栈顶指针top指向-1。
顺序栈的判空条件为栈顶指针top==-1。
在进栈操作时，顺序栈需要先对栈进行判满，判满条件为栈顶指针top是否等于数组（栈）的长度-1。进栈时将栈顶指针top+1，再对此时所指向的数组空间（data域）进行赋值。
出栈时需要先对顺序栈进行判空操作，若顺序栈为空，则返回false，出栈时，记录当前出栈的元素，再将top指针前移（top-1）。
取栈顶元素与出栈操作类似，但是无需进行栈顶指针前移操作。
因为顺序栈使用的是数组进行存储，故释放顺序栈时直接free(s)即可。
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct {
ElemType data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack*& s) { //初始化顺序栈
s = (SqStack*)malloc(sizeof(SqStack));
s->top = -1;
}
void DestoryStack(SqStack*& s) { //销毁顺序栈
free(s);
}
bool StackEmpty(SqStack* s) { //判断顺序栈是否为空
return(s->top == -1);
}
bool Push(SqStack*& s, ElemType e) { //进栈
if (s->top == MaxSize - 1) {
return false;
}
s->top++;
s->data[s->top] = e;
return true;
}
bool Pop(SqStack*& s, ElemType &e) { //出栈
if (s->top == -1) {
return false;
}
e = s->data[s->top];
s->top--;
return true;
}
bool GetTop(SqStack* s, ElemType e) { //取栈顶元素
if (s->top == -1) {
return false;
}
e = s->data[s->top];
return true;
}
#include"sqstack.h"
int main() {
SqStack* s;
ElemType e;
printf("1.初始化顺序栈：\n");
InitStack(s);
printf("2.判断顺序栈s是否非空：%s\n",StackEmpty(s)?"空":"非空");
printf("3.依次进栈元素a,b,c,d,e\n");
Push(s, 'a');
Push(s, 'b');
Push(s, 'c');
Push(s, 'd');
Push(s, 'e');
printf("4.判断顺序栈s是否非空：%s\n", StackEmpty(s) ? "空" : "非空");
printf("5.输出出栈序列：");
while (!StackEmpty(s)) {
Pop(s, e);
printf("%c ", e);
}
printf("\n");
printf("5.判断顺序栈s是否非空：%s\n", StackEmpty(s) ? "空" : "非空");
DestoryStack(s);
}
链栈
链栈采用链式存储结构对数据进行存储。
初始化链栈时，需要将s（头结点）的next域置为空（NULL）。
链栈执行判空操作时，判空的条件是s的next域为空（NULL）。
链栈执行进栈操作时，无需进行判满操作，给要进栈的元素创建新的结点（p），分配内存，让该结点（p）的data域指向该元素，将该结点（p）的next指向头结点（s）的next，再将头结点的next指向该结点（p）。该过程使用头插法完成。
链栈执行出栈操作时，需要先对链栈进行判空操作，判空条件为s（头结点）的next域为空（NULL）。出栈时，需要将一个新结点（p）置为需要出栈的结点（s->next），再将p的data域中的值（需要出栈的元素）提取出来，并让s->next指向p->next，最后释放p。
取栈顶元素时与先判空，再提取头结点的next域所指向的结点中的data域的值。
销毁链栈时，需要设置一个新指针（p）指向头结点（s）的next结点，接着释放s，将s置为p，并将p指向p的next结点。当p结点为空时跳出循环，释放此时的s结点。
#include<stdio.h>
#include<malloc.h>
typedef char ElemType;
typedef struct linknode{
ElemType data;
struct linknode* next;
}LinkStnode;
void InitStack(LinkStnode*& s) { //初始化链栈s
s = (LinkStnode*)malloc(sizeof(LinkStnode));
s->next = NULL;
}
bool StackEmpty(LinkStnode*& s) { //判断链栈s是否为空
return(s->next == NULL);
}
bool Push(LinkStnode*& s, ElemType e) { //进栈
LinkStnode* p;
p = (LinkStnode*)malloc(sizeof(LinkStnode));
p->data = e;
p->next = s->next;
s->next = p;
return true;
}
bool Pop(LinkStnode*& s, ElemType& e) { //出栈
LinkStnode* p;
if (s->next == NULL) {
return false;
}
p = s->next;
e = p->data;
s->next = p->next;
free(p);
return true;
}
bool GetPop(LinkStnode*& s, ElemType& e) { //取栈顶元素
if (s->next == NULL) {
return false;
}
e = s->next->data;
return true;
}
void DestroyStack(LinkStnode*& s) {
LinkStnode* p = s->next;
while (p != NULL) {
free(s); //释放盖子
s = p; //重置盖子
p = p->next; //p前移
}
free(s); //释放盖子（头结点）
}
#include"listack.h"
int main() {
LinkStnode* s;
ElemType e;
printf("1.初始化链栈：\n");
InitStack(s);
printf("2.判断链栈s是否为空：%s\n", StackEmpty(s) ? "空" : "非空");
printf("3.依次进栈元素a,b,c,d,e\n");
Push(s, 'a');
Push(s, 'b');
Push(s, 'c');
Push(s, 'd');
Push(s, 'e');
printf("4.判断链栈s是否为空：%s\n", StackEmpty(s) ? "空" : "非空");
printf("5.输出出栈序列：");
while (!StackEmpty(s)) {
Pop(s, e);
printf("%c ", e);
}
printf("\n");
printf("6.判断链栈s是否为空：%s\n", StackEmpty(s) ? "空" : "非空");
printf("7.释放栈\n");
DestroyStack(s);
}
环形队列
环形队列采用数组的形式对数据进行存储。
在结构体中，我们需要定义两个成员（int型）：front和rear，用作队头和队尾指针，并且需要定义环形队列的长度（数组长度）。
初始化环形队列时，我们将front和rear都置为0。
环形队列的判空操作，条件为front==rear。
环形队列入队时，先要对队列进行判满，判满条件为rear+1 mod MaxSize == front。再进行入队操作，队尾指针循环增1再进行入队。
环形队列出队时，应先对队列进行判空。队头指针循环增1，再取元素出队。
释放环形队列时，因为环形队列采用数组进行存储，故直接进行free(q)操作即可。
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct {
ElemType data[MaxSize];
int front;
int rear;
}SqQueue;
void InitQueue(SqQueue*& q) { //初始化环形队列
q = (SqQueue*)malloc(sizeof(SqQueue));
q->front = q->rear = 0;
}
bool QueueEmpty(SqQueue* q) { //判空
return(q->front == q->rear);
}
bool enQueue(SqQueue*& q, ElemType e) { //入队
if ((q->rear + 1) % MaxSize == q->front) { //判满
return false;
}
q->rear = (q->rear + 1) % MaxSize;
q->data[q->rear] = e;
return true;
}
bool deQueue(SqQueue*& q, ElemType& e) { //出队
if (q->front == q->rear) { //判空
return false;
}
q->front = (q->front + 1) % MaxSize;
e = q->data[q->front];
return true;
}
void DestroyQueue(SqQueue*& q) { //释放队列
free(q);
}
#include"sqqueue.h"
int main() {
ElemType e;
SqQueue* q;
printf("1.初始化队列q：\n");
InitQueue(q);
printf("2.判断队列q是否为空：%s\n", QueueEmpty(q) ? "空" : "非空");
printf("3.依次进队元素a,b,c\n");
enQueue(q, 'a');
enQueue(q, 'b');
enQueue(q, 'c');
printf("4.出队一个元素，输出该元素：");
deQueue(q, e);
printf("%c\n", e);
printf("5.依次进队元素d,e,f\n");
enQueue(q, 'd');
enQueue(q, 'e');
enQueue(q, 'f');
printf("6.输出出队队列：");
while (!QueueEmpty(q)) {
deQueue(q, e);
printf("%c ", e);
}
printf("\n7.释放队列");
DestroyQueue(q);
}
链队
链队采用链式存储结构对数据进行处理。
使用链队时，需要定义两个结构体：一个为链队数据结点，存放元素和指向下一个结点的指针，一个为链队，存放两个指针，front用于指向队首结点，rear用于指向队尾结点。
初始化链队时，需要将front和rear置为空（NULL）。
链队的判空操作，条件为q->rear== NULL 或 q->front== NULL。
链队无需判满操作。
链队执行入队操作时，无需进行判满，需要给需要入队的元素创建新的结点（p），将元素赋值给p的data域并将p的next域置为空（NULL）。接下来做条件判断：如果新插入的结点是链队的首结点（此时q->rear== NULL），那么直接让队头结点和队尾结点直接指向新结点p即可。如果不是链队的首结点（链队不空），我们使用尾插法让队尾结点的next域指向p，接下来操作队尾结点，使队尾结点指向新结点p（q->rear=p），这样就完成了链队非空时的元素插入操作。
链队执行出队操作时，需要定义一个取出队元素的指针t，执行出队操作之前先进行判空，接着将t置为首结点（t=q->front）。接下来做条件判断：如果出队的元素是链队中唯一的元素，那么直接将首结点和尾结点置空。如果不是唯一元素，将首结点置为要出队的元素（结点）的next结点（q->front=t->next）。执行完条件判断后，取出栈元素（e=t->data），并释放t。
链队执行释放操作时，需要定义一个指向（置为）首结点的指针pre（pre=q->front），还有一个指向首结点的next结点的指针p。执行操作：第一层条件判断为：首结点是否为空（pre!=NULL），如果为空直接释放指向front和rear的q指针；如果不为空，使p置为首结点的next结点，接下来做第二层条件判断：如果此时p结点为空（即首结点pre为链队中的唯一结点），那么直接释放pre，若p结点不为NULL，则释放pre结点，并将pre置为p，再将p指针后移（p=p->next），直到链队中只剩下一个结点。
**链队总结：**链队需要注意判空条件（q->rear== NULL或q->front== NULL）。初始化队列时需要将队头指针和队尾指针置空。入队时做出的条件判断是：插入的结点是否为链队首结点。出队时需要对队列进行判空，出队需要做的条件判断是：出队的结点是否为链队的唯一节点，并在判断且出队完毕后记录出队的元素。释放链队时，需要进行两层判断：第一层是链队是否为空，为空直接释放链队结点q，第二层是要释放的结点是否为链队的唯一结点，如果是，直接释放，如果不是，释放后需要将pre和p同步后移。
#include<stdio.h>
#include<malloc.h>
typedef char ElemType;
typedef struct DataNode {
ElemType data; //存放元素
struct DataNode* next; //下一个结点指针
}DataNode; //声明链队数据结点类型
typedef struct {
DataNode* front; //指向队首结点
DataNode* rear; //指向队尾结点
}LinkQunode; //声明链队类型
void InitQueue(LinkQunode*& q) { //初始化链队
q = (LinkQunode*)malloc(sizeof(LinkQunode));
q->front = q->rear = NULL;
}
bool QueueEmpty(LinkQunode* q) { //判空
return(q->rear == NULL);
}
void enQueue(LinkQunode*& q, ElemType e) { //入队
DataNode* p;
p = (DataNode*)malloc(sizeof(DataNode)); //创建新结点
p->data = e;
p->next = NULL; //新结点的next域置为空
if (q->rear == NULL) { //如果新结点是首结点（链队空）
q->front = q->rear = p; //头尾指向新结点
}
else { //如果链队不空
q->rear->next = p;
q->rear = p;
}
}
bool deQueue(LinkQunode*& q, ElemType& e) { //出队
DataNode* t;
if (q->rear == NULL) {
return false;
}
t = q->front;
if (q->front == q->rear) {
q->front = q->rear = NULL;
}
else {
q->front = t->next;
}
e = t->data;
free(t);
return true;
}
void DestroyQueue(LinkQunode*& q) { //释放队列
DataNode* pre = q->front, * p;
if (pre != NULL) {
p = pre->next;
while (p != NULL) {
free(pre);
pre = p;
p = p->next;
}
free(pre); //释放队列
}
free(q); //释放链队结点
}
#include"liqueue.h"
int main() {
LinkQunode* q;
ElemType e;
printf("1.初始化链队\n");
InitQueue(q);
printf("2.判断链队q是否非空：%s\n", QueueEmpty(q) ? "空" : "非空");
printf("3.依次进队元素a,b,c\n");
enQueue(q, 'a');
enQueue(q, 'b');
enQueue(q, 'c');
printf("4.出队一个元素，输出该元素：");
if (deQueue(q, e) == 0) {
printf("队空，链队中无元素\n");
}
else {
printf("%c\n", e);
}
printf("5.依次进队元素d,e,f\n");
enQueue(q, 'd');
enQueue(q, 'e');
enQueue(q, 'f');
printf("6.输出出队序列：");
while (deQueue(q, e) != 0) {
printf("%c", e);
}
printf("\n7.释放链队");
DestroyQueue(q);
return 0;
}