数据结构C代码汇总【2-栈和队列】
·
章节总目录点击→数据结构C代码汇总目录
二、栈和队列
1、栈
【1】顺序栈
//顺序栈基本运算算法
#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 DestroyStack(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->data[++s->top]=e;
return true;
}
bool Pop(SqStack *&s,ElemType &e)
{
if (s->top==-1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top--];
return true;
}
bool GetTop(SqStack *s,ElemType &e)
{
if (s->top==-1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top];
return true;
}【2】链栈
//链栈基本运算算法
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
struct linknode *next; //指针域
} LinkStNode; //链栈类型
void InitStack(LinkStNode *&s)
{
s=(LinkStNode *)malloc(sizeof(LinkStNode));
s->next=NULL;
}
void DestroyStack(LinkStNode *&s)
{
LinkStNode *p=s->next;
while (p!=NULL)
{
free(s);
s=p;
p=p->next;
}
free(s); //s指向尾结点,释放其空间
}
bool StackEmpty(LinkStNode *s)
{
return(s->next==NULL);
}
void Push(LinkStNode *&s,ElemType e)
{ LinkStNode *p;
p=(LinkStNode *)malloc(sizeof(LinkStNode));
p->data=e; //新建元素e对应的结点p
p->next=s->next; //插入p结点作为开始结点
s->next=p;
}
bool Pop(LinkStNode *&s,ElemType &e)
{ LinkStNode *p;
if (s->next==NULL) //栈空的情况
return false;
p=s->next; //p指向开始结点
e=p->data;
s->next=p->next; //删除p结点
free(p); //释放p结点
return true;
}
bool GetTop(LinkStNode *s,ElemType &e)
{ if (s->next==NULL) //栈空的情况
return false;
e=s->next->data;
return true;
}2、队列
【1】顺序队（环形队列）
//链队运算算法
#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;
}
void DestroyQueue(LinkQuNode *&q)
{
DataNode *p=q->front,*r;//p指向队头数据结点
if (p!=NULL) //释放数据结点占用空间
{ r=p->next;
while (r!=NULL)
{ free(p);
p=r;r=p->next;
}
}
free(p);
free(q); //释放链队结点占用空间
}
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;
if (q->rear==NULL) //若链队为空,则新结点是队首结点又是队尾结点
q->front=q->rear=p;
else
{ q->rear->next=p; //将p结点链到队尾,并将rear指向它
q->rear=p;
}
}
bool deQueue(LinkQuNode *&q,ElemType &e)
{ DataNode *t;
if (q->rear==NULL) //队列为空
return false;
t=q->front; //t指向第一个数据结点
if (q->front==q->rear) //队列中只有一个结点时
q->front=q->rear=NULL;
else //队列中有多个结点时
q->front=q->front->next;
e=t->data;
free(t);
return true;
}【2】顺序队（非环形队列）
//顺序队列（非环形队列）基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int front,rear; //队头和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{ q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=-1;
}
void DestroyQueue(SqQueue *&q) //销毁队列
{
free(q);
}
bool QueueEmpty(SqQueue *q) //判断队列是否为空
{
return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e) //进队
{ if (q->rear==MaxSize-1) //队满上溢出
return false; //返回假
q->rear++; //队尾增1
q->data[q->rear]=e; //rear位置插入元素e
return true; //返回真
}
bool deQueue(SqQueue *&q,ElemType &e) //出队
{ if (q->front==q->rear) //队空下溢出
return false;
q->front++;
e=q->data[q->front];
return true;
}【3】链队
//链队运算算法
#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;
}
void DestroyQueue(LinkQuNode *&q)
{
DataNode *p=q->front,*r;//p指向队头数据结点
if (p!=NULL) //释放数据结点占用空间
{ r=p->next;
while (r!=NULL)
{ free(p);
p=r;r=p->next;
}
}
free(p);
free(q); //释放链队结点占用空间
}
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;
if (q->rear==NULL) //若链队为空,则新结点是队首结点又是队尾结点
q->front=q->rear=p;
else
{ q->rear->next=p; //将p结点链到队尾,并将rear指向它
q->rear=p;
}
}
bool deQueue(LinkQuNode *&q,ElemType &e)
{ DataNode *t;
if (q->rear==NULL) //队列为空
return false;
t=q->front; //t指向第一个数据结点
if (q->front==q->rear) //队列中只有一个结点时
q->front=q->rear=NULL;
else //队列中有多个结点时
q->front=q->front->next;
e=t->data;
free(t);
return true;
}3、典型的算法代码实现
【1】栈的应用——括号配对
#include "listack.cpp"
#include <string.h>
#define MaxSize 9
bool Match(char exp[],int n)
{ char e;
bool match=true;
LinkStNode *st;
InitStack(st); //初始化栈
for (int i=0; i<n; i++) //扫描exp中所有字符
{ if (exp[i]=='I')
Push(st,exp[i]);
else if (exp[i]=='O'&&(Pop(st,e)==false||e!='I'))
{ match=false;
break;
}
}
if (!StackEmpty(st)) match=false; //栈不空时表示不匹配
DestroyStack(st); //销毁栈
return match;
}
int main()
{ char exp[MaxSize];
printf("操作序列为：");
scanf("%s",&exp);
if (Match(exp,strlen(exp)))
printf("操作序列%s中的括号配对\n\n",exp);
else
printf("操作序列%s中的括号不配对\n\n",exp);
return 1;
}【2】利用栈的数据结构对队列进行倒置
#include"sqstack.cpp"
#include"sqqueue.cpp"
ElemType e;
void Reverse(SqQueue *&q)
{
SqStack *s;
InitStack(s);
while(q->front!=q->rear)
{
deQueue(q,e);
Push(s,e);
}
InitQueue(q);
while(s->top>=0)
{
Pop(s,e);
enQueue(q,e);
}
}
int main()
{
//ElemType e;
ElemType data[10]={'a','b','c','d','e','f'};
SqQueue *q;
InitQueue(q);
printf("倒置前为：");
for(int i=0;i<10;i++)
{
enQueue(q,data[i]);
printf("%c",data[i]);
}
Reverse(q);
printf("\n倒置后为：");
for(int i=0;i<10;i++)
{
deQueue(q,e);
printf("%c",e);
}
return 0;
} 【3】栈的应用——表达式匹配
#include "listack.cpp"
#include <string.h>
bool Match(char exp[],int n)
{ char e;
bool match=true;
LinkStNode *st;
InitStack(st); //初始化栈
for (int i=0; i<n; i++) //扫描exp中所有字符
{ if (exp[i]=='('||exp[i]=='['||exp[i]=='{')
Push(st,exp[i]); //遇到'(','['或'{',则将其进栈
else if ((exp[i]==')'&&(Pop(st,e)==false||e!='(')) ||(exp[i]==']'&&(Pop(st,e)==false||e!='['))||(exp[i]=='}'&&(Pop(st,e)==false||e!='{')))
//分别考虑')'、']'和'}'，若不正常配对，就跳出循环
{ match=false;
break;
}
}
if (!StackEmpty(st)) match=false; //栈不空时表示不匹配
DestroyStack(st); //销毁栈
return match;
}
int main()
{ char exp[]="{3*[10-(7-2)]}";
if (Match(exp,strlen(exp)))
printf("表达式%s中的括号配对\n\n",exp);
else
printf("表达式%s中的括号不配对\n\n",exp);
return 1;
}【4】迷宫问题（只输出一条路径）
#include <stdio.h>
#define M 4 //行数
#define N 4 //列数
#define MaxSize 100 //栈最多元素个数
int mg[M+2][N+2]={ //一个迷宫,其四周要加上均为1的外框
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
struct
{ int i,j;
int di;
} St[MaxSize]; //定义栈
int top=-1; //栈顶指针
void dispapath() //输出一条路径
{ int k;
for (k=0;k<=top;k++) //从栈底开始输出路径
printf("(%d,%d) ",St[k].i,St[k].j);
printf("\n");
}
void mgpath(int xi,int yi,int xe,int ye) //求迷宫路径
{ int i,j,i1,j1,di;
top++; St[top].i=xi; St[top].j=yi; St[top].di=-1; //初始方块进栈
mg[xi][yi]=-1;
while (top>-1) //栈不空时循环
{ i=St[top].i; j=St[top].j; di=St[top].di;//取栈顶方块出来
if (i==xe && j==ye) //找到了出口
{ dispapath(); //输出一条路径
return;
}
for (di++; di<4; di++) //找相邻可走方块(i1,j1)
{ switch(di)
{ case 0:i1=i-1; j1=j; break;
case 1:i1=i; j1=j+1; break;
case 2:i1=i+1; j1=j; break;
case 3:i1=i; j1=j-1; break;
}
if (mg[i1][j1]==0) //找到了一个相邻可走方块(i1,j1)
{ St[top].di=di; //修改原栈顶元素的di值
top++;St[top].i=i1;St[top].j=j1;St[top].di=-1;//下一个可走方块(i1,j1)进栈
mg[i1][j1]=-1; //避免重复走到该方块
break;
}
}
if (di==4) //没有路径可走,则退栈
{ mg[i][j]=0; //让该位置变为其他路径可走方块
top--; //将栈顶方块退栈直接丢掉
}
//否则说明上面已找到可走方块且已进栈，此处不用处理，只需单分支
}
}
int main()
{ printf("迷宫路径如下:\n");
mgpath(1,1,M,N);
return 1;
}【5】迷宫问题（输出所有路径）
#include <stdio.h>
#define M 4 //行数
#define N 4 //列数
#define MaxSize 100 //栈最多元素个数
int mg[M+2][N+2]={ //一个迷宫,其四周要加上均为1的外框
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
struct Box
{ int i,j;
int di;
} St[MaxSize]; //定义栈
int top=-1; //栈顶指针
struct MinPath
{
Box data[MaxSize];
int length; //路径长度
}MinType; //存放最短路径
void dispapath() //改为输出一条路径并求最短路径
{ int k;
for (k=0;k<=top;k++) //从栈底开始输出路径
printf("(%d,%d) ",St[k].i,St[k].j);
if(MinType.length>k)
{
MinType.length=k;
for(int t=0;t<MinType.length;t++)
{
MinType.data[t]=St[t];
}
}
printf("\n\t");
}
void outMinPath()
{
printf("长度:%d\n路径：", MinType.length);
for (int i = 0; i < MinType.length; i++)
{
printf("(%d,%d) ", MinType.data[i].i, MinType.data[i].j);
}
}
void mgpath(int xi,int yi,int xe,int ye) //求迷宫路径
{ int i,j,i1,j1,di;
MinType.length=MaxSize;
int pathNum=1; //记录路径数量
top++; St[top].i=xi; St[top].j=yi; St[top].di=-1; //初始方块进栈
mg[xi][yi]=-1;
while (top>-1) //栈不空时循环
{ i=St[top].i; j=St[top].j; di=St[top].di;//取栈顶方块出来
if (i==xe && j==ye) //找到了出口
{
printf("%d:",pathNum++);
dispapath(); //输出一条路径
mg[St[top].i][St[top].j]=0; //此处回溯
top--;
i=St[top].i;j=St[top].j;di=St[top].di;
}
for (di++; di<4; di++) //找相邻可走方块(i1,j1)
{ switch(di)
{ case 0:i1=i-1; j1=j; break;
case 1:i1=i; j1=j+1; break;
case 2:i1=i+1; j1=j; break;
case 3:i1=i; j1=j-1; break;
}
if (mg[i1][j1]==0) //找到了一个相邻可走方块(i1,j1)
{ St[top].di=di; //修改原栈顶元素的di值
top++;St[top].i=i1;St[top].j=j1;St[top].di=-1;//下一个可走方块(i1,j1)进栈
mg[i1][j1]=-1; //避免重复走到该方块
break;
}
}
if (di==4) //没有路径可走,则退栈
{ mg[i][j]=0; //让该位置变为其他路径可走方块
top--; //将栈顶方块退栈直接丢掉
}
//否则说明上面已找到可走方块且已进栈，此处不用处理，只需单分支
}
printf("\n最短路径如下:\n");
outMinPath();
}
int main()
{ printf("迷宫所有路径如下:\n\t");
mgpath(1,1,M,N);
return 1;
}好了，这一章圆满结束，下一章的字符串就在下一篇博客哈~
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)