2013数据结构实验教学大纲讲解.doc

本 科 教 学 大 纲 学 院 （部）： 信息工程学院 课 程 名 称： 数据结构与算法实验 教务处 二○一三年十月 数据结构与算法实验 课程教学大纲 课程名称：数据结构与算法实验 Data structures and algorithms experiment 课程类别 学科基础课 课程编号 3072045 学时数 45 归属学院（部） 信息工程学院 授课对象 信息与计算科学专业本科生 完成人 杨海军 职称 教授 审定人 完成日期 2013 年 9 月 30 日 课程简介 《数据结构与算法实验》是结合理论课程《数据结构与算法》独立开设的实践课程。通过理论与实践密切结合，加深对理论课程中基本数据结构和算法的理解；通过动手编程，加强学生解决实际问题的能力。 该课程是我校信息与计算科学（信息科学方向）开设的必修课程之一。本实验课程分为验证性、设计性实验。其中验证性实验要求学生能理解程序，掌握程序流程，明白程序结果；设计性实验让学生利用所学的知识开发一个小型项目，分析问题，设计算法，实现程序的各项功能得到正确的可执行程序对设计过程进行系统的总结。 实验2 栈、队列及其应用实验 实验3　 稀疏矩阵及其运算实验 实验4　 树及树的应用实验 实验5 图及图的应用实验 实验6 查找算法实现实验 实验7 排序算法实验 实验8 数据结构综合应用实验 《数据结构与算法实验》教学严格按照实验教学大纲和实验教学计划组织实验教学。采取实践与理论同步进行的方式，分章节、分主题进行实验。实验中教师认真讲解、个别辅导；同时在实验过程中穿插讲解演示实验，使学生通过演示实验对概念有更清楚、明晰的了解，更好地巩固所学理论知识，开拓视野。 一、课程目的与教学基本要求 通过实验，加深学生对教学内容的理解，验证所学的算法和数据结构。培养学生设计数据结构的能力和根据数据结构设计算法的能力，使学生掌握非数值问题的数据结构和算法的设计方法。通过对具体问题的分析、设计和实现，培养学生进行软件开发所需要的动手能力，为学好后续课程打下坚实的基础。 本课程以学习数据结构和算法思想为主。通过实验，理解和验证相应数据结构及算法思想，最终达到灵活运用所学的逻辑结构和物理存储方案解决实际问题的能力，并能充分考虑解决问题所用算法的正确性、可靠性和效率等问题。 二、课程内容及学时分配 实验一 线性表的顺序表和单链表实验 实验目的： 掌握用Visual C++6.0上机调试顺序表的基本方法。 掌握顺序表的基本操作，插入、删除、查找等算法的实现。 掌握用Visual C++6.0上机调试单链表的基本方法。 掌握单链表的基本操作，插入、删除、查找、求表等算法的实现。 实验工具： Visual C++6.0 实验内容： 问题描述：实现线性表的基本操作：构造空的线性表、建立线性表、求表长、获取第i个元素、插入、删除、输出线性表等。 基本要求：分别在顺序存储结构和非顺序结构下实现。并在主程序中完成输出开始建立的线性表，输出获取的元素，输出表长，输出在插入和删除操作后的线性表的工作。 测试数据：给定线性表23、33、21、45、67，获取第3个元素的值，在第3个元素之前插入38，删除第5个元素。 实现提示：1）完成顺序表及单链表的类型定义；2）编写主程序；3）调试运行程序；4）记录并分析程序中出现的错误以及解决办法和实验结果。 扩展实验：利用线性表实现学生信息管理系统，要求完成以下任务 新增学生信息 删除学生信息 修改学生信息 查询学生信息 实验要求： 硬件基本配置：PC，局域网连接。 软件要求：Visual C++6.0。 实验学时：6学时。 实验二 栈、队列及其应用实验 实验目的： 掌握栈、队列的基本操作算法实现及栈、队列的应用方法。 实验工具： Visual C++6.0 实验内容： 已实现的栈基础上，完成检查一个表达式（或文本文件）中的花括号、方括号和圆括号是否配对的程序，并输出检测结果。 在已实现的队列基础上编程实现学生在线答疑排队模拟。 实验要求： 硬件基本配置：PC，局域网连接。 软件要求：Visual C++6.0。 写出实验报告。 实验学时：4学时。 实验三 稀疏矩阵及其运算实验 实验目的： 掌握稀疏矩阵的压缩存储表示及其运算。 实验工具： Visual C++6.0 实验内容： 设计存储结构实现稀疏矩阵的压缩存储。 设计算法实现稀疏矩阵的快速转置。 分析算法的时间复杂度。 实验要求： 硬件基本配置：PC，局域网连接。 软件要求：Visual C++6.0。 写出实验报告。 实验学时：3学时。 实验