第一篇：实验三 栈和队列的应用
一、实验目的 掌握栈的数据类型描述及栈的特点； 掌握栈的顺序存储结构的特点及算法描述； 掌握队列的数据类型描述及链式存储结构的特点和算法描述。
二、实验内容
停车场管理。设有一个可以停放n辆汽车的狭长停车场（先进后出），它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后依次从停车场最里面向大95E8口处停放（最先到达的第一辆车停放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车离开，则排在便道上的第一辆车就可以进入停车场。停车场内如有某辆车要离开，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进停车场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车没进停车场就要离开，允许其离开，不收停车费，并且仍然保持在便道上的车辆次序。试编程模拟停车场管理。
三、算法描述
提示：可以将停车场定义成一个顺序栈s1，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，故还必须有一个临时的顺序栈s2，存放让道的车辆。
当有车辆进停车场时，直接进入s1栈，若s1栈满，则进入便道（链队列q）。若有s1中车辆x离开时，先让在x后面进栈的车从s1退栈并进栈到s2中，让x离开并收取停车费，然后，再把s2中的所有车辆退栈并重新进入s1栈，最后，将链队列q的队头车辆进栈到s1中并删除队头车辆。若有链队列q（便道）中的车辆y离开时，从链队列中删除该车辆即可，不收停车费。
车辆的数据可以表示为（车辆编号，到达/离开时间）。
四.程序清单: #include
SeqStack(){top=-1;} ~SeqStack(){};void Push(int x);void Push2(int x);int *Return();int Pop(int y);int Count();void PrintStack();private: int data[StackSize];int top;};//入栈
void SeqStack::Push(int x){ if(top>=StackSize-1)throw“上溢”;for(int i=0;i<=top+1;i++){
if(data[i]==x)
{
cout<<“该车牌已经存在!请重新输入: ”;
i=-1;
cin>>x;
} } top++;data[top]=x;} //返回数组地址
int *SeqStack::Return(){ return data;} //临时栈
void SeqStack::Push2(int x){ top++;data[top]=x;
} //输出函数
void SeqStack::PrintStack(){ for(int i=0;i<=top;i++)
cout<<“位置为”< int SeqStack::Pop(int y){ if(top==-1)throw“下溢”;int x;x=data[top--];if(y==top+2)data[top+1]=123456789;if(top==-1)data[top+1]=123456789;return x;} //数数 int SeqStack::Count(){ return top;} //队列 struct Node { int data;Node *next;};class LinkQueue { public: LinkQueue();void EnQueue(int x,int *q);void xzDeQueue(int x);int Count();int DeQueue(); private: Node *front,*rear;};//构造函数 LinkQueue::LinkQueue(){ Node *s=new Node;s->next=NULL;front=rear=s;} //入队 void LinkQueue::EnQueue(int x,int *q){ Node *s=new Node;Node *p=new Node;p=front;while(p){ if(p->data ==x) { cout<<“便道已有该车牌号,请重新输入: ”; cin>>x; for(int i=0;i<5;i++) { if(x==q[i]) { cout<<“停车场已有该车牌号,请重新输入: ”; cin>>x; i=-1; } } p=front;} p=p->next;} s->data =x;s->next =NULL; rear->next =s;rear=s;} //出队 int LinkQueue::DeQueue(){ if(front==rear)throw“便道无车辆”;Node *p=new Node;int x;p=front->next;x=p->data;front->next =p->next;if(p->next ==NULL)rear=front;delete p;return x;} //计算结点数 int LinkQueue::Count(){ Node *p=new Node;p=front;int i=0;while(p&&p->next!=NULL){ p=p->next; i++;} return i;} //选择性出队 void LinkQueue::xzDeQueue(int x){ if(rear==front)throw“便道无车辆”;Node *p=new Node;p=front;int y;int i=0;for(;p->next!=NULL;p=p->next) { if(p->next->data ==x) if(p->next->next!=NULL) { Node *q=new Node; q=p->next; y=q->data; p->next =q->next; i=1; delete q; cout<<“车牌号为:”< break; } else { Node *q=new Node; q=p->next; y=q->data; p->next =NULL; i=1; delete q; if(front->next==NULL)rear=front; cout<<“车牌号为:”< break; } } if(i==0)cout<<“无车牌号为:”< SeqStack b;//b是作为临时存放车辆的栈 LinkQueue c;//c是作为便道的队列 cout<<“tttt1.车辆进入”< cout<<“tttt4.便道车辆离开”< int xh1=1;//xh1为菜单最外层的循环控制变量 int time[100];//记录各车辆进入停车场的时间 int t1=0;//作为车辆对应的时间编号 int money=1;while(xh1==1){ cout<<“请选择指令: ”; cin>>zl; switch(zl) { case 1: try{ int n1=a.Count(); int n; cout<<“请输入车牌号: ”; cin>>n; if(n1==4) { int *Num=a.Return(); for(int i=0;i<=4;i++) if(Num[i]==n) { cout<<“停车场已有该车牌号,请重新输入!”; cin>>n; i=-1; } int *CarNum=a.Return(); c.EnQueue(n,CarNum); cout<<“停车场已满,请在便道等候!”< break; } a.Push(n); cout<<“请输入进入时间: ”; cin>>time[t1]; while(time[t1]<0||time[t1]>=24) { cout<<“请输入正确的时间(0~23时):”; cin>>time[t1]; } t1++; } catch(char*s){cout< break; case 2: try{int n2;//离开车辆的编号 cout<<“请输入要离开的车的位置: ”; cin>>n2; if(a.Count()+1==0) { cout<<“该停车场没有车辆,请选择其他操作!”; break; } else while(n2<1||n2>a.Count()+1) { cout<<“请输入1~”< cin>>n2; } int j=a.Count(); for(int i=0;i<(j+1-n2);i++) b.Push2(a.Pop(n2)); a.Pop(n2); int j2=b.Count(); for(int i1=0;i1<=j2;i1++) a.Push(b.Pop(n2)); int j3=c.Count(); int time1; cout<<“请输入离开时间: ”; cin>>time1; while(time1<0||time1>23) { cout<<“请输入正确的时间(0~23时): ”; cin>>time1; } int day=0; if(time1 { cout<<“离开时间已小于进入时间!请加上停留天数(天):”; cin>>day; while(day<=0) { cout<<“输入的天数必须大于0：”; cin>>day; } } cout<<“您的费用是(元): ”<<(time1-time[n2-1]+24*day)*money< for(int i2=0;i2<(j+1-n2);i2++) time[n2-1+i2]=time[n2+i2]; t1--; if(j3!=0) { a.Push(c.DeQueue()); cout<<“ttt通知: 便道车辆请进入停车场!”< cout<<“请输入进入时间: ”; cin>>time[t1]; while(time[t1]<0||time[t1]>=24) { cout<<“请输入正确的时间(0~23时):”; cin>>time[t1]; } t1++; } }catch(char *s){cout< break; case 3: a.PrintStack();break; case 4: int n3; cout<<“请输入离开车辆的车牌号: ”; cin>>n3;try{ c.xzDeQueue(n3);}catch(char*s){cout< break; case 5: cout<<“请输入单价: ”; cin>>money; cout<<“修改成功!”< cout<<“当前停车场的费用是:”< break; case 6: xh1=0; break; } } system(“pause”);} 心得体会: 完成时间:2010-10-30 实验报告三 栈和队列 班级： 姓名： 学号： 专业： 一、实验目的： （1）掌握栈的基本操作的实现方法。 （2）利用栈先进后出的特点，解决一些实际问题。（3）掌握链式队列及循环队列的基本操作算法。（4）应用队列先进先出的特点，解决一些实际问题。 二、实验内容： 1、使用一个栈，将一个十进制转换成二进制。粘贴源程序： package Word1; public class Node } T data;Node } this.data=a;this.next=n;this(a,null); -----package Word1; public class Stack } public Node } T a=this.Top.data;this.Top=this.Top.next;return a;this.Top=new Node --package Word1; import java.util.*; public class Test { } static Scanner scan=new Scanner(System.in);static int temp=0;static int a=0;static Stack } temp=scan.nextInt();while(true){ } while(s.Top!=null){ } System.out.printf(“%d”,s.Out());a=temp%2;s.push(a);temp=temp/2;if(temp==0)break; 粘贴测试数据及运行结果： 2、回文是指正读反读均相同的字符序列，如“acdca”、“dceecd”均是回文，但“book”不是回文。利用1中的基本算法，试写一个算法判定给定的字符串是否为回文。（提示：将一半字符入栈，依次弹出与另一半逐个比较）粘贴源程序：---------package Word1; import java.util.*;public class Test1 { } static Scanner sc=new Scanner(System.in);static char[] c={'a','b','c','b','a'};static Stack } public static String One(){ } public static String Two(){ } for(int i=0;i<(c.length/2);i++){ } for(int i=c.length/2;i } return “该字符串是回文”;if(s.Out()!=c[i])return “该字符不是回文”;s.push(c[i]);for(int i=0;i<(c.length/2);i++){ } for(int i=c.length/2+1;i } return “该字符串是回文”;if(s.Out()!=c[i])return “该字符串不是回文”;s.push(c[i]);if(c.length%2!=0){ } else{ } System.out.println(Two());System.out.println(One()); ------------- 粘贴测试数据及运行结果： 3、使用3个队列分别保留手机上最近10个“未接来电”、“已接来电”、“已拨电话”。 粘贴源程序： package Word3; import java.util.*; public class Queue LinkedList } } System.out.printf(“%d n”,this.deQ()); package Word3; import java.util.*; public class Test { static Queue } static private void T2(){ int c;int[] a={22324,321321,222333};for(int i=0;i 1、查询 2、增加”);c=sc.nextInt();if(c==1){ } else{ c=sc.nextInt();while(!(list2.isEmpty()))System.out.printf(“%d n”,list2.deQ());list2.enQ(a[i]);int c=0;System.out.println(“请选择记录类型：”);System.out.println(“ 1、未接来电 2、已接来电 3、已拨电话”);switch(c=sc.nextInt()){ } case 1:T1();break;case 2:T2();break;case 3:T3();break;Frame(); } } list2.enQ(c);while(!(list2.isEmpty()))System.out.printf(“%d n”,list2.deQ());sc.close();static private void T3(){ } static private void T1(){ int c;int[] a={12324,321321,222333};for(int i=0;i 1、查询 2、增加”);c=sc.nextInt();if(c==1){ } else{ c=sc.nextInt();while(!(list1.isEmpty()))System.out.printf(“%d n”,list1.deQ());list1.enQ(a[i]);int c;int[] a={32324,321321,222333};for(int i=0;i 1、查询 2、增加”);c=sc.nextInt();if(c==1){ } else{ } sc.close();c=sc.nextInt();list3.enQ(c);while(!(list3.isEmpty()))System.out.printf(“%d n”,list3.deQ());while(!(list3.isEmpty()))System.out.printf(“%d n”,list3.deQ());list3.enQ(a[i]); } } } list1.enQ(c);while(!(list1.isEmpty()))System.out.printf(“%d n”,list1.deQ());sc.close(); 粘贴测试数据及运行结果： 三、心得体会：（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得） 实验总结报告—栈和队列 学号： 姓名： 时间： 一、目的 1.做实验的目的 加深对线性结构栈和队列的理解，学会定义栈和队列的存储结构，加强对栈和队列操作机制的理解，掌握栈和队列的基本操作，了解栈和队列的一些应用。2.撰写实验报告的目的 对本次实验情况进行总结，加强对实验内容的理解，对实验过程有一个系统的认识，从中获得本次试验的经验，并对实验结果进行适当的分析，加深对栈和队列的理解和认识。 二、内容 1.说明实验次数及实验内容 本次实验用一次实验课时完成 实验内容： （1）、编写函数CreatStack_sq(), DestoryStack_sq(), Push_sq(), Pop_sq(),StackEmpty_sq()和 StackTraverse_sq(),分别完成创建空栈,销毁栈,入栈,出栈,判断栈是否为空,遍历栈底到栈顶依 次打印栈内元素等功能(不要修改原栈),完成后进行测试。测试要求:在main 中,建立栈；判断栈是否为空；将0~9 入栈；将栈顶两个元素出栈, 两元素求和后再入栈；从栈底到栈顶依次打印元素,再从栈顶到栈底打印元素；销毁栈。 void CreatStack_sq(SqStack &S, int msize = STACK_INIT_SIZE){...} void DestoryStack_sq(SqStack &S){...}void Push_sq(SqStack &S, ElementType e){...} bool Pop_sq(SqStack &S, ElementType &e){...} bool StackEmpty_sq(SqStack S){...} bool StackTraverse_sq(SqStack S){...}（2）、编写函数, CreateQueue_L(), DestoryQueue_L(), EnQueue_L(),DeQueue_L(),分别完 成创建队列,销毁队列,入队列,出队列等操作,完成后进行测试。测试要求:在主程序中,建立队列,将0~9 依次入队列,按入队列顺序出队列并打印, 销毁队列。 void CreateQueue_L(LinkQueue &Q){ } void DestoryQueue_L(LinkQueue &Q){ } void EnQueue_L(LinkQueue &Q,int e){ } bool DeQueue_L(LinkQueue &Q, int &e){ }（3）、回文是指正读反读均相同的字符序列,如”abba”和”abdba”均是回文, 但”good”不是回文。根据第四章栈和队列所学内容,试写一个算法判 定给定的字符向量是否为回文。测试数据: 2.1 char* ch = “abccba”;2.2 char* ch = “abccbd”;（4）、(附加题)编写函数void Knapsack(int w[],int T,int n),完成背包求解问题。测试数据: w[6] = {2,8,6,5,1,4};2.做实验完成情况 实验内容在实验课时时间内完成（提前编写了大概1/3部分的代码），选做内容也完成。 本次实验内容较多，为使代码看着简洁有条理，采用了建工程的方式。栈部分： 自定义了头文件 L_stack.h： /*自定义头文件*/ #include #define STACK_INIT_SIZE 100;#define STACKINCREMENT 100; /*自定义头文件（栈相关）*/ #include /*栈的结构体定义*/ typedef struct{ ElemType *elem;int top;int stacksize;}SqStack; void CreateStack_sq(SqStack &S,int msize);//创建栈，msize为栈的大小 void DestroyStack_sq(SqStack &S);//销毁栈 void Push(SqStack &S, ElemType e);// 进栈操作，e为入栈元素 int Pop_sq(SqStack &S, ElemType &e);//出站操作，成功返回0，不成功返回-1 void Increment(SqStack &S, int inc_size);//增加栈空间 int StackEmpty_sq(SqStack S);//判断栈空，栈空返回0，栈非空返回-1； void StackTraverse_sq1(SqStack S);//遍历栈底到栈顶，若栈非空则依次打印栈中元素 void StackTraverse_sq2(SqStack S);//遍历栈顶到栈底，若栈非空则依次打印栈中元素 void Test_sq();//栈的检测程序 void MatchBracket_sq(char exp[]);// 括号匹配 void MatchWord_sq(char exp[]);//判断回文 void knapsack(int w[], int T, int n);//背包问题 在头文件中对所有要用到的自定义函数进行了声明，各函数的功能可见代码注释部分。 栈的创建： #include“L_stack.h” void CreateStack_sq(SqStack &S,int msize){ S.elem = new ElemType[msize];S.stacksize = msize;S.top =-1;}//end CreateStack_sq 此操作完成栈的创建，创建完成得到一个空栈。 栈的销毁： #include“L_stack.h” void DestroyStack_sq(SqStack &S){ delete S.elem;S.top =-1;S.stacksize = 0;}//end DestroyStack_sq 此操作将栈销毁。 入栈： #include“L_stack.h” #include void Push(SqStack &S, ElemType e){ if(S.top == S.stacksize0;break;case '}': if(!Pop_sq(S, e)|| e!= '{')matchstat = 0;break;}//end switch ch = *exp++;}//end while if(matchstat&&StackEmpty_sq(S))printf(“括号匹配n”);else printf(“括号不匹配n”);}//end MatchBracket_sq 该操作完成括号的匹配； 回文判断： #include“L_stack.h” void MatchWord_sq(char exp[]){ int i, len=0,flag=1;SqStack S;CreateStack_sq(S, 100);char ch,e;for(i = 0;exp[i]!=' ';i++)len++;//printf(“%dn”, len);if(len % 2!= 0){ printf(“非回文序列n”);return;}//序列长度为奇数，不可能为回文序列 else{ for(i = 0;i <(len / 2);i++){ ch = exp[i]; Push(S,ch); }//前一半元素入栈 while(i < len&&flag){ ch = exp[i]; if(!Pop_sq(S, e)|| e!= ch) flag = 0; i++;}//end while }//end else if(flag == 1)printf(“回文序列n”);else printf(“非回文序列n”);} 该操作完成回文的判断； 主函数： #include //元素与栈顶元素不匹配 #include“L_stack.h” //#define STACK_INIT_SIZE 100; int main(){ char exp1[20] = { '(', '8', '+', '9', ')', '/', '{', '[', '(', 'a', '*', 'b', ')', '/', '7', ']', '+', '9', '}', '#' }, exp2[20] = { '}'，'8','+', '9',')','/','{','[','(','a','*','b',')','/','7',']','+','9','}','#'}，} exp3[] = “abccba”, exp4[] = “abccbd”;int w[6] = { 2, 8, 6, 5, 1, 4 };Test_sq();MatchBracket_sq(exp1);MatchBracket_sq(exp2);MatchWord_sq(exp3);MatchWord_sq(exp4);//knapsack(w, 10, 6); system(“pause”);return 0;主函数中调用test()完成栈的检验，以及实现括号匹配和回文判断。实验结果： 为方便后面实现括号匹配和回文判断，我直接将0~9定义成的char型，头文件中ElemType定义成char。 第一步将0~9入栈；第二步从栈底到栈顶遍历栈中元素并打印，可以看出正确创建了栈并成功将0~9入栈；第三、四步将栈顶元素出栈，并分别赋给e[0]、e[1]，打印操作之后的结果可以看出成功操作；第五步将e[0]、e[1]相加并入栈，从遍历栈结果来看成功操作（由于0~9存的是char型，所以是ASCII码相加得到q）；第六步从栈顶到栈底遍历栈中元素，操作正确；第七步销毁栈，从遍历栈的结果来看成功销毁栈。到此栈的功能检验结束。然后进行括号匹配和回文判断，结果正确。 接下来利用栈进行背包问题： 由于背包问题是对int型数据进行处理，为了偷点懒直接在上面的程序中进行修改 首先将头文件中ElemType定义为int;背包问题中用到的函数为 CreateStack_sq()、Pop_sq()、Push()、StackTraverse_sq1()、StackEmpty_sq()、DestroyStack_sq()，对这些函数涉及到char型的改成int型；然后将主函数中test()、MatchBracket_sq()、MatchWord_sq()注释掉；最后调用背包问题的函数： #include“L_stack.h” void knapsack(int w[], int T, int n){ SqStack S;int k = 0,r;CreateStack_sq(S, 100);do{ while(T > 0 && k < n){ if(T-w[k] >= 0){ Push(S, k);T-= w[k];}//end if k++;}//end while if(T == 0){ } } printf(“The Result is:n”);StackTraverse_sq1(S);if(!StackEmpty_sq(S)){ r=Pop_sq(S, k);T += w[k];k++;}//end if } while(!StackEmpty_sq(S)|| k!= n);DestroyStack_sq(S);主函数： #include //#define STACK_INIT_SIZE 100; int main(){ char exp1[20] = { '(', '8', '+', '9', ')', '/', '{', '[', '(', 'a', '*', 'b', ')', '/', '7', ']', '+', '9', '}', '#' }，exp2[20] = { '}', '8','+', '9',')','/','{','[','(','a','*','b',')','/','7',']','+','9','}','#'}，} 输出结果： exp3[] = “abccba”, exp4[] = “abccbd”;int w[6] = { 2, 8, 6, 5, 1, 4 };//Test_sq();//MatchBracket_sq(exp1);//MatchBracket_sq(exp2);//MatchWord_sq(exp3);//MatchWord_sq(exp4);knapsack(w, 10, 6); system(“pause”);return 0; 可见操作正确。队列部分： 自定义了头文件 Queue.h： /*自定义头文件*/ #include typedef LinkList Queueptr; typedef struct{ Queueptr front;Queueptr rear;}LinkQueue; /*自定义函数*/ void CreateQueue_L(LinkQueue &Q);//创建队列 void DestroyQueue_L(LinkQueue &Q);//销毁队列 void EnQueue_L(LinkQueue &Q, int e);//入队列操作 int DeQueue_L(LinkQueue &Q, int &e);//出队列操作，并将队首元素赋给e，返回1，队空返回0 void QueueTraverse_L(LinkQueue Q);//遍历队列元素并打印 void test();//检查队列是否正确 头文件中声明了需要用到的自定义函数，各个函数的功能见注释 创建队列： void CreateQueue_L(LinkQueue &Q){ Q.front = Q.rear = new LNode;Q.front->next = NULL;}//end CreateQueue_L 销毁队列： #include“Queue.h” void DestroyQueue_L(LinkQueue &Q){ while(Q.front){ Q.rear = Q.front->next;delete Q.front;Q.front = Q.rear;}//end while }//end DestroyQueue_L 进队列： #include“Queue.h” void EnQueue_L(LinkQueue &Q, int e){ LinkList p;p = new LNode;p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;}//end EnQueue_L 出队列： #include“Queue.h” int DeQueue_L(LinkQueue &Q, int &e){ LinkList p;p = new LNode;if(Q.front == Q.rear)return 0;p = Q.front->next;Q.front->next = p->next; e = p->data;if(Q.rear == p)Q.rear = Q.front;delete p;return 1;}//end DeQueue_L 主函数： #include int main(){ } 主函数调用test()函数检验队列的正确性 test()函数： #include“Queue.h” system(“pause”);return 0;test();void test(){ } 输出结果： LinkQueue Q;int i,a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 },b[10],r[10];CreateQueue_L(Q);for(i = 0;i < 10;i++)EnQueue_L(Q, a[i]);QueueTraverse_L(Q);for(i = 0;i < 10;i++){ } r[i] = DeQueue_L(Q, b[i]);QueueTraverse_L(Q); 从输出结果来看符合要求，队列正确。 三、总结 实验5 栈和队列的应用 目的和要求： （1）熟练栈和队列的基本操作；（2）能够利用栈与队列进行简单的应用。 一、题目 题目1.利用顺序栈和队列，实现一个栈和一个队列，并利用其判断一个字符串是否是回文。所谓回文，是指从前向后顺读和从后向前倒读都一样的字符串。例如，a+b&b+a等等。 题目2.假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题，并实现。 题目3.打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。每台打印机具有一个队列（缓冲池），用户提交打印请求被写入到队列尾，当打印机空闲时，系统读取队列中第一个请求，打印并删除之。请利用队列的先进先出特性，完成打印机网络共享的先来先服务功能。 题目4.假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。 题目5.利用循环链队列求解约瑟夫环问题。 请大家从本组未讨论过的五道题中选择一道，参照清华邓俊辉老师MOOC视频及课本相关知识，编写相应程序。 选择题目3： 打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。 二、程序清单 //Ch3.cpp #include { p=front; front=front->link; delete p;} };template if(front==NULL){//判断是否为空 front=rear=new LinkNode front->data=rear->data=x; if(front==NULL)//分配结点失败 return false;} else{ rear->link=new LinkNode rear->link->data=x; if(rear->link==NULL) return false; rear=rear->link;} return true;};template { return false;} cout< LinkNode delete p;//释放原结点 return true;};void main() //主函数 { LinkedQueue char flag='Y'; //标志是否输入了命令 const int max=30;//一次获取输入命令的最大个数 while(flag=='Y')//循环 { int i=0;char str[max];//定义存储屏幕输入的命令的数组 gets(str);//获取屏幕输入的命令 while(str[i]!=' '){ q.put_in(str[i]);//调用提交命令函数，将每个命令存入队列中 i++; } for(int j=0;j<=i;j++){ if(q.IsEmpty()==true)//判断是否为空，为空则说明没有可执行的命令 { cout<<“已经没有可执行的命令！是否继续输入命令(Y|N)?”< cin>>flag;continue;//为空跳出for循环为下次输入命令做好准备 } q.carry_out();//调用执行命令的函数，将命令打印并删除 } 三、程序调试过程中所出现的错误 无。 四、运行结果： 五、心得体会 打印机采用的缓冲池技术，本质上就是利用了队列的先进先出的特点，体现了先来后到原则。虽然意思很简单，但是实际编程过程中，出现bug的概率还是蛮高的，因为在编写程序中一点疏忽就容易产生错误。 本来我对模板类的使用还是很模糊的，通过这个例子，至少让我清楚了模板类的使用和特点。觉得模板类的恰当使用，对于自己今后的编程好处还是很大的。 数理学院实验指导书 实验三 栈与队列的实现，栈的应用 【实验目的】 1、掌握栈和队列的特点，即先进后出与先进先出的原则。 2、掌握栈和队列的顺序存储结构和链式存储结构及其基本操作，以便在实际问题中灵活运用。 3、掌握栈和队列的基本操作实现方法。【实验内容】 1、栈的实现： 用C语言实现栈，包括类型定义和各种基本运算的实现，并在此基础上设计一个主程序，测试栈的一些基本运算： (1).初始化(2).入栈(3).出栈 (4).取栈顶元素(5).遍历栈(6).置空栈 请根据下面给出的程序（改进的顺序栈），完成这次实验，并与链栈的实现方法相比较： /*Common.h*/ #define TRUE 1 //逻辑，是 #define FALSE 0 //逻辑，否 #define OK 1 //状态，成功 #define FAILURE 0 //状态，未成功 #define ERROR-1 //状态，失败 #define OVERFLOW 1 //溢出 typedef int BOOL;typedef int Status; /*seqstack.h*/ #include typedef int ElemType; //栈 typedef struct { ElemType *elem;// 存储空间基址 int top;// 栈顶指示 int currentsize;// 当前分配的长度 }SeqStack; /*构造一个空的栈*/ SeqStack *CreateStack();/*释放栈分配的空间*/ void DestroyStack(SeqStack *S);/*判空*/ int IsEmpty(SeqStack *S);/*入栈*/ Status Push(SeqStack *S, ElemType e);/*出栈*/ Status Pop(SeqStack *S, ElemType *e);/*取栈顶元素*/ Status GetTop(SeqStack *S, ElemType *e);/*遍历*/ void Traverse(SeqStack *S, void(*visit)(ElemType, int)); /*seqstack.c*/ #include /*构造一个空的栈*/ SeqStack *CreateStack(){ SeqStack *S=(SeqStack *)malloc(sizeof(SeqStack)); if(S==NULL){ exit(OVERFLOW);} S->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(S->elem==NULL){ exit(OVERFLOW);} S->top =-1;S->currentsize = LIST_INIT_SIZE;return S;} /*释放栈分配的空间*/ void DestroyStack(SeqStack *S){ if(S!=NULL){ if(S->elem!=NULL) { free(S->elem); } S->elem=NULL;} } /*判空*/ int IsEmpty(SeqStack *S){ return S->top==-1;} /*入栈*/ Status Push(SeqStack *S, ElemType e){ if(S->top >= S->currentsize)// 当前存储空间已满，增加分配 { ElemType *newbase=(ElemType *)realloc(S->elem,(S->currentsize + LISTINCREMENT)*sizeof(ElemType)); if(newbase==NULL)// 存储分配失败 { exit(OVERFLOW); } S->elem = newbase;// 新基址 S->currentsize += LISTINCREMENT;//增加存储容量 } ++(S->top);S->elem[S->top]=e;return OK;} /*出栈*/ Status Pop(SeqStack *S, ElemType *e){ if(S->top==-1)//空栈 { return FAILURE;}(*e)=S->elem[S->top];--(S->top);// 表长减1 return OK;} /*取栈顶元素*/ Status GetTop(SeqStack *S, ElemType *e){ if(S->top==-1)//空栈 { return FAILURE;}(*e)=S->elem[S->top];return OK;} /*遍历*/ void Traverse(SeqStack *S, void(*visit)(ElemType, int)){ int i; for(i=0;i<=S->top;i++){ (*visit)(S->elem[i], i+1);} } 2.利用栈实现数制转换： 在上述栈实现的基础上，设计一个算法实现输入一个10进制整数，输出相应的2进制表示，并利用计算器工具设计若干测试数据后编写测试代码进行测试.#include cout<<“除数不能为零”< sum*=m;return sum;} int Check(char ch){ switch(ch){ case '0': return 0; break;case '1': return 1; break;} return-1;} 3.队列的实现： 用C语言实现队列，包括类型定义和各种基本运算的实现，并在此基础上设计一个主程序，测试队列的一些基本运算： (1).初始化(2).入队列(3).出队列 (4).取对头元素(5).遍历队列 请根据下面给出的程序（改进的链队列），完成这次实验，并与顺序队列的实现方法相比较，结合上述改进顺序栈的方法改进书上的顺序队列使之能根据队列使用情况自动扩展或缩短，从而解决顺序队列“上溢”的问题： /*Common.h*/ 见栈的实现 /*queue.h*/ #include //链队列 /*定义链队列中的结点类型*/ typedef struct node { ElemType data;struct node *next;}LinkNode; typedef struct { LinkNode *front;LinkNode *rear;}LinkQueue; /*构造一个空的链队列*/ LinkQueue *CreateQueue();/*销毁链队列*/ void DestroyQueue(LinkQueue *Q);/*判空*/ int IsEmpty(LinkQueue *Q);/*入队列*/ Status AddQueue(LinkQueue *Q, ElemType e);/*出队列*/ Status OutQueue(LinkQueue *Q, ElemType *e);/*取队列头元素*/ Status GetHead(LinkQueue *Q, ElemType *e);/*遍历*/ void Traverse(LinkQueue *Q, void(*visit)(ElemType, int)); /*queue.c*/ #include /*构造一个空的队列*/ LinkQueue *CreateQueue(){ LinkQueue *Q=(LinkQueue *)malloc(sizeof(LinkQueue));if(Q==NULL){ exit(OVERFLOW);} Q->front=(LinkNode *)malloc(sizeof(LinkNode)); if(Q->front==NULL){ exit(OVERFLOW);} Q->front->next=NULL;/*填头结点的next域为NULL*/ Q->rear=Q->front; /*让尾指针也指向头结点*/ return Q;} /*销毁队列*/ void DestroyQueue(LinkQueue *Q){ LinkNode *p; if(Q!=NULL){ while(Q->front!=Q->rear) { p=Q->front->next; free(Q->front); Q->front=p; } free(Q->front); Q->front=NULL; Q->rear=NULL;} } /*判空*/ int IsEmpty(LinkQueue *Q){ return Q->front==Q->rear;} /*入队列*/ Status AddQueue(LinkQueue *Q, ElemType e){ LinkNode *p;p=(LinkNode *)malloc(sizeof(LinkNode)); if(p==NULL){ exit(OVERFLOW);} p->data=e; /*填入元素值*/ p->next=NULL; /*指针域填NULL值*/ Q->rear->next=p; /*新结点插入队尾*/ Q->rear=p; /*修改队尾指针*/ return OK;} /*出队列*/ Status OutQueue(LinkQueue *Q, ElemType *e){ LinkNode *p;if(Q->front==Q->rear)//空队列 { return FAILURE; } p=Q->front; /*p指向头结点*/ Q->front=Q->front->next;free(p);(*e)= Q->front->data;return OK;} /*取队列顶元素*/ Status GetHead(LinkQueue *Q, ElemType *e){ if(Q->front==Q->rear)//空队列 { return FAILURE; }(*e)= Q->front->next->data;return OK;} /*遍历*/ void Traverse(LinkQueue *Q, void(*visit)(ElemType, int)){ LinkNode *p;int i;p=Q->front;i=1;while(p!=Q->rear){ (*visit)(p->next->data, i); p=p->next; i++;} } 【实验安排】 课时安排：2学时 【实验提示】 1.实验流程 根据所给的代码编辑源程序，注意编写的规范和体会实现的方法；设计一个主程序实现要求的测试；设计一个算法利用栈实现数制转换..2.注意事项 记录输入和编译的错误提示，书写心得体会；记录测试数据和程序的输出；注意总结.作者:王鹤 QQ:583241212 VC++6.0中调式通过的代码: #include “stdafx.h” #include 第二篇：实验三 栈和队列
第三篇：实验总结报告-栈和队列
第四篇：实验报告——栈和队列的应用
第五篇：栈队列实验指导书
点击咨询 