数据结构课设报告(编辑修改稿)

数据结构课设报告(编辑修改稿)内容摘要：

} else { if (huffTree[i].weight huffTree[s1].weight) { s2 = s1。 s1 = i。 } 9 else if (huffTree[i].weight huffTree[s2].weight) s2 = i。 } } } (5) 建立哈夫曼树函数 void Huffman::MakeCharMap() { if (n = 1) return。 int m = 2 * n 1。 //哈弗曼树所需节点数 huffTree = new HuffTreeNode[m+1]。 //0 号单元未使用 //初始化 int i。 for (i = 1。 i = n。 ++i) { huffTree[i].weight = chars[i].weight。 huffTree[i].cc = chars[i].c。 huffTree[i].parent = 0。 huffTree[i].lchild = 0。 huffTree[i].rchild = 0。 } for (i = n + 1。 i = m。 ++i) { huffTree[i].weight = 0。 huffTree[i].parent = 0。 huffTree[i].lchild = 0。 huffTree[i].rchild = 0。 huffTree[i].cc = 39。 39。 } //建哈弗曼树 for (i = n + 1。 i = m。 ++i) { int s1,s2。 select(i 1, s1, s2)。 //在 huffTree[1n]中选取 parent 和 weight 值最小的两个节点 huffTree[s1].parent = huffTree[s2].parent = i。 huffTree[i].lchild = s1。 huffTree[i].rchild = s2。 //从叶子到根节点逆向求每个字符的哈弗曼编码 huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight。 } char *cd = new char[n]。 //分配求编码的工作空间（每个字符编码结果最长 n1 再加上 39。 /039。 ） cd[n1] = 39。 /039。 //编码结束符 for(i = 1。 i = n。 ++i) //逐个字符求哈弗曼编码 10 { int start = n。 //原来是 n1，不正确，编码结果总是多了个 0 int c,f。 //从叶子到根逆向求编码 for (c = i, f = huffTree[i].parent。 f != 0。 c = f, f = huffTree[f].parent) { if (huffTree[f].lchild == c) //左孩子编码为 1 cd[start] = 39。 139。 else //右孩子编码为 0 cd[start] = 39。 039。 } chars[i].code = new char[n start]。 //为第 i 个字符编码分配空间 strcpy(chars[i].code,amp。 cd[start])。 } delete [] cd。 } (6) 统计哈夫曼编码长度函数 float Huffman::CountLength() { length = 0。 for(int i = 1。 i = n。 i ++ ) { length = length + chars[i].weight/() * (strlen((chars[i].code))4)。 } return length。 } (7) 译码函数 void Huffman::Decode() { char s[1000]={39。 \039。 }。 char d[1000]={39。 \039。 }。 coutendl。 cout 提示：译码功能是在之前编码的数据上来对二进制代码进行的 !endl。 coutendl。 cout请输入 二进制代码 :。 scanf(%s,s)。 char *ps = s。 char *pd = d。 cout译码结果为：。 while(*ps!=39。 \039。 ) { 11 int parent=2*n1。 while(huffTree[parent].lchild!=0) { if(*ps==39。 139。 ) parent=huffTree[parent].lchild。 else parent=huffTree[parent].rchild。 ps++。 } *pd=chars[parent].c。 cout*pd。 pd++。 } coutendl。 coutendl。 coutendl。 system(pause)。 } (8) 编码函数 void Huffman::Encode() { //cout ()amp。 *amp。 *amp。 *endl。 text 文件里字符的总个数 code =。 for (string::size_type i = 0。 i != ()。 ++i) { for (int j = 1。 j = n。 ++j) if (chars[j].c == text[i]) code += chars[j].code。 } (9) 打印哈夫曼码函数 void Huffman::PrintCharCode() { for (int i = 1。 i = n。 ++i) { switch (chars[i].c) { case 39。 /t39。 : cout //t。 break。 case 39。 /n39。 : cout //n。 break。 default: cout chars[i].c。 12 break。 } cout —— chars[i].code endl。 } } (10) 打印哈夫曼树函数 int Huffman::print_at_level(int h,int level) { if(!h || level 0) return 0。 if(0==level) { couthuffTree[h].cc。 return 1。 } // coutendl。 return print_at_level(huffTree[h].lchild,level 1)+print_at_level(huffTree[h].rchild,level1)。 } void Huffman::print_by_level(int h) { int i=0。 for(i=0。 i++) { if(!print_at_level(h,i)) { //coutendl。 break。 } coutendl。 } coutendl。 } void Huffman::printHuffTree() { print_by_level(2*n1)。 system(pause)。 } 13 四、 调试分析 本程序采用的数据结构有数和链表，其中树的部分有简化，这有弊有利。 在实现建立哈夫曼树，编码译码时，这些操作都十分简单易懂。 但也有不好的地方。 由于在设计之初对左右孩子采用的是数字标识的方法，而不是用一个指针，导致在最后编写打印哈夫曼树的代码时，遇到了很大问题，使得按照树的实际结构打印十分困难，最终也只能达到层次打印的效果。 这说明一个好的数据结构十分重要，对于功能的实现有着非常重要的意义。 本程序的模块划分比较合理，一共分为了初始化，编码，译码，打印哈夫曼树四个主要部分。 思路清晰， 每次写完一个部分的代码 后，及时进行测试，这样使得完成进度大大加快，一旦出现错误也能够及时准确地发现。 值得改进的地方是，在每个部分中，为了完成一个功能，有多个函数，这中间存在着设计缺陷，使得算法效率较低。 这也反映了代码量的不足，只有多练习才能尽量减少多余的代码。 五、 用户手册 本程序的演示环境是。 编译链接成功后即可进入程序执行界面，如下所示。 初始化一共有两种方法，分别是从文件读入和手动输入。 如果采取从文件读入，则需要在 文件中输入字符集，然后将此 txt 文件放在程序所在路径下。 14 手动输入比较简单，输入字符和对应权值，权值是字符出现次数。 在初始化完成后，就进入菜单界面。 选择 14，即可完成不同的功能。 六、 测试结果 在 文件中写入测试数据 “THIS PROGRAM IS MY FAVORITE”后，选择编码功能。 统计得字符对应权值为： 15 哈夫曼编码为： 16 求得编码长度为： 17 实验二 飞机订票系统 一、 需求分析 问题分析 一机场每天有 n 个航班，每个班次都有一班次号（ 1， 2， 3……n ），固定的起飞时间，固定的路线（起始站，终点站），大致的飞行时间，固定的额定载客量。 如： 班次 起飞时间 起始站 终点站 飞行时间 额定载量 定票人数 1 8： 00 天津 广汉 2 145 130 2 6： 30 天津 成都 140 140 3 7： 00 天津 成都 140 120 4 10： 00 天津 成都 140 120 试设计一个机票管理系统，对机场的售票情况进行管理。 基本要求 功能要求： (1) 录入班次信息（信息用文件保存），可不时地增加班次数据； (2) 浏览班次信息，可显示所有班次当前状况（如果系统时间超过了某班次的起飞时间，则显示 “此班已发出 ”的提示信息）； (3) 查询路线，可按班次号查询，可按终点站查询； (4) 售票和退票功能； A：根据客户提出的要求（航班号，订票数额）查询该航班情况，若尚有余票，则为客户办理订票手续，输出座位号。 若已满员或余票少于订票额，则需重新询问客户要求。 若需要，可预约等级排队等候。 选做：当客户订票要求不能满足时，系统可向客户提供到达同一目的地的其他航线情况。 B：根据客户提供的情况（日期，航班），为客户办理退票手续，然后查询该航班是否有人预约登记。 首先询问排在第一的客户。