数据结构课程设计

				// 赫夫曼树.cpp : Defines the entry point for the console application.
				//
				
				//#include "stdafx.h"
				
				#include  
				#include  
				#define Max_Node 1000 
				#define Max_Weight  1000 
				
				
				typedef struct HuffmanTreeNode 
				      {    char ch, code[20]; 
				           int weight; 
				           int parent, lchild, rchild; 
				            }HTNode, *HuffmanTree; 
				typedef struct 
				    {    HTNode arr[Max_Node]; 
				         int total; 
				            } HTree; 
				
				 int statistic_char(char *text, HTree *t) 
				   { 
				        int i, j; 
				        int text_len = strlen(text); 
				        t->total = 0; 
				        for (i=0; i				         { for (j=0;jtotal ; j++) 
				           if (t->arr[j].ch == text[i]) 
							{  
				              t->arr[j].weight ++; 
				              break; } 
				            if (j==t->total) 
				            {  
				              t->arr[t->total].ch = text[i]; 
				              t->arr[t->total].weight = 1; 
				              t->total ++; } 
				            } 
				        printf("各字符的出现频率分别为\n"); 
				        for (i=0; itotal; i++) 
				        printf("'%c'  %d\n", t->arr[i].ch, t->arr[i].weight); 
				        printf("\n"); 
				        return t->total; 
				 } 
				int create_htree(HTree *t) 
				    { 
				       int i; 
				       int total_node = t->total * 2 - 1; 
				       int min1, min2; 
				       int min1_i, min2_i; 
				       int leaves = t->total;  
				       for (i=0; i				            {  t->arr[i].parent = -1; 
				               t->arr[i].rchild = -1; 
				               t->arr[i].lchild = -1; } 
				        while (t->total < total_node) 
				            { min1 = min2 = Max_Weight; 
				              for (i=0; itotal; i++) 
							  {if (t->arr[i].parent == -1&& t->arr[i].weight < min2) 
							   { if (t->arr[i].weight < min1) 
							    {   min2_i = min1_i;  min2 = min1; 
				                    min1_i = i;    min1 = t->arr[i].weight; } 
				              else 
							  {   min2_i = i;    min2 = t->arr[i].weight; } } } 
				            t->arr[t->total].weight = min1 + min2; 
				            t->arr[t->total].parent = -1; 
				            t->arr[t->total].lchild = min1_i; 
				            t->arr[t->total].rchild = min2_i; 
				            t->arr[min1_i].parent = t->total; 
				            t->arr[min2_i].parent = t->total; 
				            t->arr[t->total].ch = ' '; 
				            t->total ++; } 
				            return 0; 
				  } 
				
				void print_htree_ldr(HTree *t, int head_i, int deep, int* path) 
				{ int i; 
				  if (head_i == -1) return; 
				  path[deep] = 0; 
				  print_htree_ldr(t, t->arr[head_i].lchild, deep + 1, path); 
				  if (deep) printf("      "); 
				  for (i=1; i				  printf("%s", path[i]==path[i-1]?"      ":"│    "); 
				  int dir = path[i]==path[i-1]; 
				  if ( t->arr[head_i].lchild == -1 && t->arr[head_i].rchild == -1) 
				      printf("%s—— %d '%c'\n", dir? "┌":"└", 
				      t->arr[head_i].weight, t->arr[head_i].ch); 
				  else if (head_i != t->total-1) 
				       printf("%s—%02d┤\n", dir? "┌":"└", t->arr[head_i].weight); 
				   else 
				        printf("    %02d┤\n", t->arr[head_i].weight); 
				        path[deep] = 1; 
				        print_htree_ldr(t, t->arr[head_i].rchild, deep + 1, path); 
				}
				
				int main(int argc, char* argv[]) 
				{ HTree t; 
				  char text[128]={0}; 
				  printf("请输入你需要处理的字符串："); 
				  gets(text); 
				  char code[128] = ""; 
				  int path[16]={0}; 
				  statistic_char(text, &t); 
				  create_htree(&t); 
				  print_htree_ldr(&t, t.total-1, 0, path);
				  return 0; 
				}