㈠ 誰能幫幫我，《數據結構》課程設計——哈夫曼編解碼器設計（用c語言的）！！！謝謝了！！！
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char* HuffmanCode;/*動態分配數組，存儲哈夫曼編碼*/
typedef struct
{
unsigned int weight ; /* 用來存放各個結點的權值*/
unsigned int parent, LChild,RChild ; /*指向雙親、孩子結點的指針*/
}HTNode, * HuffmanTree; /*動態分配數組，存儲哈夫曼樹*/
void select(HuffmanTree *ht,int n, int *s1, int *s2)
{
int i;
int min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0)
{
min = i;
i = n+1;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0)
{
if((*ht)[i].weight < (*ht)[min].weight)
min = i;
}
}
*s1 = min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0 && i!=(*s1))
{
min = i;
i = n+1;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0 && i!=(*s1))
{
if((*ht)[i].weight < (*ht)[min].weight)
min = i;
}
}
*s2 = min;
}
void CrtHuffmanTree(HuffmanTree *ht , int *w, int n)
{ /* w存放已知的n個權值，構造哈夫曼樹ht */
int m,i;
int s1,s2;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0號單元未使用*/
for(i=1;i<=n;i++)
{/*1-n號放葉子結點，初始化*/
(*ht)[i].weight = w[i];
(*ht)[i].LChild = 0;
(*ht)[i].parent = 0;
(*ht)[i].RChild = 0;
}
for(i=n+1;i<=m;i++)
{
(*ht)[i].weight = 0;
(*ht)[i].LChild = 0;
(*ht)[i].parent = 0;
(*ht)[i].RChild = 0;
} /*非葉子結點初始化*/
/* ------------初始化完畢！對應演算法步驟1---------*/
for(i=n+1;i<=m;i++) /*創建非葉子結點,建哈夫曼樹*/
{ /*在(*ht)[1]~(*ht)[i-1]的范圍內選擇兩個parent為0且weight最小的結點，其序號分別賦值給s1、s2返回*/
select(ht,i-1,&s1,&s2);
(*ht)[s1].parent=i;
(*ht)[s2].parent=i;
(*ht)[i].LChild=s1;
(*ht)[i].RChild=s2;
(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;
}
}/*哈夫曼樹建立完畢*/
void outputHuffman(HuffmanTree HT, int m)
{
if(m!=0)
{
printf("%d ", HT[m].weight);
outputHuffman(HT,HT[m].LChild);
outputHuffman(HT,HT[m].RChild);
}
}
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
/*從葉子結點到根，逆向求每個葉子結點對應的哈夫曼編碼*/
{
char *cd;
int i;
unsigned int c;
int start;
int p;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); /*分配n個編碼的頭指針*/
cd=(char * )malloc(n * sizeof(char )); /*分配求當前編碼的工作空間*/
cd[n-1]='\0'; /*從右向左逐位存放編碼，首先存放編碼結束符*/
for(i=1;i<=n;i++) /*求n個葉子結點對應的哈夫曼編碼*/
{
start=n-1; /*初始化編碼起始指針*/
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) /*從葉子到根結點求編碼*/
if( (*ht)[p].LChild == c)
cd[--start]='0'; /*左分支標0*/
else
cd[--start]='1'; /*右分支標1*/
hc[i]=(char *)malloc((n-start)*sizeof(char)); /*為第i個編碼分配空間*/
strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1;i<=n;i++)
printf("%d編碼為%s\n",(*ht)[i].weight,hc[i]);
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w;
int i,n; // the number of elements;
int wei; // the weight of a element;
int m;
printf("input the total number of the Huffman Tree:" );
scanf("%d",&n);
w=(int *)malloc((n+1)*sizeof(int));
for(i=1;i<=n;i++)
{
printf("input the %d element's weight:",i);
fflush(stdin);
scanf("%d",&wei);
w[i]=wei;
}
CrtHuffmanTree(&HT,w,n);
m = 2*n-1;
outputHuffman(HT,m);
printf("\n");
CrtHuffmanCode(&HT,&HC,n);
}
㈡ 用c語言完成：1.哈夫曼編碼/解碼器2.內部排序演算法的性能分析
我把網上的程序修改了一下，並整合了，你看看
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 50
#define MAX 100000;
typedef struct
{
int weight;//結點權值
int parent,lchild,rchild;
}HTNODE,*HUFFMANTREE;
typedef char** HUFFMANCODE;//動態分配數組存儲哈夫曼編碼表
typedef struct
{
int key; /*關鍵字*/
}RecordNode; /*排序節點的類型*/
typedef struct
{
RecordNode *record;
int n; /*排序對象的大小*/
}SortObject; //待排序序列
HUFFMANTREE huffmantree(int n,int weight[])//構建哈夫曼樹
{
int m1,m2,k;
int i,j,x1,x2;
HUFFMANTREE ht;
ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE));
for(i=1;i<(2*n);i++)//初始化哈夫曼樹中各結點的數據，沒初始值的賦值為0
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
if(i<=n)
ht[i].weight=weight[i];
else
ht[i].weight=0;
}
for(i=1;i<n;i++)//每一重循環從森林中選擇最小的兩棵樹組建成一顆新樹
{
m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{
if((ht[j].weight<m1)&&(ht[j].parent==0))
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if((ht[j].weight<m2)&&(ht[j].parent==0))
{
m2=ht[j].weight;
x2=j;
}
}
k=n+i;
ht[x1].parent=ht[x2].parent=k;
ht[k].weight=m1+m2;
ht[k].lchild=x1;
ht[k].rchild=x2;
}
return ht;
}
void huffmancoding(int n,HUFFMANCODE hc,HUFFMANTREE ht,char str[])
{
int i,start,child,father;
char *cd;
hc=(HUFFMANCODE)malloc((n+1)*sizeof(char*));//分配n個字元編碼的頭指針
cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間
cd[n-1]='\0';//編碼結束符
for(i=1;i<=n;++i)//逐個字元求哈夫曼編碼
{
start=n-1;
for(child=i,father=ht[i].parent;father!=0;child=father,father=ht[father].parent)/*從葉子結點到根結點求逆向編碼*/
if(ht[father].lchild==child)
cd[--start]='0';
else
cd[--start]='1';
hc[i]=(char*)malloc((n-start)*sizeof(char));//為i個字元編碼分配空間
strcpy(hc[i],&cd[start]);//從cd復制哈夫曼編碼串到hc
}
free(cd);//釋放工作空間
for(i=1;i<=n;++i)
{
printf("\n%c的編碼:",str[i]);
printf("%s\n",hc[i]);
}
}
void huffman()
{
int i,j,k,m,n;
char str[50];
int weight[50];
HUFFMANCODE hc=NULL;
HUFFMANTREE ht;
fflush(stdin);
printf("\n請輸入字元(一次性連續輸入所求的字元):");/*如:abcjhjg不要輸成ab cj hig,即字元間不加空格*/
gets(str);
for(j=0;j<50;j++)
{
if(str[j]=='\0')
break;
}
n=j;
for(j=n;j>0;j--)
str[j]=str[j-1];
str[n+1]='\0';
for(k=0;k<n;k++)
{
printf("\n請輸入%c的權值:",str[k+1]);
scanf("%d",&weight[k]);
}
for(k=n;k>0;k--)
weight[k]=weight[k-1];
weight[0]=0;
ht=huffmantree(n,weight);
huffmancoding(n,hc,ht,str);
}
void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
fflush(stdin);
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=1;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-1;
while((temp.key<pvector->record[j].key)&&(j>=0))
{
(*compare)++;
(*exchange)++;
pvector->record[j+1]=pvector->record[j];
j--;
}
if(j!=(i-1))
{
pvector->record[j+1]=temp;
(*exchange)++;
}
}
free(pvector);
}
void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/*復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
k=i;
for(j=i+1;j<pvector->n;j++)
{
(*compare)++;
if(pvector->record[j].key<pvector->record[k].key)
k=j;
}
if(k!=i)
{
temp=pvector->record[i];
pvector->record[i]=pvector->record[k];
pvector->record[k]=temp;
( *exchange)+=3;
}
}
free(pvector);
}
void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,noswap,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
noswap=1;
for(j=0;j<pvector->n-i-1;j++)
{
(*compare)++;
if(pvector->record[j+1].key<pvector->record[j].key)
{
temp=pvector->record[j];
pvector->record[j]=pvector->record[j+1];
pvector->record[j+1]=temp;
(*exchange)+=3;
noswap=0;
}
}
if(noswap) break;
}
free(pvector);
}
void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange)
{
int i,j,increment,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(increment=d;increment>0;increment/=2)
{
for(i=increment;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-increment;
while(j>=0&&temp.key<pvector->record[j].key)
{
(*compare)++;
pvector->record[j+increment]=pvector->record[j];
(*exchange)++;
j-=increment;
}
pvector->record[j+increment]=temp;
(*exchange)++;
}
}
free(pvector);
}
void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)
{
int i,j;
RecordNode temp;
if(left>=right)
return;
i=left;
j=right;
temp=pvector->record[i];
(*exchange)++;
while(i!=j)
{
while((pvector->record[j].key>=temp.key)&&(j>i))
{
(*compare)++;
j--;
}
if(i<j)
{
pvector->record[i++]=pvector->record[j];
(*exchange)++;
}
while((pvector->record[i].key<=temp.key)&&(j>i))
{
(*compare)++;
i++;
}
if(i<j)
{
pvector->record[j--]=pvector->record[i];
(*exchange)++;
}
}
pvector->record[i]=temp;
(*exchange)++;
QuickSort(pvector,left,i-1,compare,exchange);
QuickSort(pvector,i+1,right,compare,exchange);
}
void SortMethod(void)
{
int i,j,k,l;
unsigned long num[5][10]={0};
unsigned long sum[10]={0};
SortObject *pvector;
fflush(stdin);
printf("請輸入待排序的隨機數個數：\n");
scanf("%d",&k);
pvector=(SortObject *)malloc(sizeof(SortObject));
for(j=0;j<5;j++)
{
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<k;i++)
pvector->record[i].key=rand();
pvector->n=k;
InsertSort(pvector,&num[j][0],&num[j][1]);
SelectSort(pvector,&num[j][2],&num[j][3]);
BubbleSort(pvector,&num[j][4],&num[j][5]);
ShellSort(pvector,4,&num[j][6],&num[j][7]);
QuickSort(pvector,0,k-1,&num[j][8],&num[j][9]);
}
printf("\n排序比較如下");
for(j=0;j<5;j++)
{
printf("\n\n對%d個數進行排序，結果為：\n",k);
printf("1.插入排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][0],num[j][1]);
printf("2.選擇排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][2],num[j][3]);
printf("3.冒泡排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][4],num[j][5]);
printf("4.希爾排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][6],num[j][7]);
printf("5.快速排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][8],num[j][9]);
if(j!=5)
printf("按回車繼續\n");
getchar();
}
for(j=0;j<5;j++)
{
sum[0]=sum[0]+num[j][0];
sum[1]=sum[1]+num[j][1];
sum[2]=sum[2]+num[j][2];
sum[3]=sum[3]+num[j][3];
sum[4]=sum[4]+num[j][4];
sum[5]=sum[5]+num[j][5];
sum[6]=sum[6]+num[j][6];
sum[7]=sum[7]+num[j][7];
sum[8]=sum[8]+num[j][8];
sum[9]=sum[9]+num[j][9];
}
printf("\n\n對%d個隨機數進行5次排序，平均比較次數和平均移動次數為：\n",k);
printf("1.插入排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[0]/5,sum[1]/5);
printf("2.選擇排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[2]/5,sum[3]/5);
printf("3.冒泡排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[4]/5,sum[5]/5);
printf("4.希爾排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[6]/5,sum[7]/5);
printf("5.快速排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[8]/5,sum[9]/5);
free(pvector);
}
void sort()
{
int i;
while(1)
{
SortMethod();
printf("\n是否繼續？\n1.繼續\n2.返回菜單\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
void huff()
{
int i;
while(1)
{
huffman();
printf("\n是否繼續？\n1.繼續\n2.返回菜單\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
main()
{
int i,j,k;
while(1)
{
printf("請選擇要運行的功能：\n");
printf("1.哈夫曼編碼解碼器\n");
printf("2.內部排序性能分析\n");
printf("3.退出該程序\n\n");
printf("你的選擇為：");
scanf("%d",&i);
switch(i)
{
case 1:huff();break;
case 2:sort();break;
case 3:exit(0);
default:break;
}
fflush(stdin);
getchar();
system("cls");
}
}
㈢ 跪求C語言進行哈夫曼編碼、算術編碼和LZW編碼，要求源程序要有注釋。
以下是哈夫曼編碼
#include<iostream>
#include<math.h>
#include<string>
#include<iomanip>
using namespace std;
int n;
int isin(string str,char a)
{
int temp=0;
for(int i=0;i<str.length();i++)
{
if(str[i]==a) temp=1;
}
return temp;
}
void bubble(double p[],string sign[])//排序
{
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(p[i]<p[j])
{
double temp=p[i];
p[i]=p[j];
p[j]=temp;
string m=sign[i];
sign[i]=sign[j];
sign[j]=m;
}
}
}
}
void huff(double tempp[],string tempstr[])
{
double p[20][20];
string sign[20][20];
sign[0][i]=tempstr[i]; //符號放在sign數組中
for(int i=0;i<n;i++)
{
p[0][i]=tempp[i]; //p數組放對應的概率(第1列中)
}
for(i=0;i<n-1;i++)
{
bubble(p[i],sign[i]); //第一次排序
for(int j=0;j<n-2-i;j++)
{
p[i+1][j]=p[i][j]; //前n-2-i個概率重新放在p數組中(是數組的第2列中)
sign[i+1][j]=sign[i][j];
}
p[i+1][j]=p[i][j]+p[i][j+1];//第一次兩個最小概率求和
sign[i+1][j]=sign[i][j]+sign[i][j+1];//符號跟隨
for(j=n-1-i;j<n;j++)
{
p[i+1][j]=0;
}
}
string final[20];
for(i=n-2;i>=0;i--)
{
for(int k=0;k<n;k++)
{
if(isin(sign[i][n-2-i],sign[0][k][0])) final[k]+="0";
if(isin(sign[i][n-1-i],sign[0][k][0])) final[k]+="1";
}
}
cout<<setw(9)<<"哈弗曼編碼如下:"<<endl;
for(i=0;i<n;i++)
{
cout<<setw(7)<<sign[0][i]<<setw(7)<<p[0][i]<<setw(10)<<final[i]<<
setw(7)<<final[i].length()<<endl;
}
}
void main()
{
char a[50];
cout<<"該字元串符號為:";
cin>>a;
string s=a;
n=s.length();
char b[20][2];
for(int i=0;i<n;i++)
{
b[i][0]=a[i];
b[i][1]='\0';
}
string str[20];
for(i=0;i<n;i++)
{
str[i]=b[i];
}
double tempp[20];
cout<<"字元概率依次為：";
for(i=0;i<n;i++)
{
cin>>tempp[i];
}
huff(tempp,str);
}