计算机软件技术基础实验报告.docx

《计算机软件技术基础实验报告.docx》由会员分享，可在线阅读，更多相关《计算机软件技术基础实验报告.docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验二 栈和队列的基本操作一、实验目的1 .掌握栈与队列的数据类型描述及特点；2 .掌握栈和队列的存储；3 .掌握栈的顺序和链式存储存表示与入栈、出栈操作的程序实现；4 .掌握队列的链式存储表示与入队、出队基本操作算法实现。二、实验用软件和工具实验软件VC+ 6. 0三、实验步骤1 .根据栈数据结构，分别建立一个顺序栈和链式栈并实现其上基本操作(出栈和入栈等)， 定义一个顺序栈和链栈结构体(队列结构体)。2 .利用入栈功能保存数据。3 .利用出栈删除弹出栈内信息。4 .根据队列数据结构，分别建立链队列和循环队列，并完成其上的基本操作(出入队列等), 利用入队功能保存数据。5 .利用出队删除队列

2、信息。四、实验程序与程序运行结果顺序栈程序：sxz.h#include using namespace std;template class sq_Stackprivate:int mm;int top;T *s;public:sq_Stack(int);void prt_sq_Stack();void ins_sq_Stack(T x);T del_sq_Stack();T read_sq_Stack();)；template sq_Stack: sq_Stack(int m)(mm=m;6 = new Tmm;top=0;int x;while(flag)(coutn链式队列基本操作翁翁n

3、endl;cout,.创建队列 nendl;coutn.判断链队列是否为空endl;coutn.队头元素出队翁” vendl;cout,.新元素入队 nendl;cout!,.求队列长度 nendl;coutM.输出队列元素食Hendl;cout,.查找第i个位置元素 nendl;cout,.销毁队列 nendl;cout,食9 .其他键退出 Mendl;coutendl;cout ”请选择操作：”；cinselect;switch(select)(InitQueue_L(Q);CreateQueue_L(Q);OutputQueue_L(Q);break;if(IsEmpty(Q) cout

4、v”该队列为空! nendl;else cout”该队列不为空! nendl;break;if(IsEmpty(Q) coutvv”队列为空！ endl; break;DeleteQueue(Q,x);OutputQueue_L(Q);break;if(IsEmpty(Q) cout”队列还未创建！endl; break; cout输入要入队的元素X: ； cinx;EnterQueue(Q,x);OutputQueue_L(Q);break;if(IsEmpty(Q) cout”队列还未创建！endl; break;coutv”该链队歹U的长度为：HQueueLength_L(Q)endle

5、ndl; break;case 8:if(IsEmpty(Q) coutv” 队列还未创建！vvendl; break; DestroyQueue_L(Q);cout”销毁成功! nendlendl;break;case 7:cout”请输入要查找的位置i：cinx;if(xQueueLength_L(Q) coutHi 值不合法！nendl; break; cout该元素为：n. 7 I J 44 I基列出队度元M出列列队京长列J列退队队链元素列队晟键 式建断头元队出鬣他 链创判队新求辑_襄 123456789请选择操作：6队列的元素依次为：2 3 4 5 6 空 为 否仝 素 元 置:是队

6、素汇， 基列出队度元刈出 列列队支长列J列退队队链元素列队晟键式建断头元队出般他 链创判队新求兽_襄 1234567.89请选择操侪7请输要看我的位置i：3该元素为：4本是队素1-V- y11 V 44基列出队度元M出列列队支长列J列退队队链元素列队晟键 式建断头元队出登他 链创判队新求善_襄 - - T123456789 空 为 否仝是队素-r-基列出队度元忸出列列队支长列)列退队队链元素列队卷键 式建断头元队出弱他 链创判队新求毒 襄 1234567.89请选择操作：9Press any key to continue五、实验心得与体会通过本次上机实验，我掌握了栈的顺序和链式存储存表示与入

7、栈、出栈操作的程序实现，以 及队列的链式存储表示与入队、出队基本操作算法实现。遇到问题难以避免，认真研究代码还 是可行的，最后成功做出实验。return;template void sq_Stack:prt_sq_Stack()(int i;coutHtop=,topendl;for (i=top;i0;i-) coutsi-l endl;return;template void sq_Stack:ins_sq_Stack(T x) (if (top=mm)coutnoverflow!Hendl; return;/存储空间已满,上溢错误tOp=tOp+l；/stop-l=x;插入新元素retu

8、rn;templateT sq_Stack:del_sq_Stack()Ty;if(top=0)/空，下溢错误coutnunderflow! nendl; retum(O); y=stop-l; /top=top-1; 长度减 1 return(y);)templateT sq_Stack:read_sq_Stack()(if(top=0)/空，下溢错误coutHunderflow! nendl; retum(O); return(stop-l);sxz.cpp#include Msq_Stack.hnint main()(sq_Stack s(10);s.ins_sq_Stack(5O);s

9、.ins_sq_Stack(60);s.ins_sq_Stack(70);s.ins_sq_Stack(8O);s.ins_sq_Stack(90);s.ins_sq_Stack(l 00);coutvv”第1次输出栈顶指针与栈中的元素:endl;s.prt_sq_Stack();coutvv”输出栈顶元素:vvs.read_sq_Stack()endl; cout ”输出退栈的元素:Hendl;couts.del_sq_Stack()endl;couts.del_sq_Stack()endl;couts.del_sq_Stack()endl;coin v v ”再输出瓶顶指针与栈中的元素:H

10、endl;s.prt_sq_Stack(); return 0;)顺序队列程序：sq_Queue.h#include using namespace std;template class sq_Queueprivate:int mm;int front;int rear;int s;T*q;public:sq.Queue(int);void prt_sq_Queue();void ins_sq_Queue(T x);T del_sq_Queue();；template sq_Queue:sq_Queue(int m) (mm=m;q = new Tmm;front=mm;rear=mm;s=0

11、; return;) template void sq_Queue:prt_sq_Queue()(int i;coutHfront=nfrontendl;coutn rear=n rearendl;if (s=0)&(rear=front)cout=mm)front=i%mm ;for (i=front; irear;i+)coutqiendl;return;template void sq_Queue: ins_sq_Queue(T x)if (s= 1 )&(rear=front)coutnQueue_overflow!uendl; return;/存储空间已满，上溢错误 rear=rea

12、r+l; /if (rear=mm+l) rear= 1;qrear-l=x;插入新元素s=l;return;)template T sq_Queue:del_sq_Queue()(Ty;if (s=0)coutnQueue_underflow!nendl; return(O);存储空间已满,上溢错误 front=front+l; /if (front=mm+l) front=l;y=qfront-l ;插入新元素if (rear=front)s=0;return(y);)#include sq_Queue.hint main()(sq_Queue q(10);q.prt_sq_Queue()

13、;q.ins_sq_Queue(50);q.ins_sq_Queue(60);q.ins_sq_Queue(70);q.ins_sq_Queue(80);q.ins_sq_Queue(90);q.ins_sq_Queue(l 00);cout ”输出队头与队尾指针及队列中的元素:“endl;q.prt_sq_Queue();coutv输出退队元素:endl;coutq.del_sq_Queue()endl;coutq.del_sq_Queue()endl;coutq.del_sq_Queue()endI;cout”再输出以头与队尾指针及队列中的元素:“ endl;q.prt_sq_Queue(

14、);return 0;链栈：#include #include #include typedef char DateType; typedef struct nodeDateType data;struct node* next; LinkStack;LinkStack *top;void InitStack()top=(LinkStack)malloc(sizeof(LinkStack);top-next=NULL;top-data=0;coutdata=x;s-next=top;top=s;coutv”入栈成功!”;)void pop()(LinkStack* s;s=top;if(s-n

15、ext=NULL)cout 栈为空!”;) else(top=s-next;free(s);coutv”出栈成功”；)void readTopO(if(top=NULL)(coutvv栈为空!”;)else(cout栈顶元素为:data;)void showStack()(LinkStack* s;s = top;if(s-next=NULL)(cout 栈为空!”；)elsecoutvv”链栈元素为:n”;coutntttH;while。!=NULL)coutn ns-data;s=s-next;)void main()int ij;DateType x; while(j)coutnnnnn

16、n;cout cout cout cout coutf f 7，*3* 7, 7, 7，7，7，7, 7，7，7，*!7, 7，7，7，7, 7，7，7，*!*7, 7，7，7, 7，7，7，*!7, 7，7，7, 7, 7，7，7，*3* 7, 7, 7，7，7，1,1 1、ry*、q、*4*、*4* *2* *4* *4*、q、*4*、*4*、q、J、*4* *7*、J、4*、q、z1 I ”*”*”*菜单：创建链栈出栈入栈显示链栈元素退出*”*x*1* .1 .!* .!*k| kI k1 kJkI* *a*1*3 *x*!* .!*k| k1 k1*1!* .J* *a* IQ./i

17、iT*rj* T*T* Tw *7* rj* ri* 1* ri* ri* 1* T* T1* T* T*ri* ri*7 7 ri* TwrT* ri* 1* *1*rj* T* TwI coutv”请选择您所希望的操作：” cini;if(i=l)InitStackQ;else if(i=2)if(top=NULL)cout”请先初始化链表!”;)elsecout ”请输入要入栈的元素:;cinx;push(x);)else if(i=3)(pop()；else if(i=4)(readTopO;else if(i=5)(showStackQ;)else if(i=6)(j=0;coutv

18、v”程序结束n”;)链队列：#include #include#define TRUE 1#define FALSE 0typedef int QElemType;typedef struct LNodeQElemType data;struct LNode *next; LNode, *LinkList;typedef struct(LinkList front;LinkList rear; LinkQueue;/链式队列void InitQueue_L(LinkQueue &Q)弓 I 用做参数，Q 为结构体初始化队列Q.front=Q.rear=new LNode;if(!Q.front

19、) coutvv”存储分配失败! nendl; exit(l);) Q.front-next=NULL;)int IsEmpty(LinkQueue &Q)if(Q.front=Q.rear)(return TRUE; elsereturn FALSE;)创建队列，数据元素由键盘输入void CreateQueue_L(LinkQueue &Q) (QElemType temp;LNode *p;cout喻入要插入的队列值(输入-1结束)data=temp;p-next=NULL;Q.rear-next=p;Q.rear=p;cintemp;cout”创建成功！ endl;)入队操作int E

20、nterQueue(LinkQueue &Q,QElemType x)将数据元素x插入到队列Q中LNode *NewNode=new LNode;if(!NewNode) coutdata=x;NewNode-next=NULL;Q.rear-next=NewNode;Q.rear=NewNode;coutnext;x=p-data;Q.front-next=p-next; 队头元素 p 出队if(Q.rear=p)/如果队中只有一个元素p,则p出队后成为空队 Q.rear=Q.front;free(p);释放存储空间coutn出队成功! ,endlendl;return(TRUE);)队列长

21、度int QueueLength_L(LinkQueue Q) (int length=0;if(IsEmpty(Q) coutvv”该队列为空! nendl;else (LNode *p=new LNode;p=Q.front-next;while(p) (length+;p=p-next;return length;输出队列元素void OutputQueue_L(LinkQueue Q) LNode *p=new LNode;if(!p) coutnext;coutendl;coutdata ； p=p-next;)coutendlendl;)QElemType SearchQueue(LinkQueue &Q,int &i) (LNode *p=new LNode;if(!p) coutvv”存储分配失败! nendl; exit(l);/if(Q.front=Q.rear) coutnext;while(p&jnext;)return p-data;销毁队列void DestroyQueue_L(LinkQueue &Q) (while(Q.front)(Q.rear=Q.front-next;delete Q.front;Q.front=Q.rear;void main()(int flag=l,select;LinkQueue Q;