8580 Merge linked list

8580 合并链表

题干

8580 合并链表
时间限制:1000MS 代码长度限制:10KB
提交次数:3724 通过次数:2077

题型: 编程题 语言: G++;GCC
Description
线性链表的基本操作如下：
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define ElemType int

typedef int Status;
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;

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

Status ListDelete_L(LinkList &L, int i, ElemType &e) { // 算法2.10
// 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
LinkList p,q;
p = L;
int j = 0;
while (p->next && j < i-1) { // 寻找第i个结点,并令p指向其前趋
p = p->next;
++j;
}
if (!(p->next) || j > i-1) return ERROR; // 删除位置不合理
q = p->next;
p->next = q->next; // 删除并释放结点
e = q->data;
free(q);
return OK;
} // ListDelete_L

Design an algorithm to combine two non-decreasing ordered linked listsA和BMerge into a new non-decreasing ordered listC.

输入格式
第一行：单链表A的元素个数
第二行：单链表A的各元素（非递减）,用空格分开
第三行：单链表B的元素个数
第四行：单链表B的各元素（非递减）,用空格分开

输出格式
第一行：单链表A的元素列表
第二行：单链表B的元素列表
第三行：合并后单链表C的元素列表

输入样例
6
12 24 45 62 84 96
4
15 31 75 86

输出样例
List A:12 24 45 62 84 96
List B:15 31 75 86
List C:12 15 24 31 45 62 75 84 86 96

#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define ElemType int

typedef int Status;
typedef struct LNode
{
    
 int data;
 struct LNode *next;
}LNode,*LinkList;


int CreateLink_L(LinkList &L,int n){
    
// 创建含有n个元素的单链表
  LinkList p,q;
  int i;
  ElemType e;

  L = new LNode;
  L->next = NULL;              // 先建立一个带头结点的单链表

  q = new LNode;
  q = L;//作为指示指针,保证表头指针L无需改变

  for (i=0; i<n; i++) 
  {
    
    scanf("%d", &e);
    p = new LNode;  // 生成新结点
    p->data=e;
    q->next=p;
    q=q->next;
    p->next=NULL;
  }
  return OK;
}


int LoadLink_L(LinkList &L){
    
// 单链表遍历
 LinkList p = L->next;
 if(p->next==NULL)printf("The List is empty!"); // 请填空
 else
 {
    
	 while(p)    // 请填空
	 {
    
		printf("%d ",p->data);
		p=p->next;    // 请填空
	 }
 }
 printf("\n");
 return OK;
}


//Design an algorithm to combine two non-decreasing ordered linked listsA和BMerge into a new non-decreasing ordered listC.

int main()
{
    
    int n1,n2;
    LinkList La,Lb,Lc;
    
    scanf("%d",&n1);
    CreateLink_L(La,n1);

    scanf("%d",&n2);
    CreateLink_L(Lb,n2);

    printf("List A:");LoadLink_L(La);
    printf("List B:");LoadLink_L(Lb);

     LinkList p,q;
    p=La;   q=Lb;
    p=p->next;q=q->next;

  printf("List C:");
    while(q&&p)
    {
    

        if(p->data>q->data)
        {
    
            printf("%d ",q->data);
            q=q->next;
        }
        else
        {
    
            printf("%d ",p->data);
            p=p->next;
        }

    }
    while(!p&&q)
    {
    
        printf("%d ",q->data);
        q=q->next;
    }
    while(p)
    {
    
        printf("%d ",p->data);
        p=p->next;
    }
}

一些分析

1.In the main function in the following snippet

1. Why can't it be deletedp=p->next;q=q->next?What happens after deletion？
   If you delete not only can not sort,After running, the following problems will occur
   
   Because at the beginning, it was defined as a linked list with a header

2. 写CreateLink_L(LinkList &L,int n)千万不要死记硬背
   基本顺序：定义–>Create a linked list with a header–>Insert a new node backwards
   nextAny node in the domain must be clearly explained;
   data域：In addition to the header node, it must be explained clearly
   As for the definition,You can add as you write

3. The merging of linked lists is nothing more than the following situations：
   ①la中元素>lb中元素
   ②la中元素<lb中元素
   ③laThe watch is empty
   ④lbThe watch is empty