数据结构与算法课程实习讲义2011-2012学年第二学期林士玮、闫季鸿计算机与信息学院电子商务系2012.05目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc201560019"数据结构与算法课程实习要求与内容PAGEREF_Toc201560019\h1HYPERLINK\l"_Toc201560020"第一章线性表功能程序组PAGEREF_Toc201560020\h3HYPERLINK\l"_Toc201560021"1．静态线性表功能程序组的编制与测试PAGEREF_Toc201560021\h3HYPERLINK\l"_Toc201560022"2．动态线性表功能程序组的编制与测试PAGEREF_Toc201560022\h7HYPERLINK\l"_Toc201560023"第二章队列功能程序组PAGEREF_Toc201560023\h11HYPERLINK\l"_Toc201560024"第三章栈功能程序组PAGEREF_Toc201560024\h14HYPERLINK\l"_Toc201560025"第四章二叉树的功能程序组PAGEREF_Toc201560025\h17HYPERLINK\l"_Toc201560026"第五章线性表、栈和队列的应用PAGEREF_Toc201560026\h21HYPERLINK\l"_Toc201560027"1.线性表的应用----排序实现、航班信息的查询与检索PAGEREF_Toc201560027\h21HYPERLINK\l"_Toc201560028"2.栈与递归----猴子吃桃问题、汉诺塔问题PAGEREF_Toc201560028\h24HYPERLINK\l"_Toc201560029"3.栈的应用实例----括号匹配、数制转换、表达式求值等PAGEREF_Toc201560029\h25HYPERLINK\l"_Toc201560030"4.队列的应用实例----舞伴问题PAGEREF_Toc201560030\h27HYPERLINK\l"_Toc201560031"5.栈和队列的综合应用PAGEREF_Toc201560031\h28数据结构与算法课程实习要求与内容一、课程基本要求（一）能较熟练地编写有关线性表、栈、队列和二叉树等基本功能程序。（二）能运用线性表、队列、栈等基本功能程序，设计并实现简单的应用程序。（三）掌握程序调试的一般方法。二、课程内容（一）基本算法训练静态线性表功能程序组的编制与测试建立、输出、插入、查找、删除、求长度等动态链表功能程序组的编制与测试头插法、尾插法建立有头节点和无头节点的链表链表输出、插入、查找、删除、求长度等栈功能程序组的编制与测试；初始化、入栈、出栈、判空等队列功能程序组的编制与测试；初始化、入队、出队、判空等二叉树功能程序组的编制与测试用先序法构造二叉树实现对二叉树的广义表和凹入表表示法实现对二叉树的前序、中序、后序遍历求出二叉树的节点总数和叶子总数交换二叉树的左右子树二叉排序树生成、查找、删除结点（适用各种位置的结点）（选做）生成赫夫曼树（选做）重点：通过基本算法训练，加深对《数据结构与算法》中基本算法的理解，提高编程能力。难点：动态地址分配与指针操作。（二）线性表、栈和队列的应用1．线性表的应用排序实现直接插入二分插入冒泡排序快速排序直接选择排序希尔排序（选做）根堆排序（选做）归并排序（选做）航班信息的查询与检索（选做）2．栈与递归猴子吃桃问题汉诺塔问题（选做）3．栈的应用实例括号匹配数制转换表达式求值（选做）4．队列的应用实例舞伴问题5．提高应用图书馆借书、还书、查询与入库（选做）《停车场管理》应用程序（选做）重点：提供完整的设计文档，文档应包含需求分析、概要设计、调试分析、用户手册以及源程序等内容。线性表功能程序组1．静态线性表功能程序组的编制与测试设计要求使用数组存储线性表中的元素值实现静态线性表的初始化、查找、插入、删除、判空与更新等功能。设计分析把所有的文件放在SeqInterFace包中。定义好的接口文件SeqInterface.java的代码在下文中。定义数据类型：代表线性表的类名为：Seq，注意大小写。实现SeqInterface.java中所有的函数说明