闂傚倸鍊峰ù鍥敋閺嶎厼鍌ㄦ繛宸簻绾偓闂佽鍎煎Λ鍕倿閸偁浜滈柟瀵稿仜閸斻倝鏌ｈ箛鎾宠埞闁宠鍨块、娆撴偂鎼淬垺鐦ｆ俊鐐€栧ú鈺冪礊娓氣偓瀹曟椽鍩€椤掑嫭鐓ラ柣鏇炲€圭€氾拷第 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(;i
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