《2022年数据结构查找、排序的应用实验知识 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构查找、排序的应用实验知识 .pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、淮海工学院计算机科学系实 验 报 告 书课 程 名 ：数据结构题目： 查找、排序的应用实验班级： 学号： 姓名： 评语：成绩：指导教师：批阅时间：年月日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 18 页 - - - - - - - - - 数据结构实验报告- 1 - 排序、查找的应用实验报告要求1 目的与要求 : 1）查找、 排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。2）本次实验前， 要求同学
2、完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构；3）利用 C或 C+ 语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单机制实现实验程序的交互运行）和实用性；4） 本次与第七次实验已合二为一，实验结果在机房现场验收和评分，希望同学们认真对待，并于 2009 年 12 月 20 日按时提交本次实验报告（含电子和纸质报告），任何同学不得拖延。5）如果验收时间紧张，不能再正课时间完成者，由老师择机决定另行通知专门验收时间。凡无故不主动或拖延验收者，均按照不及格处理。5）认真书写实验报告（包括程序清单及相关实验数据与完整运行结果），并于按时提交。2 实验内容或题目题目
3、：对数据序列（查找表）：55 ，13，23，72，109，67，2，78,13 分别实现如下操作：1)顺序查找；2)分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序；3)对排好序的纪录序列表进行折半查找；4)利用原纪录序列建立一颗二叉排序树，并在其上实现特定关键字值结点的查找；5)按照 “除留余数法” 哈希构造函数和线性探测再散列的冲突处理方法创建表长为m=11的哈希表；6)实现 5）创建哈希表上的查找。7） 分别简单选择排序、堆排序、链式基数排序算法对数据序列进行排序，并显示排序结果。3 实验步骤与源程序 #include #include #include #define LI
4、ST_SIZE 20 #define TRUE 1 #define FALSE 0 #define SUCCESS 1 #define UNSUCCESS -1 #define MAX 100 #define RADIX 10 #define KEY_SIZE 6 #define LIST_SIZE 20 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 - - - - - - - - - 数据结构实验报告- 2 - typedef char KeyType; t
5、ypedef int OtherType; typedef int PVectorRADIX; typedef struct KeyType keyKEY_SIZE; int type; int next; RecordType1; typedef struct RecordType1 RLIST_SIZE+1; int length; int keynum; SLinkList; typedef struct KeyType key; OtherType other_data; RecordType; typedef struct RecordType rLIST_SIZE+1; int l
6、ength; RecordList; / 二叉排序树的创建与查找#define ENDKEY 0 typedef struct node KeyType key ; /*关键字的值 */ struct node *lchild,*rchild;/*左右指针 */ BSTNode, *BSTree; /* 哈希表的创建 */ typedef struct int key; int flag;/falg=1时表示有关键字，=0 时表示没有关键字Elemtype; typedef struct Elemtype *elem;/动态分配的哈希表的首地址 int sizeindex;/hashsizes
7、izeindex为当前容量 int count;/当前数据元素个数HashTable; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 18 页 - - - - - - - - - 数据结构实验报告- 3 - / 顺序查找void SeqSearch(RecordList l, KeyType k) /* 在顺序表 l 中顺序查找其关键字等于k 的元素，若找到，则函数值为该元素在表中的位置，否则为 0*/ int i; l.r0.key=k; i=l.length; wh
8、ile (l.ri.key!=k) i-; if (i=1) printf(该元素 k 所在的位置是 :); printf(%d,i); else printf(该元素不存在 ); / 直接插入排序void InsSort(RecordType r, int length) int i,j; for (i=2; i=length; i+) r0=ri; /*将待插入记录存放到监视哨r0中*/ j=i-1; while (r0.key rj.key ) /* 寻找插入位置 */ rj+1= rj; j=j-1; rj+1=r0; /*将待插入记录插入到已排序的序列中*/ /* InsSort *
9、/ / 简单选择排序void SelectSort(RecordType r,int length) int n,k;int x; n=length; for(int i=1;i=n-1;+i) k=i; for(int j=i+1;j=n;+j) if(rj.keyrk.key)k=j; if(k!=i) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - - - - - - 数据结构实验报告- 4 - x=ri.key ;ri.key =rk.k
10、ey ;rk.key =x; /* SelectSort */ / 冒泡排序void BubbleSort(RecordType r,int length) int x,i,n,change,j; n=length;change=TRUE; for(i=1;i=n-1&change;+i) change=FALSE; for(j=1;jrj+1.key) x=rj.key; rj=rj+1; rj+1.key=x; change=TRUE; / 快速排序int Partition(RecordList &L,int low,int high) /Partition() sub-function
11、 int pivotkey; L.r0=L.rlow; pivotkey=L.rlow.key; while(lowhigh) while(low=pivotkey) -high; L.rlow=L.rhigh; while(lowhigh&L.rlow.key=pivotkey) +low; L.rhigh=L.rlow; L.rlow=L.r0; return(low); void Qsort(RecordList &L,int low,int high) int pivotloc; if(lowhigh) pivotloc=Partition(L,low,high); Qsort(L,l
12、ow,pivotloc-1); Qsort(L,pivotloc+1,high); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 18 页 - - - - - - - - - 数据结构实验报告- 5 - void QuickSort(RecordList &L) Qsort(L,1,L.length); / 对排好的序进行折半查找算法void BinSrch(RecordList l,KeyType k) int low,high,mid; low=1; high=l.
13、length; while(low=high) mid=(low+high)/2; if (k=l.rmid.key) printf(找到该元素，其位置为%d,mid); break; /* 找到待查元素 */ else if (khigh) printf(没有找到该元素); void InsertBST(BSTree *bst, KeyType key) BSTree s; if (*bst = NULL)/*递归结束条件 */ s=(BSTree)malloc(sizeof(BSTNode);/*申请新的结点s*/ s- key=key; s-lchild=NULL; s-rchild=N
14、ULL; *bst=s; else if (key key) InsertBST(&(*bst)-lchild), key);/*将 s 插入左子树 */ else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 18 页 - - - - - - - - - 数据结构实验报告- 6 - if (key (*bst)-key) InsertBST(&(*bst)-rchild), key); /*将 s 插入右子树 */ void CreateBST(BSTree *bst
15、) KeyType key; *bst=NULL; scanf(%d, &key); while (key!=ENDKEY) /*ENDKEY为自定义常量 */ InsertBST(bst, key); scanf(%d, &key); void PreOrder(BSTree root) if (root!=NULL) printf(%d ,root-key); /*输出结点 */ PreOrder(root-lchild); /*先序遍历左子树*/ PreOrder(root-rchild); /*先序遍历右子树*/ BSTree SearchBST(BSTree bst, KeyType
16、 key) if (!bst) return NULL; else if (bst-key = key) return bst;/*查找成功 */ else if (bst-key key) return SearchBST(bst-lchild, key);/*在左子树继续查找*/ else return SearchBST(bst-rchild, key);/*在右子树继续查找*/ BSTNode * DelBST(BSTree t, KeyType k) BSTNode *p, *f,*s ,*q; p=t; f=NULL; while(p) 名师资料总结 - - -精品资料欢迎下载 -
17、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 18 页 - - - - - - - - - 数据结构实验报告- 7 - if(p-key=k ) break; f=p; if(p-keyk) p=p-lchild; else p=p-rchild; if(p=NULL) return t; if(p-lchild=NULL) if(f=NULL) t=p-rchild; else if(f-lchild=p) f-lchild=p-rchild ; else f-rchild=p-rchild ; free(p)
18、; else q=p; s=p-lchild; while(s-rchild) q=s; s=s-rchild; if(q=p) q-lchild=s-lchild ; else q-rchild=s-lchild; p-key=s-key; free(s); return t; /*DelBST*/ / 建立哈希表int CreatHashTable(HashTable &H,int m) int i,keys,p,len; H.elem = (Elemtype *)malloc(MAX * sizeof(Elemtype); H.sizeindex = MAX;/初始存储容量 H.coun
19、t=0; printf(请输入该组关键字的个数:); scanf(%d,&m); printf(请输入表长len:); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 18 页 - - - - - - - - - 数据结构实验报告- 8 - scanf(%d,&len); H.sizeindex = len; for(i = 0;i m;+i) H.elemi.flag = 0; printf(请输入该组关键字：); for(i = 0;i m;+i) scanf(%d,
20、&keys); p = keys %m; while(H.elemp.flag = 1)/处理冲突 int d=1; p = (p +d)% m; d+; H.elemp.key = keys; H.elemp.flag = 1; H.count+; for(int j=H.count;jlen;j+) H.elemj.key=0; printf(哈希表创建完毕！n); printf(下标关键字 n); for(i = 0;ilen;i+) printf(%d ,i); printf(%d,H.elemi.key); printf(n); return SUCCESS; void Search
21、HashTable(HashTable H) int keys,p; printf(请输入您要查找的关键字：n); scanf(%d,&keys); for(int i=0;i-1&pH.count) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 18 页 - - - - - - - - - 数据结构实验报告- 9 - printf(查找成功！ n); printf(该关键字在哈希表中的下标为：%d n,p); else printf(查找失败，表中无此关键字！n);
22、/ 堆排序/ 筛选void sift(RecordType r,int k,int m) int t; t=rk.key; int x=rk.key; int i=k; int j=2*i; int finished=FALSE; while(j=m&!finished) if(jm&rj.key=rj.key)finished=TRUE; else ri=rj; i=j; j=2*i; /* 继续筛选 */ ri.key=t; /* sift */ / 建堆void crt_heap(RecordType r,int length) int n=length; for(int i=n/2;i
23、=1;-i) sift(r,i,n); / 堆排序void HeapSort(RecordType r,int length) crt_heap(r,length); int n=length; int b; for(int i=n;i=2;-i) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 18 页 - - - - - - - - - 数据结构实验报告- 10 - b=r1.key; r1.key=ri.key; ri.key=b; sift(r,1,i-1);
24、/ 链式基数排序void Distribute (SLinkList *L,int i,PVector head,PVector tail) int j,p; for(j=0;jR0.next; while(p) j=L-Rp.keyi; if(headj=0) headj=p; else L-Rtailj.next=p; tailj=p; p=L-Rp.next; void Collect(SLinkList *L,PVector head,PVector tail) int j=0,t; while(headj=0) +j; L-R0.next=headj;t=tailj; while(j
25、RADIX-1) +j; while(jRt.next=headj;t=tailj; L-Rt.next=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 18 页 - - - - - - - - - 数据结构实验报告- 11 - void RadixSort(SLinkList *L ) int n,i,d,j,x,k; printf(输入链表长度 :); scanf(%d,&(L-length); printf(输入最大位数 :); scanf(%d,&(L-k
26、eynum); PVector head,tail; n=L-length; for(i=0;iRi.next=i+1; L-Rn.next=0; printf(输入各记录 :); for(j=1;jlength;j+) scanf(%d,&(L-Rj.type); for(i=1;ilength;i+) x=L-Ri.type; for(j=0;jkeynum;j+) L-Ri.keyj=x%10; x=x/10; d=L-keynum; for(i=0;ikeynum;+i) Distribute(L,i,head,tail); Collect(L,head,tail); k=0; pri
27、ntf(排序后为 :); while(L-Rk.next) printf(%d ,L-RL-Rk.next.type); k=L-Rk.next; void main() SLinkList M; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 18 页 - - - - - - - - - 数据结构实验报告- 12 - int i,j,select,a,flag=1,m=0; RecordType r20; BSTree bst,result,T; RecordList
28、 L,Q; int length,k,low; printf(1 进行顺序查找 t2 进行直接排序 t3 进行冒泡排序 n4 进行快速排序 t5 对排好序的纪录序列表进行折半查找 n6 利用原纪录序列建立一颗二叉排序树，并在其上实现特定关键字值结点的查找 n7 建立哈希表，并对其进行查找n); printf(8 简单选择排序9 堆排序10 链式基数排序n); printf(0退出 ); int symbol(1); while(flag) printf(n请选择： ); scanf(%d,&a); if(a=10)symbol=0; while(symbol) printf(请输入待排序记录的
29、长度:); /交互创建纪录表scanf(%d,&length); printf(请输入各元素：); for(i=1;i=length;i+) fflush(stdin); scanf(%d,&j); ri.key = j; printf(你输入的各元素为：); for(i=1;i=length;i+) printf(%d ,ri.key); printf(n); symbol=0; switch(a) case 1: printf(请输入你要查找的元素k：); fflush(stdin); scanf(%d,&k); L.length=length; for(i=1;i=L.length;i+
30、) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 18 页 - - - - - - - - - 数据结构实验报告- 13 - L.ri=ri; SeqSearch(L,k); printf(n); break; case 2: InsSort(r,length); printf(按直接排序后各元素为：); for(i=1;i=length;i+) printf(%d ,ri.key); printf(n);break; case 3: BubbleSort(r,len
31、gth); printf(按冒泡排序后各元素为：); for(i=1;i=length;i+) printf(%d ,ri.key); printf(n); break; case 4: L.length=length; for(i=1;i=L.length;i+) L.ri=ri; QuickSort(L); printf(进行快速排序后各元素为: ); for(i=1;i=L.length;i+) printf(%d ,L.ri.key); printf(n); break; case 5: InsSort(r,length); L.length=length; for(i=1;ikey)
32、; else printf(未找到 !n); result = DelBST(T,k); /getch(); break; case 7: HashTable H; CreatHashTable(H,m); SearchHashTable(H); break; case 0: flag=0; case 8: SelectSort(r,length); printf(按简单选择排序后各元素为：); for(i=1;i=length;i+) printf(%d ,ri.key); printf(n); break; case 9: crt_heap(r,length); HeapSort(r,le
33、ngth); printf(按简单选择排序后各元素为：); for(i=1;i=length;i+) printf(%d ,ri.key); printf(n); break; case 10: RadixSort(&M); symbol=1; break; default: printf(输入错误 ); break; 4 测试数据与实验结果（可以抓图粘贴）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 18 页 - - - - - - - - - 数据结构实验报告-
34、15 - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 18 页 - - - - - - - - - 数据结构实验报告- 16 - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 18 页 - - - - - - - - - 数据结构实验报告- 17 - 5 结果分析与实验体会通过本次的数据结构实验，我掌握了多种基本查找、和排序的思想，以及实现他们的算法，对他们有了一个更加具体、深刻的认识，尤其当使用哈希排序时，很多时候会遇到冲突的情况，掌握了解决处理冲突的方法，例如线性探测再散列的冲突处理方法来创建哈希表解决实际问题。掌握了这一系列的方法，会为我们今后的继续学习带来很大的帮助。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 18 页 - - - - - - - - -