数据结构实验报告.docx

编号:
江西理工大学
数据结构课程设计报告
班级:
学号:
姓名:
时间:

指导教师:
目录
第一章需求分析 1
1
1
第二章概要设计 2
2
2
4
第三章详细设计 5
5
6
9
第四章调试分析 10
10
12
12
第五章总结分析 13
第六章参考文献 14
附录源程序 14
需求分析

纸牌游戏

编号为1-52张牌,正面向上,从第2张开始,以2为基数,是2的倍数的牌翻一次,直到最后一张牌;然后,从第3张开始,以3为基数,是3的倍数的牌翻一次,直到最后一张牌;然后…从第4张开始,以4为基数,是4的倍数的牌翻一次, 直到最后一张牌;...再依次5的倍数的牌翻一次,6的,7的直到以52为基数的翻过,输出:这时正面向上的牌有哪些?要求:用数组、链表结构实现,采用递归方法。
哈夫曼编码
设计出下面字符表的哈夫曼编码对应的二叉树,并输出每个字符的哈夫曼编码。
字符
m
n
o
p
q
r
出现频率(%)
13
44
12
17
9
5

纸牌游戏
①了解线性表的特性,以及它们在实际问题中的应用。
②掌握顺序表和链表的实现方法,以及它们的基本操作。
③掌握线性表的链式存储结构——单链表的定义及其C语言实现。
④掌握线性表在链式存储结构——单链表中的各种基本操作。
⑤通过用链表编程实现问题的解决,提高自身的问题解决能力。
哈夫曼编码
以字符的频度为权值,建立哈夫曼树,求哈夫曼编码。根据字符及权值得到其相应的编码。
概要设计

纸牌游戏
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号单元不用,存储哈夫曼编码*/

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

①初始化头结点正面朝上
head 1
head 1
...... ......
null null

p

②初始化所有牌正面朝上
3 1
2 1
1 1
s
p
③循环完后递归
52 1
51 1
52 0
52 1
51 1
50 1
. . . . . .
. . . . . .
. . . . . .
4 1
3 0
2 0
1 1