链式存储：生成链表、融合链表

接下来是生成一个链表存放奇数，一个链表存放偶数，在将两个链表里的结点融合成一个递增的链表并存放在原来的空间里；以此演示简单的链式存储。

1. 创建链表

代码：

//  创建一个链表 ListA
typedef struct ListA{
	int data;
	struct ListA *next;
}ListA,*Listde;//类型别名与该指针别名

解读：

• 用 typedef 定义别名，data存放数据，该类型指针 next当做后继结点；Listde是该类型的指针，这里当做头指针用来传送链表地址

2. 初始化

代码：

void Initialize(Listde &l){
	l = new ListA;//生成空间
	l->data = 0;//用表示链表的有效长度
	l->next = NULL;//指向空，表结束
}

解读：

• 函数名 Initialize ，&l是引用类型，引用类型的实质是给所传入实参起个小名并通过小名使用实参（小名也就是形参）；
• new 可创建一片空间相当于(类型 *)malloc(sizeof(类型)*数量)

3. 查看链表

代码：

//  全部查看
void ShowList(Listde &l){
	ListA *p = l;
	while(1){
		p = p->next;//结点后移
		printf("%d  -> ",p->data);
		if(p->next == NULL){
			break;
		} 
	}
	printf("\n");
}

解读：

• 利用循环依次打印出链表的data,也就是数据域
• 不用for是因为不知道具体的循环次数，循环到最后一个结点（元素）的后继为空（NULL）为止

4. 插入

代码：

//  插入
int ListInsert(Listde &l,int position,int value){
	ListA *c = new ListA;
	c->data = value;//用 c存储所需数据，c是插入的结点
	c->next = NULL;
	ListA *p = l;
	int j = 0;
	while(p&&j<position-1){
		p = p->next;
		j++; 
	}
	c->next = p->next;
	p->next = c;
	l->data++;//长度加一
	return 1;
}

解读：

• 插入需要知道：所插入的链表Listde &l；所插入的位置int position；所插入的数据int value
• 创建一个c作为所插入的新单元，然后循环p,让p处于需要插入的位置；再将p的地址传给c，最后保持后继正常即p->c->下一个结点

5. 融合链表

代码：

//  融合链表
int ListMerge(Listde &l1,Listde &l2,Listde &l3){
	ListA *pa;//用pa遍历l1
	ListA *pb;//用pb遍历l2
	ListA *pc;//用pc遍历l3
	pa = l1->next;
	pb = l2->next;
	l3 = l1;
	pc = l3;
	while(pa&&pb){//l1和l2均未达到表尾，依次摘取两表值中较小的结点插入l3的最后
		if(pa->data<=pb->data){
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		} else{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}  
	pc->next = pa?pa:pb;//判断后继位置，确保序列正确
	delete l2;
	return 1;
}

解读：

• l1，l2, l3分为是奇数链表、偶数链表、融合后的递增链表；用pa,pb,pc代替操作l1，l2, l3
• while(pa&&pb)是只要pa或pb不指向NULL就一直循环
• pc->next = pa?pa:pb; <—>pc的后继是否为pa，为真则指向pa否则指向pb

6. main函数

代码：

int main(){
	Listde LA;
	Initialize(LA);
	for(int i=1;i<=101;i+=2){
		ListInsert(LA,LA->data+1,i);//从队尾插入，得到递增序列
	}
	printf("第一个链表为：\n");
	ShowList(LA);
	Listde LB;
	Initialize(LB);
	for(int i=2;i<=100;i+=2){
		ListInsert(LB,LB->data+1,i);//从队尾插入，得到递增序列
	}
	printf("第二个链表为：\n");
	ShowList(LB);
	ListMerge(LA,LB,LA);
	printf("合并后的链表为：\n");
	ShowList(LA);
}

解读：

• Listde LA; 生成链表LA ；Initialize(LA);初始化链表LA
• 循环插入数据时，ListInsert(LA,LA->data+1,i) ； LA->data+1是一直从队尾插入保证插入后呈递增趋势

全部代码：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

//  创建一个链表 ListA
typedef struct ListA{
	int data;
	struct ListA *next;
}ListA,*Listde;//类型别名与该指针别名

//  初始化
void Initialize(Listde &l){
	l = new ListA;//生成空间
	l->data = 0;//用表示链表的有效长度
	l->next = NULL;//指向空，表结束
}

//  全部查看
void ShowList(Listde &l){
	ListA *p = l;
	while(1){
		p = p->next;//结点后移
		printf("%d  -> ",p->data);
		if(p->next == NULL){
			break;
		} 
	}
	printf("\n");
}

//  插入
int ListInsert(Listde &l,int position,int value){
	ListA *c = new ListA;
	c->data = value;//用 c存储所需数据，c是插入的结点
	c->next = NULL;
	ListA *p = l;
	int j = 0;
	while(p&&j<position-1){
		p = p->next;
		j++; 
	}
	c->next = p->next;
	p->next = c;
	l->data++;//长度加一
	return 1;
}

//  融合链表
int ListMerge(Listde &l1,Listde &l2,Listde &l3){
	ListA *pa;//用pa遍历l1
	ListA *pb;//用pb遍历l2
	ListA *pc;//用pc遍历l3
	pa = l1->next;
	pb = l2->next;
	l3 = l1;
	pc = l3;
	while(pa&&pb){//l1和l2均未达到表尾，依次摘取两表值中较小的结点插入l3的最后
		if(pa->data<=pb->data){
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		} else{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}  
	pc->next = pa?pa:pb;//判断后继位置，确保序列正确
	delete l2;
	return 1;
}

int main(){
	Listde LA;
	Initialize(LA);
	for(int i=1;i<=101;i+=2){
		ListInsert(LA,LA->data+1,i);//从队尾插入，得到递增序列
	}
	printf("第一个链表为：\n");
	ShowList(LA);
	Listde LB;
	Initialize(LB);
	for(int i=2;i<=100;i+=2){
		ListInsert(LB,LB->data+1,i);//从队尾插入，得到递增序列
	}
	printf("第二个链表为：\n");
	ShowList(LB);
	ListMerge(LA,LB,LA);
	printf("合并后的链表为：\n");
	ShowList(LA);
}

运行结果：

注意：
new 与 &引用类型是有些语言不通用的，这里文件的格式后缀是.cpp