数据结构研究论文 - 范文中心

数据结构研究论文

05/21

计算机数据结构研究论文

题目： 院系： 计算机科学与信息工程系 专业： 网 络 工 程 班级： （1）班 姓名： 侯 三 杰 学号： 日期：

Huffman 编码器与Joseph 约瑟夫环

.Huffman编码器

1. 问题描述：

给出一个霍夫曼树的节点，和每个节点的权值，设计一个算法，可以通过算法将每个节点译为不同的码字. 2. 需求分析

(1) 输入的形式和输入值的范围；

输入的值是通过用户界面提示, 输入名节点数和权值, 但是要求均是正整数. (2) 输出的形式:以表的形式输出, 左边为要译的权值, 右边为要译的码字，且是二进制码,

(3) 程序所能达到的功能；将已知有权值的数译成二进制编码，且码不重复，无前缀码。

(4) 测试数据: number:6,weight:2 2 3 4 5 6

输出：1-000 2-001 3-110 4-111 5-01 6-10

3. 概要设计

1. 抽象数据类型的定义为：

void CreateHuffmanTree(HuffmanTree *HT, unsigned int *w , int n) 输出结果:w存放n 个字符的权值(均>0),构造Huffman 树HT. void Select(HuffmanTree HT, int t, int *s1, int *s2)

输出结果:在Huffman 树HT 中找出权值最小的两个节点，序号分别为s1和s2 void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n) 输出结果: 赫夫曼编码, 放入HC 中

void PrintHuffmanCode(HuffmanCode HC, unsigned int *w, int n) 输出结果: w存放n 个字符的权值(均>0),输出Huffman 编码

2. 本程序包含以下模块： （1）主程序模块： main(void) {

输入数据； 执行功能； 显示结果；

}

（2）各功能模块——实现Huffman 编码的各项功能。 各模块的调用关系：

4．详细设计：

/*编辑器devcpp*/

#include #include #include typedef struct {

unsigned int weight;/*放权值*/ unsigned int parent;/*父亲结点*/ unsigned int lchild;/*左孩子*/ unsigned int rchild;/*右孩子*/

}HTNode, *HuffmanTree; /*动态申请赫夫曼树*/ typedef char **HuffmanCode;/*动态分配赫夫曼表*/

void CreateHuffmanTree(HuffmanTree *HT, unsigned int *w , int n); void Select(HuffmanTree HT, int t, int *s1, int *s2);

void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n); void PrintHuffmanCode(HuffmanCode HC, unsigned int *w, int n); main(void) {

HuffmanTree HT; HuffmanCode HC; int i, n;

unsigned int *w;

printf("*********Huffman********\n\n") ; printf("input number of Huffman:\n"); scanf("%d", &n); if(n

w = (unsigned int *)malloc(n * sizeof(unsigned int)); printf("input weight:\n");/*输入每个叶子节点的权值*/ for(i = 0; i

scanf("%d", &w[i]); }

CreateHuffmanTree(&HT, w, n); HuffmanCoding(HT, &HC, n);

PrintHuffmanCode(HC, w, n); getch(); }

/*****************************

建立赫夫曼树,w 存放权值, 在每次把两个小的权值相加后, 在每次select 中都能包括进去新的结点每次父亲结点被重新赋值, 不为0在每次select 中除去 *****************************/

void CreateHuffmanTree(HuffmanTree *HT, unsigned int *w , int n) {

int i, m; int s1, s2; char *cd;

m = 2 * n - 1; /*总结点数*

*HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); for(i = 1; i

(*HT)[i].weight = *w; (*HT)[i].parent = 0; (*HT)[i].lchild = 0; (*HT)[i].rchild = 0; }

for(; i

(*HT)[i].weight = 0; (*HT)[i].parent = 0; (*HT)[i].lchild = 0; (*HT)[i].rchild = 0; }

for(i = n + 1; i

Select(*HT, i - 1, &s1, &s2);/*从权值中选两个最小的*/

(*HT)[s1].parent = i; /*父亲结点都被赋值, 在select 循环中可以除去*/ (*HT)[s2].parent = i;

(*HT)[i].lchild = s1; /*孩子结点被赋值*/ (*HT)[i].rchild = s2;

(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;/*加后成新结点*/ } }

/*寻找两个最小的结点s1, s2*/

void Select(HuffmanTree HT,int t,int *m1,int *m2) { int i,max; int s1,s2;

for(i=1;i

if(max

s1=s2=max;

for(i=1;i

s1=HT[i].weight; *m1=i; }

else if(HT[i].weight

void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n) /*赫夫曼编码, 放入HC 中*/ {

int i, start, c, f; char *cd;

(*HC) = (HuffmanCode )malloc((n + 1) * sizeof(char *)); cd = (char *)malloc(n * sizeof(char));/*编码的空间*/ cd[n - 1] = '\0'; /*编码结束符号*/

for(i = 1; i

start = n - 1; /*结束位置*/

for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) {

/*从叶子到根求编码*/ if(HT[f].lchild == c) {

cd[--start] = '0'; } else {

cd[--start] = '1'; } }

/*为第i 个叶子结点求空间*/

(*HC)[i] = (char *)malloc((n - start) * sizeof(char)); strcpy((*HC)[i], &cd[start]); /*从cd 复制到HC*/

} }

void PrintHuffmanCode(HuffmanCode HC, unsigned int *w, int n) /*打印编码*/ {

int i;

printf("\n*********Huffman********\n\n") ; printf("the HuffmanCode is:\n \n"); for(i = 1; i

printf("%3d---", w[i - 1]); /*先打印权值*/ printf("%s",HC[i]); /*打印表*/ printf("\n"); } }

6．用户使用说明

1,输入总叶子节点数, 也就是需要编码的个数.

2,输入每个叶子节点所带的权值, 需要根据权值计算并生成霍夫曼编码.

7．测试结果

1． 输入结果:

2． 输出结果

:

.Joseph约瑟夫环

1. 问题描述：编号为1、2、……、n 的n 个孩子围坐一 圈，任选一个数m ， 从第一个

孩子开始数，数到m 停止，这个孩子离开，再从第一个开始数，直到剩下一个孩子。最最后剩下的孩子就是赢家。

2. 需求分析

(1) 输入的形式和输入值的范围:输入值为整数, 且任选一个位置的数要小于孩子数。 (2) 输出的形式: 从屏幕显示游戏过程排列，出来的孩子顺序，和最后的赢家。

(3)程序所能达到的功能:提供用户从键盘输入，Joseph 约瑟夫环的必要数据，

并显示获胜者号。

(4) 测试数据：正确的数据如下图显示，错误的数据时，number:1,began:2,count:1,2,1

结果：bad begin position

bad interval number

2. 概要设计

1，函数说明：

int assign(); 功能：赋初值，返回1：成功，0：失败 void initial(Jose* pBoys); 功能：初始化环链表 void count(int m); 功能 ：数m 个小孩

void process(); 功能：处理所有未获胜小孩

2. 本程序包含以下模块： （1）主程序模块： main(void) {

输入数据； 执行功能； 显示结果； }

（2）各功能模块——实现Joseph 编码的各项功能。 各模块的调用关系：

4．详细设计：

#include #include

struct Jose{ //小孩结构

int code; //存放小孩编号

Jose* next; //用于指向下一个小孩结点 };

//全局变量

int n; //小孩数 int begin; //开始位置 int m; //数小孩间隔 Jose* pivot; //链表哨兵

Jose* pCur; //当前结点指针 //函数声明

int assign(); //赋初值，返回1：成功，0：失败 void initial(Jose* pBoys); //初始化环链表 void count(int m); //数m 个小孩

void process(); //处理所有未获胜小孩

//主函数 void main() {

if(!assign()){

cout

Jose* pJose=new Jose[n]; //分配结构数组 initial(pJose); //初始化结构数组 count(begin); //转到开始位置 process(); //处理所有未获胜小孩

cout code

delete[]pJose; //返还结构数组给堆空间 }

//赋初值 int assign() {

int number,start,count;

cout

cout >number;

cout >start;

cout >count;

if(number

if(start

if(countnumber){//数小孩个数校验 cerr

n=number; begin=start; m=count; //赋全局变量值 return 1; }

//链表初始化

void initial(Jose* pJose) {

int l=0;

Jose* px=pJose;

coutnext=pJose+i%n; px->code=i; px=px->next;

if((l++%10)==0) //输出行中个数控制 cout

cout

pCur=pJose+n-1; //指向结构数组最后一个元素 }

//数m 个小孩 void count(int m) {

for(int i=0; i

pivot=pCur;

pCur=pivot->next; } }

//处理获胜者决出之前的所有小孩 void process() {

int l=0;

for(int i=1; i

count(m); //数m 个小孩

if((l++%10)==0) //输出行中个数控制 cout

cout code;

pivot->next=pCur->next; //小孩脱链 pCur=pivot; } }

5，用户使用说明

1；输入要参加游戏的孩子数 2；输入要成为开始点的孩子位置 3；输入每次被数的孩子间隔数

注意：不要把位置数大于孩子数，和定义间隔的数超过孩子数，如，孩子数是3，间隔数为2，2，2，2； 6，测试结果

输入结果：

输出结果：

调试分析

1. Huffman编码器

1， 过程的调试：编码是默认为二元编码，建立赫夫曼树,w 存放权值, 在每次把两个小的权值相加后, 在每次select 中都能包括进去新的结点每次父亲结点被重新赋值, 不为0在每次select 中除去。存在的问题，设计的不够详细，只能简单实现编码，无法真正做到全面细致的编码过程，还有一些C 语言语法和结构体调用的问题，已在编码时解决。

1.2， 时间复杂度为：n, 因为都只是单循环

1.3，好的设想：定义需要调用的几个函数，需要输入信源数，来选择需要编码的范围，还要建立一个函数用来判断需要编码的个数，并选择需要压缩的次数，需要虚码0来补数M 个，通过来计算M ，如果M

2. Joseph约瑟夫环

2.1.调试过程：在调试过程中，遇到的问题就是当输入的开始位置数和间隔的总数大于孩子数的时候，就不会输出，会跳出来。这个问题可以用一个IF 句，提到，显示bad number of boys ；bad begin position；bad interval number来提示用户，还有一个问题，当输出完毕后会直接跳出，如果还想输入需要重新运行，可以加一个循环给主函数，来实现重复输入输出的功能。最后一个问题是，胜利者前面的出去的小孩没有输出。

2.2，时间复杂度为：n, 因为都只是单循环

2.3，好的设想：算法更精简些，输出的更详细些，这个算法基本比较完善了。 ．心得体会：

通过这次课程设计，发现了代码的知识是对我很大的历练，不论开始的结构体定义还是后面的指针，都是需要很强的逻辑能力。首先，编码之前，要画流程图，不能急于编码，要先把这方面的知识理清，把逻辑上的循环的指针指向也理清，其次是编码，怎样应用简单明了的方法把代码编出，怎么以一个程序员的角度为用户着想，让他们更明白的应用我们的程序，还有编程序时候的格式和排版也很重要，一个清晰明了的排版，无论是他人检查，浏览，还是自己改错都是很方便的。还有就是调试的过程中，出现的很多错误，没有人是天生不犯错的，我们只能避免少犯错，但不要因为犯错而气馁，而 急躁，一个好的程序，不仅讲求的是效率，更讲求的是质量。

.参考文献

1. 信息论与编码理论 沈世镒 陈鲁生编写 科学出版社出版发行

2. 数据结构C 语言版 严蔚敏 清华大学出版社


相关内容

  • 专题研究类论文
    专题研究类论文 本文件阐述MBA.MPA.MPACC专业学位论文撰写要求,在总结以往论 文工作经验的基础上,提出撰写过程中应注意的要点,旨在帮助研究生提高论文 工作效率和质量.MBA毕业论文都是在教师指导下进行的,每一篇论文的质量是 否符合 ...
  • 毕业论文管理系统的数据库设计
    3.4 数据库设计与实施 3.4.1数据库需求分析 用户的需求具体体现在各种信息的提供.保存.更新和查询方面,这就要求数据库结构能充分满足各种信息的输入和输出.收集基本数据,数据结构以及数据处理的流程,组成一份详尽的数据库.针对本学院的毕业 ...
  • 结构生物学
    题目二 结构生物学 xxx (2011级生物科学基地班 学号:xxxxxxxxx) 摘要:本文主要从结构生物学的本质.研究领域.发展历程.面临困境以及突破的办法.个人认识等方面简要介绍笔者对于结构生物学的看法. 关键词:结构生物学 困难 发 ...
  • 药品文献评价指导原则_百替生物
    药品文献评价指导原则 国家食品药品监督管理局药品评价中心 (征求意见稿2009.1) 一.前言 开展药品上市后研究对于准确掌握药品信息,正确评价药品的安全性和有效性,指导临床合理用药具有极其重要意义.文献评价是药品上市后研究的主要方法之一, ...
  • 支持精准医疗的国外临床决策支持系统
    DOI:10．3969/j．issn．1671-3982．2016．02．004 ・研究与探讨・ 支持精准医疗的国外临床决策支持系统 杨春华,王天津,黄思敏,刘 娜,王 颖 ［摘要］实现大数据基础上的精准医学目标,需要可靠的证据支持.信息技 ...
  • 济宁市早教市场调查报告
    济宁市幼儿教育市场前景及投资机会研究报告 2017-2022年 中商产业研究院 ASKCI Consulting CO.,LTD 中商产业研究院简介 中商产业研究院是深圳中商情大数据股份有限公司下辖的研究机构,是国内领先的产业研究咨询服务机 ...
  • 江苏省药店市场调查报告
    江苏省药店市场前景及投资机会研究报告 2017-2022年 中商产业研究院 ASKCI Consulting CO.,LTD 中商产业研究院简介 中商产业研究院是深圳中商情大数据股份有限公司下辖的研究机构,是国内领先的产业研究咨询服务机构, ...
  • 牡丹江市SPA市场调查报告
    牡丹江市SPA市场前景及投资机会研究报告 2017-2022年 中商产业研究院 ASKCI Consulting CO.,LTD 中商产业研究院简介 中商产业研究院是深圳中商情大数据股份有限公司下辖的研究机构,是国内领先的产业研究咨询服务机 ...
  • 毕节市汽车美容市场调查报告
    毕节市汽车美容市场前景及投资机会研究报告 2017-2022年 中商产业研究院 ASKCI Consulting CO.,LTD 中商产业研究院简介 中商产业研究院是深圳中商情大数据股份有限公司下辖的研究机构,是国内领先的产业研究咨询服务机 ...
  • 江苏省自助餐餐厅市场调查报告
    江苏省自助餐餐厅市场前景及投资机会研究报告 2017-2022年 中商产业研究院 ASKCI Consulting CO.,LTD 中商产业研究院简介 中商产业研究院是深圳中商情大数据股份有限公司下辖的研究机构,是国内领先的产业研究咨询服务 ...

热门内容