数据结构实验5-递归

 
  1. /*
  2.   编写递归算法int max(int a[],int left, int right),求数组a[left..right]中的最大数。
  3. */
  4. #include "ArrayIo.h"
  5. /*请将本函数补充完整,并进行测试*/
  6. int max(int a[],int left,int right)
  7. {
  8.     int mid,lmax,rmax;
  9.     if(left==right)
  10.         return a[left];
  11.     else
  12.     {
  13.         mid=(left+right)/2;
  14.         lmax=max(a,left,mid);
  15.         rmax=max(a,mid+1,right);
  16.         return lmax>rmax?lmax:rmax;
  17.     }
  18. }
  19. int main()
  20. {   int a[10];
  21.     input(a,10);
  22.     print(a,10);
  23.     printf("数组的最大数是:%d\n",max(a,0,9));
  24.     return 0;
  25. }
 
  1. /*
  2. 请编写一个递归算法函数void partion(int a[], int left, int right),
  3. 将数组a[left..right]中的所有奇数调整到表的左边,所有偶数调整到表的右边。
  4. */
  5. #include "ArrayIo.h"
  6. #define N 10
  7. /*请将本函数补充完整,并进行测试*/
  8. void partion(int a[], int left,int right)
  9. {
  10.     int temp;
  11.     while(left<right)
  12.     {
  13.         while(left<right&&a[left]%2==1)  //左边找偶数
  14.             left++;
  15.         while(left<right&&a[right]%2==0//右边找奇数
  16.             right--;
  17.         if(left<right)                   //左右交换
  18.         {
  19.             temp=a[left];
  20.             a[left]=a[right];
  21.             a[right]=temp;
  22.             partion(a,left+1,right-1);
  23.         }
  24.     }
  25. }
  26. int main()
  27. {   int a[N];
  28.     init(a,N);                /*随机产生N个数*/
  29.     print(a,N);
  30.     partion(a,0,N-1);
  31.     print(a,N);
  32.     return 0;
  33. }
 
  1. /*
  2.   请编写递归函数void bubbleSort(int a[],int n),
  3.   对长度为n的数组采用冒泡法进行升序排序。
  4.   请编写递归函数int binSearch(int a[], int left, int right,int key),
  5.   采用二分查找法在数组a[left..right]中查找值为key的元素所在的位置,
  6.   若查找失败函数返回-1。
  7.   */
  8. #include "ArrayIo.h"
  9. #define N 10
  10. /*请将本函数补充完整,并进行测试*/
  11. void bubbleSort(int a[],int n)
  12. {
  13.     int i,temp,flag;
  14.     if(n>1)
  15.     {
  16.         flag=0;
  17.         for(i=0;i<n-1;i++)
  18.         {
  19.             if(a[i]>a[i+1])
  20.             {
  21.                 temp=a[i];
  22.                 a[i]=a[i+1];
  23.                 a[i+1]=temp;
  24.                 flag=1;
  25.             }
  26.         }
  27.         bubbleSort(a,n-1);
  28.     }
  29. }
  30. int binSearch(int a[], int left,int right,int key)
  31. {
  32.     int mid;
  33.     if(left>right)
  34.         return -1;
  35.     else
  36.     {
  37.         mid=(left+right)/2;
  38.         if(a[mid]==key)
  39.             return mid;
  40.         else if(a[mid]>key)
  41.             binSearch(a,left,mid-1,key);
  42.         else
  43.             binSearch(a,mid+1,right,key);
  44.     }
  45. }
  46. int main()
  47. {   int x,pos,a[N];
  48.     init(a,N);
  49.        bubbleSort(a,N);
  50.     print(a,N);
  51.     printf("请输入要查找的数:\n");
  52.     scanf("%d",&x);
  53.     pos=binSearch(a,0,N-1,x);
  54.     if (pos!=-1) printf("a[%d]=%d\n",pos,x);
  55.     else printf("Not found!\n");
  56.     return 0;
  57. }
 
  1. /*
  2. 已知带头结点的单链表结构定义同实验3,假设链表中所有结点值均不相同,
  3. 请编写一个递归函数linklist max(linklist head),返回表中最大数所在的结点地址,若链表为空,返回NULL。
  4. */
  5. #include "slnklist.h"
  6. /*请将本函数补充完整,并进行测试*/
  7. linklist max(linklist head)
  8. {
  9.     linklist p,q;
  10.     if(!head->next)
  11.         return NULL;
  12.     else
  13.         if(!head->next->next)
  14.         return head->next;
  15.     else
  16.     {
  17.         p=max(head->next);
  18.         if(head->next->info > p->info)
  19.             return head->next;
  20.         return p;
  21.     }
  22. }
  23. int main()
  24. {   linklist head,p;
  25.     head=creatbyqueue();
  26.     print(head);
  27.     p=max(head);
  28.     if (p)
  29.         printf("max=%d\n",p->info);
  30.     else
  31.         printf("链表为空\n");
  32.     return 0;
  33. }
本文地址:http://liuyanzhao.com/3590.html 转载请注明

发表评论

目前评论:1