北邮数据结构实验报告栈和队列.docx

数据结构实验报告实验名称：实验二——2.1题目1学生姓名：班级：班内序号：学号：日期：1．实验要求根据栈和队列的抽象数据类型的定义要求：实现一个循环队列实现一个链队列编写测试main()函数测试线性表的正确性。2. 程序分析循环队列存储于表示示意图：入队和出队：算法步骤：template class Tvoid CircleQueueT::EnQueue(T x)//入队{if ((rear+1)%QueueSize == front) throw overflow;rear = (rear+1)%QueueSize; //队尾指针移向“下”一个位置data[rear] = x;}template class TT CircleQueueT::DeQueue()//出队{if (rear == front) throw underflow;front = (front+1)%QueueSize; //队头指针移向“下”一个位置return data[front];}时间复杂度为O(1)求队的长度：算法步骤：template class Tint CircleQueueT::Getlength(){return (rear-front+QueueSize)%QueueSize;}时间复杂度为O(1)链队列存储于表示示意图：入队操作：算法步骤：template class Tvoid LinkQueueT::EnQueue(T x)//入队{rear-next = new Node T;//建立新结点rear = rear-next;//移动队尾指针rear-data = x;rear-next = NULL;}时间复杂度为O(1)出队操作：算法步骤：1. 保存队头元素指针，即图中操作①；2. 如果为空队，抛出异常；3. 将原队头元素出链，即操作②；4. 保存队头数据，即操作③5. 释放原队头元素，即操作④6. 若队列变为空队列，修改队尾指针，即操作⑤；7. 返回出队数据template class TT LinkQueueT::DeQueue()//出队{new Node T * p = front-next; //保存队头元素指针if (!p) throw Underflow;front-next = p-next; //原队头元素出链T x = p-data;//保存队头数据delete p;//释放原队头元素if (!(front-next)) rear = front;//若队列变为空队，修改队尾指针return x;}时间复杂度为O(1)3、程序运行结果流程图：测试条件：入队元素数量小于队列长度减去已有队列元素数目。出队元素数量小于队列中元素数目。4. 总结第三章介绍了堆栈与队列这两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。通过这次写实验报告，就编写的程序而言，虽然能达到预期的结果，但在运行时所需的时间比较长，而且主函数不够简洁，许多问题还需要继续研究，许多代码还需要更多的改进。在这次设计的过程中，我还遇到了很多的问题。比如模板类的声明，主函数参数的使用等等。但是我都通过反复查看课本，去图书馆借一些参考资料，用Debug调试方法把他们都一一解决。而在编程过程中，在细节上总会出一些问题。比如有些变量的重复定义，有些变量又没有定义，丢掉一些定义符号等。为了使程序正常运行，只有不断修改，在这个痛苦的过程中我深刻理解到：细节决定成败，一个木桶能装多少水不在于它最高处有多高，而在于它最短的那一块，做算法编程亦是如此，因此，注重细节，完善知识点方可更加有效率的编程。这次课程设计也提醒我以前知识的匮乏,它给我敲响了警钟,让我意识到自己C++基础的不扎实,在以后的学习中，应经常对所学知识进行总结，举一反三，规范书写代码。对关键算法和语句英深入研究，不可囫囵吞枣。由于平时上机练习的少，对于教材中很多算法都掌握的不是很熟悉、不过这些都是可以弥补的，我会在剩下的时间中不断练习书上给出的算法和练习，正如教材上说的，学习数据结构，仅从书本上学习是不够的，必须经过大量的程序设计实践，在实践中体会构造性思维方法，掌握数据组织与程序设计技术。