计算机软件技术基础实验报告.docx
实验二 栈和队列的基本操作一、实验目的1 .掌握栈与队列的数据类型描述及特点；2 .掌握栈和队列的存储；3 .掌握栈的顺序和链式存储存表示与入栈、出栈操作的程序实现；4 .掌握队列的链式存储表示与入队、出队基本操作算法实现。二、实验用软件和工具实验软件VC+ 6. 0三、实验步骤1 .根据栈数据结构，分别建立一个顺序栈和链式栈并实现其上基本操作(出栈和入栈等)， 定义一个顺序栈和链栈结构体(队列结构体)。2 .利用入栈功能保存数据。3 .利用出栈删除弹出栈内信息。4 .根据队列数据结构，分别建立链队列和循环队列，并完成其上的基本操作(出入队列等), 利用入队功能保存数据。5 .利用出队删除队列信息。四、实验程序与程序运行结果顺序栈程序：sxz.h#include <iostream>using namespace std;template <class T>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 <class T>sq_Stack<T>: sq_Stack(int m)(mm=m;6 = new Tmm;top=0;int x;while(flag)(cout«n链式队列基本操作翁翁n«endl;cout«,'.创建队列 n«endl;cout«n.判断链队列是否为空"<<endl;cout«n.队头元素出队翁”< vendl;cout«,.新元素入队 n«endl;cout«!,.求队列长度 n«endl;cout«M.输出队列元素食H«endl;cout«,'.查找第i个位置元素 n«endl;cout«,.销毁队列 n«endl;cout«,食9 .其他键退出 M«endl;cout«endl;cout<< ”请选择操作：”；cin»select;switch(select)(InitQueue_L(Q);CreateQueue_L(Q);OutputQueue_L(Q);break;if(IsEmpty(Q) cout<v”该队列为空! n«endl;else cout<<”该队列不为空! n«endl;break;if(IsEmpty(Q) coutvv”队列为空！ "<<endl; break;DeleteQueue(Q,x);OutputQueue_L(Q);break;if(IsEmpty(Q) cout<<”队列还未创建！"<<endl; break; cout<<"输入要入队的元素X: "； cin»x;EnterQueue(Q,x);OutputQueue_L(Q);break;if(IsEmpty(Q) cout<<”队列还未创建！""endl; break;coutv<”该链队歹U的长度为：H«QueueLength_L(Q)«endl«endl; break;case 8:if(IsEmpty(Q) cout<v” 队列还未创建！"vvendl; break; DestroyQueue_L(Q);cout<<”销毁成功! n«endl«endl;break;case 7:cout«”请输入要查找的位置i：cin»x;if(x<l |x>QueueLength_L(Q) cout«Hi 值不合法！n«endl; break; cout<<"该元素为：n<<SearchQueue(Q,x)«endl«endl;break;case 6:OutputQueue_L(Q); break;default:flag=O; break;试验运行结果如图:栈:cT ,VI： zhanDebugzhan. exe第1次输出栈顶指针与栈中的元素:top=61009080706050：100木出退栈的元素:1009080再输出栈顶指针与栈中的元素:top=3706050Press any key to continue *1：duili eDebugduili e. exe"front=10rear=10队列空？输出队头与队尾指针及队列中的元素:front=10 rear=65060?08090100输出退队元素：506070再输出队头与队尾指针及队列中的元素:front=3rear=68090100Press any key to continue.链栈:链队列:cT"工：li andui1i eDebugldl. exe"本是队素谴 一>. 7 I J 44 I基列出队度元M出列列队京长列J列退队队链元素列队晟键 式建断头元队出鬣他 链创判队新求辑_襄 £123456789请选择操作：6队列的元素依次为：2 3 4 5 6 空 为 否仝 素 元 置:是队素汇， 基列出队度元刈出 列列队支长列J列退队队链元素列队晟键式建断头元队出般他 链创判队新求兽_襄 1234567.89请选择操侪7请输要看我的位置i：3该元素为：4本是队素1-V- y11 V 44基列出队度元M出列列队支长列J列退队队链元素列队晟键 式建断头元队出登他 链创判队新求善_襄 - - T123456789 空 为 否仝是队素-r-基列出队度元忸出列列队支长列)列退队队链元素列队卷键 式建断头元队出弱他 链创判队新求毒 襄 1234567.89请选择操作：9Press any key to continue五、实验心得与体会通过本次上机实验，我掌握了栈的顺序和链式存储存表示与入栈、出栈操作的程序实现，以 及队列的链式存储表示与入队、出队基本操作算法实现。遇到问题难以避免，认真研究代码还 是可行的，最后成功做出实验。return;template <class T>void sq_Stack<T>:prt_sq_Stack()(int i;cout«Htop=,'«top«endl;for (i=top;i>0;i-) cout«si-l «endl;return;template <class T>void sq_Stack<T>:ins_sq_Stack(T x) (if (top=mm)cout«noverflow!H«endl; return;/存储空间已满,上溢错误tOp=tOp+l；/stop-l=x;插入新元素return;template<class T>T sq_Stack<T>:del_sq_Stack()Ty;if(top=0)/空，下溢错误cout«nunderflow! n«endl; retum(O); y=stop-l; /top=top-1; 长度减 1 return(y);)template<class T>T sq_Stack<T>:read_sq_Stack()(if(top=0)/空，下溢错误cout«Hunderflow! n«endl; retum(O); return(stop-l);sxz.cpp#include Msq_Stack.hnint main()(sq_Stack<int> s(10);s.ins_sq_Stack(5O);s.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<< ”输出退栈的元素:H«endl;cout«s.del_sq_Stack()«endl;cout«s.del_sq_Stack()«endl;cout«s.del_sq_Stack()«endl;coin v v ”再输出瓶顶指针与栈中的元素:H«endl;s.prt_sq_Stack(); return 0;)顺序队列程序：sq_Queue.h#include <iostream> using namespace std;template <class T>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 <class T>sq_Queue<T>:sq_Queue(int m) (mm=m;q = new Tmm;front=mm;rear=mm;s=0; return;) template <class T>void sq_Queue<T>:prt_sq_Queue()(int i;cout«Hfront=n«front«endl;cout«n rear=n «rear«endl;if (s=0)&&(rear=front)cout<<"队歹 U 空!n«endl; return; i=front;if (front>=mm)front=i%mm ;for (i=front; i<rear;i+)cout«qi«endl;return;template <class T>void sq_Queue<T>: ins_sq_Queue(T x)if (s= 1 )&&(rear=front)cout«nQueue_overflow!u«endl; return;/存储空间已满，上溢错误 rear=rear+l; /if (rear=mm+l) rear= 1;qrear-l=x;插入新元素s=l;return;)template <class T>T sq_Queue<T>:del_sq_Queue()(Ty;if (s=0)cout«nQueue_underflow!n«endl; return(O);存储空间已满,上溢错误 front=front+l; /if (front=mm+l) front=l;y=qfront-l ;插入新元素if (rear=front)s=0;return(y);)#include "sq_Queue.h"int main()(sq_Queue<int> q(10);q.prt_sq_Queue();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;cout«q.del_sq_Queue()«endl;cout«q.del_sq_Queue()«endl;cout«q.del_sq_Queue()«endI;cout<”再输出以头与队尾指针及队列中的元素:“ <<endl;q.prt_sq_Queue();return 0;链栈：#include <iostream.h>#include <stdio.h>#include <stdlib.h> 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;cout<<”初始化链栈成功!”；)void push(DateType x)(LinkStack* s;s=(LinkStack*)malloc(sizeof(LinkStack);s->data=x;s->next=top;top=s;coutv”入栈成功!”;)void pop()(LinkStack* s;s=top;if(s->next=NULL)cout« "栈为空!”;) else(top=s->next;free(s);cout<v”出栈成功”；)void readTopO(if(top=NULL)(coutvv"栈为空!”;)else(cout<<"栈顶元素为:"<<top->data;)void showStack()(LinkStack* s;s = top;if(s->next=NULL)(cout« "栈为空!”；)elsecoutvv”链栈元素为:n”;cout«ntttH;while。!=NULL)cout«n n«s->data;s=s->next;)void main()int ij;DateType x; while(j)cout«nnnnnn;cout« cout« cout« cout« cout«f 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 ”*”*”*菜单：创建链栈出栈入栈显示链栈元素退出*”<<endl;11*1*a*k|>*x*1* .1 .!* .!*k|> kI> k1> kJ>kI* *a*1*3 *x*!* .!*k|> k1> k1>*1!* .J* *a* IQ./i i<T*rj* <T*<T* <Tw *7* rj* ri* <1* rj* *T>1* ri* <T> <T>ri* <1* <T* <T<1* <T* <T*ri* ri*7 <T> <7 ri* <T> <TwrT* ri* <1* *1*rj* <T*<T> <TwI cout<v”请选择您所希望的操作：” cin»i;if(i=l)InitStackQ;else if(i=2)if(top=NULL)cout«”请先初始化链表!”;)elsecout<< ”请输入要入栈的元素:"cin»x;push(x);)else if(i=3)(pop()；else if(i=4)(readTopO;else if(i=5)(showStackQ;)else if(i=6)(j=0;coutvv”程序结束n”;)链队列：#include <stdlib.h>#include<iostream.h>#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) coutvv”存储分配失败! n«endl; 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结束)"<<endl;cin»temp;while(temp != -1) (p=new LNode;p->data=temp;p->next=NULL;Q.rear->next=p;Q.rear=p;cin»temp;cout<<”创建成功！ "<<endl;)入队操作int EnterQueue(LinkQueue &Q,QElemType x)将数据元素x插入到队列Q中LNode *NewNode=new LNode;if(!NewNode) cout<<"存储分配失败! H«endl; exit(l); if(NewNode!=NULL) (NewNode->data=x;NewNode->next=NULL;Q.rear->next=NewNode;Q.rear=NewNode;cout<v”入队成功！ H«endl«endl;return(TRUE);) else return(FALSE); 溢出)出队操作int DeleteQueue(LinkQueue &Q,QElemType &x)将队列Q的队头元素出队，并存放到x所指的存储空间中LNode *p;/*if(Q.front=Q.rear) (cout«”该队列为空! n«endl;return (FALSE);*/p=Q.front->next;x=p->data;Q.front->next=p->next; 队头元素 p 出队if(Q.rear=p)/如果队中只有一个元素p,则p出队后成为空队 Q.rear=Q.front;free(p);释放存储空间cout«n出队成功! ,«endl«endl;return(TRUE);)队列长度int QueueLength_L(LinkQueue Q) (int length=0;if(IsEmpty(Q) coutvv”该队列为空! n«endl;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) cout<<"存储分配失败! n«endl; exit(l);) if(Q.front=Q.rear) cout«”该队列为空！”endl; else(p=Q.front->next;cout«endl;cout<< ”队列的元素依次为：”； while(p)(cout«p->data«" "； p=p->next;)cout«endl«endl;)QElemType SearchQueue(LinkQueue &Q,int &i) (LNode *p=new LNode;if(!p) coutvv”存储分配失败! n«endl; exit(l);/if(Q.front=Q.rear) cout<<”该队列为空! H«endl;int j=l;p=Q.front->next;while(p&&j<i)(j+；p=p->next;)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;
