数据结构与算法 实验指导

本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。本次实习还可以起到复习C语言的作用。

1.1① 合并线性表

问题描述：

    将两个按元素值递增有序排列的线性表A和B合并为一个按元素值递减有序排列的线性表C（允许值相同）。

基本要求：

(1)采用顺序存储结构，可另外开辟空间存放C。

(2)以单链表作存储结构，利用原表空间（即A和B的结点空间）存放C。

1.2① 多项式相乘

问题描述：

    已知一元n次多项式的形式为：F(x)=a0+a1x+a2x2+…+anxn，求两个一元多项式的乘积。

基本要求：

    以单循环链表作多项式的存储结构，链表中每一个结点为：

                系数        指数         指针

1.3① 定位运算

问题描述：

定位运算LOCATE(L,x)的功能是：查找值为x的结点在线性表L中的位置。当线性表L中存在一个值为x的结点时，结果就是该结点的位置；若线性表L中存在多个值为x的结点，则是首次找到的结点的位置；当线性表L中不存在值为x的结点，将给出一个特殊的值表示值为x的结点不存在。

基本要求：

编写符合以下要求的LOCATE运算算法：

采用双向链表作存储结构，链表中每个结点的结构为：

其中：freq是访问频度域，在链表起用之前，其值均初始化为零。

每当在链表进行一次LOCATE(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。

1.4② 运动会分数统计

问题描述： 

    参加运动会的n个学校编号分别为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m+1~m+w。由于各项目的参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。

基本要求：

    产生各学校的成绩单，内容包括各校所得的每项成绩的项目号，名次（成绩），姓名和得分；产生团体总分报表，内容包括学校编号、男子团体总分、女子团体总分和团体总分。

测试数据：

    对于n=4，m=3，w=2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。

实现提示：

    可以假设n20,m20,姓名长度不超过20个字符，每个项目结束时，将其编号，类型符（区分前五名还是前三名）输入，并按名次顺序输入运动员姓名，学校编号（和成绩）。

选作内容：

允许用户指定某项目采取其它名次取法。

1.5③ 约瑟夫环

问题描述：

    约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报到m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

基本要求：

    利用单向循环链表存储结构模拟此过程，按出列的顺序打印个人的编号。

测试数据：

    m的初始值为20；密码是3，1，7，2，4，8，4（正确的结果应为：6，1，4，7，2，3，5）

实现提示：

    程序运行后首先要求用户指定初始报数的上限值，然后读取各人的密码。设n30。

选作内容：

向上述程序中添加在顺序结构上实现的部分。

1.6④ 长整数的运算

问题描述：

设计一个程序实现两个任意长的整数求和运算。

基本要求：

利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是-215~(215-1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

测试数据：

(1)0；0；应输出“0”。

(2)-2345，67；-7654，3211；应输出“-1，0000，0000”。

(3)-9999，9999；1，0000，0000，0000；应输出“9999，0000，0001”。

(4)1，0001，0001；-1，0001，0001；应输出“0”。

(5)1，0001，0001；-1，0001，0000；输出“1”。

实现提示：

(1)每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。

(2)可以利用头结点的数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数规定上限。

选作内容：

修改上述程序，使它在整型量范围是-2n-~( 2n-1)的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。

实习二  栈和队列

    本次实习的目的在于使学生深入了解栈和队列的特性，以便在实际问题背景下灵活运用它们。同时将巩固这两种结构的构造方法，接触较复杂问题的递归算法的设计。

2.1② 停车场管理

问题描述：

    设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入，当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

基本要求：

    以栈模拟停车场，以队模拟停车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”和“离去”信息、汽车牌照号码及到达和离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。

测试数据：

    设n=2，输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。其中：‘A’表示到达；‘D’表示离去；‘E’表示输入结束。

实现提示：

    须另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的照牌号码和进入停车场的时刻。

选作内容：

（1）两个栈共享空间，思考应开辟数组的空间是多少？

（2）汽车可有不同的种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车的占地面积相当于3辆小汽车的占地面积。

（3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排列队尾。

（4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。

2.2② 魔王语言解释

问题描述：

有一个魔王总是使用自己的一种非常精练的语言讲话，没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：

(1) αβ1β2…βm

    (2)(θδ1δ2…δn) θδnθδn-1…θδ1θ

在这两种形式中，从左到右均表示解释；从右到左均表示抽象。试写一个魔王解释系统，把他的话解释成人能听懂的话。

基本要求：

用下述两个具体规则和上述规则形式(2)实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写或小写字母代替的变量。魔王语言可含人的词汇。

(1)BtAdA

(2)Asae

测试数据：

B(einxgz)B

解释成 tsaedsaeezegexeneietsaedsae

若将小写字母与汉字建立下表所示对应关系，则魔王说的话是：“天上一个鹅地下一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅”。

将魔王语言自左至右进栈，总是处理栈顶。若是开括号，则逐一出栈，将字母顺序入队，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其它情形较简单，请读者思考应如何处理。应该首先实现栈和队列的基本运算。

选作内容：

(1)实现栈和队列的顺序存储空间共享。

(2)在程序开始运行时读入一组第一种形式的规则，而不是把规则定          死在程序中（第二种形式的规则只能定死在程序中）。

2.3④ 八皇后

问题描述：

    在8×8格的国际象棋棋盘上放置8个皇后，使得任意两个皇后不能互相攻击，即任何行、列或对角线（与水平轴的夹角为450或1350的斜线）上不得有两个或两个以上的皇后。这样的格局称为问题的一个解。写一程序求出所有解。

基本要求：

    写一个递归程序，解决此问题，注意程序尽可能简洁。

测试数据：

    无。也可以按n个皇后问题编程。取n=8作为程序的输入。8皇后问题有92个解。

实现提示：

棋盘可以由一个含有8个元素的一维数组表示，数组元素的值为皇后所在列的列号。注意利用数据结构简化程序结构。输出结果的格式要尽量紧凑。

选作内容：

    通过对问题的分析，利用栈结构直接写出非递归算法。

2.4④ 售票处的服务系统

问题描述：

    设民航售票系统的计算机系统可以为客户提供下列各项服务：

（1）查询航线：根据旅客提出的终点站名输出下列信息：航班号，飞机号，星期几飞行，最后一天航班的日期和余票额。

（2）承办定票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则重新询问客户要求。若需要，可预约登记排队等候。

（3）承办退票业务：根据客户提供的情况（日期、航班），为客户办理退票手续，然后查询该航班是否有人预约登记，首先询问排在第一的客户，若所退票的票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队预约的客户。

基本要求：

    编制便于人机对话的程序，实现上述服务项目。

实现提示：

    每条航线应包含的信息有：终点站名，航班号，飞行日期（星期几），成员定额，余票额，已订票的客户名单（包括姓名、订票额、座位号）和预约登记的客户名单（包括姓名、所需票额）。这里最后两项显然是一个线性表和一个队列。为查询方便，已订票客户的线性表应按客户姓名有序，并且，为插入方便，应以链表作存储结构。由于预约人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登记在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包括上述八个域，其中乘员名单域为指向乘员名单链表的头指针，预约登记客户名单域为分别指向队头和队尾的指针。

选作内容：

    当客户订票要求不能满足时，系统可向客户提供到达同一目的地的其它航线情况。

    读者还可以充分发挥自己的想象力，增加你的系统的功能和其它服务项目。

2.5⑤ 银行业务模拟

问题描述：

    客户业务分为两种。第一种是申请从银行得到一笔资金，即取款和借款，第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应地有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立刻排入第二个队等候，直至满足时才离开银行，否则业务处理完后立刻离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第一个队列中的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者），转而继续接待第一个队列的客户，任何时刻都只开一个窗口。检查不需要时间，营业时间结束时所有客户立即离开银行。

    写一个银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。

基本要求：

    利用动态存储结构实现模拟，即利用系统提供的C标准函数malloc和free。

测试数据：

    一天营业开始时银行拥有的款额为10000（元），营业时间为600（分钟）。其它模拟参数自定。

实现提示：

    事件有两类：到达银行和离开银行。初始时银行现存资金总额为total，开始营业后的第一个事件是客户到达，营业时间从0到closetime。到达事件发生时随机地设置此客户的交易时间和距下一个到达事件之间的时间间隔。每个客户要办理的款额也是随机确定的，用负值和正值分别表示第一类和第二类业务。变量total、closetime以及上述两个随机量的上下界均交互地从终端读入，作为模拟参数。

    两个队列和一个事件均要由动态存储结构实现。注意弄清应该在什么条件下设置离开事件，以及第二个队列用怎样的存储结构实现时可以获得较高的效率。注意：事件是按时间顺序有序的。

选作内容：

    利用静态存储结构实现模拟，即先定义一个可利用结点空间，再用用户自己定义的函数GETNODE和FREENODE实现。

实习三  串

本次实习的目的是熟练掌握串类型基本运算和利用这些运算来实现串的其它各种运算的方法，掌握文本模式匹配方法，熟悉一般文字处理软件的设计方法。

3.1① 串上的运算1

问题描述：

已知串s和t，求所有包含在s中而不包含在t中的字符构成的新串r，以及新串r中每个字符在串s中第一次出现的位置。

基本要求：

(1)利用strcat、strlen、substr和strcmp四种基本运算来实现。

(2)直接在串的顺序存储结构上加以实现。

3.2① 串上的运算2

问题描述：

已知串s和t，编写从串s中删除所有和串t相同的子串的程序。

基本要求：

(1) 利用除index和replace以外的基本运算来实现。

(2) 不利用串的基本运算直接在串的顺序存储结构上加以实现。

3.3① 求串的逆

问题描述：

试利用串的基本运算赋值，联接，求串长，求子串，求出串的逆。

基本要求：

首先在串的顺序存储结构上实现以上串的基本运算，然后分别用递归和递推方法实现求串的逆。

3.4③ 文学研究助手

问题描述：

    文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手” 。

基本要求：

    英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行号，格式自行设计。

测试数据：

    以你的C源程序模拟英文小说，C语言的关键字作为待统计词汇集。

实现提示：

设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。

3.5④ 文本格式化

问题描述：

输入文件中含有待格式化(或称为排版)的文件，它是由一行一行的文字组成的，例如一篇英文文章。每行由一系列被一个或多个空格符隔开的字(一行中不含空格符的最长子串，例如“good!”算一个字)组成，任何完整的字都没有被分割在两行(每行最后一个字与下一行的第一个字之间在逻辑上应该由空格分开)，每行字符数不超过80。除了上述文本类字符之外，还存在着起控制作用的字符：符号“@”指示它后面的正文在格式化时应另起一段排放，即空一行，并在段首缩入8个字符。“@”自成一个字。

一个文本格式化程序可以处理上述输入文件，按照用户指定的版面规格重排版面：实现页内调整、分段、分页等文本处理功能，排版结果存入输出文件中。

试写一个这样的程序。

基本要求：

(1)输出文件中字与字之间只留一个空格符，即实现多个空格符的压缩。

(2)在输出文件中，任何完整的字仍不能分割在两行，行尾不齐没关系，但行首要对齐(即左对齐)。

(3)如果所要求的每页页底所空行数不少于3，则将页号印在页底空行中第二行的中间位置上，否则不印。

(4)版面要求的参数要包含：

●页长(Page Length)------每页内文字(不记页号)的行数。

●页宽(Page Wedth) ------每行内文字所占最大字符数。

●左空白(Left Margin)------每行文字前固定空格数。

●头长(Heading Length)------每页页顶所空行数。

●脚长(Footing Length)------每页页底所空行数(含页号行)。

●起始页号(Starting Page Number) ------首页的页号。

测试数据：

此略。注意在标点后加好空格符。

实现提示：

可以设：左空白数×2+页宽≤160，即行印机最大行宽，从而只要设置这样大的一个行缓冲区就足够了，每加工完一行，就输出一行。

如果输入文件和输出文件不是由程序规定死，而是可由用户指定，则有两种做法：一是象其它参量一样，交互地读入字符数组中；更好的方法是让用户通过命令行指定，具体做法依机器的操作系统而定。

应该首先实现getaword(w)这一操作，把诸如行尾处理，文件尾处理，多余空格的压缩等一系列“低级”事务留给它处理，使系统核心部分集中对付排版要求。

每个参数都可以实现缺省值设置。上述排版参数的缺省值可以分别取56，60，10，5，5和1。

选作内容：

(1)输入文件名和输出文件名要由用户指定。

(2)允许用户指定是否右对齐，即增加一个参量“右对齐否”(Right Justifying) ，缺省值可设为“y”(yes)。右对齐指每一行最后一个字的字尾要对齐，多余的空格要均匀分布在本行中各字之间。

(3)实现字符填充(character stuffing)技术。“@”作为分段控制符之后，了原文中不能有这样的字。现在去掉这一：如果原文中有这样的字，改用两个“@”并列起来表示一个“@”字。当然，如果原文中此符号夹在字中，就不必特殊处理了。

(4)允许用户指定按多栏印出一页。

实习四   数组和广义表

本次实习的目的是熟悉数组和广义表的存储结构的特性及其上的运算，进一步掌握递归算法的设计方法。

4.1① 矩阵相加

问题描述：

已知稀疏矩阵A和B，试编写求A、B相加的算法。

基本要求：

稀疏矩阵A、B均以三元组作为存储结构，另设一个三元组表C存放结果矩阵。

选作内容：

若将稀疏矩阵的非零元素以行优先的顺序存于一维数组中，并用二维数组表示稀疏矩阵中相应元素是否为零元素(以0和1分别表示零元素和非零元素)。例如:

  A= 可用U= 和V= 表示

试在上述表示法中，实现矩阵相加运算。

4.2② 稀疏矩阵的乘法

问题描述：

    稀疏矩阵是指那些多数元素为零的矩阵，利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。写一个以十字链表为存储结构的稀疏矩阵相乘的程序。

基本要求：

    作为相乘因子的两个稀疏矩阵以元素值的形式从终端读入，乘积矩阵则以通常的阵列形式印出。

测试数据：

        ×=

实现提示：

    两个矩阵的行数和列数也要读入。可设矩阵的行数和列数均不超过20。程序可以对三元组的输入序列加以。例如，按行优先。

选作部分：

将乘积矩阵首先以十字链表存储，然后再转化为数组存储结构。

4.3① 稀疏矩阵的运算

问题描述：

实现稀疏矩阵上的如下运算：  

(1) 查找稀疏矩阵上的指定结点。

(2) 修改稀疏矩阵上指定结点的数据值。

(3) 打印稀疏矩阵。

基本要求：

建立稀疏矩阵的十字链表存储结构，并在这个结构上实现上述运算。

4.4① 求马鞍点

问题描述：

    若在矩阵Am×n中存在一个元素aij满足：aij是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。试求出矩阵Am×n中的所有马鞍点。

基本要求：

以二维数组存储矩阵Am×n。

实现提示：

要考虑多个鞍点的情况。

4.5③ 广义表的操作

问题描述：

写一个程序，建立广义表的存储结构，实现以下广义表上的操作。

(1)求广义表的深度；

(2)复制广义表；

(3)判别两个广义表是否相等。

基本要求：

广义表采用单链表示法为存储结构。

实习五  树

    树是一种应用极为广泛的数据结构，本次实习的目的是熟悉树的存储结构及其上的操作，而操作的重点放在树的遍历上（因为遍历操作是其它众多操作的基础）以及如何应用树结构解决具体问题。

5.1① 树的存储

问题描述：

    树有三种常用的表示法:(1)双亲链表表示法 ,(2)孩子链表表示法（带双亲的孩子链表表示法）,(3)孩子兄弟链表表示法。已知其中任意一种表示法即可转化为其它的表示法，试编写程序实现之。

基本要求：

    将一棵树用双亲链表表示法存储起来，并将其转化为：

(1)带双亲的孩子链表表示法

(2)孩子兄弟链表表示法

5.2① 判断二叉树等价

问题描述：

称二叉树T1和T2是等价的：如果T1和T2都是空的二叉树；或者T1和T2的根结点的值相同，并且T1的左子树和T2的左子树是等价的，T1的右子树和T2的右子树是等价的。

试编写算法判断两棵二叉树是否等价。

基本要求：

二叉树以二叉链表作存储结构。

5.3① 二叉树的遍历

问题描述：

    所谓遍历是指沿某条搜索路径周游二叉树，对树中每个结点访问一次且仅一次。试编写按某种遍历方法遍历二叉树的算法。

基本要求：

  二叉树以二叉链表作存储结构，编写非递归的后序遍历二叉树的算法。

实现提示：

    用栈来实现，并且在栈中附设一个标志位，以标志正在访问该结点左子树还是右子树。

选作内容：

(1)在二叉树中查找值为x的结点，并且打印值为x的结点的所有祖先。（可利  用后序遍历的非递归算法，当找到值为x的结点时，打印栈中有关内容）。

(2)假设在二叉链表的结点中增设两个域：双亲域(parent)以指示双亲结点；标志域(mark)以区分在遍历过程中达到该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈的后序遍历算法。

5.4② 构造二叉树

问题描述：

    如果给出二叉树的前序序列和后序序列，则可以构造唯一的一棵二叉树，试编写一算法，根据一棵二叉树的前序序列和中序序列构造该二叉树。

基本要求：

（1）从终端读入二叉树的前序序列和后序序列。

（2）构造出的二叉树存于二叉链表中。

选作内容：

(1)打印出这棵二叉树，打印格式自定，可选用树形表示法、凹入表示法、广义表表示法中的任意一种。

(2)如果给出二叉树的后序序列和中序序列，则也可以构造唯一的一棵二叉树，试编写一算法，根据一棵二叉树的后序序列和中序序列构造该二叉树。

5.5② 求树的高度

问题描述：

一棵二叉树的高度定义为：从二叉树的根结点到所有叶子结点的路径长度的最大值。试编写算法求给定二叉树的高度和其长度等于高度的一条路径。

基本要求：

二叉树以二叉链表作存储结构。要求输出二叉树的高度，并打印出所求路径的结点序列。

5.6④ 哈夫曼编/译码器

问题描述：

    利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。

基本要求：

    一个完整的系统应具有以下功能：

(1)I ：初始化（Initialization）。从终端读入字符集大小n，及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree中。

(2)C：编码（Coding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetrans中的正文进行编码，然后将结果存入Codefile中。

(3)D：译码（Decoding）。利用建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。

(4)P：打印代码文件（print）。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入codeprint中。

(5)T：打印哈夫曼树（Treeprinting）。将已在内存中的哈夫曼树以直观方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。

测试数据：

（1）已知某系统在通讯联络中只可能出现八种字符，其频率分别为0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11,设计其哈夫曼编码。

（2）用下表中给出的字符集和频度的实际统计数据建立哈夫曼树并实现以下报文的编码和译码：“THIS  PROGRAM  IS  MY  FAVORITE”。

（1）用户界面可以设计为“菜单方式”，显示上述功能符号，再加上“E”，表示运行结束End，请用户键入一个选择功能符，此功能执行完毕后，再显示此菜单，直至某次用户选择了“E”为止。

（2）在程序的一次执行过程中，第一次执行I、D或C命令后，哈夫曼树已经在内存了，不必再读入，每次执行中不一定执行I命令，因为文件hfmtree可能早已建好。

实习六  图

图是另一种重要的非线性结构，图上的操作也较树更为复杂，而遍历则是图上众多操作的基础。本次实习要达到熟悉各种存储结构的特性，以及如何应用图结构解决具体问题的目的。

6.1① 判断有向图的两顶点之间是否有路径

问题描述：

试编写程序，判断以邻接表方式表示的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。

基本要求：

(1)利用图的深度优先搜索和广度优先搜索各写一个算法；

(2)要求打印出顶点vi到顶点vj的所有路径。

实现提示：

深度优先搜索和广度优先搜索这两种方法写在一个程序中，用菜单提示是用哪一种方法进行搜索，程序运行直到不想继续搜索时才结束。

选作内容：

（1）求顶点vi和vj之间存在的（简单）路径数目。

（2）求顶点vi和vj之间长度为L的（简单）路径数目。

6.2① 迷宫问题

问题描述：

    迷宫问题描述见教课书P55 例3.3，试采用深度优先策略求解迷宫。

基本要求：

（1）建立迷宫。

（2）查找路径。

（3）打印路径。

     存储结构自定。

6.3③ 求简单回路

问题描述：

试编写一个程序，求无向图中通过某个顶点vk的所有简单回路。

基本要求：

存储结构自定，要求打印出求得的所有路径。

6.4③ 图遍历的演示

问题描述：

很多涉及图上操作的算法都以图的遍历操作为基础。试写一个程序，演示连通的无向图上遍历全部结点的操作。

基本要求：

以邻接表为存储结构，实现连通无向图的深度优先搜索和广度优先搜索遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。

实现提示：

设图的结点不超过30个，每个结点用一个编号表示（如果一个图有N个结点，则它们的编号分别为1，2，……，N）。通过输入图的全部边输入一个图，每条边为一个数对，可以对边的输入顺序作出某种。注意；生成树的边是有向边，端点顺序不能颠倒。

选作内容：

（1）借助于栈类型（自已定义和实现）将深度优先遍历用非递归算法实现。

（2）以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。

（3）图的路经遍历要比结点遍历具有更为广泛的应用。再写一个图的路径遍历算法。

6.5③ 教学计划编制问题

问题描述：

    大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排上必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

基本要求：

（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串），学分和直接先修课的课程号。

（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。

（3）若根据给定的条件问题无解，则报告适当信息；否则将教学计划输出到用户指定的文件中。计划的表格自行设计。

测试数据：

    学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。课程的先修关系如下：

        课程编号     课程名称            先决条件

         C01         程序设计基础理      N0NE

         C02         离散数学            C01

         C03         数据结构            C01，C02

         C04         汇编语言            C01

         C05         语言的设计和分析    C03，C04

         C06         计算机原理          C11

         C07         编译原理            C05，C03

         C08         操作系统            C03，C06

         C09         高等数学            N0NE

         C10         线性代数            C09

         C11         普通物理学          C09

         C12         数值分析            C09，C10，C01

实现提示：

    可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程号与课程之间的对应关系。

选作内容：

    产生多种（例如5种）不同的方案，并使方案之间的差异尽可能地大。

实习七  排序

本次实习的目的是：掌握各种内部排序方法，深刻理解各种排序方法的特点并能灵活应用，能根据实际问题的需要寻找和构造高效的排序算法。

7.1① 二路归并

问题描述:

所谓归并是指将若干个已排序的子文件合并成一个有序的文件。试编写一个二路归并算法。

基本要求：

    首先对初始文件作一遍扫描，找出已经有序的记录序列，用这些子序列作为初始有序子文件，进行两两归并。

选作内容：

 先利用直接插入排序得到较长的有序子文件，然后进行两两归并。

7.2① 起泡排序

问题描述：

试编写双向起泡算法。

基本要求：

相邻两遍向相反方向起泡，第一遍把最小关键字放到当前最头上，第二遍把最大关键字放到当前最后位置。

7.3① 奇偶交换排序

问题描述：

奇偶交换排序过程为：第一趟对所有奇数i，将a[i]和a[i+1]进行比较，若a[i]>a[i+1]，则两者交换；第二趟对所有偶数i，将a[i]和a[i+1]进行比较，若a[i]>a[i+1]，则两者交换；第三趟对奇数i；第四趟对偶数i，…，依次类推直至整个文件有序为止。

基本要求：

试编写一个奇偶交换排序的算法。

7.4① 利用辅助数组排序

问题描述：

当记录本身信息量较大时，为了避免耗费大量的时间移动记录，可利用辅助数组实现排序。

基本要求：

    引入整型向量T[N]作为辅助数组，文件中的每个记录R[i]对应辅助数组T[i]。

(1)排序前令T[i]=i（0≤i(2)按辅助表的次序重排各记录使

        R[0].KEY≤R[1].KEY≤…≤R[N-1].KEY

选作内容：

一个记录在有序文件中的位置，由此文件中比该记录关键字小的记录个数而定。计数排序的思想是：文件中每个记录R[i]对应辅助数组T[i]，T[i]表示在排好序的文件中位于该记录之前的记录个数。试编写算法，确定一个无序文件中每个记录的T[i]值，并根据T[i]的值对无序文件实行物理重排。

7.5① 求竞赛成绩

问题描述：

    某系学生举行英语竞赛，竞赛分三个部分进行：第一部分：文法；第二部分：笔译；第三部分：口语。竞赛的结果按下述原则排列；（1）首先看总分的高低；（2）总分相同者按口语成绩的高低；（3）总分和口语成绩都相同按笔译成绩的高低。试设计一个结构，每个结点存放一个学生的竞赛结果，然后对所有的学生排出各人的名次。

基本要求：

（1）按名次将所有结点排序并输出。

（2）按姓名的字母顺序将所有的结点输出，在结点中给出各人的名次。

（3）用两种不同的排序方法实现。

存储结构自定。

7.6③ 快速排序

问题描述：

试编写快速排序算法。

基本要求：

用非递归的方法编写。

选作内容：

对非递归的快速排序算法进行改写。采用三者取中的规则选取比较基准(即在每一趟划分开始，首先比较第一、最后及中间的三个元素，取三者中的中值作为基准)，并在一次划分后，先对长度较短的部分进行排序，并将另一部分的上、下界入栈保存。

实习八  查找

查找是数据处理中经常使用的一种重要的运算，通过本次实习掌握各种查找方法的特点，并对查找及其相关问题有更深刻的理解。

8.1① 顺序表的查找

问题描述：

    在一已知的非空有序表中查找关键字值为K的记录。

基本要求：

假设表中记录按关键字递增排列，以不带头结点的单循环链表作存储结构，外设两个指针h和t，其中h始终指向关键字最小的结点，t则在表中浮动，其初始位置和h相同，在每次查找之后指向刚查找到的结点。查找算法的策略是：首先将给定值K和t->key进行比较，若相等，则查找成功；否则因K小于或大于t->key而从h所指结点或t所指结点的后继起进行查找。

8.2① 二叉排序树

问题描述：

    建立一棵二叉树，判断其是否为二叉排序树。

基本要求：

二叉树以二叉链表作存储结构，且树中结点的关键字均不同。

选作内容：

求出指定结点在二叉排序树中所在的层次。

8.3② 散列表设计

问题描述：

针对某个集体中人名设计一个散列表，使得平均查找长度不超过R，并完成相应的建表和查表程序。

基本要求：

假设人名为中国人姓名的汉语拼音形式。待填入散列表的人名共有3 0个，取平均查找长度的上限为2。散列函数用除留余数法构造，用伪随机探测再散列法处理冲突。

测试数据：

取读者周围较熟悉的30个人的姓名。

实现提示：

    如果随机函数自行构造，则应先调整好随机函数，使其分布均匀。人名的长度

不超过20个字符。字符的取码方法可直接利用C语言中的ord函数。可先对过长的人名作折叠处理。

选作内容：

（1）从教课书上介绍的几种散列函数构造方法中选出适用者并设计几个不同的散列函数，比较它们的地址冲突率（可以用更大的名字集合作试验）。

（2）研究这30个人名的特点，努力找一个散列函数，使得对于不同的拼音名一定不发生地址冲突。

（3）在散列函数确定的前提下尝试各种不同处理冲突的方法，考查平均查找长度的变化和造好的散列表中关键字的堆积性。

8.4⑤ 图书管理

问题描述：

图书管理基本业务活动包括：对一本书采编入库，清除库存，借阅和归还等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。

基本要求：

(1)每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。

(2)作为演示系统，不必使用文件，全部数据都在内存存放就可以了。但是由于上述四项基本业务活动都是通过书号(即关键字)进行的,所以要用B-树对书号建立索引，以获得高效率。

(3)系统应实现的操作及其功能定义如下：

1采编入库：新购入一种书，经分类和确定书号之后登记到图书帐目中去。如果这种书在帐目中已有，则只将总库存量增加。

2清除库存：某种书已无保存价值，将它从图书帐目中勾销。

3借阅：如果一种书的现存量大于零，则借出一本。登记借阅者的图书证号和归还期限。

4归还：勾销对借阅者的登记，改变该书的现存量。

5显示：以凹入表的形式显示B树。这个操作是为了调试和维护的目的而设置的，打印格式如下例所示：

        对于下列B树                       印为

                                                  60

                                                     30

                                                        20

                                                        50,52

                                                     70,72

                                                        68

                                                        71

                                                        100

测试数据:

入库书号：35  16  18  70  5  50  22  60  13  17  12  45  25

          42  15  90  30  7

然后清除：45  90  50  22  42

其余数据自行设计。由空数开始，每插入删除一个关键字后就显示B树的状态。

实现提示：

(1)B树的查找算法是基础，入库和清除操作都要调用。难点在于删除关键字的算法，因而只要算法对3阶B-树适用就可以了，暂时不必追求高阶B-树也适用的删除算法。

(2)每种书的记录可以用动（或静）态链式结构，并思考各有什么优缺点。

 借阅登记信息可以链接在相应那种书的记录之后。

选作内容：

(1)将一次会话过程(即程序一次运行)中的全部人机对话记入一个日志文件“log”中去。

(2)增加列出某著者全部著作名的操作，思考如何提高这一操作的效率。

(3)增加列出某种书状态的操作。状态信息除了包括这种录的全部信息外还包括最早到期(包括已逾期)的借阅者证号，日期可用整数实现，以求简化。

(4)增加预约借书功能。