查找和排序—数据结构.docVIP

数据结构实验报告 姓名：否 学号：2010468302 班级：计科1001 题目：查找和排序 完成日期：2012.6.8 成绩： 一，需求分析： 1： 程序分析 1） 本程序主要完成了对一堆数字的查找和排序，其中查找只有一种方法，而排序有多种方法，主要是冒泡排序，快速插入排序，希尔排序，堆排序。并且通过执行的次数可以判断其中的排序效率。 2） 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“菜单”，由用户根据自己的需求在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算提示以及信息输入显示在其后。当你不想输入信息时，你可以按G结束该次操作， 2：程序执行命令包括： 菜单 A: 冒泡排序 B: 折半查找 C: 直接排序 D: 希尔排序 E: 快速排序 F: 排序之前 G: 退出程序 3：测试数据： 依次输入：A F C F D F E F B 二 概要设计： 1：顺序存储结构的抽象数据类型定义为： ADT List{ 数据对象：D= {ai | ai ?ElemSet, i= 1,2,...n ,n=0} 数据关系：R1={ai-1,ai|ai-1,ai D,i=1,2,...n} 基本操作： maopao(); 初始条件：存在一个数据组，其顺序随意。 操作结果：将所给的一组数据排序，并且输出其执行的次数。 insertsort() 初始条件：存在一个数据组，其顺序随意。 操作结果：将所给的一组数据排序，并且输出其执行的次数。 shellsort() 初始条件：存在一个数据组，其顺序随意。 操作结果：将所给的一组数据排序，并且输出其执行的次数。 qsort() 初始条件：存在一个数据组，其顺序随意。 操作结果：将所给的一组数据排序，并且输出其执行的次数。 output() 初始条件：存在一个数据组，其顺序随意。 操作结果：数超出排序前的顺序。 search_Bin() 初始条件：存在一个数据组，其顺序随意。 操作结果：折半查找某个特定元素。 }ADT Set 本程序包含二个大模块： 主程序模块： void main() { 初始化； do{ 接受命令； 处理命令； }while(命令=“退出”)； } 2)输出模块 三，详细设计 #include stdio.h #includestdlib.h #includemalloc.h typedef struct{ int key; int data; }SElemType; typedef struct{ SElemType *elem[21]; int length; }SSTable; static int sum=0; //快速排序 int partition(SSTable *L, int low, int high) { int pivotkey; L-elem[0]=L-elem[low];sum++; pivotkey=L-elem[low]-data; while(lowhigh){ while((lowhigh)(L-elem[high]-data=pivotkey)) high--; L-elem[low]=L-elem[high];sum++; while((lowhigh)(L-elem[low]-data=pivotkey)) low++; L-elem[high]=L-elem[low]; sum++; } L-elem[low]=L-elem[0];sum++; return low; } void qsort(SSTable *L,int low,int high) { int pivotloc; if(lowhigh){ pivotloc=partition(L,low,high); qsort(L,low,pivotloc-1); qsort(L,pivotloc+1,high); } } //希尔排序 void shellinsert(SSTable *st,int dk) { int i,j; for(i=dk+1; i=st-length-1; ++i) if(st-elem[i]-data st-elem[i-dk]-data) { st-elem[0]=st-elem[i];sum++;