1052题解（链表操作）

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

//定义一个结点，可视为链表的最小单元，包括两要素：指针域和数据域
typedef struct Node
{
	struct Node *link;
	int num;
	int garde;	
} node;

node * creat(int n) /*建立单链表，n为链表中结点的个数*/
{
	node *pTail = NULL,*pHead = NULL,*pNew = NULL; 
//为了记住链表的起始地址,设置根指针*pHead保存表头结点的指针
//头指针指向链表的第1个节点,他只是一个指针,不包含任何数据
//*pTail尾节点，*pNew新结点
	int i; 

//线性表初始化，设置头结点，并使尾结点指向头结点
	if((pHead = (node *)malloc(sizeof(node)))==NULL) /*分配新存储空间并检测*/
	{
			printf("不能分配内存空间!");
			exit(0);
	}

	pHead->num=0; /*把表头结点的数据域置空*/
	pHead->garde=0;
	pHead->link=NULL; /*把表头结点的链域置空，此时还未插入任何数据*/
	pTail=pHead; /*pTail指向表头结点*/
//插入结点的步骤：
//1.生成新的结点，注意新结点的link指向NULL；
//2.将新结点添加到表尾；
//3.设置新的表尾
	for(i=0;i<n;i++)//插入n个节点
	{
		if((pNew = (node *)malloc(sizeof(node)))==NULL) /*分配新存储空间并检测*/
		{
			printf("不能分配内存空间!");
			exit(0);
		}	
		scanf("%d %d",&pNew->num,&pNew->garde);
		pNew->link=NULL;
		pTail->link=pNew; //新结点插到表尾
		pTail=pNew;//设置新的表尾
	}
	return pHead;
}

void output(node *p)
{
    do
    {
		printf("%d %d\n",p->num,p->garde);
		p= p->link;
    } while (p != NULL);
}

node *merge(node *p1,node *p2)//在链表1的尾部插入链表2
{
	node *p = p1;
	while(p->link != NULL)
    {
        p = p->link;
    }
    p->link = p2;//注意此处应该传入的是表头
    return p1;
}

//选择排序法思想：
//遍历链表，每次找出一个最小的节点，将其值与未排序节点的首个节点交换，这里需要一个指针标记值最小的节点。
node *SelectSort(node *head)
{
	node *first; /*排列后有序链的表头指针*/
	node *tail; /*排列后有序链的表尾指针*/ 
	node *p_min; /*保留键值更小节点的前驱指针*/
	node *min; /*存储最小节点*/ 
	node *p; /*当前比较的节点*/
 
	first = NULL;
	while (head != NULL) /*在链表中找键值最小的节点。*/
	{
	/*注意：这里for语句就是体现选择排序思想的地方*/
		for (p=head,min=head; p->link!=NULL; p=p->link) /*循环遍历链表中的节点，找出此时最小的节点。*/
		{   
			if (p->link->num < min->num) /*找到一个比当前min小的节点。*/
			{
				p_min = p; /*保存找到节点的前驱节点：显然p->link的前驱节点是p*/
				min = p->link; /*保存键值更小的节点。*/
			} 
		 }
  /*上面for语句结束后，就要做两件事；一是把它放入有序链表中；二是根据相应的条件判断，安排它离开原来的链表。*/

  /*第一件事*/
  if (first == NULL) /*如果有序链表目前还是一个空链表*/
  {
	first = min; /*第一次找到键值最小的节点。*/
	tail = min; /*尾指针始终指向最后一个节点*/
  }
  else /*有序链表中已经有节点*/
  {
	tail->link = min; /*把刚找到的最小节点放到最后，即让尾指针的link指向它。*/
	tail = min; /*尾指针也要指向它。*/
  }  

  /*第二件事*/
  if (min == head) /*如果找到的最小节点就是第一个节点*/
  {
	head = head->link; /*显然让head指向原head->link,即第二个节点*/
  }
  else /*如果不是第一个节点*/
  {
	p_min->link = min->link; /*前次最小节点的link指向当前min的link,这样就让min离开了原链表。*/
  }  
 }

 if (first != NULL) /*循环结束得到有序链表first*/
 {
	tail->link = NULL; /*单向链表的最后一个节点的link应该指向NULL*/ 
 }
	head = first;
	return head;
}



int main()
{
	node *pHead_a,*pHead_b,*t,*merg;
	int n,m;
	scanf("%d%d",&n,&m);
	pHead_a = creat(n)->link;//返回值为头指针
	pHead_b = creat(m)->link;
	merg = merge(pHead_a,pHead_b);
	t = SelectSort(merg);
	output(t);

	return 0;
}