链表合并（C语言版）

第 1 页 共 4 页

#include //单链表定义

typedef struct node{ int data; //数据域 struct node *next; //指针域 }lnode,*linklist; //初始化

linklist initlist() { linklist l; l=(linklist)malloc(sizeof(lnode)); l->next=0; printf(\初始化成功--\\n\

return l; }

//求表长

int listlength(linklist l) { linklist p; int count=0; p=l->next; while(p) { p=p->next;

count++; }

return count; }

//插入

void insertlist(linklist l,int i,int e) { int j=0; linklist p,q; p=l; while(p&&j

p=p->next; j++; }

if(!p||j>i-1) {

printf(\插入失败--\\n\ }

q=(linklist)malloc(sizeof(lnode)); yujmh

//声明单链表 //生成新结点 //头结点 //初始化成功 //返回单链表

//结点类型p //存储表长 //首节点 //结点不空 //结点后移 //表长

//返回表长

//变量j //结点p,q

//p指向头结点 //找寻第i-1个结点 //p结点后移

//记录结点位置 //判断插入是否成功 //插入失败,返回

//生成新结点

第 1 页

2013-4-17

第 2 页 共 4 页

q->data=e; //为新结点赋值 q->next=p->next;p->next=q; //插入新结点到链表中 //printf(\插入成功--\\n\

}

//创建链式有序表

void createlist(linklist l,int n) {

int i=0,j,e; //变量i,e linklist p; //结点p for(;inext; //首结点

j=1; //j=1使单链表每次从首节点开始比较 printf(\输入元素:\ //输入元素

while(p&&p->data<=e) //结点不为空,且其中元素非递减 {

j++; //依次比较位置 p=p->next; //结点后移

}

insertlist(l,j,e); //插入元素e到链表中,并使链表有序

}

printf(\创建成功--\\n\ //创建成功

}

//打印表中元素 void printlist(linklist l) {

linklist p; //结点p p=l->next; //首节点 printf(\表中元素:h\ //链表头部

while(p) //结点不为空 {

printf(\ //输出元素

p=p->next; //结点后移 }

printf(\ //链表尾部

}

//合并链式有序表

linklist mergelist_l(linklist la,linklist lb,linklist *lc) { //已知单链表la,lb的元素按值非递减排列 //归并la和lb得到新的单链表lc,lc的元素也按值非递减排列

linklist pa,pb,pc; //结点la,lb,lc pa=la->next;pb=lb->next; //pa和pb的初值分别指向两个表的第一个结点

yujmh

第 2 页

2013-4-17

第 3 页 共 4 页

lc=la; //用la的头结点做lc的头结点 pc=lc; //pc指向lc的头结点 while(pa&&pb) //A表和B表都不为空 {

if(pa->data<=pb->data) //依次\摘取\两表中最小的结点插入到C表{ } else {

pc->next=pb;pc=pb;pb=pb->next; //将pb所指结点链接到pc所指结点之后

的最后

pc->next=pa;pc=pa;pa=pa->next; //将pa所指结点链接到pc所指结点之后

} }

pc->next=pa?pa:pb; //插入非空表的剩余段 free(lb); //释放B表的头结点 return lc; //返回C表

}

void main() {

int i,n,e; //变量i,n,e linklist la,lb,lc; //声明表la,lb,lc printf(\

初

始

化

==================================\ printf(\表初始化...\ //A表初始化

la=initlist(); //初始化A表 printf(\表长:%d\\n\ //输出A表长 printf(\表初始化...\ //B表初始化 lb=initlist(); //初始化B表 printf(\表长:%d\\n\ //输出B表长 printf(\表初始化...\ //C表初始化 lc=initlist(); //初始化C表 printf(\表长:%d\\n\ //输出C表长 printf(\

创

建

链

表

=================================\ printf(\元素个数:\ //链表A元素个数

createlist(la,n); //创建链式有序表A printf(\表长:%d\\n\ //输出A表长

printlist(la); //打印A表中元素 printf(\元素个数:\ //链表B元素个数 createlist(lb,n); //创建链式有序表B printf(\表长:%d\\n\ //输出B表长

printlist(lb); //打印B表中元素 printf(\链式

第 3 页

表合并

yujmh 2013-4-17

第 4 页 共 4 页

================================\ lc=mergelist_l(la,lb,lc); //合并A、B表 printf(\表表长:%d\\n\输出C表长 printlist(lc); //显示合并后C表中元素

printf(\=============\ putchar('\\n'); //结束 }

yujmh 第 4 页 2013-4-17