第一篇：数据结构课程设计-查找排序
查找及排序算法实现
一、实验目的
1、熟练掌握二叉排序树查找算法及C语言描述。
2、熟练掌握折半查找算法及C语言描述。
3、熟练掌握简单选择排序算法及C语言描述。
4、熟练掌握简单插入排序算法及C语言描述。
5、熟练掌握冒泡（起泡）排序算法及C语言描述。
6、了解各种查找及排序算法的优缺点、实用性及应用。
7、将理论与实际相结合，切实提高自己的逻辑能力和动手能力。
二、设计内容
1.折半查找算法
折半查找算法的思路：
初始状态：假设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值，初始时，令low=0,high=n-1,mid=(low+high)/2 让key与mid指向的记录比较
若key==r[mid].key，查找成功,算法结束；若key
起泡排序的思路：
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即L.r[1].key>L.r[2].key），则将两个记录交换之，然后比较【第二个记录和第三个记录】的关键字。以此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称做第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。一般地，第i躺起泡排序是从L.r[1]到L.r[n-i+1]以此比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程需进行k(1<=k 首先以一个元素为基准，从一个方向开始扫描，比如从左至右扫描，以a[0]为基准，接下来从a[0]...a[9] 中找出最小的元素，将其与a[0]交换，然后将基准位置右 移一位，重复上面的动作，比如，以a[1]为基准，找出a[1]至a[9]中最小的，将其与a[1]交换，一直进行到基准位置移到数组最后一个元素时排序结束（此时基准左边所有元素均递增有序，而基准为最后一个元素，故完成排序）。4.直接插入排序算法 直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的，记录数增1的有序表。 一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r[1...i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1....i].在自i-1起往前搜索的过程中，可以同时后移记录。 整个排序过程为进行n-1躺插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止 三、程序源代码 1.二叉排序树的创建、遍历和查找删除算法 #include void Insert(Tree &T,KeyType key){ if(!T){ T=new LNode;T->data=key;T->lchild=T->rchild=NULL;} else } { } if(key } int num;char c;while(scanf(“%d”,&num)){ } Insert(T,num);c=getchar();if(c=='n')return;void In_Order(Tree T)//中序遍历 { if(T){ In_Order(T->lchild);printf(“%d ”,T->data);} In_Order(T->rchild);} void Delete(Tree &p){ Tree q,s;if(!p->rchild){ q = p;p=p->lchild;free(q);} else if(!p->lchild){ } q = p;p=p->rchild;free(q); else { } q = p;s = p->lchild;while(s->rchild){ } q = s;s = s->rchild;p->data = s->data;if(q!=p)q->rchild = s->lchild;else q->lchild = s->lchild;free(s);} void DelNode(Tree &T,KeyType key){ } if(!T){ printf(“n该结点不存在n”);return;} else { } if(key == T->data)Delete(T);else if(key < T->data)DelNode(T->lchild, key);else DelNode(T->rchild,key);Tree Search(Tree T,KeyType key)//二叉排序树查找 { if(!T){ } printf(“该结点不存在”);return 0;else if(key == T->data)return T;else if(key < T->data) return(Search(T->lchild, key));else return(Search(T->rchild, key));} int main()//主函数 { Tree T,p;T=NULL;KeyType x; printf(“请输入二叉树各结点：n”); CreatTree(T); printf(“中序遍历为：n”);In_Order(T);printf(“n请输入要查找和删除的结点：n”);scanf(“%d”,&x);p=Search(T, x);if(p){ } DelNode(T, x);printf(“中序遍历为：n”);In_Order(T); } 2、冒泡排序和折半查找算法 #include int BubbleSort(int c[]){ int i,t,j;for(i=0;i<9;i++){ } for(j=0;j<9-i;j++){ } if(c[j]>c[j+1]){ } t=c[j];c[j]=c[j+1];c[j+1]=t; printf(“n您所输入的数字的升序排列是:nn”);for(i=0;i<10;i++){ printf(“%d”,c[i]);printf(“ ”);} return 1;} //折半查找 int BinarySearch(int b[]){ } int t,mid;int i=0;int j=9;printf(“nn请输入您要查找的数字：”);scanf(“%d”, &t);while(i<=j){ mid=i+(j-i)/2; } return 1;if(t==b[mid]){ printf(“n您要查找的数字的排列位置是：%dn”,mid+1);break;} else if(t int main(int argc,char *argv[]){ int a[10];printf(“请您输入数据:nn”);for(int i=0;i<10;i++){ scanf(“%d”,&a[i]); } } BubbleSort(a);BinarySearch(a);return 0; 3、简单选择排序和简单插入排序算法 #include int i,j,min,p,key,k; for(i=0;i { key=0; min=a[i]; } for(j=i;j if(a[j] if(key==1){a[p]=a[i]; a[i]=min;} for(k=0;k printf(“%d ”,a[k]);printf(“n”); return 1;} int InserSort(int*a,int n){ int i,j,k;for(i=2;i<=n;i++){ a[0]=a[i];for(j=1;j { if(a[j]>a[i]){for(k=i;k>j;k--) a[k]=a[k-1]; a[k]=a[0]; } } break;} } for(j=1;j<=n;j++){ } printf(“%d ”,a[j]);printf(“n”);return 1;int main(){ int a[80],i,n,b;printf(“请输入关键字的个数：”);scanf(“%d”,&n);printf(“排序类型：n”);printf(“1.选择排序n”);printf(“2.插入排序n”);printf(“请选择：”);scanf(“%d”,&b);switch(b){ case 1: printf(“请输入关键字：n”);for(i=0;i SelectionSort(a,n); return 1; break; case 2: printf(“请输入关键字：n”); for(i=1;i<=n;i++){ scanf(“%d”,&a[i]);} printf(“插入排序的流程以及结果：n”); InserSort(a,n);return 1; } break;}while(a!=0); 四、实验运行结果 1.二叉排序树的创建、遍历和查找删除算法 2、冒泡排序和折半查找算法 3、简单选择排序和简单插入排序算法 七、心得体会 通过本次的数据结构课程设计报告，掌握了查找和排序的几种基本排序算法，了解了他们各自的特点和优缺点，完成了对于他们C语言的描述和实际应用，对他们有了一个更加具体、深刻的认识，同时也锻炼了我们的逻辑思维能力和动手实践能力，使我们受益匪浅，给我们今后的计算机专业课程学习带来很大的帮助。 东华理工大学 东华理工大学 课程设计报告 课程设计题目： 综合排序的设计 学生姓名：何杨 班 级：1223202 专 业：信息与计算科学 指导教师：郭树蕻 2014年 12 月 13 日 东华理工大学 目录 摘要..............................................................2 一、题目的内容及要求-----------------4 二、需求分析------------------------------4 三、概要设计------------------------------5 四、四种排序源代码详细设计--------5 五、程序输出的结果-------------------10 六、运行结果及分析-------------------12 七、收获及体会-------------------------13 八、参考文献-----------------------------1 东华理工大学 摘 要 数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。 关键字：数据结构；算法比较；比较次数；时间复杂度 东华理工大学 一、题目的内容及要求 排序综合 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求： (1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 (2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 (3)如果采用4种或4种以上的方法者，可适当加分。 二、需求分析 2.1 问题描述 此次的任务要求是输入20000个以上的随机整数，对这些数进行多种方法进行排序。（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。 约束：程序可由用户自行设定排序数的个数，但排序数具体值需要由计算机生成，然后用三种以上的排序方法对随机数组进行排序，每一种排序方法执行后需统计出数据移动次数以判断排序方法的对比随机数组的执行优劣性。另：用户自行算出每一种排序方法的时间复杂度与空间复杂度。 2.2 基本要求 2.2.1输入的形式和输入值的范围； 设定的随机数据的范围为20000以上，用户自定义随机数的个数n，随机数的数据类型均为整形。 2.2.2输出的形式； 程序是以一个完整的有序数组来进行输出。 2.2.3程序所达到的功能： 将一个无序数组进行排序随机生成20000以上个随机整数，对这些数进行多种方法进行排序。分别采用以下方法实现上述问题求解（可采用的方法有简单排序、希尔排序、冒泡排序、快速排序这四种排序方法）。 东华理工大学 三、概要设计 3.1可排序表的抽象数据类型定义： typedef int KeyType;//关键字为整型 typedef int OtherType;//关键字为整型 typedef struct { KeyType key;//关键字为KeyType型 OtherType other_data;}RecordType;//定义一个RecordType型结构体，存放关键字 void quicksort(RecordType a[],int left,int right)//快速排序 void bubbleSort(RecordType a[],int length)//冒泡排序 void shellSort(RecordType a[],int n)//希尔排序 void BinSort(RecordType r[], int length)//折半插入排序 void main()//主函数运行入口 四、四种排序源代码详细设计： 4.1快速排序模块： void quicksort(RecordType a[],int left,int right){ RecordType t;int i,j,temp; if(left>right) return; temp=a[left].key; i=left; j=right; while(i!=j) { while(a[j].key>=temp && i j--; while(a[i].key<=temp && i 东华理工大学 i++; if(i { t=a[i]; a[i]=a[j]; a[j]=t; } } a[left] = a[i]; a[i].key = temp; quicksort(a,left,i-1);//继续处理左边的，这是一个递归的过程 quicksort(a,i+1,right);//继续处理右边的，这是一个递归的过程 } /* 快速排序算法 */ 4.2冒泡排序模块： //此处是一次冒泡排序过程，在主函数中会通过循环调用此冒泡函数过程 void bubbleSort(RecordType a[],int length){ int i,temp; for(i=1;i { if(a[i].key>a[i+1].key) { temp = a[i].key; a[i].key=a[i+1].key; a[i+1].key=temp; } } }/* 冒泡排序算法 */ 4.3希尔排序模块： void shellSort(RecordType a[],int n){ int i, j, temp; int gap = 0; while(gap<=n)//根据待排序的个数生成合适的步长，gap是步长 { gap = gap * 3 + 1; 东华理工大学 } } while(gap > 0){ for(i = gap;i < n;i++){ j = igap; } a[j+gap+1].key = temp;} gap =(gap-1)/ 3;} 4.4希尔折半插入排序模块： /*折半插入排序法*/ void BinSort(RecordType r[], int length)/*对记录数组r进行折半插入排序，length为数组的长度*/ { int i,j;RecordType x;int low,high,mid;for(i=2;i<=length;++i) { x= r[i]; low=1;high=i-1; while(low<=high) /* 确定插入位置*/ { mid=(low+high)/ 2; if(x.key< r[mid].key) high=mid-1; else low=mid+1; } for(j=i-1;j>= low;--j) r[j+1]= r[j]; /* 记录依次向后移动 */ r[low]=x; /* 插入记录 */ } }/*BinSort*/ 东华理工大学 4.5主函数模块： void main(){ int n,i,j,t; char b; bool q=false; RecordType a[40000]; while(1) { printf(“nn”);printf(“ ************** 综 合 排 序*****************************nn”); printf(“ *********************菜 单***************************nn”);printf(“ * ========= * n”); printf(“ * 1.读 取 待排序长度 * n”); printf(“ * 2.产生随机数并输出 * n”); printf(“ * 3.采用快速排序法排序 * n”); printf(“ * 4.采用冒泡排序法排序 * n”); printf(“ * 5.采用希尔排序法排序 * n”); printf(“ * 6.采用折半插入排序法排序 * n”); printf(“ * 7.输 出 * n”);printf(“ * 0.退 出 系 统 * n”);printf(“ *------------------------* n”); printf(“ ”); b = getch(); switch(b) { case '1': printf(“%cn”,b); printf(“请输入待排序记录的长度：”); scanf(“%d”,&n);break; 东华理工大学 case '2': printf(“%cn”,b); srand((unsigned)time(NULL)); printf(“下面随机生成%d个数字存储在数组中n”,n); for(i=1;i<=n;i++) { a[i].key = rand()%20000; printf(“%dt”,a[i].key); if(i%100==0) printf(“n”); } printf(“n”); break; case '3': printf(“%cn”,b); printf(“n -----------------快速排序结束------------------- nn”); quicksort(a,1,n); q=true;break; case '4': printf(“%cn”,b); for(i=0;i { bubbleSort(a,n-i); } printf(“n -----------------冒泡排序结束------------------- nn”); q=true;break; case '5': printf(“%cn”,b); printf(“n -----------------希尔排序结束------------------- nn”); shellSort(a,n); q=true;break; case '6': printf(“%cn”,b); BinSort(a,n); printf(“n -----------------折半插入排序结束-------------------nn”); q=true;break; case '7': printf(“%cn”,b); 东华理工大学 if(q) { printf(“n -----------------排序后输出------------------- n”); for(i=1;i<=n;i++) { printf(“%dt”,a[i].key); if(i%100==0) printf(“n”); } } else { printf(“n * ========= * n”); printf(“ * 您未对待排序数据排序 * n”); printf(“ * 请重新选择排序的序号 * n”); printf(“ *------------------------* n”); } break; case '0': printf(“%cn”,b); printf(“n 感谢使用综合排序程序n 按任意键退出......n”); return;break; default:printf(“nn”); } } } 五、程序输出的结果： 5.1输入和输出： (1)主函数运行的输出结果： 东华理工大学 (2)选择1，读取待排序长度（这里以20000为例）： (3)选择2，产生随机数并输出： (4)选择3，采用快速排序法排序： 东华理工大学 （选择4、5、6的其他排序法的输出雷同，此处就不再重复）(5)选择7，输出排序结果： 六、运行结果及分析 6.1各算法的比较方法 1.稳定性比较 折半插入排序、冒泡排序是稳定的希尔排序、快速排序是不稳定的 2.时间复杂性比较 折半插入排序、冒泡排序的时间复杂性为O(n2)其它非线形排序的时间复杂性为O(nlog2n)3.辅助空间的比较 东华理工大学 线形排序的辅助空间为O(n),其它排序的辅助空间为O(1);4.其它比较 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。 反而在这种情况下，快速排序反而慢了。 当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。 当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。 七、收获及体会 根据四种排序法的基础理论实际性模仿和编写算法程序，很是困难，算法是程序的灵魂，数据结构确是算法的基础，但是不断的实践也是一种进步的好途径。这次课程设计主要是对基础知识的灵活应用，这就让我进一步提高了对数结构知识的巩固。这次设计的完成，困难是少不了的，还有很多其它的难题让我都不知道所措，但是通过努力最终解决他们让我体会到成就感，更重要的是我的能力在实践中得到了提升和优化，特别是对常用的排序算法的应用，这对我以后从事软件应用程序开发是有很大的帮助的。这次课程设计的心得体会通过实习我的收获如下 1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。 2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。 3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。 4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。 2、写程序的过程中要考虑周到，严密。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。 5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。我通过课程设计建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验，树立团队协作精神。同时，充分弥补了课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助从全局角度把握 东华理工大学 课程体系，并且可以将理论与实际联系。在课程设计的过程中不仅仅是书本上的知识，这便促使我去查阅更多的课外资料来充实自己的内容，同时学会在面对困难时要耐心得分析它细心得解决它以及通过合作更完美得深入了解剖析它以便得到提高。细心、耐心、团结、求知，是我这次课程设计最大的收获。同时要感谢老师这几天的悉心教导。 八、参考文献 [1] 啊哈磊，《啊哈！算法》，人民邮电出版社，2014-6-1 [2] 刘艳飞，《C语言范例开发大全》清华大学出版社，2010 [3] 严蔚敏，吴伟民。数据结构。北京：清华大学出版社，2001 电 子 科 技 大 学 实 验 报 告 学生姓名：XXX 学 号：20*** 指导教师：刘峤 实验地点：信软机房306 实验时间：2014/6/20 一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—排序与查找 三、实验学时：4 四、实验原理： 快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、J，排序开始的时候I：=1，J：=N 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）确定该区间的中点位置：mid=（low+high）/2 min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置 （2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间： A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1; B)如果R[mid].key C)如果R[mid].key=a，则查找成功。 （3）下一次查找针对新的查找区间，重复步骤（1）和（2） （4）在查找过程中，low逐步增加，high逐步减少，如果high 五、实验目的： 本实验通过实现快速排序和折半查找算法，使学生理解如何实现快速查找和排序的基本算法思想。通过练习，加强对算法的理解，提高编程能力。 六、实验内容： （1）实现数据序列的输入; （2）实现快速排序算法,并对输入的序列排序后输出； （3）实现折半查找算法,并在步骤(2)排序后的序列上,进行任意地 查找,并输出查询结果。 七、实验器材（设备、元器件）： 八、数据结构及程序 #include #define MAX_LEN 100 void Sort(int *data,int left,int right){ int i,j,temp; i=left; j=right; temp=data[left]; if(left>right) return; while(i!=j){ while(data[j]>=temp&&j>i) j--; if(j>i) data[i++]=data[j]; while(data[i]<=temp&&j>i) i++; if(j>i) data[j--]=data[i]; } data[i]=temp; Sort(data,left,i-1);PC机一台，装有C/C++语言集成开发环境。 Sort(data,i+1,right);} int Search(int *data,int start,int end,int key,int num){ int result; int p =(start + end)/ 2; if(data[p] == key&&start<=end){ result = p; num++; if(data[p] > key) result = Search(data, start, p, key,num); else result = Search(data, p + 1, end, key,num); return result; } else if(num==0&&start>end){ result =-1; printf(“n 404 NO FOUNDn”); return result; } else if(num!=0&&start>end){ result=-1; if(num==1) printf(“nFounded number only one”); else printf(“nFounded number more than one”); return result; } else if(result!=-1){ if(data[p] > key) result = Search(data, start, p-1, key, num); else result = Search(data, p + 1, end, key, num); return result; } else { result=-1; return result; } } void loadFile(int *data,char *filename,int n){ int i; FILE *pfile=NULL; pfile=fopen(filename,“r”); if(!pfile){ printf(“Open file failn”); exit(0); } else printf(“Open file success!n”); for(i = 0;i < n;i++) fscanf(pfile , “%d ”,&data[i]);} int main(int argc, const char * argv[]){ int input=1,data[MAX_LEN],num=0,key=1,i,cmd; char filename[100]; printf(“Choose Mode :n 1.Input Mode 2.File Moden”); scanf(“%d”,&cmd); if(cmd==1){ printf(“Input data :(Enter 0 to detemine)n”); while(input!=0){ printf(“Enter the %d data :”,num+1); scanf(“%d”,&input); if(input!=0){ data[num]=input; num++; } } } else{ printf(“nInput the address of the file: ”); scanf(“%s”,filename); printf(“nInput the number of elem: ”); scanf(“%d”,&num); loadFile(data,filename,--num); } Sort(data, 0, num); printf(“nSort result: ”); for(i=1;i<=num;i++) printf(“%d ”,data[i]); printf(“nn”); while(key!=0){ printf(“nInput a key to search :(Enter 0 to detemine)”); scanf(“%d”,&key); if(key!=0) Search(data, 0, num, key, 0); } return 0;} 九、程序运行结果： 1.打开程序： 2.尝试手动输入模式： 3.搜索已存在数： 4.搜索不存在数： 5.尝试文件读入模式并搜索 实验成功。 十、实验结论： 使用好的排序与查找算法对于程序的运行效率至关重要，一个好的算法，适合的算法能使计算机对数据的处理事半功倍，而选用错误的算法，不但可能事倍功半，还有可能造成不稳定因素。 快速排序的时间复杂度为n（log2n）,是排序算法中最为快速的一种，但是不稳定，对基本有序的序列效率较差。 二分查找算法在查找算法中，速度快，效率高，但是要求数据要有序。 十一、总结及心得体会： 当空间充足，对稳定性要求不高的情况，排序算法宜使用快速排序。 快速排序和二分查找配合，可以以较高的效率查找目标元素。 编号： 139 数据结构与算法课程设计 说明书 动态查找表 学 院： 海洋信息工程学院 专 业： 计算机科学与技术 学生姓名： 学 号： 指导教师： 2015年月 26 日 动态查找表 学生姓名：银杰 指导老师：王晓莹 摘 要 本课程设计说明书系统地阐述了我使用C语言在Code::Blocks软件编写的动态查找表程序的整个过程，编写的环境是win7 64位操作系统。根据题目要求，编写动态查找表使用二叉排序树，即二叉链表作为存储结构。该程序具有建立数据功能、具有数据查找功能、具有数据插入功能、具有数据删除功能等基本功能操作。 关键词：动态查找表，Code::Blocks软件，win7 64位操作系统，C# dynamic lookup table Author :yinjie Tutor :Wangxiaoying Abstract This course design specification system to explain the whole process of using C language in Code:: Blocks software written in the dynamic look-up table program, the preparation of the environment is win7 64 bit operating system.According to the topic request, the preparation of the dynamic look-up table using the two fork sort tree, that is, the two binary list as the storage structure.The program has the function of building data, data searching, data insertion, data deletion and so on.Key words:dynamic lookup table, Code::Blocks software,win7 64 bit operating system，C # 目 录 引言.........................................................................................................................................................................1 查找的基本概念.................................................................................................................................................1 小结.....................................................................................................................................................................1 题目.....................................................................................................................................................................1 第1章 程序的构图设计.....................................................................................................................................2 1.1动态查询表：...............................................................................................................................................2 1.2程序功能流程图：.......................................................................................................................................2(1)、主函数模块............................................................................................................................................2(2)、二叉排序树的生成................................................................................................................................3(3)、二叉排序树的查找模块........................................................................................................................4(4)、二叉排序树的插入模块........................................................................................................................4(5)、二叉排序树删除连接模块....................................................................................................................5(6)、二叉排序树的删除模块........................................................................................................................5(7)、二叉排序树的遍历模块........................................................................................................................6 第2章 详细设计的程序.....................................................................................................................................6 各函数模块.........................................................................................................................................................6(1)主函数模块................................................................................................................................................6(2)二叉排序树的生成模块............................................................................................................................8(3)二叉排序树的查找模块............................................................................................................................8(4)二叉排序树的插入模块............................................................................................................................9(5)多态查找表删除模块..............................................................................................................................10(6)二叉排序树的中序遍历模块..................................................................................................................12 第3章 程序测试和运行.....................................................................................................................................12 3.1 程序测试....................................................................................................................................................12 3.2 程序运行....................................................................................................................................................13 1、主界面 ...................................................................................................................................................13 2、建立二叉排序树模块界面.....................................................................................................................13 3、二叉排序树查找模块界面.....................................................................................................................14 4、二叉排序树插入模块界面.....................................................................................................................14 5、二叉排序树删除模块界面 ...................................................................................................................14 6、退出程序的界面.....................................................................................................................................14 总 结.....................................................................................................................................................................15 程序完成情况...................................................................................................................................................15 有待改进之处...................................................................................................................................................15 课程设计期间的收获.......................................................................................................................................15 附录源代码如下...................................................................................................................................................17 桂林电子科技大学课程设计说明书 引言 查找的基本概念 查找又称为检索，就是从一个数据元素集合中找出某个特定的数据元素。查找是数据处理中最为常用的一种操作，查找算法的优劣对整个软件系统的效率影响很大，尤其当所涉及的数据量较大时，更是如此。在一个数据集合中进行查找操作可选用的方法与该数据元素集合的存储结构有很大关系。 查找是根据某个给定的值，在数据元素构成的集合中确定是否在这样一个数据元素，它的关键字等于给定值的关键字。 要进行查找，必须明确要查找对象的特征，也就是要查找元素的关键值。如果在数据集合中能找到与给定值相等的关键字，则该关键字所属的数据元素就是所要查找的数据元素，此时称该查找成功；如果查遍了整个数据元素集合也未能找到与给定值相等的关键字，则称该查找失败。小结 当然对于这个说明书，我不可能做得至善至美，但是一些基本的格式内容还是符合要求的。首先，我对查找表进行一个简要的概述。然后，我就查找表进行了详细的分析，这是设计中很重要的一步。接下来，我把查找表中所有的设计简明清晰地展现出来，并把我在设计中遇到的问题和分析解决问题的办法做了分析。最后，在结论中，我对自己的课程设计做了总体的评价同时简述了我在这次课程设计中的收获和经验。 题目 选题十二：动态查找表 【问题描述】 利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。【任务要求】 算法输入：指定一组数据。 桂林电子科技大学课程设计说明书 算法输出：显示二叉排序树的中序遍历结果、查找成功与否的信息、插入和删除后的中序遍历结果(排序结果)。 算法要点：二叉排序树建立方法、动态查找方法,对树进行中序遍历。【测试数据】 自行设定，注意边界等特殊情况。 第1章 程序的构图设计 1.1动态查询表： 依照输入的一组数据{56,80,65,20}所得的二叉排序树如下（a）所示：当插入11的时候就如（b）所示。 562065801 156206580 （a） （b）1.2程序功能流程图： (1)、主函数模块 桂林电子科技大学课程设计说明书 开始打印输出动态表的6个功能选择栏do循环输入选择号hSwitch(h)执行对应函数模块程序退出结束 (2)、二叉排序树的生成 开始输入数据个数Xfor循环输入X个数据调用插入函数Insert二叉树建成结束 桂林电子科技大学课程设计说明书 (3)、二叉排序树的查找模块 开始二叉排序树是否为空否根结点关键字？key是大于递归返回在左子树查找递归返回等于小于在右子树查找查找失败查找成功结束 (4)、二叉排序树的插入模块 开始调用查询函数Search()是否查询成功否被插入结点*s为新的根结点是插入的节点根结点<被插结点*s为左孩子插入成功结束 >被插结点*s为右孩子 桂林电子科技大学课程设计说明书 (5)、二叉排序树删除连接模块 开始左右子树是否为空是While循环否向右走到尽头重接它的左右子树将被删结点的前驱s的内容直接替代该结点的内容被删除结点的左子树的右子树是否为空否重接*q的右子树是重接*q的左子树连接成功结束(6)、二叉排序树的删除模块 开始输入要删除的的数据是否存在关键字等于n的数据元素否调用删除的连接函数Delete()结束返回是找到关键字并删除 桂林电子科技大学课程设计说明书 (7)、二叉排序树的遍历模块 开始二叉树根是否为空否对左子树按中序遍历进行访问根结点对右子树按中序遍历进行遍历完成结束是递归调用 第2章 详细设计的程序 各函数模块 (1)主函数模块： 用主函数main()来实现。主要是通过设计一个do()函数并让主函数调用它来显示主菜单，让用户选择操作。在do()函数中，我应用了switch-case语句来进行选择，是个比较简单实现的模块。最后若选择“5”退出循环。否则继续循环。主要代码如下： int main(){ bitree T=NULL,p;ElemType e;int n;int h;char c; do{ printf(“********************************************************n”); 桂林电子科技大学课程设计说明书 printf(“* *n”); printf(“* 动态查找表 *n”); printf(“* 1.建立二叉排序树 *n”); printf(“* 2.二叉排序树查找元素 *n”); printf(“* 3.二叉排序树插入元素 *n”); printf(“* 4.二叉排序树删除元素 *n”); printf(“* 5.退出 *n”); printf(“* *n”); printf(“********************************************************n”); printf(“请输入你的选择: n”); scanf(“%d”,&h); switch(h) { case 1:Init(T);printf(“中序遍历二叉排序树: ”);Zhongxu(T);printf(“n”); break; case 2:printf(“请输入要查找的数据:n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) printf(“数据已经存在!n”); else { printf(“数据不存在!n”);} break; case 3:printf(“请输入要插入的数据:n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) printf(“已经存在!n”); else{Insert(T, e);printf(“成功插入!n”);printf(“中序遍历二叉排序树: ”);Zhongxu(T);printf(“n”);} break; case 4:printf(“请输入要删除的数据:n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) { Deletebit(T,n);printf(“已经成功删除!n”);printf(“中序遍历二叉排序 桂林电子科技大学课程设计说明书 树: ”);Zhongxu(T);printf(“n”);} else printf(“数据不存在!n”); break; case 5:printf(“退出！n”); break; default:printf(“选择错误，重新开始!n”); } } while(h!=5);}(2)二叉排序树的生成模块： 二叉排序树的生成，是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插到当前已经生成的二叉排序树中。主要代码如下： void Init(bitree &T)//构造一个动态查找表T { int x;int i;int n; ElemType e;printf(“请输入结点个数: ”);scanf(“%d”,&x); for(i=1;i<=x;i++) { printf(“第%d个结点数据值:”,i);scanf(“%d”,&n); e.key=n;Insert(T,e); } printf(“二叉排序树已经建立!n”);} (3)二叉排序树的查找模块： 二叉排序树的查找方法如下。当二叉排序树为空时，查找失败。 当二叉排序树根结点的关键字等于key时，查找成功。 桂林电子科技大学课程设计说明书 当二叉排序树根结点的关键字大于key时，从根结点的左子树中以同样方法进行查找。当二叉树根结点的关键字小于key时，从根结点的右子树以同样方法进行查找。显然，该过程是一个递归过程，下面给出这一算法的实现。 主要代码： bitree Search(bitree T,ElemType e,bitree f,bitree &p)//在二叉排序树中查找数据 { if(!T) { p=f; return NULL; }//查找不成功 else if(T->data.key==e.key) { p=T;return T; } //查找成功 else if(T->data.key>e.key) return Search(T->lchild,e,T,p); else return Search(T->rchild,e,T,p);}//在二叉排序树中查找数据(4)二叉排序树的插入模块： 若要将一个关键字值为key的结点t插到二叉排序树中，只需要使该结点插入后，二叉排序树中的元素依然按照原来的规律排列即可。二叉排序树的插入方法如下。 若二叉排序树是空树，则key称为二叉排序树的根。 若二叉排序树为非空，则将key与二叉排序树的根结点进行比较：如果key的值等于根结点的值，则停止插入；如果key的值小于根结点的值，则将key插到左子树；如果key的值大于根结点的值，则将key插到右子树中。主要代码如下： void Insert(bitree &T,ElemType e)//在二叉排序树中插入数据 桂林电子科技大学课程设计说明书 { bitree p,s; if(!Search(T,e,NULL,p))//查找不成功 { s=(bitree)malloc(sizeof(bitnode)); s->data=e;s->lchild=s->rchild=NULL; if(!p)T=s;//被插入结点*s为新的根结点 else if(e.key data.key) p->lchild=s;//被插结点*s为左孩子 else p->rchild=s;//被插结点*s为右孩子 } }(5)多态查找表删除模块： 从二叉排序树中删除一个结点，不能简单地把以该结点为根的子树都删除，只能删除掉该结点，并且还应该保证删除后所得到的二叉树依然满足二叉树的性质不变。也就是说，在二叉排序树中删除一个结点相当于删除有序序列中的一个结点。 假设要删除的结点为P，其双亲结点为F，同时假设结点P是结点F的左孩子（右孩子的情况类似）。删除操作首先要确定被删结点P是否在二叉排序树中。若不在，则不做任何操作；若在，分为以下三种情况讨论。若P为叶子结点，可直接将其删除。 若结点P只有左子树，或只有右子树，则可将P的左子树或右子树直接改为其双亲结点F的左子树或右子树。 若P既有左子树，又有右子树此时有两种处理方法。 方法1：首先找到结点P在中序序列中的直接前驱结点S，然后用结点P的左子树改为F的左子树，而将P的右子树改为S的右子树。 方法2：首先找到结点P在中序序列中的直接前驱结点s，然后用结点s的值替代结点p的值，再将结点s删除，原结点s的左子树改为s的双亲结点q的右子树。主要代码如下： 桂林电子科技大学课程设计说明书 void Delete(bitree &p)//从二叉排序树中删除结点p，并重接它的左或右子树 { bitree q,s; if(!p->rchild)//右子树空，只需重接它的左子树 { q=p;p=p->lchild;free(q);q=NULL; } else if(!p->lchild)//左子树空，只需重接它的右子树 { q=p;p=p->rchild;free(q);q=NULL; } else{//左右子树均不空 q=p;s=p->lchild; while(s->rchild)//向右走到尽头 { q=s;s=s->rchild; } p->data=s->data;//将被删结点的前驱s的内容直接替代该结点的内容 if(q!=p)//若被删除结点的左子树的右子树不为空 q->rchild=s->lchild;//重接*q的右子树 else q->lchild=s->lchild;//重接*q的左子树 free(s);s=NULL; } }//删除结点 void Deletebit(bitree &T,int n)//删除二叉排序树中的数据 { if(!T)return;//不存在关键字等于n的数据元素 桂林电子科技大学课程设计说明书 else{ if(T->data.key==n)return(Delete(T));//找到关键字等于n的数据元素并删除它 else if(T->data.key>n)Deletebit(T->lchild,n);//继续在左子树中删除 else Deletebit(T->rchild,n);//继续在右子树中删除 } } (6)二叉排序树的中序遍历模块： 中序遍历二叉树定义：若二叉树根为空，则返回；否则，中序遍历左子树；访问根结点；中序遍历右子树。主要代码如下： void Zhongxu(bitree T)//中序遍历 { if(T!=NULL) { Zhongxu(T->lchild); printf(“%d ”,T->data.key); Zhongxu(T->rchild); } } 第3章 程序测试和运行 3.1 程序测试 程序测试是程序质量保证的主要活动之一，在程序编写的过程中，在各个阶段都有可能存在错误和缺陷。通过测试是可以发现程序设计中存在的种种问题，并可以及时改正。避免在程序运行时才出现不必要的错误。测试是质量保证一个临界和决定惩罚，它提供对程序说明、设计和编码的最终评审。是发现程序缺陷和错误的有力手段。根据系统设计目标和功能，对系统进行测试。 桂林电子科技大学课程设计说明书 1、功能性 （1）程序实现的主要功能，包括查询，插入，删除等。 （2）题目要求的输入输出字段，以及题目要求的输入限制。 2、可靠性 程序正确实现了对动态查找表的查询、插入、删除等各种功能。 3、易用性 现有程序实现了如下易用性： （1）查询，插入，删除，操作相关提示信息的一致性，可理解性 （2）输入限制的正确性 （3）输入限制提示信息的正确性，可理解性，一致性 （4）界面排版简洁完整 3.2 程序运行 1、主界面 ： 2、建立二叉排序树模块界面 ： 桂林电子科技大学课程设计说明书 3、二叉排序树查找模块界面 ： 4、二叉排序树插入模块界面 ： 5、二叉排序树删除模块界面 ： 6、退出程序的界面 ： 桂林电子科技大学课程设计说明书 总 结 程序完成情况 在编写程序写课程设计的时间里，虽然历经重重困难和挫折，但是在我自己的努力和老师的帮助下终于完成了动态查找表的设计。尽管该程序在功能和性能上可能还有一些缺陷，但是我已经完成了课程设计的任务和目标，达到了题目基本要求，成功完成了算法与数据结构课程设计。有待改进之处 有待改进： 1、我在编写程序的时候，用的是C++格式去保存编译的，用了C语言来编写，但是有一些C++的形式，当我用C来新建保存的时候却出现问题。所以程序我是用C++来新建保存的。 2、流程图画的不是很规范表准，在一些逻辑表达上不够简洁清晰。课程设计期间的收获 在完成此次的课程设计的过程中，我跨越了传统方式下的教与学的体制束缚，桂林电子科技大学课程设计说明书 通过自己的思考和设计，培养了自学能力和动手能力。并且由原先的被动的接受知识转换为主动的寻求知识，这可以说是学习方法上的一个很大的突破。在以往的传统的学习模式下，我们可能会记住很多的书本知识，但是通过课程设计，我们学会了如何将学到的知识转化为自己的东西，学会了怎么更好的处理知识和实践相结合的问题。 通过这次课程设计，我认识到数据结构与算法是计算机科学的基础课程，是我们学习的核心课程。我对数据结构和算法又有了新的认识。数据结构的研究不仅涉及到计算机软件，而且和计算机硬件的研究也有着密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便使查找和存取数据元素更为方便。可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一个核心内容，是从事计算机科学研究及其应用的人必须掌握的重要内容。 这次的课程设计有效的培养了我们独立思考的能力，提高了我们的动手操作水平。在具体设计中，我们巩固了上学期所学的数据结构与算法的理论知识，进一步提高了自己的编程能力。这也是课程设计的目的所在。通过编程实践，不仅开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力，更充分锻炼了我们的编程能力。 在这次课程设计中我也知道了的编程能力不强，有很多程序与算法是借鉴别人的，我想只要我有自己写程序，并且结合他人的程序算法，把程序完成，那我还是学习到东西了的。 在课程设计中我体会到：一个好的程序应该是一个高内聚低耦合的程序。而要做出一个好的程序则应该通过对算法与其数据结构的时间复杂度和空间复杂度进行实现与改进。然而，实际上很难做到十全十美，原因是各要求有时相互制约，要节约算法的执行时间往往要以牺牲更多的存储空间为代价：而为了节省存储空间又可能要以更多的时间为代价。因此，只能根据具体情况有所侧重：如果程序的使用次数较少，则应该力求算法简单易懂；如果程序反复多次使用，则应该尽可能选用快速算法或者设置为内联函数；如果解决问题的数据量极大，但是机器的内存空间不是很充足，则在编写算法时应该考虑如何节省空间。 学习了《数据结构与算法》这门课，我们在编写程序时就应该注意到所编写程序的时间复杂度和空间复杂度，以及是否运用了良好的算法，而不是只是象以前编写程序时单纯使用C++的知识。我们要充分考虑程序的性能，从而编写出更好的程序。 桂林电子科技大学课程设计说明书 在设计报告的写作过程中我也学到了做任何事情都要有的心态，首先我明白了做学问要一丝不苟，对于出现的任何问题都不要轻视，要通过正确的途径去解决，在做事情的过程中要有耐心和毅力，不要一遇到困难就打退堂鼓，只要坚持下去就可以找到思路去解决问题的，在遇到问题时，有必要向老师和同学请教，合作沟通的意义是巨大的。 在这次课程设计中，我认识到了自己的不足之处同时我也收获了很多知识和经验，在今后的学习中，我一定勤于思考，并灵活运用所学知识，多进行编程实践。在总结反思和编程训练中，不断提升自己的编程能力。相信在我的努力下，我的程序设计水平一定会不断提高。 参考文献 [1]数据结构与算法/汪沁，奚李峰主编.-北京：清华大学出版社，2012.9（第8章 查找） [2]百度文库>专业资料>IT/计算机>计算机软件及应用>动态查找表实验报告 http://wenku.baidu.com/link?url=crizbdK6WO86YXeSJWwkHNdXpaxUDkRJnoShcVDJqBfGO03Cbk6LAdVwBYHxE82kYHkuIjC1HFCiOrSiEWJXOOspWGIo3PNSDjbeY1jHbJu 附录源代码如下： 数据结构与算法的课程设计1.cpp 实验题9.1 设计一个程序exp9-1.cpp，输出在顺序表{3，6，2，10，1，8，5，7，4，9}中采用顺序方法找关键字5的过程。程序如下： //文件名:exp9-1.cpp #include KeyType key; //KeyType为关键字的数据类型 //其他数据 //定义表中最多记录个数 InfoType data; } NodeType;typedef NodeType SeqList[MAXL]; //顺序表类型 int SeqSearch(SeqList R,int n,KeyType k)//顺序查找算法 { int i=0; while(i { } printf(“%d ”,R[i].key);i++; //从表头往后找 if(i>=n)return-1; else } void main(){ SeqList R;{ } printf(“%d”,R[i].key);return i; } int n=10,i;KeyType k=5;int a[]={3,6,2,10,1,8,5,7,4,9};for(i=0;i //建立顺序表 printf(“关键字序列:”);for(i=0;i 截图如下： 实验题9.2 设计一个程序exp9-2.cpp，输出在顺序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找关键字9的过程。 程序如下： //文件名:exp9-2.cpp #include //定义表中最多记录个数 KeyType key; //KeyType为关键字的数据类型 InfoType data; //其他数据 } NodeType;typedef NodeType SeqList[MAXL]; //顺序表类型 int BinSearch(SeqList R,int n,KeyType k)//二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high) { mid=(low+high)/2;printf(“ 第%d 次 比 较 :在[%d,%d]R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid; if(R[mid].key>k) //继续在R[low..mid-1]中查找 high=mid-1; else low=mid+1; //继续在R[mid+1..high]中查找 } return-1;} void main(){ SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i //建立顺序表 R[i].key=a[i];printf(“关键字序列:”);for(i=0;i 比 较 元 素 中 } else printf(“元素%d的位置是%dn”,k,i);printf(“元素%d不在表中n”,k); 截图如下： 实验题9.3 设计一个程序exp9-3.cpp，输出在顺序表{8，14，6，9，10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分块查找法查找（每块的块长为5，共5块）关键字46的过程。 程序如下： //文件名:exp9-3.cpp #include KeyType key; //KeyType为关键字的数据类型 //定义表中最多记录个数 //定义索引表的最大长度 InfoType data; //其他数据 } NodeType;typedef NodeType SeqList[MAXL];typedef struct { KeyType key;int link; //KeyType为关键字的类型 //指向分块的起始下标 //顺序表类型 } IdxType;typedef IdxType IDX[MAXI]; //索引表类型 int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)//分块查找算法 { int low=0,high=m-1,mid,i,count1=0,count2=0;int b=n/m; //b为每块的记录个数 printf(“二分查找n”);while(low<=high) //在索引表中进行二分查找,找到的位置存放在low中 { mid=(low+high)/2;printf(“ 第%d 次 比 较 :在[%d,%d] 中 比 较 元R[%d]:%dn”,count1+1,low,high,mid,R[mid].key); if(I[mid].key>=k) high=mid-1; else low=mid+1; count1++; //累计在索引表中的比较次数 } if(low //在索引表中查找成功后,再在线性表中进行顺序查找 { printf(“比较%d次,在第%d块中查找元素%dn”,count1,low,k); i=I[low].link; printf(“顺序查找:n ”); while(i<=I[low].link+b-1 && R[i].key!=k) { i++;count2++; printf(“%d ”,R[i].key);} //count2累计在顺序表对应块中的比较次数 printf(“n”); printf(“比较%d次,在顺序表中查找元素%dn”,count2,k); if(i<=I[low].link+b-1) return i; else return-1;} 素 } return-1;void main(){ } SeqList R;KeyType k=46;IDX I;int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;for(i=0;i<25;i++)R[i].key=a[i]; //建立顺序表 I[0].key=14;I[0].link=0;I[1].key=34;I[1].link=4;I[2].key=66;I[2].link=10;I[3].key=85;I[3].link=15;I[4].key=100;I[4].link=20;if((i=IdxSearch(I,5,R,25,k))!=-1)else printf(“元素%d不在表中n”,k);printf(“元素%d的位置是%dn”,k,i);printf(“n”); 截图如下：第二篇：数据结构课程设计—综合排序
第三篇：数据结构实验报告-排序与查找
第四篇：数据结构课程设计：动态查找表
第五篇：数据结构查找实验报告
点击咨询 