jiegou.h

多关键字排序算法,按照多个关键字来排序的算法,关于算法和数据结构的原代码

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include <malloc.h>
#include "time.h"
//#include <conio.h>	// getch
#include <dos.h>   //getime()


#define MAX_NUM_OF_KEY 8            //关键字项数的最大基数，本设计中只用到5
#define RADIX 10                    //关键字基数，此时是十进制整数的基数
#define MAX_SPACE 10000

typedef int KyeType;
#define CHINESE 1      //语文
#define MATH 2         //数学
#define ENGLISH 3      //英语
#define XX 4           //x科  
#define TOTAL 5        //总分

typedef struct{
	char name[4];
	KyeType keys[MAX_NUM_OF_KEY+1];            //关键字
	int next;                                  //
}SLCell;                                       //静态链表的节点类型

typedef struct{
	SLCell r[MAX_SPACE+1];
	int keynum;                                //记录的当前关键字个数，这里是科目
	int recnum;                                //静态链表的当前长度
}SLList;                                       //静态链表类型  

typedef int ArrType[RADIX];                    //指针数组内容 

clock_t start,end; //时间变量，精确到ms！


SLList L, copy;               //用L创建一个副本copy，用来回复被排序的L，



void InitSLList(SLList &L,int num)             //num为关键字个数
{
	L.recnum=num;
	L.keynum=5;
}

//////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////内部稳定简单选择排序//////////////////////////////////////////////
int SelectMaxKey(SLList L,int key,int i)     //用于简单排序
{
	int k,max=i;

	for( k=i; k<=L.recnum; k++ )
	{
		if(L.r[k].keys[key] > L.r[max].keys[key])
		{
			max=k;
		}
	}
	return max;
}
void SteadySort(SLList &L, int key)          //稳定排序  选择关键字key排序    
{
	int i,j;
	SLCell T;
	for( i=1; i<=L.recnum; ++i )                //简单选择排序
    {
		j=SelectMaxKey(L,key,i);
		if(i!=j) 
		{
			T=L.r[i]; L.r[i]=L.r[j]; L.r[j]=T;		
		}
	}
}

/////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////　基数排序　　LSD　///////////////////////////////////////////////
int ord(int score , int i)
{
	int j;
	if(i==1) j=score%100%10;
	else 
		if(i==2) j=score%100/10;
		else j=score/100;
	return j;
}

void Distribute(SLCell r[], int i,ArrType &f, ArrType &e, int key)
{
	int j,p;
	for(j=0; j<RADIX; j++){ f[j]=0; e[j] = 0 ; }
	for(p=r[0].next; p; p=r[p].next)           //最后r[L.recnum].next是以0结束的
	{		
		j=ord(r[p].keys[key],i);
		if(!f[j]) f[j]=p;
		else 
		r[e[j]].next=p;

		e[j]=p;
	}
}

int succ(ArrType f,int &j)
{	

	while( !f[j] && j<RADIX ) 
	{j++;} 
	return j;
}

void Collect(SLCell r[], int i, ArrType f, ArrType e)
{
	int j=0,t=0;
	for(j=RADIX-1; j>=0 ; j-- )
	{
		if(f[j])
		{
			r[t].next=f[j];
			t=e[j];
		}
	}
	r[t].next=0;

/*	j=succ(f,j);   //找到第一个非空子表，succ为求后记函数  这种方法不好，麻烦 效率没有上面的高！
    printf("\tjjj=%d\n",j);	
	r[0].next=f[j]; t=e[j];                    //r[0].next指向第一个非空子表中第一个节点
	printf("r[0].next=%d\t",r[0].next);
	while( j<RADIX )
	{	
		j++;

		for(j=succ(f,j); j<RADIX-1&&!f[j]; j=succ(f,j)) ;  //找到下一个非空子表
		if(f[j]) 
		{
			r[t].next=f[j];
			printf("r[%d].next=%d\tf[%d]=%d\n",t,r[t].next,j,f[j]);
			t=e[j]; 
		}
	}
*/
}

void RadixSort(SLList &L,short key)              // 用基数排序“分配”和“收集”
{
	ArrType f,e; 
	int i;
	for( i=1; i<=3; i++ )
	{	
		Distribute(L.r,i,f,e,key);
		Collect(L.r,i,f,e);
	}
}