data_structures.cpp

用C＋＋实现的数据结构常用排序以及HUFFMAN编码解码和最短路径算法的小程序

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
/******************排序相关***********************/
#define ARRMAX 1000000
long ts,tc1,tc2,tc3,i;        //用于计算时间
int sourceArr[ARRMAX],arrLength;
int resultArr[ARRMAX];
int temp[ARRMAX];             //归并排序时要使用
int b[ARRMAX];                //基数排序时要用
void sortmenu();
void insertSort();
void mergeSort();
void merge(int resultArr[],int left,int right);
void quickSort();
void quick(int a[],int i,int j);
int  partition(int a[],int l,int r,int pivot);
void heapSort();
void heap(int*heap,int index);
void createHeap(int *heap,int root,int index);
void radixSort();
void radix(int a[],int n,int k,int r);
/****************最短路径相关*********************/
#define MAXNODES 1024
int dist[MAXNODES][MAXNODES];
#define INFINITY 1000000
int  dijkstra();
void shortctl();
int shortestpath(int n,int s,int t,int path[]);
/***************huffman树相关*********************/
#define MAX 999
#define MAXNODE 1024
#define CODE_LENGTH 128
/*****全局变量******/
int path[CODE_LENGTH];
int psuffix;
int n;
int root;
int curIndex;
struct tNOde{
	char name;
    int flag;
	int lchild;
    int rchild;
	int parent;
	int weight;
}hTree[MAXNODE];
/*******函数********/
void huffman();
void huffmanTree();
void code();
void concat(int ch);
char get_yn();
/********************其他辅助函数*********************/ 
int  mainMenu();
int  quit();
int  limitInput(int);
int  inputArr(int sourceArr[]);
void copyArr(int from[],int to[],int length);
void swap(int arr[],int n,int m);
void printArr(int array[],int length);

/****主函数****/
void main(){
   mainMenu();
}

/*程序主界面*/
int mainMenu(){
   int  choice;
   printf("\n   ******************************************\n");
   printf("\t          <主界面>                   \n");
   printf("\t-------------------------------      \n");
   printf("\t1.----排序                           \n");
   printf("\t2.----Huffman编码和解码              \n");
   printf("\t3.----Dijkstra最短路径               \n");
   printf("\t4.----退出                           \n");
   printf("\t-------------------------------      \n");
   printf("   ******************************************\n");
   printf("   请选择操作类型( 1-4)：");
   choice = limitInput(4);
   if(choice == 1) {sortmenu();}
   else if(choice == 2) {huffman();getch();}
   else if(choice == 3) {shortctl();}
   else if(choice == 4) return 0;
   return 1;
}

/*排序界面*/
void sortmenu() {
   int  choice;
   printf("\n   ******************************************\n");
   printf("\t           <排序界面>          \n");
   printf("\t-------------------------------\n");
   printf("\t1.----插入排序                 \n");
   printf("\t2.----归并排序                 \n");
   printf("\t3.----快速排序                 \n");
   printf("\t4.----堆排序                   \n");
   printf("\t5.----基数排序                 \n");
   printf("\t6.----返回                     \n");
   printf("\t7.----退出                     \n");
   printf("\t-------------------------------\n");
   printf("   ******************************************\n");
   printf("   请选择操作类型( 1-7)：");
   
   choice = limitInput(7);
   if(choice == 1) insertSort(); 
   if(choice == 2) mergeSort();  
   if(choice == 3) quickSort();
   if(choice == 4) heapSort();
   if(choice == 5) radixSort();
   if(choice == 6) mainMenu();
   if(choice == 7) exit(EXIT_SUCCESS);
   sortmenu();
}

/*插入排序及控制*/   
void insertSort(){
	int i,j;
	char ch;
	printf("   是否进行排序步骤演示?请选择 (y/n):  ");
    printf("%c\n",(ch = getch()));
	if(ch == 'y'){
		arrLength = inputArr(sourceArr);
	    copyArr(sourceArr,resultArr,arrLength);
 			  
    	printf("\n^_^你好，下面是插入排序!");
		printf("\n-------------------------------------------------------------------------------");
		printf("\nstep0:");
		printArr(sourceArr,arrLength);
    
		for(i=1;i<arrLength;i++){
			for(j=i;(j>0) && (resultArr[j-1] > resultArr[j]);j--)
	 	        swap(resultArr,j,j-1);
	
			printf("step%d:",i);
     	   printArr(resultArr,arrLength);
		}
  	  printf("-------------------------------------------------------------------------------");
  	  printf("\n注：插入排序逐个处理待排序的记录，每个新记录跟它前面\n"
    	  "    的子序列进行比较，将它插入到子序列中正确的位置\n");
    }

    
        ts = clock();
        for(i=0;i<ARRMAX/100;i++)
           sourceArr[i] = rand();
        tc1=clock()-ts;
        printf("\n   给一个长度 %ld 的数组随机赋值所用时间为: %ld (ms) \n",ARRMAX/100,tc1);
    	
        ts = clock();
        for(i=0;i<ARRMAX/100;i++)
           resultArr[i] = sourceArr[i];
        tc2 = clock() - ts;
          printf("   复制长度为 %d  数组到另一数组所用时间为: %ld (ms) \n",ARRMAX/100,tc2);

        ts = clock();
        for(i=1;i<ARRMAX/100;i++)
    	    for(j=i;(j>0) && (resultArr[j-1] > resultArr[j]);j--)
	             swap(resultArr,j,j-1);
        tc3 = clock() - ts;
          printf("   用插入排序法排序个 %ld 的数组所用时间为: %ld (ms) \n",ARRMAX/100,tc3);   
        

}

/*归并排序控制*/
void mergeSort(){		
    char ch;
	printf("   是否进行排序步骤演示?请选择 (y/n):  ");
   	printf("%c\n",(ch = getch()));
	if(ch == 'y'){
        arrLength = inputArr(sourceArr);
    	copyArr(sourceArr,resultArr,arrLength);
    	printf("\n^_^你好，下面是归并排序!");
    	printf("\n-------------------------------------------------------------------------------");
    	printf("\nsourceArr:");
        printArr(sourceArr,arrLength);
    	merge(resultArr,0,arrLength-1);
    	printf("resultArr:");
    	printArr(resultArr,arrLength);
    	printf("-------------------------------------------------------------------------------");
    	printf("\n注：归并排序将一个序列分成两个等长子序列，为每一个子序列排序然\n"
			   "    后将它们合并成一个序列。合并两个有序子序列的过程称为归并。\n");
	}
	
         ts = clock();
         for(i=0;i<ARRMAX;i++)
            sourceArr[i] = rand();
         tc1=clock()-ts;
         printf("\n   给一个长度 %ld 的数组随机赋值所用时间为: %ld (ms) \n",ARRMAX,tc1);
	
         ts = clock();
         for(i=0;i<ARRMAX;i++)
            resultArr[i] = sourceArr[i];
         tc2 = clock() - ts;
           printf("   复制长度为 %d 数组到另一数组所用时间为: %ld (ms) \n",ARRMAX,tc2);
         ts = clock();
         merge(resultArr,0,ARRMAX-1);
         tc3 = clock() - ts;
           printf("   用归并排序法排序长 %ld 的数组所用时间为: %ld (ms) \n",ARRMAX,tc3);   
    
}

/*快速排序控制*/
void quickSort(){
    char ch;
	printf("   是否进行排序步骤演示?请选择 (y/n):  ");
   	printf("%c\n",(ch = getch()));
	if(ch == 'y'){
		arrLength = inputArr(sourceArr);
		copyArr(sourceArr,resultArr,arrLength);
		printf("\n^_^你好，下面是快速排序!");
		printf("\n-------------------------------------------------------------------------------");
		printf("\nsourceArr:");
  		printArr(sourceArr,arrLength);
	    quick(resultArr,0,arrLength-1);
	    printf("resultArr:");
	    printArr(resultArr,arrLength);
	    printf("-------------------------------------------------------------------------------");
        printf("\n注：快速排序是基于分治的思想，它选一个轴值，把大于它的数放右边\n"
		   "    小于它的数放左边，再把轴值分成的两个子序列用同样的方法“分治”。\n");
    }
	
         ts = clock();
         for(i=0;i<ARRMAX;i++)
            sourceArr[i] = rand();
         tc1=clock()-ts;
         printf("\n   给一个长度 %ld 的数组随机赋值所用时间为: %ld (ms) \n",ARRMAX,tc1);
	
         ts = clock();
         for(i=0;i<ARRMAX;i++)
            resultArr[i] = sourceArr[i];
         tc2 = clock() - ts;
           printf("   复制长度为 %d 数组到另一数组所用时间为: %ld (ms) \n",ARRMAX,tc2);

         ts = clock();
         quick(resultArr,0,ARRMAX-1);
         tc3 = clock() - ts;
           printf("   用快速排序法排序长 %ld 的数组所用时间为: %ld (ms) \n",ARRMAX,tc3);   
}

/*堆排序控制*/
void heapSort(){
	char ch;
	printf("   是否进行排序步骤演示?请选择 (y/n):  ");
   	printf("%c\n",(ch = getch()));
	if(ch == 'y'){
         arrLength = inputArr(sourceArr);
	     copyArr(sourceArr,resultArr,arrLength);
	     printf("\n^_^你好，下面是堆排序!");
	     printf("\n-------------------------------------------------------------------------------");
         heap(resultArr,arrLength);
	     printf("\nsourceArr:");
         printArr(sourceArr,arrLength);
	     printf("resultArr:");
	     printArr(resultArr,arrLength);
	     printf("-------------------------------------------------------------------------------");
         printf("\n注：堆排序是利用最大堆来排序的，每次把未排的数建成一个最大堆\n"
	     	    "    最大值与最后一个元素交换，然后把未排序的数再建成堆如此循环。\n");
	}
	     ts = clock();
         for(i=0;i<ARRMAX;i++)
            sourceArr[i] = rand();
         tc1=clock()-ts;
         printf("\n   给一个长度 %ld 的数组随机赋值所用时间为: %ld (ms) \n",ARRMAX,tc1);
	
         ts = clock();
         for(i=0;i<ARRMAX;i++)
            resultArr[i] = sourceArr[i];
         tc2 = clock() - ts;
           printf("   复制长度为 %d 数组到另一数组所用时间为: %ld (ms) \n",ARRMAX,tc2);

         ts = clock();
         heap(resultArr,ARRMAX);
         tc3 = clock() - ts;
         printf("   用堆排序算法排序长 %ld 的数组所用时间为: %ld (ms) \n",ARRMAX,tc3); 

}

/*基数排序及控制*/
	
void radixSort(){
    int i;
	int max; /*最大数*/
	int bins = 1; /*最大数的位数做为排序的趟数*/
    
    char ch;
	printf("   是否进行排序步骤演示?请选择 (y/n):  ");
   	printf("%c\n",(ch = getch()));
	if(ch == 'y'){
	    arrLength = inputArr(sourceArr);
	    copyArr(sourceArr,resultArr,arrLength);

        /*计算最大数的位数*/
	    max = sourceArr[0];
	    for(i=1;i<=arrLength;i++){
            if(sourceArr[i]>sourceArr[i-1])
	    		max = sourceArr[i];
	    }
    	while((max = max/10)>0) bins++;
    	printf("\n****thebins = %d****",bins);

    	printf("\n^_^你好，下面是基数排序!");
    	printf("\n-------------------------------------------------------------------------------");
	
        radix(resultArr,arrLength,bins,10);

    	printf("\nsourceArr:");
        printArr(sourceArr,arrLength);
    	printf("resultArr:");
    	printArr(resultArr,arrLength);
    	printf("-------------------------------------------------------------------------------");
        printf("\n注：基数排序是利用最大堆来排序的，每次把未排的数建成一个最大堆\n"
    		   "    最大值与最后一个元素交换，然后把未排序的数再建成堆如此循环。\n");
	}    /*****计算时间******/
    	 ts = clock();
         for(i=0;i<ARRMAX;i++)
            sourceArr[i] = rand();
         tc1=clock()-ts;
         printf("\n   给一个长度 %ld 的数组随机赋值所用时间为: %ld (ms) \n",ARRMAX,tc1);

		 bins = 1;
		 max = sourceArr[0];
	     for(i=1;i<=arrLength;i++){
            if(sourceArr[i]>sourceArr[i-1])
	    		max = sourceArr[i];
		 }
    	 while((max = max/10)>0) bins++;
	
         ts = clock();
         for(i=0;i<ARRMAX;i++)
            resultArr[i] = sourceArr[i];
         tc2 = clock() - ts;
           printf("   复制长度为 %d 数组到另一数组所用时间为: %ld (ms) \n",ARRMAX,tc2);

         ts = clock();
         radix(resultArr,ARRMAX,bins,10);
         tc3 = clock() - ts;
         printf("   用基数排序法排序长 %ld 的数组所用时间为: %ld (ms) \n",ARRMAX,tc3); 
}
int limitInput(int max){
   int choice;
   choice=getch();
   printf("%c",choice);
   while(choice>max+48||choice<1+48){
      printf("\n   输入错误,请输入(1-%d): ",max);
      printf("%c",choice=getch());
   }
   putchar('\n');
   return choice-48;
}

/***********************************************
限制输入整数(1-max)，返回符合范围的一个整数
int limitInput(int max){
   int choice;
   scanf("%d",&choice);
   while(choice>max || choice<1){
      printf("   输入错误,请输入(1-%d): ",max);
      scanf("%d",&choice);
   }
   return choice;
}
*************************************************/
/*输入数组函数，返回元素的个数*/	
int inputArr(int sourceArr[]){
	int i;
	int arrLength;
	printf("   请输入元素个数(1-50)：");
	arrLength = limitInput(50);
	printf("\n   请输入要排序的元素:\n");
	for(i=0;i<arrLength;i++){
		printf("   第 %d 个数:  ",i);