计科专业数据结构实验任务书.doc
计算机科学与技术专业基础课程数据结构实验任务书数据结构实验按教学大纲要求，计划学时16，授课区间3周10周，共计8周(2013年9月17日开始)。实验一 线性表的应用【实验目的】：1、掌握线性表的逻辑结构定义2、掌握线性表的两种存储结构（顺序和链式）3、掌握顺序表和链表的定义及基本操作【实验内容】通过编程完成具有一定实际意义的课题，加深对线性表应用的理解和掌握。参考题目如下所示。学生可在完成以下题目之后经指导教师同意自行设计其它选题并将选题源程序与执行结果提交指导教师审阅。1、实验题目：字母链表n 功能要求：生成26个字母的线性表，并实现对特定字母的插入和删除。n 程序说明：使用顺序表或者链表生成字母有序表，并应用相应数据结构实现对单个字母的插入和删除操作。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。n2、实验题目：链表的创建n 功能要求：使用简单数据类型，利用指针创建一个基本链表。n 程序说明：使用指针，通过在头结点之后插入新节点的操作，逐步生成基本链表。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。3、 实验题目：链表的逆序输出n 功能要求：使用简单数据类型，利用指针创建一个基本链表。n 程序说明：使用指针，通过在尾结点之前插入新节点的操作，逐步逆序生成基本链表，之后，利用头结点实现顺序输出，以达到链表逆序的功能。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。4、 连接两个链表n 功能要求：使用简单数据类型，利用指针创建一个基本链表。n 程序说明：使用指针，首先使用程序一生成两个基本链表，之后使用两个链表的头尾指针相连，从而实现两个链表的连接。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。5、【考核办法及成绩评定】每个学生应在课堂规定时间内完成任务书所列任务，并提交实验报告一份（内容包括封面、实验题目、实验目的、实验内容、实验源代码以及执行结果清单，其中封面见附录。）实习报告不合格者，需修改合格后再提交。成绩评定由实验教师根据试验大纲按比例评定，之后提交授课教师审核。实验二 栈与队列的应用【实验目的】：1、 掌握栈和队列的结构定义和特性2、 掌握栈和队列的基本操作以及栈和队列在程序设计中的应用。【实验内容】通过编程完成具有一定实际意义的课题，加深对栈与队列应用的理解和掌握。参考题目如下所示。学生可在完成以下题目之后经指导教师同意自行设计其它选题并将选题源程序与执行结果提交指导教师审阅。1、实验题目：利用栈实现数制转换n 功能要求：使用栈完成十进制数到各种不同进制数的数制转换。n 程序说明：利用堆栈工作原理实现对任意十进制数的数值转换操作。其中，实现堆栈功能的各个库函数由自行建立的头文件“stack.h”提供，“stack.h”可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。n2、实验题目：简单四则运算程序n 功能要求：使用堆栈数据结构，完成10以内的四则运算。n 程序说明：按照操作符的优先级，使用堆栈数据结构，由左至右读入字符并判定计算步骤完成操作，并生成结果输出。其中，实现堆栈功能的各个库函数由自行建立的头文件“stack.h”提供，“stack.h”可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。3、 实验题目：表达式括号匹配程序n 功能要求：使用堆栈，对整行输入的表达式进行括号匹配操作，并判定匹配与否将结果输出。n 程序说明：使用堆栈与字符比较，判定表达式括号是否匹配。其中，实现堆栈功能的各个库函数由自行建立的头文件“stack.h”提供，“stack.h”可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。4、 堆栈与队列的遍历操作（可选）n 功能要求：使用简单数据类型，利用指针分别创建一个基本栈和一个基本队列，并使用指针将堆栈与队列元素按顺序输出。n 程序说明：使用指针，首先两个基本数据结构，之后分别使用两个不同数据结构的指针实现对各自元素的输出。其中，实现堆栈功能的各个库函数由自行建立的头文件“stack.h”提供，“stack.h”可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。5、 判定回文程序（可选）n 功能要求：同时使用栈和队列数据结构判断一个字符序列是不是“回文”。n 程序说明：“回文”：指一列字符无论采用顺序或逆序进行输出时，字符序列完全相同。首先使用两个基本数据结构读入字符序列，之后通过不同的工作方式对弹出的元素进行比较，判断字符序列是不是“回文”。其中，实现堆栈功能的各个库函数由自行建立的头文件“stack.h”提供，“stack.h”可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。【考核办法及成绩评定】每个学生应在课堂规定时间内完成任务书所列任务，并提交实验报告一份（内容包括封面、实验题目、实验目的、实验内容、实验源代码以及执行结果清单，其中封面见附录。）实习报告不合格者，需修改合格后再提交。成绩评定由实验教师根据试验大纲按比例评定，之后提交授课教师审核。实验三 串的应用【实验目的】：1、掌握串的数据类型定义，串的存储结构。2、掌握串的基本操作实现与应用。【实验内容】通过编程完成具有一定实际意义的课题，加深对串结构应用的理解和掌握。参考题目如下所示。学生可在完成以下题目之后经指导教师同意自行设计其它选题并将选题源程序与执行结果提交指导教师审阅。1、实验题目：串的置换算法n 功能要求：编写一个实现串的置换操作Replace(&S,T,V)的算法。n 程序说明：对一个字符串S，使用一个长度小于S的串T替换S的子串V，并将替换后的串输出。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。2、实验题目：串反序的递推/递归算法n 功能要求：给定字符串进行逆序输出。n 程序说明：使用单链表存储字符串。设计递推或递归程序，完成字符串逆序输出。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。【考核办法及成绩评定】每个学生应在课堂规定时间内完成任务书所列任务，并提交实验报告一份（内容包括封面、实验题目、实验目的、实验内容、实验源代码以及执行结果清单，其中封面见附录。）实习报告不合格者，需修改合格后再提交。成绩评定由实验教师根据试验大纲按比例评定，之后提交授课教师审核。实验四 数组的应用【实验目的】：1、掌握数组的定义和实现，加深对数组的类型理解。2、掌握数组的存储结构和访问方式。3、掌握特殊矩阵的存储方法。【实验内容】通过编程完成具有一定实际意义的课题，加深对数组结构应用的理解和掌握。参考题目如下所示。学生可在完成以下题目之后经指导教师同意自行设计其它选题并将选题源程序与执行结果提交指导教师审阅。1、实验题目：稀疏矩阵计算n 功能要求：使用三元组完成稀疏矩阵的存储，并进行矩阵相加计算。n 程序说明：利用数组结构分别存储两个稀疏矩阵A、B，并进行矩阵相加的运算，将结果存入C矩阵。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。2、实验题目：数组元素移位程序n 功能要求：将数组An至An-1循环右移k位。n 程序说明：设计一个程序，使用一个元素大小的附加存储，将数组An至An-1循环右移k位。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。【考核办法及成绩评定】每个学生应在课堂规定时间内完成任务书所列任务，并提交实验报告一份（内容包括封面、实验题目、实验目的、实验内容、实验源代码以及执行结果清单，其中封面见附录。）实习报告不合格者，需修改合格后再提交。成绩评定由实验教师根据试验大纲按比例评定，之后提交授课教师审核。实验五 二叉树的应用【实验目的】：1、掌握二叉树的性质和存储结构；2掌握二叉树的遍历和线索化及其应用；3掌握哈夫曼树的应用。【实验内容】通过编程完成具有一定实际意义的课题，加深对二叉树结构应用的理解和掌握。参考题目如下所示。学生可在完成以下题目之后经指导教师同意自行设计其它选题并将选题源程序与执行结果提交指导教师审阅。1、实验题目：二叉树的建立及遍历n 功能要求：生成一棵二叉树，并使用三种遍历方式进行遍历。n 程序说明：利用二叉树结构生成一棵二叉树并对其进行三序遍历，将结果按遍历顺序输出。其中，完成二叉树的操作的库函数，可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。n2、实验题目：二叉排序树的遍历n 功能要求：生成一棵二叉排序树，遍历并统计其叶子节点的数目。n 程序说明：设计一个程序，生成二叉排序树之后进行中序遍历，同时统计该树叶子节点的数目并输出。其中，完成二叉树的操作的库函数，可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。n3、实验题目：二叉排序树的层序遍历（可选）n 功能要求：生成一棵二叉树，对其进行层序遍历。n 程序说明：设计一个程序，生成二叉树之后按二叉树层次顺序进行并输出节点。其中，完成二叉树的操作的库函数，可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境4、实验题目：判断同构二叉树（可选）n 功能要求：生成两棵二叉树，判定两棵树是否同构。n 程序说明：设计一个程序，生成二叉树之后通过反复比较其子树结构判定这两棵二叉树是否同构并将判定结果输出。其中，完成二叉树的操作的库函数，可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境5、实验题目：最近公共祖先（可选）n 功能要求：对二叉树中的两个给定节点，判定其最近公共祖先。n 程序说明：设计一个程序，生成二叉树之后，任意给定节点对(m,n)，查找这两个节点的最近公共祖先，并将祖先节点输出。其中，完成二叉树的操作的库函数，可参考授课教材相关章节，如需使用其他数据结构，请参考相关教材章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境【考核办法及成绩评定】每个学生应在课堂规定时间内完成任务书所列任务，并提交实验报告一份（内容包括封面、实验题目、实验目的、实验内容、实验源代码以及执行结果清单，其中封面见附录。）实习报告不合格者，需修改合格后再提交。成绩评定由实验教师根据试验大纲按比例评定，之后提交授课教师审核。实验六 图的应用【实验目的】：1、掌握图的定义和存储结构；2掌握图的遍历算法与树的遍历算法之区别；3掌握图的最小生成树。【实验内容】通过编程完成具有一定实际意义的课题，加深对图结构应用的理解和掌握。参考题目如下所示。学生可在完成以下题目之后经指导教师同意自行设计其它选题并将选题源程序与执行结果提交指导教师审阅。1、实验题目：建立图的邻接表n 功能要求：给定图的相关信息，使用邻接表结构存储图。n 程序说明：利用邻接表存储结构，依次输入图的顶点和弧的数目，各顶点与各条弧的信息，建立有向图，并将遍历结果输出。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。2、实验题目：图的顶点/边的插入删除（选做）n 功能要求：在已存在的图G中插入新的顶点/边。n 程序说明：使用图的相关存储结构建立有向/无向图G，对G进行顶点/边的插入或删除。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。【考核办法及成绩评定】每个学生应在课堂规定时间内完成任务书所列任务，并提交实验报告一份（内容包括封面、实验题目、实验目的、实验内容、实验源代码以及执行结果清单，其中封面见附录。）实习报告不合格者，需修改合格后再提交。成绩评定由实验教师根据试验大纲按比例评定，之后提交授课教师审核。实验七 查找【实验目的】：1、掌握顺序表和有序表的查找方法2掌握二叉排序树的构造和查找方法【实验内容】通过编程完成具有一定实际意义的课题，加深对查找算法应用的理解和掌握。参考题目如下所示。学生可在完成以下题目之后经指导教师同意自行设计其它选题并将选题源程序与执行结果提交指导教师审阅。1、实验题目：顺序查找和折半查找n 功能要求：使用顺序和折半两种查找方法查找磁盘文件中的学生成绩记录。n 程序说明：合适的数据结构生成查找表，读取学生记录并对相应关键字进行记录查找，并将查找结果进行输出。学生记录存在于磁盘文件“student.txt”当中。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。2、实验题目：二叉排序树的构造和查找n 功能要求：使用二叉排序树结构进行查找。n 程序说明：设计一个程序，将带查找序列使用二叉排序树结构进行存储，之后查找关键字并输出。其中，完成二叉树的操作的库函数，可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。【考核办法及成绩评定】每个学生应在课堂规定时间内完成任务书所列任务，并提交实验报告一份（内容包括封面、实验题目、实验目的、实验内容、实验源代码以及执行结果清单，其中封面见附录。）实习报告不合格者，需修改合格后再提交。成绩评定由实验教师根据试验大纲按比例评定，之后提交授课教师审核。实验七 排序【实验目的】：1、深刻理解排序的定义和各种排序方法的特点；2、掌握简单插入排序、快速排序、堆排序的算法并加以应用。3、掌握各种排序方法的时间复杂度的分析方法。【实验内容】通过编程完成具有一定实际意义的课题，加深对排序算法应用的理解和掌握。参考题目如下所示。学生可在完成以下题目之后经指导教师同意自行设计其它选题并将选题源程序与执行结果提交指导教师审阅。1、实验题目：各种排序算法n 功能要求：实现教材中讲述的各种排序算法。n 程序说明：使用合适的数据结构存储待排序序列，并使用不同排序算法排序后将排序结果进行输出。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。2、实验题目：输油管道问题（可选）n 功能要求：给定n口油井的位置，计算各油井到主管道之间的输油管道最小长度总和。n 程序说明：某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路径（或南或北）与主管道相连。如果给定n口油井的位置，即他们的x坐标（东西向）和y坐标（南北向），试确定主管道的最优位置，使各油井到主管道之间的输油管道长度总和最小。各油井位置如下示例（每行2个整数x和y，分别代表据主管道的横纵坐标（-10000<x,y<10000）：油井数：5位置：(1, 2) (2,2) (1,3) (3,-2) (3,3)其中，完成二叉树的操作的库函数，可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。n 实验分组：每组1人，使用微机一台，C或C+兼容环境。【考核办法及成绩评定】每个学生应在课堂规定时间内完成任务书所列任务，并提交实验报告一份（内容包括封面、实验题目、实验目的、实验内容、实验源代码以及执行结果清单，其中封面见附录。）实习报告不合格者，需修改合格后再提交。成绩评定由实验教师根据试验大纲按比例评定，之后提交授课教师审核。附：实验课程时间表（2013.9-2013.11）21231 , 21232周二 1-2节实验室教师21233 , 21234周五 7-8 节808李佳音21235 , 21236周五 3-4 节（如遇假期或课程冲突，可根据学生课表调整）附录 C+语言课程设计报告书封面模版（见下页）数据结构实验报告（实验题目）班级学号学生姓名提交日期2013年9月1日成 绩 ：计算机与通信工程学院2013
