数据结构实验指导书.pdf

数据结构实验指导书 数据结构实验指导书 实验一顺序表 实验目的：熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。实验要求：了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。实验内容：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%实验报告，占 40%实验课程的总成绩为各个实验项目成绩的总和。本成绩以 50%的比例计入数据结构课程的平时成绩。