第一篇：数据结构-实验8查找的算法
8.1 实现顺序查找的算法
一，实验目的
1.熟悉掌握各种查找方法，深刻理解各种查找算法及其执行的过程； 2.学会分析各种查找算法的性能。
二，实验内容
8.1 实现顺序查找的算法
编写一个程序，输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序查找法查找关键字5的结果。
8.2 实现折半查找算法
编写一个程序，输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查找关键字9的结果。要求：（1）用非递归方法；（2）用递归方法。8.3 实现二叉排序树的基本运算
编写一个程序实现二叉排序树的基本运算，并在此基础上完成如下功能：（1）由{4,9,0,1,8，6,3,5,2,7}创建一个二叉排序树bt；
（2）判断bt是否为一棵二叉排序树（提示：在遍历过程中检查是否符合二叉排序树定义）；
（3）采用非递归方法查找关键字为6的结点，并输出其查找路径（提示：查找过程中保留经过的结点信息，找到后顺序输出之）。8.4 实现哈希表的相关运算
编写一个程序，实现哈希表的相关运算，并在此基础上完成如下功能：
（1）建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0…12]，哈希函数为H(k)=key % 11，并采用线性探测法解决冲突。输出哈希表；（2）在上述哈希表中查找关键字为29的记录；
（3）在上述哈希表中删除关键字为77的记录，再将其插入，然后输出哈希表。要求：输出格式
哈希地址：0 1 2 ………..12 关键字值：……………………
三，源代码及结果截图
8.1 //实现顺序查找的算法 #include
//定义表中最多记录个数 typedef int KeyType;typedef int InfoType;typedef struct {
KeyType key;//KeyType为关键字的数据类型 InfoType data;//其他数据 } NodeType;
typedef NodeType SeqList[MAXL];
//顺序表类型 int Search(SeqList R,int n,KeyType k)//顺序查找算法
{ int i=0;while(i printf(“%d ”,R[i].key); i++; //从表头往后找 } if(i>=n) return-1;else { printf(“%d”,R[i].key); return i;} } void main(){ SeqList R;int n=10;KeyType k=5;InfoType a[]={3,6,2,10,1,8,5,7,4,9};int i;for(i=0;i //建立顺序表 R[i].key=a[i];printf(“查找结果：n”);if((i=Search(R,n,k))!=-1) printf(“n元素%d的位置是:%d”,k,i);else printf(“n元素%d不在表中n”,k);printf(“n”);} 8.2 //实现折半查找算法 #include //定义表中最多记录个数 typedef int KeyType;typedef char InfoType[10];typedef struct { KeyType key; //KeyType为关键字的数据类型 InfoType data; //其他数据 } NodeType;typedef NodeType SeqList[MAXL]; //顺序表类型 int BinSearch1(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;int BinSearch2(SeqList R,KeyType k,int low,int high,int count)//递归二分查找算法 { int mid;if(low<=high){ mid=(low+high)/2;第%d 次 查 找 : 在[%d,%d] 中 查 找 到 元 素printf(“R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid;else if(R[mid].key>k) //继续在R[low..mid-1]中查找 BinSearch2(R, k,low,mid-1,count);else BinSearch2(R, k,mid+1,high,count); //继续在R[mid+1..high]中查找 } else 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 //建立顺序表 printf(“用非递归方法:n”);if((i=BinSearch1(R,n,k))!=-1)printf(“元素%d的位置是%dn”,k,i);else printf(“元素%d不在表中n”,k);printf(“用递归方法:n”);if((i=BinSearch2(R,k,0,9,0))!=-1)printf(“元素%d的位置是%dn”,k,i);else printf(“元素%d不在表中n”,k); 8.3 //实现二叉排序树的基本运算 #include int key; struct BTNode *lchild; struct BTNode *rchild;}BTNode;//定义二叉排序树插入结点的算法 int BSTInsert(BTNode *&T,int k){ if(T==NULL) { T=(BTNode *)malloc(sizeof(BTNode)); T->lchild=T->rchild=NULL; T->key=k; return 1; } else { if(k==T->key) return 0; else if(k return BSTInsert(T->lchild, k); else return BSTInsert(T->rchild, k); } } //定义二叉排序树的创建算法 BTNode *createBST(int k[],int n){ BTNode *T; T=NULL; for(int i=0;i<=n-1;i++){ BSTInsert(T,k[i]); } return T;} //判断是否为二叉排序树 Status Judge(BTNode *&T){ } //定义二叉排序树的查找算法 BTNode *BSTSearch(BTNode *&T,int k){ if(T==NULL) return NULL; else if(T==NULL)return 1;else if((T>T->lchild)&&(T } else return 0;Judge(T->lchild);Judge(T->rchild); { printf(“%d ”,T->key); if(T->key==k) return T; else if(k { return BSTSearch(T->lchild, k); } else { return BSTSearch(T->rchild, k); } } } void main(){ int a[50]={4,9,0,1,8,6,3,5,2,7}; BTNode *bt=createBST(a,10); if(Judge(bt)==0)cout<<“bt不是二叉排序树”< } 8.4 //实现哈希表的相关运算 #include //定义最大哈希表长度 #define NULLKEY 0 //定义空关键字值 #define DELKEY-1 //定义被删关键字值 typedef int KeyType; //关键字类型 typedef char * InfoType;//其他数据类型 typedef struct { KeyType key;//关键字域 InfoType data; //其他数据域 int count; //探查次数域 } HashTable[MaxSize]; //哈希表类型 void InsertHT(HashTable ha,int *n,KeyType k,int p)中 { //将关键字k插入到哈希表 int i,adr;adr=k % p;if(ha[adr].key==NULLKEY || ha[adr].key==DELKEY)//x[j]可以直接放在哈希表中 } void CreateHT(HashTable ha,KeyType x[],int n,int m,int p)//创建哈希表 { } else { } n++;i=1;do { adr=(adr+1)% p;i++; //i记录x[j]发生冲突的次数 //发生冲突时采用线性探查法解决冲突 ha[adr].key=k;ha[adr].count=1;} while(ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);ha[adr].key=k;ha[adr].count=i; { int i,n1=0;for(i=0;i //哈希表置初值 { ha[i].key=NULLKEY; ha[i].count=0; } } int SearchHT(HashTable ha,int p,KeyType k){ int i=0,adr;adr=k % p;while(ha[adr].key!=NULLKEY && ha[adr].key!=k){ } if(ha[adr].key==k)return adr; //查找失败 //查找成功 i++; //采用线性探查法找下一个地址 //在哈希表中查找关键字k for(i=0;i } return-1;int DeleteHT(HashTable ha,int p,int k,int *n)//删除哈希表中关键字k { } void DispHT(HashTable ha,int n,int m) //输出哈希表 { float avg=0;int i;printf(“ 哈希表地址:t”);for(i=0;i } else //在哈希表中未找到该关键字 ha[adr].key=DELKEY;n--; //哈希表长度减1 //在哈希表中找到该关键字 return 1;return 0; printf(“ n”); printf(“ 哈希表关键字:t”); for(i=0;i if(ha[i].key==NULLKEY || ha[i].key==DELKEY)printf(“ ”); //输出3个空格 else printf(“ %3d”,ha[i].key);printf(“ n”);printf(“ 搜索次数:t”);for(i=0;i if(ha[i].key==NULLKEY || ha[i].key==DELKEY)printf(“ ”); //输出3个空格 else printf(“ %3d”,ha[i].count);printf(“ n”); for(i=0;i } if(ha[i].key!=NULLKEY && ha[i].key!=DELKEY)avg=avg+ha[i].count;avg=avg/n;printf(“平均搜索长度ASL(%d)=%gn”,n,avg); void main(){ int x[]={16,74,60,43,54,90,46,31,29,88,77};int n=11,m=13,p=13,i,k=29;HashTable ha;CreateHT(ha,x,n,m,p);printf(“n”);DispHT(ha,n,m);printf(“ 查找关键字29:n”);i=SearchHT(ha,p,k);if(i!=-1)printf(“ ha[%d].key=%dn”,i,k);else printf(“ 未找到%dn”,k);k=77;printf(“ 删除关键字%dn”,k);DeleteHT(ha,p,k,&n);DispHT(ha,n,m);i=SearchHT(ha,p,k);if(i!=-1)printf(“ ha[%d].key=%dn”,i,k);else printf(“ 未找到%dn”,k); } printf(“ 插入关键字%dn”,k);InsertHT(ha,&n,k,p);DispHT(ha,n,m);printf(“n”); 四，实验小结 1、通过本次实验，加深了我对查找表的认识。 2、有序表的查找之折半查找：前提必须是有序表，性能只有在均匀分布的时候才是最优的。 3、二叉排序树查找：通过一系列的查找和插入过程形成的树。之所以叫做排序树，因为按照中序遍历可得一个有序的序列。 实验五 查找算法 实验项目：必做：顺序查找、折半查找 选做：二叉查找树 实验类型: 验证性 实验内容： 顺序查找：用数组或链表实现，数据有序或无序均可； 折半查找：必须用数组实现，且数据有序； 注意：提交的实验报告要显示已有的数据元素、待查找的数据；应包含查找成功、不成功的情况。 《数据结构》 第八次实验报告 学生姓名 学生班级 学生学号 指导老师 重庆邮电大学计算机学院 计算机专业实验中心 一、实验内容 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与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点。在学习过程中，善于发现，会找到更多的捷径。 六、附录 运行结果截图。 金陵科技学院实验报告 学 生 实 验 报 告 册 课程名称： 学生学号： 所属院部： （理工类） 算法与数据结构 专业班级： 13网络工程 1305106009 学生姓名： 陈韬 网络与通信工程学院 指导教师： 沈奇 14 ——20 15 学年 第 1 学期 金陵科技学院教务处制 金陵科技学院实验报告 实验报告书写要求 实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。 实验报告书写说明 实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 （1）细致观察，及时、准确、如实记录。（2）准确说明，层次清晰。 （3）尽量采用专用术语来说明事物。 （4）外文、符号、公式要准确，应使用统一规定的名词和符号。（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。 金陵科技学院实验报告 实验项目名称： 顺序表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。 （2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。（3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。 （4）删除顺序表中所有等于X的数据元素。 2、选做题 （5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。 程序清单： #include 金陵科技学院实验报告 } sequenlist;sequenlist L={{1,3,5,5,7,8,10,12,17},8};void print_list(){ int i;for(i=0;i<=L.last;i++)printf(“%4d”,L.data[i]);} void find_all_x(int x){ int found=0,i;for(i=0;i<=L.last;i++)if(L.data[i]==x){ printf(“%3d”,i+1);found=1;} if(found==0)printf(“-1n”);} void insert_x(int x){ int loc,i;for(i=0;i<=L.last;i++)if(x 金陵科技学院实验报告 loc=i;for(i=L.last;i>=loc;i--)L.data[i+1]=L.data[i];L.data[loc]=x;L.last++;} void delete_x(int x){ int i,j,found=0;for(i=0;i<=L.last;i++)if(x==L.data[i]){ found=1;for(j=i+1;j<=L.last;j++)L.data[j-1]=L.data[j];i--;L.last--;} if(found==0)printf(“x is not foundn”);else { printf(“x is deletedn”);printf(“the list after deletion is:n”);print_list(); 金陵科技学院实验报告 } } void main(){ int x,choice;while(1){ printf(“**********menu**********n”);printf(“ 1--printn”);printf(“ 2--searchn”);printf(“ 3--insertn”);printf(“ 4--deleten”);printf(“ 5--exitn”);printf(“please input your choice:”);scanf(“%d”,&choice); switch(choice){case 1: printf(“the original list is:n”);print_list();break;case 2: printf(“pls input x you want to search:n”); 金陵科技学院实验报告 scanf(“%d”,&x);find_all_x(x);break;case 3: printf(“pls input x you want to insert:n”);scanf(“%d”,&x);insert_x(x);printf(“the list after insertion is:n”);print_list();break;case 4: printf(“pls input x you want to delete:n”);scanf(“%d”,&x);delete_x(x);printf(“the list after deletion is:n”);print_list();break;case 5: exit(0);} } } 金陵科技学院实验报告 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 单链表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验2 单链表 一、实验目的和要求 1、实验目的 掌握单链表的定位、插入、删除等操作。 2、实验要求 （1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。 （2）链表不能实现直接定位，一定注意指针的保存，防止丢失。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2）在递增有序的单链表中插入一个新结点x，保持单链表的有序性。 解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。 （3）编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。 2、选做题 已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。程序清单： 金陵科技学院实验报告 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 堆栈和队列 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验3 堆栈和队列 一、实验目的和要求 （1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。 （3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）判断一个算术表达式中开括号和闭括号是否配对。（2）测试“汉诺塔”问题。 （3）假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。 2、选做题 在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 串 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验4 串 一、实验目的和要求 掌握串的存储及应用。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。 （2）编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。 解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。（3）设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。 2、选做题 假设以链结构表示串，编写算法实现将串S插入到串T中某个字符之后，若串T中不存在这个字符，则将串S联接在串T的末尾。 提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 二叉树 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验5 二叉树 一、实验目的和要求 （1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。 （2）在第一题基础上，求二叉树中叶结点的个数。（3）在第一题基础上，求二叉树中结点总数。（4）在第一题基础上，求二叉树的深度。 2、选做题 已知一棵完全二叉树存于顺序表sa中，sa.elem[1…sa.last]存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。 解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 图 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验6 图 一、实验目的和要求 （1）熟练掌握图的基本概念、构造及其存储结构。 （2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）构造一个无向图（用邻接矩阵表示存储结构）。 （2）对上面所构造的无向图，进行深度优先遍历和广度优先遍历，输出遍历序列。 2、选做题 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。简单路径是指其顶点序列中不含有重复顶点的路径。提示：两个顶点及k值均作为参数给出。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 排序 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验7 排序 一、实验目的和要求 （1）熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的基本概念。 （2）掌握以上各种排序的算法。区分以上不同排序的优、缺点。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 用随机数产生100000个待排序数据元素的关键字值。测试下列各排序函数的机器实际执行时间（至少测试两个）：直接插入排序、希尔排序（增量为4，2，1）、冒泡排序、快速排序、直接选择排序、堆排序。 2、选做题 假设含n个记录的序列中，其所有关键字为值介于v和w之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v…w]，令number[i]统计关键字为整数i的纪录个数，然后按number重排序列以达到有序。试编写算法实现上述排序方法，并讨论此种方法的优缺点。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 查找 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验8 查找 一、实验目的和要求 （1）掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。（2）掌握哈希表设计。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）在一个递增有序的线性表中利用二分查找法查找数据元素X。 2、选做题 （2）构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。 提示：构造哈希表只是完成查找的第一步，大家应该掌握在哈希表上进行查找的过程，可以试着编程序实现。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 北 京 邮 电 大 学 计 算 机 科 学 与 技 术 学 院 算 法 与 数 据 结 构 实 验 指 导 书 杨俊、徐塞虹、漆涛 编著 2006年9月 算法与数据结构 实验指导书 目录 实验要求....................................................................................................................................3 试验 一、约瑟夫环..............................................................................…………………..……4 试验 二、长整数四则运算运算………………………………………………………………4 实验三、八皇后.....................................……..........................................................................5 实验 四、骑士遍历......................................……………………..............................................5 实验 五、桌面计算器...............................……………..............................................................6 实验 六、平衡排序二叉树....................…...…….....................................................................6 试验 七、多重集合的实现……......................................………………………………………7 试验 八、图论………………………………………………………………………….……..8 实验 八、内部排序性能的比较..........………………….............................................................8 教材及主要参考文献………………………………………………………………………………..9 2 北京邮电大学 计算机科学与技术学院 算法与数据结构 实验指导书 实验要求 一、本课程在讲课期间需要做上机实验，目的之一是检查学生对所学算法的掌握和理解程度；其次是锻炼学生的团队合作精神。 二、成绩： 1、编码：占整个实验成绩的50%； 2、测试：占整个实验成绩的20%； 3、文档：占整个实验成绩的30%。 三、按时提交上机文档，实验文档包含以下各项： 1、问题描述：实验题目、内容和要求； 2、算法思路：实验小组对问题的解决方法的文字描述； 3、算法描述：用类算法语言等对算法进行描述； 4、源程序及驱动程序：上机实验编制的代码源程序及程序运行环境； 5、测试数据：对算法的测试用例； 6、结果分析和结论：对算法及测试结果的分析及结论； 7、心得体会：通过实验获得的心得体会； 8、分工及签名：最后是小组成员的分工及签名。 北京邮电大学 计算机科学与技术学院-1-算法与数据结构 实验指导书 实验 一、约瑟夫环 一、实验类别：设计型实验。 二、问题描述：约瑟夫环问题是：n个人p0,p1,…pn 围坐成一个圆环。每个人pk持有一个秘密的数字ck。0 < ck <= m。开始时随机选取一个数 c = c0。每个人从p0 开始从1开始报数。报到数c 的人出对。然后以出队的人的秘密数字作为新的c 值。从出队者的下一个人顺时针从1 开始再报数。直到所有的人全部出队。 三、实验目的：检查学生对各种线性表的实现的掌握程度。 四、实验学时：2小时 五、实验组人数：1人。 六、实验设备环境：计算机。 七、实验原理及要点（知识点）：各种队列的实现。 八、实验内容和要求：至少用3种以上的线性表来完成此试验。可以在带头节点的和不带头节点的线性表、循环的和非循环线性表、动态链表和静态链表以及向量（数组）之间选择三种。从空表开始，为每个人生成一个随机数。然后将此人加入到线性表之中。 九、可研究与探索的问题：给出各种实现的优缺点比较。 十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出各种线性表实现的优缺点分析。 实验 二、长整数四则运算 一、实验类别：验证实验。 二、问题描述：计算机CPU本身可以做32位或者64位的整数四则运算。本试验要求对任意大小的整数实现其四则运算。将一个整数N表示为 N = ±(d0 + d1*B + d2*B2 + ….+ bk*Bk) 其中 1< B <= 256 为一个取定的整数。0 <= dk < B。用线性表存储{bk}。给出整数的四则运算程序。 三、实验目的：对具体的问题选择适当的线性表实现。 四、实验学时：2小时 五、实验组人数：3人。 六、实验设备环境：计算机。 七、实验原理及要点（知识点）：各种队列的实现。 八、实验内容和要求：至少用2种以上的线性表来完成此试验。比较不同线性表实现的速度。 九、可研究与探索的问题：1）对具体问题选择合适的线性表实现。2）B 的选取问题。可 否选择更大的基B。B的选择所应考虑的因素。 十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。能够得出用向量（数组）实现的线性表速度最快。 实验三、八皇后问题 一、实验类别：设计型实验。 二、问题描述：在n*n 的国际象棋棋盘上放置n个皇后，使每个皇后不受其他皇后的攻击。 三、实验目的：检查学生对堆栈和递归程序掌握程度。 四、实验学时：2小时 五、实验组人数：1人。 六、实验设备环境：计算机。 七、实验原理及要点（知识点）：递归程序与堆栈 八、实验内容和要求： 分别用递归和堆栈完成此试验。统计程序运行时间与问题规模n 的关系。 九、可研究与探索的问题：问题的复杂度。当n 比较大时，讨论提高程序运行的方法。 十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。找出程序运行速度的瓶颈。 实验 四、骑士遍历 一、实验类别：设计型实验。 二、问题描述：在国际象棋n*n的棋盘中，一匹马从棋盘中任意一格出发，要求用n2-1步走完所有的n2个格子。每个格子走且只走过一次。应如何走？ 试给出算法实现。 三、实验目的：检查学生对堆栈与回溯算法的掌握。 四、实验学时：2小时 五、实验组人数：3人。 六、实验设备环境：计算机。 七、实验原理及要点（知识点）：堆栈与回溯 八、实验内容和要求：用堆栈完成此试验。统计程序运行时间与问题规模n 的关系。 九、可研究与探索的问题：怎样枚举所有马下一步可走的位置。选择下一步所走位置的策略。注意由于这个程序非常耗时，在初期程序调试时应取较小的n。 十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。找出程序运行速度的瓶颈。给出不同选择策略的程序运行 速度的比较结果。 实验 五、桌面计算器（表达式求值） 一、实验类别：设计型实验。 二、问题描述：模仿Unix系统下的dc命令。输入表达式字符串，按回车键后给出表达式的值。操作数为实数。 1）操作符有 “+”、“-”、“*”、“/”、“^”（乘方） 2）还可以有临时变量。用法如 pi = 3.1415926，r = 3, r*pi^2 3）还可以有事先定义的函数如：“sin()”（正弦）、“cos()”（余弦）、“log()”（对数）、“ln()”（自然对数）等函数。 三、实验目的：检查学生用堆栈解决实际问题。为本课程后续的内容提供伏笔。也为后继的课程如编译原理预习。 四、实验学时：2小时 五、实验组人数：3人。 六、实验设备环境：计算机。 七、实验原理及要点（知识点）：堆栈，线性表，命令行参数的处理。 八、实验内容和要求：学生应至少应实现处理五个运算符：“+”、“-”、“*”、“/”、“^”（乘方）。可以用一个线性表来存储临时变量。另一个线性表来存储预定义的函数名。 九、可研究与探索的问题：查找临时变量名的不同方法。如哈希表，二叉树。 十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。 实验 六、平衡排序二叉树 一、实验类别：设计型实验。 二、问题描述：随机生成一组整数p0,p1,…pn－１。将这组整数按生成的次序插入到一个平衡排序二叉树中。然后将p0,p1,…pn－１随机重新排列为q0,q1,…qn－１。再按照次次序将这些整数从生成的平衡排序二叉树删除。 三、实验目的：平衡排序二叉树的插入和删除。 四、实验学时：2小时 五、实验组人数：3人。 六、实验设备环境：计算机。 七、实验原理及要点（知识点）：平衡排序二叉树的插入和删除中的旋转。 八、实验内容和要求：统计在平衡排序二叉树的插入和删除过程中各种旋转的出现次数。 九、可研究与探索的问题：研究平衡排序二叉树与一般的排序二叉树在插入和删除方面的性能比较。 十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出在均匀的随机分布下，平衡排序二叉树与一般排序二叉树的性能比较。 实验 七、多重集合的实现 一、实验类别：设计型实验。 二、问题描述：实现数学上多重集合。所谓的多重集合类似于集合，但是一件东西可以放置多个副本。就如一个菜篮子里面可以放两个苹果。 三、实验目的：查找结构的各种实现。 四、实验学时：2小时 五、实验组人数：3人。 六、实验设备环境：计算机。 七、实验原理及要点（知识点）：平衡排序二叉树的插入和删除、遍历，查找。哈希查找结构。 八、实验内容和要求： 假设集合中包含的元素是可以排序的。将多重集合封装成一个类。具体的实现可以是中序线索化的平衡排序二叉树，或者带父节点指针的平衡排序二叉树。多重集合的界面如下： template { Multi_set(void);//构造函数，初始化为空集合~Multi_set(void);//析构函数 Multi_set& operator=(Multi_set const a);//重载运算符= bool contains(T const& v)const;//如果集合包含v 则返回true，否则返回false Multi_set& operator+=(Multi_set const&a);//将集合a 并到自身中。 Multi_set& operator-=(Multi_set const& a);//自身减去集合a Multi_set& operator-=(T const& a);//自身减去一个元素a };//~class Multi_set //返回集合a,b的并 template //返回集合a,b的差 template //返回 a –{v} template Multi_set 九、可研究与探索的问题：哈希函数的选取。比较哈希与平衡排序二叉树的优缺点、性能和速度。 十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出平衡排序二叉树实现的多重集合和用哈希实现的多重集合的性能比较。 实验 八、图论 一、实验类别：设计型实验。 二、问题描述：实现图论中的各种算法。 1）最小代价生成树的Krscal 算法和Prim算法。2）单源点的最短路径的Dijstra 算法。3）深度优先遍历与广度优先遍历。4）拓扑排序 5）求所有节点之间的最短路径Floyd算法 （在这五个小题中只要选作一个即可。） 三、实验目的：学习根据不同的运算来选取不同的存储结构。 四、实验学时：2小时 五、实验组人数：3人。 六、实验设备环境：计算机。 七、实验原理及要点（知识点）：图论中的各种算法及其复杂度。根据不同的操作来决定图的存储结构。 八、实验内容和要求：至少实现上面五个小题目中的一个。从文件中读入一个图的信息。 九、可研究与探索的问题：高级数据结构如堆、并查集在图论算法中的应用。 十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出在均匀的随机分布下，平衡排序二叉树与一般排序二叉树的性能比较。 实验 九、内部排序性能的比较 一、实验类别：设计型实验。 二、问题描述：随机生成一组整数p0,p1,…pn－１。对这组数据进行排序。 三、实验目的：比较不同排序算法的性能。 四、实验学时：2小时 五、实验组人数：3人。 六、实验设备环境：计算机。 七、实验原理及要点（知识点）：各种内部排序算法。 八、实验内容和要求： 1）实现插入排序，选择排序，希尔排序，堆排序以及快速排序。2）快速排序的多种版本。3）对单链表实现归并排序。4）基数排序。 5）对小型问题（n = 10）、中型问题（n = 1000）以及大型问题（n = 1百万）分别统计不同排序算法的键值比较次数、键值移动次数以及程序运行时间。 26）排序算法的时间复杂度可以有O(n)和 O(n log n)。对相同复杂度的算法，给出他们运行时间与时间复杂度的比值。 九、可研究与探索的问题：研究快速排序算法的不同改进方法。自省排序算法。只需要移动而不需要交换的快速排序方法。 十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出在均匀的随机分布下，对大中小问题的最快的排序算法。 教材及主要参考文献 [1] 严蔚敏、吴伟民，数据结构习题集，清华大学出版社，1999年 [2] John R.Hubbard, Data Structures with C++, China Machine Press, 2002.[3] Mark Allen Weiss, Data Structures and Problem Solving Using C++, 2ed, 清华大学出版社。2004年。[4] Robert Sedgewick，Algorithms in C Part 1 – 4: Fundamentals, Data Structures, Sorting, rdSearching, 3, 中国电力出版社，2003年。 [5] 严蔚敏、吴伟民，数据结构(C语言版)，清华大学出版社，2006年第二篇：数据结构实验指导(实验五：查找算法)
第三篇：数据结构实验报告-查找算法
第四篇：算法与数据结构实验
第五篇：算法与数据结构实验指导书
点击咨询 