1、实验报告May72015姓名：陈斌学号：E11314079专业：13计算机科学与技术数据结构第二次实验学号E11314079专业计算机科学与技术姓名陈斌实验日期2015.05.07教师签字成绩实验报告实验名称栈和队列的根本操作的实现【实验目的】1. 理解并掌握栈和队列的逻辑结构和存储结构；2. 理解栈和队列的相关根本运算；3. 编程对相关算法进行验证；4. 学会利用栈和队列解决实际问题。【实验内容】1.实现顺序栈的根本运算编写一个程序，实现顺序栈的各种根本运算，并在此根底上设计一个主程序完成如下功能:(1)初始化栈S;(2)判断栈S是否为空；依次进栈元素-1,2,10,-3,5；(4)判断栈S
2、是否为空；(5)输出栈长度：(6)输出从栈顶到栈底的元素：(7)输出出栈序列；(8)判断栈S是否为空。源代码：head.h:#include#include#include/malloc()#include/INT,MAX#include/EOF,NULL#include/atoi()#include/eof()#include/floor(),ceil(),abs()#include/exit()#include/cout,cin函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/OVERFL
3、OW在math.h中己定义为3typedefintStatus;typedefintBoolean;/布尔类型head2.h:#defineSTACKNnSIZE100#defineSTACKINCREMENT10typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;main.cpp:#defineSEIemTypeint#includehead.h#includehead2.hStatuslnitStack(SqStack&S)*构造一个空栈S*/S.base=(SEIemType*)malloc(STACK_INIT_
4、SIZE*sizeof(SEIemType);if(!S.base)eit(OVERFLOW);/存储分配失败*/S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;)StatusStackEmptyfSqStack&S)*假设栈S为空栈，那么返回TRUE,否那么返回FALSE*/if(S.top=S.base)returnTRUE;elsereturnFALSE;)intStackLengthfSqStack&S)*返回S的元素个数，即栈的长度*/returnS.top-S.base;)StatusGetTop(SqStack&S,SEIemT
5、yPe&e)*假设栈不空，那么用e返回S的栈顶元素，并返回OK；否那么返回ERRoR*/if(S.topS.base)e=*(S.top-l);returnOK;)elsereturnERROR;)StatusPushfSqStack&S,SEiemTyPee)*插入元素e为新的栈顶元素*/if(S.top-S.base=S.stacksize)/*栈满，追加存储空间*/(S.base=(SEIemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SEIemType);if(!S.base)eit(OVERFLOW);/*存储分配
6、失败*/S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;)*S.top+=e;returnOK;)StatusPop(SqStack&S,SElemTyPe&e)*假设栈不空，那么删除S的栈顶元素，用e返回其值，并返回0K；否那么返回ERROR*/if(S.top=S.base)returnERROR;e=*-S.top;returnOK;)StatusStackTraverse(SqStackS,Status(*visit)(SEIemType)*从栈顶到栈底依次对栈中每个元素调用函数ViSit()。*/*一旦ViSit()失败，那么
7、操作失败*/while(S.topS.base)visit(*-S.top);coutendl;return0K;)StatusVisitfSEIemTypec)coutc;returnOK;voidPrintMenuf)cout*欢送使用*11endl;CoUt叮.初始化栈s.endl;COUt”2.判断栈s是否为空Jendl;COUtv”3.依次进栈元素l,2,10,3,5Jendl;COUtV4.输出栈长度Jendl;COUt5.输出从栈顶到栈底的元素.endl;CoUt,6输出出栈序列Jendl;COUt”0.退出.,endl;COut*,)voidmain()SqStacks;SEI
8、emTypee;PrintMenuf);while(l)coutendl;CoUtnumber;switch(number)case 1:InitStackfs);CoUteC”顺序栈s初始化成功Jendl;break;case 2:if(StackEmpty(s)CoUt顺序栈s为空.endl;elseCoUt顺序栈s不为空Jendl;break;case 3:PUSh(S,-1);PUSh(S,2);PUSh(S,10);PUSh(S,-3);PUSh(S,5);CoUt”入栈成功Jendl;break;case 4:coutis的长度为:StackLength(s)endl;break;
9、case 5:8Ut”从栈顶到栈底的元素依次为广；StackTraverse(szvisit);break;case 6: cout”出栈序列为:“；while(!StackEmpty(s)POP(S,e);coute;)coutendl;break;case0:couttttt感谢使用!endl;cout斌斌Jvendl;exit(0);default:CoUt功能选择有误,请重新选择Jendl;)运行结果：2.实现链栈根本运算编写一个程序，实现链栈的各种根本运算，并在此根底上设计一个主程序完成如下功能:(1)初始化栈s；(2)判断栈S是否为空；(3)依次进栈元素10,-2,10,-3,15
10、12；(4)判断栈S是否为空；(5)输出栈长度：(6)输出从栈顶到栈底的元素：(7)输出出栈序列；(8)判断栈S是否为空。源代码：head.h:#include#include#include/malloc()#include/INT,MAX#include/EOF,NULL#include/atoi()#include/eof()#include/floor(),ceil(),abs()#include/exit()#include/cout,cin函数结果状态代码#defineTRUE1#defineFALSEO#defineOK1#defineERRORO#defineINFEASIB
11、LE-1/OVERFLOW在math.h中已定义为3typedefintStatus;typedefintBoolean;/布尔类型head2.h:typedefstructLNode(SElemTypedata;structLNode*next;LNode,*LinkStack;main.cpp:#defineSEIemTypeint#includehead.hftinclude,head2.hStatusInitLinkStacktLinkStack&L)1.=(LinkStack)malloc(sizeof(LNode);*产生头结点,并使S指向此头结点*/if(!L)/*存储分配失败*
12、/exit(OVERFLOW);1.-next=NULL;/*指针域为空*/returnOK;)StatusLinkStackEmptyfLinkStack&L)/*假设栈S为空栈，那么返回TRUE,否那么返回FALSE*/if(L-next=NULL)returnTRUE;elsereturnFALSE;)intLinkStackLengthtUnkStack&L)inti=0;1.inkStackp=L-next;while(p)+i；p=p-next;)returni;)StatusHeadInserttLinkStack&L,SEIemTyPee)1.inkStacks;s=(Link
13、Stack)malloc(sizeof(LNode);*生成新结点*/s-data=e;/*给结点赋值*/s-net=L-next;/*插在表头*/1.-next=s;returnOK;)StatusDeleteFirst(LinkStack&L,SEIemType&e)1.inkStackp=L-next;if(p)e=p-data;1.-next=p-next;free(p);returnOK;)elsereturnERROR;)StatusLinkStackTraverse(LinkStack&LzStatus(*visit)(SEIemType)(1.inkStackp=L-net;w
14、hile(p)visit(p-data);p=p-next;)coutendl;returnOK;)StatusVisitfSEIemTypec)coutc;returnOK;voidPrintMenuf)cout*欢送使用*11endl;COUtL初始化栈s.endl;COUt”2.判断栈s是否为空Jendl;CoUk”3.依次进栈元素10,-2,10,-3,15,12Jendl;COUt4.输出栈长度Jendl;COUt5输出从栈顶到栈底的元素.,endl;COUt”6.输出出栈序列Jendl;cout0.i三.,endl;COut*)voidmain()1.inkStacks;SEIem
15、Typee;PrintMenuf);while(l)coutendl;CoUtnumber;switch(number)case 1:InitLinkStack(s);COUt”链栈s初始化成功.endl;break;case 2:if(LinkStackEmpty(s)CoUt链栈s为空Jendl;elseCoUt”链栈s不为空.endl;break;case 3:HeadlnSert(S,10);HeadInSert(S,-2);HeadInSert(S,10);HeadmSert(S,-3);HeadInSert(S,15);Headlnsert(s,12);CoUt”入栈成功.endl
16、break;case 4:CoUt链栈s的长度为:LinkStackLength(s)endl;break;case 5:CoUt”从栈顶到栈底的元素依次为:“；1.inkStackTraverse(SzVisit);break;case 6:CoUteC咄栈序列为:;while(!LinkStackEmpty(s)DeleteFirst(sze);coute)coutendl;break;caseO:couttttt感谢使用!,endl;cout斌斌Avendl;eit(0);default:COUt功能选择有误,请重新选择Jendl;)运行结果：3.实现循环队列的根本运算编写一个程序，实
17、现循环队列的各种根本运算，并在此根底上设计一个主程序完成如下功能：(1)初始化队列q；(2)判断队列q是否为空：(3)依次进队列元素-1,2,10；(4)出队一个元素，并输出该元素：(5)输出队列的长度(元素个数)；(6)依次进队元素-3,12,10；输出出队序列；(8)判断队列q是否为空。源代码：head.h:#include#include#include/malloc()#include/INT,MAX#include/EOF,NULL#include/atoi()#include/eof()#include/floor(),ceil(),abs()#include/exit()#inc
18、lude/cout,cin函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/OVERFLOW在math.h中已定义为3typedefintStatus;typedefintBOOIean;/布尔类型head2.h:#defineMAXQSIZE100*最大队列长度(对于循环队列，最大队列长度要减1)*/typedefstruct(QElemType*base;/*初始化的动态分配存储空间*/intfront;/*头指针,假设队列不空,指向队列头元素*/intrear;/*尾指针,假设队列不空,
19、指向队列尾元素的下一个位置*/JSqQueue;main.cpp:#defineQEIemTypeint#includehead.h#includehead2.hStatusInitQueuefSqQueue&Q)*构造一个空队列Q*/Q.base=(QEIemType*)malloc(MAXQSIZE*sizeof(QEIerType);if(!Q.base)/*存储分配失败*/exit(OVERFLOW);Q.front=Q.rear=0;returnOK;)StatusQueueEmptyfSqQueue&Q)/*假设队列Q为空队列,那么返回TRUE,否那么返回FALSE*/if(Q.f
20、ront=Q.rear)/*队列空的标志*/returnTRUE;elsereturnFALSE;)intQueueLengthfSqQueue&Q)*返回Q的元素个数,即队列的长度*/return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;)StatusEnQueuefSqQueue&CbQEIemTypee)/*插入元素e为Q的新的队尾元素*/if(Q.rear+l)%MAQSIZE=Q.front)/*队列满*/returnERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+l)%MAXQSIZE;returnOK;StatusDeQueue
21、fSqQueue&Q,QEIemTyPe&e)*假设队列不空,那么删除Q的队头元素,用e返回其值,并返回OK;否那么返回ERROR*/if(Q.front=Q.rear)/*队列空*/returnERROR;e=Q.baseQ.front;Q.front=(Q.front+l)%MAXQSIZE;returnOK;voidPrintMenu()cout* * *欢送使用*”endl;CoUt1.初始化队列q.endl;COUt2.判断队列q是否为空Jendl;COUt”3.依次进队列元素l,2,10.endl;COUt”4.出队一个元素，并输出该元素Jendl;COUt,5.输出队列的长度（元
22、素个数）.,endl;CoUt6依次进队元素-3,12,10.endl;CoUt”7.输出出队序列Jendl;cout,0.iMlBendl;cout,I*Il)voidmain()SqQueueq;QEIemTypee;PrintMenu();while(l)coutendl;CoUtnumber;switch(number)case 1:InitQueue(q);CoUt”队列q初始化成功.endl;break;case 2:if(QueueEmpty(q)COUt”队列q为空Jendl;elseCoUt”队列q不为空Jendl;break;case 3:EnQueue(q,-l);EnQ
23、ueuefq,2);EnQUeiJe(q,10);CoUt入队歹J成功.endl;break;case 4:DeQueue(q,e);cout出队列成功.该元素为:eendl;break;case 5:CoUt”队列q的长度为:QueueLength(q)endl;break;case 6:EnQUeUe(q,-3);EnQueuefq,12);EnQUeUe(q,10);CoIIt,入队列成功.endl;break;case 7:CoUt”出队序列为:“；WhiIe(IQueueEmptyfq)DeQueue(q,e);coute)coutendl;break;case0:couttttt感
24、谢使用!,endl;cout斌斌J,endl;eit(O);default:CoUt”功能选择有误,请重新选择.endl;)运行结果：4.实现链队列的根本运算编写一个程序，实现链队列的各种根本运算，并在此根底上设计一个主程序完成如下功能:(1)初始化队列q：(2)判断队列q是否为空；(3)依次进队列元素1,12,-10；(4)出队一个元素，并输出该元素；(5)输出队列的长度(元素个数)；(6)依次进队元素13,-12,10；(7)输出队列长度;(8)输出出队序列。源代码：head.h:#include#include#include/malloc()include/INT,MAXinclude
25、/EOF,NULLinclude/atoi()#include/eof()#include/floor(),ceil(),abs()#include/exit()#include/cout,cin函数结果状态代码#defineTRUEl# defineFALSE0# defineOK1# defineERROR0# defineINFEASIBLE-1/OVERFLOW在math.h中已定义为3typedefintStatus;typedefintBoolean;/布尔类型head2.h:typedefstructQNode(QElemTypedata;structQNode*next;QNo
26、deQueuePtr;typedefstruct(QueuePtrfront,rear;*队头、队尾指针*/JLinkQueue;main.cpp:#defineQEIemTypeint#includehead.h#includehead2.hStatuslnitQueue(LinkQueue&Q)*构造一个空队列Q*/Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;)StatusQueueEmptylLinkQueue&Q)*假设Q为空队列,
27、那么返回TRUE,否那么返回FALSE*/if(Q.front=Q.rear)returnTRUE;elsereturnFALSE;)intQueueLength(LinkQueue&Q)*求队列的长度*/inti=0;QueuePtrp;p=Q.front;while(Q.rear!=p)+i；p=p-next;)returni;)StatusGetHeadlLinkQueueQ,CIemType&e)*假设队列不空,那么用e返回Q的队头元素,并返回OK,否那么返回ERROR*/QueuePtrp;if(Q.front=Q.rear)returnERROR;p=Q.front-next;e=
28、p-data;returnOK;)StatusEnQueuefLinkQueue&Q,QEIemTyPee)*插入元素e为Q的新的队尾元素*/QueuePtrP=(QUeilePtljmalIOC(SiZeOf(QNOde);if(!p)/*存储分配失败*/eit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;)StatusDeQueuefLinkQueue&Q,Q日emType&e)/*假设队列不空,删除Q的队头元素,用e返回其值,并返回OK,否那么返回ERROR*/QueuePtrp;if(Q.front=Q.
29、rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;voidPrintMenu()COUt,1,初始化队列q.endl;CoUt2.判断队列q是否为空.endl;CoUt.依次进队列元素12,-10.endl;CoUt,4.出队一个元素，并输出该元素Jendl;COUt,5.输出队列的长度(元素个数).,endl;COUt”6.依次进队元素13,-12,10.endl;COUt”7.输出出队序列Jendl;cout0.iMendl;U*”
30、)voidmain()(1.inkQueueq;QEIemTypee;PrintMenu();while(l)(coutnumber;switch(number)case 1:InitQueue(q);CoUt”队列q初始化成功Jendl;break;case 2:if(QueueEmpty(q)CoUt队列q为空.endl;elseCoUt”队列q不为空.,endl;break;case 3:EnQueue(qzl);EnQUeUe(q,12);EnQueue(q,-10);CoUt入队歹J成功.endl;break;case 4:DeQueue(q,e);COUt”出队列成功.该元素为:
31、eendl;break;case 5:CoUt队歹IJq的长度为:QueueLength(q)endl;break;case 6:EnQUeUe(q,13);EnQueue(qz-12);EnQUeUe(q,10);COUt”入队歹!成功.endl;break;case 7:CoUt”出队序列为:“；WhiIe(IQueueEmptyfq)DeQueue(q,e);coute)coutendl;break;case0:couttttt感谢使用!,endl;cout斌斌J,endl;eit(O);default:COUt”功能选择有误,请重新选择Jendl;)运行结果：附加题：1.借助栈实现数制
32、转换。要求将非负十进制整数N转换为二进制输出。源代码：head.h:#include#include#include/malloc()#include/INT,MAX#include/EOF,NULL#include/atoi()#include/eof()#include/floor(),ceil(),abs()#include/exit()#include/cout,cin函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/OVERFLOW在math.h中已定义为3typedefintSta
33、tus;typedefintBOOIean;/布尔类型head2.h:#defineSTACKNnSIZE100#defineSTACKINCREMENT10typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;main.cpp:#defineSEIemTypeint#includehead.h#includehead2.hStatusInitStackfSqStack&S)*构造一个空栈S*/S.base=(SEIemType*)malloc(STACK_INIT_SIZE*sizeof(SEIemType);if(!S
34、base)exit(OVERFLOW);*存储分配失败*/S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;)StatusStackEmptyfSqStack&S)*假设栈S为空栈，那么返回TRUE,否那么返回FALSE*/if(S.top=S.base)returnTRUE;elsereturnFALSE;)StatusPushfSqStack&S,S曰emTypee)*插入元素e为新的栈顶元素*/if(S.top-S.base=S.stacksize)/*栈满，追加存储空间*/S.base=(SEIemType*)realloc(S.ba
35、se,(S.stacksize+STACKINCREMENT)*sizeof(SEIemType);if(!S.base)eit(OVERFLOW);/*存储分配失败*/S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;)*S.top+=e;returnOK;)StatusPop(SqStack&S,SEIemTyPe&e)*假设栈不空，那么删除S的栈顶元素，用e返回其值，并返回0K；否那么返回ERROR*/if(S.top=S.base)returnERROR;e=*-S.top;returnOK;)voidconversion()*对
36、于输入的任意一个非负十进制整数，打印输出与其等值的二进制数*/SqStacks;intn;SEIemTypee;InitStack(三);/*初始化栈*/do(CoUtn;while(n0);CoUt非负十进制整数n转换为二进制数为:n;if(n=O)cout0;While(n)/*当n不等于0*/(PUSh(S,n%2);/*入栈n除以2的余数(2进制的低位)*/n=n2;while(!StackEmpty(s)/*当栈不空*/Pop(s,e);/*弹出栈顶元素且赋值给e*/coute;/*输出e*/coutendl;)voidmain()conversion);运行结果:2.借助队列实现杨
37、辉三角的评算。要求输出输出杨辉三角的前N行。源代码:head.h:#include#include#include/malloc()#include/INT,MAX#include/EOF,NULL#include/atoi()#include/eof()#include/floor(),ceil(),abs()#include/exit()#include/cout,cin函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/OVERFLOW在math.h中已定义为3typedefintStat
38、us;typedefintBoolean;/布尔类型head2.h:typedefstructQNode(QElemTypedata;structQNode*next;QNode,*QueuePtr;typedefstruct(QueuePtrfront,rear;*队头、队尾指针*/JLinkQueue;main.cpp:#defineQEIemTypeint#includehead.h#includehead2.hStatusInitQUeUe(LinkQUeUe&Q)*构造一个空队列Q*/Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;)StatusQUeUeEmPty(LinkQUeUe&Q)*假设Q为空队列,那么返回TRUE,否那
