序号:

学号: 12453118

课 程 设 计

设计课程名称： C语言课程设计

题 目： Data Compression

学 生 姓 名： 郭宏宇

学 院： 数理学院 专 业 班 级： 应数121

指 导 教 师： 王军 专业技术职务： 讲师

设计时间： 2013 年 6 月 17 日 2013 年 6 月 28 日

目录

1、引言及设计要求 3

1.1引言 3

1.2设计需求 3

1.2.1题目要求 3

1.2.2输出要求 3

2 、概要设计 3

2.1数据结构的描述 3

2.1.1数据类型的定义 3

2.1.2主要算法流程描述 4

2.2流程图 4

3、详细设计及实现 5

4、调试分析 5

5、总结及心得 11

5.1专题总结 11

5.2心得体会 11

6、设计日志及参考文献 12

6.1设计日志 12

6.2参考文献 12

附录：程序源代码 13

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

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

1、引言及设计要求

1.1引言

在多媒体计算机系统中，信息从单一媒体转到了多种媒体，要表示、传输和处理大量的声音、图像甚至影像视频信息，其数据量之大是非常惊人的。数字化多媒体信息的数据量是如此巨大，加之信息种类多、实时性要求高，给数据的存储、传输以及加工处理均带来了巨大的压力，不仅要求计算机有更高的数据处理和数据传输能力以及巨大的存储空间，而且也要求通信信道有更高的带宽。为了解决存储、处理和传输多媒体数据的问题，除了提高计算机本身的性能以及通信信道的带宽外，更重要的则是对多媒体数据进行有效的压缩。因此数据压缩编解码自然就成为了多媒体技术中最为关键的核心技术。

1.2设计需求

1.2.1题目要求

A:在每一次迭代过程中，我们需要跟踪的符号（或复合）的最低频率和第二频率最低的发生。这可以很容易地使用优先队列（一个链表，其中的元素总是插入正确的位置）。文件encode.c包含的模板代码（pq_insert()）的实现优先级队列。你需要填写缺少的部分。确保你照顾下列条件：（i）队列为空（ii）新的元素在开始前存储进去（iii）新元素存储在队列最后或中间。

B:符号的使用优先队列的pq_pop功能删除。在一个优先队列中，元素总是从一开始就删除。文件encode.c包含模板代码来实现这个。请填写所缺的部分。确保你的更新要被删除的元素的指针。

C:一旦代码树是建立在内存中，我们需要生成的每个符号的编码字符串。填入所缺的代码生成generate_code()。

D:最后填写缺失的代码来释放所有资源和内存,然后退出代码。

1.2.2输出要求

程序输出两个文件encoded.txt含有编码的输出和code.txt显示霍夫曼编码。

2 、概要设计

2.1数据结构的描述

2.1.1数据类型的定义

struct tnode

{

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

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

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

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

float freq;

int isleaf;

char symbol;

};

struct Symbol

{

char symbol;

float freq;

};

/*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*/

2.1.2主要算法流程描述

Main函数调用pq_insert函数频率初始化，调用pq_pop 、talloc 、pq_insert函数构建树，调用generate_code函数构建代码，调用dump_code函数输出代码，调用encode函数实现一个样品的字符串编码。

2.2流程图

3、详细设计及实现

分配新的代码：动态申请一块区域，用强制类型把它转换成结构体类型struct tnode的指针并赋给同类型的指针变量p，再将信息赋给申请的区域里。

在代码功能中显示tnodes的列表：调用struct tnode，输出字符和出现的频率。

插入一个元素到优先列表中：利用全局变量qhead，分不同的情况将元素插入到优先列表中。删除第一个元素：利用全局变量qhead，分两种情况删除元素。

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

输出代码文件：将code信息输出到文件（就是code.txt）。

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

4、调试分析

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

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

111101

110

! 10111001111

" 1011101

& 01101100111101001

' 111100101

( 10111001100111101

) 10111001100111100

, 011001

- 101110000

. 1111100

/ 011011001111010000

0 1011100110010

1 0110110011111

2 10111000101100

3 011011001111001

4 101110011001110

5 011011001111011

6 011011001111000

7 101110011001100

8 10111000101101

9 1011100110011111

: 11110011111011

; 111100111111

? 1111001001

A 1111001101

B 0110110100

C 10111001101

D 01101100011

E 01101100110

F 111100111101

G 101110011000

H 101110010

I 0110001

J 011011001110

K 1011100010111

L 10111000100

M 1111001000

N 10111000110

O 10111000111

P 111100111100

Q 101110011001101

R 01101100010

S 1111001110

T 011011011

U 11110011111010

V 1111001111100

W 1111001100

X 0110110011110101

Y 0110110010

Z 011011001111010001

a 1000

b 1111000

c 101111

d 10110

e 001

f 100110

g 011010

h 0100

i 0000

j 10111001110

k 0110000

l 10010

m 111001

n 0101

o 0111

p 1111101

q 0110110000

r 11101

s 0001

t 1010

u 111111

v 0110111

w 111000

x 0110110101

y 100111

z 101110001010

5、总结及心得

5.1专题总结

在本专题的课程设计中运用了C语言的知识设计了数据压缩，我们利用C语言的知识设计了可以对数据进行压缩的系统，在系统中我们了解到了霍夫曼编码（Huffman Coding是一种编码方式，是一种用于无损数据压缩的权编码算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于A Method for the Construction of Minimum-Redundancy Codes一文）。数据压缩包含的内容很多，我做的这个程序调用的函数也比较多。程序包含7个调用函数和一个主函数，主函数分别调用这几个不同功能的函数。分别为：分配新的代码，在代码功能中显示tnodes的列表，插入一个元素到优先列表中，删除第一个元素，生成的字符串的代码树，输出代码文件，输出压缩流。总结：获取a，b，c...的频率；根据频率做霍夫曼二叉树；根据二叉树获得a，b，c...的编码；编码到文件中

在设计中我们利用使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。系统不完善，应进一步设计与细化。

5.2心得体会

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

这次是我第一次参加课程设计，因此刚完成分组拿到课题是还是很紧张的。由于五人联合完成一个课题，需要较好地处理分步完成和协调好组内同学的配合。在这一方面，数据压缩课题是不同于其他课题的。所以在此次课程设计中，对于我们各位来说团队精神都得到了很大提升。在设计的过程中，除了组内同学的配合之外，我们还得到了其他同学的答疑和帮助，在此也一并感谢。

开始时，看了数据压缩的英文版解释，大致了解了这个程序分为三个部分，第一部分：霍夫曼解码器的实现：第二部分：实现霍夫曼编码器；第三部分：压缩大文件。第一部分相对其它两个部分简单点，第二部分应该是其中最难的了。而且，对于第二部分所涉及的C语言知识，我也是没有想到的，因为之前对于链表、递归我还是不了解的，我也通过这次C语言课程设计把落下的知识补上来了。也许我做的还不是很好，但是，通过这次课程设计我学会了在C语言编程中如何更好地运用所学的知识，和别人合作完成一个大的编程。

学校组织我们进行课程设计的用意也是希望我们能够把在C语言课程中学到的理论知识同实践结合起来，复合地利用所学知识丰富自己的涵养，提高自己的水平。只有把所学的理论知识与实践相结合起来，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，在这次课程设计之后，我一定会完善自己的不足之处。

6、设计日志及参考文献

6.1设计日志

六月十五号--六月十六号 我们拿到题目，进行了分组。

六月十七号--六月十八号 将老师所给题目资料、部分程序代码进行整理和汇总，题目英文部分进行翻译，打印成册，组员每人一份。初步了解设计的要求、目的、所需知识内容，将设计分为三个部分，分配人员负责。

六月十九号--六月二十号 进一步了解设计，发现问题，重新部署。

六月二十一号--六月二十三号 查阅资料，结合老师已给程序，弄清每部分程序的职能，完成大概的程序填充。

六月二十四号--六月二十五号 请教高水平同学，完善粗糙的程序。

六月二十六号 进行程序的调试运行，纠错。

六月二十七号 撰写程序设计报告，编写设计心得等。

六月二十八号 完善设计报告和准备答辩

6.2参考文献

《c语言程序设计（第二版）》

《数据压缩基本原理》

霍夫曼代码 – 维基百科，自由的百科全书

哈夫曼代码 – 百度百科

附录：程序源代码

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

#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

{

int symbol;

char strcode[MAX_LEN];

};

/*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;

p->isleaf=0;

}

return p;

}

/*

@function build_tree

@desc builds the symbol tree given the list of symbols and code.h

NOTE: alters the global variable root that has already been allocated in main

*/

void build_tree(FILE* fp)

{

char symbol;

char strcode[MAX_LEN];

int items_read;

int i,len;

struct tnode* curr=NULL;

while(!feof(fp))

{

items_read=fscanf(fp,"%c %s\n",&symbol,strcode);

if(items_read!=2) break;

curr=root;

len=strlen(strcode);

for(i=0;i

{

/*TODO: create the tree as you go*/

if(strcode[i]=='0')

{

if(curr->left)

{

curr = curr->left;

}

else

{

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

curr->left = p;

p->left = 0;

p->right = 0;

p->symbol = 0;

p->isleaf =0;

curr = p;

}

}

else

{

if(curr->right)

{

curr = curr->right;

}

else

{

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

curr->right = p;

p->left = 0;

p->right = 0;

p->symbol = 0;

p->isleaf =0;

curr = p;

}

}

}

/*assign code*/

curr->isleaf=1;

curr->symbol=symbol;

printf("inserted symbol:%c，%s\n",symbol,strcode);

}

}

/*

function decode

*/

void decode(FILE* fin,FILE* fout)

{

char c;

struct tnode* curr=root;

while((c=getc(fin))!=EOF)

{

/*TODO:

traverse the tree

print the symbols only if you encounter a leaf node

*/

if(curr->isleaf == 0)

{

if(c == '1')

{

curr = curr->right;

if(curr->isleaf)

{

putc(curr->symbol,fout);

curr = root;

}

}

else

{

curr = curr->left;

if(curr->isleaf)

{

putc(curr->symbol,fout);

curr = root;

}

}

}

}

curr = NULL;

free(curr);

}

/*

@function freetree

@desc cleans up resources for tree

*/

void freetree(struct tnode* root)

{

if(root==NULL)

return;

freetree(root->right);

freetree(root->left);

free(root);

}

int main()

{

const char* IN_FILE="encoded.txt";

const char* CODE_FILE="code.txt";

const char* OUT_FILE="decoded.txt";

FILE* fout;

FILE* fin;

/*allocate root*/

root=talloc();

fin=fopen(CODE_FILE,"r");

/*build tree*/

build_tree(fin);

fclose(fin);

/*decode*/

fin=fopen(IN_FILE,"r");

fout=fopen(OUT_FILE,"w");

decode(fin,fout);

fclose(fin);

fclose(fout);

/*cleanup*/

freetree(root);

getchar();

return 0;

}

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

#include

#include

#include

#include

#include

#define MAX_SYMBOLS 128

#define MAX_LEN 20

struct tnode

{

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

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

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

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

float freq;

int isleaf;

char symbol;

};

struct Symbol

{

char symbol;

float freq;

};

/*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*/

/*

@function talloc

@desc allocates new node

*/

struct tnode* talloc(int symbol,float freq)

{

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

if(p!=NULL)

{

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

p->symbol=symbol;

p->freq=freq;

p->isleaf=1;

}

return p;

}

/*

@function display_tnode_list

@desc displays the list of tnodes during code construction

*/

void pq_display(struct tnode* head)

{

struct tnode* p=NULL;

printf("list:");

for(p=head;p!=NULL;p=p->next)

{

printf("(%c,%f) ",p->symbol,p->freq);

}

printf("\n");

}

/*

@function pq_insert

@desc inserts an element into the priority queue

NOTE: makes use of global variable qhead

*/

void pq_insert(struct tnode* p)

{

struct tnode* curr=NULL;

struct tnode* prev=NULL;

printf("inserting:%c,%f\n",p->symbol,p->freq);

if(qhead==NULL) /*qhead is null*/

{

/*TODO: write code to insert when queue is empty*/

qhead = p;

}

/*TODO: write code to find correct position to insert*/

else

{

curr = prev = qhead;

if(qhead->next == NULL || (p->freq <= qhead->freq))

{

curr = qhead;

}

else

{

do

{

prev = curr;

curr = prev->next;

if((curr == NULL)||((prev->freq <= p->freq)&&(curr->freq >= p->freq)))

break;

}while(1);

}

if(curr==qhead)

{

/*TODO: write code to insert before the current start*/

if(p->freq <= curr->freq)

{

qhead = p;

qhead->next = curr;

}

else

{

qhead->next = p;

p->next = NULL;

}

}

else /*insert between prev and next*/

{

/*TODO: write code to insert in between*/

prev->next = p;

p->next = curr;

}

}

}

/*

@function pq_pop

@desc removes the first element

NOTE: makes use of global variable qhead

*/

struct tnode* pq_pop()

{

struct tnode* p=NULL;

/*TODO: write code to remove front of the queue*/

if(qhead->next!= NULL)

{

p = qhead;

qhead = qhead->next;

printf("popped:%c,%f\n",p->symbol,p->freq);

return p;

}

else

{

printf("popped:%c,%f\n",qhead->symbol,qhead->freq);

return qhead;

}

}

/*

@function build_code

@desc generates the string codes given the tree

NOTE: makes use of the global variable root

*/

char a[MAX_LEN]="";

void generate_code(struct tnode* root,char * a,int depth)

{

static int symbol;

static int len; /*length of code编码长度*/

if(root == NULL) return;

if(root->isleaf)

{

symbol=root->symbol;

len =depth;

/*start backwards开始向后*/

a[len]=0;

code[symbol][len]=0;

/*

TODO: follow parent pointer to the top

to generate the code string跟随父顶指针生成代码字符串

*/

printf("built code:%c,%s\n",symbol,a);

strcpy(code[symbol],a);

}

else

{

a[depth] = '0';

generate_code(root->left,a,depth+1);

a[depth] = '1';

generate_code(root->right,a,depth+1);

}

}

/*

@func dump_code

@desc output code file

*/

void dump_code(FILE* fp)

{

int i=0;

for(i=0;i

{

if(code[i][0]) /*non empty*/

{

if(i != 32)

fprintf(fp,"%c %s\n",i,code[i]);

else

fprintf(fp,"%c %s\n",'_',code[i]);

}

}

}

/*

@func encode

@desc outputs compressed stream

*/

void encode(char* str,FILE* fout)

{

while(*str)

{

fprintf(fout,"%s",code[*str]);

str++;

}

}

/*

@function main

*/

int main()

{

struct tnode* p=NULL;

struct tnode* lc,*rc;

FILE* fout=NULL;

FILE* fin=NULL;

const char* IN_FILE="..\\book.txt";

const char *CODE_FILE="..\\code.txt";

const char *OUT_FILE="..\\encoded.txt";

struct Symbol frequence[MAX_SYMBOLS];

struct Symbol sort_temp;

int i = 0, j = 0;

char ch;

char cha[2]="";

int char_num=0;

double sizein=0,sizeout=0;

memset(frequence,0,sizeof(frequence));

fin=fopen(IN_FILE,"r");

for(i=0;i

{

frequence[i].freq = 0;

frequence[i].symbol = i;

}

while ((ch = getc(fin))!=EOF)

{

frequence[ch].freq ++;

}

for(i=0;i

for(j=i;j

if(frequence[j].freq

{

sort_temp = frequence[j];

frequence[j] = frequence[i];

frequence[i] = sort_temp;

}

for(i=0;i

{

if(frequence[i].freq==0)

char_num ++;

}

// char_num = 128;

qhead=NULL;

/*initialize with freq*/

for(i=char_num;i

{

pq_insert(talloc(frequence[i].symbol,frequence[i].freq));

}

/*build tree*/

for(i=0;i

{

lc=pq_pop();

rc=pq_pop();

/*create parent*/

p=talloc(0,lc->freq+rc->freq);

/*set parent link*/

lc->parent=rc->parent=p;

/*set child link*/

p->right=rc; p->left=lc;

/*make it non-leaf*/

p->isleaf=0;

/*add the new node to the queue*/

pq_insert(p);

}

/*get root获得根*/

root=pq_pop();

root=root->next;

/*build code构建代码*/

// generate_code(root,0);

generate_code(root,a,0);

/*output code输出代码*/

puts("code:");

fout=fopen(CODE_FILE,"w");

dump_code(stdout);

dump_code(fout);

fclose(fout);

rewind(fin);/*使文件位置指针重新返回到文件的开头*/

/*encode a sample string*/

puts(IN_FILE);

fout=fopen(OUT_FILE,"w");

while((ch=getc(fin))!=EOF)

{

cha[0] = ch;

encode(cha,fout);

}

fclose(fin);

fclose(fout);

/*TODO: clear resources*/

fin = fopen(IN_FILE,"r");

fout = fopen(OUT_FILE,"r");

while (getc(fin)!=EOF)/*EOF文件结束标志*/

{

sizein ++;

}

while (getc(fout)!=EOF)

{

sizeout ++;

}

printf("%lf",sizeout/(sizein*8));

system("pause");

return 0;

}

常州大学课程设计报告