09级《数据结构》实验指导书

《数据结构实验指导书》潘向辉/吴学毅编写印包学院数字媒体技术专业2011年3月实验说明【实验环境】操作系统：Microsoft Windows XP/2000。

编程语言：C语言【实验要求】1.实验前，了解实验目的、实验内容及相关的基本理论知识，并按照实验内容要求设计程序流程，书写预习报告；2.本课程实验均为单人单组，独立完成；3.实验所用计算机固定，以便实现实验之间的延续性；4.按要求完成实验内容，在实验结束后按照格式和规范撰写实验报告。

【实验项目及学时分配】1．实验报告撰写符合格式及规范要求，详见实验报告撰写格式及规范；2．本课程实验占课程总成绩的15%。

实验（一）线性表一、实验项目名称：线性表课时：4学时二、实验要求1、掌握顺序表的定义与实现，包括查找、插入、删除算法的实现；2、掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构；三、实验环境Widows操作系统、C语言四、实验内容（1）顺序表建立一如下表所示的学生信息表使用结构体，用顺序表完成以下内容：1.初始化线性表为空；2.依次输入数据元素；（由键盘输入）3.完成数据元素的插入、删除操作；4.取第i个数据元素；5.依次显示当前线性表中的数据元素。

（2）单链表建立一个单链表，依次输入数据元素0～9。

使用结构体，用单链表完成以下内容：1.初始化单链表；2.在单链表指定位置插入一个数据元素；3.删除指定位置的一个数据元素；4.取第i个数据元素；5.查找数据元素x 是否在单链表中；6.销毁单链表；五、思考题：在什么情况下使用顺序表比链表好？实验（二）栈和队列一、实验项目名称：栈和队列课时：2学时二、实验要求1、掌握栈的顺序表示、链表表示以及相应操作的实现。

特别注意栈空和栈满的条件；2、掌握队列的顺序表示、链表表示以及相应操作的实现。

特别是循环队列中队头与队尾指针的变化情况；三、实验环境Widows操作系统、VC6.0四、实验内容分别使用顺序循环队列和堆栈以及链式队列和堆栈编写程序：判断一个字符序列是否是回文。

《数据结构》实验教学指导书数据结构是计算机课程的一门重要的基础课，它的教学要求大致有三个重要方面：其一就是让学生学会分析研究计算机加工的数据对象的特性，以便为数据选择适当的物理结构和逻辑结构；其二，根据结构，选择适当的算法，并初步掌握算法的时间分析和空间分析；其三，学习复杂的程序设计。

基于以上的三点要求，在整本书中贯穿这样的中心思想：让读者通过数据结构的实验课，理论结合实践，达到这三点要求。

读者在使用这本书时，要以这三点要求为出发点，力求理解结构、掌握算法、读懂程序。

本书每个实验，都给出了明确的实验目的、简明的实验原理，限于篇幅，没有给出详细的说明，事实上也没有必要。

因为这些读者可以从课堂和书本上得到。

所以读者应该详细的读懂书上的相关部分，然后依据本书认真实验。

考虑到读者的水平的差异，本书给出了参考程序，所有的参考程序都已在TURBO C2.0上通过编译，结果正确，可以参考。

但是在上机时，应当注意避免输入参考程序了事，应当事先编写自己的程序，上机调试，参考程序只是用做参考。

另外，有些参考程序也不是最佳的，应对之进行改进处理。

实验时，还应多多考虑怎样将每一个实验应用到实际当中去，举一反三，可以不必拘泥于某一个实验，要前后贯通，注意对基本的数据结构的理解和普遍的算法的研究。

目录实验一熟悉C语言 (5)实验二线性表 (9)实验三栈 (14)实验四串 (17)实验五数组和广义表 (20)实验六树的操作（二叉树及其先序遍历） (24)实验七图的操作（邻接表的建立） (28)实验八排序 (33)数据结构课程名称：数据结构英文名称：Data Structures设置形式：非独立设课课程模块：专业核心课实验课性质：专业实验课程编号：501816课程负责人：邱秀伟大纲主撰人：邱秀伟大纲审核人：李焕勤一、学时、学分课程总学48实验学时：16课程学分：3时：二、适用专业及年级教育技术学三、课程目标与基本要求本课程学习的目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。

《数据结构实验》实验指导书及答案信电工程学院计算机科学和技术教研室编2011.12数据结构实验所有代码整理作者郑涛声明：在这里我整理了数据结构实验的所有代码，希望能对大家的数据结构实验的考试有所帮助，大家可以有选择地浏览，特别针对一些重点知识需要加强记忆（ps:重点知识最好让孙天凯给出），希望大家能够在数据结构实验的考试中取得令人满意的成绩，如果有做的不好的地方请大家谅解并欢迎予以指正。

实验一熟悉编程环境实验预备知识：1．熟悉本课程的语言编译环境（TC或VC），能够用C语言编写完整的程序，并能够发现和改正错误。

2．能够灵活的编写C程序，并能够熟练输入C程序。

一、实验目的1．熟悉C语言编译环境，掌握C程序的编写、编译、运行和调试过程。

2．能够熟练的将C程序存储到指定位置。

二、实验环境⒈硬件：每个学生需配备计算机一台。

⒉软件：Windows操作系统+Turbo C；三、实验要求1．将实验中每个功能用一个函数实现。

2．每个输入前要有输入提示（如：请输入2个整数当中用空格分割：），每个输出数据都要求有内容说明（如：280和100的和是：380。

）。

3．函数名称和变量名称等用英文或英文简写（每个单词第一个字母大写）形式说明。

四、实验内容1．在自己的U盘中建立“姓名+学号”文件夹，并在该文件夹中创建“实验1”文件夹（以后每次实验分别创建对应的文件夹），本次实验的所有程序和数据都要求存储到本文件夹中（以后实验都按照本次要求）。

2．编写一个输入某个学生10门课程成绩的函数（10门课程成绩放到结构体数组中，结构体包括：课程编号，课程名称，课程成绩）。

3．编写一个求10门成绩中最高成绩的函数，输出最高成绩和对应的课程名称，如果有多个最高成绩，则每个最高成绩均输出。

4．编写一个求10门成绩平均成绩的函数。

5．编写函数求出比平均成绩高的所有课程及成绩。

#include<stdio.h>#include<conio.h>struct subject{int subject_id;char subject_name[20];double subject_grades;};struct subject sub[10];void input(){int i;printf("please input:\n");for(i=0;i<10;i++){scanf("%d %s %lf",&sub[i].subject_id,&sub[i].subject_name,&sub[i].subject_g rades);}printf("you just input:\n");for(i=0;i<3;i++){printf("%d %s %lf\n",sub[i].subject_id,sub[i].subject_name,sub[i].subject_g rades);}}void subject_max(){int i,flag;double max=sub[0].subject_grades;for(i=0;i<10;i++){if(sub[i].subject_grades>max)max=sub[i].subject_grades;flag=i;}printf("The high score of subjectis %s %lf\n",sub[flag].subject_name,max);}void subject_average(){int i;double average,sum=sub[0].subject_grades;for(i=1;i<10;i++){sum+=sub[i].subject_grades;}average=sum/10;printf("subject's average is %lf\n",average);}void subjct_gtaverage(){int i,flag;double average,sum=sub[0].subject_grades;for(i=1;i<10;i++){sum+=sub[i].subject_grades;}average=sum/10;for(i=0;i<10;i++){if(sub[i].subject_grades>average){flag=i;printf("subject greater than average is %s %lf\n",sub[flag].subject_name,sub[flag].subject_grades);}}}int main(){input();subject_max();subject_average();subjct_gtaverage();return 0;}实验二顺序表的基本操作实验预备知识：1．熟练运用数组进行程序设计，掌握数组名和指针作为函数参数。

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

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

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

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

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

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

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

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

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

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

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

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

《数据结构》实验指导书第一部分前言一、实验的目的《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。

本课程的另一重要教学目的是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，要做到这一点，上机实习是必须的。

数据结构实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。

通常，实验课题中的问题比平时的习题复杂得多，也更接近实际。

实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，训练学生实际动手进行程序设计和调试程序的能力，加深对数据结构相关概念和算法的理解。

通过完成本实验课程的实验，学生应学会并掌握本课程的基本和重点知识，深刻理解逻辑结构、物理结构和算法设计之间的关系，初步学会算法分析的方法，并能在一定范围内运用所掌握的分析方法进行算法分析，培养软件工作所需要的动手能力和作为一个软件工作者所应具备的科学工作方法和作风。

二、实验前的准备工作1．每个学生需配备一台计算机，操作系统需Windows2000/XP以上版本，软件需Visual C++6.0以上版本。

2．实验前要求学生按实验要求编写好相关实验程序，准备上机调试运行。

三、实验的步骤（一）建立一个文件夹，如“数据结构”，用来存放自己的所有实验程序，在该文件夹中建立子目录用来存放每个项目（一个子目录一个项目），如“顺序表”，项目中需要的所有文件都存在该文件夹中。

（二）新建一个项目文件1．双击Visual C++ 6.0快捷图标，进入Visual C++ 6.0集成开发环境；或者点击“开始”→“程序”→“Microsoft Visual Studio 6.0”→“Microsoft Visual C++ 6.0”进入Visual C++ 6.0集成开发环境。

2．单击“File”菜单，选择“New”命令3．创建一个项目文件并保存在项目所在文件夹中；3. 创建源程序文件并保存在项目所在文件夹中；4．输入源程序；5．单击“保存”按钮保存源程序。

《数据结构》实训指导书实训一线性表基本操作算法设计一、实训目的与要求1、掌握线性表的顺序存储结构的实现及其基本操作的算法设计；2、掌握线性表的链式存储结构的实现及其基本操作的算法设计；3、掌握算法转化为C程序的方法。

二、实训内容1、根据线性表L=(a,b,c,d,e,f)，编写程序建立其顺序存储结构并完成插入或删除操作。

2、根据线性表L=(a,b,c,d,e,f)，编写程序建立其链式存储结构并完成插入或删除操作。

三、实训步骤1、根据算法设计编写源程序；2、输入并编辑源程序；3、运行并分析程序；四、实训总结与体会[根据本次实训过程，总结你对线性表基本操作算法设计的基本体会]实训二栈和队列基本操作的算法设计一、实训目的与要求1、掌握栈的基本操作算法设计的实现；2、掌握队列的基本操作算法设计的实现。

二、实训内容1、根据栈S=(a,b,c,d,e)，建立其顺序存储结构或链式存储结构，并完成对该栈的进栈或出栈操作；2、根据队列Q=(a,b,c,d,e)，建立其顺序存储结构或链式存储结构，并完成对该队列的进队或出队操作；三、实训步骤1、根据算法编写源程序；2、输入并编辑源程序；3、调试、分析程序。

四、实训总结[根据本次实训内容和过程，总结你对栈、队列的基本操作算法设计的体会]实训三二叉树的遍历算法设计一、实训目的与要求1、掌握二叉树的链式存储结构的算法实现；2、掌握遍历二叉树的算法实现。

二、实训内容1、根据算法编写程序建立下图所示二叉树的链式存储结构（建立二叉链表）；2、根据算法编写程序完成对该二叉树的中序遍历（或先序遍历、后序遍历）。

三、实训步骤1、根据算法编写程序；2、输入并编辑程序；3、运行并分析程序。

四、实训总结与体会【根据本次实训内容及过程，简述对二叉树存储结构的实现及遍历二叉树算法设计的体会】实训四图的存储及遍历算法设计一、实训目的与要求1、掌握图的邻接矩阵、邻接表存储结构的算法实现；2、掌握图的遍历算法设计。

引言概述正文内容
1.实验环境配置
1.1硬件要求
计算机硬件配置要求
操作系统要求
附加硬件设备要求（如虚拟机等）
1.2软件要求
编程语言要求（如C/C++、Java等）开发环境配置（如IDE、编译器等）1.3实验库和工具
实验需要使用的库文件和工具
如何获取和配置实验库和工具
2.实验内容介绍
2.1实验目标和背景
数据结构实验的作用和意义
实验背景和相关应用领域介绍
2.2实验概述
实验内容的大致流程和步骤
实验中可能遇到的问题和挑战
2.3实验要求
对学生实验流程和实验结果的要求
实验过程中需要注意的事项和技巧
3.实验步骤
3.1实验准备
配置实验环境
获取实验所需数据和文件
3.2实验具体步骤
根据实验要求将数据结构知识应用到具体问题中根据实验要求实现相应的算法和数据结构
3.3实验示例代码
提供示例代码以供学生参考和学习
解析示例代码中的关键步骤和实现细节
4.实验答案
4.1实验题目
实验题目及相关说明
确定实验的具体要求和目标
4.2实验答案解析
对实验答案的具体实现进行解析
对实验中可能遇到的问题和错误进行分析和解决4.3实验答案示例
提供实验答案的示例代码
解析实验答案中的关键实现步骤和说明
5.实验总结
5.1实验成果评估
对学生实验成果进行评估
分析实验结果的优点和不足
5.2实验心得
学生对本次实验的收获和感想
学生对未来实验的建议和展望
总结。

《数据结构》实验指导书姚建绩编北方民族大学计算机科学与工程学院2009年8月目录实验一：线性表的实现（设计，2学时） 3 实验二：顺序栈、链栈的实现（设计，2学时）7 实验三：队列的实现（设计，2学时）9 实验四：特殊矩阵的压缩存储实现及访问（设计，2学时）11 实验五：二叉树的存储和实现（设计，2学时）13 实验六：图的存储和实现（设计，2学时）14 实验七：常用排序算法的实现（设计，2学时）15 实验八：基本查找算法的实现（设计，2学时）16课程编号：11100713 课程类别：专业基础课适用专业：计算机科学与技术、软件工程、网络工程、信息管理与信息系统课程总学时：80 实验学时：16开设实验项目数：8实验一：线性表的实现（设计，2学时）一、实验目的与要求1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。

2.掌握线性表的顺序存储结构的定义及C语言实现。

3.掌握线性表的链式存储结构——单链表的定义及C语言实现。

4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。

5.掌握线性表在链式存储结构——单链表中的各种基本操作。

二、实验环境安装有Visual C++6.0或其它C编译环境的PC机一台。

三、实验预习与准备1．复习教材相关章节内容。

2．复习C语言中关于结构体与指针的相关内容。

3．认真阅读实验题目，事先写好程序。

四、实验内容和步骤实验题目1：实现顺序表各种基本运算的算法。

编写一个程序，实现顺序表的各种基本运算，以下各功能分别用一个函数来实现，并在此基础上设计一个主函数进行验证各函数的正确性：（1）初始化顺序表L。

（必做）（2）输出顺序表L。

（必做）（3）输出顺序表L的长度。

（必做）（4）判断顺序表L是否为空。

（5）输出顺序表L的第i个元素的值。

（6）输出元素x的位置。

（7）在第i个元素位置上插入x元素。

（8）删除L的第i个元素。

（9）删除L中值为x的元素。

注：（1）～（3）为必做的内容，（4）～（9）可任选两个。

《数据结构》课程实验指导《数据结构》实验教学大纲课程代码：0806523006 开课学期：3 开课专业：信息管理与信息系统总学时/实验学时：64/16 总学分/实验学分：3.5/0.5一、课程简介数据结构是计算机各专业的重要技术基础课。

在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。

数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。

通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。

另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

二、实验的地位、作用和目的数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。

另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。

三、实验方式与基本要求实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。

具体实验要求如下：1.问题分析充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。

2.数据结构设计针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。

对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。