东华大学2013数据结构课程设计

1、 数据结构课程设计-个人设计报告专 业：班 级：姓 名：学 号：指导教师：日 期： 目录1 课程设计目的32 课程设计内容和要求33 任务完成情况34 设计报告44.1顺序表44.1.1 设计目的44.1.2 设计内容及要求44.1.3 需求分析44.1.4 概要设计54.1.5 详细代码64.1.6 使用说明64.1.7 测试结果与分析74.1.8 参考文献104.2链表114.2.1 设计目的114.2.2 设计内容及要求114.2.3 需求分析114.2.4 概要设计114.2.5 详细代码114.2.6 使用说明114.2.7 测试结果与分析114.2.8 参考文献114.3树和二叉树

2、124.3.1 设计目的124.3.2 设计内容及要求124.3.3 需求分析124.3.5 详细代码124.3.6 使用说明124.3.7 测试结果与分析124.3.8 参考文献125 体会与感想13附录：14设计一（顺序表）的代码14设计二（链表）的代码17设计三（树和二叉树）的代码171 课程设计目的1、 学习获取知识的方法；2、 提高发现问题、分析问题和解决实际问题的能力；3、 加强创新意识和创新精神；4、 加强团队的分工与合作；5、 掌握面向实际背景思考问题的方法。2 课程设计内容和要求内容：前言第一章 顺序表第二章 链表第三章 树和二叉树个人基本任务：完成第1,2,3章，其中选做题

3、可不做。3 任务完成情况任务完成情况介绍，如表3-1.表3-1 任务完成情况表完成任务名称顺序表链表树和二叉树4 设计报告4.1 顺序表4.1.1 设计目的熟悉顺序表的应用4.1.2 设计内容及要求本程序用C语言编写，完成以下功能：1）实现二路归并排序算法。2）实现快速排序算法。3）实现堆排序算法。4）实现冒泡排序和选择排序算法5）删除线性表中所有值为item的数据元素6）五种排序方法性能测试 4.1.3 需求分析本程序用C编写，完成5种排序和性能测试，删除线性表中所有值为item的数据元素等功能，并且需要一个菜单让用户自主选择执行的功能。 输入的形式和输入值的范围：输入的元素是整形，输入值的

4、范围是0-9，输入-1结束。 输出的形式：在每次选择菜单后，输出相应的结果，并且询问下次操作的项目。 程序所能达到的功能：完成5种排序和性能测试，删除线性表中所有值为item的数据元素。每次操作结束后，都会有菜单方便用户进行下一步的操作。 测试数据：A菜单显示为：请输入您要测试的项目：1顺序存储的线性表5种排序算法 选择 1 显示 请输入元素个数 输入 整数 输出 5种排序方法排序后的元素2删除线性表中所有值为item的数据元素 选择 2 显示 请输入元素个数 输入 整数 显示 依次输入元素，按空格分开 输入 整数 显示 请输入item的值（整数） 输入 整数 输出 剩下的元素3性能测试 选择

5、 3 输出 5种排序（有序/随机元素）的时间0退出管理系统 选择 0 退出当前程序4.1.4 概要设计1） 为了实现上述程序功能，需要定义顺序表的抽象数据类型：typedef struct listint key;/关键字项 RedType;/记录类型 typedef structRedType rMAXSIZE;/r0闲置或用作哨兵单元 int length; /顺序表长度，参加排序元素的实际个数SqList;/顺序表类型2） 本程序包含16个函数： void InitialRandom(SqList *L)ContactList void Initial(SqList *L) void M

6、erge(RedType SR, RedType TR,int i,int m,int n) void Msort(RedType SR ,RedType TR1 ,int s ,int t) void Mergesort(SqList *L ) void choice(SqList *L) void bubble(SqList *L) void quicksort(SqList *L,int start,int end) void Heapsort(SqList *L) void HeapAdjust(SqList *L,int s,int m) void out(SqList *L) in

7、t Delete(SqList *L, int item) void OrderInitial(SqList *L) void InOrderInitial(SqList *L) void Performance() int main()4.1.5 详细代码见附录一4.1.6 使用说明程序执行后出现如图4.1-2的菜单：图4.1-2 菜单菜单共有四个选项，选择不同的选项会出现相应的提示进行下一步操作：选择1：顺序存储的线性表5种排序算法选择2：删除线性表中所有值为item的数据元素选择3：性能测试选择0：退出4.1.7 测试结果与分析1 顺序存储的线性表5种排序算法，如图4.1-3：图4.1-

8、3 实验结果：生成随机数，用5种方法从小到大排序2 删除线性表中所有值为item的数据元素，如图4.1-4：图4.1-4 删除元素实验结果：分三类讨论，分别是删除第一个，最后一个，当中元素3 性能测试，如图4.1-5：如图4.1-5 一万元素性能测试如图4.1-6 五十万元素性能测试实验结果：分别生成有序和无需的元素，用5种排序方法分别排序，并输出时间注意：VS6.0中10万元素以上就会溢出，特别是快速排序只能在1万元素时实现，否则栈会溢出，故在50万测试时把快速排序的函数用“/”注释掉，因此时间为0。4 输入0退出4.1.8 参考文献1 严蔚敏等著， 数据结构（C语言版）， 清华大学出版社2

9、 高一凡著， 数据结构算法解析， 清华大学出版社4.2链表的应用4.2.1 设计目的熟悉链表的应用4.2.2 设计内容及要求本程序用C语言编写，完成以下功能：1）删除元素使两个链表相等。2）猴子选大王。3）非循环双向链表按频度排序。4）稀疏矩阵的存储4.2.3 需求分析本程序用C编写，完成4种链表功能，并且需要一个菜单让用户自主选择执行的功能。 输入的形式和输入值的范围：输入的元素是整形，输入值的范围是0-9，输入-1结束。 输出的形式：在每次选择菜单后，输出相应的结果，并且询问下次操作的项目。 程序所能达到的功能：完成4种链表功能。每次操作结束后，都会有菜单方便用户进行下一步的操作。 测试数

10、据：A菜单显示为：请输入您要测试的项目：1顺序存储的线性表5种排序算法 选择 1 显示 创建链表A/B,请将递增输入整数，用空格分开，输入-1结束 输入 整数. -1 显示 删除元素后A,B链表为: 输出 A,B中的元素2猴子选大王 选择 2 显示 请输入猴子总数n 输入 整数 显示 请输入出局猴子报的数m(mn) 输入 整数 输出 i号猴子为大王3非循环双向链表按频度排序 选择 3 显示 请输入元素值(1-10整数)，用空格分开,-1表示结束 输入 整数. -1 显示 随机访问10次元素，令元素freq加1并，使此链表中结点保持按访问频度递减的顺序排列，随机访问的元素为 输出 按freq排序

11、后的元素4稀疏矩阵的存储 选择 4 显示 请输入矩阵的总行数，总列数，用空格分开,行与列从0记起 输入 a b (整数) 显示 建立第一/二个矩阵 输入 例如 输出 输出第一/二个矩阵 输出 输出相加后的矩阵0退出管理系统 选择 0 退出当前程序4.2.4 概要设计1）为了实现上述程序功能，需要定义链表的抽象数据类型：/这是单链表 typedef struct LNodeint data;struct LNode* next;LNode,*LinkList;/双向链表 typedef struct DuLNodeint data,freq;/freq是频率 struct DuLNode *pr

12、ev,*next;/前后两个指针DuLNode,*DuLinkList;/矩阵结点 typedef struct MatrixNodeint row,column,data;/行 列 数值 struct MatrixNode *next;MatrixNode,*MatrixList;2）本程序包含17个函数： void Initial(LinkList &L)/建立链表 int not_in_L(int m,LinkList L)/判断元素是否在L中 void del(LinkList L1,LinkList L2)/对L1操作，删除在L1中而不在L2中的元素void output(LinkL

13、ist L)/输出链表void fun1() void Monkey()/猴子选大王 void fun2() void InitDuList(DuLinkList &L)/创建有表头结点的双向链表 DuLNode* Locate(DuLNode*L,int x)/在L中找到值为x的节点，freq值加一，返回找到结点的地址，类型为指针型/对p所指结点进行插入，使链表中结点保持按访问频度递减排列void OutputDuLink(DuLinkList L)输出双向链表 void fun3() void InitMatrix(MatrixList &L)/创建稀疏矩阵 int FindData(Ma

14、trixList L,int a,int b)/返回矩阵L的a行b列的值 void AddMatrix(MatrixList A,MatrixList B,MatrixList &C,int hang,int lie)/矩阵C=A+B void MatrixOutput(MatrixList L,int hang,int lie)/输出矩阵 void fun4() int main()4.2.5 详细代码见附录二4.2.6 使用说明程序执行后出现如图4.2-2的菜单：图4.2-2 菜单菜单共有五个选项，选择不同的选项会出现相应的提示进行下一步操作：选择1：删除元素使两个链表相等选择2：猴子选大

15、王选择3：非循环双向链表按频度排序选择4：稀疏矩阵的存储选择0：退出4.2.7 测试结果与分析1 删除元素使两个链表相等，如图4.2-3：图4.2-3 实验结果：输出删除元素后的A,B链表，若有相同的元素则保留2 猴子选大王，如图4.2-4：图4.2-4 删除元素实验结果：输出几号猴子是大王3 非循环双向链表按频度排序，如图4.2-5：图4.2-5 实验结果：随机访问链表10次，按照频度由大到小排列输出4 稀疏矩阵的存储，如图4.2-6输入数据： + = 图4.2-6实验结果：输出相加后的矩阵5 输入0退出4.2.8 参考文献1 严蔚敏等著， 数据结构（C语言版）， 清华大学出版社2 高一凡著

16、， 数据结构算法解析， 清华大学出版社4.3 树与二叉树 4.3.1 设计目的熟悉二叉树的应用4.3.2 设计内容及要求本程序用C语言编写，完成以下功能：1）输入字符序列，建立二叉链表，中序遍历二叉树输出。2）二叉树的叶子结点按从左到右的顺序连成一个单链表3）判断某二叉树是否是完全二叉树。4）判断某二叉树是否是二叉排序树4.3.3 需求分析本程序用C编写，完成4种二叉树功能，并且需要一个菜单让用户自主选择执行的功能。 输入的形式和输入值的范围：输入的元素是整形，输入值的范围是一位整数，输入空格开标节点为空。 输出的形式：在每次选择菜单后，输出相应的结果，并且询问下次操作的项目。 程序所能达到的

17、功能：完成4种二叉树功能。每次操作结束后，都会有菜单方便用户进行下一步的操作。 测试数据：A菜单显示为：请输入您要测试的项目：1输入字符序列，建立二叉链表，中序遍历二叉树输出 选择 1 显示 请依次先序输入，两个元素之间不需要空格，结点为空输入空格，按回车结束 输入 例如：123 4 5 回车 输出 中序遍历输出二叉树2二叉树的叶子结点按从左到右的顺序连成一个单链表 选择 2 显示 请依次先序输入，两个元素之间不需要空格，结点为空输入空格，按回车结束 输入 例如：123 4 5 回车 输出 先序遍历叶子节点，链表输出叶子节点3判断某二叉树是否是完全二叉树 选择 3 显示 请依次先序输入，两个元

18、素之间不需要空格，结点为空输入空格，按回车结束 输入 例如：123 4 5 回车 输出 是否是完全二叉树4判断某二叉树是否是二叉排序树 选择 4 显示 请依次先序输入，两个元素之间需要空格，结点为空输入0，按回车结束 输入 例如：1 2 3 0 0 4 0 0 5 0 0 回车 输出 是否是二叉排序0退出管理系统 选择 0 退出当前程序4.3.4 概要设计1）为了实现上述程序功能，需要定义链表的抽象数据类型：/data是char类型的二叉树 typedef struct BiTNodechar data;struct BiTNode * lchild,*rchild;BiTNode,*BiTr

19、ee;/data是int类型的二叉树 typedef struct BiTNode2int data;struct BiTNode2 * lchild,*rchild;BiTNode2,*BiTree2;2）本程序包含13个函数/创建 data是char类型的二叉树 void CreateBiTree(BiTree & T) / 创建 data是int类型的二叉树 void CreateBiTree2(BiTree2 &T)/中序遍历 void InOrder(BiTree T)/把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head void LeafLinkList(BiTr

20、ee T)/先序遍历叶子结点 void PreOrderLeaf(BiTree T)/判断是否是完全二叉树 层次遍历二叉树 返回 是true，否false int CompleteBiTree(BiTree T)/int型中序遍历2 void InOrder2(BiTree2 T)/判断是否是二叉排序树 返回 是true，否false /二叉排序树的中序遍历是有序递增的 int SortTree()void fun1()void fun2()void fun3()void fun4()int main() 4.3.5 详细代码见附录三4.3.6 使用说明程序执行后出现如图4.2-2的菜单：图4

21、.32 菜单菜单共有五个选项，选择不同的选项会出现相应的提示进行下一步操作：选择1：输入字符序列，建立二叉链表，中序遍历二叉树输出选择2：二叉树的叶子结点按从左到右的顺序连成一个单链表选择3：判断某二叉树是否是完全二叉树选择4：判断某二叉树是否是二叉排序树选择0：退出4.3.7 测试结果与分析1 输入字符序列，建立二叉链表，中序遍历二叉树输出，如图4.33：测试数据为：图4.33 实验结果：中序遍历输出二叉树2 二叉树的叶子结点按从左到右的顺序连成一个单链表，如图4.4：图4.34 实验结果：先序遍历叶子节点，链表输出叶子节点3 判断某二叉树是否是完全二叉树，如图4.35：测试数据：图4.35

22、实验结果：第一棵树是完全二叉树，第二棵不是。4 判断某二叉树是否是二叉排序树，如图4.36测试数据： 图4.36实验结果：第一棵树是二叉排序树，第二棵不是5 输入0退出4.3.8 参考文献1 严蔚敏等著， 数据结构（C语言版）， 清华大学出版社2 高一凡著， 数据结构算法解析， 清华大学出版社5 体会与感想经过这次实验，我对数据结构中的顺序表，链表，二叉树有了进一步的认识。对于实现算法我总结出以下几点： 1. 问题是否是已经学过的数据结构，如果不是，就阅读相关参考书，并加以自己的思考。2. 在测试数据是要注意分类讨论，考虑问题必须全面。例如：删除链表节点时，要考虑删除的元素位于链表中的第一个，

23、最后一个，中间，删除后链表为空，链表本来为空，这5中情况进行测试。3.在实现代码编译正确的同时，要注重代码的质量，其中包括代码实际的模块化，代码的风格（上下括号要匹配），测试代码要全面，没有漏洞。 4.在实现线性表第三个函数：“分别生成有序和无需的元素，用5种排序方法分别排序，并输出时间时” 快速排序会出现一些问题。VS6.0中10万元素以上就会报错，特别是快速排序只能在1万元素时实现，否则栈会溢出，故在50万测试时把快速排序的函数用“/”注释掉，因此时间为0。因此本实验中就用1万元素进行实验。5. 碰到一道题目如果没有思路时，可以先在纸上画出流程图，写出算法的分析，把题目的结果推算出来（例如

24、画出完全二叉树、二叉排序树，写出中序遍历和先序遍历），这样可以使自己的变成思路变得清晰、明了。对于解决复杂的问题有帮助。对于算法的实现，尽量保证程序执行的高效率，尽量做到程序代码结构清晰，可读性良好，针对输入的数据进行多方面的分类讨论，程序的适应性良好。操作界面加入提示，做到人性化。为了实现这几个算法，经过思考后，我参考了书上的算法，并参考了一些课外资料，并加以自己的算法优化。今后争取提高编程的速度与正确率，并进一步思考更有难度的代码。附录：设计一的代码#include #include#include#includeusing namespace std;#define MAXSIZE 10

25、000 /50万 (vs6.0中10万以上就会报错)/结构体typedef struct listint key;/关键字项 RedType;/记录类型 typedef structRedType rMAXSIZE;/r0闲置或用作哨兵单元 int length; /顺序表长度，参加排序元素的实际个数SqList;/顺序表类型 void InitialRandom(SqList *L) int i;cout请输入元素个数L-length;srand(unsigned)time(NULL); cout随机生成数字endl;for(i=0;ilength;i+) L-ri.key=rand()%1

26、00;coutri.key ;coutendl;void Initial(SqList *L) int i;cout请输入元素个数L-length;cout依次输入元素，按空格分开endl;for(i=0;ilength;i+)cinL-ri.key;void Merge(RedType SR, RedType TR,int i,int m,int n)/将有序的SRi.m和SRm+1.n由小到大合并成有序表TRi.n /i开始。m中间。n结尾 int j,k,p,q;k=i;j=m+1;p=i; /将较小的放入TR中，i,j是指针，i指向开头，j指向中间 while( i=m & j=n)

27、if(SRi.keySRj.key)TRk+.key=SRi+.key;elseTRk+.key=SRj+.key; while( i=m )TRk+=SRi+;/将剩余的SRi.m复制到TR while( j=n )TRk+.key=SRj+.key;/将剩余的SRj.m复制到TR for(q=p; qlength; RedType *b=new RedTypen;Msort( L-r, b , 0 , n-1 );/a归并到b /选择排序void choice(SqList *L)int i,j,k;int temp;for(i=0;ilength;i+)k=i;for(j=i+1;jle

28、ngth;j+)if(L-rj.keyrk.key)k=j;if(i!=k)/第i个元素与第k个元素交换temp=L-ri.key;L-ri.key=L-rk.key;L-rk.key=temp;/冒泡排序void bubble(SqList *L)int i,j,temp;for(i=0;ilength;i+)for(j=L-length-1;ji;j-)if(L-ri.keyL-rj.key)temp=L-ri.key;L-ri.key=L-rj.key;L-rj.key=temp;/快速排序算法void quicksort(SqList *L,int start,int end)int

29、i,j;int mid;if(start=end)return;i=start;j=end;mid=L-ri.key;while(ij)while(irj.keymid)/找到比mid小的数j-;if(iri.key=L-rj.key;i+;while(iri.key=mid)/找到比mid大的数i+;if(irj.key=L-ri.key;j-;L-ri.key=mid;/一次划分得到基准值的正确位置quicksort(L,start,i-1);/递归调用左子区间quicksort(L,i+1,end);/递归调用右子区间/堆排序算法void Heapsort(SqList *L)void

30、HeapAdjust(SqList *L,int s,int m);/函数申明int temp;/临时变量 int i;/forfor(i=L-length/2;i=0;-i)HeapAdjust(L,i,L-length-1);for(i=L-length-1;i0;-i)temp=L-r0.key;L-r0.key=L-ri.key;L-ri.key=temp;HeapAdjust(L,0,i-1);/单个结点调整void HeapAdjust(SqList *L,int s,int m)int j;int temp=L-rs.key;for(j=2*s;j=m;j*=2)if(jrj.k

31、eyrj+1.key)+j;if(temp=L-rj.key)break;L-rs.key=L-rj.key;s=j;L-rs.key=temp;void out(SqList *L)/cout遍历输出endl;for(int i=0;ilength;i+)/遍历输出coutri.key ;coutlength-1; /设立数组头尾指针 while(iri.key!=item) i+; /若值不为item，头指针右移 if(L-rj.key=item) j-;/若数组尾值为item,尾指针左移 if(L-ri.key=item&L-rj.key!=item) L-ri+.key=L-rj-.k

32、ey;/用末尾元素代替item if(j=0)/表为空时的情况 cout表为空nlength=j+1; out(L); return (1); void OrderInitial(SqList *L) /生成50万有序的数字 int i;L-length=MAXSIZE;for(i=0;ilength;i+)L-ri.key=i;void InOrderInitial(SqList *L) /生成50万随机的数字 int i;srand(unsigned)time(NULL); L-length=MAXSIZE;for(i=0;ilength;i+)L-ri.key=rand()%100;vo

33、id Performance()SqList L;clock_t start,finish;double time; cout元素个数MAXSIZEendl;/二路归并 OrderInitial(&L); /out(&L);start=clock();Mergesort(&L);finish=clock();cout二路归并 有序(double)(finish-start)/CLK_TCKsendl;InOrderInitial(&L);start=clock();Mergesort(&L);finish=clock();cout二路归并 无序(double)(finish-start)/CL

34、K_TCKsendl;/快速排序 OrderInitial(&L); /out(&L);start=clock();quicksort(&L,0,L.length-1);finish=clock();cout快速排序 有序(double)(finish-start)/CLK_TCKsendl;InOrderInitial(&L);/warning:此处快速排序无序元素时可能造成崩溃 start=clock();quicksort(&L,0,L.length-1);/here finish=clock();cout快速排序 无序(double)(finish-start)/CLK_TCKsend

35、l;/堆排序 OrderInitial(&L); /out(&L);start=clock();Heapsort(&L);finish=clock();cout堆排序 有序(double)(finish-start)/CLK_TCKsendl;InOrderInitial(&L);start=clock();Heapsort(&L);finish=clock();cout堆排序 无序(double)(finish-start)/CLK_TCKsendl;/冒泡排序OrderInitial(&L); /out(&L);start=clock();bubble(&L);finish=clock()

36、;cout冒泡排序 有序(double)(finish-start)/CLK_TCKsendl;InOrderInitial(&L);start=clock();bubble(&L);finish=clock();cout冒泡排序 无序(double)(finish-start)/CLK_TCKsendl;/选择排序OrderInitial(&L); /out(&L);start=clock();choice(&L);finish=clock();cout选择排序 有序(double)(finish-start)/CLK_TCKsendl;InOrderInitial(&L);start=cl

37、ock();choice(&L);finish=clock();cout选择排序 无序(double)(finish-start)/CLK_TCKsendl;int main()int a;int item;SqList L; cout 1、顺序表的应用endl;cout*endl;cout 1.顺序存储的线性表5种排序算法endl;cout 2.删除线性表中所有值为item的数据元素endl;cout 3.性能测试endl;cout 0.退出endl;cout*endl;while(1)cout请选择:a;switch(a)case 0:return 0;case 1:InitialRand

38、om(&L);cout二路归并排序算法endl;Mergesort(&L);out(&L);cout快速排序算法endl;quicksort(&L,0,L.length-1);out(&L);cout堆排序算法endl;Heapsort(&L);out(&L);cout冒泡排序算法endl;bubble(&L);out(&L);cout选择排序算法endl;choice(&L);out(&L);break;case 2: Initial(&L); cout请输入item的值（整数）item; Delete(&L,item); break;case 3: Performance(); break

39、; 设计二的代码#include#include#include#includeusing namespace std;/这是单链表 typedef struct LNodeint data;struct LNode* next;LNode,*LinkList;/双向链表 typedef struct DuLNodeint data,freq;/freq是频率 struct DuLNode *prev,*next;/前后两个指针DuLNode,*DuLinkList;/矩阵结点 typedef struct MatrixNodeint row,column,data;/行 列 数值 struc

40、t MatrixNode *next;MatrixNode,*MatrixList;/建立链表 void Initial(LinkList &L)coutx;if(x=-1) break;p-next=new LNode;p=p-next;p-data=x;p-next=NULL; /判断元素是否在L中int not_in_L(int m,LinkList L) /元素在L中返回0，不再L中返回1 LNode*p;for(p=L-next;p!=NULL;p=p-next) if(m=p-data) /找到 return 0; return 1;/对L1操作，删除在L1中而不在L2中的元素 v

41、oid del(LinkList L1,LinkList L2)LNode *p=L1;while(p-next!=NULL) if(not_in_L(p-next-data,L2)/在L1不在L2里 p-next=p-next-next;/删除元素 else p=p-next; /输出链表void output(LinkList L)LNode *p;p=L-next;while(p)coutdatanext; coutendl;void fun1() LinkList A,B; cout创建链表A:endl; Initial(A);cout创建链表B:endl;Initial(B);del(A,B);del(B,A);cout删除元素后A,B链表为:next=NULL;L-data=1; LNode *p=L; cout请输入猴子总数nn;cout请输入出局猴子报的数m(mn)m;/建立循环链表，开始时，头结点指向其自身/没有头节点，建立头指针和尾指针 for