“数据结构”上机作业
1，上机时间：星期一晚11-12节（7-9点），计算中心4、5、6微机室，第3周开始。必须参加（登记考勤）
2，上机作业应按时独立完成，在本次作业的截止日期之前交给你的辅导老师。 超过截止日期一周以内时按照本次作业的50％计入成绩，超过日期一周以上不计成绩。
3，把程序通过email附件的方式提交给你的辅导老师，文件命名方式：m0130201.c 表示05级学号013的同学的第2次作业的第1个c文件。余类推。其他年级同学的文件第一个字母用x，其余字母的编码方式同上。
4，平时作业和上机在课程的最终成绩中占30％。

注意：上机程序作业必须通过编译和运行，否则作为没有完成的作业，由辅导老师酌情处理。

注意：相关页中有书上实例代码，请直接使用它们，不必重新输入。
序号 布置日期 截止日期 作业内容
7 11.23 11.29 必做题：（上次的选做题）教科书208页上机题：
1）实现一个采用拉练法的散列表，存储学生姓名和学号，以姓名作为关键码。
2）写一个主函数，读入学生信息文件（例如下面的本课程学生文件），把信息存入你实现的散列表，最后按散列桶的顺序打印出学生名单。
3）这里是本次课程的学生信息列表。

选做题：1，写一个函数，它能判断任何保存整数作为数据的二叉树是否二叉排序树。 2，写一个函数，它能判断任何一棵二叉树是否平衡。
3，在书上二叉排序树的基础上，实现一种关键码和数据信息都是任意长的字符串的二叉排序树。实现一个程序，它以你所实现的二叉排序树为基础，读入一个HTML网页，提取出其中的链接信息存入二叉排序树（以网页里的链接作为关键码，相应的文字内容作为数据。或者反过来，以文字内容作为索引，以链接作为值），最后按顺序打印输出有关信息。（下载一些复杂的网页试验你的程序）

6 11.16 11.22 必做题：
给书上链接表示的二叉树（假定树结点中保存的是 int）增加下面操作（请试试同时写出几个函数的递归定义和非递归定义，体会一下其中的问题）：
1，写一个函数计算二叉树的深度；
2，写一个函数，从左到右输出二叉树的所有叶结点的整数值；
3，写一个函数，计算出二叉树中所有结点的整数之和；
4，写一个主函数，首先构造一棵至少包含10个结点的链接二叉树，而后调用你定义的函数，输出各计算结果。

156页上机题第2题。假定程序的输入（通过标准输入或者指定文件）形式为：
a 3 b 12 c 2 d 31 e 6 f 13 ...
（字符及其出现频度），你的程序应能输出每个字符的Huffman编码。

选做题
再增加其他二叉树操作，例如：
1，计算二叉树中的结点个数；
2，计算出二叉树中所有结点的整数乘以结点的层数加1得到的值之和；
3，比较两棵二叉树是否相同；
4，比较两棵二叉树是否具有相同的边缘（叶结点按顺序相同）；等等。

实现一个链接字典，其中保存本次上课的学生记录（学号和姓名），把下面操作实现为独立函数：

  • 读入文件建立字典的函数
  • 通过学号检索
  • 通过姓名检索
  • 插入学生记录
  • 根据学号删除学生记录
  • 根据姓名删除学生记录
  • 打印操作，按学号顺序打印链表字典里的各个记录
  • 实现一个主函数，实现一个简单的学生管理系统
这里是本课程的学生记录文件。
5 11.2 请首先做课程项目实习题。如果有空闲时间可以考虑下面选做题：

选做题
1，设输入里有三种括号：{, }, [, ], (, )，请写一个程序，它能检查输入里的括号是否正确配对。请试用这个程序检查 C 源程序里的括号是否配对。

2，扩充上题的程序，使它可以检查 C 程序里的括号配对问题，注意不同部分之间的相互影响（注释、字符串、字符）。如果有时间，可以增加对 C 语言里的其他“括号”的处理。

3，队列常被用于做服务模拟。假定某银行对一个储蓄所做了调查统计，总结出顾客到达的时间间隔在1分钟到3分钟之间，每个人的业务需要1分钟到10分钟。假定银行有3个队列，顾客到银行后总排入当时最短的队列。

  • 请设法模拟一个工作日（8小时，480分钟），统计顾客的平均站队时间和在银行的总滞留时间。（模拟中应该用随机数生成函数，生成顾客的到来和业务时间）
  • 银行计划改进工作方式，采用叫号取号方式。同样条件下顾客能得到更好的服务吗？
  • 请改进你的模拟程序，使它容易适应问题中各种条件的修改。
4 10.19 10.25 必做题：
实现一个简单的后缀表达式计算器。假定表达式里的基本数值为实数，可用的运算符包括+,-,*,/,^，其中的 ^ 表示求幂运算。
1，你可以假定输入表达式里的数和运算符之间都有空格，这样可以简化输入的处理；
2，输入的算术表达式以分号为结束符。你的计算器应该能输入并计算一系列表达式，遇到一行的第一个字符就是分号时程序结束。

下面是有关实现程序输入的一些建议：
1，你可以考虑用 scanf 直接读入表达式里的数，也可考虑用读入一个个字符的方式输入（例如用getchar）。标准库 stdlib.h 里的函数 double atof(const char *) 能把表示实数的字符串转换为 double。（这个函数也不难自己实现）
2，标准库函数 ungetc(int c, FILE* s) 可用于把字符 c 退还输入流 s。你也可以考虑把一个完整的输入行读入一个字符数组（用gets）而后再用 sscanf 从数组中读入数值和运算符的方式。

这里有一些简单测试实例

选做题：
一，上题的扩充：
1，给计算器增加一元函数功能，允许表达式里写 sin, asin, tan, log（自然对数）等，还可以考虑加入 C 语言提供的各种数学函数。再加上“函数” minus 表示求负。还可以参考下题做进一步的扩充。

二，参考上题，实现一个计算中缀表达式的计算器。可以考虑如下扩充：
1，增加计算结果记录功能，允许在后续表达式里用 #n 表示第 n 个表达式的结果。
2，考虑如何增加“程序变量”和赋值（允许把计算结果赋给这种变量）。
3，修改程序的输入功能，允许比较自由的格式（例如各项之间可以没有空格）。
4，继续做一些扩充，你就实现了一个小的计算器语言和它的一个解释器。

三，编写求解8皇后问题（101页习题7）的程序。

3 10.12 10.18 必做题：
参考课堂介绍的“动态顺序表”定义一种动态的顺序字符串类型，提供下面操作（C语言库函数 strlen，strcpy 等可能有用，也可以完全不用它们）：
1，实现两个函数，它们分别创建空串，以及创建用C语言字符串初始化的串
2，实现连接两个串的函数 concat（这个函数构造一个新字符串，其内容是原来的两个串的拼接），以及将字符串内容翻转的函数 reverse
3，在一个串的后面直接拼接上另一个串的内容，必要时扩大原来第一个串的存储
3，实现朴素算法的子串匹配函数
4，请定义一个主函数，其中调用你实现的串函数构造出包含100个 PekingUniversity 的字符串。打印这个大字符串。而后找出子串 ing 在其中出现的各个位置并打印它们（修改你的子串匹配函数，使之可以指定一个开始匹配位置，以便能用于做一系列匹配）。翻转前面构造出的大字符串，找出子串 revin 在翻转后的串里出现的所有位置并输出。（把上述这些做成一个完整的C程序）

选做题：（如果想处理较多的数据，请考虑使用VC或者其他新的C/C++系统）
1，为你的字符串类型扩充一些有用操作。若想进一步了解字符串的有用操作，可参考C语言标准库的<string.h>和C++语言标准库的字符串类型。
2，考虑如何给你的字符串类型增加快速匹配算法（自己看书，下节课讨论）。
3，实现一个字符串模式类型（在基本字符串类型的基础上扩充一个next数组成分），修改快速字符串匹配算法，使之用这种模式类型与字符串匹配，并为匹配函数增加一个起始位置参数，实现“在字符串 t 里找出位置 b 之后的第一个与 p 的匹配”。
4，做一些试验，考察两种匹配算法的效率（例如在一些实际文本里查找各种字符串；下载一些网页，在其中查找字符串）。
5，在有关书籍或者互联网上找 Boyer-Moore 的字符串匹配算法，根据该算法为你的字符串类实现另一个匹配函数并做一些试验。设法查找并阅读一些其他串匹配算法及其实现的文献材料（有专门的著作）。

2 9.28 10.11 必做题：参考单链表的程序，实现一个带头尾指针的以整数为元素的双向链表数据结构，并增加如下操作：（数据类型定义）
1，insertOrder(PDLinkList l, DataType x)，它把元素 x 插入表中第一个大于 x 的元素之前。
2，在表的最前和最后插入元素的函数 insert_front 和 insert_back。
3，写一个主函数检测上述数据结构，其中用到你实现的一些函数。程序中加入必要说明，说明它完成了什么工作。
请把定义的类型和相关函数放入一个C文件，把你的主函数也放在这个文件里，形成一个完整程序。上交的程序一定要经过编译和运行，否则就是没有完成作业。

选做题
用书中的顺序表、单链表和你实现的双链表做下述试验，比较它们的性能：
1，向表中顺序插入30000个元素（如果时间太短不好比较，就插入更多元素。但TC下要插入更多元素需要换编译模式，否则空间就会用完）；
2，向表中随机的位置插入30000个元素；（注意生成合法的表元素下标）
3，从30000个元素的表中随机的位置删除元素，直至把表删空。
自己设计一些其他试验，并分析试验的结果。

4，基于双链表实现 Josephus 问题的求解程序。其中每次计数时投一个骰子，决定是向前数还是向后数。

1 9.21 9.29 请在程序中加入必要的注释，说明它们完成的工作。

必做题：

  1. 为顺序表的实现扩充在表的最后插入/删除元素的函数 backinsert_seq(PSeqList, DataType) 和 backdelete_seq(PSeqList)。
    定义 print_list (...) 函数，它打印顺序表的全部元素（假定元素是 int）。
    写一个主函数，其中建立一个以整数为元素的顺序表，用上述后端插入函数在顺序表里加入20组1、2、3（交替加入），然后调用 print_list 打印表的内容。再调用 backdelete_seq 从表里删除 30 个元素，再打印表的内容。
  2. 请定义在顺序表最前面插入删除元素的函数。并完成与上一题类似的工作。
  3. 实现函数insertOrder(PSeqList l, DataType x)，它把元素 x 插入表中的第一个大于 x 的元素之前。
    实现一个主函数，其中建立一个以整数为元素的顺序表，调用 insertOrder 将生成的 100 个随机整数插入表里，最后打印表内容（用 print_list）。
选做题
1，定义生成包含 n 个随机整数的顺序表的函数。
2，请考虑基于顺序表实现“集合”抽象数据类型，定义出“集合”的数据表示和操作集合并实现之。
本页及相关页面（除另声明者外）由裘宗燕创建维护，可自由用于各种学习活动。其他使用需得到作者许可。