数据结构实验5-递归

avatar 2016年12月05日11:50:14 0 4410 views
博主分享免费Java教学视频，B站账号：Java刘哥 ，长期提供技术问题解决、项目定制：本站商品点此
 
  1. /*
  2.   编写递归算法int max(int a[],int left, int right)，求数组a[left..right]中的最大数。
  3. */
  5. #include "ArrayIo.h"
  6. /*请将本函数补充完整，并进行测试*/
  7. int max(int a[],int left,int right)
  8. {
  9.     int mid,lmax,rmax;
  10.     if(left==right)
  11.         return a[left];
  12.     else
  13.     {
  14.         mid=(left+right)/2;
  15.         lmax=max(a,left,mid);
  16.         rmax=max(a,mid+1,right);
  17.         return lmax>rmax?lmax:rmax;
  18.     }
  19. }
  20. int main()
  21. {   int a[10];
  22.     input(a,10);
  23.     print(a,10);
  24.     printf("数组的最大数是:%d\n",max(a,0,9));
  25.     return 0;
  26. }

  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;
  23.             partion(a,left+1,right-1);
  24.         }
  25.     }
  26. }
  27. int main()
  28. {   int a[N];
  29.     init(a,N);                /*随机产生N个数*/
  30.     print(a,N);
  31.     partion(a,0,N-1);
  32.     print(a,N);
  33.     return 0;
  34. }

  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.   */
  9. #include "ArrayIo.h"
  10. #define N 10
  11. /*请将本函数补充完整，并进行测试*/
  12. void bubbleSort(int a[],int n)
  13. {
  14.     int i,temp,flag;
  15.     if(n>1)
  16.     {
  17.         flag=0;
  18.         for(i=0;i<n-1;i++)
  19.         {
  20.             if(a[i]>a[i+1])
  21.             {
  22.                 temp=a[i];
  23.                 a[i]=a[i+1];
  24.                 a[i+1]=temp;
  25.                 flag=1;
  26.             }
  27.         }
  28.         bubbleSort(a,n-1);
  29.     }
  30. }
  31. int binSearch(int a[], int left,int right,int key)
  32. {
  33.     int mid;
  34.     if(left>right)
  35.         return -1;
  36.     else
  37.     {
  38.         mid=(left+right)/2;
  39.         if(a[mid]==key)
  40.             return mid;
  41.         else if(a[mid]>key)
  42.             binSearch(a,left,mid-1,key);
  43.         else
  44.             binSearch(a,mid+1,right,key);
  45.     }
  46. }
  47. int main()
  48. {   int x,pos,a[N];
  49.     init(a,N);
  50.        bubbleSort(a,N);
  51.     print(a,N);
  52.     printf("请输入要查找的数：\n");
  53.     scanf("%d",&x);
  54.     pos=binSearch(a,0,N-1,x);
  55.     if (pos!=-1) printf("a[%d]=%d\n",pos,x);
  56.     else printf("Not found!\n");
  57.     return 0;
  58. }

  1. /*
  2. 已知带头结点的单链表结构定义同实验3，假设链表中所有结点值均不相同，
  3. 请编写一个递归函数linklist max(linklist head)，返回表中最大数所在的结点地址，若链表为空，返回NULL。
  4. */
  7. #include "slnklist.h"
  8. /*请将本函数补充完整，并进行测试*/
  9. linklist max(linklist head)
  10. {
  11.     linklist p,q;
  12.     if(!head->next)
  13.         return NULL;
  14.     else
  15.         if(!head->next->next)
  16.         return head->next;
  17.     else
  18.     {
  19.         p=max(head->next);
  20.         if(head->next->info > p->info)
  21.             return head->next;
  22.         return p;
  23.     }
  24. }
  25. int main()
  26. {   linklist head,p;
  27.     head=creatbyqueue();
  28.     print(head);
  29.     p=max(head);
  30.     if (p)
  31.         printf("max=%d\n",p->info);
  32.     else
  33.         printf("链表为空\n");
  34.     return 0;
  35. }

本文地址：http://liuyanzhao.com/3590.html

转载请注明
历史上的今天
十二月
05日
  • 微信
  • 交流学习，资料分享
  • weinxin
  • 个人淘宝
  • 店铺名：言曌博客咨询部

  • (部分商品未及时上架淘宝)
avatar

发表评论

avatar 登录者：匿名
匿名评论，评论回复后会有邮件通知

  

已通过评论：0   待审核评论数：0