给定一个含n个整数顺序存储的线性表，按分治法思路，采用二分策略，设计一个求出其最大值和最小值算法，编写相应测试程序。要求使用分治法设计出其中求最大值、最小值组合的递归算法。
输入格式:
若干整数，个数小于等于10000。
输出格式:
最小值,最大值。
| 输入样例: | 100 2 3 -2 -8 -6 -9 -10 50 2 -1 |
|---|---|
| 输出样例: | -10,100 |
| 作者 | 李卫明 |
|---|---|
| 单位 | 杭州电子科技大学 |
| 代码长度限制 | 16 KB |
| 时间限制 | 400 ms |
| 内存限制 | 64 MB |
C语言版本：
#include <stdio.h>
typedef struct Node{
int data;
struct Node *next;
} Node;
Node* input(){
char str[1024];
char *delim = " ";
scanf("%[^\n]", str);
Node* head = (Node*)malloc(sizeof(Node));
Node * end = head;
Node * node;
char *p = strtok(str, delim);
head->data = atoi(p);
while((p = strtok(NULL, delim))){
node = (Node*)malloc(sizeof(Node));
node->data = atoi(p);
head->next = node;
head = head->next;
}
return end;
}
//非递归程序 选择排序
Node* min_max(Node* head){
int num[1024];
int count=0;
//数据全部放到数组里面
while(head!=NULL){
num[count++]=head->data;
head = head->next;
}
//先对输入的数 进行排序
for(int i=0;i<count;i++){
int minNum=num[i];
for(int j=i+1;j<count;j++){
if(num[j]<minNum){
int temp=minNum;
minNum=num[j];
num[j]=temp;
}
}
num[i]=minNum;
}
//封装成结构体返回 最大值 最小值
Node* h = (Node*)malloc(sizeof(Node));
Node * end = h;
//最小值
h->data=num[0];
//最大值
Node * node=(Node*)malloc(sizeof(Node));
h->next = node;
node->data = num[count-1];
return end;
}
void output(Node* head){
while(head!=NULL){
printf(" %d",head->data);
head = head->next;
}
}
// sort
int main(void) {
Node * h = input();
printf("%d,",min_max(h)->data);
printf("%d\n",min_max(h)->next->data);
}
