数据结构实验报告

编号：

江西理工大学

数据结构课程设计报告

班 级：

学 号： 姓 名：

时 间：

指导教师：

目 录

第一章 需求分析 .......................................... 1

1.1实验内容概述 ...................................... 1 1.2实验目的概述 ...................................... 1

第二章 概要设计 ...................................... 2

2.1抽象数据类型定义 .................................. 2 2.2程序流程图 ........................................ 2 2.3链表分析 .......................................... 4

第三章 详细设计 ...................................... 5

3.1定义关键步骤 ...................................... 5 3.2定义关键函数 ...................................... 6 3.3主函数 ............................................ 9

第四章 调试分析 ..................................... 10

4.1问题讨论 ......................................... 10 4.2经验与体会 ....................................... 12 4.3测试结果 ......................................... 12

第五章 总结分析 ..................................... 13 第六章 参考文献 ..................................... 14 附录 源程序 ................................................................................ 14

第一章 需求分析

1.1实验内容概述

 纸牌游戏

编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？要求：用数组、链表结构实现，采用递归方法。

 哈夫曼编码

设计出下面字符表的哈夫曼编码对应的二叉树,并输出每个字符的哈夫曼编码。 字符 m n 44 o 12 p 17 q 9 r 5 出现频率（%） 13

1.2实验目的概述

 纸牌游戏

①了解线性表的特性，以及它们在实际问题中的应用。 ①掌握顺序表和链表的实现方法，以及它们的基本操作。

①掌握线性表的链式存储结构——单链表的定义及其C语言实现。 ①掌握线性表在链式存储结构——单链表中的各种基本操作。 ①通过用链表编程实现问题的解决，提高自身的问题解决能力。

 哈夫曼编码

以字符的频度为权值，建立哈夫曼树，求哈夫曼编码。根据字符及权值得到其相应的编码。

第 1 页

第二章 概要设计

2.1抽象数据类型定义

 纸牌游戏

struct node //定义结点 { int data;

int key; //定义标志位 struct node *next; }

 哈夫曼编码

typedef struct

{int weight; /*结点的权值*/

int lchild,rchild,parent; /*左、右孩子及双亲的下标*/ }htnode;

typedef htnode huffmantree[m+1]; /* huffmantree是结构数组类型,其0号单

元不用，存储哈夫曼树 */

typedef struct

{char ch; /*存储字符*/ char code[n+1]; /*存放编码位串*/ }codenode;

typedef codenode huffmancode[n+1]; /*huffmancode是结构数组类型,其0号单

元不用,存储哈夫曼编码*/

2.2程序流程图

 纸牌游戏

第 2 页

开始 建立一个线性表L，将所有变量赋初值为0，表示牌正面向上 i>=2&&i<=52 j>=i&&j<=5222 j%i=0 翻牌，如果L.data[j]=1,则变为0 翻牌，如果L.data[j]=0,则变为1 j++ 输出线性表中正面向上的牌的编号 结束

第 3 页

 哈夫曼编码

2.3链表分析

①初始化头结点正面朝上

①初始化所有牌正面朝上 p 第 4 页

p

①循环完后递归

. . . . . . s

. . . . . . 第三章 详细设计

3.1定义关键步骤

 纸牌游戏

struct node *create() //定义链表建立函数create()

{ struct node *p,*head,*s; //其返回值为结构指针 int i;

head=NULL; //初始化头指针

p=(struct node*)malloc(sizeof(*p)); //生成P结点 if(p==NULL)

{ printf(\"Memory is too small!\\n\"); }

head=p;

head->data=1; head->key=1;

head->next=NULL;

第 5 页

. . . . . .

for(i=2;i<=52;i++) //建立结点的链表 { s=(struct node*)malloc(sizeof(*p)); s->data=i;

s->key=1; // 初始化所有牌都是正面朝上 p->next=s; p=s; }

p->next=NULL; return(head); }

 哈夫曼编码 #include

#include // 用到系统标准输出函数的 #include

#include //用到像getch()这种键盘输入函数 #define n 6 /*叶子数目根据需要设定*/ #define m 2*n-1 /* Huffman 树中结点总数 */

3.2定义关键函数

 纸牌游戏

void fanpai(struct node *p) //翻牌算法 { struct node *p1,*p2; p1 = p; if(p1!=NULL){

fanpai(p1->next); /*递归，一直调用p1但不执行，直到p1=52，然后p2从52开始、51开始、50开始......*/

} //先执行外循环，直到p1->next=null,在执行内循环，即翻牌 for(p2=p1;p2!=NULL;p2=p2->next) //p1从2开始固定，然后p2一直往后走 {

if(p2->data%p1->data==0) //是p1的倍数则翻牌 {

if(p2->key==0) p2->key=1; else

p2->key=0;

第 6 页

} } }

 哈夫曼编码 1) 初始化函数：

void inithuffmantree(huffmantree ht) {int i;

for(i=0;i<=m;i++) {ht[i].weight=0;

ht[i].lchild=ht[i].rchild=ht[i].parent=0; } }

2) 输入权值函数：

void inputweight(huffmantree ht) {int i;

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

printf(\" ……请输入第[%d]个权值: \

scanf(\"%d\

} printf(\"\\n\");

}

3) 选权值最小序号函数：

void selectmin(huffmantree ht, int i, int *p1, int *p2)

{int j,min1,min2; /* min1,min2分别是最小权值和次小权值*/ min1=min2=32767; *p1=*p2=0; for(j=1;j<=i;j++)

{if(ht[j].parent==0) /* j 为根结点*/

第 7 页

if(ht[j].weightif(min1!=32767) {min2=min1; *p2=*p1;} min1=ht[j].weight; *p1=j; } else

if(ht[j].weight4) 构造哈夫曼树函数

void createhuffmantree(huffmantree ht) {

int i,p1,p2;

inithuffmantree(ht); /* 将ht初始化*/

inputweight(ht); /* 输入叶子权值至ht [1..n]的weight域*/

for(i=n+1;i<=m;i++) /* 共进行n-1次合并，新结点依次存于ht[i]中*/

{selectmin(ht,i-1,&p1,&p2); /*在ht [1.. i-1]中选择两个权值最小的根结点，其序号分别为p1和p2*/ ht[p1].parent=ht[p2].parent=i;

ht[i].lchild=p1; /* 最小权值的根结点是新结点的左孩子*/

ht[i].rchild=p2; /* 次小权值的根结点是新结点的右孩子*/

ht[i].weight=ht[p1].weight+ht[p2].weight; } }

5) 编码函数

void huffmancodes(huffmantree ht,huffmancode hcd)

第 8 页

{

int c,p,i; /* c和p分别指示 ht中孩子和双亲的位置 */

char cd[n+1]; /* 临时存放编码*/

int start; /* 指示编码在cd 中的起始位置*/ cd[n]='\\0';

getchar(); /* 编码结束符*/ printf(\"2.……请依次输入字符……:\");

for(i=1;i<=n;i++) /* 依次求叶子ht [i]的编码*/ { hcd[i].ch=getchar(); /* 读入叶子ht [i]对应的字符*/ start=n; /* 编码起始位置的初值*/ c=i; /* 从叶子ht [i]开始上溯*/ while((p=ht[c].parent)!=0) /* 直至上溯到ht [ c]是树根为止*/ { cd[--start]=(ht[p].lchild==c)?'0':'1'; /*若ht [ c]是ht[p]的左孩子，则生成代码0，否则生成代码1*/

c=p; /* 继续上溯*/ }

strcpy(hcd[i].code,&cd[start]); /* 复制编码位串*/ } printf(\"\\n\");

printf(\"3.………哈夫曼编码结果为：……\\n\"); printf(\"\\n\"); for(i=1;i<=n;i++)

printf(\" ……第[%d]个符[%c]的编码为：%s\\n\ }

3.3主函数

 纸牌游戏 void main()

{ struct node *head,*np; head=create(); if(head==NULL) printf(\"链接错误！\\n\");

fanpai(head); //调用翻牌算法开始翻牌

第 9 页

printf(\"\\n 最后正面向上的牌有\");

for(np=head;np!=NULL;np=np->next) //输出翻牌完成后的结果 { if(np->key==0)

printf(\"%4d\->data); }

printf(\"\\n\"); }

 哈夫曼编码 void main() {huffmantree t; huffmancode h;

printf(\"|^^^^^^^^^^^^^^^^^^^^^^^^^^^*########################*^^^^^^^^^^^^^^^^^^^|\\n\");

printf(\"|^^^^^^^^^^^^^^^^^^^^^^^^^^^*欢迎使用哈弗曼编码系统！*^^^^^^^^^^^^^^^^^^^|\\n\");

printf(\"|^^^^^^^^^^^^^^^^^^^^^^^^^^^*########################*^^^^^^^^^^^^^^^^^^^|\\n\"); printf(\"\\n\");

printf(\"1.…………请输入%d个权值:……\\n\ printf(\"\\n\");

createhuffmantree(t); /* 构造huffman树*/ huffmancodes(t,h); /* 构造huffman编码*/ }

第四章 调试分析

4.1问题讨论

 纸牌游戏

之前的代码：

void fanpai(struct node *p)

第 10 页

{ struct node *p1,*p2;

for(p1=p->next;p1!=NULL;p1=p1->next) { for(p2=p1;p2!=NULL;p2=p2->next)

{ if(p2->data%p1->data==0) { if(p2->key=1; else p2->key=0; } } } }

由于没有用到递归，不满足实验要求，所以改为以下代码 void fanpai(struct node *p) { struct node *p1,*p2; p1 = p; if(p1!=NULL){ fanpai(p1->next); }

for(p2=p1;p2!=NULL;p2=p2->next) {

if(p2->data%p1->data==0) {

if(p2->key==0) p2->key=1; else

p2->key=0; } }

}

 哈夫曼编码

第 11 页

4.2经验与体会

在编写程序时应该用规范化的格式输入源程序，同时注意不要忘了编写头文件#include、#include；在编程时不要忽略了一些细节，不要忘了；、｝等符号，否则程序将无法正常运行。

在调用指针时应先将其初始化，如果没有初始化指针就调用它，这样很不安全，虽然你有时可以运行，却有了不安定的因素。如：int *data;可以成定义：int data [52];这里的data是一个常量地址，也是一个数组名，因此不用担心它没有被初始化。

4.3测试结果

 纸牌游戏

第 12 页

 哈夫曼编码

第五章 总结分析

通过这次的数据结构课程设计，我明显感觉到自己在很多方面的不足，但问题总是要解决的，必须找出问题然后将其一一解除。所以在整个过程中，我不断加深了对数据结构的理解与一些程序写书时要注意的事项，也让我对这门课程有了进一步的了解和认识。完成一个课程设计要注意很多方面，无论是格式、书写的内容还是要表达的思想，所以我们必须严格要求自己。本次课程设计涉及了很多

第 13 页

知识，由于往日学得不扎实，对某些问题仍然存在疑惑，我查阅了相关书籍，以便将疑难问题解决，同时更加进一步的掌握相关知识。

此次的课程设计不仅让我深刻体会到了学习这门课程的重要性与必要性，也让我懂得了学习是思考一个的过程，我们应该主动去思考学到的知识以及学到后怎么去运用，而不是一味地被动地接受。数据结构及其算法在解决现实生活中的常见问题和书写软件设计方面上都有着重要的意义，我们应该好好掌握它的相关知识，在以后的学习过程中，更多的去学会如何运用知识。

第六章 参考文献

[1]刘振鹏 张晓莉 郝杰.数据结构.北京：中国铁道出版社.2005 [2]谭浩强 .C语言程序设计（第二版）.北京：清华大学出版社.2008 [3]严蔚敏 吴伟民.数据结构（C语言版）.北京：清华大学出版社.2010 [4]黄国瑜 叶乃菁.数据结构（C语言版）.北京：清华大学出版社.2002 [5]朱站立.数据结构（第三版）.西安：西安交通大学出版社.2004

附录 源程序

 纸牌游戏

#include #include #include

struct node //定义结点

{ int data; //定义数据域，即牌的序号

int key; //标志 key为1表示正面朝上key为0表示反面朝上 struct node *next; };

struct node *create() //定义链表建立函数create() { struct node *p,*head,*s; //其返回值为结构指针 int i; //牌的序号,1-52

head=NULL; //初始化头指针

p=(struct node*)malloc(sizeof(*p)); //生成P结点 if(p==NULL)

{ printf(\"Memory is too small!\\n\"); }

head=p;

head->data=1;

第 14 页

//第一张牌

head->key=1;

head->next=NULL;

for(i=2;i<=52;i++) //建立结点的链表

{ s=(struct node*)malloc(sizeof(*p)); //s结点是临时的，p结点跟着s结点走，直到52

s->data=i; //牌号,1-52

s->key=1; // 初始化所有牌都是正面朝上 p->next=s; p=s; }

p->next=NULL; return(head); }

void fanpai(struct node *p) //翻牌算法 { struct node *p1,*p2; p1 = p;

if(p1!=NULL){

fanpai(p1->next); //递归，一直调用p1但不执行，直到p1=52，然后p2从52开始、51开始、50开始。。。

} //先执行外循环，直到p1->next=null,在执行内循环，即翻牌

for(p2=p1;p2!=NULL;p2=p2->next) //p1从2开始固定，然后p2一直往后走 {

if(p2->data%p1->data==0) //是p1的倍数则翻牌 {

if(p2->key==0) p2->key=1; else

p2->key=0; } } }

void main()

{ struct node *head,*np; head=create(); if(head==NULL)

printf(\"链接错误！\\n\");

fanpai(head); //调用翻牌算法开始翻牌 printf(\"\\n 最后正面向上的牌有\");

for(np=head;np!=NULL;np=np->next) //输出翻牌完成后的结果 { if(np->key==0)

printf(\"%4d\->data); }

第 15 页

printf(\"\\n\"); }

 哈夫曼编码

#include

#include // 用到系统标准输出函数的 #include

#include //用到像getch()这种键盘输入函数 /* Huffman 树的存储结构*/

#define n 6 /*叶子数目根据需要设定*/ #define m 2*n-1 /* Huffman 树中结点总数 */ /* Huffman 树的存储结构*/

typedef struct /*结构体定义*/ {int weight; /*结点的权值*/

int lchild,rchild,parent; /*左、右孩子及双亲的下标*/ }htnode; /*哈夫曼树结点类型*/

typedef htnode huffmantree[m+1]; /* huffmantree是结构数组类型,其0号单元不用，存储哈夫曼树 */

typedef struct

{char ch; /*存储字符*/ char code[n+1]; /*存放编码位串*/ }codenode; /*编码结点类型*/

typedef codenode huffmancode[n+1]; /*huffmancode是结构数组类型,其0号单元不用,存储哈夫曼编码*/

void inithuffmantree(huffmantree ht) /*初始化哈夫曼树函数inithuffmantree()*/ {int i;

for(i=0;i<=m;i++) {ht[i].weight=0;

ht[i].lchild=ht[i].rchild=ht[i].parent=0; } }

第 16 页

void inputweight(huffmantree ht) /*输入权值函数 */ {int i;

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

printf(\" ……请输入第[%d]个权值: \

scanf(\"%d\

} printf(\"\\n\"); }

void selectmin(huffmantree ht, int i, int *p1, int *p2)

/* 在ht[1..i]中选两个权值最小的根结点，其序号为*p1和*p2，*p1中放权值最小的根结点的序号，*p2中放权值次小的根结点的序号*/

{int j,min1,min2; /* min1,min2分别是最小权值和次小权值*/

min1=min2=32767; *p1=*p2=0; for(j=1;j<=i;j++)

{if(ht[j].parent==0) /* j 为根结点*/ if(ht[j].weightif(min1!=32767) {min2=min1; *p2=*p1;} min1=ht[j].weight; *p1=j; } else

if(ht[j].weightvoid createhuffmantree(huffmantree ht) /*构造huffman树，ht[m]为其根结点*/ {

int i,p1,p2;

第 17 页

inithuffmantree(ht); /* 将ht初始化*/

inputweight(ht); /* 输入叶子权值至ht [1..n]的weight域*/

for(i=n+1;i<=m;i++) /* 共进行n-1次合并，新结点依次存于ht[i]中*/

{selectmin(ht,i-1,&p1,&p2); /*在ht [1.. i-1]中选择两个权值最小的根结点，其序号分别为p1和p2*/ ht[p1].parent=ht[p2].parent=i;

ht[i].lchild=p1; /* 最小权值的根结点是新结点的左孩子*/

ht[i].rchild=p2; /* 次小权值的根结点是新结点的右孩子*/

ht[i].weight=ht[p1].weight+ht[p2].weight; } }

void huffmancodes(huffmantree ht,huffmancode hcd) /*根据huffman树ht求huffman编码*/ {

int c,p,i; /* c和p分别指示 ht中孩子和双亲的位置 */

char cd[n+1]; /* 临时存放编码*/

int start; /* 指示编码在cd 中的起始位置*/ cd[n]='\\0';

getchar(); /* 编码结束符*/ printf(\"2.……请依次输入字符……:\");

for(i=1;i<=n;i++) /* 依次求叶子ht [i]的编码*/ { hcd[i].ch=getchar(); /* 读入叶子ht [i]对应的字符*/ start=n; /* 编码起始位置的初值*/ c=i; /* 从叶子ht [i]开始上溯*/ while((p=ht[c].parent)!=0) /* 直至上溯到ht [ c]是树根为止*/ { cd[--start]=(ht[p].lchild==c)?'0':'1'; /*若ht [ c]是ht[p]的左孩子，则生成代码0，否则生成代码1*/

c=p; /* 继续上溯*/ }

第 18 页

strcpy(hcd[i].code,&cd[start]); /* 复制编码位串*/ } printf(\"\\n\");

printf(\"3.………哈夫曼编码结果为：……\\n\"); printf(\"\\n\"); for(i=1;i<=n;i++)

printf(\" ……第[%d]个字符[%c]的编码为：%s\\n\ }

void main() {huffmantree t; huffmancode h;

printf(\"|^^^^^^^^^^^^^^^^^^^^^^^^^^^*########################*^^^^^^^^^^^^^^^^^^^|\\n\");

printf(\"|^^^^^^^^^^^^^^^^^^^^^^^^^^^*欢迎使用哈弗曼编码系统！*^^^^^^^^^^^^^^^^^^^|\\n\");

printf(\"|^^^^^^^^^^^^^^^^^^^^^^^^^^^*########################*^^^^^^^^^^^^^^^^^^^|\\n\"); printf(\"\\n\");

printf(\"1.…………请输入%d个权值:……\\n\ printf(\"\\n\");

createhuffmantree(t); /* 构造huffman树*/ huffmancodes(t,h); /* 构造huffman编码*/ }

第 19 页