实验总结报告-栈和队列.doc

实验总结报告栈和队列学号： 姓名： 时间：1、 目的1. 做实验的目的加深对线性结构栈和队列的理解，学会定义栈和队列的存储结构，加强对栈和队列操作机制的理解，掌握栈和队列的基本操作，了解栈和队列的一些应用。2. 撰写实验报告的目的对本次实验情况进行总结，加强对实验内容的理解，对实验过程有一个系统的认识，从中获得本次试验的经验，并对实验结果进行适当的分析，加深对栈和队列的理解和认识。2、 内容1. 说明实验次数及实验内容本次实验用一次实验课时完成实验内容：（1）、编写函数CreatStack_sq(), DestoryStack_sq(), Push_sq(), Pop_sq(),StackEmpty_sq() 和StackTraverse_sq(),分别完成创建空栈,销毁栈,入栈,出栈,判断栈是否为空,遍历栈底到栈顶依次打印栈内元素等功能(不要修改原栈),完成后进行测试。测试要求:在main 中,建立栈；判断栈是否为空；将09 入栈；将栈顶两个元素出栈,两元素求和后再入栈；从栈底到栈顶依次打印元素,再从栈顶到栈底打印元素；销毁栈。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(),分别完成创建队列,销毁队列,入队列,出队列等操作,完成后进行测试。测试要求:在主程序中,建立队列,将09 依次入队列,按入队列顺序出队列并打印,销毁队列。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),完成背包求解问题。测试数据:w6 = 2,8,6,5,1,4;2. 做实验完成情况实验内容在实验课时时间内完成（提前编写了大概1/3部分的代码），选做内容也完成。本次实验内容较多，为使代码看着简洁有条理，采用了建工程的方式。栈部分：自定义了头文件 L_stack.h：/*自定义头文件*/#include#define STACK_INIT_SIZE 100;#define STACKINCREMENT 100;/*自定义头文件（栈相关）*/#includetypedef char ElemType;/typedef int ElemType;/*栈的结构体定义*/typedef structElemType *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，不成功返回-1void 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);/背包问题在头文件中对所有要用到的自定义函数进行了声明，各函数的功能可见代码注释部分。栈的创建：#includeL_stack.hvoid CreateStack_sq(SqStack &S,int msize)S.elem = new ElemTypemsize;S.stacksize = msize;S.top = -1;/end CreateStack_sq此操作完成栈的创建，创建完成得到一个空栈。栈的销毁：#includeL_stack.hvoid DestroyStack_sq(SqStack &S)delete S.elem;S.top = -1;S.stacksize = 0;/end DestroyStack_sq此操作将栈销毁。入栈：#includeL_stack.h#includevoid Push(SqStack &S, ElemType e)if (S.top = S.stacksize - 1)Increment(S, 100);S.elem+S.top = e;/end Push_sq此操作将元素e入栈，其中若栈空间不够需要增加空间，用到了自定义函数Increment()：#includeL_stack.hvoid Increment(SqStack &S, int inc_size)int i;ElemType *a;a = new ElemTypeS.stacksize + inc_size;if (!a)printf(Error!);return;for (i = 0; i S.stacksize; i+)ai = S.elemi;delete S.elem;S.elem = a;S.stacksize += inc_size;/end Increment_sq出栈：#includeL_stack.hint Pop_sq(SqStack &S, ElemType &e)if (S.top = -1)return 0;e = S.elemS.top-;return 1;/end Pop_sq此操作栈顶元素出栈并赋给元素e，成功出栈返回1，否则返回0；判断栈空：#includeL_stack.hint StackEmpty_sq(SqStack S)if (S.top = -1)return 1;elsereturn 0;此操作判断栈是否为空栈，空栈返回1，否则返回0；栈的遍历：#includeL_stack.hvoid StackTraverse_sq1(SqStack S)int i;if (S.top = -1)printf(Stack is Empty!n);return;for (i = 0; i = 0; i-)printf(%5c, S.elemi);if (i + 1) % 6 = 0)printf(n);printf(n);/end StackTraverse_sq2此操作从栈顶到栈底遍历栈内元素并打印；在主函数中调用自定义函数test()函数用以检验栈是否正常工作：自定义函数test()：#includeL_stack.hvoid Test_sq()printf(=n);printf(Test Begain:n);SqStack S;char a10 = 0,1,2,3,4,5,6,7,8,9,e10;int i, r10;CreateStack_sq(S, 100);for (i = 0; i 10; i+)Push(S, ai);StackTraverse_sq1(S);r0 = Pop_sq(S, e0);r1 = Pop_sq(S, e1);StackTraverse_sq1(S);Push(S, e0+e1);StackTraverse_sq1(S);StackTraverse_sq2(S);DestroyStack_sq(S);StackTraverse_sq1(S);printf(Test Endn);printf(=n);括号匹配：#includeL_stack.hvoid MatchBracket_sq(char exp)int matchstat = 1;SqStack S;CreateStack_sq(S,100);char ch,e;ch = *exp+;while (ch != #&matchstat) /exp未处理完switch(ch)case (:case :case :Push(S, ch);break;case ):if (!Pop_sq(S, e) | e != ()matchstat = 0;break;case :if (!Pop_sq(S, e) | e != )matchstat - 0;break;case :if (!Pop_sq(S, e) | e != )matchstat = 0;break;/end switchch = *exp+;/end whileif (matchstat&StackEmpty_sq(S)printf(括号匹配n);elseprintf(括号不匹配n);/end MatchBracket_sq该操作完成括号的匹配；回文判断：#includeL_stack.hvoid MatchWord_sq(char exp)int i, len=0,flag=1;SqStack S;CreateStack_sq(S, 100);char ch,e;for (i = 0; expi!=0; i+)len+;/printf(%dn, len);if (len % 2 != 0)printf(非回文序列n);return;/序列长度为奇数，不可能为回文序列elsefor (i = 0; i (len / 2); i+)ch = expi;Push(S,ch);/前一半元素入栈while (i len&flag)ch = expi;if (!Pop_sq(S, e) | e != ch) /元素与栈顶元素不匹配flag = 0;i+;/end while/end elseif (flag = 1)printf(回文序列n);elseprintf(非回文序列n);该操作完成回文的判断；主函数：#include#include#includeL_stack.h/#define STACK_INIT_SIZE 100;int main()char exp120 = (, 8, +, 9, ), /, , , (, a, *, b, ), /, 7, +, 9, , # ,exp220 = , 8,+, 9,),/,(,a,*,b,),/,7,+,9,#,exp3 = abccba, exp4 = abccbd;int w6 = 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()完成栈的检验，以及实现括号匹配和回文判断。实验结果：为方便后面实现括号匹配和回文判断，我直接将09定义成的char型，头文件中ElemType定义成char。第一步将09入栈；第二步从栈底到栈顶遍历栈中元素并打印，可以看出正确创建了栈并成功将09入栈；第三、四步将栈顶元素出栈，并分别赋给e0、e1，打印操作之后的结果可以看出成功操作；第五步将e0、e1相加并入栈，从遍历栈结果来看成功操作（由于09存的是char型，所以是ASCII码相加得到q）；第六步从栈顶到栈底遍历栈中元素，操作正确；第七步销毁栈，从遍历栈的结果来看成功销毁栈。到此栈的功能检验结束。然后进行括号匹配和回文判断，结果正确。接下来利用栈进行背包问题：由于背包问题是对int型数据进行处理，为了偷点懒直接在上面的程序中进行修改首先将头文件中ElemType定义为int;背包问题中用到的函数为 CreateStack_sq()、Pop_sq()、Push()、StackTraverse_sq1()、StackEmpty_sq()、DestroyStack_sq()，对这些函数涉及到char型的改成int型；然后将主函数中test()、MatchBracket_sq()、MatchWord_sq()注释掉；最后调用背包问题的函数：#includeL_stack.hvoid knapsack(int w, int T, int n)SqStack S;int k = 0,r;CreateStack_sq(S, 100);dowhile (T 0 & k = 0)Push(S, k);T -= wk;/end ifk+;/end whileif (T = 0)printf(The Result is:n);StackTraverse_sq1(S);if (!StackEmpty_sq(S)r=Pop_sq(S, k);T += wk;k+;/end if while (!StackEmpty_sq(S) | k != n);DestroyStack_sq(S);主函数：#include#include#includeL_stack.h/#define STACK_INIT_SIZE 100;int main()char exp120 = (, 8, +, 9, ), /, , , (, a, *, b, ), /, 7, +, 9, , # ,exp220 = , 8,+, 9,),/,(,a,*,b,),/,7,+,9,#,exp3 = abccba, exp4 = abccbd;int w6 = 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 struct LNodeint data;struct LNode *next;LNode,*LinkList;typedef LinkList Queueptr;typedef structQueueptr 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，队空返回0void QueueTraverse_L(LinkQueue Q);/遍历队列元素并打印void test();/检查队列是否正确头文件中声明了需要用到的自定义函数，各个函数的功能见注释创建队列：void CreateQueue_L(LinkQueue &Q)Q.front = Q.rear = new LNode;Q.front-next = NULL;/end CreateQueue_L销毁队列：#includeQueue.hvoid DestroyQueue_L(LinkQueue &Q)while (Q.front)Q.rear = Q.front-next;delete Q.