当前位置:   article > 正文

查找和排序_设计一个算法,输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序方法查找关键字5的过

设计一个算法,输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序方法查找关键字5的过

1  顺序查找

编写一个程序,输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序方法查找关键字5的过程。

#include <stdio.h>

#define MAXL 100                            /*定义表中最多记录个数*/

typedef int KeyType;

typedef char InfoType[10];

typedef struct

{    

       KeyTypekey;                /*KeyType为关键字的数据类型*/

   InfoType data;                  /*其他数据*/

} NodeType;

typedef NodeType SeqList[MAXL];                  /*顺序表类型*/

int SeqSearch(SeqList R,int n,KeyType k) /*顺序查找算法*/

 

{

   int i=0;

   while (i<n && R[i].key!=k)

       {

              printf("%d",R[i].key);

              i++;                             /*从表头往后找*/

       }

   if (i>=n)

              return-1;

   else

       {

              printf("%d",R[i].key);

              returni;

       }

}

void main()

{

       SeqListR;

       intn=10;

       KeyTypek=5;

       inta[]={3,6,2,10,1,8,5,7,4,9},i;

       for(i=0;i<n;i++)                         /*建立顺序表*/

              R[i].key=a[i];

       printf("\n");

       if((i=SeqSearch(R,n,k))!=-1)

              printf("\n元素%d的位置是%d\n",k,i);

       else

              printf("\n元素%d不在表中\n",k);

       printf("\n");

}

2  二分查找

编写一个程序,输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用二分查找法查找关键字9的过程。

#include <stdio.h>

#define MAXL 100                           /*定义表中最多记录个数*/

typedef int KeyType;

typedef char InfoType[10];

typedef struct

{    

       KeyTypekey;                /*KeyType为关键字的数据类型*/

   InfoType data;                  /*其他数据*/

} NodeType;

typedef NodeType SeqList[MAXL];           /*顺序表类型*/

int BinSearch(SeqList R,int n,KeyTypek)  /*二分查找算法*/

{

       intlow=0,high=n-1,mid,count=0;

       while(low<=high)

       {             

              mid=(low+high)/2;

              printf("第%d次查找:在[%d,%d]中查找到元素R[%d]:%d\n",++count,low,high,mid,R[mid].key);

              if(R[mid].key==k)      /*查找成功返回*/

                     returnmid;

              if(R[mid].key>k)     /*继续在R[low..mid-1]中查找*/

                     high=mid-1;

              else

                     low=mid+1;            /*继续在R[mid+1..high]中查找*/

       }

       return-1;

}

void main()

{

       SeqListR;

       KeyTypek=9;

       inta[]={1,2,3,4,5,6,7,8,9,10},i,n=10;

       for(i=0;i<n;i++)                         /*建立顺序表*/

              R[i].key=a[i];

       printf("\n");

       if((i=BinSearch(R,n,k))!=-1)

              printf("元素%d的位置是%d\n",k,i);

       else

              printf("元素%d不在表中\n",k);

       printf("\n");

}

3  直接插入排序

编写一个程序实现直接插入排序过程,并输出{9,8,7,6,5,4,3,2,1,0}的排序过程

#include <stdio.h>

#define MAXE 20                /*线性表中最多元素个数*/

typedef int KeyType;

typedef char InfoType[10];

typedef struct           /*记录类型*/

{    

       KeyTypekey;             /*关键字项*/

       InfoTypedata;              /*其他数据项,类型为InfoType*/

} RecType;

void InsertSort(RecType R[],int n) /*对R[0..n-1]按递增有序进行直接插入排序*/

{

       inti,j,k;

       RecTypetemp;

       for(i=1;i<n;i++)

       {

              temp=R[i];

              j=i-1;                   /*从右向左在有序区R[0..i-1]中找R[i]的插入位置*/

              while(j>=0 && temp.key<R[j].key)

              {   

                     R[j+1]=R[j];   /*将关键字大于R[i].key的记录后移*/

                     j--;

              }

       R[j+1]=temp;                                    /*在j+1处插入R[i]*/

              printf("         i=%d ",i);             /*输出每一趟的排序结果*/

              for(k=0;k<n;k++)

                     printf("%3d",R[k].key);

              printf("\n");

       }

}

void main()

{

       inti,k,n=10;

       KeyTypea[]={9,8,7,6,5,4,3,2,1,0};

       RecTypeR[MAXE];

       for(i=0;i<n;i++)

              R[i].key=a[i];

       printf("\n");

       printf("  初始关键字  ");          /*输出初始关键字序列*/

       for(k=0;k<n;k++)

              printf("%3d",R[k].key);

       printf("\n");

       InsertSort(R,n);

       printf("   最后结果   ");           /*输出初始关键字序列*/

       for(k=0;k<n;k++)

              printf("%3d",R[k].key);

       printf("\n\n");

}

4  希尔插入排序

编写一个程序实现希尔插入排序过程,并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。

#include <stdio.h>

#define MAXE 20                /*线性表中最多元素个数*/

typedef int KeyType;

typedef char InfoType[10];

typedef struct           /*记录类型*/

{    

       KeyTypekey;             /*关键字项*/

   InfoType data;              /*其他数据项,类型为InfoType*/

} RecType;

void ShellSort(RecType R[],int n) /*希尔排序算法*/

{

       inti,j,d,k;

       RecTypetemp;

       d=n/2;                                 /*d取初值n/2*/

       while(d>0)

       {    

              for(i=d;i<n;i++)    /*将R[d..n-1]分别插入各组当前有序区中*/

              {    

                     j=i-d;

                     while(j>=0 && R[j].key>R[j+d].key)

                     {    

                            temp=R[j];      /*R[j]与R[j+d]交换*/

                            R[j]=R[j+d];

                            R[j+d]=temp;

                            j=j-d;

                     }

              }

              printf("       d=%d: ",d); /*输出每一趟的排序结果*/

              for(k=0;k<n;k++)

                     printf("%3d",R[k].key);

              printf("\n");

       d=d/2;                          /*递减增量d*/

       }

}

void main()

{

       inti,k,n=10;

       KeyTypea[]={9,8,7,6,5,4,3,2,1,0};

       RecTypeR[MAXE];

       for(i=0;i<n;i++)

              R[i].key=a[i];

       printf("\n");

       printf("初始关键字  ");            /*输出初始关键字序列*/

       for(k=0;k<n;k++)

              printf("%3d",R[k].key);

       printf("\n");

       ShellSort(R,n);

       printf("   最后结果  ");                   /*输出初始关键字序列*/

       for(k=0;k<n;k++)

              printf("%3d",R[k].key);

       printf("\n\n");

}

5  冒泡排序

编写一个程序实现冒泡排序过程,并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。

#include <stdio.h>

#define MAXE 20                /*线性表中最多元素个数*/

typedef int KeyType;

typedef char InfoType[10];

typedef struct           /*记录类型*/

{    

       KeyTypekey;             /*关键字项*/

   InfoType data;              /*其他数据项,类型为InfoType*/

} RecType;

void BubbleSort(RecType R[],int n)     /*冒泡排序算法*/

{

       inti,j,k;

       RecTypetemp;

       for(i=0;i<n-1;i++)

       {    

              for(j=n-1;j>i;j--)   /*比较,找出本趟最小关键字的记录*/

                     if(R[j].key<R[j-1].key)  

                     {    

                            temp=R[j];  /*R[j]与R[j-1]进行交换,将最小关键字记录前移*/

                            R[j]=R[j-1];

                            R[j-1]=temp;

                     }

              printf("         i=%d ",i);      /*输出每一趟的排序结果*/

              for(k=0;k<n;k++)

                     printf("%2d",R[k].key);

              printf("\n");

       }

}

void main()

{

       inti,k,n=10;

       KeyTypea[]={9,8,7,6,5,4,3,2,1,0};

       RecTypeR[MAXE];

       for(i=0;i<n;i++)

              R[i].key=a[i];

       printf("\n");

       printf("  初始关键字  ");   /*输出初始关键字序列*/

       for(k=0;k<n;k++)

              printf("%2d",R[k].key);

       printf("\n");

       BubbleSort(R,n);

       printf("   最后结果   ");    /*输出初始关键字序列*/

       for(k=0;k<n;k++)

              printf("%2d",R[k].key);

       printf("\n\n");

}

6  快速排序

编写一个程序实现快速排序过程,并输出{6,8,7,9,0,1,3,2,4,5}的排序过程。

#include <stdio.h>

#define MAXE 20                /*线性表中最多元素个数*/

typedef int KeyType;

typedef char InfoType[10];

typedef struct           /*记录类型*/

{    

       KeyTypekey;             /*关键字项*/

   InfoType data;              /*其他数据项,类型为InfoType*/

} RecType;

void QuickSort(RecType R[],int s,int t) /*对R[s]至R[t]的元素进行快速排序*/

{

       inti=s,j=t,k;

       RecTypetemp;

       if(s<t)                                /*区间内至少存在一个元素的情况*/

       {    

              temp=R[s];                      /*用区间的第1个记录作为基准*/

       while (i!=j)                 /*从区间两端交替向中间扫描,直至i=j为止*/

              {    

                     while(j>i && R[j].key>temp.key)

                         j--;                     /*从右向左扫描,找第1个关键字小于temp.key的R[j] */

                  if (i<j)                  /*表示找到这样的R[j],R[i]、R[j]交换*/

                     {    

                            R[i]=R[j];

                            i++; 

                     }

            while (i<j &&R[i].key<temp.key)

                         i++;               /*从左向右扫描,找第1个关键字大于temp.key的记录R[i] */

                  if (i<j)                  /*表示找到这样的R[i],R[i]、R[j]交换*/

                     {    

                            R[j]=R[i];

                            j--;  }

                  }

             R[i]=temp;

                     printf("             ");     /*输出每一趟的排序结果*/

                     for(k=0;k<10;k++)

                            if(k==i)

                                   printf("[%d]",R[k].key);

                            else

                                   printf("%4d",R[k].key);

                     printf("\n");

                     QuickSort(R,s,i-1);/*对左区间递归排序*/

                     QuickSort(R,i+1,t);/*对右区间递归排序*/

       }

}

void main()

{

       inti,k,n=10;

       KeyTypea[]={6,8,7,9,0,1,3,2,4,5};

       RecTypeR[MAXE];

       for(i=0;i<n;i++)

              R[i].key=a[i];

       printf("\n");

       printf("  初始关键字 ");                   /*输出初始关键字序列*/

       for(k=0;k<n;k++)

              printf("%4d",R[k].key);

       printf("\n");

       QuickSort(R,0,n-1);

       printf("   最后结果  ");                   /*输出初始关键字序列*/

       for(k=0;k<n;k++)

              printf("%4d",R[k].key);

       printf("\n\n");

}

7  直接选择排序

编写一个程序实现直接选择排序过程,并输出{6,8,7,9,0,1,3,2,4,5}的排序过程。

#include <stdio.h>

#define MAXE 20                /*线性表中最多元素个数*/

typedef int KeyType;

typedef char InfoType[10];

typedef struct           /*记录类型*/

{    

       KeyTypekey;             /*关键字项*/

   InfoType data;              /*其他数据项,类型为InfoType*/

} RecType;

void SelectSort(RecType R[],int n) /*直接选择排序算法*/

{

       inti,j,k,l;

       RecTypetemp;

       for(i=0;i<n-1;i++)            /*做第i趟排序*/

       {    

              k=i;

              for(j=i+1;j<n;j++)       /*在当前无序区R[i..n-1]中选key最小的R[k] */

                     if(R[j].key<R[k].key)

                            k=j;              /*k记下目前找到的最小关键字所在的位置*/

              if(k!=i)                       /*交换R[i]和R[k] */

              {    

                     temp=R[i];R[i]=R[k];R[k]=temp; 

              }

              printf("         i=%d ",i);      /*输出每一趟的排序结果*/

              for(l=0;l<n;l++)

                     printf("%2d",R[l].key);

              printf("\n");

       }

}

void main()

{

       inti,k,n=10,m=5;

       KeyTypea[]={6,8,7,9,0,1,3,2,4,5};

       RecTypeR[MAXE];

       for(i=0;i<n;i++)

              R[i].key=a[i];

       printf("\n");

       printf("  初始关键字  ");                 /*输出初始关键字序列*/

       for(k=0;k<n;k++)

              printf("%2d",R[k].key);

       printf("\n");

       SelectSort(R,n);

       printf("   最后结果   ");                  /*输出初始关键字序列*/

       for(k=0;k<n;k++)

              printf("%2d",R[k].key);

       printf("\n\n");

}




















声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/喵喵爱编程/article/detail/807692
推荐阅读
相关标签
  

闽ICP备14008679号