数据结构实验报告.doc

1、数据结构 实验报告 姓名： 学号： 班级： 学院： 实验一单链表实验 (一) 实验目的 1.理解线性表的链式存储结构。 2.熟练掌握动态链表结构及有关算法的设计。 3.根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。 (二) 实验任务 编写算法实现下列问题的求解 1.求链表中第 i 个结点的指针（函数），若不存在，则返回 NULL。 2.在第 i 个结点前插入值为 x 的结点。 3.删除链表中第 i 个元素结点。 4.在一个递增有序的链表 L 中插入一个值为 x 的元素，并保持其递增有序特性。 5.将单链表 L 中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，

2、然后再将 这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。 6.求两个递增有序链表 L1 和 L2 中的公共元素，并以同样方式连接成链表 L3。 (三) 主要仪器设备 PC 机，Windows 操作平台，Visual C+ (四) 实验分析 顺序表操作：定义一个顺序表类，该类包括顺序表的存储空间、存储容量和长度，以及构造、插 入、删除、遍历等操作的方法 (五) 源程序 头文件文件名：linklist.h #include using namespace std; struct node int data; node *next; ; class list public:

3、 list(); int length()const return count;/求链表长度 list(); void create();/链表构建，以 0 为结束标志 void output();/链表输出 intget_element(constinti)const;/按序号取元素 node *locate(constint x) const;/搜索对应元素 int insert(constinti,constint x);/插入对应元素 intdelete_element(constinti);/删除对应元素 node *get_head() return head;/读取头指针 voi

4、d insert2(constint x); friend void SplitList(list L1, list friend void get_public(list L1, list L2, list private: int count; node *head; ; list:list() head=new node; head-next=NULL; count=0; void list:create()/链表构建，以 0 为结束标志 int x; coutx; node *rear=head; while(x!=0) count+; node *s=new node; s-data

5、=x; rear-next=s; rear=s; rear-next=NULL; cinx; void list:output() node *p=head-next; cout*Top of this list*endl; while(p!=NULL) coutdatanext; coutendl*End of this list*next; j=1; while(p!=NULL j+; if(p=NULL) return 0; else return x=p-data; return 1; node *list:locate(constint x)const node *p=head-ne

6、xt; while(p!=NULL) if(p-data=x)return p; else p=p-next; return NULL; int list:insert(constinti,constint x)/实验 2 node *p=head; int j=0; while(j!=i-1 j+; if(icount+1) return 0; node *s=new node; s-data=x; s-next=p-next; p-next=s; count+; return 1; int list:delete_element(constinti)/实验 3 node *p=head;

7、int j=0; while(j!=i-1 j+; if(icount) return 0; node *u=p-next; p-next=u-next; delete u; count-; return 1; void list:insert2(constint x)/实验 4 node* p,*q; p=head; while(p-next!=NULL if (p-next=NULL | p-next-datax) q=new node; q-data=x; q-next=p-next; p-next=q; count+; list:list() while(head-next!=NULL

8、) delete_element(1); 主程序 #include #includelinklist.h using namespace std; voidSplitList(list L1, list for(inti = 1; p1 != NULL; i+) if(i % 2) L2.insert(L2.count+1,p1-data); else L3.insert(L3.count+1,p1-data); p1=p1-next; L1.output(); L2.output(); L3.output(); voidget_public(list L1,list L2,list whil

9、e (p1!=NULL else if (p1-datap2-data) p2=p2-next; else L3.insert(L3.count+1,p1-data); p1=p1-next; p2=p2-next; int main() list L1; inti,x; cout当前为实验 1、2、3; L1.create(); couti; coutL1.get_element(i)endl; coutxi; L1.insert(i,x); L1.output(); couti; L1.delete_element(i); L1.output(); list L1; int x; cout

10、实验 4，输入递增有序的 L; L1.create(); coutx; L1.insert2(x); L1.output(); list L1,L2,L3; cout当前为实验 5，单链表 L 奇数、偶数项分开; L1.create(); SplitList(L1,L2,L3); list L1,L2,L3; cout当前为实验 6，求 L1 与 L2 公共元素; L1.create(); L2.create(); get_public(L1,L2,L3); L3.output(); return 0; (六) 代码测试 实验 1、2、3 当 i 为 n 时 实验 1、2、3 当 i 为 n+

11、1 时 实验 1、2、3 当 i 为 0 时 实验 4 实验 5 实验 6 实验二二叉树实验 (一) 实验目的 1.掌握二叉树的动态链表存储结构及表示。 2.掌握二叉树的 3 种遍历算法（递归和非递归两类方式）。 3.运用二叉树 3 种遍历的方法求解有关问题。 (二) 实验任务 编写算法实现下列问题的求解 1.求二叉树的高度。 2.设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。 3.将按顺序方式存储在数组中的二叉树转换为二叉链表形式。 4.复制一棵二叉树 T 到 T1。 5.交换二叉树中每个结点的左右孩子指针的值。 6.设计算法以实现下面所提到以扩展二叉树的先序序列作为输入构建二

12、叉树的功能。 (三) 主要仪器设备 PC 机，Windows 操作平台，Visual C+ (四) 实验分析： 为了完成针对特定问题和要求的二叉树的算法的实验，通常需要完成以下工作： （1）设计或选择合适的存储结构。在许多情况下可能是指定一种存储结构，就二叉树来说，一般 默认为或者是较多地采用二叉链表存储结构。具体结构的设计可参考教科书。 （2）设计出针对所选择的结构的算法。 （3）构造一棵（或者多棵，为了能充分地实验，应该分别构建多棵）二叉树以作为算法运行时的 数据。为达到有效检验算法的目的，一般要求所构造的二叉树要尽可能多地包含多种情况，要有 一定的复杂度，否则难以达到预定的目标。 (五)

13、 源程序： 头文件文件名： bitre.h #include using namespace std; typedefstruct node char data; struct node *lchild, *rchild; bnode,*bitre; /bnode 为树节点，bitre 为指向树节点的指针 intmaxn=0; classBiTree public: BiTree(char a) cout输入扩展二叉树的先序序列来构造二叉树; root=create_pre_bitre(root); BiTree()/构造时若无参数，则构造出空树 BiTree() dis(root); voi

14、d preorder() cout-the top of the preorder of this tree-endl; preorder(root); coutendl-the end of the preorder of this tree-endl; voidinorder() inorder(root); voidinorder_re() cout-the top of the value of every node in this tree-endl; inorder_re(root,1); cout-the end of the value of every node in thi

15、s tree-data=T1-data; T2-lchild=copy_bitre(T2-lchild,T1-lchild); T2-rchild=copy_bitre(T2-rchild,T1-rchild); return T2; bitreBiTree:exch_array(bitreT,char A,intn,intnum)/从数组形式转换到链表二叉树 if (ndata=An-1; T-lchild=exch_array(T-lchild,A,2*n,num); T-rchild=exch_array(T-rchild,A,2*n+1,num); else T=NULL; retur

16、n T; bitreBiTree:create_pre_bitre(bitre T) /以扩展二叉树读入后构造二叉树 charch; cinch; if (ch=.) T=NULL; else T=new bnode; T-data=ch; T-lchild=create_pre_bitre(T-lchild); T-rchild=create_pre_bitre(T-rchild); return T; void BiTree:dis(bitre T)/析构函数组成函数 if(T!=NULL) dis(T-lchild); dis(T-rchild); delete T; bitreBiTr

17、ee:exchange_child(bitre T)/交换左右孩子指针的值 if (T!=NULL) bitre temp; temp=T-rchild; T-rchild=T-lchild; T-lchild=temp; T-lchild=exchange_child(T-lchild); T-rchild=exchange_child(T-rchild); return T; void BiTree:travel_re(bitreT,int n) /带求高度的遍历 if (T!=NULL) n+; if (nmaxn) maxn=n; travel_re(T-lchild,n); trav

18、el_re(T-rchild,n); voidBiTree:preorder(bitre T) if(T!=NULL) coutdatalchild); preorder(T-rchild); void BiTree:inorder_re(bitreT,int n)/中序遍历并输出数据和层数 if (T!=NULL) inorder_re(T-lchild,n+1); coutdata:data depth:nrchild,n+1); 主程序 #include #includebitre.h using namespace std; intnum; int main() char A100;

19、BiTree T; inti; coutnum; coutenter the bitree;/数组读入二叉树 for (i=0; iAi; T.exch_array(A,num); /从数组形式转换到链表二叉树 T.preorder(); /先序遍历输出 cout高度为T.travel_re()endl; T.inorder_re(); BiTree T2; T2.copy_bitre(T); /拷贝树 T2.preorder(); BiTreeT3(1); T3.exchange_child(); /交换左右孩子指针 T3.preorder(); return 0; (六) 代码测试 以数组

20、形式输入二叉树。从数组形式转换到链表二叉树后，先序输出，求出高度，中序输出 各结点的值及其所对应的层次数，拷贝后再次先序输出。 输入扩展二叉树的先序序列来构造二叉树，交换左右指针后输出。 实验三排序实验 (一) 实验目的 1.掌握各种内部排序算法。 2.理解各种内部排序算法的特性、时间性能和空间性能，在此基础上能根据具体情况选择合适 的排序算法。 3.掌握通过实验方式分析算法的正确性、时间性能和空间性能的方法。 (二) 实验任务 编写算法实现下列问题的求解 完成下面功能：将一个整型数组调整为这样的数组：所有 3 的倍数在最左边，所有除以 3 余 1 的数在中间，而所有除以 3 余 2 的数在最

21、右边。要求算法的时间尽可能少。 (三) 主要仪器设备 PC 机，Windows 操作平台，Visual C+ (四) 实验分析： 可采用划分算法来实现。 (五) 源程序： #include using namespace std; constintmaxn=100; int n; void partition(int A,intt,int while(i!=j) while(ij if(ij) Ai=Aj; i+; while(ij if(ij) Aj=Ai; j-; Ai=x;cutpoint=i; void partition2(int A,ints,int t) int x=As,i=s,j=t; while(i!=j) while(ij if(ij) Ai=Aj; i+; while(ij if(ij) Aj=Ai; j-; Ai=x; voidFx(int A,int t) inti; partition(A,t,i); if (Ai%3=0) partition2(A,i+1,t); else partition2(A,i,t); int main() int Amaxn; coutn; cout输入各个数字; for(inti=0; iAi; Fx(A,n-1); for(int j=0; jn; j+) coutAj ; return 0; (六) 代码测试