/*
* 线性表单链式存储结构（代码块完整，可直接执行）
* 建议使用 VS Code.配置自查，有需要我再发。
* By: HSGO 19-08-12
*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 //不可行的
#define OVERFLOW -2 //溢出
typedef int Status;
//-----------------------------------------------
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
//-----------------------------------------------
#include <stdio.h>
#include <stdlib.h>
/* 输出链表 */
void ShowLNode();
/* 算法01 获取第i个元素，并赋予e */
Status GetElem_L();
/* 算法02 在i位置插入e元素 */
Status ListInsert_L();
/* 算法03 删除i位置元素，并将值赋予e */
Status ListDelete_L();
/* 算法04 建立单链表(将结点连接起来) */
void CreateList_L();
/* 算法05 归并两个链表 */
void MergeList_L();
int main(){
LNode A;//声明1个头结点
int a = 1;
for (int i = 1; i <= 5; i++)//循环插入5个结点
{
ListInsert_L(&A, i, a);
a++;
a++;
}
printf("Lnode A are :\t");
for (int i = 0; i < 5; i++)//打印
{
ElemType e;
GetElem_L(&A, i, &e);
printf("%d\t",e);
}
ElemType E;
ListDelete_L(&A, 3, &E);//删除一个结点
printf("\nAfter delete adr 3 elem\nLnode A are :\t");
for (int i = 0; i < 4; i++)//打印
{
ElemType e;
GetElem_L(&A, i, &e);
printf("%d\t",e);
}
LinkList B;//声明三个头节点指针
LinkList C;
LinkList D;
printf("\nScanf B:");
/* 注意此处参数为头结点指针的指针&B，因为参数传递的是指针所指的变量，
* 如果单纯传B，它没有指定变量，即失效，
* 传入&B,实际指的是它的对象B，但使用时还是要遵循规定。 */
CreateList_L(&B, 5);//初始化B表，并输入5个数.
ShowLNode(B);
printf("\nScanf C:");
CreateList_L(&C, 5);//初始化C表，并输入5个数
ShowLNode(C);
MergeList_L(B, C, &D);//合并
printf("\nAfter mergeted... :");
for (int i = 0; i < 10; i++)//打印
{
ElemType e;
GetElem_L(D, i, &e);
printf("%d\t",e);
}
LinkList aa = A.next; //释放分配的内存。
while (aa)
{
free(aa);
aa = aa->next;
}
while (B || C)
{
free(B);
free(C);
B = B->next;
C = C->next;
}
while (D)
{
free(D);
D = D->next;
}
return 0;
}
//-----------------------------------------------
void ShowLNode(LinkList L){
printf("Lnode are :\t");
LinkList p = L->next;
while(p){
printf("%d\t", p->data);
p = p->next;
}
}
Status GetElem_L(LinkList L, int i, ElemType *e){
//L为带头结点的头指针
LinkList p = L->next;
int j = 0;
while (p && j<i)
{
p = p->next;
++j;
}
if(!p || j>i) return ERROR;
*e = p->data;
return OK;
}
Status ListInsert_L(LinkList L, int i, ElemType e){
LinkList p = L;
int j = 0;
while( p && j < i-1 ){
p = p->next;
++j;
}
if( !p || j > i-1 ) return ERROR;
LinkList s = (LinkList) malloc ( sizeof(LNode) );
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
Status ListDelete_L(LinkList L, int i, ElemType *e){
LinkList p = L;
int j = 0;
while (p->next && j < i-1)
{
p = p->next;
++j;
}
if (!(p->next) || j>i-1) return ERROR;
LinkList q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
void CreateList_L(LinkList *L, int n){
LinkList l = (LinkList) malloc (sizeof(LNode));
l->next = NULL;
*L = l;
for (int i = n; i > 0; i--)
{
LinkList p = (LinkList) malloc (sizeof(LNode));
scanf("%d",&(p->data));
p->next = (*L)->next;
(*L)->next = p;
}
}
void MergeList_L(LinkList La, LinkList Lb, LinkList *Lc){
//La,Lb皆为递增链表，此函数得到合并之后的递增链表。
LinkList pa = La->next;
LinkList pb = Lb->next;
LinkList pc;
*Lc = pc = La;
while (pa && pb)
{
if (pa->data <= pb->data)
{//此处为难点，pc指的是Lc链表的当前最后一项，即：它的next应是下一个要存入的结点指针。
pc->next = pa;
pc = pa;//把pa结点归到Lc下后，pa即为当前Lc的最后一项。
pa = pa->next;//pa指针指向pa的下一个结点。
}else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;//剩余的归并。
free(Lb);
}
结果打印：
Lnode A are : 1 3 5 7 9
After delete adr 3，
Lnode A are : 1 3 7 9
Scanf B: 10 8 6 4 2
Lnode are : 2 4 6 8 10
Scanf D:9 7 5 3 1
Lnode are : 1 3 5 7 9
After mergeted... :1 2 3 4 5 6 7 8 9 10
