实验四 查找
一．实验目的
二．实验例题
[问题描述]
将折半查找算法写成完整的程序，并上机通过。 [输入]
有序表（12,23,28,35,37,39,50,60,78,90）及待查找记录23,58。 [输出]
输入23，表中存在待查找记录，则显示该记录在表中位置2，输入58显示该记录不存在。 [存储结构]
有序表采用顺序方式存储。 [算法的基本思想]
首先用待查找记录与查找区间中间位置记录比较，若相等则查找成功，返回该记录在表中的位置数，若小于中间位置记录，则修改区间上界为中间位置减 1，若大于中间位置记录，则修改区间下界为中间位置加 1，在新的区间内继续查找。当查找区间下界大于上界，则该记录不存在。
三．程序清单
#include\typedef struct{ int a[30]; int length; }sqtable; sqtable st; int b=0;
void createst(int k){ int i;
printf(\ data:\ st.a[0]=-100;
for (i=1;(!b&&(i<=k));i++){ scanf(\if (st.a[i] printf(\ b=1; } } if (!b) {st.length=k; printf(\ } } void stfind(sqtable st,int y){ int f,l,h,m; } l=1;h=st.length; f=1; while ((l<=h)&&f){ m=(l+h)/2; if (y==st.a[m]) f=0; else if (y if (!f) printf(\%d in position %d.\\n\ else printf(\find %d.\\n\ } main(){ int n,x; printf(\ scanf(\ createst(n); if (b==0) { printf(\input you want find value:\ scanf(\ stfind(st,x); } 四．运行结果 输入有序表（2,23,24,35,46,57,68,79,81,89,99），输入23，表中存在待查找记录，则显示该记录在表 中位置2，输入58显示该记录不存在。 五．实验结果与分析 通过本次实验，我掌握查找表上的有关查找方法，并学会分析时间复杂度。 课程名称：实验项目：实验地点：专业班级：学生姓名：指导教师： 数据结构 实验五 内排序 博学楼B座 学号： 201200 杨崇艳 2014年12月07日 实验五 内排序 一．实验目的 二．实验例题 [问题描述] 将快速排序算法写成完整的程序上机通过，并统计递归深度。 [输入] 待排序记录个数n，各待排序记录值。 [输出] n个记录由小到大排列的结果。 [存储结构] 待排序记录顺序存储。 [算法的基本思想] 快速排序算法每次任取一个记录的关键字为标准，将其余记录分为两组，将所有关键字小于或等于标准的记录都放在它的位置之前，将所有关键字大于标准的记录都放在它的位置之后。 三．程序清单 #include void q(int l,int r){ int p; d++; if(dl printf(\ \ printf(\ if(l i=l; j=r; x=afile[i]; while(i!=j){ while((afile[j]>x)&&(j>i)) j--; if(i afile[i++]=afile[j]; while((afile[i] i++; if(i afile[j--]=afile[i]; } afile[i]=x; for(p=1;p<=n;p++) printf(\; printf(\ q(l,i-1); q(i+1,r); } d--; printf(\ * *%d* *\\n\} main() { int p; printf(\ scanf(\ printf(\ for(p=1;p<=n;p++) scanf(\ d=0; dl=0; l=1; r=n; q(l,r); for(p=1;p<=n;p++) printf(\ printf(\ printf(\} 四．运行结果 输入3，待排记录为（3,8,5,4），（12,76,89,34），（4546,976,34549,244,13）。输出（3,4,5,8）， （12,34,76,89），（13,244,976,4546,34549）。 五．实验结果与分析 通过本次实验，我掌握了线性表的排序方法，并学会分析时间复杂度。