数据结构上的实习资料

教育信息化2.0行动计划

)1)根据每次实习的要求选定题目。

)2)分析主题要求，明确实现的功能。 数据结构设计； 基于面向对象的确定了编程方法、算法的基本思想、主要模块、各模块的功能和调用关系，并用c语言细化主要算法。(3)编写上层程序，进行静态检查，产生程序中的逻辑错误和语法将错误减少到最小限度。

)4)准备测试数据，考虑调试手段，上程序； 当程序通过时，打印源程序列表和测试数据的执行结果。)5)最后编写调试分析报告和使用说明书，完成完整的实习报告。实习报告的内容实习的主题和要求包括主题和功能要求双需求分析

包括问题说明、系统环境、运用要求等三概要设计

包括数据结构和存储结构的设计、算法设计、模块设计等四详细设计包括类的函数和数据成员设计、接口设计以及其他模块设置计划和实现5调试分析

调试过程中遇到的主要问题是如何解决的； 设计和编码的次数回顾讨论和分析算法的时间和空间复杂性分析算法的演变步骤改善等。六使用说明书

使用说明主要说明你的程序的使用方法和使用时的注意事项。七测试结果

如果主题规定了测试数据，则结果将包括这些测试数据和运输行输出当然也可以包含其他测试数据及其执行输出()测试数据)。八源程序列表

在源程序中添加必要的注释。实习一线性表，堆叠和队列和APP应用任意问题1、一元稀疏多项式运算器【问题的说明】

设计一元稀疏多项式的简单计算机。【基本要求】(1)输入并创建两个多项式。

)2)把多项式a和b相加，形成和多项式c。)3)减去多项式a和b，生成差多项式d；)输出多项式a、b、c、d。 输出形式：例如多项式a为：

a(x )=c1xe1 c2xe2 … cmxem，其中ci和ei分别表示第I项的系数和指数，还有各项都是按指数的乘方排列的。 即，0e1<； e2<； …<； em。【测试数据】

(1) (1 x x2 x3 x4 x5 ) ) (-x3-x4 )=(1xx2x5) ) ) ) )。(2) x X100 (X100 x200 )=) x2x100 x200 )(3) ) 2x 5x

8-3x11 ) (7-5x8 11x9) ) ) )=(7 2x 11x9-3x11 ) ) )。(4) 6x-3- x4.4x2- 1.2x9(-(-6x-34.4 x 27.8 x 15 ) )。=(12x-3-x-1.2x9-7.8x15 )【实现提示】

(1)用起始节点的单链表容纳多项式。

)2)每个多项式链表只存储非零系数项目。 多项式a和b中的指数在加/减以下两项后，如果系数为零，则该项不存储在和/差多项式c中指数项。【扩大内容】

计算机的模拟界面。

教育信息化工作管理系统

累积运算的中间结果和最终计算结果的数据类型要求整数型——。 这是问题本身的要求。尝试设计合适的存储结构，对每个元素或节点要求最多的存储的3位数值。)2)数据操作及其实现：

要基于设计的记忆结构实现乘法操作，需要从键盘输入n值； 在画面上显示最终的计算结果。【测试数据】

(1) n=20，n！=2432902008176640000

)2) n=30，n！=2652528598121910586363084800000【实现提示】(1)设计数据存储结构：

阶乘运算的正确性和实体数据表示的不正确性，本

问题是不能用实数型表示累积运算的中间结果和最终的计算结果。只能使用整数。 但是，可以用普通整数型和长整数型表示的数的范围受其字长的限制，无法表示大数阶乘的累积结果，因此是必须的例如，通过设计适当的数据结构来存储数据个元素或节点存储数据的若干位值。

从问题的说明中可以看出，n的值是任意的值，所以尽量不限制程序系统应采用动态存储结构。)2)要实现两个数的乘法运算，需要考虑以下事项：乘数的每一位必须与被乘数相乘乘法运算中的进位问题及其实现。元素或节点存储最多三位数的数据值节点中的数字大于999，因此必须进位到上一个元素或节点。3、表达式后缀显示【问题的说明】

表达式包含运算对象、运算符、括号等，并习惯性地使用前缀表示运算符夹在两个运算符对象之间。 计算公式的值与运算符的优先级级别有关，例如先乘除后加减。 包含在对中圆括号内的子表达式必须首先计算，因此可以将其视为特殊表达式运算符。 享有最高优先权。 括号可以任意嵌套。 也就是说左括号后跟表达式，形成表达式的递归定义。 为了直接指示表达式中每个运算对象的首选计算顺序，以允许表达式中的骑马钉将形式转换为后缀(指运算符放在二运算对象之后)形式。 范例例如，式a*b-(cd )/e为通常骑马订形式，其后缀为ab*cd e/-，括号以后缀的形式消失。设计一个转换程序，将输入的表达式之一转换为相应的后缀形式在表达式之后输出。【基本要求】

为了简单起见，假设运算对象只包含变量，每个变量名称只有一个字符表示； 运算符只包含、*、/和括号。 表达式是分号“； ’结束。 在转换过程中，需要进行必要的语法检查，如括号是否配对、单词等是否合法等。必须为转换程序分别创建非递归和递归算法。【测试数据】

(1) A*B*C

)2) AB*(C-D )-e/f

(3) A B ) de/) fa*d ) c实习二叉树和二叉树和APP应用程序任意问题

1、实现Windows资源管理器【问题的说明】

Windows资源管理器是用于管理计算机资源的窗口，用于管理电气大脑中的所有文件都在资源管理器中，在资源管中在资源管理器中查看文件夹的层次结构时，可以利用资源管理器快速前进使用行文件和文件夹。 例如磁盘(根)、目录、不同的类类型的文件。这里，文件信息包括文件名、类型、创建时间和文件大小等等； 磁盘信息包括磁盘名称、总大小、可用空间等。 目录信信息包括目录名称、修改日期、大小、对象数量等。

中小学学科教学资源微课汇总

(6)使当前目录成为当前目录的上一个目录，即目录以树形式输出当前目录下的文件和文件夹信息，统计目录数量和文件数量)7)模糊地检索目录/文件信息，并显示检索结果(8)撤销1个资源管理器

2、遍历树

【问题的说明】

)1)具有n个节点的有根树，节点标记为1到n，不同点标签不同。 对于各个节点，求出其子孙节点中有多少个节点的标签小于其标签。)2)因为知道一棵树的边长，所以有多少对节点的距离在k以下，可以定制k的值或构建自己的树。【扩展内容】从具有n个节点的树和边上定义的权重w中，选择最高的

节点多p个的集合s。 定义d[i]=min{dis[i，j]，j为s中的节点}、给定的d [1] d [2]……为了使d [ n ]最小，要求这样的s。3、确定唯一二叉树【问题的说明】

给定横切二叉树的前序序列和中序序列，可以构成如下唯一的二叉树。 尝试编写实现上述功能的程序。【基本要求】知道一棵二叉树的前序和中序序列，原型设计完成了以下任务之一个算法：

(1)建立二叉树

)2)证明结构是正确的)，即按前序和中序分别扫描该树，即可得到结果与给定序列进行比较)。)3)对该二叉树进行后相遍历，输出后相遍历序列。(4)用凹法输出该二叉树。【测试数据】

(1)前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC)2)前序排列为-AB C/D-e，中序排列为a bcd/e。【扩大内容】众所周知，后序和中序序列构成二叉树。实习3检索与应用

任意问题

1、实现词典检索【问题的说明】

采用块搜索、双叉搜索树搜索、散列表搜索等不同的检索方法实现词典的检索，进行不同的分析提高检索方法的效率，统计检索所需的时间。2、电话号码查询系统【问题的说明】

设计散列表实现电话号码查询系统。【基本要求】(1)假设每条记录有以下数据项。电话号码、用户名、地址)2)通过键盘输入各条记录，分别以电话号码和用户名为键单词列表的制作；)3)用适当的方法解决冲突

)4)检索并显示指定的电话号码记录)5)检索并显示指定用户名的记录。【实现提示】

构建散列函数时，请注意确保分布均匀。 用户名的所有长度20个字符以下。 字符的代码取法可以直接使用ord函数。 好的先折叠处理过长的用户名。【选择内容】

)1)从几种散列函数构造方法中选择适用者，设计一些节点的哈希函数与它们的地址冲突率进行比较。)2)以散列函数确定为前提，尝试各种处理的冲突的方法比较平均查找长度的变化。实习四图及其应用任意问题

1、求有向连通图的生成树【问题的说明】

为了在n个城市之间建设通信网络，架设n-1路径即可很好。 如何以最低的经济成本建设这个通信网，就是网的最小生成树问题。【基本要求】

)1)采用克鲁斯卡尔算法求解网络最小生成树，其中教科书的等价类表示构建生成树过程中的连通分量。)2)用预算法求解网络最小生成树。(3)将生成树内的各边及其权重作为文本文件输出。2、遍历图

有一个长方形的房间，房间里的地面覆盖着正方形瓷砖，瓷砖是红色或黑色的。 一个人站在其中在黑色的瓷砖上，他可以移动到周围的瓷砖上，但不能如果移动到红色瓷砖上，只能在黑色瓷砖上移动的话，他会到达这个房间的黑色瓷砖数量是多少？【测试数据】

输入的测试数据应该是两个整数w和h，分别表示这一点房间中x和y方向的瓷砖数量。 可以选择适当的符号层代代替黑色瓷砖和红色瓷砖，例如“#”表示黑色瓷砖，“*”表示红色瓷砖瓷砖，“@”表示该位置的黑色瓷砖，此时人站在上面。 注意味着每个测试数据只有一个“@”符号。 输出数据来自初始位设置的黑瓷砖经过最后位置的黑瓷砖数。