数据结构课程设计查找排序_数据结构课程设计排序
数据结构课程设计查找排序由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计排序”。
查找及排序算法实现
一、实验目的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，查找成功,算法结束；若keyr[mid].key，则low=mid+1；重复上述操作，直至low>high时，查找失败。2.起泡排序算法
起泡排序的思路：
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即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
首先以一个元素为基准，从一个方向开始扫描，比如从左至右扫描，以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 #include typedef int KeyType;typedef struct node { KeyType data;struct node *lchild,*rchild;}LNode,*Tree;
void Insert(Tree &T,KeyType key){
if(!T){ T=new LNode;T->data=key;T->lchild=T->rchild=NULL;} else
} {
} if(keydata)Insert(T->lchild,key);else Insert(T->rchild,key);void CreatTree(Tree &T)//二叉排序树的创建 {
} 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 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 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 #include #define M 10 //冒泡排序
int BubbleSort(int c[]){
int i,t,j;for(i=0;i
} for(j=0;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
int BinarySearch(int b[]){
} int t,mid;int i=0;int j=9;printf(“nn请输入您要查找的数字：”);scanf(“%d”, &t);while(i
} 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
} } BubbleSort(a);BinarySearch(a);return 0;
3、简单选择排序和简单插入排序算法
#include int SelectionSort(int*a,int n){
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
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
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
scanf(“%d”,&a[i]);} printf(“插入排序的流程以及结果：n”);
InserSort(a,n);return 1;
} break;}while(a!=0);
四、实验运行结果
1.二叉排序树的创建、遍历和查找删除算法
2、冒泡排序和折半查找算法
3、简单选择排序和简单插入排序算法
七、心得体会
通过本次的数据结构课程设计报告，掌握了查找和排序的几种基本排序算法，了解了他们各自的特点和优缺点，完成了对于他们C语言的描述和实际应用，对他们有了一个更加具体、深刻的认识，同时也锻炼了我们的逻辑思维能力和动手实践能力，使我们受益匪浅，给我们今后的计算机专业课程学习带来很大的帮助。
