【C语言】数据结构C语言版实验5 递归

分手后的思念是犯贱 2022-12-27 09:14 165阅读 0赞

/*
      编写递归算法int max(int a[],int left, int right)，求数组a[left..right]中的最大数。
    */
    #include "ArrayIo.h"
    /*请将本函数补充完整，并进行测试*/
    int max(int a[],int left,int right)
    {
        int mid,lmax,rmax;
        if(left==right)
            return a[left];
        else
        {
            mid=(left+right)/2;
            lmax=max(a,left,mid);
            rmax=max(a,mid+1,right);
            return lmax>rmax?lmax:rmax;
        }
    }
    int main()
    {   int a[10];
        input(a,10);
        print(a,10);
        printf("数组的最大数是:%d\n",max(a,0,9));
        return 0;
    }

/*
    请编写一个递归算法函数void partion(int a[], int left, int right)，
    将数组a[left..right]中的所有奇数调整到表的左边，所有偶数调整到表的右边。
    */
    #include "ArrayIo.h"
    #define N 10
    /*请将本函数补充完整，并进行测试*/
    void partion(int a[], int left,int right)
    {
        int temp;
        while(left<right)
        {
            while(left<right&&a[left]%2==1)  //左边找偶数
                left++;
            while(left<right&&a[right]%2==0) //右边找奇数
                right--;
            if(left<right)                   //左右交换
            {
                temp=a[left];
                a[left]=a[right];
                a[right]=temp;
                partion(a,left+1,right-1);
            }
        }
    }
    int main()
    {   int a[N];
        init(a,N);                /*随机产生N个数*/
        print(a,N);
        partion(a,0,N-1);
        print(a,N);
        return 0;
    }

/*
      请编写递归函数void bubbleSort(int a[],int n)，
      对长度为n的数组采用冒泡法进行升序排序。
      请编写递归函数int binSearch(int a[], int left, int right,int key)，
      采用二分查找法在数组a[left..right]中查找值为key的元素所在的位置，
      若查找失败函数返回-1。
      */
    #include "ArrayIo.h"
    #define N 10
    /*请将本函数补充完整，并进行测试*/
    void bubbleSort(int a[],int n)
    {
        int i,temp,flag;
        if(n>1)
        {
            flag=0;
            for(i=0;i<n-1;i++)
            {
                if(a[i]>a[i+1])
                {
                    temp=a[i];
                    a[i]=a[i+1];
                    a[i+1]=temp;
                    flag=1;
                }
            }
            bubbleSort(a,n-1);
        }
    }
    int binSearch(int a[], int left,int right,int key)
    {
        int mid;
        if(left>right)
            return -1;
        else
        {
            mid=(left+right)/2;
            if(a[mid]==key)
                return mid;
            else if(a[mid]>key)
                binSearch(a,left,mid-1,key);
            else
                binSearch(a,mid+1,right,key);
        }
    }
    int main()
    {   int x,pos,a[N];
        init(a,N);
           bubbleSort(a,N);
        print(a,N);
        printf("请输入要查找的数：\n");
        scanf("%d",&x);
        pos=binSearch(a,0,N-1,x);
        if (pos!=-1) printf("a[%d]=%d\n",pos,x);
        else printf("Not found!\n");
        return 0;
    }

/*
    已知带头结点的单链表结构定义同实验3，假设链表中所有结点值均不相同，
    请编写一个递归函数linklist max(linklist head)，返回表中最大数所在的结点地址，若链表为空，返回NULL。
    */
    #include "slnklist.h"
    /*请将本函数补充完整，并进行测试*/
    linklist max(linklist head)
    {
        linklist p,q;
        if(!head->next)
            return NULL;
        else
            if(!head->next->next)
            return head->next;
        else
        {
            p=max(head->next);
            if(head->next->info > p->info)
                return head->next;
            return p;
        }
    }
    int main()
    {   linklist head,p;
        head=creatbyqueue();
        print(head);
        p=max(head);
        if (p)
            printf("max=%d\n",p->info);
        else
            printf("链表为空\n");
        return 0;
    }