第一篇：数据结构实验报告-静态查找表中的查找
数据结构实验
实验一 静态查找表中的查找
一、实验目的：
1、理解静态查找表的概念
2、掌握顺序查找和折半查找算法及其实现方法
3、理解顺序查找和折半查找的特点，学会分析算法的性能
二、实验内容：
1、按关键字从小到大顺序输入一组记录构造查找表，并且输出该查找表；
2、给定一个关键字值，对所构造的查找表分别进行顺序查找和折半查找，输出查找的结果以及查找过程中“比较”操作的执行次数。
三、实验要求：
1、查找表的长度、查找表中的记录和待查找的关键字值要从终端输入；
2、具体的输入和输出格式不限；
3、算法要具有较好的健壮性，对错误操作要做适当处理；
4、输出信息中要标明所采用的查找方法类型。
实验二 基于二叉排序树的查找
一、实验目的：
1、理解动态查找表和二叉排序树的概念
2、掌握二叉排序树的构造算法及其实现方法
3、掌握二叉排序树的查找算法及其实现方法
二、实验内容：
1、输入一组记录构造一颗二叉排序树，并且输出这棵二叉排序树的中序序列；
2、给定一个关键字值，对所构造的二叉排序树进行查找，并输出查找的结果。
三、实验要求：
1、二叉排序树中的记录和待查找的关键字值要从终端输入；
2、输入的记录格式为(整数，序号)，例如(3, 2)表示关键字值为3，输入序号为2的记录；
3、算法要具有较好的健壮性，对错误操作要做适当处理。
四、程序实现：
(1)实现顺序查找表和折半查找表：
#include
int key[MAX_LENGTH];
int length;}stable;
int seqserch(stable ST,int key,int &count){
int i;
for(i=ST.length;i>0;i--)
{
count++;
if(ST.key[i]==key)
return i;
}
return 0;}
int binserch(stable ST,int key,int &count){
int low=1,high=ST.length,mid;
while(low<=high)
{
count++;
mid=(low+high)/2;
if(ST.key[mid]==key)
return mid;
else if(key high=mid-1; else low=mid+1; } return 0;} main(){ stable ST1; int a,b,k,x,count1=0,count2=0,temp=0; ST1.length=0; printf(“请按从小到大的顺序输入查找表数据：(-1代表结束！)n”); for(a=0;a { scanf(“%d”,&temp); if(temp!=-1) { ST1.key[a]=temp; ST1.length++; } else break; } printf(“输入数据为：n”); for(b=0;b { printf(“%d ”,ST1.key[b]); } printf(“n请输入要查找的数据：”); scanf(“%d”,&k); a=seqserch(ST1,k,count1)+1; printf(“n顺序查找： 该数据的位置在第：%d个n”,a); printf(“查找次数为：%dnn”,count1-1); a=binserch(ST1,k,count2)+1; printf(“折半查找： 该数据的位置在第：%d个n”,a); printf(“查找次数为：%dn”,count2-1);}（2）二叉排序树的查找： #include typedef struct node { int data; int key; struct node *left,*right;}bitnode,*bittree; void serchbst(bittree T,bittree *F,bittree *C,int data){ while(T!=NULL) { if(T->data==data) { *C=T; break; } else if(data { *F=T; T=T->left; } else { *F=T; T=T->right; } } return 0;} int insertbst(bittree *T,int key,int data){ bittree F=NULL,C=NULL,s; serchbst(*T,&F,&C,data); if(C!=NULL)return 0; s=(bittree)malloc(sizeof(bitnode)); s->data=data; s->key=key; s->left=s->right=NULL; if(F==NULL)*T=s; else if(data F->left=s; else F->right=s; return 1;} void creatbst(bittree *T){ int key,data;*T=NULL; printf(“请输入数据以构造二叉排序树：(数据格式为:m n(-1000,-1000)代表结束)n”); scanf(“%d%d”,&key,&data); while(key!=-1000 || data!=-1000) { insertbst(T,key,data); scanf(“%d%d”,&key,&data); } } void midTraverse(bittree T){ if(T!=NULL) { midTraverse(T->left); printf(“(%d,%d)”,T->key,T->data); midTraverse(T->right); } } main(){ bittree T=NULL,C=NULL,F=NULL; int key,data,temp; creatbst(&T); printf(“此二叉树的中序序列为：”); midTraverse(T); printf(“n请输入要查找的关键字：”); scanf(“%d”,&data); serchbst(T,&F,&C,data); printf(“此关键字的数据为：%dn”,C->key);} 五、实现结果： (1)顺序查找和折半查找： (2)二叉树排序树查找： 六、实验之心得体会： （1）在这次实验中，我基本上掌握了顺序查找、折半查找和二叉排序树查找的基本思想和实现方法，让我体会到了写程序时，不仅要考虑是否能够调试出结果，还要考虑程序实现的效率，这是一个编程人员必须要具备的一项总要的素质。 （2）通过这次实验，让我体会到同样的数据在不同的查询方法下有着不同的查询效率，就拿实验一来说，用顺序查找法在12个数据中查找一个关键字需要的查找的次数为8次，但是，如果折半查找法却只要两次，由此可以看出，我们在查找时不仅要考虑查找的实现，还要考虑查找的效率和查找所用的时间。 （3）用二叉排序树查找效率也比较高，只要你输入相应的关键字，就可已找到所需要的数据，就我个人看来，用二叉排序树的效率要比顺序查找和折半查找的效率更高，查询的速度更快。 实验题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”); 截图如下： 《数据结构》 第八次实验报告 学生姓名 学生班级 学生学号 指导老师 重庆邮电大学计算机学院 计算机专业实验中心 一、实验内容 1)有序表的二分查找 建立有序表，然后进行二分查找 2)二叉排序树的查找 建立二叉排序树，然后查找 二、需求分析 二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x 三、概要设计 1、顺序查找，在顺序表R[0..n-1]中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1，具体的算法如下所示： int SeqSearch(SeqList R,int n,KeyType k){ } int i=0;while(i } if(i>=n){ } printf(“%d”,R[i].key);return i;return-1;else printf(“%d”,R[i].key);i++; 2、二分查找，在有序表R[0..n-1]中进行二分查找，成功时返回记录的位置，失败时返回-1，具体的算法如下： int BinSearch(SeqList R,int n,KeyType k){ } return-1;} 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;high=mid-1;low=mid+1;if(R[mid].key>k)else 四、详细设计 源代码： #include static int a[1024],count=0; void Find1(int low,int high,int x){ int mid;if(low<=high){ mid=(low+high)/2;count++;if(a[mid]>x)Find1(low,mid-1,x);else if(a[mid] void Find2(int low,int high,int x){ int mid;if(low<=high){ mid=(low+high)/2;count++;if(a[mid] 五、心得体会 通过这次在实现顺序和二分查找算法的过程中，让我对顺序和二分查找算法有了更多的了解。查找根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）的操作，应用十分广泛。顺序查找是一种最简单的查找方法。它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等,则查找成功；若扫描结束后,仍未找到关键字等于k的记录,则查找失败。二分查找也称为折半查找要求线性表中的结点必须己按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点。在学习过程中，善于发现，会找到更多的捷径。 六、附录 运行结果截图。 电 子 科 技 大 学 实 验 报 告 学生姓名：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第二篇：数据结构查找实验报告
第三篇：数据结构实验报告-查找算法
第四篇：数据结构实验报告-排序与查找
第五篇：数据结构课程设计：动态查找表
点击咨询 