paixu.cpp

学习VC++的好资料

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <limits.h>
#define MAX 10  //用于基数的排序
int com_number=0,exc_number=0;//用于比较的次数，交换的次数

//定义结点，用于基数排序
typedef struct node {
	int key;//用于存储元素
	int data;//用于存储信息0
	struct node *next;
}*lnode;

//用于锦标排序
typedef struct {
	int data;//用于存储信息
	int key;//用于存储元素
	int parent,lchild ,rchild;
}HTNode,*HuffmanTree;//动态分配数组的空间存储树

#define N 3500000  //总的空间的大小
typedef int Keytype;
typedef struct {
	Keytype key;//用于存储元素
	Keytype data;//用于存储信息
}RecType;

typedef struct {
	RecType r[N+1];//静态的数组
	int length;//表的长度
}SeqList;//SeqList为顺序表类型，表中第一号单元为哨兵

SeqList L;//定义一个链表类型

FILE *Create_file(FILE *fp)
{//创建文件的函数
	char file[50];
	printf("请输入保存结果路径:");
	scanf("%s",file);
	if ((fp=fopen(file,"w"))==NULL){
		printf("cannot open name!\n");
		exit(1);
	}
	return fp;//返回文件的地址
}

FILE *Open_file()
{//打开所创建的文件
	FILE *fp;
	char file[50];
	printf("请输入已有的文件名:");
	scanf("%s",file);
	if ((fp=fopen(file,"r"))==NULL)
	{
		printf("cannot open name!\n");exit(1);
	}
	return fp;//返回文件的地址
}

void create_sq(SeqList &L)
{//方法二：初始化，把文件中的数存到表中
	FILE *fp=Open_file();
	int i,m,n;
	L.length=0;
	while (!feof(fp))
	{
		i=fscanf(fp,"%d (%d)",&m,&n);//从文件中读入一个数放入数组s中
	    if (i==-1)  break;//用于结束循环
		L.r[++L.length].key=m;//0号空间未用 
        L.r[L.length].data=n;
	}
	fclose(fp);//关闭文件
}

//锦标排序的算法
void Select(HuffmanTree HT,SeqList &L,int n)
{//从剩下的元素中，选择最小的元素放入树的根中
	if (n==2*L.length-1) return;
    if (HT[HT[HT[n].parent].lchild].key<HT[HT[HT[n].parent].rchild].key)
		HT[HT[n].parent].key=HT[HT[HT[n].parent].lchild].key;
	else  HT[HT[n].parent].key=HT[HT[HT[n].parent].rchild].key;
	Select (HT,L,HT[n].parent);//递归调用选择函数
}

void Printf_Sort_Tree (HuffmanTree HT,SeqList &L)
{//打印锦标排序结果
	FILE *fp=Create_file(fp);
	int n=2*L.length-1;
	for (int i=1; i<=L.length; i++,n=2*L.length-1){
		while (n>L.length){//从根开始遍历到叶子，并输出最小的元素
            if ( HT[HT[n].lchild].key==HT[n].key )
                n=HT[n].lchild;
		    else n=HT[n].rchild;
            com_number++;
			exc_number++;
		}      
		fprintf(fp,"%d (%d)\n",HT[n].key,HT[n].data);//把最小的元素存入文件中
        HT[n].key=LONG_MAX;//把最小的元素的结点赋为最大的值	
		Select (HT,L,n);
	}
	printf("交换次数：%d\n",exc_number+1);
	printf("比较次数：%d\n",com_number);
	printf("数据个数:\n");
	printf("%d\n",L.length);//输出总的元素的个数
	fclose(fp);
}

int Select_min (HuffmanTree HT,int t)
{//　找出相邻两个结点中的最小元素
	com_number++;
 	if ( HT[t].key<HT[t+1].key )
		return t;
    else  return t+1;
}

void Create_Tree (HuffmanTree HT,SeqList &L)
{//存放n个字符的权值(均大于0)，构造树HT
	int m,i,t=1,j,n;
	com_number=0;exc_number=0;
	HuffmanTree p;
	if( L.length<= 1)
		return ;
    m= 2*L.length-1;
	HT= (HuffmanTree) malloc ( (m+1)*sizeof (HTNode) );//0号单元未用
	for ( p=HT+1,i=1; i <= L.length; i++,++p )//给表赋初值
	{
		p->key=L.r[i].key;
		p->data=L.r[i].data;
		p->parent=0;
		p->lchild=0;
		p->rchild=0;
	}
	for (; i <= m; i++,++p)
	{
		p->key=0;
		p->parent=0;
		p->lchild=0;
		p->rchild=0;		
	}
    for (j=1,i=L.length+1; i<=m; i++,j++,t=2*j-1)//建锦标排序树
	{
        n=Select_min(HT,t);//调用选择的函数，选择相邻两个结点最小的元素，其序号为n
		HT[t].parent=i;// 记录父元素的位置
		HT[t+1].parent=i;
		HT[i].lchild=t;//记录左和右孩子的位置
		HT[i].rchild=t+1;
		HT[i].key=HT[n].key;
	}
	Printf_Sort_Tree(HT,L);//调用打印的函数
}

void Printf_Sort (SeqList &L)
{//打印各种排序的结果
	FILE *fp=Create_file(fp);
	for (int i=1; i<=L.length; i++){
		fprintf(fp,"%d (%d)\n",L.r[i].key,L.r[i].data);//把信息存入文件中
	}
	printf("交换次数为：%d\n",exc_number);
	printf("比较次数为：%d\n",com_number);
	printf("数据个数:\n");
	printf("%d\n",L.length);//输出总的元素的个数
	fclose(fp);
}

//堆排序的算法　
void Heapify(SeqList &L,int s,int m)
{
	int j;
    L.r[0]=L.r[s];//把数临时放入0号单元中
	exc_number+=2;;
	j=2*s;
	while ( j<=m){//把最大的数放入树的根中
		if ( L.r[j].key<L.r[j+1].key&&j<m ) j++;//比较左右的孩子的大小
		if ( L.r[0].key>L.r[j].key ) break;//将根和左右孩子中的最大的数比较
		L.r[s]=L.r[j];
		s=j;
		j=j*2;
		com_number+=2;
		exc_number++;
	}
	L.r[s]=L.r[0];
}

void BuidingHeap(SeqList &L,int n)
{//建堆的函数
	int i;
	for ( i=n/2;i>0;i-- )
        Heapify(L,i,n);
}

void Heap_Sort(SeqList &L)
{//重新调整堆
	int i;
	com_number=0;exc_number=0;
	BuidingHeap(L,L.length);
	for ( i=L.length;i>1;i--){
		L.r[0]=L.r[1];
		L.r[1]=L.r[i];
		L.r[i]=L.r[0];
		Heapify(L,1,i-1);
	}
}

//归并排序的算法
void Merge(SeqList &L,int low,int m,int high)
{
	int i=low,j=m+1,p=0;
	int *R1,*R2;
	R1=(int *)malloc((high-low+1)*sizeof(int));//用于保存数项
	R2=(int *)malloc((high-low+1)*sizeof(int));//用于保存信息项
	if (!R1)
		return;
	for (;i<=m&&j<=high;){//比较两边的数，并把最小的数放在r1中
		R1[p]=(L.r[i].key<=L.r[j].key)?L.r[i].key:L.r[j].key;
		R2[p++]=(L.r[i].key<=L.r[j].key)?L.r[i++].data:L.r[j++].data;
	}//end for
	for (;i<=m; R2[p++]=L.r[i++].data)//将剩下的数放入r1中
		R1[p]=L.r[i].key;
	for (;j<=high; R2[p++]=L.r[j++].data)
		R1[p]=L.r[j].key;
	for (p=0,i=low; i<=high; L.r[i].data=R2[p],p++,i++)//把排好的数重新放入表中
		L.r[i].key=R1[p];
}

void Merge_SortDC(SeqList &L,int low,int high)
{//调用结合的函数
	int mid;
	if (low<high)
	{
		mid=(low+high)/2;
		Merge_SortDC(L,low,mid);
		Merge_SortDC(L,mid+1,high);
		Merge(L,low,mid,high);
	}
}

//基数排序的算法
lnode my_input(int *d)
{//初始化，创建动态的链表
	int i,n;
	lnode head,temp,terminal;
	FILE *fp=Open_file();
	char s[MAX+1];
	head=NULL;
	*d=0;//用于存放最大数的个数
	terminal=NULL;
	while (!feof(fp))
	{
		i=fscanf(fp,"%s (%d)",s,&n);//把文件中的数放入数组s中
	    if (i==-1)  break;//用于结束循环
		temp=(lnode)malloc(sizeof(struct node));//用于申请动态的空间
		if ((int)strlen(s)>*d)
			*d=strlen(s);//判断有多少个字符
		temp->key=atoi(s);
		if (head==NULL)//连接各结点
		{
			head=temp;
			terminal=temp;
		}
		else
		{
			terminal->next=temp;
			terminal=temp;
		}
        temp->data=n;//把数后的信息放于结点中
	}
	terminal->next=NULL;
	fclose(fp);
	return head;
}

void my_output(lnode h)
{//输出链表的函数
	lnode t=h;
	int i=0;//用于统计总元素的个数
	FILE *fp=Create_file(fp);
	while (h!=NULL)
	{
		i++;
		fprintf(fp,"%-7d(%d)\n",h->key,h->data);//把结点中的信息放入文件中
		h=h->next;
	}
	h=t;// 用于释放空间
	printf("数据个数:\n");
	printf("%d\n",i);
	fclose(fp);
}

lnode Radix_Sort(lnode head,int d)
{//基数排序的算法
	lnode p,q,h,t;
	int i,j,x,radix=1;
	h=(lnode)malloc(10*sizeof(struct node));//头结点
	t=(lnode)malloc(10*sizeof(struct node));// 尾结点
	for (i=d; i>=1; i--){
		for (j=0; j<=9; j++){//将头和尾结点赋为0
			h[j].next=NULL;
			t[j].next=NULL;
		}
		p=head;
		while(p!=NULL){//从个位向高位取余，放入各单元中
			x=((p->key)/radix)%10;
			if (h[x].next==NULL){
				h[x].next=p;
				t[x].next=p;
			}
			else{
				q=t[x].next;
				q->next=p;
				t[x].next=p;
			}
			p=p->next;
		}//end while
		j=0;//开始从0到9收集元素
		while(h[j].next==NULL)
			++j;
		head=h[j].next;
		q=t[j].next;
		for (x=j+1; x<=9; x++)
			if (h[x].next!=NULL){
				q->next=h[x].next;
				q=t[x].next;
			}
		q->next=NULL;
		radix*=10;
	}//end for 
	return head;
}

void my_free(lnode h)
{//释放各结点的空间
	lnode temp=h;
	while(temp){
		h=temp->next;
		free(temp);
		temp=h;
	}
}

//快速排序的算法
int Partition (SeqList &L,int low,int high)
{
	Keytype pivotkey=L.r[low].key;//用于子表中的第一个记录和作为枢轴
    L.r[0]=L.r[low];
	while ( low< high){//从表中的两端向中间扫描
		for (; low < high && L.r[high].key >= pivotkey; com_number++) --high;
        L.r[low] = L.r[high];//将比枢轴小的记录移动到高端
		for (; low < high && L.r[low].key <= pivotkey; com_number++) ++low;
		L.r[high] =L.r[low];//将比枢轴大的记录移动到低端
		exc_number+=2;
	}
	L.r[low] = L.r[0];//枢轴记录到位
	exc_number++;
	return low;//返回枢轴记录位置
}

void Qsort (SeqList &L,int low,int high)
{
	int pivotloc;
	if (low < high ){//长度大于1，就比较
		pivotloc = Partition ( L,low,high );//将数组一分为二
		Qsort ( L,low,pivotloc-1);//对低子表递归排序
		Qsort (L,pivotloc+1,high);//对高子表递归排序
	}
}

void QuickSort (SeqList &L)
{//对顺序表L作快迅的排序
	exc_number=0;com_number=0;
	Qsort (L,1,L.length);
}

//希尔排序的算法
void shellpass(SeqList &L,int d,int n)
{//希尔排序中的一趟排序　，d为当前的增量
	int i,j;
	for(i = d+1;i <= n;i++)//将e[d+1,   n]分别插入各组当前的有序的区
		if(L.r[i].key<L.r[i-d].key){
			L.r[0]=L.r[i];//的e[0]中只是暂时的存单地元，不是哨兵
			j=i-d;
			do{//查找e[i]的插入位置
				L.r[j+d]=L.r[j];//后移记录
				j=j-d;//查找前一记录
				exc_number++;
				com_number++;
			}while(j>0&&L.r[0].key<L.r[j].key);
			L.r[j+d]=L.r[0];//插入e[i]到当前的正确的位置上
			exc_number++;
			com_number++;
		}//end if 
}

void shellsort(SeqList &L)
{//
	int increment=L.length;//增量初值，不妨设为n>0
	exc_number=0;com_number=0;
	do{
		increment=increment/3+1;//求下一增量
		shellpass(L,increment,L.length);//一趟增量为increment的shell 插入排序
	}while(increment>1);
}

//信息函数
void message ()
{
    printf ("--------------------------------------------\n");
	printf ("功能选项：            0.退出             \n");
	printf ("          1.锦标排序  2.堆排序 3.归并排序 \n");
	printf ("          4.希尔排序  5.快速排序  6.基数排序\n");
    printf ("--------------------------------------------\n");
}

//主函数
void main()
{
	HTNode HT;//各元素的初始化
	
	lnode h;//定义一个结点的类型
	int c,d;
	message();
	while (1){
		printf ("请选择一个上面的选项(0-6):");
		scanf ("%d",&c);
		switch (c){
		case 5://调用锦标排序的函数
			create_sq(L);//调用创建的函数
            Create_Tree (&HT,L);
			break;
		case 2://调用堆排序的函数
			create_sq(L);//调用创建的函数
			Heap_Sort(L);
	        Printf_Sort(L);
			break;
		case 3://调用归并排序的函数
			create_sq(L);//调用创建的函数
			Merge_SortDC(L,1,L.length);
	        Printf_Sort(L);
			break;
		case 6://调用基数排序的函数
			h=my_input(&d);
			h=Radix_Sort(h,d);
	        my_output(h);
	        my_free(h);
			break;
		case 1://调用快速排序的函数
			create_sq(L);//调用创建的函数
			QuickSort(L);
	        Printf_Sort(L);
			break;
		case 4://调用希尔排序的函数
			create_sq(L);//调用创建的函数
			shellsort(L);//调用比较的函数
            Printf_Sort(L);//输出结果
			break;
		}//end switch
		if (c==0) {//结束循环的语句
			printf ("操作结束!\n");
			break;
		}//end if 
	}//end while
}