数据结构实验指导书.doc

数据结构实验指导书实验一 顺序表实验目的：熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。实验要求：了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。实验内容：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语言描述 作者：唐策善等出版社：高等教育出版社实验指导书：算法与数据结构实验大纲及指导书作者：付百文 张宇红 季全芝出版社：自编实验成绩的