《数据结构(同名7128)》由会员分享，可在线阅读，更多相关《数据结构(同名7128)（17页珍藏版）》请在金锄头文库上搜索。
1、算法设计基础实验 班级： 学号： 姓名： 谭驷睿 实验一 线性表的应用实验内容：1 给定一线性表L=（15,25,05,36,78,85,23），写出顺序存储结构下的插入、删除、排序操作的算法及程序。2 写出链接存储结构下的插入、删除、排序操作的算法及程序。实验要求：1 掌握顺序及链接存储下的插入、删除算法；2 掌握直接插入排序算法；实验程序及结果：#include #include typedef int ElemType;struct ListElemType *list;int size;int MaxSize;/初始化线性表void InitList(List &L)L.MaxSize
2、 = 12;/初始定义数组长度为12，可增减。L.list = new ElemTypeL.MaxSize;if(L.list = NULL)cout动态可分配的内存空间用完，退出运行！endl;exit(1);L.size=0;/删除线性表的所有元素，使之成为一个空表void ClearList(List &L)if(L.list!=NULL)delete L.list;L.list=NULL;L.MaxSize=0;L.size=0;/得到线性表长度int LenthList(List &L)return L.size;/查找函数bool FindList(List &L,ElemType
3、 &item)for(int i=0;iL.size;i+)if(L.listi=item)item = L.listi;return true;return false;/遍历函数void TraverseList(List &L)for(int i=0;iL.size;i+)coutL.listi ;coutendl;/插入一个元素bool InsertList(List &L,ElemType item,int pos)if(posL.size+1)coutpos值无效！endl;return false;int i;if(pos=0)for(i=0;iL.size;i+)if(item
4、L.listi) break;pos=i+1;else if(pos=-1) pos = L.size+1;if(L.size=L.MaxSize)int k=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);if(L.list=NULL)cout动态可分配内存用完，退出运行！=pos-1;i-)L.listi+1=L.listi;L.listpos-1=item;L.size+;return true;/删除函数bool DeleteList(List &L,ElemType item,int pos)if(L.
5、size=0)cout线性表为空，删除无效！endl;return false;if(posL.size)coutpos值无效！endl;return false;int i;if(pos=0)for(i=0;iL.size;i+)if(item = L.listi) break;if(i=L.size) return false;pos=i+1;else if(pos=-1) pos=L.size;item = L.listpos-1;for(i=pos;iL.size;i+)L.listi-1=L.listi;L.size-;return true;/排序函数void SortList(L
6、ist &L)int i,j;ElemType x;for(i=1;i=0;j-)if(xL.listj) L.listj+1=L.listj;else break;L.listj+1=x;void main()int a12=3,6,9,12,15,18,21,24,27,30,33,36;int i; ElemType x;List t;InitList(t);/将数组a的元素赋值给线性表tfor(i=0;i12;i+)InsertList(t,ai,i+1);TraverseList(t);/插入函数部分InsertList(t,48,13);InsertList(t,40,0);/查找
7、部分coutx;if(FindList(t,x) cout查找成功！endl;else cout查找失败！endl;/删除部分 coutx;if(DeleteList(t,x,0) cout删除成功！endl;else cout删除失败！endl; TraverseList(t);/插入部分coutx;if(InsertList(t,x,0) cout插入成功！endl;else cout插入失败！endl;TraverseList(t);/排序部分cout待排序的线性表s:endl;int b12=7,6,9,99,12,10,29,24,27,38,33,36;int j; List s;
8、InitList(s);/将数组b的元素赋值给线性表sfor(j=0;j12;j+)InsertList(s,bj,j+1);TraverseList(s);cout排序结果:endl;SortList(s);TraverseList(s);实验二 二叉树的遍历实验内容：给定一棵用广义表表示的二叉树T，写出其前序遍历、中序遍历、后序遍历、层序遍历的算法及程序。实验要求：1 掌握二叉树的前序、中序、后序遍历的递归算法；2 了解其非递归算法，并试着仿写。3 掌握层序遍历算法，学会队列的应用。实验程序及结果：#include #include typedef char ElemType;struct
9、 BTreeNodeElemType data;BTreeNode*left;BTreeNode*right;/初始化二叉树void InitBTree(BTreeNode*& BT)BT=NULL; /建立二叉树void CreateBTree(BTreeNode*&BT,char *a)const int MaxSize=10;BTreeNode*sMaxSize;int top=-1;BT=NULL;BTreeNode*p;int k;int i=0;while(ai)switch(ai)case :break;case (:if(top=MaxSize-1)cout栈空间太小，请增加M
10、axSize的值！endl;exit(1);top+;stop=p;k=1;break;case ):if(top=-1)cout二叉树广义表字符串错！data=ai;p-left=p-right=NULL;if(BT=NULL) BT=p;elseif(k=1) stop-left=p;else stop-right=p;i+;/输出二叉树void PrintBTree(BTreeNode*BT)if(BT!=NULL)coutdata;if(BT-left!=NULL|BT-right!=NULL)coutleft); if(BT-right!=NULL) coutright); coutleft);ClearBTree(BT-right);delete BT;BT=NULL;/前序遍历void PreOrder(BTreeNode* BT)if(BT!=NULL)coutdataleft);PreOrder(BT-right);/中序遍历void InOrder(BTreeNode* BT)if(BT!=NULL)InOrder(BT-left);coutdata ;InO
