《数据结构》实验指导书.doc

PAGE 1 实验指导书 课程名称：数据结构 计算机科学与工程系 《数据结构》课程组  目 录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc163291445 前 言 PAGEREF _Toc163291445 \h 1 HYPERLINK \l _Toc163291446 一、实验的作用和目的 PAGEREF _Toc163291446 \h 2 HYPERLINK \l _Toc163291447 二、实验方式与考核方式 PAGEREF _Toc163291447 \h 2 HYPERLINK \l _Toc163291448 三、实验要求 PAGEREF _Toc163291448 \h 3 HYPERLINK \l _Toc163291449 四、实验报告要求 PAGEREF _Toc163291449 \h 4 HYPERLINK \l _Toc163291450 五、实验内容 PAGEREF _Toc163291450 \h 5 HYPERLINK \l _Toc163291451 实验一 线性表应用 PAGEREF _Toc163291451 \h 5 HYPERLINK \l _Toc163291452 实验二 栈与队列应用 PAGEREF _Toc163291452 \h 10 HYPERLINK \l _Toc163291453 实验三 二叉树的操作 PAGEREF _Toc163291453 \h 14 HYPERLINK \l _Toc163291454 实验四 图的遍历 PAGEREF _Toc163291454 \h 18 HYPERLINK \l _Toc163291455 实验五 查找算法应用 PAGEREF _Toc163291455 \h 21 HYPERLINK \l _Toc163291456 六、选做实验内容 PAGEREF _Toc163291456 \h 24 HYPERLINK \l _Toc163291457 实验六 排序 PAGEREF _Toc163291457 \h 24 HYPERLINK \l _Toc163291458 实验七 数组和广义表 PAGEREF _Toc163291458 \h 26 HYPERLINK \l _Toc163291459 实验八 串 PAGEREF _Toc163291459 \h 27 前 言 《数据结构》数据结构是计算机科学与技术及相关专业的一门重要专业基础课，它主要介绍线性结构、树型结构、图状结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法，以及算法的时间、空间效率分析。 这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过本课程的学习，使学生熟练地掌握数据结构的内在逻辑关系及其在计算机中的表示方法（存储结构），以及相关基本操作的算法实现；掌握典型算法的设计思想及程序实现；熟悉各种数据结构在计算机科学中的基本应用；培养和训练学生结合实际应用，根据实际问题选取合适的数据结构、存储方案设计出简洁、高效、实用的算法；并为学习《操作系统》、《编译原理》、《数据库原理》等后续课程和研制开发各种系统和应用软件打下扎实的理论与实践基础。 学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写此实验指导书。实验指导书按照实验教学大纲的要求，为每个主要的知识点精选了的典型的实验题目，对每个实验题目提出具体实现要求，并对算法的实现进行提示，希望对同学实验有所帮助。 《数据结构》课程组 2005年5月 一、实验的作用和目的 实验课是对学生的一种全面综合训练，是与课堂教学、课后练习相辅相成的必不可少的一个教学环节。 《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机实验作业。通过课程的上机实验，可使学生深刻理解各种逻辑结构、存储结构的特性；学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。 本课程的实验着眼于原理与应用的结合点。通过课程的实验，培养学生分析问题，并能针对实际应用问题选择适用的逻辑结构、存储结构，设计和实现相应算法。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练，培养设计具有专业水准应用程序的能力。 二、实验方式与考核方式 课程实验采用课内实验学时与课外实验学时相结合（课外实验学时是课内实