lianbiao.cpp

C＋＋的链表排序算法

// lianbiao.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#define NULL 0

typedef struct  std 
{int v;
 struct std * next;
} STD;

STD * delnode(STD * h , STD * maxp);
STD * sortnode(STD *st);

void  main()
{	int a[10]={241,5,56,985,456,78,94,26,98,266};  
	int n=10;
	int i,j;

	STD st[10],*head=st;

	for (i=0;i<n;i++) 
	{ st[i].v=a[i];       //给结构赋值
	  if (i==n-1) 
	     {st[i].next= NULL ; }  
	  else 
	  {st[i].next=&st[i+1];}

	   printf("%d  %d  ",st[i].v,st[i].next); //打印结构数组内容 
	}
    
	head=sortnode(st);
    //head= delnode(st , &st[8]);
	while (head!=NULL)
	{    printf("\n%d  ",head->v);
		head=head->next ;
	}
	
} 

STD * sortnode(STD *st)
{	STD * h , *t, *maxp , *head=NULL, *end=NULL;	
	int maxn;

	h=st;  // h ：动态头指针
	
	while(h !=NULL)                 //只要当前链中不为空就循环
	{
		t=h;  // t ：临时指针

		maxn=t->v; maxp=t;          //把当前t中的值作为最大
		while (t->next !=NULL)      //只要t后面还有节点就循环
		{   t=t->next ;		    	//t往后移动一个
			if (t->v > maxn)     	//如果t中的值大于maxn，则记下其值和位置		
				{	maxn=t->v;
					maxp=t;} 
		}                            //找出当前头开始在链中最大节点 maxp

		h=delnode(h,maxp);           //删除maxp节点,返回剩下的链表
		maxp->next=NULL;			 //maxp  的下节点设为空
		if (head==NULL) {head=maxp;end=maxp;}   //第一个就放入头中，并记下尾部位置
		else {end->next=maxp;end=end->next;}    //非第一个就把maxp接在尾部
	}                                           //继续循环
	
	return head;
}


STD * delnode(STD * h , STD * maxp)      //删除一个节点，返回剩下的链表首地址
{   STD * t;
	

	if (h==maxp)                         //如果maxp 等于 头，
	{	t= maxp-> next;					 //就把下一个返回
		maxp-> next=NULL;
		 return t;
		}
	else								//否则
	{   t=h;
		while(t->next!=maxp ) {t=t->next;}   //找到maxp 的前节点t   
		t->next = maxp->next ;                //删除maxp，maxp后面的接到t后面
		maxp->next = NULL;
		return h;							  //链首依然是h ,返回
	}
}