数据压缩实验

实验二图像预测编码

一、实验题目:

图像预测编码：

二、实验目的:

实现图像预测编码和解码.

三、实验内容:

给定一幅图片，对其进行预测编码，获得预测图像，绝对残差图像, 再利用预测图像和残差图像进行原图像重建并计算原图像和重建图像误差.

四、预备知识:

预测方法，图像处理概论。

五、实验原理:

根据图像中任意像素与周围邻域像素之间存在紧密关系,利用周围邻域四个像素来进行该点像素值预测,然后传输图像像素值与其预测值的差值信号，使传输的码率降低，达到压缩的目的。

六、实验步骤:

(1)选取一幅预测编码图片;

(2)读取图片内容像素值并存储于矩阵;

(3)对图像像素进行预测编码;

(4)输出预测图像和残差图像;

(5)根据预测图像和残差图像重建图像;

(6)计算原预测编码图像和重建图像误差.

七、思考题目:

如何采用预测编码算法实现彩色图像编码和解码.

八、实验程序代码:

预测编码程序1:

编码程序:

i1=imread('lena.jpg');

if isrgb(i1)

i1=rgb2gray(i1);

end

i1=imcrop(i1,[1 1 256 256]);

i=double(i1);

[m,n]=size(i);

p=zeros(m,n);

y=zeros(m,n);

y(1:m,1)=i(1:m,1);

p(1:m,1)=i(1:m,1);

y(1,1:n)=i(1,1:n);

p(1,1:n)=i(1,1:n);

y(1:m,n)=i(1:m,n);

p(1:m,n)=i(1:m,n);

p(m,1:n)=i(m,1:n);

y(m,1:n)=i(m,1:n);

for k=2:m-1

for l=2:n-1

y(k,l)=(i(k,l-1)/2+i(k-1,l)/4+i(k-1,l-1)/8+i(k-1,l+1)/8);

p(k,l)=round(i(k,l)-y(k,l));

end

end

p=round(p);

subplot(3,2,1);

imshow(i1);

title('原灰度图像');

subplot(3,2,2);

imshow(y,[0 256]);

title('利用三个相邻块线性预测后的图像');

subplot(3,2,3)；

imshow(abs(p),[0 1]);

title('编码的绝对残差图像');

解码程序

j=zeros(m,n);

j(1:m,1)=y(1:m,1);

j(1,1:n)=y(1,1:n);

j(1:m,n)=y(1:m,n);

j(m,1:n)=y(m,1:n);

for k=2:m-1

for l=2:n-1

j(k,l)=p(k,l)+y(k,l);

end

end

for r=1:m

for t=1:n

d(r,t)=round(i1(r,t)-j(r,t));

end

end

subplot(3,2,4);

imshow(abs(p),[0 1]);

title('解码用的残差图像');

subplot(3,2,5);

imshow(j,[0 256]);

title('使用残差和线性预测重建后的图像');

subplot(3,2,6);

imshow(abs(d),[0 1]);

title('解码重建后图像的误差');

九、实验结果:

图2.1 Lena图像预测编码实验结果

预测编码程序2:

x=imread('e:\imagebase\cameraman.jpg');

figure(1)

subplot(2,3,1);

imshow(x);

title('原始图像');

subplot(2,3,2);

imhist(x);

title('原始图像直方图');

subplot(2,3,3);

x=double(x);

x1=yucebianma(x);

imshow(mat2gray(x1));

title('预测误差图像');

subplot(2,3,4);

imhist(mat2gray(x1));

title('预测误差直方图');

x2=yucejiema(x1);

subplot(2,3,5);

imshow(mat2gray(x2));

title('解码图像');

e=double(x)-double(x2);

[m,n]=size(e);

erms=sqrt(sum(e(:).^2)/(m*n));

%预测编码函数；

%一维无损预测编码压缩图像x，f为预测系数，如果f默认，则f=1，即为前值预测

function y=yucebianma(x,f)

error(nargchk(1,2,nargin))

if nargin<2

f=1;

end

x=double(x);

[m,n]=size(x);

p=zeros(m,n);

xs=x;

zc=zeros(m,1);

if length(f)>1

for j=1:length(f)

xs=[zc xs(:,1:end-1)];

p=p+f(j)*xs;

end

y=x-round(p);

else

xs=[zc xs(:,1:end-1)];

p=xs;

y=x-round(p);

end

% yucejiema是解码程序,与编码程序用的是同一个预测器function x=yucejiema(y,f)

error(nargchk(1,2,nargin));

if nargin<2

f=1;

end

if length(f)>1

f=f(end:-1,1);

[m,n]=size(y);

order=length(f);

x0=zeros(m,n+order);

for j=1:n

jj=j+order;

for i=1:m

tep=0.0;

for k=order:-1:1

tep=tep+f(k)*x0(i,jj-order-1+k);

end

x0(i,jj)=y(i,j)+tep;

end

end

x=x0(:,order+1:end);

else

[m,n]=size(y);

x0=zeros(m,n+1);

for j=1:n

jj=j+1;

for i=1:m

x0(i,jj)=y(i,j)+x0(i,jj-1);

end

end

x=x0(:,2:end);

end

图2.2 摄影师图像预测编码实验结果

实验三图像熵编码与压缩

一、实验题目：

图像熵编码与压缩

二、实验目的：

学习和理解建立在图像统计特征基础上的熵编码压缩方法。

三、实验内容：

（1）编程实现二值文本图像的行程编码。

（2）编程实现灰度图像的霍夫曼编码，并计算图像熵、平均码字长度及

编码效率。

四、预备知识：

（1）熟悉行程编码原理。

（2）熟悉霍夫曼编码原理。

（3）熟悉在MATLAB环境下对图像文件的I/O操作。

五、实验原理：

（1）行程编码

行程编码是将一行中颜色相同的相邻像素用一个计数值和该颜色值来代替。比如，aaabbcccccdddeeee可以表示为3a2b5c3d4e。如果一幅图像由很多块颜色相同的大面积区域组成，则采用行程编码可大大提高压缩效率，尤其适用于二值图像。但当图像中每两个相邻像素的颜色都不相同时，采用这种方法不但不能实现数据压缩，反而使数据量增加一倍。因此，对复杂的图像都不能单纯地采用行程编码。

（2）霍夫曼编码

霍夫曼编码是一种代码长度不均匀的编码方法。它的基本原理是按信源符号出现的概率大小进行排序，出现概率大的分配短码，反之则分配长码。

霍夫曼编码基本步骤如下：

步骤1：统计图像每个灰度级（信息符号）出现的概率，并按概率从大到小进行排序。

步骤2：选出概率最小的两个值进行组合相加，形成的新概率值和其他概率值形成一个新的概率集合。

步骤3：重复步骤2，反复利用合并和排序的方法，直到只有两个概率为止。

步骤4：分配码字，对最后两个概率一个赋予“0”码字，一个赋予“1”

码字。

如此反向进行到开始的概率排列，这样就得到了各个符号的霍夫曼编码。

六、实验步骤：

（1）编程实现二值文本图像的行程编码。

（2）编程实现连续灰度图像的霍夫曼编码，并计算图像熵、平均码字长度及编码效率。

七、思考题目：

将行程编码与霍夫曼编码结合，能否提高压缩效果？试验证之。

八、实验程序代码：

（1）二值文本图像的行程编码程序：

clear,close all

t=imread('text.png');

ts=logical(t);

codetable=zeros(1,20000);

[m,n]=size(ts);

nn=n+1;

icodecount=1;

for i=1:m

p1=ts(i,1);%第i行，第1个像素

ipcount=1;%同一灰度值连续出现的次数

for j=2:n

p2=ts(i,j);

if ((p1==p2)&(ipcount

ipcount=ipcount+1;

else

codetable(icodecount)=ipcount;

codetable(icodecount+1)=p1;

icodecount=icodecount+2;

p1=p2;

ipcount=1;

end;

end;

codetable(icodecount)=ipcount;

codetable(icodecount+1)=p1;

icodecount=icodecount+2;

codetable(icodecount)=nn;%行结束符号

icodecount=icodecount+1;

end;

codetable(icodecount)=65535;%码表结束符号

（2）连续灰度图像的霍夫曼编码程序代码function s=reduce(p)

s=cell(length(p),1);

for i=1:length(p)

s{i}=i;

end;

n=size(s,1);

while n>2

[p,i]=sort(p);

p(2)=p(1)+p(2);

p(1)=[];

s=s(i);

s{2}={s{1},s{2}};

s(1)=[];

n=size(s,1);

end;

function makecode(sc,codeword)

global CODE

if isa(sc,'cell')

makecode(sc{1},[codeword 0]);

makecode(sc{2},[codeword 1]);

else

CODE{sc}=char('0'+codeword); end;

function CODE=huffman(p)

global CODE

CODE=cell(length(p),1);

if length(p)>1

p=p/sum(p);

s=reduce(p);

makecode(s,[]);

else

CODE={'1'};

end;

function y=mat2huff(x)

y.size=uint32(size(x));

x=round(double(x));

xmin=min(x(:));

xmax=max(x(:));

pmin=double(int16(xmin)); pmin=uint16(pmin+32768); y.min=pmin;

x=x(:)';

h=histc(x,xmin:xmax); maxh=max(h);

if maxh>65535

h=65535*h/maxh; end;

h=uint16(h);

y.hist=h;

map=huffman(double(h)); hx=map(x(:)-xmin+1);

hx=char(hx)';

hx=hx(:)';

hx(hx==' ')=[];

ysize=ceil(length(hx)/16); hx16=repmat('0',1,ysize*16); hx16(1:length(hx))=hx;

hx16=reshape(hx16,16,ysize); hx16=hx16'-'0';

twos=pow2(15:-1:0);

%y.code=uint16(sum(t3,2))'; t1=ones(ysize,1);

t2=twos(t1,:);

t3=hx16.*t2;

t4=sum(t3,2);

y.code=uint16(t4)';

实验四 图像DCT 变换编码与压缩

一、实验题目：

图像DCT 变换编码与压缩

二、实验目的：

（1）掌握离散余弦变换DCT 的实现方法，了解DCT 的幅度分布特性，从而加深对DCT 变换的认识。

（2）掌握图像DCT 变换编码的实现方法，从而加深对变换编码压缩图像原理的理解。

三、实验内容：

编程实现图像DCT 变换编码。

四、预备知识：

（1）熟悉DCT 原理。 （2）熟悉变换编码原理。

（3）熟悉在MATLAB 环境下对图像文件的I/O 操作。

五、实验原理：

变换编码是在变换域进行图像压缩的一种技术。图2.2.1显示了一个典型的变换编码系统。

图4.1 变换编码系统

在变换编码系统中，如果正变换采用DCT 变换就称为DCT 变换编码系统。 DCT 用于把一幅图像映射为一组变换系数，然后对系数进行量化和编码。对于大多数的正常图像来说，多数系数具有较小的数值且可以被粗略地量化（或者完全抛弃），而产生的图像失真较小。

DCT 是仅次于K-L 变换的次最佳正交变换，且以获得广泛应用，并成为许多图像编码国际标准的核心。离散余弦变换的变换核为余弦函数，计算速度快，有利于图像压缩和其他处理。

(4.1)

其中，

MATLAB 图像处理工具箱实现离散余弦变换有两种方法：

（1）使用函数dct2，该函数用一个基于FFT 的算法来提高当输入较大的方阵时的计算速度。

（2）使用由dctmtx 函数返回的DCT 变换矩阵，这种方法较适合于较小的输入方阵（例如8×8或16×16）。

①函数：dct2

实现图像的二维离散余弦变换。调用格式为： B = dct2(A) B = dct2(A,[M N]) B = dct2(A,M,N)

式中A 表示要变换的图像，M 和N 是可选参数，表示填充后的图像矩阵大小，B 表示变换后得到的图像矩阵。

②函数：dctmtx

除了用dct2函数实现二维离散余弦变换，还可用 dctmtx 函数来计算变换矩阵，调用格式为：

D = dctmtx(N)

式中D 是返回N ×N 的DCT 变换矩阵，如果矩阵A 是N ×N 方阵，则A 的DCT 变换可用D ×A ×D ’来计算。这在有时比dct2计算快，特别是对于A 很大的情况。

③函数：idct2

实现图像的二维离散余弦反变换。调用格式为： B = idct2(A) B = idct2(A,[M N]) B = idct2(A,M,N) 式中参数同dct2。

此外，为了实现8×8子块的DCT 图像变换还要用到MATLAB 中的blkproc 函数。将这个函数和函数dctmtx 一起用于块处理可以大大简化运算。调用函数blkproc 的格式为：

B=blkpro(A,[M,N],FUN,P1,P2,…)

其中，A 表示原图像，[M,N]指定了大小为M ×N 的滑动邻域，FUN 是对M ×N 的矩阵进行计算的函数，P i 是传递给FUN 的附加参数。该函数自动实现图像块处理的整个过程。Blkproc 把A 分成M ×N 个块，对每个块调用参数为P1

，

P2，…的函数FUN，并重新将结果组合到输出图像B。

blkproc函数实现n×n矩阵的DCT变换和反变换。编程中可写成：Y=blkproc(F，[8 8]，’P1*x*P2’，H，H’)。同样的道理，blkproc函数还用于量化和反量化。

显示误差直方图可能用到的MATLAB函数有：

Max %找图像差最大值

[ ]=hist %用于生成直方图数据

Bar %显示图像差值直方图

以上函数用MATLAB的help查看具体使用方法。

图4.2显示了采用JPEG标准化矩阵进行DCT变换编码的结果。

六、实验步骤：

DCT变换编码流程如下:

步骤1：设置JPEG标准化数组;

步骤2：求8×8快的DCT变换矩阵;

步骤3: 计算8×8快的DCT变换；

步骤4：对DCT系数量化和反量化；

步骤5：求反量化系数的逆DCT变换；

步骤6：重新显示重建图像、误差图像和误差图像的直方图。

量化时可采用JPEG标准推荐的归一化数组，如表4.1所示。

七、思考题目：

（1）观察图像8×8子块的DCT系数的分布，并分析其特点。

（2）将量化步长分别增大为初始值的2倍、4倍、8倍后再进行DCT变换编码，显示不同量化步长条件下的重建图像、误差图像以及误差图像的直方图。分析重建图像质量和量化步长的关系。

八、实验程序代码：

function y=dctcoder(x,quality)

m=[16 11 10 16 24 40 51 61

12 12 14 19 26 58 60 55

14 13 16 24 40 57 69 56

14 17 22 29 51 87 80 62

18 22 37 56 68 109 103 77

24 35 55 64 81 104 113 92

49 64 78 87 103 121 120 101

72 92 95 98 112 100 103 99]*quality;

[xm,xn]=size(x);

xx=x;

x=double(x);

t=dctmtx(8);

y1=blkproc(x,[8 8],'P1*x*P2',t,t');%DCT

y2=blkproc(y1,[8 8],'round(x./P1)',m);%Q

y3=blkproc(y2,[8 8],'x.*P1',m);%IQ

y=blkproc(y3,[8 8],'P1*x*P2',t',t);%IDCT

subplot(2,2,1);imshow(xx);title('原始图像');

subplot(2,2,2);imshow(mat2gray(y));title('重建图像');%reconstruted image

d=x-y;%original-reconstruted

subplot(2,2,3);imshow(mat2gray(d));title('误差图像');

[h,k]=hist(d(:),512);

subplot(2,2,4);bar(k,h,'k');title('误差图像直方图');

实验五图像小波变换编码与压缩

一、实验题目：

图像小波变换编码与压缩

二、实验目的：

掌握图像压缩编码的原理，熟悉小波变换的基本知识，了解嵌入零数小波编码原理，并应用MATLAB编程实现嵌入零数小波编、解码程序。

三、实验内容：

（1）对图像进行小波分解求取小波系数；

（2）编程实现嵌入零数小波的编码程序；

（3）编程实现嵌入零数小波的解码程序。

四、预备知识：

（1）熟悉图像读写和显示；

（2）理解图像压缩编码的原理；

（3）理解小波变换的原理；

（4）理解嵌入零数小波编码原理。

五、实验原理：

随着多媒体和网络技术的迅猛发展,人们对基于网络的图像传输、浏览和检索等应用提出了愈来愈广泛的需求,研究具有高效的压缩能力、支持用户个性化浏览并适合网络渐进传输的图像编码方法已成为目前静态图像编码领域的研究热点。

在大量的图像编码方法中,Shapiro提出的嵌入式零树小波编码算法(Embedded Zerotree Wavelet encoder ，简称EZW编码)是公认的效率最高的图像渐进式编码（progressive encoding）方法之一,这种算法得到的比特流中的比特按其重要性排序。使用这种算法，编码者能够在任一点结束编码，允许精确到任一个目标比特率或目标失真率。

（1）嵌入零数小波编码算法原理

①内嵌编码(Embedded Coding)

内嵌编码就是编码器将待编码的比特流按重要性的不同进行排序，根据目标码率或失真度大小要求随时结束编码；同样，对于给定码流解码器也能够随时结束解码，并可以得到相应码流截断处的目标码率的恢复图像。内嵌编码的次序是从最重要的位（最高位）到最不重要的位（最低位）逐个发送，直到达到所需码

率时停止。

内嵌编码的输出信息主要包括两部分：排序信息和重要像素的位信息。位信息是编码必不可少的有效信息；排序信息是辅助信息，按其重要性从左到右排列，反映了重要像素在原图上的空间位置，用于恢复原始的数据结构。

一幅图像经过三级小波分解后形成了10个子带，如图5-1所示。小波系数的分布特点是越往低频子带系数值越大，包含的图像信息越多，对视觉比较重要，如图7-1中的LL 3子带。越往高频子带系数值越小，包含的图像信息越少，对视觉来说不太重要。这样对相同数值的系数选择先传较低频的系数的重要比特，后传较高频系数的重要比特。正是由于小波系数具有这些特点，它非常适合于嵌入式图像的编码算法。在JPEG2000标准中以小波变换作为图像编码的变换方法。

图5.1 小波系数间的父子关系

②几个基本概念

一幅原始图像经过变换后得到的是空间分布的小波系数，引入字符来表示每一个小波系数状态，这样更有利于将来的量化和熵编码。

零数根(ZTR)：在本次量化中，该小波系数的幅值小于给定的阈值T ，并且它的子孙后代中任何一个的幅值都比T 小。与此同时，还要求该系数的父节点系数的幅值大于T ；

负大系数(NEG)：在本次量化中，该小波系数的幅值大于给定的阈值T 。但是，它的最高位为1，即它实际的值是一个负数；

正大系数(POS)：在本次量化中，该小波系数的幅值大于给定的阈值T 。并且，它的最高位为0，即它实际的值是一个正数；

孤独零(IZ)：在本次量化中，该小波系数的幅值小于给定阈值T 。但是，它的子孙后代中至少存在一个系数的幅值大于T ，即该小波系数的子孙后代中存在有大系数（无论正负）。与此同时，该系数的父节点的幅值可以为任意值。

零数，在某一量化级中它的任何一个节点都不是大系数，其中，最上层的那个系数就是零数根。

EZW

算法利用小波系数的特点较好的实现了图像编码的嵌入功能，主要包

括：零数预测、用零数结构编码重要图和逐次逼近量化。

③零数预测

一幅经过小波变换的图像按其频带从低到高形成一个树状结构，树根是最低频子带的节点，它有3个孩子分别位于3个次低频子带的相应位置，其余子带（最高频子带除外）的节点都有4个孩子位于高一级子带的相应位置（由于高频子带分辨率增加，所以一个低频子带节点对应有四个高频子带节点，即相邻的2×2矩阵）。这样图2.7.1所示的三级小波分解就形成了深度为4的树。

定义一个零树的数据结构：一个小波系数x，对于一个给定的门限T，如果|x|

④用零树结构编码重要图

重要图包括3种要素：重要系数、孤立零和零树根。其中，对于一个给定的阈值T，如果系数x本身和它的所有子孙都小于T，则该点就称为零树根；如果系数本身小于T，但其子孙至少有一个大于或等于T，则该点就称为孤立零点。在编码时分别用三种符号与之对应。当编码到最高分辨率层的系数时，由于它们没有子孙，零树根不再存在，只需其余两种符号即可。为了有利于内嵌编码，将重要系数的符号与重要图一起编码，这样就要使用四种符号：零树根、孤立零、正重要系数、负重要系数。

⑤逐次逼近量化（SAQ: Successive-Approximation Quantization）

内嵌编码的核心在于采用了逐次逼近的量化方法（SAQ）。SAQ按顺序使用了一系列阈值T0,T1,…,T N-1来判断重要性，其中，T i=T i-1/2，初始阈值T0按如下条件选择，|X j|<2T0，其中X j表示所有变换系数。

在编（译）码过程中，始终保持着两个分离的列表：主表和辅表。主表对应于编码中的不重要的集合或系数，其输出信息起到了恢复各重要值的空间位置结构的作用，而辅表是编码的有效信息，输出为各重要系数的二进制值。

编码分为主、辅两个过程：在主过程中，设定阈值为T i，按上述原理对主表进行扫描编码，若是重要系数，则将其幅值加入辅表中，然后将该系数在数组中置为零，这样当阈值减小时，该系数不会影响新零树的出现；在辅过程中，对辅表中的重要系数进行细化，细化过程类似于比特平面编码。扫描顺序对最终的压缩结果会有些许影响，目前提出的扫描顺序有好几种，比较常见的有如图5.2所示的两种。

图5.2 小波系数的扫描顺序

对阈值T i来说，重要系数的所在区间为[T i,2T i]，若辅表中的重要系数位于[T i,3T i/2]，则用符号“0”表示，重构值为1.25 T i-1；否则用符号“1”表示，重构值为1.75 T i-1。输出的符号“0”、“1”由一个辅扫描表记录。

编码在两个过程中交替进行，在每个主过程前将阈值减半。译码时系数的重构值可以位于不确定区间的任意处，如果采用MMSE准则，则重构值应位于不确定区间的质心处。

SAQ是和位平面编码直接关联的，它是EZW快速算法的基础。

（2）算法分析

在图像的低比特率编码中，用来表示非零系数所在位置的开销远远大于用来表示非零系数值的开销。零树结构正是一种描述图像经过小波变换后非零数值位置的有效方法。

EZW的编码思想是不断扫描变换后的图像，生成多棵零树来对图像编码：一棵零树的形成需要对图像进行两次扫描。在生成第一棵零树时，首先找出变换后图像的最大绝对值系数，用它对应的T0作初始阈值，对图像进行第一次扫描。将图像中绝对值小于阈值的系数都看作零，然后按前面的符号定义形成零树。在第二次扫描中，对那些绝对值大于阈值的节点（POS和NEG），按其绝对值是否大于阈值的1.5倍附加一个比特1或0来描述其精度。

这样做的目的是减小非零节点系数值的变换范围，使其适应下一次阈值减半后的比特附加。而后将阈值减半，再经两次扫描生成第二棵零树，在第一次扫描生成零树时，以前已经大于阈值的节点不再考虑，而第二次扫描附加比特时则要考虑以前数值较大的节点以保证精度。如此重复下去，不断生成零树，直到达到需要的编码精度为止。

EZW算法也存在一些问题：

①由于编码时它形成多棵零树，因而要多次扫描图像，效率低。且每一棵树必须在前一棵树形成之后才能形成，难以用并行算法优化；

②对所有频域进行等同重要度的编码，不能充分利用小波变换的特点。改进办法之一是把最低频子图与其它子图分开处理，对其进行单独得无失真编码；

③在一棵零树中包含的元素越多，越有利于数据压缩。在EZW算法中存在这样的树间冗余，在后续算法如SPIHT中则进一步利用了这种树间冗余；

④通过对小波系数的分析发现，在同一子带中相邻元素间有一定的相关性，尤其在高频子带存在大量的低值元素，所以可以通过子带中的集合把大量的这种低值元素组织到一起，达到数据压缩的目的。EZW算法并没有充分利用这种相关性。

以Lena.bmp的局部图像（128×128）为例，图5.3显示了该图经过三层小波变换后的小波系数分布。

图5.3 一幅图像三层小波变换后的小波系数分布该图经过EZW算法编码后每级编码主表及辅表得到的部分数据流显示如下（此处扫描顺序为RASTER scan）：

主表：Znnnznznzzzzzzznnznnnzznzzzzzzznnznnzzn

zzzzzzzznnzzzznnnzzzzzznnnzzzzzzzzzppp

辅表：0000000011001101011100011000011100000100

000000100100101101000000000

(3)嵌入零数小波解码算法

解码过程其实与主扫描过程非常类似，按照扫描次序扫描解码矩阵。

①初始化

获取扫描次序列表，初始化符号矩阵，创建以下几个空表：重要系数重构列表，量化器编号列表，上一次解码用到的辅扫描表。

获取本级解码需要的主扫描表和辅扫描表。创建解码矩阵，量化符号列表编号，主扫描表扫描编号。

压缩技术实验编码

压缩技术实验编码 实验一统计编码 实验目的 1.熟悉统计编码的原理 2.掌握r元Huffman编码的方法； 3.了解Huffman编码效率及冗余度的计算; 二、实验原理 霍夫曼编码，又称最佳编码，根据字符出现概率来构造平均长度最短的变长编码。 Huffman编码步骤： (1)把信源符号x i(i=1,2,…按出现概率的值由大到小的顺序排列； (2)对两个概率最 小的符号分别分配以“ 0和“ 1,'然

后把这两个概率相加作为一个新的辅助符号的概率； (3)将这个新的辅助符号与其他符号一起重新按概率大小顺序排列； ⑷跳到第2步，直到出现概率相加为1为止； (5)用线将符号连接起来，从而得到一个码树，树的N个端点对应N个信源符号； (6)从最后一个概率为1的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“ 0或“ 1顺序排列起来，就是端点所对应的信源符号的码字。 以上是二元霍夫曼编码。如果是r元霍夫曼编码，则应该如何做呢？ 在HUFFMAN 编码方案中，为出现概率较小的信源输出分配较长的码字，而对那些出现可能性较大的信源输出分配较短的码字。为此，首先将r 个最小可能的信源输出合并成为一个新的输出，该输出的概率就是上述的r 个输出的概率之和。重复进行该过程直到只剩下一个输出为止。信源符号的个数q 与r 必须满足如下的关系式： q = (r-1) n + r n 为整数如果不满足上述关系式，可通过添加概率为零的信源符号来满足。这样就生成了一个树，从该树的根节点出发并将0、1 分别分配给任何r 个来自于相同节点的 分支，生成编码。可以证明用这种方法产生的编码在前向树类

数据结构实验指导书(2016.03.11)

《数据结构》实验指导书 郑州轻工业学院 2016.02.20

目录 前言 (3) 实验01 顺序表的基本操作 (7) 实验02 单链表的基本操作 (19) 实验03 栈的基本操作 (32) 实验04 队列的基本操作 (35) 实验05 二叉树的基本操作 (38) 实验06 哈夫曼编码 (40) 实验07 图的两种存储和遍历 (42) 实验08 最小生成树、拓扑排序和最短路径 (46) 实验09 二叉排序树的基本操作 (48) 实验10 哈希表的生成 (50) 实验11 常用的内部排序算法 (52) 附：实验报告模板 .......... 错误！未定义书签。

前言 《数据结构》是计算机相关专业的一门核心基础课程，是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础，也是很多高校考研专业课之一。它主要介绍线性结构、树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法，并在此基础上介绍一些典型算法及其时、空效率分析。这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中的表示、存储和运算，培养学生能够设计有效表达和简化算法的数据结构，从而提高其程序设计能力。通过学习，要求学生能够掌握各种数据结构的特点、存储表示和典型算法的设计思想及程序实现，能够根据实际问题选取合适的数据表达和存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。另外本课程的学习过程也是进行复杂程序设计的训练过程，通过算法设计和上机实践的训练，能够培养学生的数据抽象能力和程序设计能力。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。 一、实验目的 本课程实验主要是为了原理和应用的结合，通过实验一方面使学生更好的理解数据结构的概念

数据压缩技术综述

龙源期刊网 https://www.doczj.com/doc/8c15974687.html, 数据压缩技术综述 作者：汪见晗 来源：《科学与财富》2016年第04期 摘要：在现今的电子信息技术领域，正发生着一场有长远影响的数字化革命。由于数字 化的多媒体信息尤其是数字视频、音频信号的数据量特别庞大，如果不对其进行有效的压缩就难以得到实际的应用。因此，数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。本文从专利文献的视角对数据压缩技术的发展进行了全面的统计分析，总结了与数据压缩相关的专利申请趋势、主要申请人分布，介绍了数据压缩技术的重点技术分支及其发展历程，并分析了全球数据压缩技术演进特点，并绘制了国内重点申请人的技术发展路线图。 关键词：数据压缩；发展路线 1 数据压缩介绍 1.1 数据压缩的分类 目前，通用的主流压缩方法分为无损压缩和有损压缩。无损压缩利用数据的统计冗余进行压缩。数据统计冗余度的理论限制为2：1到5：1，所以无损压缩的压缩比一般比较低。这类方法广泛应用于文本数据、程序和特殊应用场合的图像数据等需要精确存储数据的压缩，通常的无损压缩编码方法有香农-范诺编码，霍夫曼（Huffman）编码，算术编码，字典压缩编码等。 有损压缩方法利用了人类视觉、听觉对图像、声音中的某些频率成分不敏感的特性，允许压缩的过程中损失一定的信息。虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响较小，却换来了比较大的压缩比。有损压缩广泛应用于语音、图像和视频数据的压缩，按照应用领域来分，有损压缩编码分为图像压缩编码，视频压缩编码，音频压缩编码。 2 数据压缩专利申请数据分析 本章主要对全球和国内数据压缩专利申请情况以及国内外专利重要申请人进行分析，从中得到技术发展趋势，以及各阶段专利申请人所属的国家分布和主要申请人。其中以每个同族中最早优先权日期视为该申请的申请日，一系列同族申请视为一件申请。 2.1 全球专利申请状况 2.1.1 全球数据压缩专利申请量

数据结构实验指导书

《数据结构》实验指导书 实验一顺序表 实验目的： 熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。 实验要求： 了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。 实验内容： 1、编写程序实现在线性表中找出最大的和最小的数据元素，并符合下列要求： （1）设数据元素为整数，实现线性表的顺序存储表示。 （2）从键盘输入10个数据元素，利用顺序表的基本操作建立该表。 （3）利用顺序表的基本操作，找出表中最大的和最小的数据元素（用于比较的字段为整数）。 2、编写一个程序实现在学生成绩中找出最高分和最低分，并符合下列要求： （1）数据元素为学生成绩（含姓名、成绩等字段）。 （2）要求尽可能少地修改第一题的程序来得到此题的新程序，即要符合第一题的所有要求。（这里用于比较的字段为分数） 实验二链表 实验目的： 熟悉链表的逻辑特性、存储表示方法的特点和链式表的基本操作。 实验要求： 了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。

实验内容： 1、编写一个程序建立存放学生成绩的有序链表并实现相关操作，要求如下： （1）设学生成绩表中的数据元素由学生姓名和学生成绩字段组成，实现这样的线性表的链式存储表示。 （2）键盘输入10个（或若干个，特殊数据来标记输入数据的结束）数据元素，利用链表的基本操作建立学生成绩单链表，要求该表为有序表 并带有头结点。（用于比较的字段为分数）。 （3）输入关键字值x，打印出表中所有关键字值<=x的结点。（用于比较的关键字字段为分数）。 （4）输入关键字值x，删除表中所有关键字值<=x的结点。（用于比较的关键字字段为分数）。 （5）输入关键字值x，并插入到表中，使所在的链表仍为有序表。（用于比较的字段为分数）。 实验三栈的应用 实验目的： 熟悉栈的逻辑特性、存储表示方法和栈的基本操作。 实验要求： 了解并熟悉栈的逻辑特性、顺序和链式存储表示方法和栈的基本操作的实现和应用。 实验内容： (1)判断一个表达式中的括号（仅有一种括号，小、中或大括号） 是否配对。编写并实现它的算法。 (2)用不同的存储方法，求解上面的问题。 (3)* 若表达式中既有小括号，又有大括号（或中括号），且允许 互相嵌套，但不能交叉，写出判断这样的表达式是否合法的算 法。如 2+3*（4-{5+2}*3）为合法；2+3*（4-{5+2 * 3} 、 2+3*（4-[5+2 * 3）为不合法。

2017数据结构实验指导书

《数据结构》实验指导书 贵州大学 电子信息学院 通信工程

目录 实验一顺序表的操作 (3) 实验二链表操作 (8) 实验三集合、稀疏矩阵和广义表 (19) 实验四栈和队列 (42) 实验五二叉树操作、图形或网状结构 (55) 实验六查找、排序 (88) 贵州大学实验报告 (109)

实验一顺序表的操作 实验学时：2学时 实验类型：验证 实验要求：必修 一、实验目的和要求 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。 2、以线性表的各种操作（建立、插入、删除等）的实现为重点。 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。 二、实验内容及步骤要求 1、定义顺序表类型，输入一组整型数据，建立顺序表。 typedef int ElemType; //定义顺序表 struct List{ ElemType *list; int Size; int MaxSize; }; 2、实现该线性表的删除。 3、实现该线性表的插入。 4、实现线性表中数据的显示。 5、实现线性表数据的定位和查找。 6、编写一个主函数，调试上述算法。 7、完成实验报告。 三、实验原理、方法和手段 1、根据实验内容编程，上机调试、得出正确的运行程序。 2、编译运行程序，观察运行情况和输出结果。 四、实验条件 运行Visual c++的微机一台 五、实验结果与分析 对程序进行调试，并将运行结果进行截图、对所得到的的结果分析。 六、实验总结 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等，并将其写入实验报告中。

【附录----源程序】 #include #include using namespace std; typedef int ElemType; struct List { ElemType *list; int Size; int MaxSize; }; //初始化线性表 bool InitList(List &L) { L.MaxSize=20; L.list=new ElemType[L.MaxSize]; for(int i=0;i<20&&L.list==NULL;i++) { L.list=new ElemType[L.MaxSize]; } if(L.list==NULL) { cout<<"无法分配内存空间，退出程序"<L.Size+1||pos<1) { cout<<"位置无效"<

数据结构实验报告记录文件压缩

数据结构实验报告记录文件压缩

————————————————————————————————作者：————————————————————————————————日期：

数据结构与程序设计实验 实验报告 课程名称数据结构与程序设计实验课程编号0906550 实验项目名称文件压缩 学号年级 姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静 实验室名称地点21B276 哈尔滨工程大学

实验报告四 实验课名称：数据结构与程序设计实验 实验名称：文件压缩 班级：学号：姓名：时间：2016.04.21 一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树， 并将该哈夫曼树保存到文件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);

《数据结构》实验指导书

《数据结构》实验指导书 实验类别：课内实验实验课程名称：数据结构 实验室名称：软件工程实验室实验课程编号：N02070601 总学时：64 学分： 4 适用专业：计算机科学与技术、网络工程、物联网工程、数字媒体专业 先修课程：计算机科学导论、离散数学 实验在教学培养计划中地位、作用： 数据结构是计算机软件相关专业的主干课程，也是计算机软硬件专业的重要基础课程。数据结构课程实验的目的是通过实验掌握数据结构的基本理论和算法，并运用它们来解决实际问题。数据结构课程实验是提高学生动手能力的重要的实践教学环节，对于培养学生的基本素质以及掌握程序设计的基本技能并养成良好的程序设计习惯方面发挥重要的作用。 实验一线性表的应用（2学时） 1、实验目的 通过本实验，掌握线性表链式存储结构的基本原理和基本运算以及在实际问题中的应用。 2、实验内容 建立某班学生的通讯录，要求用链表存储。 具体功能包括： （1）可以实现插入一个同学的通讯录记录； （2）能够删除某位同学的通讯录； （3）对通讯录打印输出。 3、实验要求 （1）定义通讯录内容的结构体； （2）建立存储通讯录的链表结构并初始化； （3）建立主函数： 1）建立录入函数（返回主界面） 2）建立插入函数（返回主界面） 3）建立删除函数（返回主界面） 4）建立输出和打印函数（返回主界面） I）通过循环对所有成员记录输出 II）输出指定姓名的某个同学的通讯录记录 5）退出 实验二树的应用（2学时） 1、实验目的 通过本实验掌握二叉排序树的建立和排序算法，了解二叉排序树在实际中的应用并熟练运用二叉排序树解决实际问题。 2、实验内容 建立一个由多种化妆品品牌价格组成的二叉排序树，并按照价格从低到高的顺序 打印输出。 3、实验要求 （1）创建化妆品信息的结构体； （2）定义二叉排序树链表的结点结构； （3）依次输入各类化妆品品牌的价格并按二叉排序树的要求创建一个二叉排序树链表；（4）对二叉排序树进行中序遍历输出，打印按价格从低到高顺序排列的化妆品品牌信息。 实验三图的应用（2学时）

多媒体技术基础(数据压缩、标准、音频、图像)作业及答案

第二章作业 作业总体要求： 1.认真独立的完成 2.让文件名重新命名为自己的学号，然后通过http://10.66.4.241提交。 一．选择题 1.下列说法中不正确的是【B】。 A.有损压缩法会减少信息量 B.有损压缩法可以无失真地恢复原始数据 C.有损压缩法是有损压缩 D.有损压缩法的压缩比一般都比较大 2.下列属于无损压缩的是【B 】。 A．WA VE文件压缩成MP3文件 B.TXT文件压缩成RAR文件 C. BMP文件压缩成JPEG文件 D.A VI文件压缩成RM文件 3.图像序列中的两幅相邻图像，后一幅图像与前一幅图像之间有较大的相关， 这是【 D 】。 A. 空间冗余 B.时间冗余 C.信息熵冗余 D.视觉冗余 4.衡量数据压缩技术性能好坏的主要指标是【C】。 （1）压缩比（2）算法复杂度（3）恢复效果（4）标准化 A. （1）（3） B. （1）（2）（3） C. （1）（3）（4） D.全部 5.MPEG标准不包括下列哪些部分【C 】。 A.MPEG视频 B.MPEG音频 C.MPEG系统 D.MPEG编码 6.下列属于静态图像编码和压缩标准的是【B 】。 A．JPEG B.MPEG-1 C．MPEG-2 D.MPEG-4 7.声音信号是声波振幅随时间变化的【A 】信号. A.模拟 B.数字

C.无规律 D.有规律 8.在数字视频信息获取与处理过程中，下述顺序正确的是【A 】。 A.采样、A/D变换、压缩、存储、解压缩、D/A变换 B.采样、D/A变换、压缩、存储、解压缩、A/D变换 C.采样、压缩、A/D变换、存储、解压缩、D/A变换 D.采样、压缩、D/A变换、存储、解压缩、A/D变换 9.一般来说,表示声音的质量越高,则【C 】 A.量化位数越多和采样频率越低 B.量化位数越少和采样频率越低 C.量化位数越多和采样频率越高 D.量化位数越少和采样频率越高 10.5分钟双声道、16位采样位数、44.1kHZ采样频率声音的不压缩数据量是 【 B 】。 A. 48.47MB B. 50.47MB C. 105.84MB D. 25.23MB 11.下列采集的波形声音【 D 】的质量最好。 A、单声道,8位量化，22.05kHz采样频率 B、双声道,8位量化，44.1kHz采样频率 C、单声道,16位量化，22.05kHz采样频率 D、双声道,16位量化，44.1kHz采样频率 12.频率在20HZ-20KHZ的被称为【 A 】 A. 可听声波 B. 次声波 C.超声波 D.超音波 13.MIDI是音乐与【 A 】结合的产物. A.计算机 B.通信 C.高科技 D.通讯 14.Windows中使用录音机录制的声音文本的格式是【B 】 A. MIDI B.WA V C.MP3 D.MOD

数据结构实验指导书(C版)

数据结构实验指导书（C语言版） 2017年9月

目录 1、顺序表的实现 (1) 2、链栈的实现 (3) 3、前序遍历二叉树 (5) 4、图的深度优先遍历算法 (7) 5、散列查找 (9)

1、顺序表的实现 1. 实验目的 ⑴掌握线性表的顺序存储结构； ⑵验证顺序表及其基本操作的实现； ⑶理解算法与程序的关系，能够将顺序表算法转换为对应的程序。 2. 实验内容 ⑴建立含有若干个元素的顺序表； ⑵对已建立的顺序表实现插入、删除、查找等基本操作。 3. 实现提示 定义顺序表的数据类型——顺序表结构体SeqList，在SeqList基础上实现题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。简单起见，本实验假定线性表的数据元素为int型，要求学生： （1）将实验程序调试通过后，用模板类改写； （2）加入求线性表的长度等基本操作； （3）重新给定测试数据，验证抛出异常机制。 4. 实验程序 在编程环境下新建一个工程“顺序表验证实验”，并新建相应文件，文件包括顺序表结构体SeqList的定义，范例程序如下： #define MaxSize 100 /*假设顺序表最多存放100个元素*/ typedef int DataType; /*定义线性表的数据类型，假设为int型*/ typedef struct { DataType data[MaxSize]; /*存放数据元素的数组*/ int length; /*线性表的长度*/ } SeqList; 文件包括建立顺序表、遍历顺序表、按值查找、插入操作、删除操作成员函数的定义，范例程序如下： int CreatList(SeqList *L, DataType a[ ], int n) { if (n > MaxSize) {printf("顺序表的空间不够，无法建立顺序表\n"); return 0;} for (int i = 0; i < n; i++) L->data[i] = a[i]; L->length = n; return 1; }

实验六压缩试验

实验六 压缩试验(快速法) 1 试验目的 测定土的湿密度、含水率，计算土样干密度、初始孔隙比，并用此密度、含水率条件下的试样进行压缩试验，根据试验数据绘制孔隙比与压力的关系曲线（即压缩曲线），确定土的压缩系数、压缩模量，评价土体的压缩性。 ⑴掌握以磅秤式(或杠杆式)加压设备测定土压缩系数的方法，并根据试验数据绘制孔隙比与压力的关系曲线（即压缩曲线）； ⑵根据求得的压缩系数21-a 评定土的压缩性。 2 试验方法 ⑴密度试验——环刀法； ⑵含水率试验——烘干法； ⑶压缩试验——快速固结试验法。 3 试验原理 土样在外力作用下便产生压缩，其压缩量的大小是与土样上所加的荷重大小以及土样的性质有关。如在相同的荷重作用上，软土的压缩量就大，而坚密的土则压缩量小；又如在同一种土样的条件下，压缩量随着荷重的加大而增加。因此，我们可以在同一种土样上，施加不同的荷重，一般情况下，荷重分级不宜过大。视土的软硬程度及工程情况可取为12.5、25、50、100、200、300、400、600、800 kPa 等。最后一级荷重应大于土层计算压力的100～200kPa 。这样，便可得不同的压缩量，从而可以算出相应荷重时土样的孔隙比。如图6-1可见，当土样在荷重P 1作用下，压缩量为h ?。一般认为土样的压缩主要由于土的压密使孔隙减少产生的。因此，与未加荷前相比，可得：10e e h -=?。 而土样在荷重P 1作用下产生的应变为 h h ?= ε，从图6-1可得： ) 1(100 100 1 00e h h e e e e e h h +?=-+-=? 式中：1e ——在荷重P 1作用下，土样变形稳定时的孔隙比； 0e 、0 h ——分别为原始土样的孔隙比和高度； h ?——在荷重P 1作用下，土样变形稳定时的压缩量。

数据压缩,算法的综述

数据压缩算法的综述 S1******* 许申益 摘要：数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机通讯领域中的出现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法上一些已经取得的成果，其中包括算术编码、字典式压缩方法以及Huffman码及其改进。 关键字：数据压缩；数据存储；计算机通讯；多媒体技术 1.引言 数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。在数据的存储和表示中常常存在一定的冗余度，一些研究者提出了不同的理论模型和编码技术降低了数据的冗余度。Huffman 提出了一种基于统计模型的压缩方法，Ziv Jacob 提出了一种基于字典模型的压缩方法。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机和通讯两个领域中的出现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法上的一些已经取得的成果。 本文主要介绍了香农范诺编码以及哈弗曼算法的基本思想，运用其算法的基本思想设计了一个文件压缩器，用Java 语言内置的优先队列、对象序列化等功能实现了文件压缩器的压缩和解压功能。 2数据压缩算法的分类 一般可以将数据压缩算法划分为静态的和动态的两类。动态方法又是又叫做适应性（adaptive）方法，相应的，静态方法又叫做非适应性方法（non-adaptive）。 静态方法是压缩数据之前，对要压缩的数据经过预扫描，确定出信源数据的

多媒体数据处理中几种无损压缩算法的比较概要

119 摘要:为了使大容量的多媒体数据在网 络上有效的传输,必须对多媒体数据进行压缩。对多媒体数据压缩中的几种无损压缩方法进行了比较,并对每种方法用一个例子说明。 关键词:数据压缩;霍夫曼树;LZW;二 叉树 引言 随着网络发展的速度越来越快,视频, 音频的广泛应用使得大数据量的传输显得尤为重要,如何更快、更多、更好地传输与存储数据成为数据信息处理的首要问题。 在压缩算法中分为无损压缩和有损压 缩。相对于有损压缩来说,无损压缩的占用空间大,压缩比不高,但是它100%的保存了原始信息,没有任何信号丢失并且音质高,

不受信号源的影响,这点是有损压缩不可比拟的。而且随着时间的推移,限制无损格式的种种因素将逐渐被消除,比如说硬盘容量的急剧增长以及低廉的价格使得无损压缩格式的前景无比光明。 1、无损压缩的原理以及几种常见算法 本质上压缩数据是因为数据自身具有冗 余性。数据压缩是利用各种算法将数据冗余压缩到最小,并尽可能地减少失真,从而提 高传输效率和节约存储空间。 常见的无损压缩算法有,游长编码;香 浓-凡诺算法;霍夫曼算法;LZW算法;下面 详细介绍这些算法或编码步骤,并比较其优缺点。 2、游长编码 也叫行程编码,它是数据压缩中最简单 的一种方法。它的思想是:将图像一行中颜色值相同的相邻象素用一个计数值和该颜色值来代替。例如:aabbbccccdddddeeeeee对

其进行游长编码可得2a3b4c5d6e,可见其效 率很高。但它有两个致命缺点。 一:如果图象中每两个相邻点的颜色 都不同,用这种算法不但不能压缩,反而数 据量会增加,例如对abcdeabcde进行编码得 1a2b3c4d5e1a2b3c4d5e,可见数据量反而增 加了1倍。 二:容错性差。还是以aabbbccccddddde eeeee为例,如果在第二位a出错,例如丢失 了a,那么编码后结果为1a3b4c5d6e,虽然只 有一位发生了错误,但是在恢复数据时,将 和原始数据完全不同。 所以说游长编码在要压缩信息源中的符 号形成连续出现片段时才有效,并且它不是一种自适应的编码方式。 3、香浓-凡诺算法香浓-凡诺算法由贝尔实验室的Shannon 和MIT的Robert Fano开发的。它的编码步骤如下:一:根据符号出现的频率对符号进行排序二:递归的把符号分成两部分,每一部分中的符号具有相似的频率,直到所有的部分只有一个符号为止。这样,就得到一颗二叉树,我们把树中的左支赋为0,把树中的右支赋为1。那么从根节点到节点的路径即为它的编码。例如:对字符串abcccd编码。进行排序后为cabd。递归过程图1-图3。应当指出香浓-凡诺算法的编码结果并不是唯一的,例如在图1的时候可以交换左右子树的位置,在图3的时候也可以交换b,d的位置。香

材料拉伸与压缩试验报告

材料的拉伸压缩实验 【实验目的】 1．研究低碳钢、铸铁的应力——应变曲线拉伸图。 2．确定低碳钢在拉伸时的机械性能（比例极限R p、下屈服强度R eL、强度极限R m、延伸率A、断面收缩率Z等等）。 3. 确定铸铁在拉伸时的力学机械性能。 4.研究和比较塑性材料与脆性材料在室温下单向压缩时的力学性能。 【实验设备】 1.微机控制电子万能试验机； 2.游标卡尺。 3、记号笔 4、低碳钢、铸铁试件 【实验原理】 1、拉伸实验 低碳钢试件拉伸过程中，通过力传感器和位移传感器进行数据采集，A/D转换和处理，并输入计算机，得到F-?l曲线，即低碳钢拉伸曲线，见图1。 对于低碳钢材料，由图1曲线中发现OA直线，说明F正比于?l，此阶段称为弹性阶段。屈服阶段（B-C）常呈锯齿形，表示载荷基本不变，变形增加很快，材料失去抵抗变形能力，这时产生两个屈服点。其中，B'点为上屈服点，它受变形大小和试件等因素影响；B点为下屈服点。下屈服点比较稳定，所以工程上均以下屈服点对应的载荷作为屈服载荷。测定屈服载荷Fs时，必须缓慢而均匀地加载，并应用σs=F s/ A0（A0为试件变形前的横截面积）计算屈服极限。 图1低碳钢拉伸曲线 屈服阶段终了后，要使试件继续变形，就必须增加载荷，材料进入强化阶段。

当载荷达到强度载荷F b后，在试件的某一局部发生显著变形，载荷逐渐减小，直至试件断裂。应用公式σb=F b/A0计算强度极限（A0为试件变形前的横截面积）。 根据拉伸前后试件的标距长度和横截面面积，计算出低碳钢的延伸率δ和端面收缩率ψ，即 % 100 1? - = l l l δ，% 100 1 0? - = A A A ψ 式中，l0、l1为试件拉伸前后的标距长度，A1为颈缩处的横截面积。 2、压缩实验 铸铁试件压缩过程中，通过力传感器和位移传感器进行数据采集，A/D转换和处理，并输入计算机，得到F-?l曲线，即铸铁压缩曲线，见图2。 对铸铁材料，当承受压缩载荷达到最大载荷F b时，突然发生破裂。铸铁试件破坏后表明出与试件横截面大约成45?～55?的倾斜断裂面，这是由于脆性材料的抗剪强度低于抗压强度，使试件被剪断。 材料压缩时的力学性质可以由压缩时的力与变形关系曲线表示。铸铁受压时曲线上没有屈服阶段，但曲线明显变弯，断裂时有明显的塑性变形。由于试件承受压缩时，上下两端面与压头之间有很大的摩擦力，使试件两端的横向变形受到阻碍，故压缩后试件呈鼓形。 铸铁压缩实验的强度极限：σb=F b/A0（A0为试件变形前的横截面积）。 【实验步骤及注意事项】 1、拉伸实验步骤 （1）试件准备：在试件上划出长度为l0的标距线，在标距的两端及中部三个位置上，沿两个相互垂直方向各测量一次直径取平均值，再从三个平均值中取最小值作为试件的直径d0。 （2）试验机准备：按试验机→计算机→打印机的顺序开机，开机后须预热十分钟才可使用。按照“软件使用手册”，运行配套软件。 （3）安装夹具：根据试件情况准备好夹具，并安装在夹具座上。若夹具已 图2 铸铁压缩曲线

数据结构实验指导书

目录 实验规则 (2) 实验环境 (2) 实验报告要求 (3) 实验一单链表（一） (4) 实验二单链表（二） (5) 实验三栈 (6) 实验四二叉树 (7) 实验五最短路径 (8) 实验六内部排序 (9)

实验规则 为了顺利完成实验教学任务，确保人身、设备的安全，培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质，特制定以下实验规则： 1、实验前必须充分预习，完成指定的预习任务。预习要求如下： （1）认真阅读指导书，进行必要的设计与计算。 （2）熟悉实验内容。 （3）预先复习，并按要求编写程序。 （4）未完成预习任务者不得进入实验室。 2、遵守以下纪律： （1）在实验室不得做和实验无关的事情。 （2）进行任课老师指定内容以外的实验，必须经指导教师同意。 （3）遵守纪律，不迟到。 （4）保持实验室内安静、整洁，爱护公物，不许乱写乱画。 实验环境 本实验在386以上的微机上进行，运行环境为VC6.0。

实验报告要求 1、实验题目 2．实验目的 3．实验环境 4．实验内容与完成情况（可以附上自主设计的源程序）5．出现的问题及对问题的解决方案 6．实验思考：（学生对本次实验的收获的总结）

一、实验目的 掌握线性表的链式存储结构及其基本操作。 二、预习要求 1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。 2、根据要求，编写程序准备上机调试。 三、实验内容 实现一个简单的学生信息管理系统，该系统的功能有： 1、利用单链表建立学生基本信息表 2、浏览每个学生的信息 3、根据学号查询某个学生的基本信息 4、添加学生信息到单链表中 5、删除一个学生的信息 四、实现提示 设计结点的结构体类型，包括学生的学号、姓名、年龄、性别；要求设计一个简单的菜单界面，根据需要选择所要进行的操作；构造函数，每一个函数实现上述的一个功能。

数据压缩的基本原理和方法(pdf 87页)

第三章多媒体数据压缩

3.1 数据压缩的 基本原理和方法

3.1 数据压缩的基本原理和方法 ?压缩的必要性 音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。 例如，一幅具有中等分辨率（640×480）的真彩色图像（24b/像素），它的数据量约为7.37Mb/帧，一个 100MB（Byte）的硬盘只能存放约100帧图像。若要达到每秒25帧的全动态显示要求，每秒所需的数据量为 184Mb，而且要求系统的数据传输率必须达到184Mb/s。 对于声音也是如此，若采用16b样值的PCM编码，采样速 率选为44.1kH Z ，则双声道立体声声音每秒将有176KB的 数据量。

3.1 数据压缩的基本原理和方法 ?视频、图像、声音有很大的压缩潜力 信息论认为：若信源编码的熵大于信源的实际熵，该信源中一定存在冗余度。 原始信源的数据存在着很多冗余度：空间冗余、时间冗余、视觉冗余、听觉冗余等。

3.1.1 数据冗余的类型 ?空间冗余：在同一幅图像中，规则物体和规则背景的表面物理特性具有相关性，这些相关性的光成像结果在数字化图像中就表现为数据冗余。 –一幅图象中同一种颜色不止一个象素点，若相邻的象素点的值相同，象素点间（水平、垂直）有冗余。 –当图象的一部分包含占主要地位的垂直的源对象时，相邻 线间存在冗余。

3.1.1 数据冗余的类型 ?时间冗余：时间冗余反映在图像序列中就是相邻帧图像之间有较大的相关性，一帧图像中的某物体或场景可以由其它帧图像中的物体或场景重构出来。 –音频的前后样值之间也同样有时间冗余。 –若图象稳定或只有轻微的改变，运动序列帧间存在冗余。

文件压缩与解压实验报告

院系：计算机学院 实验课程：实验3 实验项目：文本压缩与解压 指导老师： 开课时间：2010 ～ 2011年度第 1学期专业： 班级： 学生： 学号：

一、需求分析 1.本程序能够实现将一段由大写字母组成的内容转为哈弗曼编码的编码功能以及将哈弗曼编码翻译为字符的译码功能。 2.友好的图形用户界面，直观明了，每一个操作都有相应的提示，用户只需按着提示去做，便能轻松实现编码以及译码的效果，编码及译码结果都被保存成txt 文档格式，方便用户查看。 3.本程序拥有极大的提升空间，虽然现在只能实现对大写字母的译码以及编码，但通过改进鉴别的算法，即能够实现小写字母乃至其他特殊符号等的编码。 4.本程序可用于加密、解密，压缩后文本的大小将被减小，更方便传输 5.程序的执行命令包括： 1）初始化 2）编码 3）译码 4）印代码文件 5）印哈弗曼树 6）退出 6.测试数据 （1）THIS PROGRAM IS MY FAVOURITE （2）THIS IS MY FAVOURITE PROGRAM BUT THE REPORT IS NOT 二、概要设计 为实现上述功能，应有哈弗曼结点，故需要一个抽象数据类型。 1.哈弗曼结点抽象数据类型定义为： ADT HaffTree{ 数据对象：HaffNode* ht，HaffCode* hc 基本操作： Haffman(int w[],int n) 操作结果：构造哈弗曼树及哈弗曼编码，字符集权值存在数组w，大小为n setdep() setdep(int p,int l) 操作结果：利用递归，p为哈弗曼节点序号，l为哈弗曼节点深度setloc() 操作结果：设置哈弗曼节点坐标，用以输出到界面 setloc2() 操作结果：设置哈弗曼节点坐标，用以输出到文本，默认状态下不启用 } ADT HaffTree 2.本程序包含4个模块 1）主程序模块： 接受用户要求，分别选择执行①初始化②编码③译码④印代码文件⑤印哈弗曼树⑥退出 2）哈弗曼树单元模块——建立哈弗曼树 3）哈弗曼编码单元模块——进行哈弗曼编码、译码 4）响应用户操作，输出内容到界面或文本 各模块之间的关系如下：

数据结构实验指导书

《数据结构与算法》实验指导书马晓波秦俊平刘利民编 内蒙古工业大学信息工程学院计算机系 2008年9月1日

《数据结构与算法》实验教学大纲 三、实验目的、内容与要求 实验一线性表的创建与访问算法设计(4学时) （一）实验目的 数据结构于算法实验是计算机类本科学生计算机软件知识重要的实验环节，它将使学生从实践上学会用高级语言程序设计、实现复杂的数据结构，为大型软件设计奠定基础。本实验以某种线性表的创建与访问算法设计作为实验内容，举一反三，全面、深刻掌握线性结构的实现方法，培养解决问题的能力。 （二）实验内容 1、编写生成线性表的函数，线性表的元素从键盘输入； 2、编写在线性表中插入元素的函数； 3、编写在线性表中删除元素的函数； 4、编写输出线性表的函数； 5、编写主函数，调用以上各函数，以便能观察出原线性表以及作了插入或删除后线性表的屏 幕输出。 方案一采用顺序存储结构实现线性表。 方案二采用单链表结构实现线性表。 （三）实验要求 1、掌握线性结构的机器内表示； 2、掌握线性结构之上的算法设计与实现； 3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。 实验二二叉树的创建与访问算法设计(4学时) （一）实验目的 本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。 （二）实验内容 1、编写生成二叉树的函数，二叉树的元素从键盘输入； 2、编写在二叉树中插入元素的函数；

3、编写在二叉树中删除元素的函数； 4、编写遍历并输出二叉树的函数。 方案一采用递归算法实现二叉树遍历算法。 方案二采用非递归算法实现二叉树遍历算法。 （三）实验要求 1、掌握树型结构的机器内表示； 2、掌握树型结构之上的算法设计与实现； 3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。 实验三图的创建与访问算法设计(4学时) （一）实验目的 本实验以图的创建与访问算法设计作为实验内容，掌握图型结构的实现方法，培养解决负责问题的能力。 （二）实验内容 1、编写生成图的函数，图的元素从文件输入； 2、编写在图中插入元素的函数； 3、编写在图中删除元素的函数； 4、编写遍历并输出图的函数。 方案一采用BFS深度优先搜索算法实现图的遍历。 方案二采用DFS广度优先搜索算法实现图的遍历。 （三）实验要求 1、掌握图结构的机器内表示； 2、掌握图型结构之上的算法设计与实现； 3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。 四、考核方式 1、学生课前要认真阅读实验教材，理解实验内容与相关理论知识的关系，并完成预习报告； 2、实验课上教师讲解实验难点及需要注意的问题，并对实验数据签字； 3、学生课后要完成实验报告，并将签字的实验数据与实验报告交给带课教师； 4、教师根据学生实验情况，及时对实验内容和方法进行必要的调整和改进。 根据实验预习报告、实验课考勤、课上实验能力与实验效果、实验报告的完成情况确定最终的实验成绩，实验成绩占课程总成绩的10%。 五、建议教材与教学参考书 1、建议教材 [1]严蔚敏、吴伟民主编. 数据结构（C语言版）. 北京：清华大学出版社，1997 2、教学参考书 [1] 严蔚敏、吴伟民主编. 数据结构题集（C语言版）. 北京：清华大学出版社，1997 [2] 李春葆编. 数据结构习题与解析. 北京：清华大学出版社，2002 [3] 刘振鹏主编. 数据结构. 北京：中国铁道出版社，2003 [4] 许卓群编．数据结构．北京：中央电大出版社， 2001 [5] Anany Levitin著．潘彦译．算法设计与分析．北京：清华大学出版社， 2004

数据结构实验报告-文件压缩

数据结构与程序设计实验实验报告 哈尔滨工程大学

实验报告四 一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树， 并将该哈夫曼树保存到文件HufTree.dat 中。 根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并 将字符编码保存到HufCode.txt 文件中。 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件Code。 解压：将Code 文件利用哈夫曼树译码解压，恢复为源文件。 二、数据结构设计 由于哈夫曼树中没有度为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_ const *, char *ch){ FILE *in_file = Fopen(, "r"); unsigned int flag = fread(ch, sizeof(char), N, in_file); if(flag == 0){ printf("%s读取失败\n", ); fflush(stdout); } printf("读入的字符串是: %s\n\n", ch); Fclose(in_file); int len = strlen(ch);