[C语言]利用链表采用分治法进行递归查找不大于10000个数中的最大值

 给定一个含n个整数顺序存储的线性表，按分治法思路，采用二分策略，设计一个求出其最大值和最小值算法，编写相应测试程序。要求使用分治法设计出其中求最大值的递归算法。

输入样例:

100 2 3 -2 -8 -6 -9 -10 50 2 -1

输出样例

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    struct node *next,*prev;
    int data;
}Node;
Node *_createNode() {
    Node *p;
    p = (Node*)malloc(sizeof(Node));
    p -> next = NULL;
    return p;
}

int _searchMax(Node *pList,int count,Node *ptail) {
    Node *phead,*pnext,*List;
    List = pList;
    phead = List -> next;
    pnext = phead -> next;
    int max;
    //如果只有两个元素则直接进行比较
    if(count == 2) {
        if(phead -> data > pnext -> data) {
            List -> next = pnext -> next;
            max = phead -> data;
            return max;
        }
        else {
            List -> next = pnext;
            max = pnext -> data;
            return max;
        }
    }

    //比较n与n-1的大小
    else {
        count--;
        max = _searchMax(List,count,ptail -> prev);
        if(max > ptail -> data) {
            return max;
        }
        else {
            max = ptail -> data;
            return max;
        }

    }
}
int main()
{
    int max;
    int count = 0;

    //创建一个链表
    Node *List = _createNode();
    Node *ptail;
    ptail = List -> next;
    //输入数据
    int num;
    do {
        scanf("%d",&num);
        Node *pnew = _createNode();
        pnew -> data = num;
        if(ptail == NULL) {
            List -> next = pnew;
            ptail = pnew;
        }
        else if(ptail != NULL) {
            ptail -> next = pnew;
            pnew -> prev = ptail;
            ptail = pnew;
        }
        count++;
    }
    while(getchar() == ' ');

    //查找
    max = _searchMax(List,count,ptail);
    //打印
    printf("%d",max);
    //销毁
    //_destroy(List);
    Node *p = List;
    while(p) {
        List = List -> next;
        free(p);
        p = List;
    }
    return 0;
}

:  

100

代码如下：