单链表排序交换节点算法

单链表交换节点排序，包括选择法、比较法、排序法。

用C实现代码如下：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW 0
#define OK 1
typedef int Status;
typedef int ElemType;

struct LNode
{ 
	ElemType data;
	struct LNode *next;
};
typedef struct LNode LinkList;
LinkList *InitList(LinkList *L);/*初始化一个链表*/
void DestoryList(LinkList *L);/*销假链表*/
void ClearList(LinkList *L);/*清空链表 */
Status ListEmpty(LinkList *L);/*判断链表是否为空 */
int ListLength(LinkList *L);/*返回表的长度  */
Status GetElem(LinkList *L,int i,ElemType *e);/*返回第i个元素的值 */
int LocateElem(LinkList *L,ElemType e,Status(*compare)(ElemType));/*返回L中第1个与e满足关系compare()的数据元素的位序*/
Status PriorElem(LinkList *L,ElemType cur_e,ElemType *pre_e);/*返回前驱的值 */
Status NextElem(LinkList *L,ElemType cur_e,ElemType *next_e);/*返回后继的值*/
Status ListInsert(LinkList *L,int i,ElemType e);/*在带头结点的单链表中第i个位置之前插入元素e*/
Status ListDelete(LinkList *L,int i,ElemType *e);/*在带头结点的单链表中，删除第1个元素，用e返回其值勤*/
void ListTraverse(LinkList *L,void(*visit)(ElemType));/*依次对L的每个元素调用函数visit() */
void print(ElemType e);
Status equal(ElemType c1,ElemType c2);
void Listprint(LinkList *L);
void Merge(LinkList *La,LinkList *Lb);/*两个集合的交集 */
void Merge1(LinkList *La,LinkList *Lb);/*利用函数实现集合的交集*/
/*void Differ(LinkList La,LinkList Lb); *//*两个集合的差集        */
void Union1(LinkList *La,LinkList *Lb);/*利用函数实现集合的并集   */
void Differ(LinkList *La,LinkList *Lb);/*利用函数实现集合的差集   */

LinkList *InitList(LinkList *L)/*构造一个空链链表*/
{ 
	L=(LinkList*)malloc(sizeof(LinkList));/*产生头结点,并使L指向此头结点*/
	if(L==NULL) exit(OVERFLOW);
	L->next=NULL;
	return L;
}
void DestroyList(LinkList *L)/*销毁L*/
{  
	LinkList *q;
	while(L!=NULL)/*L指向结点*/
	{ 
		q=L->next;/*q指向首元结点*/
		free(L);
		L=q;/*L指向原首结点*/
	}
}
void ClearList(LinkList *L)
{ /*将表清空 */
	LinkList *p=L->next;
	L->next=NULL;
	DestroyList(p);/*销毁P所指向的单链表 */
}
Status ListEmpty(LinkList *L)
{ /*表为空则返回TRUE，否则返回FALSE */
	if(L->next!=NULL) return FALSE;
	else return TRUE;
}
int ListLength(LinkList *L)
{/*返回表中的元素的个数*/
	int i=0;
	LinkList *p=L->next;/*P指向第一个结点*/
	while(p!=NULL)/*未到表尾*/
	{ 
		i++;
		p=p->next;
	}
	return i;
}

Status GetElem(LinkList *L,int i,ElemType *e)/*当第i个元素存在时，将其值赋给e */
{
	int j=1;/*计数器初值为1*/
	LinkList *p=L->next;/*p指向第一个结点*/
	while((p!=NULL)&&(j<i))/*顺指针向后查找，直到找到p指向第i个结点*/
	{
		j++;
		p=p->next;
	}
	if((p==NULL)||(j>i)) return ERROR;/*p==NULL说明L中节点数目小于i，若j>i成立，则必有i<1时，i越界*/
	(*e)=p->data;
	return OK;
}
int LocatElem(LinkList *L,ElemType e,Status(*compare)(ElemType,ElemType))
{   /*返回表中第1个数据域与e满足关系compare()的数据关系的节点的位序 */
	int i=0;/*计数器初值为0 */
	LinkList *p=L->next;
	while(p!=NULL)/*未到表尾   */
	{
		i++;
		if(compare(p->data,e))/*找到这样的元素*/
			return i;/*返回其位序*/
		p=p->next;
	}
	return 0;/*不存在相应节点*/
}
Status PriorElem(LinkList *L,ElemType cur_e,ElemType *pre_e)
{ /*返回前驱 */
	LinkList *q,*p=L->next;/*p指向第一个元素*/
	while(p->next!=NULL)/*p指的结点有后继 */
	{ 
		q=p->next;/*q指向p的后继   */
		if(q->data==cur_e)/*p的后继为cur_e  */
		{ 
			(*pre_e)=p->data;
			return OK;
		}
		p=q;/*p的后继不为cur_e,向后移*/
	}
	return ERROR;
}
Status NextElem(LinkList *L,ElemType cur_e,ElemType *next_e)
{ /*返回后继 */
	LinkList *p=L->next;
	while(p->next!=NULL)/*p所指结点的后继 */
	{ 
		if(p->data==cur_e)  
		{
			(*next_e)=p->next->data;
			return OK;
		}
		p=p->next;
	}
	return ERROR;
}

Status ListInsert(LinkList *L,int i,ElemType e)
{ 
	/*在第i个位置之前插入元素e */
	int j=0;/*计数器初值为0*/
	LinkList *s,*p=L;/*p指向头结点*/
	while((p!=NULL)&&(j<i-1))/*寻找第i个结点*/
	{ 
		j++;
		p=p->next;
	}
	if((p==NULL)||(j>i-1)) return ERROR;/*p==NULL说明L中节点数目小于i，若j>i成立，则必有i<1时，i越界*/
	s=(LinkList*)malloc(sizeof(LinkList));/*生成新的结点*/
	s->data=e;
	s->next=p->next;/*新结点指向原第i个结点*/
	p->next=s;/*原第i-1个结点指向新结点*/
	return OK;
}
Status ListDelete(LinkList *L,int i,ElemType *e)
{/*在带头结点的单链表中删除第i个元素，并用e返回其值*/
	int j=0;/*计数器初值为0*/
	LinkList *q,*p=L;/*p指向头结点*/
	while((p->next!=NULL)&&(j<i-1))/*寻找第i个结点，并用p指向其前驱*/
	{
		j++;
		p=p->next;
	}
	if((p->next==NULL)||(j>i-1)) return ERROR;/*p->next==NULL说明L中节点数目小于i，若j>i成立，则必有i<1时，i越界*/
	q=p->next;
	p->next=q->next;
	(*e)=q->data;
	free(q);
	return OK;
}

void ListTreaverse(LinkList *L,void(* visit)(ElemType))
{/*依次对L的每个数据元素调用函数visit()*/
	LinkList *p=L->next;/*p指向第一个元素 */
	while(p)
	{
		visit(p->data);
		p=p->next;
	}
	printf("\n");
}

Status equal(ElemType c1,ElemType c2)
{  /*判断两个数是否相等 */
	if(c1==c2)
		return TRUE;
	else
		return FALSE;
}
void print(ElemType e)
{ 
	printf("%d",e);
}

void Listprint(LinkList *L)/*输出单链表*/
{  
	LinkList *p=L->next;
	while(p!=NULL)
	{  
		printf("%d",p->data);
		p=p->next;
	}
	printf("\n");
}

void Merge(LinkList *La,LinkList *Lb)/*两个集合的交集*//*存在错误小缺陷,,重复元素的问题*/
{  
	LinkList *pa,*pb;
	/*pa=La->next; */
	/*pb=Lb->next;*/
	for(pa=La;pa->next!=NULL;pa=pa->next)
		for(pb=Lb->next;pb->next!=NULL;pb=pb->next)
		{
			if(pa->data==pb->data)
				printf("%d",pa->data);
		}
}

void Merge1(LinkList *La,LinkList *Lb)/*利用函数实现集合的交集*/
{
	ElemType e=0;
	int La_len,Lb_len;
	int i;
	La_len=ListLength(La);
	Lb_len=ListLength(Lb);
	for(i=1;i<=Lb_len;i++)
	{
		GetElem(Lb,i,&e);
		if(LocatElem(La,e,equal))
			printf("%d",e);
	}
}


void Union1(LinkList *La,LinkList *Lb)/*利用函数实现集合的并集*/
{ 
	ElemType e=0;
	int La_len,Lb_len;
	int i;
	La_len=ListLength(La);
	Lb_len=ListLength(Lb);
	for(i=1;i<=Lb_len;i++)
	{
		GetElem(Lb,i,&e);/*取表中第i个元素赋给e */
		if(LocatElem(La,e,equal)==0)/*表La中不存在和e相同的元素*/
			ListInsert(La,++La_len,e);/*在表la中插入元素e */
	}
	Listprint(La);
}

void Differ(LinkList *La,LinkList* Lb)/*利用函数实现集合的差集 */
{
	ElemType e=0;
	int La_len,Lb_len;
	int i;
	La_len=ListLength(La);
	Lb_len=ListLength(Lb);
	for(i=1;i<=La_len;i++)
	{ 
		GetElem(La,i,&e);/*取表中第i个元素赋给e */
		if(LocatElem(Lb,e,equal)==0)/*表Lb中不存在这样的元素 */
			printf("%d",e);
	}
}
void main()
{  
	LinkList *L,*La,*Lb;
	int i=0,k=0,j=0,e1=0,e=0;
	L=NULL;
	La=NULL;
	Lb=NULL;
	L=(LinkList*)malloc(sizeof(LinkList));
	L=InitList(L);/*初始化链表 */
	k=ListEmpty(L);
	printf("L为空表?k=%d(k=1,是;k=0,否)",k);
	printf("\n");
	for(i=1;i<=5;i++)
		ListInsert(L,1,i);
	printf("线性表为L=");
	/*ListTraverse(L,print);*/
	Listprint(L);
	printf("\n表的长度为%d\n",ListLength(L));
	/*删除元素 */
	k=ListDelete(L,3,&e);
	if(k==ERROR)  
		printf("删除不成功");
	else 
		printf("删除元素成功，其值为%d",e);
	printf("\n");
	/*判断表是否为空 */
	k=ListEmpty(L);
	printf("L为空表?k=%d(k=1,是;k=0,否)",k);
	printf("\n");
	/*清空表后*/
	ClearList(L);/*清空表 */
	printf("表清空后长度为%d",ListLength(L));
	Listprint(L);
	/*再次判断表是否为空*/
	k=ListEmpty(L);
	printf("L为空表?k=%d(k=1,是;k=0,否)",k);
	printf("\n");
	for(j=1;j<=10;j++)
		ListInsert(L,j,j);/*在L的表尾插入j */
	printf("重新插入元素之后表变为:");
	Listprint(L);
	/*判断前驱*/
	for(j=1;j<=ListLength(L);j++)
	{
		GetElem(L,j,&e);/*把L中第j个元素赋给e */
		k=PriorElem(L,e,&e1);/*求e的前驱，并赋给e1*/
		if(k==ERROR)
			printf("元素%d无前驱\n",e);
		else
			printf("元素%d的前驱为%d\n",e,e1);
	}
	printf("\n");
	/*判断后继*/
	for(j=1;j<=ListLength(L);j++)
	{ 
		GetElem(L,j,&e);/*把L中第j个元素赋给e*/
		k=NextElem(L,e,&e1);/*求e的前驱，并赋给e */
		if(k==ERROR)
			printf("元素%d无后继\n",e);
		else 
			printf("元素%d的后继为%d\n",e,e1);
	} 
	/*两个单链表的操作*/
	La=InitList(La);
	for(i=1;i<=5;i++)
		ListInsert(La,i,i);
	printf("单链表La:");
	Listprint(La);
	printf("\n");
	Lb=InitList(Lb);
	for(i=1;i<=5;i++)
		ListInsert(Lb,i,2*i);
	printf("单链表Lb:");
	Listprint(Lb);
	printf("\n");
	/*两个集合的交集*/
	printf("两个集合的交集:");
	Merge(La,Lb);
	printf("\n");
	/*利用函数实现集合的交集 */
	printf("利用函数实现集合的交集:");
	Merge1(La,Lb);
	printf("\n");
	/*两个集合的差集 */
	printf("利用函数实现集合的差集La-Lb:");
	Differ(La,Lb);
	printf("\n");
	/*两个集合的并集*/
	printf("两个集合的并集:");
	Union1(La,Lb);
	getch();
}

单链表排序交换节点算法,布布扣,bubuko.com

单链表排序交换节点算法

原文：http://blog.csdn.net/ouchengguo/article/details/24195325