用插排的:
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node
{
ElementType Data;
PtrToNode
Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表;空链表将输出NULL */
List Merge( List L1, List L2 );
List _InsertSort(List h, int x);
void _free(List h);
int main()
{
List L1, L2, L;
L1 = Read();
L2 = Read();
L = Merge(L1, L2);
Print(L);
Print(L1);
Print(L2);
_free(L1);
_free(L2);
_free(L);
return 0;
}
/* 你的代码将被嵌在这里 */
List Read()
{
PtrToNode first = NULL;
int n;
printf("Enter a series of integers (0 to terminate): \n");
while (scanf("%d",&n)==1 && n!=0)
{
PtrToNode new_node = (PtrToNode)malloc(sizeof(struct Node));
if (new_node == NULL)
{
printf("Error: malloc failed in add to list\n");
exit(0);
}
new_node->Data = n;
new_node->Next = first;
first = new_node;
}
return first;
}
void Print(List L)
{
for (; L!=NULL; L=L->Next)
printf("%d ", L->Data);
printf("\n");
}
List Merge(List L1, List L2)
{
List L=NULL;
for (; L1!=NULL; L1=L1->Next)
L = _InsertSort(L, L1->Data);
for (; L2!=NULL; L2=L2->Next)
L = _InsertSort(L, L2->Data);
return L;
}
List _InsertSort(List h, int x)
{
List p, q, s;
p = h;
q = NULL;
s = (List)malloc(sizeof(struct Node));
if (s == NULL)
{
printf("Error: malloc failed in add to list\n");
exit(0);
}
s->Data = x;
s->Next = NULL;
while (p)
{
if (x <= p->Data)
{
s->Next = p;
break;
}
q = p;
p = p->Next;
}
if (q)
q->Next = s;
else
h = s;
return h;
}
void _free(List h)
{
List p;
while (h)
{
p = h->Next;
free(h);
h = p;
}
}