计算机软件基础上机实验报告

计算机软件基础上机实验报告 一 一 实验目的实验目的 1 熟知 C 程序的结构特征及运行特点 2 掌握算法分析和编码的意义 二 二 实验要求实验要求 实践内容 1 试设计一算法 从包括 n 个元素的数组中 求最大和最小元素 并使得当 n 个元素为 有序排列时 元素之间的比较次数仅为 n 1 次 2 在给出的 Huffman 编码源程序基础上 要求画出 Huffman 树 求出与等长编码相比时 的压缩比 实验要求 1 根据实验内容编写算法 并用 C 语言进行程序设计 2 将所编程序在计算机上调试通过 并全面测试 3 整理完成实验报告 包括 姓名 学号 实验日期等 三 实验过程三 实验过程 1 include define N 10 int max int a int n int i m a 0 for i 1 im m a i return m int min int a int n int i m a 0 for i 1 i n i if a i m m a i return m void main int i f N for i 0 i N i scanf d printf max d min d n max f N min f N 运行结果 2 include include include include include typedef struct unsigned int weight 结点权值 unsigned int parent lchild rchild 结点的父指针 左右孩子指针 HTNode HuffmanTree 动态分配数组存储哈夫曼树 typedef char HuffmanCode 动态分配数组存储哈夫曼编码表 void CreateHuffmanTree HuffmanTree 生成哈夫曼树 void HuffmanCoding HuffmanTree HuffmanCode 对哈夫曼树进行编码 void PrintHuffmanCode HuffmanCode unsigned int int 显示哈夫曼编码 void Select HuffmanTree int int 在数组中寻找权值最小的两个结点 void main HuffmanTree HT 哈夫曼树 HT HuffmanCode HC 哈夫曼编码表 HC int n i n 是哈夫曼树叶子结点数 unsigned int w w 存放叶子结点权值 char j y printf 演示构造哈夫曼树 n printf 输入需要进行编码的字符数目 n 例如 8 n printf 然后输入每个字符出现的次数 权值 n printf 例如 5 29 7 8 14 23 3 11 n printf 自动构造一棵哈夫曼树并显示哈夫曼编码 n printf 5 0110 n 29 10 n 7 1110 n 8 1111 n 14 110 n printf 23 00 n 3 0111 n 11 010 n while j N scanf d 输入字符数目 if n 1 printf 该数不合理 n continue w unsigned int malloc n sizeof unsigned int 开辟空间存放权值 printf 请输入各字符出现的次数 权值 n for i 0 i n i scanf d 输入各字符出现的次数 权值 CreateHuffmanTree HT w n 生成哈夫曼树 HuffmanCoding HT HC n 进行哈夫曼编码 PrintHuffmanCode HC w n 显示哈夫曼编码 printf 哈夫曼树构造完毕 还要继续吗 Y N scanf c void CreateHuffmanTree HuffmanTree int s1 s2 HuffmanTree p if n 1 return m 2 n 1 n 个叶子结点的哈夫曼树 有 2 n 1 个结点 HT HuffmanTree malloc m 1 sizeof HTNode 开辟 2 n 各结点空间 for p HT 1 i 1 iweight w p parent 0 p lchild 0 p rchild 0 for iweight 0 p parent 0 p lchild 0 p rchild 0 for i n 1 i m i 建哈夫曼树 Select HT i 1 s1 s2 从 HT 1 i 1 中选择 parent 为 0 且 weight 最小的两个结点 其序号分别为 s1 和 s2 HT s1 parent i HT s2 parent i 修改 s1 和 s2 结点的父指针 parent HT i lchild s1 HT i rchild s2 修改 i 结点的左右孩子指针 HT i weight HT s1 weight HT s2 weight 修改权值 void HuffmanCoding HuffmanTree HT HuffmanCode char cd HC HuffmanCode malloc n 1 sizeof char 分配 n 个编码的头指针向量 cd char malloc n sizeof char 开辟一个求编码的工作空间 cd n 1 0 编码结束符 for i 1 i n 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 若是左孩子编为 0 else cd start 1 若是右孩子编为 1 HC i char malloc n start sizeof char 为第 i 个编码分配空间 strcpy HC i 将编码从 cd 复制到 HC 中 free cd 释放工作空间 void PrintHuffmanCode HuffmanCode HC unsigned int w int n 显示有 n 个叶子结点的哈夫曼树的编码表 int i printf HuffmanCode is n for i 1 i n i printf 3d w i 1 puts HC i printf n void Select HuffmanTree HT int t int m n 10000 for i 1 i t i if HT i parent 0s1 s2 s2 i 运行结果 Huffman 树 21 3 45 0 01 0 1 1 01 Huffman 编码的平均码长 1 5 3 3 2 2 2 2 4 Huffman 编码的压缩比 3 2 4 1 25 四 实验心得四 实验心得 在实验过程中我再次复习了 c 的编写及运行 以前在学习 C 的过程中有涉及到各 种排序 查找 那时我们只是机械般的想要编写出正确的结果 却从未想过这样做有着怎 样的意义 然而通过对计算机软件基础课程的学习以及此次的实验 我了解到选择合适的 方法可以很大程度地提高运算效率 实验中也使我对上个学期的信息论与编码有了很好的 复习和新的认识 虽然等长编码的译码要方便的多 可是在实际过程中 总是希望电文