阿伟，别打电动了，休息一下好不好

实验五 递归

第一题

/*
  编写递归算法int max(int a[],int left, int right)，求数组a[left..right]中的最大数。
*/

#include "ArrayIo.h"
/*请将本函数补充完整，并进行测试*/
int max(int a[],int left,int right)
{
	int l, r, mid;
	if(left >= right)	return a[left];//设置递归终止条件
	else
	{
		mid = left + right >> 1;
		l = max(a, left, mid);//不断的划分为子问题
		r = max(a, mid + 1, right);
		return l > r ? l : 	r;//三目运算符
	}
}
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)
{
	while(left < right && a[left] % 2 == 1)	left++;//跳转到第一个需要交换的位置
	while(left < right && a[right] % 2 == 0)	right--;
	if(left < right)
	{
		a[left] = a[left] + a[right];//不需要提供额外的空间来存储变量
		a[right] = a[left] - a[right];
		a[left] = a[left] - a[right];
		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, flag = 0;//flag的作用为判定该数组是否排好序的依据
	if(n > 0)//递归终止条件
	{
		for(i = 0; i < n - 1; i ++)
		{
			flag = 0;
			if(a[i] > a[i + 1])
			{
				a[i] += a[i + 1];//无需额外的值交换变量
				a[i + 1] = a[i] - a[i + 1];
				a[i] -= a[i + 1]; 
				flag = 1;											
			}		
		}
		if(flag)	return bubbleSort(a, n - 1);//如果flag == 0 表示这个数组已经排好序了
	}
	return ;
}
int binSearch(int a[], int left,int right,int key)
{
	int mid;
	if(left > right)	return -1;//设置递归结束条件
	else
	{
		mid = left + right >> 1;
		if(a[mid] > key) return binSearch(a, left, mid - 1, key);//二分返回结果
		else if(a[mid] == key)	return mid;
		else return 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 r;
	    if (head->next == NULL)//递归终止条件
	            return NULL;
	    else
	        if (head->next->next == NULL)//对于递归结果进行处理
	            return head->next;
	        else
	        {
	            r = max(head->next);
	            return head->next->info > r->info ? head->next : r;
	        }
}
}
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;
}