兰州大学数据结构课程设计4

《兰州大学数据结构课程设计4》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》课程设计题目程序实现采用C语言）题目1：猴子选王（学时：3）一堆猴子都有编号，编号是1,2,这群猴子（m个）按照1-山的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈屮只剩下最后一只猴子，则该猴子为大王。要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。题目2:字符逆转（学时：3）从键盘读入一个字符串，把它存入一个链表（每个结点存储1个字符），并按相反的次序将字符吊输出到显示屏。题目3:工资核算（学时：3）设冇一个单位的人员工资有如下信息：name、department、basepayal1owan

2、ce、totalo现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的basepay增加100元，增加后将工资数据显示于屏幕（每行1人）。题目4：满足条件的有序表生成（学时：3）已知三个有序表A、B、C,它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所冇的既在B中又在C中出现的元索。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。题目5：—元多项式的减法（学时：6）设有两个一元多项式A（x）,B（x）,请完成运算A（x）+B（x）、A（x）-B（x），要求多项式采用链表进行

3、存储。另外该任务耍求具冇建立多项式链表以及输岀多项式到屏幕的功能。题目6：床位分配（学时：6）某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收冋床位的程序。要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。题目7：文本文件单词的检索及计数（学时：6）要求编程建立一个文木文件，每个单词不包括空格及跨行，单词由字符序列构成口区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文

4、件屮首次出现的行号及位置。题目8：二叉树的遍历（学时：6）二叉树以1son-rson链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输岀后序遍历结果、交换左右子树、统计高度，其屮对于屮序、后序的遍历运算要求采用非递归方式。题目9：创建二叉排序树（学时：3）二叉排序树以lson-rson链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示屮序遍丿力结果的程序。题目10：霍夫曼编码应用（学时：3）假设一吊由大写字母构成的电文，采用霍夫曼规则对其进行编码，以菜单方式设计并完成功能任务：建立霍夫曼树、霍夫曼编码

5、生成、编码文件译码。#include#include#include#definen100#definem2*n-ltypedefstnict〃码结点的存储结构charch;charbitsf9];intlen;}CodcNodc;typedefCodeNodeHuffmanCode[n+1J;typcdcfstruct〃树结点的存储结构{intweight;intlchild,rchild,parent;JHTNode;typedefHTNodeHuffmanTree[m+1];intnum;voidselect(

6、HuffmanTreeHT,intk,int&sl,int&s2)〃挑选权值最小的两个结点{inti,j;intminl=32767;for(i=l;i<=k;i++)if(HT[i].weight

7、计输入字符和串char*p;inti,j,k=O;inttcmp[257];for(i=0;i<257;i++)temp[iJ=O;for(p=s;*p!=*';p+4-)temp[*p]++;for(i=0,j=0;i<=256;i++)if(temp[i]!=O){j++；str[j]=i;cnt[j]=tcmp[i];}num=j;returnj;}〃建立霍夫曼树voidchuffmanTree(HuffmanTree&HT,HuffmanC(xle&HC,intcnt[],charstr[]){inti,sl,s2;for(i