实验五查找及排序

1、实验五 查找及排序实验课程名： 数据结构与算法一、实验目的及要求1、掌握查找的不同方法，并能用高级语言实现查找算法。2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法。3、掌握常用的排序方法，并能用高级语言实现排序算法。4、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。5、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、实验内容任务一：顺序表的顺序查找。 有序表的折半查找。完成下列程序，该程序实现高考成绩表（如下表所示）的顺序查找，在输出结果中显示查找成功与查找不成功信息。准考证号姓名各科成绩总分政治语文外语数学物理化学生物179328何芳芳8

2、58998100938047592179325陈红858688100929045586179326陆华78759080958837543179327张平82807898849640558179324赵小怡76859457776944502解答：（1）源代码：#include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.

3、h> / exit() #include<iostream.h> / cout,cin / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALS

4、E#define MAX_LENGTH 100#include<string.h> #include<ctype.h> #include<malloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #inc

5、lude<process.h> / exit() #include<iostream.h> / cout,cin / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布

6、尔类型,其值是TRUE或FALSE #define N 5 / 数据元素个数#define EQ(a,b) (a)=(b)#define LT(a,b) (a)<(b)#define LQ(a,b) (a)<=(b)typedef long KeyType; / 设关键字域为长整型 #define key number / 定义关键字为准考证号 struct ElemType / 数据元素类型(以教科书图9.1高考成绩为例) long number; / 准考证号，与关键字类型同 char name9; / 姓名(4个汉字加1个串结束标志) int politics; / 政治 i

7、nt Chinese; / 语文 int English; / 英语 int math; / 数学 int physics; / 物理 int chemistry; / 化学 int biology; / 生物 int total; / 总分 ;typedef struct ElemType *elem; / 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int length; / 表长度 SSTable;void Creat_Seq(SSTable &ST,ElemType r,int n) / 操作结果：由含n个数据元素的数组r构造静态顺序查找表ST int i; ST

8、.elem=(ElemType*)calloc(n+1,sizeof(ElemType); / 动态生成n+1个数据元素空间(0号单元不用) if(!ST.elem) exit(ERROR); for(i=1;i<=n;i+) ST.elemi=ri-1; / 将数组r的值依次赋给ST ST.length=n; void Ascend(SSTable &ST) / 重建静态查找表为按关键字非降序排序 int i,j,k; for(i=1;i<ST.length;i+) k=i; ST.elem0=ST.elemi; / 待比较值存0单元 for(j=i+1;j<=ST

9、.length;j+) if LT(ST.elemj.key,ST.elem0.key) k=j; ST.elem0=ST.elemj; if(k!=i) / 有更小的值则交换 ST.elemk=ST.elemi; ST.elemi=ST.elem0; void Creat_Ord(SSTable &ST,ElemType r,int n) / 操作结果：由含n个数据元素的数组r构造按关键字非降序查找表ST Creat_Seq(ST,r,n); / 建立无序的查找表ST Ascend(ST); / 将无序的查找表ST重建为按关键字非降序查找表 Status Destroy(SSTabl

10、e &ST) / 初始条件：静态查找表ST存在。操作结果：销毁表ST free(ST.elem); ST.elem=NULL; ST.length=0; return OK; int Search_Seq(SSTable ST,KeyType key) / 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则返回 / 该元素在表中的位置，否则返回0。算法9.1 int i; ST.elem0.key=key; / 哨兵 for(i=ST.length;!EQ(ST.elemi.key,key);-i); / 从后往前找 return i; / 找不到时，i为0 void Tr

11、averse(SSTable ST,void(*Visit)(ElemType) / 初始条件：静态查找表ST存在，Visit()是对元素操作的应用函数 / 操作结果：按顺序对ST的每个元素调用函数Visit()一次且仅一次 ElemType *p; int i; p=+ST.elem; / p指向第一个元素 for(i=1;i<=ST.length;i+) Visit(*p+); void print(ElemType c) / Traverse()调用的函数 printf("%-8ld%-8s%4d%5d%5d%5d%5d%5d%5d%5dn",c.number,

12、,c.politics, c.Chinese,c.English,c.math,c.physics,c.chemistry,c.biology,c.total); int main() ElemType rN=179328,"何芳芳",85,89,98,100,93,80,47, 179325,"陈红",85,86,88,100,92,90,45,179326,"陆华",78,75,90,80,95,88,37,179327,"张平",82,80,78,98,84,96,40,179324,"

13、赵小怡",76,85,94,57,77,69,44; / 数组不按关键字有序 SSTable st; int i; long s; for(i=0;i<N;i+) / 计算总分 ri.total=ri.politics+ri.Chinese+ri.English+ri.math+ri.physics+ ri.chemistry+ri.biology; Creat_Seq(st,r,N); / 由数组r产生顺序静态查找表st printf("准考证号 姓名 政治 语文 外语 数学 物理 化学 生物 总分n"); Traverse(st,print); / 按顺

14、序输出静态查找表st printf("请输入待查找人的考号: "); scanf("%ld",&s); i=Search_Seq(st,s); / 顺序查找 if(i) print(st.elemi); else printf("没找到n"); Destroy(st); return 0; （2）运行结果：（3） 运行结果分析：运用顺序结构完成查询。任务二：哈希表的开放定址法算法。在输出结果中显示查找成功与查找不成功信息。解答：（1）源代码：#include<string.h> #include<ctype.

15、h> #include<malloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.h> / exit() #include<iostream.h> / cout,c

16、in / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE#define EQ(a,b) (a)=(b)#define LT(a,b) (a)<(b)

17、#define LQ(a,b) (a)<=(b)#define N 11 / 数据元素个数#define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1 #define NULL_KEY 0 / 0为无记录标志 #define N 10 / 数据元素个数 typedef int KeyType; / 设关键字域为整型 struct ElemType / 数据元素类型 KeyType key; int ord; ;int hashsize=11,19,29,37; / 哈希表容量递增表，一个合适的素数序列 int m=0; / 哈希表表

18、长，全局变量 struct HashTable ElemType *elem; / 数据元素存储基址，动态分配数组 int count; / 当前数据元素个数 int sizeindex; / hashsizesizeindex为当前容量 ;void InitHashTable(HashTable &H) / 操作结果：构造一个空的哈希表 int i; H.count=0; / 当前元素个数为0 H.sizeindex=0; / 初始存储容量为hashsize0 m=hashsize0; H.elem=(ElemType*)malloc(m*sizeof(ElemType); if(!

19、H.elem) exit(OVERFLOW); / 存储分配失败 for(i=0;i<m;i+) H.elemi.key=NULL_KEY; / 未填记录的标志 void DestroyHashTable(HashTable &H) / 初始条件：哈希表H存在。操作结果：销毁哈希表H free(H.elem); H.elem=NULL; H.count=0; H.sizeindex=0; unsigned Hash(KeyType K) / 一个简单的哈希函数(m为表长，全局变量) return K%m; void collision(int &p,int d) / 线性

20、探测再散列 / 开放定址法处理冲突 p=(p+d)%m; Status SearchHash(HashTable H,KeyType K,int &p,int &c) / 在开放定址哈希表H中查找关键码为K的元素，若查找成功，以p指示待查数据 / 元素在表中位置，并返回SUCCESS；否则，以p指示插入位置，并返回UNSUCCESS / c用以计冲突次数，其初值置零，供建表插入时参考。算法9.17 p=Hash(K); / 求得哈希地址 while(H.elemp.key!=NULL_KEY&&!EQ(K,H.elemp.key) / 该位置中填有记录并且关键字

21、不相等 c+; if(c<m) collision(p,c); / 求得下一探查地址p else break; if EQ(K,H.elemp.key) return SUCCESS; / 查找成功，p返回待查数据元素位置 else return UNSUCCESS; / 查找不成功(H.elemp.key=NULL_KEY)，p返回的是插入位置 Status InsertHash(HashTable &,ElemType); / 对函数的声明 void RecreateHashTable(HashTable &H) / 重建哈希表 int i,count=H.count

22、; ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType); p=elem; printf("重建哈希表n"); for(i=0;i<m;i+) / 保存原有的数据到elem中 if(H.elem+i)->key!=NULL_KEY) / 该单元有数据 *p+=*(H.elem+i); H.count=0; H.sizeindex+; / 增大存储容量 m=hashsizeH.sizeindex; p=(ElemType*)realloc(H.elem,m*sizeof(ElemType); if(!

23、p) exit(OVERFLOW); / 存储分配失败 H.elem=p; for(i=0;i<m;i+) H.elemi.key=NULL_KEY; / 未填记录的标志(初始化) for(p=elem;p<elem+count;p+) / 将原有的数据按照新的表长插入到重建的哈希表中 InsertHash(H,*p); Status InsertHash(HashTable &H,ElemType e) / 查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK； / 若冲突次数过大，则重建哈希表，算法9.18 int c,p; c=0; if(SearchHash(

24、H,e.key,p,c) / 表中已有与e有相同关键字的元素 return DUPLICATE; else if(c<hashsizeH.sizeindex/2) / 冲突次数c未达到上限，(c的阀值可调) / 插入e H.elemp=e; +H.count; return OK; else RecreateHashTable(H); / 重建哈希表 return UNSUCCESS; void TraverseHash(HashTable H,void(*Vi)(int,ElemType) / 按哈希地址的顺序遍历哈希表 printf("哈希地址0%dn",m-1)

25、; for(int i=0;i<m;i+) if(H.elemi.key!=NULL_KEY) / 有数据 Vi(i,H.elemi); Status Find(HashTable H,KeyType K,int &p) / 在开放定址哈希表H中查找关键码为K的元素，若查找成功，以p指示待查数据 / 元素在表中位置，并返回SUCCESS；否则，返回UNSUCCESS int c=0; p=Hash(K); / 求得哈希地址 while(H.elemp.key!=NULL_KEY&&!EQ(K,H.elemp.key) / 该位置中填有记录并且关键字不相等 c+;

26、if(c<m) collision(p,c); / 求得下一探查地址p else return UNSUCCESS; / 查找不成功(H.elemp.key=NULL_KEY) if EQ(K,H.elemp.key) return SUCCESS; / 查找成功，p返回待查数据元素位置 else return UNSUCCESS; / 查找不成功(H.elemp.key=NULL_KEY) void print(int p,ElemType r) printf("address=%d (%d,%d)n",p,r.key,r.ord); int main() Elem

27、Type rN=17,1,60,2,29,3,38,4,1,5,2,6,3,7,4,8,60,9,13,10; HashTable h; int i,p; Status j; KeyType k; InitHashTable(h); for(i=0;i<N-1;i+) / 插入前N-1个记录 j=InsertHash(h,ri); if(j=DUPLICATE) printf("表中已有关键字为%d的记录，无法再插入记录(%d,%d)n",ri.key,ri.key,ri.ord); printf("按哈希地址的顺序遍历哈希表:n"); Trave

28、rseHash(h,print); printf("请输入待查找记录的关键字: "); scanf("%d",&k); j=Find(h,k,p); if(j=SUCCESS) print(p,h.elemp); else printf("没找到n"); j=InsertHash(h,ri); / 插入第N个记录 if(j=ERROR) / 重建哈希表 j=InsertHash(h,ri); / 重建哈希表后重新插入 printf("按哈希地址的顺序遍历重建后的哈希表:n"); TraverseHash(h

29、,print); printf("请输入待查找记录的关键字: "); scanf("%d",&k); j=Find(h,k,p); if(j=SUCCESS) print(p,h.elemp); else printf("没找到n"); DestroyHashTable(h); return 0; （2）运行结果：（3） 运行结果分析：运用哈希表开放定地址算法实现。任务三：各种插入排序算法的实现。解答：（1）源代码：#include<string.h> #include<ctype.h> #includ

30、e<malloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.h> / exit() #include<iostream.h> / cout,cin / 函数结果状态代码

31、 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE typedef int InfoType; / 定义其它数据项的类型 #define EQ(a,b) (a)=(b) #d

32、efine LT(a,b) (a)<(b) #define LQ(a,b) (a)<=(b) #define MAX_SIZE 20 / 一个用作示例的小顺序表的最大长度 typedef int KeyType; / 定义关键字类型为整型 struct RedType / 记录类型 KeyType key; / 关键字项 InfoType otherinfo; / 其它数据项，具体类型在主程中定义 ; struct SqList / 顺序表类型 RedType rMAX_SIZE+1; / r0闲置或用作哨兵单元 int length; / 顺序表长度 ; void InsertS

33、ort(SqList &L) / 对顺序表L作直接插入排序。 int i,j; for(i=2;i<=L.length;+i) if LT(L.ri.key,L.ri-1.key) / "<",需将L.ri插入有序子表 L.r0=L.ri; / 复制为哨兵 for(j=i-1;LT(L.r0.key,L.rj.key);-j) L.rj+1=L.rj; / 记录后移 L.rj+1=L.r0; / 插入到正确位置 void BInsertSort(SqList &L) / 对顺序表L作折半插入排序。 int i,j,m,low,high; for(

34、i=2;i<=L.length;+i) L.r0=L.ri; / 将L.ri暂存到L.r0 low=1; high=i-1; while(low<=high) / 在rlow.high中折半查找有序插入的位置 m=(low+high)/2; / 折半 if LT(L.r0.key,L.rm.key) high=m-1; / 插入点在低半区 else low=m+1; / 插入点在高半区 for(j=i-1;j>=high+1;-j) L.rj+1=L.rj; / 记录后移 L.rhigh+1=L.r0; / 插入 void P2_InsertSort(SqList &L) / 2_路插入排序 int i,j,first,final; RedType *d; d=(RedType*)malloc(L.length*sizeof(RedType); / 生成L.length个记录的临时空间 d0=L.r1; / 设L的第1个记录为d中排好序的记录(在位置0) first=final=0; / first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 for(i=2;i&