华南农业大学数据结构oj 8580 合并链表_华农oj数据结构

#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define ElemType int
 
typedef struct LNode
{
 int data;
 struct LNode *next;
}LNode,*LinkList;
 
int CreateLink_L(LinkList &L,int n){
// 创建含有n个元素的单链表
  LinkList p,q; // p为当前数据内容，q为下一个数据的地址
  //LinkList L只改变结构体的内容，不改变L的地址
  //而LinkList *L会改变L的地址
  int i;
  ElemType e;
  L = (LinkList)malloc(sizeof(LNode));//生成新结点作为头结点,即L为头结点
  //动态内存申请样例：p = (int *)malloc(sizeof(int));
  L->next = NULL;              // 给头结点下一个结点接上NULL，以NULL隔开，让头结点成为旧结点
 
  q = (LinkList)malloc(sizeof(LNode));//给予新结点q内存空间
  q = L;//新结点q变成旧结点(为下一个新结点的生成铺垫条件,即q结点为null后的结点）
  for (i=0; i<n; i++)
 { //生成n个元素的单链表
    scanf("%d", &e);
    p = (LinkList)malloc(sizeof(LNode));  // 给新节点p分配空间
    p -> data = e; //把e赋给结点p的数据域
    q -> next = p; //旧结点的指针指向新节点 把新旧结点链接起来
    p -> next = NULL; //新节点指向空，因为后面还没有元素加入
    q = p; //把新结点p变为旧结点q,为新的结点加入而做铺垫
 
  }
  return OK;
}
 
int ListInsert_L(LinkList &L, int i, ElemType e) {  // 算法2.9
LNode * newNode = (LinkList)malloc(sizeof(LNode)); //定义新节点newNode并赋予内存，LNode为定义新节点
newNode->data=e;//将e值放入newNode结点中
newNode->next=NULL;//给newNode接上一个为空的新结点
int num=0;//记录链表有多少个结点
LNode * p = L->next;//头节点的下一个结点位置定义为结点p
while(p!=NULL)//p非空时
{
	p=p->next;//指向p的下一个结点
	num++;//结点数+1
}
if(i>num+1)//当输入的第i个位置超出了链表长度时
{
	return ERROR;//返回ERROR值
}
p= L;//将p定位为头节点
int j=0;
while(j<i-1&&p!=NULL) //查找第i-1个结点，p指向该结点
{
	p=p->next;
	j++;
}
newNode->next=p->next;//将i-1结点的下一个位置(即i)赋给新结点的下一个位置
    p->next=newNode;//将新结点放入i-1结点的下一个位置(即i)
    return OK;
}
 
int ListDelete_L(LinkList &L, int i, ElemType &e) {  // 算法2.10
  // 在带头结点的单链线性表L中第i个位置之前插入元素e
// 请补全代码
LNode * newNode = (LinkList)malloc(sizeof(LNode)); //定义新节点newNode并赋予内存，LNode为定义新节点
newNode->data=e;//将e值放入newNode结点中
newNode->next=NULL;//给newNode接上一个为空的新结点
int num=0;//记录链表有多少个结点
LNode * p = L->next;//头节点的下一个结点位置定义为结点p
while(p!=NULL)//p非空时
{
	p=p->next;//指向p的下一个结点
	num++;//结点数+1
}
if(i>num+1)//当输入的第i个位置超出了链表长度时
{
	return ERROR;//返回ERROR值
}
p= L;//将p定位为头节点
int j=0;
while(j<i-1&&p!=NULL) //查找第i-1个结点，p指向该结点
{
	p=p->next;
	j++;
}
newNode->next=p->next;//将i-1结点的下一个位置(即i)赋给新结点的下一个位置
    p->next=newNode;//将新结点放入i-1结点的下一个位置(即i)
    return OK;
}
 
int LoadLink_L(LinkList &L)
{
// 单链表遍历并输出数据
 LinkList p = L->next;
 if(p==NULL)
 printf("The List is empty!");
 else
 {
	 while(p!=NULL)
	 {
		printf("%d ",p->data);
		p=p->next;//指针下移
	 }
 }
 printf("\n");
 return OK;
}
 
int MergeList_Sq(LinkList &A, LinkList &B, LinkList &C)
{
    LinkList pA = A->next;  //让pA指针指向A链表第一个有效节点（首节点，即头结点的下一个结点）
    LinkList pB = B->next;  //让pB指针指向B链表第一个有效节点（首节点, 即头结点的下一个结点）
    LinkList pC = C;        //让pC指针指向C链表的头结点
    while (pA != NULL && pB != NULL)//当pA指针与pB的指针的指向都非空时
    {
        if (pA->data > pB->data)//如果A链表的首结点大于B链表的首结点
        {
            pC->next = pB;  //让pB指针指向的B表中的对应结点接到C上
            pB = pB->next;  //指针后移动
            pC = pC->next;  //指针后移动
        }
        else//否则
        {
            pC->next = pA;   //让pA的指针指向的B表中的对应结点接到C上
            pA = pA->next;   //指针后移动
            pC = pC->next;   //指针后移动
        }
    }
    if (pA == NULL)//如果指针pA指向的链表A结点为空
    {
        while (pB != NULL)//当指针pB指向的链表B结点非空时
        {
            pC->next = pB;//让pB指针指向的对应B表中的对应结点接到C上
            pB = pB->next;//指针后移
            pC = pC->next;//指针后移
        }
    }
    else
    {
        while (pA != NULL)//当指针pA指向的链表B结点非空时
        {
            pC->next = pA;//让pB指针指向的对应B表中的对应结点接到C上
            pA = pA->next;//指针后移
            pC = pC->next;//指针后移
        }
    }
    return OK;  //别忘了
}
 
int main()
{
LinkList A;
LinkList B;
int a,n;
scanf("%d",&n);
CreateLink_L(A,n);
scanf("%d",&a);
CreateLink_L(B,a);
printf("List A:");
LoadLink_L(A);
printf("List B:");
LoadLink_L(B);
LinkList C = (LinkList)malloc(sizeof(LNode));
C->next = NULL; // 先建立一个带头结点的单链表
MergeList_Sq(A, B, C);
printf("List C:");
LoadLink_L(C);
}

以上我加过注释后的代码，望同学们易读好学，有改进之处可以提出来！有错误之处也望大神指出！