原创 合并A和B得到非递减排列的C

首先就是头文件LinkList.h这个头文件:

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

#define ListSize 100

typedef int DataType;

typedef struct Node
{
 DataType data;
 struct Node *next;
}ListNode, *LinkList;

/*******************************************************************************
函数名:InitList(LinkList *head)
函数功能:单链表的初始化操作
入口参数:
出口参数:
********************************************************************************/
void InitList(LinkList *head)
{
/*将单链表初始化为空，动态生成一个头结点，并将
头结点的指针域置为空*/
 if((*head=(LinkList)malloc(sizeof(ListNode)))==NULL)/*为头结点分配
  一个存储空间*/
  exit(-1);
 (*head)->nex*******************************************************************************
函数名:ListEmpty(LinkList head)
函数功能:判断单链表是否为空
入口参数:
出口参数:
********************************************************************************/
int ListEmpty(LinkList head)
{
/*判断单链表是否为空，就是通过判断头结点的指针域
是否为空*/
 if(head->next==NULL)/*判断单链表的头结点的指针域是否为空*/
  return 1;/*当单链表为空时，返回1，否则返回0*/
 else
  return 0;
}

/*******************************************************************************
函数名:         *Get(LinkList head, int i)
函数功能:  按序号查找操作
入口参数:
出口参数:
********************************************************************************/
ListNode *Get(LinkList head, int i)
{
/*查找单链表中第i个结点。查找成功返回该结点的指针表示成
功，否则返回NULL表示失败*/
 ListNode *p;
 int j;
 
 if(ListEmpty(head))/*在查找第i个元素之前，判断链表是否
  为空*/
  return NULL;
 
 if(i<1)/*在查找第i个元素之前，判断该序号是否合法*/
  return NULL;
 
 j=0;
 p=head;
 
 while(p->next != NULL && j<i)
  {
   p=p->next;
   j++;
  }
 if(j==i)/*查到第i个结点，返回指针p*/
  return p;
 else
  return NULL;/*如果没有找到第i个元素，返回NULL*/
}

/*******************************************************************************
函数名:        *LocateElem(LinkList head, DataType e)
函数功能:  按内容查找操作
入口参数:
出口参数:
********************************************************************************/
ListNode *LocateElem(LinkList head, DataType e)
{
/*查找线性表中元素值为e的元素，查找成功将对应元素
的结点指针返回，否则返回NULL表示失败*/
 ListNode *p;
 p=head->next;/*指针p指向第一个结点*/
 while(p)
  {
   if(p->data!=e)
    p=p->next;
   else
    break;/*如果等于e的话推出*/
  }
 return p;
}

/*******************************************************************************
函数名:        LocatePos(LinkList head,DataType e)
函数功能:  定位操作
入口参数:
出口参数:
********************************************************************************/
int LocatePos(LinkList head,DataType e)
{
/*查找线性表中元素值为e的元素，查找成功将对应元素
的序号返回，否则返回0表示失败*/
 ListNode *p;
 int i;
 if(ListEmpty(head))/*查找第i个元素之前判断链表是否为空*/
  return 0;
 p=head->next;/*指针p指向第一个结点*/
 i=1;
 while(p)
  {
   if(p->data==e)/*找到与e相等的元素，返回该序号*/
    return i;
   else
    {
     p=p->next;
     i++;
    }
  }
 if(!p) /*如果没有找到与e相等的元素，返回0表示失败*/
  return 0;
}

/*******************************************************************************
函数名:   InsertList(LinkList head, int i, DataType e)
函数功能:  插入操作
入口参数:
出口参数:
********************************************************************************/
int InsertList(LinkList head, int i, DataType e)
{
/*在单链表中第i个位置插入一个结点，结点元素值为e，插入
成功返回1，否则失败返回0*/
 ListNode *p,*pre;/*定义指向第i个元素的前驱结点指针pre
指针p指向新生成的结点*/
 int j;
 pre=head;/*指针p指向头结点*/
 j=0;
 while(pre->next != NULL && j<i-1)/*找到第i-1个结点，即第i个结点的
  前驱结点*/
  {
   pre=pre->next;
   j++;
  }
 if(j!=i-1)
  {
   printf("插入位置错");
   return 0;
  }
 /*新生成一个结点，并将e值赋给改结点的数据域*/
 if((p=(ListNode *)malloc(sizeof(ListNode)))==NULL)
  exit(-1);
 p->data=e;
 /*插入结点操作*/
 p->next=pre->next;
 pre->next=p;
 return 1;
}

/*******************************************************************************
函数名:  DeleteList(LinkList head, int i, DataType *e)
函数功能:  删除操作
入口参数:
出口参数:
********************************************************************************/
int DeleteList(LinkList head, int i, DataType *e)
{
/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回
0*/
 ListNode *pre,*p;
 int j;
 pre=head;
 j=0;
 while(pre->next !=NULL && pre->next->next !=NULL && j<i-1)
  {
   pre=pre->next;
   j++;
  }
 if(j!=i-1)
  {
   printf("删除位置错误");
   return 0;
  }
 /*指针p指向单链表中的第i 个结点，并将该结点的数据域
 值赋给e*/
 p=pre->next;
 *e=p->data;
 /*将前驱结点的指针域指向要删除结点的下一个结点，也
 就是将p指向的结点与单链表断开*/
 pre->next=p->next;
 free(p);/*释放p指向的结点*/
 return 1;
}

/*******************************************************************************
函数名: ListLength(LinkList head)
函数功能: 查表长度操作
入口参数:
出口参数:
********************************************************************************/
int ListLength(LinkList head)
{
 ListNode *p;
 int count=0;
 p=head;
 while(p->next != NULL)
  {
   p=p->next;
   count++;
  }
 return count;
}

/*******************************************************************************
函数名: DestroyList(LinkList head)
函数功能: 销毁链表操作
入口参数:
出口参数:
********************************************************************************/
void DestroyList(LinkList head)
{
 ListNode *p,*q;
 p=head;
 while(p != NULL)
  {
   q=p;
   p=p->next;
   free(q);
  }
}

然后就是实现功能的主函数代码了：

/*******************************************************************************
文件名:合并A和B得到非递减排列的C

功能要求:
利用A和B的原有空间建立新表C，通过依次比较单链表A和B的
结点元素，改变A和B的next域，将所有A和B的元素按照非递减
顺序连接在一起即可

时间:2011年10月5日
********************************************************************************/

#include"LinkList.h"

/*******************************************************************************
函数名:main()
函数功能:主函数
入口参数:
出口参数:
********************************************************************************/
void MergeList(LinkList A,LinkList B, LinkList *C)
{
 ListNode *pa,*pb,*pc;/*定义指向单链表A,B,C的指针*/
 pa=A->next;/*pa指向A的第一个结点*/
 pb=B->next;/*pb指向B的第一个结点*/

 *C=A;/*将单链表A的头结点作为C的头结点*/
 (*C)->next=NULL;/*将C的头结点的指针域清空*/
 pc=*C;//指针pc指向C的首地址
 /*依次将链表A和B中较小的元素存入链表C中*/
 while(pa && pb)
  {
   if(pa->data <= pb->data)
    {
     pc->next = pa;/*如果A中的元素小于或等于B中的
     元素将A中的结点作为C中的结点*/
      
     pc=pa;/*pc指向A的第一个结点也就是C的接下来加载
     上去的元素*/
     
     pa=pa->next;/*指针pa则指向A的下一个元素*/
    }
   else
    {
     pc->next=pb;/*如果A中的元素大于B中的元素，将
     B中的元素的结点作为C的结点*/
     pc=pb;/*pc指向B的结点也就是指向C的接下来加载上
     去得元素*/
      
     pb=pb->next;/*pb指向下一个元素*/
    }
   

  }
  pc->next = pa ? pa : pb;/*将剩余的结点插入C中*/
  free(B);/*释放B的头结点*/
}

/*******************************************************************************
函数名:main()
函数功能:主函数
入口参数:
出口参数:
********************************************************************************/
void main()
{
 int i;
 DataType a[]={6,7,9,14,37,45,65,67};
 DataType b[]={3,7,11,34,45,89};
 LinkList A,B,C;
 ListNode *p;
 InitList(&A);
 InitList(&B);
 for(i=1; i<=sizeof(a) / sizeof(a[0]); i++)/*将数组a中的元素插入到
 单链表A中*/
  {
   if(InsertList(A, i, a[i-1])==0)
    {
     printf("位置不合法");
     return;
    }
  }
 for(i=1; i<=sizeof(b) / sizeof(b[0]); i++)
  {
   if(InsertList(B, i, b[i-1])==0)
    {
     printf("位置不合法");
     return;
    }
  }
 printf("单链表A中的元素有%d个:\n",ListLength(A));
 for(i=1; i<=ListLength(A); i++)/*输出单链表A中的每个元素*/
  {
   p=Get(A, i);/*返回单链表A中的每个结点的指针*/
   if(p)
    printf("%4d",p->data);/*输出单链表A中的每个元素*/
  }
 printf("\n");
 printf("单链表B中的元素有%d个:\n",ListLength(B));
 for(i=1; i<=ListLength(B); i++)
  {
   p=Get(B,i);
   if(p)
    printf("%4d",p->data);
  }
 printf("\n");

 MergeList(A,B,&C);
 printf("将单链表A和B的元素合并到C中后，C中的元素有%d个:\n",ListLength(C));
 for(i=1; i<=ListLength(C); i++)
  {
   p=Get(C, i);
   if(p)
    printf("%4d",p->data);
  }
 printf("\n");
 
}