实训指导书课程 数据结构

1、 实 训 指 导 书第一章 概述一、实训总目的1、 巩固对数据结构课程中的几大数据类型链表、有序表、图、树的建立、添加、删除、查找以及排序的操作。2、对知识掌握的熟练程度、对一个小系统的总体设计框架的搭建以及后期对设计内容加以完善等环节都可以得到很好的锻炼。二、实训内容和时间进程安排：序号实训内容学时时间安排备注1实训一 命题分析、数据结构定义主函数模块22实训一 链表的建立、添加、删除、查找、排序等操作63实训一 程序调试和实训报告生成24实训二 命题分析、数据结构定义主函数模块15实训二 二叉树的建立66实训二 利用桟作四则运算57实训二 调试、实训报告产生28实训三 命题分析、数据结构定

2、义19实训三 键树的建立510实训三 键树的遍历、查找611实训三 调试、实训报告212实训四 题目分析，数据类型定义213实训四 根据信息建立存储图614实训四 建立已有图的邻接表415实训四 调试、报告生成2三、实训条件： 硬件： 软件：turboc场地：机房四、实训成绩考核办法 实训成绩考勤占10%，考核占90。考核主要根据题目规定要实现的功能的完成情况以及程序的可读性的优劣来评定。第二章 实训内容实训一：运动会分数统计一、实训目的：本次实训内容主要是对链表的建立、添加、删除、查找以及排序的操作，但有别于书本上同类习题，题目要求实用性和综合性。完成的过程中，学生对知识掌握的熟练程度、对一

3、个小系统的总体设计框架的搭建以及后期对设计内容加以完善等环节都可以得到很好的锻炼。二、实训理论基础： 线性表的链式表示和实现。线性表的存储有不同的方式，在本例中要求能够方便的检索，查找信息，采用链式方法便于对数据进行修改和查询。三、实训内容：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=0数据关系：D= ai-1，| ai D，ai-1，ai 为键树的兄弟结点，i2，3，

4、n基本操作：InitTree（&T）: 建立空键树；CreatDLTree（ &T, *key）：将查找字典的关键字key逐渐的插入到键树中，形成字典；Insert-DLTree（&T，K，n）:若不存在和K相同的关键字，则将关键字K插入到键树相应的位置，树中关键字个数n加一且返回TRUE；否则不再插入，返回FALSE；Search-DLTree（T, j, &K）：若文章的一行中从第j 个字符起长度为k的子串和指针rt所指向双链树中的单词相同，则数组count中相应的分量加1，并返回true，否则返回false。2、主程序流程及调用关系的两个模块主程序模块：Void main（） 初始化；

5、处理命令； 输出结果；树的查找树的建立树的插入 键树模块主程序模块五、拓展思考题：在实现时是否有优化方案？六、收获和体会：实训四：教务课程计划的辅助制定一、实训目的：由于课程之间存在先后的 约束关系，所以如何使得一个学生可以在最短的时间内学完所有的课程，需要借助图的拓扑排序来解决教务课程安排的问题。这是一个实际的事例，可以很好的巩固学生对拓扑排序的掌握并且了解在实际中的应用。二、实训理论基础：图、拓扑结构概念，图的建立以及拓扑排序算法。三、实训内容：扩展拓扑排序算法，进行课程学习计划的辅助设定。一个学生可以在一学期同时学习多门课程，根据个课程之间存在的先后次序，制定出学生在最短时间内学完所有课

6、程的计划。本课程设置中，可以根据各自学校所开课程的实际情况来安排一个专业的计划，也可根据给定的情况。例如：开设课程为计算机专业必修课，计算机导论、离散数学、线性代数、汇编语言、c语言、数据库、数据结构、操作系统、微机原理、编译原理和pascal语言。每门课之间的关系如下：微机原理计算机导论C语言线性代数Pascal语言操作系统数据库编译原理汇编语言数据结构离散数学如果把上面的关系图改成下面的形状，就很容易看出他们之间的先后顺序，这就是拓扑集合划分。计算机导论线性代数Pascal语言微机原理离散数学数据结构C语言汇编语言操作系统编译原理数据库需求分析：本程序以顶点表示课程，有向弧表示优先关系，构

7、造课程AOV网。以字符串形式输出各课程的名称，按其编号输入课程间的优先关系，由此形成AOV网的存储结构，此后执行拓扑集合划分程序，输出每学期应开设的课程。依据测试数据，输出的结果形式为：the result a Toposet sorting:1 term:线性代数计算机导论；2term：pascal语言微机原理离散数学3term：数据结构c语言汇编语言4term：编译原理操作系统数据库四、实训步骤：程序中所需的抽象数据类型：有向图的基本操作：CreateGraph（&G，V，VR）：V是图的顶点集，VR是 图中弧的集合。按V和VR的定义构造有向图G；DestroyGraph（&G）：销毁已存在的图G；CreatUDCG（&G）：建立该图对应的邻接表。本程序包含三个模块