数据结构与C语言综合训练实习
61 商店存货管理系统 (1) 初步完成总体设计，建好框架，确定人机对话的界面，确定函数个数； (2) 完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能； (3) 进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。 建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。 分步实施： （1）初步完成总体设计，建好框架，确定人机对话的界面，确定函数个数； （2）完成最低要求：建立一个文件，包括5个种类的货物情况，能对商品信息进行扩充（追 加），修改和删除以及简单的排序； （3）进一步要求：扩充商品数量，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。 输入，统计，排序，查询，信息存储。 四种算法都是前序、中序、后序三种算法要求递归和非递归实现，层遍历用非递归实现。 62 63 运动会分数统计 二叉树遍历算法的实现 64 链表的综合算法设计 设有一职工文件，其结构为：职工号(no)、姓名(name)、部门号(depno)、工资数(salary)、职工号指针(pno)、部门号指针(pdepno)、工资数指针(psalary),设计一程序，从一文件中读取记录到单链表中，并完成如下功能： (1) 输入：添加一个职工记录；(2) 输出：输出全部职工记录； (3) 按no排序：通过pno指针将职工记录按no从小到大链接起来； (4) 按no输出：沿pno链输出全部职工记录； (5) 按depno排序：通过pdepno指针将职工记录按depno从小到大链接起来； (6) 按depno输出：沿pdepno链输出全部职工记录； (7) 按salary排序：通过psalary指针将职工记录按salary从小到大链接起来； (8) 按salary输出：沿psalary链输出全部职工记录； (9) 全清：删除职工文件中的全部记录； (10) 存贮退出：将单链表中的全部结点存贮到职工文件中，然后退出程序运行。 11
数据结构与C语言综合训练实习
设计一个哈希表，实现个人身份证号码查询系统 基本要求： （1） 设每个记录有下列数据项：身份证号码，电话号码、用户名、用户住址； 基于哈希表的身份证查询（2） 从键盘输入各记录，分别以身份证号码和用户名为关键字建立哈希表； 系统的设计与实现 a) 设计不同的哈希函数，比较冲突率； b) 在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度 的变化。 （3） 查找并显示给定电话号码/用户名的记录。 基本要求： （1）对一个描述工程的AOE网，建立其存储结构；（注：数据的输入可以是键盘输入或文件输入两种方式） 65 66 关键路径问题 （2）判断该AOE网是否能够顺利进行。 （3）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。（注：结果的输出可以是屏幕输出和文件输出两种方式） 问题描述：一个邮递员从邮局选好邮件去投递，然后回到邮局。当然他必须经过他所管辖的每条街至少一次。请为他设计一条投递路线，使其所行的路程尽可能地短。 基本要求： 67 邮路问题 （1）设计邮递员的辖区，并将其抽象成图结构进行表示，建立其存储结构。 (注：数据输入 可以是键盘输入和文件输入两种方式) （2）按照输入邮局所在位置，为邮递员设计一条最佳投递路线，要能考虑到辖区一般情况。 （3）界面要求：有合理的提示和人机交互。 12
数据结构与C语言综合训练实习
68 n元多项式乘法 要求： (1) 界面友好，函数功能要划分好 (2) 总体设计应画一流程图 (3) 程序要加必要的注释 (4) 要提供程序测试方案 (5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 问题描述：文件是管理用户信息和应用程序的一种工具。每个文件有唯一的文件名，可以通过文件名访问文件，同时可对文件进行生成、删除及文件名修改等操作。文件系统对若干文件进行管理时将所有的文件目录组合在一起构成一个目录文件。通过对目录文件的管理达到“按名存取”的目的，目录文件常采用的组织结构是树型目录结构。 基本要求： 函数功能要划分好，程序要有必要的注释。 用户通过界面菜单选择以下操作： （1） 生成文件，选择路径和文件名，实现对文件的生成。 （2） 删除文件，对指定文件进行删除操作。 （3） 修改文件，对指定文件进行内容修改或者文件名修改。 （4） 输出该目录结构。 给定简单的算术表达式，包括加减乘除括号这几种运算操作符，请计算表达式的值。 (1)能够正确处理加减乘除这四种运算； (2)能够正确处理括号运算； 实现提示： 首先将算术表达式转化成逆波兰式，然后针对逆波兰式进行运算。 布线区域分成m?n的方格阵列。要求确定连接方格s到方格d的最短布线方案。布线的时候， 电路只能沿着直线或者直角布线，有障碍的方格做了封锁标记（X），其他线路不允许穿过被 69 文件目录管理系统 70 简单算术表达式运算 71 机器人布线 13
数据结构与C语言综合训练实习
封锁的方格。 (1)用文件保存布线区域，用1、0分别表示某个格子是否有障碍；S,D表示起点和终点； (2)给出最短的布线路径长度； (3)用文件保存布线路径，用*表示布线的方格。 开发计算两个字符串间的编辑距离，LCS距离和N-gram距离的函数。 （1）编辑距离 字符串a和b的编辑距离ED(i,j)表示把字符串a转换成b所需要的最少操作次数，这些操作 可以是：插入一个字符，删除一个字符，替换一个字符。显然，ED(i,j)越小，a，b越相似。ED(i,j)可按下列公式计算： 72 字符串距离 14
数据结构与C语言综合训练实习
ED(0,0)?0ED(0,i)?ED(i,0)?i?ED(i?1,j?1)ED(i,j)???1?MIN(ED(i?1,j),ED(i,j?1),ED(i?1,j?1))（2）LCS相似度 字符串a和b的LCS(Longest Common Subsequence)相似度是a和b间的最大相同子串的长度。显然LCS(i,j)越大，a，b越相似。a，b的LCS相似度定义如下： ai?bjai?bji?0或j?0?0?LCS(i,j)??1?LCS(i?1,j?1)ai?bj?MAX(LCS(i?1,j),LCS(i,j?1))ai?bj?（3）N-gram相似度 设Ngram(a) 是字符串a中长度为N的子串的集合。两个字符串a,b的N-gram相似度NG(a,b)定义如下： NG(a,b)?Ngram(a)?Ngram(b)Ngram(a)?Ngram(b)73 字符串操作 NG(a,b)越大，字符串a，b越相似。 编写程序，不使用标准库函数，实现字符串的拷贝、拼接、字串查找、长度计算等函数。 (1)在不使用相关的标准库函数的情况下，完成本任务； (2)实现两个字符串拼接的函数strcat(str1, str2)； (3)实现字符串拷贝的函数strcpy(str1,str2)； (4)实现字符串查找的函数strcstr(str1,str2)； (5)实现字符串长度计算的函数strlen(str1)； 15