数据结构试验(矩阵压缩)

数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2. 掌握稀疏矩阵的加法、转置、乘法等基本运算；3. 加深对线性表的顺序存储和链式结构的理解。

第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。

一、特殊矩阵的压缩存储1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。

对n阶对称矩阵，我们只需要存储下三角元素就可以了。

事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。

问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。

任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里：k=i(i+1)/2+j (i≥j)图5-1 下三角矩阵a00 a10 a11 a20 … an-1,0 … an-1,n-1k= 0 1 2 3 …n(n-1)/2 …n(n+1)/2-1图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。

这里，i=d-1，（d是使sum= > k的最小整数），j= 。

2. 三对角矩阵在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。

矩阵压缩存储矩阵是在计算机科学和数学中常见的数据结构，用于表示具有行和列的二维数据。

在很多应用中，矩阵的大小可能非常大，占用大量的存储空间。

为了节省存储空间并提高计算效率，在某些情况下可以使用矩阵压缩存储技术。

什么是矩阵压缩存储？矩阵压缩存储是一种将稀疏矩阵（其中大部分元素为零）以更紧凑形式表示的技术。

通过只存储非零元素及其位置，可以显著减少所需的存储空间。

稀疏矩阵稀疏矩阵是指其中大部分元素为零的矩阵。

在实际应用中，很多情况下只有少数元素非零，例如图像处理、网络分析、自然语言处理等领域。

对于这些稀疏矩阵，传统的二维数组表示方法会浪费大量的存储空间。

稀疏矩阵压缩存储方法COO格式COO（Coordinate）格式是最简单直观的稀疏矩阵压缩存储方法。

它使用三个数组分别存储非零元素的值、行索引和列索引。

例如，对于矩阵：1 0 00 2 03 0 4COO格式可以表示为：values = [1, 2, 3, 4]rows = [0, 1, 2, 2]cols = [0, 1, 0, 2]CSR格式CSR（Compressed Sparse Row）格式是一种常用的稀疏矩阵压缩存储方法。

它使用三个数组分别存储非零元素的值、每行第一个非零元素在值数组中的位置和列索引。

例如，对于矩阵：1 0 00 2 03 0 4CSR格式可以表示为：values = [1, 2, 3, 4]row_ptrs = [0, -1, -1, -1] # 第一个非零元素在values中的位置cols = [0, -1, -1, -1] # 列索引CSC格式CSC（Compressed Sparse Column）格式与CSR格式类似，只是将行和列交换。

它使用三个数组分别存储非零元素的值、每列第一个非零元素在值数组中的位置和行索引。

其他压缩存储方法除了COO、CSR和CSC格式，还有其他一些矩阵压缩存储方法，如LIL（List of Lists）格式、DOK（Dictionary of Keys）格式等。

实验4 数组与广义表
课程实验共安排8个难度各易的实验，训练重点在于掌握基本的数据结构，而不强调面面俱到。

通过实验，掌握抽象数据类型的概念和基本数据结构，掌握各种数据结构内在的逻辑关系，各种数据结构在计算机中的存储表示，基于各种数据结构上的基本运算、算法实现及算法分析。

●实验目的
(1) 了解数组的存储表示方法，掌握其在作为运行的存储结构中的地址计算方法。

(2) 了解特殊矩阵及稀疏矩阵压缩存储特点和适用范围，领会其运算采用的处理方法。

(3) 了解广义表的结构特点及存储表示方法，掌握其主要运算的实现方法。

●实验内容
1. 鞍点问题
[问题描述] 若矩阵A中的某一元素A[i, j]是第i行中的最小值，而又是第j列中的最大值，则称A[i, j]为矩阵A中的一个鞍点。

请写出一个可确定此鞍点位置的算法（如果这个鞍点存在），并给出此算法的时间复杂度。

[基本要求] 要求算法要考虑某行中具有多个相同的且又是该行中最小的元素的情况。

2. 对称矩阵运算
[问题描述] 已知A和B为两个n×n阶的对称矩阵，试编写一个计算对称矩阵A和B的乘积的函数。

[基本要求] 输入时对称矩阵只输入下三角形元素，存入一维数组，即采用压缩存储。

3. 广义表运算
[问题描述] 在给定的广义表中查找数据为x的结点，编写该算法。

[基本要求] 广义表采用扩展线性链表存储表示。

●实验要求
(1) 认真分析题目。

(2) 进行算法设计。

(3) 编写程序代码
(4) 上机调试程序。

(5) 保存和打印出程序的运行结果，并结合程序进行分析。

一、实验目的1. 理解并掌握矩阵压缩存储的基本原理和方法。

2. 学习针对不同类型矩阵（对称矩阵、三角矩阵、稀疏矩阵）的压缩存储技术。

3. 通过编程实现矩阵压缩存储，并验证其正确性和效率。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 20194. 实验数据：随机生成的矩阵数据三、实验内容本次实验主要针对以下三种特殊矩阵的压缩存储进行实验：1. 对称矩阵2. 三角矩阵（上三角矩阵和下三角矩阵）3. 稀疏矩阵四、实验步骤1. 对称矩阵压缩存储- 设计一个对称矩阵的结构体，包含矩阵的行数、列数以及压缩后的数组。

- 实现一个函数，将输入的对称矩阵压缩存储到一维数组中。

- 实现一个函数，根据一维数组中的元素索引还原对称矩阵。

2. 三角矩阵压缩存储- 设计一个三角矩阵的结构体，包含矩阵的行数、列数以及压缩后的数组。

- 实现两个函数，分别用于将输入的上三角矩阵和下三角矩阵压缩存储到一维数组中。

- 实现两个函数，分别用于根据一维数组中的元素索引还原上三角矩阵和下三角矩阵。

3. 稀疏矩阵压缩存储- 设计一个稀疏矩阵的结构体，包含矩阵的行数、列数、非零元素个数以及压缩后的数组。

- 实现一个函数，将输入的稀疏矩阵压缩存储到一维数组中。

- 实现一个函数，根据一维数组中的元素索引还原稀疏矩阵。

五、实验结果与分析1. 对称矩阵压缩存储- 实验结果：成功将输入的对称矩阵压缩存储到一维数组中，并可以正确还原。

- 分析：对称矩阵压缩存储可以节省约50%的存储空间。

2. 三角矩阵压缩存储- 实验结果：成功将输入的上三角矩阵和下三角矩阵压缩存储到一维数组中，并可以正确还原。

- 分析：三角矩阵压缩存储可以节省约75%的存储空间。

3. 稀疏矩阵压缩存储- 实验结果：成功将输入的稀疏矩阵压缩存储到一维数组中，并可以正确还原。

- 分析：稀疏矩阵压缩存储可以大大节省存储空间，提高矩阵运算的效率。

1.实验目的：掌握稀疏矩阵的压缩存储方法及主要运算的实现。

2.实验内容与要求：设计一个稀疏矩阵计算器，要求能够：⑴输入并建立稀疏矩阵；⑵输出稀疏矩阵；⑶执行两个矩阵相加；⑷执行两个矩阵相乘；⑸求一个矩阵的转置矩阵。

3.数据结构设计逻辑结构：线性结构存储结构：顺序存储结构4.算法设计#include<stdio.h>#define MAXSIZE 100typedef int datatype;typedef struct{ int i,j;datatype v;}Triple;typedef struct{ Triple data[MAXSIZE+1];int rpos[MAXSIZE+1];int mu,nu,tu;}RLSMatrix;int main(){ void AddSMatrix(RLSMatrix M);void MultSMatrix(RLSMatrix M);void FastTransposeSMatrix(RLSMatrix M);RLSMatrix M;int k;printf("请输入稀疏矩阵M的行数、列数和非零元素个数:");scanf("%d%d%d",&M.mu,&M.nu,&M.tu);printf("请输入稀疏矩阵M中非零元素的行号、列号和元素的值:\n");for(k=1;k<=M.tu;k++)scanf("%d%d%d",&M.data[k].i,&M.data[k].j,&M.data[k].v);printf("请输出稀疏矩阵M中非零元素的行号、列号和元素的值:\n");for(k=1;k<=M.tu;k++){ printf("%d%3d%3d",M.data[k].i,M.data[k].j,M.data[k].v);printf("\n");}AddSMatrix(M);MultSMatrix(M);FastTransposeSMatrix(M);return 0;}void AddSMatrix(RLSMatrix M){ RLSMatrix N,R;int k,l=1,s=1;printf("请输入稀疏矩阵N的行数、列数和非零元素个数:");scanf("%d%d%d",&N.mu,&N.nu,&N.tu);printf("请输入稀疏矩阵N中非零元素的行号、列号和元素的值:\n"); for(k=1;k<=N.tu;k++)scanf("%d%d%d",&N.data[k].i,&N.data[k].j,&N.data[k].v);if(M.mu!=N.mu||M.nu!=N.nu) printf("错误\n");else{ R.mu=M.mu;R.nu=M.nu;k=1;if(M.tu*N.tu!=0){ while(k<=M.tu&&l<=N.tu){ if(M.data[k].i==N.data[l].i){ if(M.data[k].j<N.data[k].j){ R.data[s].i=M.data[k].i;R.data[s].j=M.data[k].j;R.data[s].v=M.data[k].v;k++;s++;}else if(M.data[k].j==N.data[l].j){ R.data[s].i=M.data[k].i;R.data[s].j=M.data[k].j;R.data[s].v=M.data[k].v+N.data[l].v;if(R.data[s].v!=0) s++;k++;l++;}else{ R.data[s].i=N.data[l].i;R.data[s].j=N.data[l].j;R.data[s].v=N.data[l].v;l++;s++;}}else if(M.data[k].i<N.data[l].i){ R.data[s].i=M.data[k].i;R.data[s].j=M.data[k].j;R.data[s].v=M.data[k].v;k++;s++;}else{ R.data[s].i=N.data[l].i;R.data[s].j=N.data[l].j;R.data[s].v=N.data[l].v;l++;s++;}}while(k<=M.tu){ R.data[s].i=M.data[k].i;R.data[s].j=M.data[k].j;R.data[s].v=M.data[k].v;k++;s++;}while(l<=N.tu){ R.data[s].i=N.data[l].i;R.data[s].j=N.data[l].j;R.data[s].v=N.data[l].v;l++;s++;}}printf("请输出稀疏矩阵M和稀疏矩阵N的和矩阵R中非零元素的行号、列号和元素的值:\n");for(k=1;k<s;k++)printf("%d%3d%3d\n",R.data[k].i,R.data[k].j,R.data[k].v);}}void MultSMatrix(RLSMatrix M){ RLSMatrix D,Q;int num1[MAXSIZE],num2[MAXSIZE],ctemp[MAXSIZE],arow,brow,ccol,p,q,tp,t; printf("请输入稀疏矩阵D的行数、列数和非零元素个数:");scanf("%d%d%d",&D.mu,&D.nu,&D.tu);printf("请输入稀疏矩阵D中非零元素的行号、列号和元素的值:\n");for(t=1;t<=D.tu;t++)scanf("%d%d%d",&D.data[t].i,&D.data[t].j,&D.data[t].v);for(ccol=1;ccol<=M.mu;ccol++)num1[ccol]=0;for(t=1;t<=M.tu;t++)num1[M.data[t].i]++;M.rpos[1]=1;for(ccol=2;ccol<=M.mu;ccol++)M.rpos[ccol]=M.rpos[ccol-1]+num1[ccol-1];for(ccol=1;ccol<=D.mu;ccol++)num2[ccol]=0;for(t=1;t<=D.tu;t++)num2[D.data[t].i]++;D.rpos[1]=1;for(ccol=2;ccol<=D.mu;ccol++)D.rpos[ccol]=D.rpos[ccol-1]+num2[ccol-1];if(M.nu!=D.mu) printf("错误\n");else{ Q.mu=M.mu;Q.nu=D.nu;Q.tu=0;if(M.tu*D.tu!=0){ for(arow=1;arow<=M.mu;arow++){ for(ccol=1;ccol<=Q.nu;ccol++)ctemp[ccol]=0;Q.rpos[arow]=Q.tu+1;if(arow<M.mu) tp=M.rpos[arow+1];else tp=M.tu+1;for(p=M.rpos[arow];p<tp;p++){ brow=M.data[p].j;if(brow<D.mu) t=D.rpos[brow+1];else t=D.tu+1;for(q=D.rpos[brow];q<t;q++){ ccol=D.data[q].j;ctemp[ccol]+=M.data[p].v*D.data[q].v;}}for(ccol=1;ccol<=Q.nu;ccol++)if(ctemp[ccol]!=0){ if(++Q.tu>MAXSIZE) printf("错误\n");else{ Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;Q.data[Q.tu].v=ctemp[ccol];}}}}}printf("请输出稀疏矩阵M和稀疏矩阵D的乘积矩阵Q中非零元素的行号、列号和元素的值:\n");for(ccol=1;ccol<=Q.tu;ccol++)printf("%d%3d%3d\n",Q.data[ccol].i,Q.data[ccol].j,Q.data[ccol].v);}void FastTransposeSMatrix(RLSMatrix M){ RLSMatrix T;int num[MAXSIZE],cpot[MAXSIZE],col,p,q,t;T.mu=M.mu;T.nu=M.nu;T.tu=M.tu;if(T.tu!=0){ for(col=1;col<=M.mu;col++)num[col]=0;for(t=1;t<=M.tu;t++)num[M.data[t].j]++;cpot[1]=1;for(col=2;col<=M.nu;col++)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;p++){ col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].v=M.data[p].v;cpot[col]++;}}printf("请输出将稀疏矩阵M转置后的稀疏矩阵T中非零元素的行号、列号和元素的值:\n");for(col=1;col<=T.tu;col++)printf("%d%3d%3d\n",T.data[col].i,T.data[col].j,T.data[col].v);}。

1.课程设计的目的(1> 熟练使用 C ++语言编写程序，解决实际问题。

(2> 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。

(3> 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。

(4> 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。

2.需求分析问题描述：对于特殊矩阵可以通过压缩存储减少存储空间。

基本要求：1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值。

2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值。

特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。

最常见的特殊矩阵有对称矩阵、上(下>三角矩阵、对角矩阵等。

b5E2RGbCAP 特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的值相同的多个矩阵元素压缩存储到一个存储空间中。

p1EanqFDPw3.矩阵的压缩与解压缩问题的设计图1-14.调试分析图1-2程序运行界面图1-3 程序运行界面图1-4 文件的输入5.小结经过矩阵的压缩与解压缩的实验，让我了解到计算机是怎么为了减少承储空间的，存储矩阵的。

以及特殊矩阵式在计算机中存储，以及把这些矩阵的压缩后怎么解压出来，恢复原来的样子！我觉得像这样的课程设计，一定要先想好有哪些板块，以及那些板块之间的关系这么样！谁调谁！DXDiTa9E3d6、参考文献[1]严蔚敏，吴伟民编著. 数据结构(C 语言版>--北京: 清华大学出版社，2007.2[2]严蔚敏，吴伟民M宁编著. 数据结构题集(C 语言版>--北京: 清华大学出版社，2007.3[3]网上搜索相关程序作为参考附录：#include <iostream>#include<fstream>using namespace std。

精品资料数据结构实验五矩阵的压缩存储与运算........................................第五章矩阵的压缩存储与运算【实验目的】1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2. 掌握稀疏矩阵的加法、转置、乘法等基本运算；3. 加深对线性表的顺序存储和链式结构的理解。

第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。

一、特殊矩阵的压缩存储1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。

对n阶对称矩阵，我们只需要存储下三角元素就可以了。

事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。

问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。

任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里：k=i(i+1)/2+j (i≥j)图5-1 下三角矩阵a00 a10 a11 a20 … an-1,0 … an-1,n-1k= 0 1 23 …n(n-1)/2 …n(n+1)/2-1图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。

这里，i=d-1，（d是使sum= > k的最小整数），j= 。

矩阵压缩储存三元组带状矩阵矩阵压缩储存是一种常用的数据结构，用于减少存储空间和提高数据处理效率。

在某些特殊类型的矩阵中，存在大量的零元素，这些零元素会占据大量的存储空间，并且对于计算和处理时也会造成浪费。

因此，为了更高效地存储和处理这些特殊类型的矩阵，我们可以使用三元组带状矩阵的方法。

三元组带状矩阵是一种压缩储存矩阵的方法，它通过记录矩阵中非零元素的值、所在行和列的信息，来表示整个矩阵。

与普通的矩阵相比，三元组带状矩阵可以大大减少存储空间的使用。

三元组带状矩阵的存储方式如下：首先，我们需要记录矩阵的行数和列数，以及非零元素的个数。

然后，我们使用一个数组来存储非零元素的值，另外还需要两个数组来存储非零元素所在的行和列的信息。

这样，我们就可以通过这三个数组来表示整个矩阵了。

举个例子来说明三元组带状矩阵的存储方式。

假设有一个5x5的矩阵，其中只有4个非零元素，分别是2、4、6和8。

那么我们可以使用如下的三个数组来表示这个矩阵：值数组：[2, 4, 6, 8]行数组：[1, 2, 3, 4]列数组：[1, 2, 3, 4]通过这三个数组，我们就可以还原出原始的矩阵。

在这个例子中，我们可以得到如下的矩阵：2 0 0 0 00 4 0 0 00 0 6 0 00 0 0 8 00 0 0 0 0可以看到，通过三元组带状矩阵的存储方式，我们只需要存储非零元素的信息，而零元素则可以省略不存储。

这样就大大减少了存储空间的使用。

而带状矩阵是指矩阵中非零元素所在的行和列的分布呈带状结构。

带状矩阵可以用来表示一些具有特定规律的矩阵，比如对角线元素较多的矩阵。

在带状矩阵中，非零元素分布在主对角线及其附近的带状区域内，其宽度可以根据实际情况确定。

通过使用带状矩阵的特性，我们可以进一步优化三元组带状矩阵的存储方式。

在存储非零元素的值、行和列的数组中，我们可以按照带状矩阵的分布规律来存储元素的信息，这样可以进一步减少存储空间的使用。

数据结构实验指导书计算机学院专业基础教研室2004年3月实验一线性表及其应用一、实验目的1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。

2.掌握线性表的顺序存储结构的定义及C语言实现。

3.掌握线性表的链式存储结构——单链表的定义及C语言实现。

4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。

5.掌握线性表在链式存储结构——单链表中的各种基本操作。

二、实验内容1.顺序线性表的建立、插入及删除。

2.链式线性表的建立、插入及删除。

三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。

3.建立一个带头结点的单链表，结点的值域为整型数据。

要求将用户输入的数据按尾插入法来建立相应单链表。

四、实现提示1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。

因此，可用C语言的一维数组实现线性表的顺序存储。

在此，我们利用C语言的结构体类型定义顺序表：#define MAXSIZE 1024typedef int elemtype; /* 线性表中存放整型元素*/typedef struct{ elemtype vec[MAXSIZE];int len; /* 顺序表的长度*/}sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。

2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。

3.单链表的结点结构除数据域外，还含有一个指针域。

用C语言描述结点结构如下：typedef int elemtype;typedef struct node{ elemtype data; //数据域struct node *next; //指针域}linklist;注意结点的建立方法及构造新结点时指针的变化。

数据结构与程序设计实验实验报告哈尔滨工程大学实验报告四一、问题描述哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。

要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。

统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat 中。

根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt 文件中。

压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。

解压：将CodeFile.dat 文件利用哈夫曼树译码解压，恢复为源文件。

二、数据结构设计由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。

1.使用结构体数组统计词频，并存储:typedef struct Node{int weight; //叶子结点的权值char c; //叶子结点int num; //叶子结点的二进制码的长度}LeafNode[N];2.使用结构体数组存储哈夫曼树:typedef struct{unsigned int weight;//权值unsigned int parent, LChild, RChild;}HTNode,Huffman[M+1]; //huffman树3.使用字符指针数组存储哈夫曼编码表：typedef char *HuffmanCode[2*M]; //haffman编码表三、算法设计1.读取文件，获得字符串void read_file(char const *file_name, char *ch){FILE *in_file = Fopen(file_name, "r");unsigned int flag = fread(ch, sizeof(char), N, in_file);if(flag == 0){printf("%s读取失败\n", file_name);fflush(stdout);}printf("读入的字符串是: %s\n\n", ch);Fclose(in_file);int len = strlen(ch);。