data_structures.cpp

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

	    scanf("%d",&sourceArr[i]);
    }
	return arrLength;
}

/*复制数组的函数*/
void copyArr(int from[],int to[],int length){
	int i;
	for(i=0;i<length;i++)
		to[i] = from[i];
}

/*交换数组中的两个元素*/
void swap(int arr[],int n,int m){
	int temp;
	temp = arr[n];
	arr[n] = arr[m];
	arr[m] = temp;
}

/*打印数组的函数*/
void printArr(int array[],int length){
    int i; 
	for(i=0;i<length;i++)
		printf("%6d",array[i]);
	putchar('\n');
}

/*归并排序*/
void merge(int resultArr[],int left,int right){	
   int i,j,k;
   int mid = (left+right)/2;
   int count = 1;
   if(left == right) return;
   merge(resultArr,left,mid);
   merge(resultArr,mid+1,right);

   for(i=mid;i>=left;i--) 
	   temp[i]=resultArr[i]; /*把resultArr[]前半部分复制到temp[]左部*/
   for(j=1;j<=right-mid;j++) 
	   temp[right-j+1] = resultArr[j+mid]; /*把resultArr[]右半部分反序复制到temp[]右部*/
   
   /*从temp[]归并到a[]*/
   for(i=left,j=right,k=left;k<=right;k++)
	   if(temp[i]<temp[j]) resultArr[k] = temp[i++];
	   else resultArr[k] = temp[j--];
}
/*快速排序*/
void quick(int a[],int i,int j){
	int pivotindex,k;
	if(i>=j) return;
	pivotindex = (i+j)/2;
	swap(a,pivotindex,j);
	k = partition(a,i-1,j,a[j]);
    swap(a,k,j);
	quick(a,i,k-1);
	quick(a,k+1,j);
}

int partition(int a[],int l,int r,int pivot){
	do{
		while(a[++l]<pivot);
		while((r!=0) && (a[--r]>pivot));
		swap(a,l,r);
	}while(l<r);
	swap(a,l,r);
	return l;
}

/*建最大堆的函数*/
void createHeap(int *heap,int root,int index){
     int j;
	 int temp;   /*于数据交换时的暂存变量*/
	 int finish; /*判断堆是否建成*/

	 j = 2 * root + 1;
	 temp = heap[root]; /*暂存堆的根值*/
	 finish = 0; /*默认堆尚未建立*/
	 
	 while(j<index && finish == 0){
	     /*找出最大的子结点*/
		 if(j<index-1 && heap[j]<heap[j+1])
			 j++;
		 if(temp >= heap[j])
			 finish = 1; /*堆建好了*/
		 else{
		     heap[(j-1)/2] = heap[j]; 
			 j = j * 2 + 1;
		 }
	 }
	 heap[(j-1)/2] = temp; /*根值降到合适的位置*/
}

void heap(int *heap,int index){   
    int i,temp;
	
	/*将二叉树转成堆*/ 
	for(i=(index-1)/2;i>=0;i--)
		createHeap(heap,i,index);
    /*开始进行堆排序*/
	for(i=index-2;i>=0;i--){
	    createHeap(heap,0,i+2);
		temp = heap[i+1];
		heap[i+1] = heap[0];
		heap[0] = temp;
   //   int j;
   //   printf("\nstep%d:  ",index-2-i);
   //   for(j=0;j<index;j++)
   //	   printf("%6d",heap[j]);		
	}
   // 	putchar('\n');
}

/*基数排序
 * n是待排序元素的个数。
 * k是最大的数有几位，也是排序的趟数。
 * r是基数，十进制时为10。
*/
void radix(int a[],int n,int k,int r){
     int cnt[10];  /*cnt[]是统计每一个桶的大小。*/
	 int i,j;
	 int rtok; /*每一趟中所处理的位的权值*/
	 /*一次外循环一趟分配，从个位开始*/
	 for(i=0,rtok=1;i<k;i++,rtok*=r){
	      for(j=0;j<r;j++) cnt[j] = 0;  /*趟开始初始化桶大小*/
		  for(j=0;j<n;j++) ++cnt[(a[j] / rtok) % r]; /*计算一躺中各个桶大小*/
		  for(j=1;j<r;j++) cnt[j] = cnt[j-1] + cnt[j]; /*计算每个桶的右边界*/
		  for(j=n-1;j>=0;j--) b[--cnt[(a[j]/rtok)%r]] = a[j]; /*把数分配到对应桶中，
		                                                           从桶右边界开始*/
		  for(j=0;j<n;j++) a[j] = b [j]; /*把数值拷回a[]中，准备下一趟分配*/
	 }
}

/***********************************以下是最短路径******************************/
void shortctl(){
	int i,j,hops;
	int notes;
	int path[MAXNODES];
	int startNote,endNote;
	int noLinkValue = 999;
	srand(time(NULL));
	printf("   请输入结点数： ");
	scanf("%d",&notes);

	printf("\n   %d个结点，结点连接图如下：\n   v\\v   ",notes);
	for(j=0;j<notes;j++) printf("v%-3d",j);
    printf("\n        ");
	for(j=0;j<4*notes;j++) printf("-");

    for(j=0;j<notes;j++){
		for(i=0;i<j;i++){ 
			dist[i][j] = dist[j][i] = rand()%97+3;
		    if(rand()%2 == 0) dist[i][j] = dist[j][i] = noLinkValue;
		}
		dist[j][j] = 0;
        
	}
	for(j=0;j<notes;j++){
		printf("\n   v%-2d:",j);
		for(i=0;i<notes;i++)
			if(dist[j][i] == noLinkValue) 
				printf("   -");
		    else
				printf("%4d",dist[j][i]);
	}
   	printf("\n        ");
	for(j=0;j<4*notes;j++) printf("-");
	
   //printf("\n-->要开始查找点到点最短路径吗");

	printf("\n-->请你输入源结点: ");
	scanf("%d",&startNote);
    if(startNote>notes){
	    printf("\n输入有误:\n");
		printf("\n-->请你输入源结点: ");
	    scanf("%d",&startNote);
	}
	// printf("\n-->请输入目标结点: ");
   // scanf("%d",&endNote);
	for(endNote = 0;endNote<notes;endNote++){
		if(endNote != startNote){  
		    hops = shortestpath(notes,startNote,endNote,path);
	        if(hops<=0) printf("\n 结点%d 和 结点%d 之间是没有路径的哈哈!");
	    //    printf("\n从源结点 %d 到目标结点 %d 的路径如下：\n",startNote,endNote);
	        for(j=0;j<hops;j++)
		    printf("  (%d)  ",dist[path[j]][path[j+1]]);
	        printf("\n"); 
	        for(j=0;j<hops;j++) printf("%-2d----->",path[j]);
	        printf("%-2d\n",path[hops]);
		    putchar('\n');
		}
	}
	mainMenu();
}

/************最短路径算法***************/
int shortestpath(int n,int s,int t,int path[]){
	struct state{
	   int predecessor;
	   int length;
	   int flag;
	}state[MAXNODES];
	int i,k,min;
	int hops=0;
	struct state *p;
	for(p=&state[0];p<&state[n];p++){
	    p->predecessor = -1;
		p->length = INFINITY;
		p->flag = 0;
	}
    state[t].length = 0;
	state[t].flag = 1;
	k = t;
	do{
		for(i=0;i<n;i++)
			if(dist[k][i] !=0 && state[i].flag == 0){
				if(state[k].length+dist[k][i] <state[i].length){
				     state[i].predecessor = k;
					 state[i].length = state[k].length + dist[k][i];
				}
			}
        /*处理剩下的未处理的结点*/ 
         k = 0;
		 min = INFINITY;
		 for(i=0;i<n;i++)
			 if(state[i].flag == 0 && state[i].length<min){
			    min = state[i].length;
				k = i;
			 }
	     state[k].flag = 1;

	}while(k != s);
	/********把路径打印到数组里边********/
    i = 0;
	k = s;
	do{
		path[i++] = k; 
		k =state[k].predecessor;
		hops++;
	}while(k>=0);
	return hops-1;
}

/******************************以下是huffman树*******************************/
void huffmanTree(){
    int i,j,k;
	int min1,min2;
	int id1,id2;
    i = 1;
    srand(time(NULL));
    printf("\n\t请输入叶结点数：");
    scanf("%d",&n);
	for(k=1;k<=n;k++){
		hTree[k].name = k+64;
		hTree[k].weight = rand()%59;
	//	printf("%5c%5d\n",hTree[k].name,hTree[k].weight);
	}	
	while(i<=(n-1)){
         min1 = MAX;
		 min2 = MAX;
		 id1 = 0;
		 id2 = 0;
		 /*******寻找两个最小值*******/
		 for(j=1;j<n+i;j++){      
			  if((hTree[j].weight < min1) && (hTree[j].flag == 0)){
			       min2 = min1;
				   id2 = id1;
				   min1 = hTree[j].weight;
				   id1 = j;
			  }
			  else if((hTree[j].weight < min2) && (hTree[j].flag == 0)){
			        min2 = hTree[j].weight;
					id2 = j;
			  }
		 }
		 hTree[id1].flag = 1;
		 hTree[id2].flag = 1;
		 hTree[n+i].weight = hTree[id1].weight+hTree[id2].weight;
		 hTree[n+i].lchild = id1;
		 hTree[n+i].rchild = id2;
		 hTree[n+i].flag = 0;
		 hTree[id1].parent = hTree[id2].parent = n+i;
	     i++; 
	}
	root = 2*n-1;            //共有2n - 1 个结点；
}

/********编码函数********/
void code(){
	int i,j,pNode;
	for(i=1;i<=n;i++){
		/***每次循环对一个叶接点编码***/
		pNode = i;
		psuffix = 0;
		printf("\n\t");
		printf("%c :   ",hTree[i].name);
		while(hTree[pNode].parent != 0){
		  
			path[psuffix++] = pNode;
		    pNode = hTree[pNode].parent;
		}
        path[psuffix++] = pNode;
        
		/*******打印路径*******
    	for(j=0;j<psuffix;j++)
           printf("%-4d",path[j]);
	    printf("\t\t"); *******/

	    /*******打印编码*******/
	    j = psuffix-1;
		while(hTree[path[j]].lchild!=0 && hTree[path[j]].rchild!=0){
			if(hTree[path[j]].lchild == path[j-1]) {putchar('0');}
			else if(hTree[path[j]].rchild == path[j-1]) {putchar('1');}
			j--;
        }   
	}
}
/********解码函数**********/
void decode(){
	char ch;
	printf("\n\t输入y进行解码，输入n 退出:(y/n) : ");
	ch = get_yn();
	while (ch != 'n'){
	      curIndex = 2 * n - 1;
		  printf("\t请输入编码:  ");
		  while(hTree[curIndex].lchild!=0 &&hTree[curIndex].rchild!=0){
			  if((ch=getch()) == '1'){ 
				   curIndex = hTree[curIndex].rchild;
				   printf("%c",ch);
			  }
			  else if(ch == '0'){
				   curIndex = hTree[curIndex].lchild;
			       printf("%c",ch);
			  }
			  else {
				   printf("%c",ch);
				   break;
			  }
		  }
		  if(hTree[curIndex].name != '\0') printf("    --- %-6c\n",hTree[curIndex].name);
		  else printf("    ---编码有误!请检查。\n");
		  printf("\n\t是否继续进行解码,键入n退出(y/n): ");
	      ch = get_yn();
	}
	printf("\n\t解码结束,欢迎再次使用!\n\t");
}
/*****z只能输入y或n判断是否继续*******/
char get_yn(){
	char chyn;
    chyn = getch();
	while(chyn !='y' && chyn !='n'){
	     chyn = getch();
	}
	printf("  %c\n",chyn);
	return chyn;
}
/*********huffman控制**********/
void huffman(){
   int k;
   huffmanTree();
   printf("\n\t\t%-8s%-8s%-8s%-8s%-8s%-8s",
	   "name","lchild","rchild","parent","flag","weight\n");
   for(k=1;k<2*n;k++)
	   printf("\t%-8d%-8c%-8d%-8d%-8d%-8d%-8d\n",
	          k,hTree[k].name,hTree[k].lchild,hTree[k].rchild,
	          hTree[k].parent,hTree[k].flag,hTree[k].weight);
   code();   //编码
   printf("\n\n");
   decode(); //解码 
   mainMenu();
}