1、 数据结构数据结构课程设计课程设计 报告书报告书 2012/2013 第第 1 学期学期 专业班级：_ 学 号：_ 学生姓名：_ 计算机信息工程学院 一一课程认识课程认识 数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及 它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一 门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智 能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处 理。 通过课程设计可以提高学生的思维能力， 促进学生的综合
2、应用能力和专业素质的提高。 通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工者所应具备的科 学的工作方法和作风。 二二课题选择课题选择 1、内部排序演示内部排序演示 （一）（一）问题描述及分析：问题描述及分析： 设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 (1) 对起泡排序、直接排序、简单选择排序、快速排序、希尔
3、排序、堆排序算法进行比较； (2) 待排序的元素的关键字为整数。其中的数据要用伪随机产生程序产生(如 10000 个)，至少 用 5 组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总 比较。 （gettickcount()） （二）（二）数据结构描述：数据结构描述： 本程序采用顺序表结构，具体结构定义如下： typedef struct ElemType *elem; int length; SqList; （三）（三）主要算法流程描述：主要算法流程描述： 1.主要函数流程主要函数流程 1.void addlist(SqList #define LIST_INIT_S
4、IZE 50000 int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n;/ yd，bj 为记录关键字比较和移动的次数 typedef struct int key; ElemType; typedef struct ElemType *elem; int length; SqList; void addlist(SqList scanf(“%d“, if(n50000) printf(“超出范围重新输入!n“); goto a; L.elem=(ElemType*)malloc(LIST_I
5、NIT_SIZE*sizeof(ElemType); if(!L.elem)exit(0); void random(SqList static bool first=true; if(first) srand(time(0); first=false; /使输入相同个数时每次产生的随机数不同 for(int i=1;i30000) goto a; +L.length; void memory(SqList for(int i=1;i1;-i) L.elem1=L.elemi; yd6+=3; HeapAdjust(L,1,i-1); void main() SqList L,M; int a
6、; M.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!M.elem)exit(0); a: coutcoef=c; s-exp=e; r-next=s; r=s; printf(“coef:“); scanf(“%d“, printf(“exp: “); scanf(“%d“, r-next=NULL; return(h); void print(node *p) /输出函数，打印出一元多项式 while(p-next!=NULL) p=p-next; printf(“ %d*x%d“,p-coef,p-exp); void polyadd(node *ha, node *hb)/一元多项式相加函数，用于将两个多项 式相加，然后将和多项式存放在多项式 ha
