数据结构课程设计报告new

《数据结构课程设计报告new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构课程设计》报告书2012/2013第1学期专业班级：_________学号：_________学生姓名：_________计算机信息工程学院一．课程认识数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能

2、力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：n了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；n初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；n提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工者所应具备的科学的工作方法和作风。二．课题选择1、内部排序演示（一）问题描述及分析：设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔

3、排序、堆排序算法进行比较；(2)待排序的元素的关键字为整数。其中的数据要用伪随机产生程序产生(如10000个)，至少用5组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。（gettickcount()）（二）数据结构描述：本程序采用顺序表结构，具体结构定义如下：typedefstruct{ElemType*elem;intlength;}SqList;（三）主要算法流程描述：1.主要函数流程1.voidaddlist(SqList&L)//初始化顺序表2.voidrandom(SqList&L)//随机数产生程序3.voi

4、dmemory(SqList&M,SqList&L)//记录L，使每个排序算法都用一组相同的随机数4.voidBubbleSort(SqList&L)//冒泡排序5.voidInsertSort(SqList&L)//直接插入排序6.voidSelectSort(SqList&L)//选择排序7.intPartition(SqList&L,intlow,inthigh)//快速排序8.voidQSort(SqList&L,intlow,inthigh)//对顺序表的子序列作快速排序9.voidShellSort(SqList&L)//希尔排序10.vo

5、idHeapAdjust(SqList&L,ints,intm)//调整L.elem[s]的关键字，使L.elem[s…..m]成为一个大根堆11.voidHeapSort(SqList&L)//对顺序表L进行堆排序12.voidmain()主函数2.主要代码及程序说明#include"iostream"#include"stdio.h"#include"stdlib.h"#include"string.h"#include"time.h"usingnamespacestd;#defineLIST_INIT_SIZE50000intbj1=0,yd1=

6、0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n;//yd，bj为记录关键字比较和移动的次数typedefstruct{intkey;}ElemType;typedefstruct{ElemType*elem;intlength;}SqList;voidaddlist(SqList&L)//初始化顺序表{a:printf("请输入你要输入的个数:");scanf("%d",&n);if(n>50000){printf("超出范围重新输入!!!");gotoa;}L.ele

7、m=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(0);}voidrandom(SqList&L)//随机数产生程序{L.length=0;staticboolfirst=true;if(first){srand(time(0));first=false;}//使输入相同个数时每次产生的随机数不同for(inti=1;i30000)gotoa;++L.length;}

8、}voidmemory(SqList&M,SqList&L)//记录L，使每个排序算法都用一组