学步园

两种头插法分别建立一个链表，然后合并，按非递减型输出：

 #include<iostream>
 /* 函数结果状态代码 */
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 #define OVERFLOW -2 
 using namespace std;
 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
 typedef int ElemType;
 struct LNode
 {
   ElemType data;
   LNode *next;
 };
 typedef LNode *LinkList;
 
 Status InitList(LinkList *L)
 { /* 操作结果：构造一个空的线性表L */
   *L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
   if(!*L) /* 存储分配失败 */
     exit(OVERFLOW);
   (*L)->next=NULL; /* 指针域为空 */
   return OK;
 }

 Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */
 { /* L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
   int j=1; /* j为计数器 */
   LinkList p=L->next; /* p指向第一个结点 */
   while(p&&j<i) /* 顺指针向后查找,直到p指向第i个元素或p为空 */
   {
     p=p->next;
     j++;
   }
   if(!p||j>i) /* 第i个元素不存在 */
     return ERROR;
   *e=p->data; /* 取第i个元素 */
   return OK;
 }

 Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改变L */
 { /* 在带头结点的单链线性表L中第i个位置之前插入元素e */
   int j=0;
   LinkList p=L,s;
   while(p&&j<i-1) /* 寻找第i-1个结点 */
   {
     p=p->next;
     j++;
   }
   if(!p||j>i-1) /* i小于1或者大于表长 */
     return ERROR;
   s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
   s->data=e; /* 插入L中 */
   s->next=p->next;
   p->next=s;
   return OK;
 }


 Status ListTraverse(LinkList L,void(*vi)(ElemType))
 /* vi的形参类型为ElemType，与bo2-1.c中相应函数的形参类型ElemType&不同 */
 { /* 初始条件：线性表L已存在 */
   /* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
   LinkList p=L->next;
   while(p)
   {
     vi(p->data);
     p=p->next;
   }
   cout<<endl;
   return OK;
 }

 void CreateList(LinkList &L,int n) // 
 { // 逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L
   int i;
   LinkList p;
   L=(LinkList)malloc(sizeof(LNode));
   L->next=NULL; // 先建立一个带头结点的单链表
   cout<<"请输入"<<n<<"个数据\n";
   for(i=n;i>0;--i)
   {
     p=(LinkList)malloc(sizeof(LNode)); // 生成新结点
     scanf("%d",&p->data); // 输入元素值
     p->next=L->next; // 插入到表头
     L->next=p;    //这就是书上的那个头插法~~ 
   }
 }

 void CreateList2(LinkList &L,int n)
 { // 正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表
   int i;
   LinkList p,q;
   L=(LinkList)malloc(sizeof(LNode)); // 生成头结点
   L->next=NULL;
   q=L;
   cout<<"请输入"<<n<<"个数据\n";
   for(i=1;i<=n;i++)
   {
     p=(LinkList)malloc(sizeof(LNode));
     cin>>p->data;
     q->next=p;
     q=q->next;   //这就是另一种头插法~~ 
   }
   p->next=NULL;
 }

 void MergeList(LinkList La,LinkList &Lb,LinkList &Lc)//
 { // 已知单链线性表La和Lb的元素按值非递减排列。
   // 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
   LinkList pa=La->next,pb=Lb->next,pc;
   Lc=pc=La; // 用La的头结点作为Lc的头结点
   while(pa&&pb)
     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; // 插入剩余段
   free(Lb); // 释放Lb的头结点
   Lb=NULL;
 }

 void visit(ElemType c) // ListTraverse()调用的函数(类型要一致)
 {
   cout<<c<<" ";
 }

int main()
 {
   int n=5;
   LinkList La,Lb,Lc;
   cout<<"按非递减顺序, ";
   CreateList2(La,n); // 正位序输入n个元素的值
   cout<<"La="; // 输出链表La的内容
   ListTraverse(La,visit);
   cout<<"按非递增顺序, ";
   CreateList(Lb,n); // 逆位序输入n个元素的值
   cout<<"Lb="; // 输出链表Lb的内容
   ListTraverse(Lb,visit);
   MergeList(La,Lb,Lc); // 按非递减顺序归并La和Lb,得到新表Lc
   cout<<"合并后按非递减型输出\nLc="; // 输出链表Lc的内容
   ListTraverse(Lc,visit);
 }