数据结构大作业报告.doc

数据结构课程设计课题名称 专业名称 学生姓名 学号+电话 指导教师 评分细则目 录评分细则2一、课题描述4二、需求分析42.1 4 2.2 -4 2.3 -4 三、概要设计4 3.1 结构分析43.2 函数4 3.2.1 malloc() 4 3.2.2 getchar()5 3.2.3 list_create()5 3.2.4 list_disp()5 3.2.5 list_sort()5四、详细设计54.1课题分析5 4.1.1选择 5 4.1.2 冒泡5 4.1.3 堆6 4.1.4 快速6 4.1.5 基数-6 4.1.6 希尔6 4.1.7 归并-64.2课题实现7五、测试数据及结果9六、调试分析及总结10一、课题描述将随机多个整数号数按顺序输出，即编写一个将输入数据从小到大输出的程序。二、需求分析本程序用C编写，完成单链表的生成。2.1输入的形式和输入值的范围： 输入一个数组，要求数组元素为n位整数。2.2 输出的形式： 输出一个按要求位数的数组，要求从小到大排列。2.3 程序所能达到的功能： 完成单链表的生成、顺序表的输出操作。三、概要设计3.1数据逻辑结构、存储结构分析。每两个相邻的数据进行比较，满足某一种条件就交换（大于或者小于），否则不交换，如n个数据比较（n-1）轮排序成功。本程序借助指针类型来实现链式存储结构。3.2程序包含的函数： 3.2.1malloc（） malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。void* 表示未确定类型的指针。 分配长度为num_bytes字节的内存块，如果分配成功则返回指向被分配内存的指针(此存储区中的初始值不确定)，否则返回空指针NULL。当内存不再使用时，应使用free()函数将内存块释放。3.2.2.getchar() getchar有一个int型的返回值.当程序调用getchar时.程序就等着用户按键.用户输入的字符被存放在键盘缓冲区中.直到用户按回车为止(回车字符也放在缓冲区中).当用户键入回车之后,getchar才开始从stdio流中每次读入一个字符.getchar函数的返回值是用户输入的第一个字符的ASCII码,如出错返回-1,且将用户输入的字符回显到屏幕.如用户在按回车之前输入了不止一个字符,其他字符会保留在键盘缓存区中,等待后续getchar调用读取.3.2.3 list_create（） 3.2.4 list_disp（）3.2.5 list_sort（）4、 详细设计4.1课题分析 由于本次课题要求输出给定位数的有序数组，所以有一下几种方法可选择：4.1.1选择排序 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。不稳定的排序方法。4.1.2冒泡排序 a.比较相邻的元素。如果第一个比第二个大，就交换他们两个。 b.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 c.针对所有的元素重复以上的步骤，除了最后一个。 d.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。4.1.3堆排序 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。4.1.4快速排序 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。是对冒泡排序法的一种改进。4.1.5基数排序 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。4.1.6希尔排序 希尔排序是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。它是一种非稳定排序算法。4.1.7归并排序 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。4.2课题实现 由于本次课题要求输入数据少，功能简洁，所以选择使用并不陌生而且简单的冒泡排序法，代码部分如下：#include #include #include #define OK 1 #define ERROR 0 typedef struct node int data; node *next; node,*LinkList; /node node55 = 2,4,5,7,1 ; node *list_create(int num) LinkList L,p,s; L = (LinkList)malloc(sizeof(node); if(!L) return ERROR; L-next = NULL; p = L; for(int i=0;idata); p-next = s; p = p-next; p-next = NULL; return L; /p-next = NULL; int list_disp(LinkList L) LinkList p; p = L-next; while(p!=NULL) printf(n%d,p-data); p = p-next; getchar(); return OK; int list_sort(LinkList L,int num) /LinkList p; LinkList p=L-next; int temp,i,j; for(i=0;inext; for( j=0;jdata p-next-data) temp = p-data; p-data = p-next-data; p-next-data = temp; p = p-next; / p = p-1;直接减不行，p是结构体指针，长度不是1 printf(n); list_disp(L); return OK; int main() int num=8; LinkList head; head = list_create(num); list_disp(head); list_sort(head,8); getchar(); return 0; 五、测试数据及结果 当输入6位数时： 3 6 9 1 4 7 屏幕截图： 当输入8位数时：7 6 9 1 6 3 2 6