大学幼师常州大学课程设计报告

2020年12月8日发(作者：张治中)

序号

:

学号

:

12453118

C

H

A

N

G

Z

H

O

U

U

N

I

V

I

T

Y

R

S

E

< br>

课

程

设

计

设计课程名称：

C

语言课程设计

题

目：

Data

Compression

学

生

姓

名：

郭宏宇

学

院：

数理学院

专

业

班

级：

应数

121

指

导

教

师：

王军

专业技术职务：

讲师

设计时间：

2013

年

6

月

17

日

?

2013

年

6

月

28

日

常州大学课程设计

目录

1

、引言及设计要求

............... .................................................. .................

3

1.1

引言

.

.... .................................................. ...............................................

3

1.2

设计需求

< p>................................................ .................................................. ........

3

1.2.1

< p>题目要求

..................................... .................................................. ........

3

1.2.2

< p>输出要求

..................................... .................................................. ........

3

2

、 概要设计

....................................... .................................................. ....

3

2.1

数据结构 的描述

........................................ .................................................. ....

3

2.1.1

数据类型的定义

.

............................................... .....................................

3

2.1.2

主要算法流程描 述

.......................................... .....................................

4

2.2

流程图

................................................. .................................................. ...........

4

3

、详细设计及实现

............... .................................................. .................

5

4

、调试分析

............................... .................................................. ..............

5

5

、总结及心得

................................. .................................................. ......

1

1

5.1< /p>

专题总结

................................. .................................................. .....................

11

5.2

心得体会

......................... .................................................. .............................

11

6

、设计日志及参考文献

............. .................................................. .........

1

2

6 .1

设计日志

.............................. .................................................. ........................

1

2

6.2

参 考文献

........................................ .................................................. ..............

1

2

附录：程序源代码

....................... .................................................. .........

1

3

第 一部分：霍夫曼解码器的实现

.............................. .........................................

1

3

第二部分：实现霍夫曼编 码器

......................................... ..................................

1

7

2

常州大学课程设计

1

、引言及设计要求

1.1

引言

在多媒体计算机系 统中，

信息从单一媒体转到了多种媒体，

要表示、

传输和处

理大量的声音、

图像甚至影像视频信息，

其数据量之大是非常惊 人的。

数字化多

媒体信息的数据量是如此巨大，

加之信息 种类多、

实时性要求高，

给数据的存储、

传输以及加工处 理均带来了巨大的压力，

不仅要求计算机有更高的数据处理和数

据传输能 力以及巨大的存储空间，

而且也要求通信信道有更高的带宽。

为了解决

< p>
存储、

处理和传输多媒体数据的问题，

除了提高计算机本身的性能以 及通信信道

的带宽外，

更重要的则是对多媒体数据进行有效的压缩。

因此数据压缩编解码自

然就成为了多媒体技术中最为关键的核心技术。

1.2

设计需求

1.2.1

题目要求

A:

在每一次迭代过程中，

我们需要跟踪的符号

（或复合）

的最低频率和第二

频率最低的发生。

这可以很容易地使用优先队列

（一个链表，

其中的元素总是插

入正确的位置）

。文件

encode.c

包含的模板代码（

pq_insert( )

）的实现优先级

队列。你需要填写缺少的部分。确保你照顾下列条件：

（

i

）队列为空（

ii

）新的

元素在开始前存储进去（

iii

）新元素存储在队列最后或中 间。

B:

符号的使用优先队列的

pq_ pop

功能删除。在一个优先队列中，元素总是

从一开始就删除。

文件

encode.c

包含模板代码来实现这个。

请填写 所缺的部分。

确保你的更新要被删除的元素的指针。

< br>C:

一旦代码树是建立在内存中，

我们需要生成的每个符号的编码字符串。

填

入所缺的代码生成

generate_code()< /p>

。

D:

最后填写缺失的代码来释放所有资 源和内存

,

然后退出代码。

1.2.2

输出要求

程序输出 两个文件

含有编码的输出和

显示霍夫曼编

码。

2

、概要设计

2.1

数据结构的描述

2.1.1

数据类型的定义

struct tnode

{

struct tnode* left; /*used when in tree*/

struct tnode*right; /*used when in tree*/

3

常州大学课程设计

struct tnode*parent;/*used when in tree*/

struct tnode* next; /*used when in list*/

float freq;

int isleaf;

char symbol;

};

struct Symbol

{

};

/*global variables

整体变量

*/

char code[MAX_SYMBOLS][MAX_LEN];

struct tnode* root=NULL;/*tree of symbols*/

struct tnode* qhead=NULL;/*list of current symbols*/

struct cnode* chead=NULL;/*list of code*/

char symbol;

float freq;

2.1.2

主要算法流程描述

< p>
Main

函数调用

pq_insert

函数频率初始 化，调用

pq_pop

、

talloc

、

< p>
pq_insert

函数构建树，调用

generate_code

函数构建代码，调用

dump_code

函

数输出代码，调用

encode

函数实现一个样品的字符串编码。

2.2

流程图

开

始

实

现

霍

夫

曼

编

码

器

分

配

新

的

代

码

在

代

码

功

能

中

显

示

t nodes

的

列

表

插

入< /p>

一

个

元

素

到

优

先

列

表

中

删

除< /p>

第

一

个

元

素

生

成

的

字

符

串

的< /p>

代

码

树

输

出

代

码

文

件

输

出

< p>压

缩

流

main

函

数

霍

夫

曼

解

码

器

的

实

现

压

缩

大

文

件

结

束

4

常州大学课程设计

3

、详细设计及实现

分配新的 代码：动态申请一块区域，用强制类型把它转换成结构体类型

struct tnode

的指针并赋给同类型的指针变量

p

，再将信息赋给申请的区域里。

在代码功能中显示

tnodes

的列表 ：调用

struct

tnode

，输出字符和出现的

频率。

插入一个元素到优先列表中：利用全局变量

qhead

， 分不同的情况将元素插

入到优先列表中。

删除第一个元素：

利用全局变量

qhead

，

分两种情况删除元素。

生成的字符串的代码树：运用递归调用的方法建立一个叶子节点。

输出代码文件：将

code

信息输出到文件（就是

）

。

Main

函数：调用不同的函数完成这个程序。

4

、调试分析

在

main

函数中调用函数，结果如下：

5

常州大学课程设计

6

常州大学课程设计

7

常州大学课程设计

8

常州大学课程设计

显示在二叉树中各个字符的寻找路径

111101

110

! 1

& 01001

' 111100101

( 11101

) 11100

, 011001

- 101110000

. 1111100

/ 010000

9

常州大学课程设计

0 1

1 1

2 10

3 001

4 110

5 011

6 000

7 100

8 11

9 1111

: 1111

; 1

? 1111001001

A 1111001101

B

C 1

D

E

F 1

G 1

H 101110010

I 0110001

J

K 1

L 1

M 1111001000

N 1

O 1

P 0

Q 101

R

S 1111001110

T 011011011

U 1111

V 00

W 1111001100

X 0101

Y

Z 010001

a 1000

b 1111000

c 101111

d 10110

e 001

10

常州大学课程设计

f 100110

g 011010

h 0100

i 0000

j 1

k 0110000

l 10010

m 111001

n 0101

o 0111

p 1111101

q

r 11101

s 0001

t 1010

u 111111

v 0110111

w 111000

x

y 100111

z 1

5

、总结及心得

5.1

专题总结

在本专题的课 程设计中运用了

C

语言的知识设计了数据压缩，

我们利用

C

语言的

知识设计了可以对数据进行压缩的系统，在系统中我们了 解到了霍夫曼编码

（

Huffman Coding

是一 种编码方式，是一种用于无损数据压缩的权编码算法。

1952

年，

David

A.

Huffman

在麻省理工攻读博 士时所发明的，

并发表于

A

Method

for the Construction of Minimum- Redundancy Codes

一文）。数据压缩包含

的内 容很多，

我做的这个程序调用的函数也比较多。

程序包含

7

个调用函数和一

个主函数，主函数分别调用这几个不同功能的函数。分别为：分 配新的代码，在

代码功能中显示

tnodes

的列表，< /p>

插入一个元素到优先列表中，

删除第一个元素，

生成的字符 串的代码树，输出代码文件，输出压缩流。总结：获取

a

，

b

，

c...

的频率；根据频率做霍夫曼二叉树；根据二叉树获 得

a

，

b

，

c...

的编码；编码

到文件中

在设计中我们利用使 用变长编码表对源符号（如文件中的一个字母）进行编码，

其中变长编码表是通过一种评 估来源符号出现机率的方法得到的，

出现机率高的

字母使用较短的编码，

反之出现机率低的则使用较长的编码，

这便使编码之后的

字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。系统不完善，

应进一步 设计与细化

。

5.2

心得体会

首先感谢王老师在课程中和在为期两周的设计过程中的支持。

11

常州大学课程设计

这次是我第一次参加课程设计，

因此刚完成分组拿到课题是还是很紧张的。

由于五人联合完成一个课题，需要较好地处理分步完成和协调好组内同学的配

合。在这 一方面，数据压缩课题是不同于其他课题的。所以在此次课程设计中，

对于我们各位来说 团队精神都得到了很大提升。

在设计的过程中，

除了组内同学

的配合之外，我们还得到了其他同学的答疑和帮助，在此也一并感谢

。

开始时，

看了数据压缩的英文版解释，

大致了解了这个程序分 为三个部分，

第一

部分：霍夫曼解码器的实现：第二部分：实现霍夫曼编 码器；第三部分：压缩大

文件。

第一部分相对其它两个部分简单点，

第二部分应该是其中最难的了。

而且，

对于第二部分所涉及的

C

语言知识，

我也是没有想到的，

因为之前对于链 表、

递

归我还是不了解的，

我也通过这次

C

语言课程设计把落下的知识补上来了。

也许

我做的还不 是很好，

但是，

通过这次课程设计我学会了在

C

语 言编程中如何更好

地运用所学的知识，和别人合作完成一个大的编程。

学校组织我们进行课程设计的用意也是希望我们能够把在

C

语言课程中学到

的理论知识同实践结合起来，

复合地利用所学知识丰富 自己的涵养，

提高自己的

水平。

只有把所学的理论知识与 实践相结合起来，

从而提高自己的实际动手能力

和独立思考的能力。

在设计的过程中难免会遇到过各种各样的问题，

同时在设计

的 过程中发现了自己的不足之处，

对以前所学过的知识理解得不够深刻，

掌握得

不够牢固，在这次课程设计之后，我一定会完善自己的不足之处。

6

、设计日志及参考文献

6.1

设计日志

六月十五号

--

六月十六号

我们拿到题目，进行了分组。

六月十七号

--

六月十八号

将老师所给题目资料、部分程序代码进行整理

和汇总，题目英文部分进行翻译， 打印成册，组员每人一份。初步了解设计的要

求、目的、所需知识内容，将设计分为三个 部分，分配人员负责。

六月十九号

--

六月二十号

进一步了解设计，发现问题，重新部署。

六月二十一号

--

六月二十三号

查阅资料，

结合老师已给程序，

弄清每部分

程 序的职能，完成大概的程序填充。

六月二十四号

--

六月二十五号

请教高水平同学，完善粗糙的程序。

六月二十六号

进行程序的调试运行，纠错。

六月二十七号

撰写程序设计报告，编写设计心得等。

六月二十八号

完善设计报告和准备答辩

6.2

参考文献

《

< p>c

语言程序设计（第二版）

》

《数据压缩基本原理》

霍夫曼代码

–

维基百科，自由的百科全书

哈夫曼代码

–

百度百科

12

常州大学课程设计

附录：程序源代码

第一部分：霍夫曼解码器的实现

#include

#include

#include

#define MAX_SYMBOLS 255

#define MAX_LEN

10

struct tnode

{

struct

tnode* left; /*used when in tree*/

struct

tnode*right; /*used when in tree*/

int

isleaf;

char

symbol;

};

struct code

{

};

/*global variables*/

struct tnode* root=NULL; /*tree of symbols*/

/*

@function

talloc

@desc

allocates new node

*/

struct tnode* talloc()

{

struct tnode* p=(struct tnode*)malloc(sizeof(struct tnode));

if(p!=NULL)

{

p->left=p->right=NULL;

p->symbol=0;

13

int

symbol;

char strcode[MAX_LEN];