数据结构实验报告二(栈、队列与杨辉三角).docx

数据结构实验报告 项目名称 栈、队列与杨辉三角 专业班级 软件工程工科试验班 学 号 3903120128 姓 名 谢江 实验成绩： 批阅教师：2012年 5月 22 日实验1单链表的建立与约瑟夫问题实验学时： 实验地点： 寝室与实验室 实验日期： 2012年5月22日 1需求分析实验2 主要是关于栈。队列的建立以及杨辉三角问题的解决（队列运用）2概要设计以及详细设计（1）栈class Stackpublic:Stack();bool empty();/判断栈是否为空T peek();/显示栈顶元素void push(T value);/入栈T pop();/出栈int getSize();/当前栈中元素的数量private:T *elements;/数组指针int size;/栈中的元素数量int capacity;/栈的容量void ensureCapacity();/确认栈的容量是否大于元素数量;（2）队列class Queuepublic:Queue();void enQueue(T element);/元素入队T deQueue();/元素出对，如果没有元素，抛出异常int getSize();/获取队列大小private:LinkedList list;/定义表;3调试分析内容包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；经验和体会等。个人标记: 能建立顺序栈，以及链表顺序队列，对于比较复杂的链栈、循环队列等比较不熟悉，杨辉三角问题存在问题此次报告暂时不交，还有就是抛出异常的问题，例如：T deQueue()throw (runtime_error);/元素出对，如果没有元素，抛出异常会提示警告：C+ exception specification ignored except to indicate a function is not_declspec(nothrow)于是尽可能用if()throw runtime_error,就不报错了4附录（1）栈Stack.h*/采用数组的方式进行栈的操作#ifndef STACK_H#define STACK_Htemplateclass Stackpublic:Stack();bool empty();/判断栈是否为空T peek();/显示栈顶元素void push(T value);/入栈T pop();/出栈int getSize();/当前栈中元素的数量private:T *elements;/数组指针int size;/栈中的元素数量int capacity;/栈的容量void ensureCapacity();/确认栈的容量是否大于元素数量;templateStack:Stack()capacity = 10;/初始栈的大小size = 0;/初始元素的数量elements = new Tcapacity;/建立指针templatebool Stack:empty()if(size = 0)return true;elsereturn false;template/只显示栈顶元素并不出栈T Stack:peek()return elementssize - 1;templatevoid Stack:ensureCapacity()if(size = capacity)/如果满足进行指针的更换T *old = elements;capacity = size + 1;elements = new Tcapacity;for(int i = 0; i size; i+)elementsi = oldi;delete old;templatevoid Stack:push(T value)ensureCapacity();/入栈前进行栈是否溢出的判断elementssize+ = value;templateT Stack:pop()return elements-size;templateint Stack:getSize()return size;#endif*TestStack.cpp*#include#includeStack.husing namespace std;int main()Stack intS;cout before push size of intStack is: intS.getSize() endl;/统计入栈前栈的大小for(int i = 0; i 10; i+)int num;cout num;intS.push(num);cout now size of intStack is: intS.getSize() endl;/统计入栈后栈的大小while(!intS.empty()cout intS.pop() out endl; cout after pop size of intStack is: intS.getSize() endl;/出站后栈的大小system(pause);return 0;#(2)队列LinkedList.h*#ifndef LINKEDLIST_H#define LINKEDLIST_H#includeusing namespace std;templateclass Queue;/前视定义，否则无法友元templateclass Nodepublic :T element;/节点数据域Node *next;/指向下指针Node()next = NULL;Node(T element)this - element = element;next = NULL;templateclass LinkedListpublic:LinkedList();T removeFirst();/移除并返回表头元素void addLast(T element);/尾端插入新元素int getSize();/获取表的大小private:Node *head, *tail;/定义头节点、尾节点int size;templateLinkedList:LinkedList()/初始化链表NULLhead = tail = NULL;size = 0;templatevoid LinkedList:addLast(T element)if(tail = NULL)head = tail = new Node(element);elsetail -next = new Node(element);tail = tail -next;size+;/作添加工作，size+templateT LinkedList:removeFirst()if(size = 0)throw runtime_error(No elements);/抛出异常情况else/删除并返回头节点元素，把下一节点作为新的头节点Node *temp = head;head = head -next;if(head = NULL)tail = NULL;size-;/作删除工作，size-T element = temp -element;delete temp;return element;templateint LinkedList:getSize()/返回sizereturn size;#endif*Queue.h*#ifndef QUEUE_H#define QUEUE_H#includeLinkedList.h#includeusing namespace std;templateclass Queuepublic:Queue();void enQueue(T element);/元素入队T deQueue();/元素出对，如果没有元素，抛出异常int getSize();/获取队列大小private:LinkedList list;/定义表;templateQueue:Queue()/空的构造函数templatevoid Queue:enQueue(T element)list.addLast(element);/入队（后插）templateT Queue:deQueue()return list.removeFirst();/出对（前删）templateint Queue:getSize()return list.getSize();#endif*TestQueue.cpp*#include#include#includeQueue.husing namespace std;int main()Queue q;cout before enQueue size is: q.getSize() endl;for(int i = 0; i 10; i+)q.enQueue