DS实习指导.docVIP

《数据结构》上机实习指导书 上机实习是对学生的一种全面综合训练，是与课堂听讲、自学和练习薄相辅相成的必不可少的一个教学环节。一般而言，实习题中的问题比平时的习题集复杂得多，也更接近实际。实习着眼于原理与应用的结合。使学生学会如何把所学用于解决实际问题，培养软件工作所需的动手能力，又能帮助学生深化理解和灵活掌握教学内容。 实习步骤 问题分析和任务定义。即明确问题要求什么，限制条件是什么。 数据类型和系统设计。分概要设计和详细设计两步实现。 编码实现和静态检查。编码实现即关于问题的源代码，静态检查即人工检查。 上机准备和上机调试。 总结和整理实习报告。 实习报告规范 实习报告开头应写明题目、班级、姓名、学号、完成曰期。实习报告应包括： 需求分析 概要设计 详细设计 调试分析 测试结果 三、实习内容 实验一：合并线性表 问题描述：对采用顺序存储结构的两个线性表予以合并，结果表中应无重复元素。 基本要求：可采用静态分配的存储结构，元素类型为int或char,线性表为随机输入获得，学生应掌握其算法思想，并编写能上机可执行程序，所用语言为C语言。并提交实验报告。 测试数据：A={1,22,7,5,6},B={5,7,90,11,2,35,98}; A={u,r,t,w,m,I},B={I,u,y,r,e}; A={u,9,3,I,} ,B={U,0,u,I}； 再自行输入若干组测试数据。 实现提示： 1、定义两个数组，为节省空间，第一个数组可适当大，可作结果数组； 2、把第二个数组中的元素与第一个数组中元素逐个比较，没有相同的插入。 选作内容：元素为结构体类型。 实验二：创建链表 问题描述：创建一个线性链表，元素用结点存储，必要时可增加头结点；实现其插入、删除、查找等操作。 基本要求：采用动态分配申请内存，按线性表的元素逻辑顺序予以链接，然后在链表中实现在任意位置的元素插入和删除，以及查找某一已知元素，返回其位序。 测试数据：设有一图书目录，其每一条记录包含有书名、编号等字段，用链表实现其存储、添加，删除等，以实现目录的更新。 实现提示： 定义结点类型； 用malloc()申请内存，构造一个结点，其地址为链表的头指针；重复以上操作以构造链表。查找操作位置，修改指针以实现插入和删除。 实验三：栈的应用 问题描述：设有一任意十进制整数，要求将其转换成任意进制数。 基本要求：用栈存储结果数的诸位，利用栈的操作方式以获得正确结果，所有转换用一个函数实现。 测试数据： 将768转换成二进制数； 将2345转换成八进制数； 将来8865转换成十六进数。 实现提示：将十进制数M转换成N进制数，是将M不断除N取余，依次获得结果数的低位至高位，直至商为0；利用栈的操作方式，恰能得到结果的高位至低位。其中转换成十六进制数应注意字符的转换。 选作内容： 1、思考栈的空间应为多大合适？ 2、用链栈实现。 实验四：串的连接 问题描述：对随机输入的两个串，实现其连接，并能在串中查找子串、返回子串的位序。 基本要求：采用定长顺序的存储结构，数组的零号分量存储串的长度，串的实际内容存储在第一号分量及以后的单元中，按串的连接方式返回结果；并能在已知串中能正确求得子串的位置。 测试数据：从终端随机输入。 实现提示：定义二个char型数组，存储两个串，将其长度存储在零号分量中，将第二个串连接在第个串后面。值得注意的是：当两个串的长度大于结果数组的长度时，应采用“截断”。 为节省内存空间，可将其中一个数组作为结果数组。 选作内容： 这种存储结构最多能存储多少个字符？ 实现串的插入、删除等，进而编写一系统服务程序，其功能类似记事本。 实验五：树的操行 问题描述：对于一二叉树，实现查找其双亲结点、孩子结点，并能输出其中序遍历结果。 基本要求：所用存储结构为顺序存储结构，建二叉树，每个结点的序号为其对应的二叉树的编号，根据随机选取的序号，求得其双亲及孩子。并能返回遍历结果。 测试数据：随机选取各种二叉树。 实现提示：顺序存储树的建树相对较容易，实现遍历却较抽象，可采用递归和非递归两种算法，但从根本上说，其思想都是递归。另外，用顺序存储，结点i的双亲为i/2,孩子为2*i及2*i+1。 选作内容：1、顺序存储结构有什么缺点？ 2、先序和后序遍历树。 实验六：树的遍历 问题描述：对于给定的一二叉树，实现各种约定的遍历。 基本要求：二叉树采用链式存储，实现其非递归遍历。应包括创建二叉树、遍历二叉树。 测试数据：随机选取各种二叉树。 实现提示：采用先序建树，动态获得内存，然后根据递归的思想建递归工作栈，以更深刻理解树的遍历和递归的具体进程。 选作内容： 与顺序存储结构相比较，二叉链表有何优点？ 对二叉树线索化，对求遍历顺