《数据结构》实验教学大纲.doc

数据结构实验教学大纲课程代码： B03203 课程名称： 数据结构 英文名称： Data Structures 课程总学时： 60 （其中理论课 46 学时，实验 14 学时） 学 分： 2.5 课程类别： 必修 课程性质： 专业基础课 先修课程： 计算机导论、Java语言程序设计 面向专业： 软件技术、计算机网络技术 开课单位：软件工程系 一、实验教学的性质地位和任务数据结构实验课是计算机类专业的一门专业基础实验课，是后续专业课程的基础；该课程的主要任务是：进一步掌握和拓展所学的理论知识，初步掌握解决问题的基本结构以及建立在该结构上的算法，培养学生的综合能力；本课程主要内容包括：线性表及其应用实验，串及其应用实验，树及其应用实验，图及其应用实验，查找实验，内部排序实验；通过本实验课的学习，学生应学会分析研究计算机加工的数据结构的特性，培养数据抽象的能力，训练学生进行复杂程序设计的技能，培养良好程序设计的习惯，初步掌握算法的时间分析和空间分析的技术。 二、实验内容与要求项目一、线性表及其应用（1）实验目标1加深理解线性表的顺序表示与链式表示的意义和区别，理解不同存储结构下插入与删除操作的算法；2熟练掌握线性表的顺序存储方式及其插入、删除等基本操作的算法实现；3熟练掌握线性表的链式存储方式及其插入、删除等基本操作的算法实现；（2）具体内容 1设计一组输入数据并编写主程序分别调用上述算法（顺序表示的算法为InitList_Sq、ListInsert_Sq、ListDelete_Sq等，链式表示的算法为InitList_L、ListInsert_L、ListDelete_L等），调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解；2设计一个可以容纳40位数的求n!的程序。（3）主要仪器设备与工具PC机一台/每人。项目二、栈及其应用（1）实验目标1理解栈的概念；2掌握利用数组实现栈的基本操作；3应用栈结构来解决表达式求值的问题。（2）具体内容 1完成对堆栈中数据的存取（入栈 ,出栈,访问栈中元素）；2利用堆栈来实现求前序表达式或后序表达式的方法。（3）主要仪器设备与工具PC机一台/每人。项目三稀疏矩阵运算（1）实验目标掌握三元组法存储稀疏矩阵的方法及相关的基本操作，用数组存放矩阵的三元组，矩阵的行数和列数及非0数据从键盘输入，若两个矩阵不能相乘则输出“Error”（2）具体内容编写一个程序实现下列目标。1用三元组法存放稀疏矩阵2求出矩阵相乘结果3输出结果矩阵（3）主要仪器设备与工具PC机一台/每人。项目四、树及其应用实验（1）实验目标1掌握二叉树链表的结构和二叉排序树的建立过程；2掌握二叉排序树的插入和删除操作；3加深对二叉树的理解。（2）具体内容 1编写二叉排序树的基本操作函数 查找结点函数 SearchNode（ TREE *tree，int key， TREE *pkpt ， TREE *kpt） 二叉排序树插入函数 InsertNode （TREE *tree，int key ） 二叉排序树删除函数 DeleteNode （TREE *tree，int key）2调用上述函数实现下列操作 初始化二叉树 调用插入函数建立二叉排序树 调用查找函数在二叉树中查找指定的结点 调用删除函数删除指定的结点，并动态地显示删除结果。（3）主要仪器设备与工具PC机一台/每人。项目五、图及其应用实验（1）实验目标1掌握图的邻接矩阵、邻接表的表示方法；2掌握建立图的邻接矩阵的算法；3掌握建立图的邻接表的算法；4加深对图的理解。（2）具体内容 1编写图的基本操作函数 建立图的邻接表，邻接矩阵 Create_Graph（LGraph lg，MGraph mg） 邻接表表示的图的递归深度优先遍历 LDFS（LGraph g，int i ） 邻接矩阵表示的图的递归深度优先遍历 MDFS（MGraph g， int i， int vn） 邻接表表示的图的广度优先遍历 LBFS（LGraph g， int s， int n） 邻接矩阵表示的图的广度优先遍历 MBFS（LGraph g， int s， int n）2调用上述函数实现下列操作 建立一个图的邻接矩阵和图的邻接表 采用递归深度优先遍历输出图的邻接矩阵 采用递归深度优先遍历输出图的邻接表 采用图的广度优先遍历输出图的邻接表 采用图的广度优先遍历输出图的邻接矩阵（3）主要仪器设备与工具PC机一台/每人。项目六、查找实验（1）实验目标1掌握在数组上进行各种查找的方法和算法；2深刻理解各种方法的特点，并加以灵活运用。（2）具体内容1编写各种查找方法的基本操作函数 无序线性表的顺序查找 search1（ int *k，int n， int key） 有序线性表的顺序查找 search2（ int *k ， int n ， int key） 折半查找 bin_search（int *k ， int n ， int key）2调用上述函数实现下列操作： 对给定的数组EN=213，111，222，77，400，300，987，1024，632，555调用无序线性表的顺序查找函数进行查找。 调用有序线性表的顺序查找函数进行查找。 调用折半法查找函数进行查找。（3）主要仪器设备与工具PC机一台/每人。项目七、内部排序实验（1）实验目标1掌握在数组上进行各种排序的方法和算法； 2理解各种方法的特点，并能灵活运用。（2）具体内容1编写各种排序方法的基本操作函数 选择排序 ss_sort（ int e ，int n ） 直接插入排序 si_sort（ int e ，int n） 冒泡排序 sb_sort（ int e ，int n ） 二路合并排序 Merge（ int e ，int n ）2调用上述函数实现下列操作 对给定的数组EN=213，111，222，77，400，300，987，1024，632，555调用选择排序函数进行排序。 调用直接插入函数进行排序。 调用冒泡函数进行排序。 调用二路归并排序函数进行排序。（3）主要仪器设备与工具PC机一台/每人。三、学时分配序号实验项目名称时数实验要求实验类型所在实验室1线性表及其应用实验2必做设计计算机实习基地I2栈及其应用实验2必做设计计算机实习基地I3稀疏矩阵运算2必做设计计算机实习基地I4树及其应用实验2必做设计计算机实习基地I5图及其应用实验2必做设计计算机实习基地I6查找实验2必做综合计算机实习基地I7内部排序实验2必做综合计算机实习基地I四、考核方式与成绩评定本实验课程采用随堂考查。考查形式中：预习报告、上机调试、实验报告各占20%、50%、30%。五、大纲说明1本大纲实验课时仅为课堂上机课时，要达到大纲要求必须有课外时间保障：课前准备、课堂上机调试与课后上机练习所占时间比为：4：1：2。2本实验主要以每个实验项目的实验目标为基准，以实验内容为主要知识点，采用过程式考核。六、推荐教材及参考书1 朱战立数据结构Java语言描述北京：清华大学出版社，20052 严蔚敏，吴伟民数据结构（C语言版）北京：清华大学出版，19993 李春保数据结构习题与解析（C语言篇）北京：清华大学出版社，2001执 笔：审 核：审 批：5