《程序技术基础》实验报告.doc

程序技术基础课程实验指导课程代码：070050 开课学期：4开课专业：信管类总学时/实验学时：64/32总学分/实验学分：4/2一、课程简介数据结构是计算机各专业的重要技术基础课。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。二、实验的地位、作用和目的数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。三、报告与考核每个实验都要求学生根据上机内容写出实验报告，报告要求包括以下七个方面的内容：1实验目的；2实验内容；3实验要求；4算法设计；5详细程序清单；6程序运行结果；7实验心得体会。目录实验一 顺序表的操作实验3实验二 链表的操作实验6实验三 栈和队列的操作实验8实验四 二叉树的遍历实验11实验五 二叉排序树的查找操作14实验六 图的操作实验16实验七 查找操作实验18实验八 排序操作实验21实验一 顺序表的操作实验一、实验名称和性质所属课程数据结构实验名称顺序表的操作实验学时4实验性质验证 综合 设计必做/选做必做 选做二、实验目的1掌握线性表的顺序存储结构的表示和实现方法。2掌握顺序表基本操作的算法实现。3了解顺序表的应用。三、实验内容1建立顺序表。2在顺序表上实现插入、删除和查找操作（验证性内容）。3删除有序顺序表中的重复元素（设计性内容）。4完成一个简单学生成绩管理系统的设计（应用性设计内容）。七、设计性实验编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。1. 实验要求 根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。 删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。2. 核心算法提示要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第0个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。3. 核心算法描述/ 删除有序顺序表L中的所有重复元素，即使得有序顺序表中相同的元素只保留一个public static void remove_repeat(SqList L) int i=0; while(iL.getCurLen()-1) if (L.getListElem()i.equals(L.getListElem()i+1) /如果第i个及第i+1个相邻元素值相等 for (int j=i+1;jL.getCurLen();j+) /将第i+1个元素及其之后的所有元素前移一个位地置 L.getListElem()j-1=L.getListElem()j; L.setCurLen(L.getCurLen()-1); /有序顺序表的表长减1 else i+; 结果：八、应用性设计实验编程实现一个简单学生成绩管理系统的设计。实验要求此系统的功能包括： 查询：按特定的条件查找学生 修改：按学号对某个学生的某门课程成绩进行修改 插入：增加新学生的信息 删除：按学号删除已退学的学生的信息。学生成绩表的数据如下：学号姓名性别大学英语高等数学2008001AlanF93882008002DanieM75692008003HelenM56772008004BillF87902008006PeterM79862008006AmyF6875要求采用顺序存储结构来实现对上述成绩表的相关操作。截图实验心得：实验二 链表的操作实验一、实验名称和性质所属课程数据结构实验名称链表的操作实验学时4实验性质验证 综合 设计必做/选做必做 选做二、实验目的1掌握线性表的链式存储结构的表示和实现方法。2掌握链表基本操作的算法实现。三、实验内容1建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。2建立双向链表，并在双向链表上实现插入、删除和查找操作（设计性内容）。3计算已知一个单链表中数据域值为一个指定值x的结点个数（应用性设计内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5以上或Eclipse、MyEclipse等编程环境下。五、知识准备前期要求熟练掌握了Java语言的编程规则、方法和单链表和双向链表的基本操作算法。六、验证性实验运行结果参考如图4-1所示：七、设计性实验 两个一元多项式的相乘 P54-55截图：八、应用性设计实验编写一个程序，计算出一个单链表中数据域值为一个指定值x的结点个数。实验要求： 从键盘输入若干个整数，以此序列为顺序建立一个不带头结点的单链表； 输出此单链表中的各个数据元素值； 给定一个x的具体整数值，计算并返回此单链表中数据域值为x的结点个数值。截图实验心得：实验三 栈和队列的操作实验一、实验名称和性质所属课程数据结构实验名称栈和队列的操作实验学时4实验性质验证 综合 设计必做/选做必做 选做二、实验目的1掌握栈和对的存储结构的表示和实现方法。2掌握栈的入栈和出栈等基本操作算法实现。3了解栈在解决实际问题中的简单应用。三、实验内容1建立顺序栈，并在顺序栈上实现入栈和出栈操作（验证性内容）。2建立链栈，并在链栈上实现入栈和出栈操作（设计性内容）。3实现汉诺（Hanoi）塔求解问题（应用性设计内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5以上或Eclipse、MyEclipse等编程环境下。五、知识准备前期要求熟练掌握了Java语言的编程规则、方法和顺序栈、链栈的基本操作算法。六、验证性实验实验截图七、设计性实验P111 4-1,4-3，4-4,4-5，4-10截图：4-1 4-3 4-4 4-5 4-10 八、应用性设计实验编程实现汉诺（Hanoi）塔求解问题。1实验要求假设有三个命名为X、Y和Z的塔座，在塔座X上插有n个直径大小各不相同且从小到大编号为1,2,n的圆盘。现要求将塔座X上的n个圆盘借助于塔座Y移至塔座Z上，并仍按同样顺序叠排。圆盘移动时必须遵循下列规则： 每次只能移动一个圆盘； 圆盘可以插在X、Y和Z中的任何一个塔座上； 任何时刻都不能将一个较大的圆盘压在较小的圆盘上。截图：实验心得：实验四 二叉树的遍历实验一、实验名称和性质所属课程数据结构实验名称二叉树的操作实验学时4实验性质验证 综合 设计必做/选做必做 选做二、实验目的1理解二叉树的类型定义与性质。2掌握二叉树的二叉链表存储结构的表示和实现方法。3掌握二叉树遍历操作的算法实现。4熟悉二叉树遍历操作的应用。三、实验内容1建立二叉树的二叉链表存储结构。2实现二叉树的先根、中根和后根三种遍历操作（验证性内容）。3应用二叉树的遍历操作来实现判断两棵二叉树是否相等的操作（设计性内容）。4求从二叉树根结点到指定结点p之间的路径（应用性设计内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5以上或Eclipse、MyEclipse等编程环境下。五、知识准备前期要求掌握二叉树的二叉链表的存储结构表示和三种遍历操作算法。六、验证性实验4运行结果七、设计性实验编程实现根据二叉树的先序遍历序列和中序遍历序列来建立两棵二叉树，并判断这两棵二叉树是否相等。1. 实验要求 假设二叉树的结点值是字符，请分别根据输入的两棵二叉树的先根遍历序列和中根遍历序列来建立二叉链表表示的两棵二叉树。 分别利用先根、中根和后根遍历方法来实现判断两棵二叉树是否相等的操作。 主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行利用哪一种遍历方法来判断两棵二叉树是否相等。截图：实验心得：实验五 二叉排序树的查找操作一、实验名称和性质所属课程数据结构实验名称二叉排序树的操作实验学时4实验性质验证 综合 设计必做/选做必做 选做二、实验目的1掌握二叉排序树的含义及其在计算机中的存储实现。2掌握在二叉排序树上查找操作的算法实现。3掌握二叉排序树的插入、删除操作的算法实现。三、实验内容1建立二叉排序树。2在二叉排序树上实现对给定值进行查找操作（验证性内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5以上或Eclipse、MyEclipse等编程环境下。 五、知识准备前期要求掌握二叉排序树的含义、二叉排序树上的查找算法和二叉排序上的插入、删除操作的算法。六、验证性实验运行结果： 七、设计性实验编程判断一棵二叉树是否为二叉排序树。1实验要求 二叉树采用二叉链表作为存储结构，且树中结点的关键字均不相同。 要输出最后的判断结果。截图：实验心得：实验六 图的操作实验一、实验名称和性质所属课程数据结构实验名称图的操作实验学时4实验性质验证 综合 设计必做/选做必做 选做二、实验目的1掌握图的相关概念。2掌握用邻接矩阵和邻接表的方法描述图的存储结构。3掌握图的深度优先搜索和广度优先搜索遍历的方法及其计算机的实现。4理解最小生成树的有关算法三、实验内容1用邻接表作为图的存储结构建立一个图，并对此图分别进行深度优先搜索和广度优先搜索遍历（验证性内容）。 2用邻接矩阵作为图的存储结构建立一个网，并构造该网的最小生成树（设计性内容）。3校园导游程序的实现（应用性设计内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5以上或Eclipse、MyEclipse等编程环境下。五、知识准备前期要求掌握图与网的含义、图的邻接矩阵和邻接表的存储表示、图的深度优先搜索遍历和广度优先搜索遍历方法、最小生成树的概念及其构造算法。六、验证性实验运行结果七、设计性实验用邻接矩阵作为图的存储结构建立一个网，并构造该网的最小生成树。截图实验心得：实验七 查找操作实验一、实验名称和性质所属课程数据结构实验名称查找操作实验学时4实验性质验证 综合 设计必做/选做必做 选做二、实验目的1掌握顺序查找操作的算法实现。2掌握二分查找操作的算法实现及实现该查找的前提。3掌握哈希查找操作的算法实现。三、实验内容1建立顺序查找表，并在此查找表上实现顺序查找操作（验证性内容）。2建立有序顺序查找表，并在此查找表上实现二分查找操作（验证性内容）。3建立索引查找表，并在此查找表上实现索引查找操作（设计性内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5以上或Eclipse、MyEclipse等编程环境下。五、知识准备前期要求掌握查找的含义和顺序查找、二分查找及索引查找操作的方法。六、验证性实验(一)运行结果。运行结果（二）哈希表操作1实验要求运行结果实验心得：实验八 排序操作实验一、实验名称和性质所属课程数据结构实验名称排序操作实验学时4实验性质验证 综合 设计必做/选做必做 选做二、实验目的1熟悉并掌握各种排序方法的设计思路。2掌握各种具体排序算法在计算机上的实现。3掌握各种排序方法的性能比较。三、实验内容1比较用直接插入排序、冒泡排序和简单选择排序方法进行排序时对关键字的比较次数和移动次数（验证性内容）。2希尔排序、归并排序和快速排序算法的实现（设计性内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5以上或Eclipse、MyEclipse等编程环境下。五、知识准备前期要求掌握排序的含义、各种排序的方法及其性能指标分析。六、验证性实验运行结果七、设计性实验设一列关键字为3,17,12,61,8,70,97,75,53,26,54,61，分别实现直接插入排序，希尔排序、冒泡排序、快速排序、选择排序和归并排序截图实验心得：