数据结构实验线性表及堆栈操作.doc

数据结构实验（1）（线性表的操作）实验目的1、 会定义线性表的顺序存储类型。2、 熟悉C或C+程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。3、 熟悉对线性表的一些基本操作和具体的函数定义。4、 熟悉TurboC或VC操作环境的使用以及多文件程序的输入、编辑、调试和运行的全过程。程序要求：该程序的功能是对元素类型为整型的顺序存储的线性表进行一些操作。该程序包含三个文件，一个为头文件，用来存储定义的线性表结构类型以及对线性表进行的各种操作的函数声明；第二个为线性表操作的实现文件，用来存储每一种线性表操作的具体函数定义；第三种为主文件，用来定义线性表和调用线性表的一些操作，实现对给定线性表的具体运算。代码如下：#include#includeconst int ML=10;/定义ElemType为int类型typedef int ElemType;/线性表顺序存储类型struct LinearList ElemType* list; /存线性表元素int size; /存线性表长度int MaxSize; /存list数组长度;/初始化线性表void InitList(LinearList& L, int ms) L.list=new ElemTypems;if(!L.list) cerrMemory allocation failure!endl;exit(1); L.size=0;L.MaxSize=ms;/清空线性表void ClearList(LinearList& L) L.size=0;/求线性表长度int ListSize(LinearList& L) return L.size;/检查线性表是否为空bool ListEmpty(LinearList& L) return L.size=0; /检查线性表是否为满bool ListFull(LinearList& L) return L.size=L.MaxSize; /遍历线性表void TraverList(LinearList& L) for(int i=0; iL.size; i+) coutL.listi ;coutendl; /从线性表中查找元素bool FindList(LinearList& L, ElemType& item) for(int i=0; iL.size; i+)if(L.listi=item) item=L.listi;return true;return false; /更新线性表中的给定元素bool UpdateList(LinearList& L, const ElemType& item) for(int i=0; i0) for(int i=L.size-1; i=0; i-)L.listi+1=L.listi;L.list0=item; else if(mark0) L.listL.size=item;else for(int i=0; iL.size; i+) if(item=i; j-) L.listj+1=L.listj; L.listi=item;L.size+;return true; /从线性表中删除表头、表尾或等于给定值的元素bool DeleteList(LinearList& L, ElemType& item, int mark)if(ListEmpty(L) return false;if(mark0) item=L.list0;for(int i=1; iL.size; i+)L.listi-1=L.listi; else if(mark0) item=L.listL.size-1;else for(int i=0; i=L.size) return false; else item=L.listi; for(int j=i+1; jL.size; j+) L.listj-1=L.listj;L.size-;return true; /对线性表按升序或降序输出void OrderOutputList(LinearList& L, int mark)int* b=new intL.size;int i,k;for(i=0; iL.size; i+)bi=i;for(i=1; iL.size; i+) k=i-1;for(int j=i; jL.size; j+) if(mark=1 & L.listbjL.listbk) k=j; /升序 if(mark!=1 & L.listbkL.listbj) k=j; /降序if(k!=i-1) int x=bi-1; bi-1=bk; bk=x;for(i=0; iL.size; i+)coutL.listbi ;coutendl;代码操作截图：添加并遍历删除一个整数：实验（5）二叉树操作实验内容下面给出两个程序，它们都是用来实现对二叉树的操作。第一个程序采用结构定义二叉树结点的类型，采用普通函数对二叉树进行每一种操作的处理；第二个程序采用类定义二叉树的类型，采用成员函数实现二叉树的每一种操作。代码如下：#include#include#includetypedef char ElemType; /定义二叉树结点类型struct BTreeNode ElemType data; BTreeNode* left; BTreeNode* right; /初始化二叉树，即把树根指针置空 void InitBTree(BTreeNode*& BT);/根据存于字符数组a的二叉树广义表建立对应的二叉树存储结构 void CreateBTree(BTreeNode*& BT, char* a);/判断二叉树是否为空 bool BTreeEmpty(BTreeNode* BT);/按任一种遍历次序输出二叉树中的所有结点 void TraverseBTree(BTreeNode* BT, int mark);/求二叉树的深度 int BTreeDepth(BTreeNode* BT);/求二叉树中所有结点数 int BTreeCount(BTreeNode* BT);/求二叉树中所有叶子结点数 int BTreeLeafCount(BTreeNode* BT);/按照二叉树的一种表示方法输出整个二叉树 void PrintBTree(BTreeNode* BT);/清除二叉树，使之变为一棵空树 void ClearBTree(BTreeNode*& BT); /二叉树操作的实现文件 /初始化二叉树，即把树根指针置空void InitBTree(BTreeNode*& BT)BT=NULL; /根据存于字符数组a的二叉树广义表建立对应的二叉树存储结构void CreateBTree(BTreeNode*& BT, char* a)BTreeNode* s10; /s数组作为存储二叉树中根结点指针的栈int top=-1; /top作为s栈的栈顶指针BT=NULL; /给树根指针置空BTreeNode* p; /定义p为指向二叉树结点的指针int k; /用k作为处理结点的左子树和右子树的标记，k=1处理 /左子树，k=2处理右子树istrstream ins(a); /把字符串a定义为输入字符串流对象inschar ch; insch; /从ins流对象顺序读入一个字符， while (ch!=) /每循环一次处理一个读入的字符，直到扫描到字符为止switch(ch)case (:top+; stop=p; k=1; break; case ):top-; break;case ,:k=2; break;default:p=new BTreeNode;p-data=ch; p-left=p-right=NULL;if(BT=NULL) BT=p;else if(k=1) stop-left=p;else stop-right=p; insch;/判断二叉树是否为空bool BTreeEmpty(BTreeNode* BT)return BT=NULL; /按任一种遍历次序输出二叉树中的所有结点void TraverseBTree(BTreeNode* BT, int mark)if(mark=1) /先序遍历if(BT!=NULL) coutdataleft,mark); TraverseBTree(BT-right,mark); else if(mark=2) /中序遍历 if(BT!=NULL) TraverseBTree(BT-left,mark); coutdataright,mark);else if(mark=3) /后续遍历if(BT!=NULL) TraverseBTree(BT-left,mark); TraverseBTree(BT-right,mark); coutdata ;else if(mark=4) /按层遍历 const MaxLength=30; BTreeNode* QMaxLength; /定义存储二叉树结点指针的数组空间作为队列使用 int front=0, rear=0; /定义队首指针和队尾指针，初始均置0表示空队 BTreeNode* p; if(BT!=NULL) rear=(rear+1)%MaxLength; /后移队尾指针 Qrear=BT; /将树根结点指针进队 while (front!=rear) /当队列非空时执行循环 front=(front+1)%MaxLength; /后移队首指针 p=Qfront; /删除队首结点 coutdataleft!=NULL) /若结点存在左孩子，则左孩子结点指针进队 rear=(rear+1)%MaxLength; Qrear=p-left; if(p-right!=NULL) /若结点存在右孩子，则右孩子结点指针进队 rear=(rear+1)%MaxLength; Qrear=p-right;else cerrmark的值无效! 遍历失败!left); /计算右子树的深度int dep2=BTreeDepth(BT-right); /返回树的深度if(dep1dep2) return dep1+1; else return dep2+1; /求二叉树中所有结点数int BTreeCount(BTreeNode* BT)if(BT=NULL) return 0;else return BTreeCount(BT-left)+BTreeCount(BT-right)+1; /求二叉树中所有叶子结点数int BTreeLeafCount(BTreeNode* BT)if(BT=NULL) return 0;else if(BT-left=NULL & BT-right=NULL) return 1;else return BTreeLeafCount(BT-left)+BTreeLeafCount(BT-right); /按照二叉树的一种表示方法输出整个二叉树void PrintBTree(BTreeNode* BT) /输出二叉树的广义表表示if(BT=NULL) return; /树为空时返回else /否则执行如下操作coutdata; /输出根结点的值if(BT-left!=NULL | BT-right!=NULL) coutleft); /输出左子树 if(BT-right!=NULL) coutright); /输出右子树 coutleft); /删除左子树ClearBTree(BT-right); /删除右子树delete BT; /删除根结点BT=NULL; /置根指针为空 /进行二叉树操作的主程序文件 void main() /定义指向二叉树结点的指针，并用它作为树根指针BTreeNode* bt; /初始化二叉树，即置树根指针bt为空InitBTree(bt); /定义一个用于存放二叉树广义表的字符数组char b50; /从键盘向字符数组b输入以字符结束的二叉树广义表cout输入以字符作为结束符的二叉树广义表表示:endl;cin.getline(b,sizeof(b); /建立以bt作为树根指针的二叉树的链接存储结构 CreateBTree(bt,b); /以广义表形式输出二叉树PrintBTree(bt); coutendl; /前序遍历以bt为树根指针的二叉树cout前序：;TraverseBTree(bt,1); coutendl; /中序遍历以bt为树根指针的二叉树cout中序：;TraverseBTree(bt,2); coutendl; /后序遍历以bt为树根指针的二叉树cout后序：;TraverseBTree(bt,3); coutendl; /按