c语言归并两个有序链表
/**
归并有序列表L1,L2到L3,使L3有序,从小到大
xxwu
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode * next;
} LNode, *LinkList;
//初始化 尾插法 以9999退出
LinkList initListTill(LinkList L);
//归并两个有序链表L1,L2到L3,使L3有序
LinkList mergeList(LinkList L1, LinkList L2, LinkList L3);
//打印链表
void printLNode(LinkList L);
//初始化 尾插法 以9999退出
LinkList initListTill(LinkList L) {
L = (LNode *) malloc(sizeof(LNode));
L->next = NULL;
LNode *s, *r;
r = L;
int x;
scanf("%d", &x);
while(x!=9999) {
s = (LNode *) malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d",&x);
}
r->next = NULL;
return L;
}
//打印链表
void printLNode(LinkList L){
LinkList p = L->next;
int i = 1;
while(p != NULL) {
printf("第 %d 个元素值 %d \t\t对应地址%x\n",i,p->data,p);
p = p->next;
i++;
}
}
//归并两个有序链表L1,L2到L3,使L3有序
LinkList mergeList(LinkList L1, LinkList L2, LinkList L3) {
LNode *c1 = L1->next;
LNode *c2 = L2->next;
L3 = (LinkList)malloc(sizeof(LNode));
LNode *till = L3;
while(c1 && c2) {
LNode *c3 = (LinkList) malloc(sizeof(LNode));
if(c1->data < c2->data) {
c3->data = c1->data;
c1 = c1->next;
}else{
c3->data = c2->data;
c2 = c2->next;
}
//L3尾插法
till->next = c3;
till = c3;
}
while(c1) {
LNode *c3 = (LinkList) malloc(sizeof(LNode));
c3->data = c1->data;
till->next = c3;
till = c3;
c1 = c1->next;
}
while(c2) {
LNode *c3 = (LinkList) malloc(sizeof(LNode));
c3->data = c2->data;
till->next = c3;
till = c3;
c2 = c2->next;
}
till->next = NULL;
//释放L1,L2
// free(L1);free(L2);
return L3;
}
int main()
{
LinkList L = NULL;
L = initListTill(L);// L地址发生了改变
printLNode(L);
LinkList L2 = NULL;
L2 = initListTill(L2);// L地址发生了改变
printLNode(L2);
LinkList L3 =NULL;
L3 = mergeList(L,L2,L3);
printLNode(L3);
// insertElem(L2,3,555);
// LNode *p = getLocateElem(L2,3);
// printf("第3个元素%d\n",p->data);
// printLNode(L2);
// deleteLocateElem(L2,1);
// deleteElem(L2,p);
// printLNode(L2);
return 0;
}
测试: