数据结构与算法-大作业(1)

1、数据结构与算法-综合设计题目01哈夫曼编码02图书馆管理系统03交通导航系统01哈夫曼编码题目内容在数据通信领域，常采用不等长的编码方式，即对常用的字符用较少的码位编码，对不常出现的字符用较多的码位编码，哈夫曼编码就是基于此目的的不等长编码方法。要求通过统计一段文章中各字符的出现频率，构造哈夫曼树生成哈夫曼编码，并通过该编码实现对基于该编码的二进制码文件的解码。 1 在记事本软件中，放入不小于1000个英文字符的文本，命名为source.txt。3根据字符列表文件建立字符列表的哈夫曼编码本12编写过程，挑出文本中的不相同字符，输出文件列出每个字符的出现概率。4以哈夫曼编码本1为参照，将文本文件

2、source.txt的内容转换为二进制码文件code.dat5以哈夫曼编码本1为参照，将二进制码文件code1.dat的内容解码为target.txt明文6编写函数，对比source.txt和 target.txt是否相同，不同则返回出现不同的位置点。题目内容进阶要求q能实现从运行程序中读取并编译不同的文件q要求有良好的人机界面，具有较强的纠错性（健壮性）进阶要求q封面（包含设计课题名称，专业，班级，姓名，学号，指导教师）q设计任务和技术要求q内容摘要q正文q总体设计方案（方案的论证，框图等）q数据结构和算法设计（数据结构的选择，算法原理阐述）q程序设计（源程序清单和注释）q程序调试和参数测试

3、q总结02图书馆管理系统题目内容图书馆管理信息系统涉及大量的数据处理。由于内存不适合存储这类数据，所以一般是将它们存储于外存设备中，通常把这种存放在外存中的数据结构称为文件。图书信息表所表示的就是数据库文件，它是带有结构的记录的集合，每个记录可由若干数据构成。图书管理一班包括图书采编、图书编目、图书查询和图书流通（借、还）等。 图书管理一般包含图书采编，图书编目，图书查询和图书流通（借，还）等，要求设计一个图书管理信息系统，从而实现下列功能：题目要求具体要求：q 建立一个图书信息数据库文件，输入若干种书的记录，建立一个以书号为主关键字的索引文件，建立以书名，作者和出版社为次关键字的索引q 建立

4、关于书号，书名，作者和出版社的图书查询q 实现图书的借还子系统，包括建立读者文件，借还文件，读者管理和图书借还的相关处理数据文件类型设计q 主数据库文件typedef structchar bno5; 书号char bname21; 书名int namenext；书名指针链，作记录的指针地址char author9;作者Int authornext；作者指针链char press11;出版社Int prenext；出版社指针链char sortno4;分类号int sortenum;藏书量int borrownum;借出书BookRecType;数据库记录类型typedef structBoo

5、kRecType BookDbaseBookSize;int len;文件当前长度BookDbaseFile;定义图书数据库文件类型数据文件类型设计q 书号索引文件typedef structchar bno5; 书号int RecNo； 记录指针BidRecType;索引文件记录类型typedef structBidRecType BnoIdxBookSize;int len;文件当前个数BnoIdxNum;定义书号索引文件类型数据文件类型设计q 书名链头索引文件typedef structchar bname21; 书名int lhead;链头指针int RecNum； 长度BNRecTy

6、pe;索引文件记录类型typedef structBNRecType LHFrec1BLHnum;int len1;文件当前个数LHFile1;定义书号索引文件类型q 作者链头索引文件q 出版社链头索引文件数据文件类型设计q 读者文件typedef structchar rno4;读者号char name8;读者名int bn1;可借书数int bn2;已借书数RRecType;读者文件记录类型typedef structRRecType ReadRecRrnum;int len;当前读者数Readerfile;读者文件类型数据文件类型设计q 借还书文件typedef structchar r

7、no4; 读者号char bno5;书号char date19;借书日期char date29;还书日期BbookRecType; 借还书文件记录类型typedef structBbookRecType BbookBookSize;int len;当前借书数BbookFile;借还书类型记录号记录号书号书号书名书名指针指针1作者作者指针指针2出版社出版社指针指针3分类分类藏书量藏书量借出书借出书11021数据库0李小云0人民邮电00218021014数据结构0刘晓阳0中国科学00136031106操作系统0许海平0人民邮电10247041108数据结构2孙华英0清华大学00135051203程

8、序设计0李小云1中国科学20356062105数据库1许海平3清华大学40216071012数据结构4李小云5人民邮电20135080109程序设计5刘晓阳2清华大学603570书名书名链头地址链头地址长度长度数据库62数据结构73操作系统31程序设计82作者作者链头地址链头地址长度长度李小云73刘晓阳82许海平62孙华英41出版社出版社链头地址链头地址长度长度人民邮电73中国科学52清华大学831. 输入图书记录的相关文件q追加一条图书主数据库记录q修改书号索引表q修改书名索引和书名链头索引表q修改作者索引和作者链头索引表q修改出版社索引和出版社链头索引表q输入图书记录的控制程序2. 建立关

9、于书号，书名，作者和出版社的查询q按书号查询算法（二分法查找）q按书名查询算法q按作者查询算法q按出版社查询算法q输出一条图书主数据库记录q图书查询控制程序3. 借还书处理q借书处理算法q还书处理算法4. 读者管理子系统（增加新读者）5. 各类文件写盘6. 读入盘中各类文件图书管理系统图书管理系统系统维护系统维护读者管理读者管理图书管理图书管理图书流通图书流通退出系统退出系统初始初始化化读盘读盘图书图书信息信息输入输入图书图书信息信息查询查询借书借书还书还书增加增加新读新读者者存盘存盘并退并退出出书名书名查询查询作者作者查询查询出版出版社查社查询询书号书号查询查询返回返回系统结构图系统功能算法

10、分析输入一条图书记录 Void AppeDBaseFile(BookDbaseFile &df) 提示输入项的输入顺序； 输入一条记录； 图书记录计数器加1； 建立图书数据库文件及对应的索引文件书号索引文件的修改Void ChangeBnoIdxF(BookDbaseFile &df，BnoIdxFile &bif)取当前图书记录中书号送至变量sh；输入一条记录；While（j=1）If(sh索引表中第j个记录的书号)k=j+1; break;j-;有序索引表中插入一个索引记录；记录后移，留出位置；插入记录；bif.len+; 建立图书数据库文件及对应的索引文件以书名次

11、关键字建立索引的算法Void ChangeLinkHeadF1(BookDbaseFile &df，LHFile1 &lhf1)处理图书文件当前记录；While（j=1&choose=5）显示图书查询菜单：1. 书号 2. 书名 3. 作者 4.出版社 5.退出请用户选择: to chooseSwitch(choose)Case 1: 输入书号；调用书号查询算法； break；Case 2: 输入书名；调用书名查询算法； break；Case 3: 输入作者；调用作者查询算法； break；Case 4: 输入出版社；调用出版社查询算法； break；Case 5: r

12、eturn； 建立图书数据库文件及对应的索引文件书号查询算法Int BinSearch(BnoIdxFile bif, char key)While(low=high)Mid=(low+high)/2;If(strcmp(key, L.slmid.key)=0) return mid;Else if(If(strcmp(key, L.slmid.key)0) high=mid-1;Else low=mid+1书名查找办法int BnameFind(LHFile1 lhf1, char key)/顺序查找书名链头文件for（i=0; ilhf1.len1; i+）if(key=链头文件中当前记录

13、的书名)k=链头文件当前记录链头；退出循环return k； 建立图书数据库文件及对应的索引文件借书处理算法void BorrowBook(BookDaseFile bf, BbookFile bbf, ReaderFile rf)输入读者号，书号，借阅日期借书处理：查找读者文件，验证读者身份，先检验读者是否可以借书，若不能借，就提示读者“书已借满，不能再借”；若可借，则查图书主文件，借阅的书是否已被借出，若借出，显示“图书已借出”，否则，借还书文件追加一条记录，记录相关内容，并分别修改图书文件和读者文件还书处理算法void BackBook(BookDaseFile bf, BbookFil

14、e bbf, ReaderFile rf)输入读者号，书号，还书日期；还书处理：查找读者文件，修改借书数；查图书主文件，修改借出数；查询借还书文件，填入还书日期； 借书和还书处理算法交通导航系统03题目内容该设计案例主要在图的基本概念和基本算法的基础上考察学生数据的存储结构和最短路径的相应求解算法。模拟导航系统，在选择出发地点和目的地点后，依据不同的导航模式，给出不同的导航路径。例如最短路径是基于两地点之间的距离求解，而最短时间则是基于道路限速情况，最少花费则需要衡量该段路段是否要进行收费等。 该设计案例主要在图的基本概念和基本算法的基础上考察学生数据的存储结构和最短路径的相应求解算法。模拟导航系统，在选择出发地点和目的地点后，依据不同的导航模式，给出不同的导航路径。例如最短路径是基于两地点之间的距离求解，而最短时间则是基于道路限速情况，最少花费则需要衡量该段路段是否要进行收费等。题目要求具体要求：q 建立地图数据库，要求建立城市及道路数据库，并将信息保存于文件