数据结构实验指导书
- 格式:doc
- 大小:48.00 KB
- 文档页数:6
《数据结构》实验指导书
实验一顺序表
实验目的:
熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。
实验要求:
了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。
实验内容:
1、编写程序实现在线性表中找出最大的和最小的数据元素,并符合下列要求:
(1)设数据元素为整数,实现线性表的顺序存储表示。
(2)从键盘输入10个数据元素,利用顺序表的基本操作建立该表。
(3)利用顺序表的基本操作,找出表中最大的和最小的数据元素(用于比较的字段为整数)。
2、编写一个程序实现在学生成绩中找出最高分和最低分,并符合下列要求:
(1)数据元素为学生成绩(含姓名、成绩等字段)。
(2)要求尽可能少地修改第一题的程序来得到此题的新程序,即要符合第一题的所有要求。(这里用于比较的字段为分数)
实验二链表
实验目的:
熟悉链表的逻辑特性、存储表示方法的特点和链式表的基本操作。
实验要求:
了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。
实验内容:
1、编写一个程序建立存放学生成绩的有序链表并实现相关操作,要求如下:
(1)设学生成绩表中的数据元素由学生姓名和学生成绩字段组成,实现这样的线性表的链式存储表示。
(2)键盘输入10个(或若干个,特殊数据来标记输入数据的结束)数据元素,利用链表的基本操作建立学生成绩单链表,要求该表为有序表
并带有头结点。(用于比较的字段为分数)。
(3)输入关键字值x,打印出表中所有关键字值<=x的结点。(用于比较的关键字字段为分数)。
(4)输入关键字值x,删除表中所有关键字值<=x的结点。(用于比较的关键字字段为分数)。
(5)输入关键字值x,并插入到表中,使所在的链表仍为有序表。(用于比较的字段为分数)。
实验三栈的应用
实验目的:
熟悉栈的逻辑特性、存储表示方法和栈的基本操作。
实验要求:
了解并熟悉栈的逻辑特性、顺序和链式存储表示方法和栈的基本操作的实现和应用。
实验内容:
(1)判断一个表达式中的括号(仅有一种括号,小、中或大括号)
是否配对。编写并实现它的算法。
(2)用不同的存储方法,求解上面的问题。
(3)* 若表达式中既有小括号,又有大括号(或中括号),且允许
互相嵌套,但不能交叉,写出判断这样的表达式是否合法的算
法。如 2+3*(4-{5+2}*3)为合法;2+3*(4-{5+2 * 3} 、
2+3*(4-[5+2 * 3)为不合法。
实验四队列应用
实验目的:
熟悉队列的逻辑特性、存储表示方法和队列的基本操作。
实验要求:
了解并熟悉队列的逻辑特性、列队存储表示方法,掌握循环队列的基本操作。实验内容:
(1)编程实现循环队列的基本操作,包括构造空队列、判断队空、
入队和出队,并打印相应的结果。
(2)应用队列打印杨辉三角形。
实验五二叉树的基本操作和应用
实验目的:
熟悉树的基本概念,树状结构的逻辑特性、存储表示方法和二叉树的基本操作。
实验要求:
熟悉树的基本概念,树状结构的逻辑特性、存储表示方法和树的基本操作,实现二叉树的遍历算法(前序、中序和后序遍历)。
实验内容:
(1)实现行政机构的二叉树表示,设数据元素类型为字符串(如总经理、
业务部经理、财务部经理、业务主管A、业务主管B、业务员A1、
业务员A2、业务员B1、业务员B2(可没有)、财务主管A、财务
主管B、财务员A1、财务员A2(可没有)、财务员B1、财务员B2),
建立这棵二叉树。
(2)实现该二叉树的前序、中序和后序遍历,输出遍历结果。
(3)*按职务从高到低的次序依次输出这些职位。(即按层遍历、要求
利用队列来实现)
(4)*求该机构的职务等级数。
(5)*键盘输入一个职位,查找并输出其上级和下级职位。
实验六顺序和二分查找
实验目的:
熟悉查找算法及过程。
实验要求:
实现顺序和二分等查找方法。
实验内容:
(1)建立一个整数构成的顺序表。
(2)根据用户输入的查找值,实现顺序表的顺序查找。
(3)建立一个有序的整数构成的顺序表(可直接利用前面排序实验的结果)。
(4)根据用户输入的查找值,实现二分查找,并输出比较的元素、元素的比
较次数等。要求实现递归和非递归算法。
(5)*模拟统计查找长度,随机产生100,200,500,1000,2000等若干个
随机整数,在(3)中定义的有序表中查找这些值,统计查找成功和查
找不成功的平均查找长度。
实验七四种主要排序算法编程及问答
实验目的:
熟悉排序算法及过程。
实验要求:
编写程序实现四种主要的排序算法
实验内容:
(1)编写程序实现直接插入排序、冒泡排序、快速排序、直接选择排序。
(2)回答程序中已经设置的相关问题
实验八图及其应用
实验目的:
熟悉图的基本概念、逻辑特性、存储表示方法和图的基本操作。
实验要求:
熟悉图的基本概念、逻辑特性、存储表示方法,实现无向网的存储表示、图的深度优先搜索遍历、广度优先搜索遍历、单源最短路径算法。
实验内容:
(1)实现交通网、通信网或局域网的邻接矩阵存储表示,设数据元素类
型为字符串(如地名、房间号等)。
(2)实现该网的深度优先搜索遍历,输出遍历结果。
(3)*实现上述网络的邻接表存储表示,实现其广度优先搜索遍历,输出
遍历结果。
(4)*求从一个地点到其它各个地点的最短路径。
实验指导书和参考书
参考教材:《数据结构—用C语言描述》作者:唐策善等
出版社:高等教育出版社
实验指导书:《算法与数据结构实验大纲及指导书》
作者:付百文张宇红季全芝
出版社:自编
实验成绩的评定
学生每完成一个实验,将得到一个成绩。
上述成绩的评定有以下三部分组成:
实验过程(含实验准备情况),占20%
实验结果,占40%