作者: ubuntuer 时间: 2008-10-24 23:33:00
这个题目应该不是考什么算法,考数据结构了
|
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 5
typedef struct list
{
int num;
struct list* next;
}LIST;
void init_list(LIST** L)
{
*L = (LIST*)malloc(sizeof(LIST));
(*L)->next = NULL;
}
void add_list(LIST* L, int num)
{
LIST* p = (LIST*)malloc(sizeof(LIST));
p->num = num;
p->next = L->next;
L->next = p;
}
void print_list(LIST* L)
{
LIST* p = L->next;
while(p!=NULL)
{
printf("%d\t", p->num);
p = p->next;
}
printf("\n");
}
LIST* merge(LIST* L1, LIST* L2)
{
LIST* L = L1;
LIST* p1 = L1->next;
LIST* p2 = L2->next;
LIST* q1;
LIST* q2;
while(p1!=NULL&&p2!=NULL)
{
q1 = p1;
p1 = p1->next;
q1->next = p2;
q2 = p2;
p2 = p2->next;
q2->next = p1;
}
return L;
}
int main(int argc, char *argv[])
{
int i = 0;
int num = 0;
srand((unsigned int)time(NULL));
LIST* L1 = NULL;
LIST* L2 = NULL;
init_list(&L1);
init_list(&L2);
for(i=0;i<N;i++)
{
num = rand()%100+1;
add_list(L1, num);
}
for(i=0;i<N;i++)
{
num = rand()%100+1;
add_list(L2, num);
}
printf("list1 is:\n");
print_list(L1);
printf("list2 is:\n");
print_list(L2);
LIST* L = merge(L1,L2);
printf("list is:\n");
print_list(L);
system("PAUSE");
return 0;
}
|
上面那个代码有点问题,如果L2比L1长的话,错误就出来了!!!!刚实验室一哥们找到一递归的方法,perfect!!!可怜我想不到啊
LIST* merge(LIST* L1,LIST* L2)
{
if(L1==NULL)
return L2;
else
L1->next = merge(L2,L1->next);
return L1;
}
简洁,了当就是有点不好理解!!!!其实递归就是考虑一种情况时的状况就可以了....
L1 --- L11 --- L111 --- NULL
L2 --- L22 --- L222 --- NULL
从最前面开始考虑:
如果L1==null的话直接return L2
merge(L1,L2) => L1->next = merge(L2,L1->next)
ok对感叹就这么easy
|
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 5
typedef struct list
{
int num;
struct list* next;
}LIST;
void init_list(LIST** L)
{
*L = (LIST*)malloc(sizeof(LIST));
(*L)->next = NULL;
}
void add_list(LIST* L, int num)
{
LIST* p = (LIST*)malloc(sizeof(LIST));
p->num = num;
p->next = L->next;
L->next = p;
}
void print_list(LIST* L)
{
LIST* p = L->next;
while(p!=NULL)
{
printf("%d\t", p->num);
p = p->next;
}
printf("\n");
}
LIST* merge(LIST* L1, LIST* L2)
{
LIST* L = L1;
LIST* p1 = L1->next;
LIST* p2 = L2->next;
LIST* q1;
LIST* q2;
while(p1!=NULL&&p2!=NULL)
{
q1 = p1;
p1 = p1->next;
q1->next = p2;
q2 = p2;
p2 = p2->next;
if(p1!=NULL)
q2->next = p1;
}
if(p1==NULL)
q1->next = q2;
return L;
}
LIST* merge1(LIST* L1, LIST* L2)
{
if(L1==NULL)
return L2;
else
L1->next = merge1(L2, L1->next);
return L1;
}
int main(int argc, char *argv[])
{
int i = 0;
int num = 0;
srand((unsigned int)time(NULL));
LIST* L1 = NULL;
LIST* L2 = NULL;
init_list(&L1);
init_list(&L2);
for(i=0;i<N-2;i++)
{
num = rand()%100+1;
add_list(L1, num);
}
for(i=0;i<N;i++)
{
num = rand()%100+1;
add_list(L2, num);
}
printf("list1 is:\n");
print_list(L1);
printf("list2 is:\n");
print_list(L2);
#if 0
LIST* L = merge(L1,L2);
printf("list is:\n");
print_list(L);
#endif
#if 1
L1->next = merge1(L1->next,L2->next);
printf("list is:\n");
print_list(L1);
#endif
system("PAUSE");
return 0;
}
|
