C语言程序设计教程（第三版）课后习题11.8 （C语言描述—选择排序）

#include<stdio.h>
#include <stdlib.h>
typedef struct CStudent
{
	int m_num;
	float m_score;

	struct CStudent* pNext;
}STU;

STU* CreatLink(int n);
void CombineLink(STU* a,STU* b);
STU* SortLink(STU* phead);
void PrintfLink(STU* phead);
void FreeLink(STU* phead);
int main()
{
	int N,M;
	STU* a;
	STU* b;
	scanf("%d",&N);
	scanf("%d",&M);
	a=CreatLink(N);
	b=CreatLink(M);
	CombineLink(a,b);
	PrintfLink(SortLink(a));
	FreeLink(a);
	return 0;
}

STU* CreatLink(int n)
{
	STU* phead,*pt,*p;
	int i;
	for(i=1;i<=n;i++)
	{
		p=(STU*)malloc(sizeof(STU));
		scanf("%d",&p->m_num);
		scanf("%f",&p->m_score);
		if (i==1)
		{
			phead=p;
			pt=phead;
		}
		else
		{
			pt->pNext=p;
			pt=p;
		}
	}
	p->pNext=NULL;
	return phead;
}

void CombineLink(STU* a,STU* b)
{
	STU* pend;
	pend=a;
	while(pend->pNext!=NULL)
		pend=pend->pNext;
	pend->pNext=b;
}
STU* SortLink(STU* phead)
{
	//1.交换数据域---不用这种
	//2.交换结点---选择排序--另创建一个链表
	STU* new_phead=NULL,*pend; //新链表的头、尾结点
	STU *pbefore,*pmin,*pcur;//保存前结点，最小值的结点，当前结点
	while(phead!=NULL)
	{
		for(pcur=phead,pmin=phead;pcur->pNext!=NULL;pcur=pcur->pNext) //找出每轮的最小值
		{
			if (pcur->pNext->m_num < pmin->m_num)
			{
				pbefore=pcur;
				pmin=pcur->pNext;
			}
		}
		if (new_phead==NULL) //如果新链表头还是空的
		{
			new_phead=pmin; //头
			pend=pmin;//尾，下面用后插法一个个加进来
		}
		else  //有了头
		{
			pend->pNext=pmin;
			pend=pmin; //新的尾巴
		}
		//把最小值从原链表中脱离
		if(pmin==phead) //刚好是头
			phead=phead->pNext; //原链表头结点前移
		else
			pbefore->pNext=pmin->pNext; //断开
	}
	if(new_phead!=NULL)
		pend->pNext=NULL; //尾结点指针域为空
	phead=new_phead;
	return phead;
}
void PrintfLink(STU* phead)
{
	STU* p=phead; //保护链表头；
	while(p!=NULL)
	{
		printf("%d %.0f\n",p->m_num,p->m_score);
		p=p->pNext;
	}
}
void FreeLink(STU* phead)
{
	STU *p;
	while(phead!=NULL)
	{
		p=phead;
		phead=phead->pNext;
		free(p);
	}
	return;
}