目录

一：哈夫曼编码译码器 .................................................................................................... 2

1.需求分析 ................................................................................................................ 2

2.详细设计 ................................................................................................................ 2

2.1.哈夫曼树节点的数据类型定义为： ...................................................................... 2

2.2.所实现的功能函数如下 ........................................................................................ 2

2.3.流程图： ............................................................................................................. 3

3.调试分析 ................................................................................................................ 3

4.用户手册 ................................................................................................................ 3

5.测试结果 ................................................................................................................ 4

6.附录 ....................................................................................................................... 4

二. 多叉路口交通灯管理 ................................................................................................ 11

1.需求分析 .............................................................................................................. 11

2.详细设计 .............................................................................................................. 12

2.1 .数据结构 .......................................................................................................... 12

2.2.算法流程图........................................................................................................ 12

2.2.1建立邻接矩阵的流程图 ................................................................................... 12

2.2.2 交通灯颜色模块的流程图 ............................................................................... 12

2.3 相关函数 .......................................................................................................... 13

2.3.1输入图函数 void Create(Graph &G) .................................................................. 13

2.3.2 染色函数 void trycolor(int s,Graph G) .............................................................. 14

2.3.3 定位函数 int LocateVex(Graph G,char u) .......................................................... 14

2.3.4 主程序 int main() ........................................................................................... 15

3.调试分析 .............................................................................................................. 15

4.用户手册 .............................................................................................................. 15

5.测试结果 .............................................................................................................. 15

6.附录 ..................................................................................................................... 16

1 / 19

一：哈夫曼编码译码器

1.需求分析

。目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。在传送报文的时候，总是希望总长尽可能的短，这就要用到哈夫曼编码。

2.详细设计

2.1.哈夫曼树节点的数据类型定义为：

typedefstruct{ //赫夫曼树的结构体

charch; int weight; //权值 intparent,lchild,rchild; //父结点，左孩子与右孩子

}htnode,*hfmtree;

2.2.所实现的功能函数如下

1、void hfmcoding(hfmtree&HT,hfmcode&HC,int n)

初始化哈夫曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树。此函数块调用了Select（）函数。

2、void Select(hfmtree&HT,inta,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点

2、int main()

主函数： 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入）

对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。

3、Encoding 编码功能：对输入字符进行编码

4、Decoding 译码功能： 利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat 中。

Print()打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。

2 / 19

5、主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。 使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。

2.3.流程图：

3.调试分析

在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是若没有定义所引用的相关头文件，必定调试不通过；

在文件输入读取中要注意文件字符串的读取等操作。

4.用户手册

在VC++环境下，运行该程序。运行程序后，根据相应的选项完成操作

I.

II.

III. I.Init初始化哈夫曼树 E.Encoding编码 D.Decoding译码

IV. Q.Exit退出

按照相关操作可以进行哈夫曼编码与译码。相应操作保存在相应TXT文档中。

3 / 19

5.测试结果

I.Init初始化哈夫曼树

E.Encoding编码

D.Decoding译码 Q.Exit退出

6.附录

带注释的源程序

#include<iostream.h>

4 / 19

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<fstream.h>

typedefstruct{ //赫夫曼树的结构体

charch; int weight; //权值

intparent,lchild,rchild;

}htnode,*hfmtree;

typedef char **hfmcode;

void Select(hfmtree&HT,inta,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点

{

inti,j,x,y; for(j=1;j<=a;++j){ } if(HT[j].parent==0){ x=j; break; } for(i=j+1;i<=a;++i){ if(HT[i].weight<HT[x].weight&&HT[i].parent==0){ x=i; //选出最小的节点 } } for(j=1;j<=a;++j) { if(HT[j].parent==0&&x!=j) { y=j; } break; } for(i=j+1;i<=a;++i) { if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i) { } y=i; //选出次小的节点 } if(x>y){ } *p1=y; *p2=x; 5 / 19

else { } *p1=x; *p2=y;

}

void hfmcoding(hfmtree&HT,hfmcode&HC,int n) //构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC

{

inti,start,c,f,m,w;

int p1,p2;

char *cd,z;

if(n<=1){

return;

}

m=2*n-1;

HT=(hfmtree)malloc((m+1)*sizeof(htnode));

for(i=1;i<=n;++i) //初始化n个叶子结点

{

printf("请输入第%d字符信息和权值：",i);

scanf("%c%d",&z,&w);

while(getchar()!='\n')

{

continue;

}

HT[i].ch=z;

HT[i].weight=w;

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

}

for(;i<=m;++i) //初始化其余的结点

{

HT[i].ch='0';

HT[i].weight=0;

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

}

for(i=n+1;i<=m;++i) //建立赫夫曼树

{

Select(HT,i-1,&p1,&p2);

HT[p1].parent=i;HT[p2].parent=i;

6 / 19

}

} HT[i].lchild=p1;HT[i].rchild=p2; HT[i].weight=HT[p1].weight+HT[p2].weight; HC=(hfmcode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i) //给n个字符编码 { start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { if(HT[f].lchild==c) { } else { } cd[--start]='1'; cd[--start]='0'; } HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd);

int main(){

char code[100],h[100],hl[100];

intn,i,j,k,l; ifstreaminput_file; //文件输入输出流 ofstreamoutput_file; charchoice,str[100]; hfmtree HT; hfmcode HC; cout<<"\n";

cout<<" "<<"网络 1001 班 "<<" "<<"学号201013136021"<<" "<<"liquan\n";

while(choice!='Q'&&choice!='q') //当choice的值不为q且不为Q时循环

{

7 / 19

cout<<" "<<"*************************赫夫曼编码/译码器*************************\n";

cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exit\n";

cout<<"请输入您要操作的步骤：";

cin>>choice; if(choice=='I'||choice=='i') //初始化赫夫曼树 { } cout<<"请输入字符个数："; cin>>n; hfmcoding(HT,HC,n); for(i=1;i<=n;++i) { cout<<HT[i].ch<<":"<<HC[i]<<endl; } output_file.open("hfmTree.txt"); if(!output_file){ cout<<"can't oen file!"<<endl; return 1; } for(i=1;i<=n;i++) { output_file<<"("<<HT[i].ch<<HC[i]<<")"; } output_file.close(); cout<<"赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!"<<endl;

else if(choice=='E'||choice=='e') //进行编码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中

{

printf("请输入字符："); gets(str); output_file.open("ToBeTran.txt"); if(!output_file) { cout<<"can't oen file!"<<endl; return 1; } output_file<<str<<endl; output_file.close(); output_file.open("CodeFile.txt"); if(!output_file){ cout<<"can't oen file!"<<endl; return 1; 8 / 19

} } for(i=0;i<strlen(str);i++){ for(j=0;j<=n;++j) { if(HT[j].ch==str[i]) } output_file.close(); cout<<"\n"; cout<<"编码完毕，并且已经存入CodeFile.txt文件！\n"; input_file.open("CodeFile.txt"); //从CodeFile.txt中读入编码，输出在if(!input_file) { cout<<"can't oen file!"<<endl; } return 1; } { } output_file<<HC[j]; break; 终端 input_file>>code; cout<<"编码码值为："<<code<<endl; input_file.close();

else if(choice=='D'||choice=='d') //读入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.txt中

{ input_file.open("CodeFile.txt"); if(!input_file){ cout<<"can't oen file!"<<endl; return 1; } input_file>>h; input_file.close(); output_file.open("Textfile.txt"); if(!output_file) { } cout<<"can't oen file!"<<endl; return 1;

往后移

k=0; while(h[k]!='\0') //先用编码中的前几个和字符的编码相比较，然后9 / 19

{

for(i=1;i<=n;i++){

l=k;

for(j=0;j<strlen(HC[i]);j++,l++){

hl[j]=h[l];

}

hl[j]='\0';

if(strcmp(HC[i],hl)==0)

{

output_file<<HT[i].ch;

k=k+strlen(HC[i]);

break;

}

}

}

output_file.close();

input_file.open("Textfile.txt");

if(!input_file){

cout<<"can't oen file!"<<endl;

return 1;

}

input_file>>h;

cout<<h<<endl;

input_file.close();

cout<<"译码结束，字符已经存入Textfile.txt文件中！"<<endl; }

else if(choice=='Q'||choice=='q') //退出程序

{

exit(0);

}

else //如果选了选项之外的就让用户重新选择 {

cout<<"您没有输入正确的步骤，请重新输入！"<<endl; }

cout<<endl;

}

return 0;

}

10 / 19

二.多叉路口交通灯管理

1.需求分析

通常，在十字路口只需设红、绿两色的交通灯便可以保证正常的交通秩序，而在多叉路口需设计几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流量。该程序就是在多叉路口情况下，判断各个路口交通灯颜色，以便人们进行管理。对于用户任意输入的多叉路口（实际输入所有的可以通行的方向及数量，从而构建出图），输出需要的交通灯的数量。

假设有一个如图1所示的五叉路口，其中C和E为单行道。在路口有13条可行的道路，其中有的可以同时通行，如A—>B和E—>C，而有的不能同事通行，如E—>B，A—>D，那么，如何设置交通灯呢？

每个圆圈表示五叉路口上的一条通路，两个圆圈之间的连线表示这两个圆圈表示的两条道路不能同事通行。设置交通灯的问题等价为对图的顶点进行染色问题。要求对图上的每个顶点染一种颜色，并且要求有限相连的两个顶点不能具有相同颜色，而且总的颜色种类尽可能少。所以，我准备把每个顶点用字母“a、b、c、……”表示，而染色的颜色用数字表示。可以同时通行的道路交通灯的颜色相同，不能同时通行的颜色不同。顶点B为Aa，AC为b，AD为c，BA为d，BC为e，BD为f，DA为g，DB为h，DC为i，EA为j，EB为k，EC为l，ED

为

11 / 19

m，顶点之间的边全都用“1”表示。

2.详细设计

2.1.数据结构

首先，是考虑数据类型。在多叉路口中，每条通路是最基本的组成部分，对于交通灯管理已经不可能在细分了，所以选定通路作为数据的基本类型，并在程序中定义图的数据结构,其中包含存放图的顶点和图的边，以及顶点数和边数。用邻接矩阵表示图的结构。其形式描述如下：

int color[30]={0};//来存储对应块的对应颜色

typedef char vextype;

typedefintadjtype;

typedefstruct //定义图

{

vextypevexs[MAXedg]; //存放边的矩阵

adjtype arcs[MAXedg][MAXedg]; //图的邻接矩阵

intvnum,arcnum; //图的顶点数和边数

}Graph;

在选择数据结构方面，直接用数组来存储数据，即使是在内存中也用数组来处理数据间的联系。运用顺序表这个结构虽然不是那么直观，但在查找数据时的算法设计比较简单容易实现，效率高，而且在内存中的数据可以直接读入到文件中，文件中的数据也可以直接读入内存，不需要进行转换。所以在衡量的各个方面之后，我决定用数组来处理数据间的联系。

2.2.算法流程图

2.2.1建立邻接矩阵的流程图

2.2.2 交通灯颜色模块的流程图

12 / 19

2.3.1输入图函数void Create(Graph &G)

考虑到输入的问题，就是在输入界面以何种形式输入，输入顶点和边数以及边的权值在计算机内部建立数组存储。部分代码如下：

printf("输入多叉路口的顶点数和边数:\n");

scanf("%d%d",&G.vnum,&G.arcnum);

getchar();

printf("输入多叉路口的各顶点：\n");

for(i=1;i<=G.vnum;i++)

{

scanf("%c",&G.vexs[i]);

getchar();

13 / 19

}

printf("输入边的两个顶点和权值:\n");

for(k=0;k<G.arcnum;k++)

{

scanf("%c", &v1);getchar();

scanf("%c", &v2);getchar();

scanf("%d", &w); getchar();

i=LocateVex(G,v1);

j=LocateVex(G,v2);

G.arcs[i][j]=w;

G.arcs[j][i]=w;

}

2.3.2染色函数void trycolor(ints,Graph G)

给各个顶点染色，然后输出染色结果，并调用判断颜色是否满足要求函数。从第一个顶点开始染色，而后判断和其相邻的顶点的颜色是够与第一个顶点相同。部分代码如下： if(s>G.vnum)

{

output(G);

exit(1);

}

else

{

for(i=1;i<=N;i++)//对每一种色彩逐个测试

{

color[s]=i;

if(colorsame(s,G)==0)

trycolor(s+1,G);//进行下一块的着色

}

}

2.3.3定位函数intLocateVex(Graph G,char u)

在已经输入的图中，找到与要记录的顶点在图中的位置，返回值是在数组中的位置。部分代码如下：

for(i=1;i<=G.vnum;i++)

{

if(u==G.vexs[i])

return i;

}

if(i==G.vnum)

{

printf("Error u!\n");

exit(1);

14 / 19

}

return 0;

2.3.4主程序int main()

{

inti,j;

Graph G;

Create(G);

printf("多叉路口的各顶点：\n");

for(i=1;i<=G.vnum;i++)

printf("%c ",G.vexs[i]);

printf("\n");

printf("相应的亮灯方案:\n");

trycolor(1,G);

return 0;

}

3.调试分析 一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。TC里检查错误都是用英文来显示出来的，经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。此次的程序设计能够成功，是我和我的同学三个人共同努力作用的结果。在这一段努力学习的过程中，我们的编程设计有了明显的提高。

4.用户手册

在VC++环境下，运行该程序。根据提示输入多叉路口的顶点数和边数，例如五叉路口的情况，顶点5个，10条边，就输入5 10然后回车，根据提示输入顶点A B C D E 回车，根据提示输入两个顶点和权值A B 1 A C 2 ……回车，程序结果就出现在屏幕上了“亮灯方案： 1 1 1 1 1

5.测试结果

15 / 19

第一组：

第二组：

第三组：

当输入不符合规定时，程序发生意外停止.(程序的BUG)

6.附录

带注释的源程序

#include <stdio.h>

#include <stdlib.h>

#define MAXedg 30

#define MAX 0

#define N 4 //亮灯的颜色数

int color[30]={0};//来存储对应块的对应颜色

typedef char vextype;

typedefintadjtype;

typedefstruct //定义图

{

vextypevexs[MAXedg]; //存放边的矩阵

adjtype arcs[MAXedg][MAXedg]; //图的邻接矩阵 intvnum,arcnum; //图的顶点数和边数

16 / 19

}Graph;

intLocateVex(Graph G,char u)

{

int i;

for(i=1;i<=G.vnum;i++)

{

if(u==G.vexs[i])

return i;

}

if(i==G.vnum)

{

printf("Error u!\n");

exit(1);

}

return 0;

}

void Create(Graph &G) //输入图 {

inti,j,k,w;

vextype v1,v2;

printf("输入多叉路口的顶点数和边数:\n"); scanf("%d%d",&G.vnum,&G.arcnum); getchar();

printf("输入多叉路口的各顶点：\n"); for(i=1;i<=G.vnum;i++)

{

scanf("%c",&G.vexs[i]);

getchar();

}

printf("输入边的两个顶点和权值:\n"); for(k=0;k<G.arcnum;k++)

{

scanf("%c", &v1);getchar();

scanf("%c", &v2);getchar();

scanf("%d", &w); getchar();

i=LocateVex(G,v1);

j=LocateVex(G,v2);

G.arcs[i][j]=w;

G.arcs[j][i]=w;

}

17 / 19

}

intcolorsame(ints,Graph G)//判断这个颜色能不能满足要求 {

inti,flag=0;

for(i=1;i<=s-1;i++)//分别于前面已经着色的几块比较 if(G.arcs[i][s]==1&&color[i]==color[s])

{flag=1;break;}

return flag;

}

void output(Graph G)

{

int i;

for(i=1;i<=G.vnum;i++)

printf("%d ",color[i]);

printf("\n");

}

void trycolor(ints,Graph G)//s为开始图色的顶点，从1开始{

int i;

if(s>G.vnum)

{

output(G);

exit(1);

}

else

{

for(i=1;i<=N;i++)//对每一种色彩逐个测试 {

color[s]=i;

if(colorsame(s,G)==0)

trycolor(s+1,G);//进行下一块的着色

}

}

}

int main()

{

inti,j;

Graph G;

Create(G);

18 / 19

printf("多叉路口的各顶点：\n"); for(i=1;i<=G.vnum;i++)

printf("%c ",G.vexs[i]);

printf("\n");

printf("相应的亮灯方案:\n"); trycolor(1,G);

return 0;

}

19 / 19