计算机22班课内实验

1、数据结构课内实验计算机 22一、线性表及栈与队列操作实现2120505046针对线性表或栈或队列（任选一种），编程实现选择顺序或链式(任选一种)结构下数据结构建立、元素果。（1）程序代码#include 、删除等基本操作，并演示实际例子运行结using namespatd;template class Stackprivate:top; maxsize;E * stack;public:Stack(size = 100)top=0;maxsize = size;stack = new E maxsize;Stack()delete stack;void push ( E i )stacktop

2、 = i; top+;E pop()top-;return (stacktop);void clear()top=0;length()return top;E topelement()return stacktop-1;void maenu(Stack& stack)void push(Stack& stack);void pop(Stack& stack);void topelement(Stack& stack);void length(Stack& stack);void clear(Stack& stack);coutplease choose the operationendl1.p

3、ush elementsendl2.pop an elementendl3.show the top elementendl4.show the lengthendl5.clear the stacki; if(i=1)push(stack); if(i=2)pop(stack); if(i=3)topelement(stack); if(i=4)length(stack); if(i=5)clear(stack);void push(Stack& stack)couti;put the push numberendl;for(j=0;jk;stack.push(k);maenu(stack)

4、;void pop(Stack& stack)coutstack.pop()endl;maenu(stack);void topelement(Stack& stack)coutstack.topelement()endl;maenu(stack);void length(Stack& stack)coutstack.length()endl;maenu(stack);void clear(Stack& stack)main()maxsize;coutplease input the maxsize maxsize;Stack stack( maxsize );maenu(stack);（2）

5、.程序分析类名为 Stack 的栈中 private 成员有 top 表示栈内元素个数，maxsize 表示栈的最大容量，stack 表示表示数组空间，public 成员有构造函数Stack(size =100)，析构函数Stack（），入栈函数void push ( E i )，出栈函数E pop()，清空函数void clear()，显示长度函数length()，显示栈头成员E topelement()，用界面的形式来实现对栈的实例操作，在主界面void maenu(Stack& stack)中有 5 中操作可以选择，分别对应实现入栈，出栈，显示栈顶，显示长度，清空栈。没实现玩一个操作后回

6、到主函数，实现清空栈以后结束程序运行。Main 函数中可以输入栈的最大容量来实例化一个Stack 对象。（3）.程序运行二、二叉树与树的操作实现（二者选一）编程实现二叉搜索树的建立、中序遍历、元素查找等功能，并演示实际例子的运行结果。（1）程序代码#include using namespatd;template clapublic:odeE it;Node * lc; Node * rc; Node( E i)it = i;lc = NULL; rc = NULL;template class BSTprivate:Node * root; nodecount;public:BST()roo

7、t = NULL; nodecount = 0;void insert( E x )Node * newnode = new Node(x); inserthelper( root ,newnode);void inserthelper( Node * x, Node * y)Node * current; current = x; if(current = NULL)root = y; return;if( (current-it y-it) & (current-lc!=NULL) )current = current-lc; inserthelper(current,y);else if

8、( (current-it it) & (current-rc!=NULL) )current = current-rc; inserthelper(current,y);if( (current-it y-it) & (current-lc = NULL) )current - lc = y;else if( (current-it it) & (current-rc = NULL) )current - rc = y;nodecount +;void shownodecount()coutnodecountendl;void traverse()Node * current; curren

9、t = root; traversehelper(current); coutendl;void traversehelper( Node * current )if(current != NULL)traversehelper( current-lc );coutitrc );void search(E x)Node * current; current = root; searchhelper(current,x);void searchhelper(Node *current,E x)E y; y=x;if(current = NULL)cout不存在it=y)cout存在it y)cu

10、rrent=current-lc; searchhelper(current,y);else if(current-it rc; searchhelper(current,y);main()BST treeone;coutpleasr input 10 numbersendl; a10;for(i=0;iai; i=0;i=9;i+)treeone.insert(ai);for(cout中序遍历endl; treeone.traverse();coutplease input the search numberx;treeoarch(x);coutplease input the search numbery;treeoarch(y); return 0;（2）程序分析先构建一个节点类Node，public 成员有本身元素it，指向左子树的指针lc,指向右子树的指针rc 及构造函数Node( E i)，在构建搜索二叉树类 BST，private成员有根指针root，节点个数nodecount，public 成员有构造函数 BST()，节点的函数void insert( E x )，及void inserthelper( Node * x, Node * y)，显示节点个数的函数 void shownodecount()，中序遍