《算法与数据结构》实验指导书

数据结构与算法实习_实验指导书数据结构与算法课程实习实验指导书目录实验一顺序表的基本操作 (2)实验二链表的基本操作 (3)实验三二叉树的基本操作 (4)实验四综合应用 (5)附录A 实验报告示例 (9)附录B实验报告封面、评语得分表 (12)实验一顺序表的基本操作【实验目的】1、掌握顺序存储的概念，学会对顺序表的基本操作。

2、加深对顺序存储数据结构的理解，逐步培养解决实际问题的能力。

【实验性质】设计型实验【实验内容】1、实现顺序表显示；2、实现顺序表插入；3、实现顺序表查找（显示比较次数）；4、实现顺序表删除（显示移动次数）；5、实现顺序表排序（分别实现简单选择、快速，显示比较次数、移动次数）；6、实现顺序表的折半查找（显示比较次数）；7、编程实现一个顺序表的就地逆置，即利用原表的存储空间将顺序表逆置；8顺序表有序插入（显示比较次数、移动次数），屏幕提示后，从键盘输入一个元素值，在经过排序的线性表中插入这个元素；屏幕显示比较次数和移动次数，应有溢出判断和报告；9、要求以较高的效率实现删除顺序表中元素值在x到y（x和y自定）之间的所有元素;10、编程实现将两个非递减的顺序表进行合并，要求同样的数据元素只出现一次；*11、编程实现顺序表的shell排序（步长为5, 3，1）；*12、编程实现堆排序算法；*13、利用三元组顺序表存储矩阵，实现矩阵的转置（请独立写程序实现）。

【实验环境】VC++ 6.0【实验要求】将如上文件保存在命名为学号+姓名”勺文件夹中并上传到指定的服务器。

实验二链表的基本操作【实验目的】1、掌握链表的概念，学会对链表进行操作。

2、加深对链式存储结构的理解，逐步培养解决实际问题的编程能力。

【实验性质】设计型实验【实验内容】1、实现单链表的创建；2、实现单链表的显示；3、实现单链表的查找（显示比较次数）；4、实现单链表的插入；5、实现单链表的删除（显示比较次数）；6、对已创建的链表（数据不限）进行直接插入排序；7、将链接存储线性表逆置，即最后一个结点变成第1个结点，原来倒数第2个结点变成第2个结点，如此等等；8、生成有序的两个单链表A和B （链表的数据和个数自定），其首结点指针分别为a 和b,要求将两个单链表合并为一个有序的单链表C,其首结点指针为c,并且合并后的单链表的数据不重复；9、将一个首结点指针为a的单链表A分解成两个单链表A和B，其首结点指针分别为a和b，使得链表A中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序；10、请编程实现链栈的基本操作函数，并通过调用这些基本函数，实现十进制和八进制转换的功能。

《数据结构和算法》实验指导书实验及学时数分配序号实验名称学时数（小时）1 实验一线性表 42 实验二树和二叉树 23 实验三图 24 实验四查找 25 实验五内部排序 2合计12几点要求：一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。

二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。

上机时签到；下机时验收签字。

三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。

实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。

【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。

(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。

若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。

若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。

【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。

1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i，和要插入的元素值；实现插入；显示插入后的线性表）3、指定一个元素，删除此元素。

《数据结构与算法》实验指导书马晓波秦俊平刘利民编内蒙古工业大学信息工程学院计算机系2009年3月1日《数据结构与算法》实验教学大纲三、实验目的、内容与要求实验一线性表的创建与访问算法设计(4学时)（一）实验目的数据结构于算法实验是计算机类本科学生计算机软件知识重要的实验环节，它将使学生从实践上学会用高级语言程序设计、实现复杂的数据结构，为大型软件设计奠定基础。

本实验以某种线性表的创建与访问算法设计作为实验内容，举一反三，全面、深刻掌握线性结构的实现方法，培养解决问题的能力。

（二）实验内容1、编写生成线性表的函数，线性表的元素从键盘输入；2、编写在线性表中插入元素的函数；3、编写在线性表中删除元素的函数；4、编写输出线性表的函数；5、编写主函数，调用以上各函数，以便能观察出原线性表以及作了插入或删除后线性表的屏幕输出。

方案一采用顺序存储结构实现线性表。

方案二采用单链表结构实现线性表。

（三）实验要求1、掌握线性结构的机器内表示；2、掌握线性结构之上的算法设计与实现；3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。

实验二二叉树的创建与访问算法设计(4学时)（一）实验目的本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。

（二）实验内容1、编写生成二叉树的函数，二叉树的元素从键盘输入；2、编写在二叉树中插入元素的函数；3、编写在二叉树中删除元素的函数；4、编写遍历并输出二叉树的函数。

方案一采用递归算法实现二叉树遍历算法。

方案二采用非递归算法实现二叉树遍历算法。

（三）实验要求1、掌握树型结构的机器内表示；2、掌握树型结构之上的算法设计与实现；3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。

实验三图的创建与访问算法设计(4学时)（一）实验目的本实验以图的创建与访问算法设计作为实验内容，掌握图型结构的实现方法，培养解决负责问题的能力。

《数据结构与算法》实验指导书湖南理工学院信息与通信工程学院信息工程教研室编写适用专业：信息工程电子信息工程通信工程自动化信息与通信工程学院前言本实验指导书是与《数据结构与算法》（C语言版，郭龙源胡虚怀何光明编著，清华大学出版社）一书配套的实验指导书，实验课时为24课时，共安排有12个实验。

实验设置采取先简后繁、先量少后量大、先精叙后粗讲的原则，建议在教授完第3章栈之后即开始实验，实验的安排应与教学进度相配合。

本实验指导书由湖南理工学院信息与通信工程学院信息工程教研室组织编写，其中邓涛老师编写了实验一至四和实验九至十二，邓涛和李文彬老师合作编写了实验五至八，严太山老师、齐琦老师和吴岳芬老师分别审订了实验一至四、实验五至八和实验九至十二。

2013年4月实验项目设置与内容提要根据各专业培养计划，数据结构与算法课程的实验学时一共安排了24学时。

本课程实验开设12个必修实验（24学时），每个实验都安排有预习内容、课堂实践内容和课后思考内容，要求学生课前学习预习内容，课中完成课堂实践内容，而课后思考内容学生则应根据掌握知识的程度选做。

实验一栈的定义（一）实验学时：2实验类型：综合实验要求：必修一、实验目的本实验作为课程配套实验的第一个实验，旨在帮助学生进一步理解数据结构—栈，并运用已学习的知识实现一个顺序栈。

与此同时，也对复杂程序的设计过程和常见的开发技巧进行一些介绍。

请同学们在学习完教材相关内容后、在阅读预习内容的同时或之后完成课堂实践内容。

二、预习内容1、关于抽象数据类型编写复杂程序或者大型程序是有基本步骤的，如果不按这些步骤来编写，则或者无法按期完成工作，或者完成的工作质量很差。

现在假设我们要编写一本书，例如我们手上的这本《数据结构与算法》教材，那么我们应该怎样来开始我们的工作呢？一般的写作过程是，首先确定这本书要编入哪些内容，这些内容应分布到哪些章节，这样就可以确定出这本书的目录及各章节的内容，然后再开始编写每一章节。

数据结构与算法基础实验指导书实验1 线性表及其应用实验目的1．掌握线性表顺序存储结构的特点及线性表在顺序存储结构中各种基本操作的实现。

2．掌握线性表链式存储结构的特点及线性表在链式存储结构中各种基本操作的实现。

3．重点巩固和体会线性表在链式存储结构上的各种操作和应用。

实验要求对学生要求：1．掌握单向链表的存储特点及其实现。

2．掌握单向链表的插入、删除算法及其应用算法的程序实现。

3．掌握多项式的代数运算算法。

4．根据算法编写与实验内容相关的程序，要求该程序的多项式动态输入输出。

对实验指导教师要求：1．掌握单向链表的存储特点及其实现。

2．掌握单向链表的插入、删除算法及其应用算法的程序实现。

3．编写并运行该题目程序代码，具有该题目的参考答案。

5．深刻理解题目内涵，能够清晰描述问题，掌握该题目涉及的知识点，指导学生实验时需要注意的问题。

实验内容采用链式结构实现任意多项式的存储，求两个多项式的和。

实验评分标准一．课堂表现（10分）1．出勤情况（按时，迟到，早退，缺席）2．是否遵守课堂纪律二．实验结果（50分）1．当堂按时完成（10）2．独立完成（10），（和同学协商完成，在老师帮助下完成）3．结果正确无误（10）4．功能齐全，界面美观，具有较好演示效果（10）5．在源程序中有必要的注释和说明（5）6．程序文档齐全（5）三．实验报告（40）1．对预习要求的回答（10）2．实验过程中遇到的问题如何解决的（10）3．实验的体会（10）4．思考题（10）实验2 树及其应用实验目的1．掌握树的链式存储方式及其操作实现（创建、遍历、查找等）。

2．掌握二叉树用不同方法表示所对应的不同输入形式。

3．掌握二叉树中各种重要性质在解决实际问题中的应用。

4．掌握哈夫曼树的构造方法及其编码方法。

5．掌握二叉排序树的特性及其构造方法。

实验要求对学生要求：1．掌握二叉树的链式存储特点及其实现。

2．掌握二叉树的创建、遍历、查找算法及其程序实现。

数据结构与算法实践作业指导书第一章基本概念与算法效率分析 (2)1.1 算法基本概念 (2)1.2 算法效率评价 (2)1.3 时间复杂度分析 (2)1.4 空间复杂度分析 (3)第二章线性表 (3)2.1 线性表的定义与基本操作 (3)2.2 顺序存储结构 (4)2.3 链式存储结构 (4)2.4 线性表的应用实例 (4)第三章栈与队列 (5)3.1 栈的定义与基本操作 (5)3.2 栈的顺序存储结构 (5)3.3 栈的链式存储结构 (5)3.4 队列的定义与基本操作 (6)第四章树与二叉树 (6)4.1 树的定义与基本操作 (6)4.2 二叉树的定义与性质 (6)4.3 二叉树的遍历算法 (7)4.4 线索二叉树 (7)第五章图 (8)5.1 图的定义与基本概念 (8)5.2 图的存储结构 (8)5.3 图的遍历算法 (8)5.4 最短路径算法 (8)第六章排序算法 (9)6.1 排序算法概述 (9)6.2 冒泡排序 (9)6.3 选择排序 (9)6.4 插入排序 (10)第七章查找算法 (10)7.1 查找算法概述 (10)7.2 顺序查找 (10)7.3 二分查找 (11)7.4 哈希查找 (11)第八章动态规划 (12)8.1 动态规划概述 (12)8.2 最长公共子序列 (12)8.3 最小路径和 (12)8.4 最大子段和 (12)第九章贪心算法 (12)9.1 贪心算法概述 (12)9.2 活动选择问题 (13)9.3 背包问题 (13)9.4 最小树问题 (13)第十章分治算法 (13)10.1 分治算法概述 (13)10.2 快速排序 (13)10.2.1 快速排序算法描述 (14)10.2.2 快速排序算法实现 (14)10.3 归并排序 (14)10.3.1 归并排序算法描述 (14)10.3.2 归并排序算法实现 (14)10.4 最大子数组和问题 (15)10.4.1 分治算法求解最大子数组和问题 (15)10.4.2 最大子数组和问题的分治算法实现 (15)第一章基本概念与算法效率分析1.1 算法基本概念算法是计算机科学中一个核心概念，指的是解决问题的一系列明确且有效的步骤。

综合实践1(数据结构与算法分析)指导书一、目的和要求数据结构与算法分析综合实践不仅是数据结构与算法分析课程的实践教学环节，而且是一门综合性实验项目。

通过这个实践环节，培养学生综合运用数据结构与算法分析基本知识和程序设计基本知识，解决实际问题，提高程序设计与调试程序的能力。

本综合实践的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

具体要求如下：1．学生通过实践掌握线性表、树、图等数据结构的存储结构及算法实现；2．培养利用数据结构知识和基本算法设计方法解决实际问题的能力；3．初步具备查阅资料、分析设计、上机实现和书写科技报告的能力；4．掌握程序测试和调试技术。

二、综合实践的内容及时间安排综合实践要求独立完成，题目自选（参考题目见附录，也可自拟）,但需要老师确认，一人一题，要求有界面进行功能的选择,只能用文件存储数据和处理数据不能使用数据库。

要求在教学周的第16周前完成。

综合实践设计报告内容如下：1、问题描述与分析在该部分先叙述要解决的问题，并给出解决问题的每个模块的功能要求。

2、数据结构设计和基本算法设计方法的选择为完成题目所选择的数据逻辑结构、存储结构及相应算法，说明原因和合理性（主要的成绩考核项，这项内容如果没有，成绩为不合格）。

3、软件结构设计在此说明软件的构架，模块之间的关系。

4、算法设计各个算法的流程图或类C语言描述的算法，算法实现的源程序以及算法分析。

源程序要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

5、调试分析选择测试数据，测试输出的结果，时间复杂度和空间复杂度的分析。

6、总结1）综合实践过程的收获；2）遇到问题以及解决问题的思路和方法；3）程序调试能力的思考；4）在综合实践设计过程中对《数据结构与算法分析》课程的认识等内容。

三、基本要求1、参加综合实践的学生要珍惜机会、勤奋工作、勇于创新、勇于探索、勇于实践，虚心向指导教师请教，向同学学习，独立完成设计任务。

《数据结构》实验指导书软件学院2011年9月概述实习目的和要求《数据结构》在计算机科学中是一门实践性较强的专业基础课, 上机实习是对学生的一种全面综合训练, 是与课堂听讲、自习和练习相辅相成的必不可少的一个教学环节。

实习着眼于原理与应用的结合, 使学生学会把学到的知识用于解决实际问题, 起到深化理解和灵活掌握教学内容的目的。

同时, 通过本课程的上机实习, 使学生在程序设计方法及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

实习包括的步骤1. 简要描述题目要求, 对问题的描述应避开算法及所涉及的数据类型, 只是对所需完成的任务做出明确的陈述, 例如输入数据的类型、值的范围以及输入的形式, 输出数据的类型、值的范围以及输出的形式。

2. 选定数据结构, 写出算法, 根据自顶向下发展算法的方法, 首先描述算法的基本思想, 然后进行算法细化, 再对所设计的算法的时间复杂性和空间复杂性进行简单分析。

3. 准备好上机所需的程序, 选定一种程序设计语言（如C 语言）, 手工编好上机程序, 并进行反复检查, 使程序中的逻辑错误和语法错误减少到最低程度。

对程序中有疑问的地方, 应做出标记, 以便在上机时给予注意。

4．上机输入和调试程序, 在调试程序过程中除了系统的问题以外, 一般应自己独立解决。

在程序调试通过后, 打印输出程序清单和运行结果。

5．上机结束后, 总结和整理实习报告。

实习报告的内容1．简述题目要解决的问题是什么, 并说明输入和输出数据的形式。

2．简述存储结构和算法的基本思想。

3．列出调试通过的源程序。

4．列出上面程序对应的运行结果。

分析程序的优缺点、时空性能以及改进思想, 写出心得体会。

实验一线性表一. 目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现, 提高分析和解决问题的能力。

要求仔细阅读并理解下列例题, 上机通过, 并观察其结果, 然后独立完成后面的实习题。

数据结构实验指导书实验一线性表[实验目的]1．了解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。

2．了解单链表的结构特点及有关概念，掌握单链表建立、插入、删除的基本操作算法。

[实验内容]1．顺序表的实践。

1)建立4个元素的顺序表list[]={2，3，4，5}，实现顺序表建立的基本操作。

2)在list[]={2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。

3)在list[]={2，3，4，9，5}中删除指定位置（i=3）上的元素9，实现顺序表的删除的基本操作。

2．单链表的实践。

1)建立一个包括头结点和3个结点的（4，2，1）的单链表，实现单链表建立的基本操作。

2)在已建好的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。

3)在一个包括头结点和4个结点的（4，2，3，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。

[实验要点及说明]线性表（linear list）是n（n≥0）个数据元素a1，a2，…a n组成的有限序列。

其中n 称为数据元素的个数或线性表的长度，当n=0时称为空表，n>0时称为非空表。

通常将非空的线性表记为（a1，a2，…,a n），其中的数据元素a i（1≤i≤n）是一个抽象的符号，a i是第i个数据元素,称i为数据元素a i在线性表中的位置。

其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。

顺序表也称为线性表的顺序存储结构。

其存储方式为：在内存中用一组地址连续的存储单元依次存储线性表的数据元素，但该连续存储空间的大小要大于或等于顺序表的长度。

一般让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。

可定义顺序表如下：#define maxnumelemtype list[maxnum];int num=-1;线性表的链式存贮结构，也称为链表。