数据结构栈和队列的基本操作及应用实验报告.docx
- 文档编号:13355071
- 上传时间:2023-06-13
- 格式:DOCX
- 页数:28
- 大小:36.74KB
数据结构栈和队列的基本操作及应用实验报告.docx
《数据结构栈和队列的基本操作及应用实验报告.docx》由会员分享,可在线阅读,更多相关《数据结构栈和队列的基本操作及应用实验报告.docx(28页珍藏版)》请在冰点文库上搜索。
数据结构栈和队列的基本操作及应用实验报告
实验日期2010.4.26教师签字成绩
【实验目的】
(1)熟悉栈的特点(先进后出)及栈的基本操作,如入栈、出栈等,掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现;
(2)熟悉队列的特点(先进先出)及队列的基本操作,如入队、出队等,掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。
【实验内容】
1.链栈的基本操作(链栈的初始化、进栈、出栈以及取栈顶的
值)
#includeHstdio.hH
#includeHmalloc.hn
include"stdlib.h"
typedefintElemtype;
typedefstructstacknode{
Elemtypedata;
stacknode*next;
JStackNode;
typedefstruct{
stacknode*top;〃栈顶指针
}LinkStack;
/*初始化链栈*/
voidInitStack(LinkStack*s)
{s->top=NULL;
printf("\n已经初始化链栈!
\n”);
)
/*链栈置空*/
voidsetEnipty(LinkStack*s)
{s・>top二NULL;
printf(H\n链栈被置空!
\n”);
}
/*入栈*/
voidpushLstack(LinkStack*s,Elemtypex)
{StackNode*p;p=(StackNode*)maHoc(sizeof(StackNode));〃建立一个节点°p->data=x;
p->next=s->top;//ill于是在栈顶pushLstack,所以要指向栈顶。
s->top=p;〃插入
}
/*出栈勺
ElemtypepopLstack(LinkStack*s)
{Elemtypex;
StackNode*p;p=s->top;〃指向栈顶
if(s->top==0)
{printf("\n栈空,不能出栈!
\n”);exit(-l);
}
x=p->data;
s->top=p->next;〃当前的栈顶指向原栈的next
free(p);〃释放
returnx;
}
/*取栈顶元素*/
ElemtypeStackTop(LinkStack*s)
{if(s->top==0)
{printf(H\n链栈空\n”);
exit(-l);
)
returns->top->data;
}
/*遍历链栈*/
voidDisp(LinkStack*s)
{printf("\n链栈中的数据为:
\n");
printf(H======================================\nn);StackNode*p;
p=s->top;
while(p!
=NULL)
{printf(H%d\n'\p->data);
p=p->next;
}printf("=======================================\n");
}
voidmain()
{printf(H====================链栈操作==========\n\nj;
inti,m,n,a;LinkStack*s;s=(LinkStack*)malloc(sizeof(LinkStack));intcord;
do{printf(H\nn);
printf(”第一次使用必须初始化!
\nH);
printf(H\ii
主菜单
W);
printf(H\n
1
初始化链栈
\n“);
printf(H\n
2
入栈
\n“);
printf(M\ii
3
出栈
\n");
printf(H\n
4
取栈顶元素
\n");
printf(H\n
5
置空链栈
\n");
printf(H\n
6
结束程序运行
\n”);
printf(H\n
printfC*请输入您的选择(1,2,3,4,5,6)”);
scanf(M%d,\&cord);
printf(H\nn);
switch(cord)
{case1:
{InitStack(s);
Disp(s);
}break;
case2:
(printfC输入将要压入链栈的数据的个数:
I匸“);scanf(”%d”,&n);
printf(”依次将%d个数据圧入链栈:
\n",n);
for(i=l;i<=n;i++)
{scanf("%d”,&a);pushLstack(s,a);
}
Disp⑸;
[break;
case3:
{printf("\n出栈操作开始!
\n“);printf("输入将要出栈的数据个数:
m=”);scrmf(”%d:
&m);
for(i=I;i<=m;i++)
{printf("\n第%d次出栈的数据是:
%d",i,popLstack(s));)Disp(s);
[break;
case4:
{printf("\n\n链栈的栈顶元素为:
%d\n",StackTop(s));printf(H\nH);
(break;
case5:
{setEnipty(s);
Disp(s);
(break;
case6:
exit(O);
}
)while(cord<=6);
}
2.顺序栈的基本操作(顺序栈的初始化、进栈、出栈以及取栈顶的值)
#include
#include
#include
#defineSTACKSIZE100
#defineSTACKINCREMENT10
#definenull0
typedefstruct{
int水base;
int*top;
intstacksize;
}SqStack;
SqStackInitstack()
{
SqStackS;
S.base=(int*)malloc(STACKSIZE*sizeof(int));
if(!
S.base){printf("\n存储分配失败\n");exit(0);}
S.top=S.base;
S.stacksize二STACKSIZE;
returnS;
}
intStackEmpty(SqStackS)
{
if(S.top==S.base)return1;
elsereturn0;
}
intStackLength(SqStackS)
{
int*p;
p=S.base;
for(inti=0;p!
=S・top;p++,i++);
returni;
intGetTop(SqStackS)
inte;
if(StackEmpty(S)){printf(”当前栈为空,不能执行此操作\n”);exit(O);}e=*(S.top-l);
returne;
}
intPush(SqStack&Sjnte)
{
if(StackLength(S)>=S.stacksize){
S.base=(int
*)realloc(S.base,(STACKSIZE+STACKINCREMENT)*sizeof(int));
if(!
S.base){printf("\n再分配存储失败\n");return0;}
S・top=S・base+S.stacksize;
S.stacksize+二STACKINCREMENT;
}
*S.top++=e;
return1;
}
intPop(SqStack&S)
{
inte;
if(StackEmpty(S)){printf("当前栈为空,不能执行此操作\n”);exit(0);}
e=*—S.top;
returne;
}
voidmain()
{
inti=0,e;
int*p;
SqStackS;
S=Initstack();
printf("\n1.元素进栈\n2.元素出栈\n3.取栈顶元素\n4.
求栈的长度\n5.判栈空\n6.退出\n“);
for(;i!
=6;){
printf(“\n请选择你要进行的操作:
“);
scanf(H%d\&i);
switch(i){
casel:
printf("\n请输入进栈元素:
");
scanf(”%cT,&e);
Push(S,e);p=S.base;
printf("\n当前栈中元素:
");if(StackEmpty(S))printfC'当前栈为空\n”);while(p!
=S.top){printf(n%d'\*p);p++;}
break;
case2:
printf("\n%d已出栈\n",Pop(S));printf("\n当前栈中元素:
”);if(StackEmpty(S))printf(,'当前栈为空\n“);
p=S.base;
while(p!
=S.top){printf("%d",*p);p++;}break;
case3:
printf("\n栈顶元素为:
%d\n",GetTop(S));break;
case4:
printf("\n栈的长度为:
%d\n",StackLength(S));break;
case5:
if(StackEmpty(S))printf("\n当前栈为空\n");
elseprintf("\n当前栈不空\n");break;
default:
printf("\n退出程序\n");
}
}
}
3•顺序队列的基本操作(顺序队的初始化、进队、出对以及取对
头)
#include
#include
#defineMAXNUM100
#defineElemtypeint
#defineTRUE1
#defineFALSE0
typedefstruct
{ElemtypequeuefMAXNUM];
intfront;
intrear;
Jsqqueue;
/*队列初始化*/
intinitQueue(sqqueue*q)
{if(!
q)returnFALSE;
q->front=-1;
q->rear=-1;
returnTRUE;
}
/*入队*/
intappend(sqqueueElemtypex)
{if(q->rear>=MAXNUM-1)returnFALSE;
q->rear++;
q->queue[q->rear]=x;
returnTRUE;
/*出队*/
ElemtypeDelete(sqqueue*q)
{Elemtypex;
if(q->front==q->rear)return0;
x=q->queue[++q->front];
returnx;
}
/*判断队列是否为空*/
intEmpty(sqqueue*q)
{if(q->front=q->rear)returnTRUE;
returnFALSE;
}
/*取队头元素*/
intgethead(sqqueue*q)
{if(q->front==q->rear)return0;return(q->queue[q->front+1]);
)
/*遍历队列*/
voiddisplay(sqqueue*q)
{ints;
s=q->front;
if(q->front==q->rear)printf(”队列空!
\n“);
else
{printf("\n顺序队列依次为:
“);while(s
{s=s+l;
printf(H%d<-'\q->queue[s]);
}
printf(H\nH);
printf("顺序队列的队尾元素所在位置:
rear=%d\n",q->rear);printf("顺序队列的队头元素所在位S:
front=%d\n",q->front);
}
)
/*建立顺序队列*/
voidSetsqqueue(sqqueue*q)
{intnjjn;
printf("\n请输入将要入顺序队列的长度:
”);scanf(H%d,r,&n);
printfC*\n请依次输入入顺序队列的元素值:
\n“);
for(i=0;i {scanf(”%d”,&m); append(qjn);} main() {sqqueue*head; intx,y,z,select;head=(sqqueue*)malloc(sizeof(sqqueue)); do{printf("\n第一次使用请初始化! \n"); printf("\n请选择操作(1-7): \n”); printf("=================================\n");printf(nl初始化\n“); printf("2建立顺序队列\n"); printf("3入队\n”); printf("4出队\n“); printf("5判断队列是否为空\n“); printf("6取队头元素\n"); printf(H7遍历队列\n“);printf(,,===================================\n");scanf("%d",&select); switch(select) {case1: {initQueue(head); printfC'B经初始化顺序队列! \n“);break; ) case2: {Setsqqueue(head); printf("\n已经建立队列! \n"); display(head);break; ) case3: {printf("请输入队的值: \n”); scanf(”%cT,&x); append(head,x);display(head); break; ) case4: {z=Delete(head); printf("\n队头元素%(1已经出队! \n",z);display(head); break; ) case5: if(Empty(head)) printf(”队列空\n”); else printf("队列非空\n“); break; } case6: {y=gethead(head); printf("队头元素为: %d\n",y); break; ) case7: {display(head); break; } } }while(select<=7); } 4•链队列的基本操作(链队列的初始化、进队、出对操作) #include #include #defineElemTypeint typedefstructQnode {ElemTypedata; structQnode*next; (Qnodetype; typedefstruct {Qnodetype*front; Qnodetype*rear; JLqueue; /*初始化并建立链队列*/ voidcreat(Lqueue*q) {Qnodetype*h; inti,n,x; printf(”输入将建立链队列元素的个数: n=”); scanf(“%d",&n); h=(Qnodetype*)malloc(sizeof(Qnodetype)); h->next=NULL; q->front=h; q->rear=h; for(i=l;i<=n;i++) {printfC链队列第%<1个元素的值为: ”,i); scanf(“%d”,&x); Lappend(q,x); ) /*入链队列*/ voidLappend(Lqueue*q,intx) {Qnodetype*s;s=(Qnodetype*)manoc(sizeof(Qnodetype));s->data=x; s->next=NULL; q->rear->next=s; q->rear=s; } /*出链队列勺 ElemTypeLdelete(Lqueue*q) {Qnodetype*p; ElemTypex; if(q->front==q->rear) {printfC*队列为空! \n“); x=0; ) else {p=q->front->next; q->front->next=p->next;if(p->next=NULL)q->reai*=q->front; x=p->data; free(p); } return(x); ) /*遍历链队列*/ voiddisplay(Lqueue*q) {Qnodetype*p; p=q->front->next;/*指向第一个数据元素节点*/ printf("\n链队列元素依次为: ”); while(p! =NULL) {printf("%d—>",p->data); p=p->next; } printf(H\n\n遍历链队列结束! \nn); } main() {Lqueue*p; intx^cord; printf(H\n*****第一次操作请选择初始化并建立链队列! **林*\口”); W); W); printf(M 1 初始化并建立链队列 \nn); printf(” 2 入链队列 S'); printf(” 3 出链队列 S'); printf(H 4 遍历链队列 W); printf(H 5 结束程序运行 W); 主菜单 W); printf(H=======================================\nH); printf(H scanf(M%d1',&cord); switch(cord) {case1: {p=(Lqueue*)malloc(sizeof(Lqueue));creat(p); display(p); }break; case2: {printf(“请输入队列元素的值: x=“); scanf(”%d”,&x); Lappend(p,x);display(p); (break; case3: {printf(n出链队列元素: x=%d\ii*\Ldelete(p)); display(p); (break; case4: {display(p);)break; case5: {exit(0);)} (while(cord<=5); ) 5•循环队列的基本操作: #include int*base;intfront;intrear; ); voidinitQueue(Queue&Q) { Q.base=(int*)malloc(maxsize*sizeof(int)); Q.front=Q.rear=0; } intQueueLen(QueueQ) { return(Q.rear-Q・front+maxsize)%maxsize; } voidEnQueue(Queue&Q,inte) { if((Q.rear+1)%maxsize=Q.front) cout«"队列已满,无法插入! "«endl; else { Q.base[Q.rear]=e;Q.reai-(Q.rear+l)%maxsize; ) } intDeQueue(Queue&Q,int&e) { if(Q.reai"==Q.front)coutvv"队列已空,无法删除「vvendl;else { e=Q.base[Q.front];Q.front=(Q.front+1)%maxsize; cout«"被删除的元素是: ,<<'\t'«e«endl; returne; } ) voidmain() { QueueQ; initQueue(Q); loop: cout«、Fvv"请选择你要进行的操作: "«endl; cout«'\t'«"1.插入元素"< inti;cin»i; switch(i) { case(l): { inte; coutvv”请输入要插入的元素: cin»e; EnQueue(Q,e); gotoloop; } case (2): { inte; DeQueue(Q.e); gotoloop; } case(3): { int1; l=QueueLen(Q); cout«"队列的长度为: "«'\t'«l«endl;gotoloop; ) case(4): break; default: cout«"输入错误,请重新输入! "«endl;gotoloop; } } 6•两个栈实现队列的功能 #include #include #include #include #defineSTACK_INIT_SIZE100 #defineSTACKINCREMENT10 typedefcharSElemType; typedefstruct { SEIeniType*base; SEleniType*top; intstacksize; JSqStack; 〃队列III两个栈S1.S2构成 typedefstruct { SqStackS1; SqStackS2; }Queue; voidInitStack(SqStack*S) S->base=(SElemType*)malloc(STACKJNIT_SIZE*sizeof(SElemType));if(! S->base)exit(O); S->top=S->base;S->stacksize=STACK_INIT_SIZE; } voidpush(SqStack*S,SElemTypee) { if(S->top-S->base==S->stacksize
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 队列 基本 操作 应用 实验 报告