查找和排序-数据结构

《查找和排序-数据结构》由会员分享，可在线阅读，更多相关《查找和排序-数据结构（10页珍藏版）》请在装配图网上搜索。

1、 数据结构实验报告姓名：否学号：班级：计科1001题目：查找和排序完成日期：2012.6.8成绩：一，需求分析：1： 程序分析1） 本程序主要完成了对一堆数字的查找和排序，其中查找只有一种方法，而排序有多种方法，主要是冒泡排序，快速插入排序，希尔排序，堆排序。并且通过执行的次数可以判断其中的排序效率。2） 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“菜单”，由用户根据自己的需求在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算提示以及信息输入显示在其后。当你不想输入信息时，你可以按G结束该次操作，2：程序执行命令包括： 菜单 A: 冒泡排序 B: 折半查找 C: 直接排

2、序 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 D,i=1,2,.n基本操作：maopao();初始条件：存在一个数据组，其顺序随意。操作结果：将所给的一组数据排序，并且输出其执行的次数。insertsort()初始条件：存在一个数据组，其顺序随意。操作结果：将所给的一组数据排序，并且输出其执行的次数。shellsort()初始条件：存在一个

3、数据组，其顺序随意。操作结果：将所给的一组数据排序，并且输出其执行的次数。qsort()初始条件：存在一个数据组，其顺序随意。操作结果：将所给的一组数据排序，并且输出其执行的次数。output()初始条件：存在一个数据组，其顺序随意。操作结果：数超出排序前的顺序。search_Bin()初始条件：存在一个数据组，其顺序随意。操作结果：折半查找某个特定元素。ADT Set2. 本程序包含二个大模块：1） 主程序模块：void main() 初始化；do 接受命令； 处理命令；while(命令=“退出”)；2)输出模块三，详细设计#include #include#includetypedef s

4、tructint key;int data;SElemType;typedef structSElemType *elem21;int length;SSTable; static int sum=0; /快速排序int partition(SSTable *L, int low, int high) int pivotkey;L-elem0=L-elemlow;sum+; pivotkey=L-elemlow-data; while(lowhigh) while(lowelemhigh-data=pivotkey) high-; L-elemlow=L-elemhigh;sum+; whil

5、e(lowelemlow-dataelemhigh=L-elemlow; sum+; L-elemlow=L-elem0;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; ilength-1; +i

6、)if(st-elemi-data elemi-dk-data)st-elem0=st-elemi;sum+;for(j=i-dk; j0 & st-elemj-data st-elem0-data; j-=dk)st-elemj+dk = st-elemj;sum+; st-elemj+dk=st-elem0;sum+;void shellsort(SSTable *st, int dlta, int t) int k,j;sum=0;for(k=0;kt;k+) shellinsert( st, dltak); printf(希尔排序的结果是：n); for (j=1; jlength;

7、j+) printf(%d ,st-elemj-data); printf(n希尔排序的次数是：%dn,sum); printf(n);/直接排序void insertsort(SSTable st) int i,j;sum=0;for(i=2; idata data)st.elem0=st.elemi; sum+;for(j=i-1; st.elemj-data st.elem0-data; -j)st.elemj+1 = st.elemj;sum+; st.elemj+1=st.elem0;sum+; printf(直接排序的结果是：n); for (j=1;jdata); printf(

8、n直接排序的次数是：%dn,sum);/折半查找int search_Bin(SSTable st,int k) int low,high,mid;low=1; high=st.length;while(lowkey=k) return mid;if(st.elemmid-keyk) high=mid-1;else low=mid+1;return 0;/冒泡排序void maopao(SSTable st) int i=0,j=0;sum=0;for (j=1;jst.length;j+)for(i=1;idata st.elemi+1-data)int temp; temp=st.elem

9、i-data;sum+; st.elemi-data=st.elemi+1-data;sum+; st.elemi+1-data=temp;sum+; printf(冒泡排序的结果是：n); for (j=1;jdata); printf(n冒泡排序的次数是：%dn,sum);/输出函数void output(SSTable st) int j;printf(输出的结果是：n); for (j=1;jdata); printf(n);void main() int i=0; int text21=0,11,4,55,72,38,64,87,22,9,97,99,10,15,49,86,48,1

10、9,56,14,59; int T3=5,3,1; char c; SElemType S21; SSTable ST; SSTable *temp; for(i=0;i21;i+) /text.length() Si.key=i+1; Si.data=texti; ST.elemi=&Si; ST.length=21; temp=&ST; /text.length(); printf( 菜单 n); printf(A: 冒泡排序n); printf(B: 折半查找n); printf(C: 直接排序n); printf(D: 希尔排序n); printf(E: 快速排序n); printf(

11、F: 排序之前n); printf(G: 退出程序n); do printf( 请选择:); c=getchar();/scanf(%c,&c);fflush(stdin); for(i=0;idata); break; caseC: insertsort(ST); break; caseD: shellsort(temp, T, 3); break; caseE: int j; sum=0; qsort(temp, 1,ST.length-1); printf(快速排序的结果是：n); for (j=1;jdata); printf(n快速排序的次数是：%dn,sum); break; ca

12、seF: output(ST); break; while(c!=G);creatUDG(G) DFSTraverse(G) BFSTraverse(G)函数的调用关系图反映了程序的层次结构： main() maopao(); qsort() output() insertsort() search_Bin() shellsort() partition() shellinsert()四 调试分析：1：在执行希尔排序和快速排序时出现问题，结果查出是因为它们是二介调用，要用指针的指针才可以使这改变。2：在冒泡排序中使用了数组指针，开始使用错误，最后仔细排查，得出正确结果。五 测试结果：1)菜单项：2)排序及其效率输出：2)输出查找及退出：