数据结构上机实验指导

数据结构与算法实验指导书中国石油大学(北京)计算机科学与技术系前言《数据结构》是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。

它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。

这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。

通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。

学习这门课程，习题和实验是两个关键环节。

学生理解算法，上机实验是最佳的途径之一。

因此，实验环节的好坏是学生能否学好《数据结构》的关键。

为了更好地配合学生实验，特编写实验指导书。

一、实验目的更好的理解算法的思想、培养编程能力。

二、实验要求1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。

2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。

3、实验结束后总结实验内容、书写实验报告。

4、遵守实验室规章制度、不缺席、按时上、下机。

5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。

6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。

三、实验环境 VC++6.0或者VC2010四、说明1、本实验的所有算法中元素类型可以根据实际需要选择。

2、实验题目中带＊者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。

3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。

五、实验报告的书写要求1．明确实验的目的及要求；2．记录实验的输入数据和输出结果；3．说明实验中出现的问题和解决过程；4．写出实验的体会和实验过程中没能解决的问题；六、参考书目《数据结构》（C++语言描述）王红梅等清华大学出版社《DATA STRUCTURE WITH C++》 William Ford,William Topp清华大学出版社（影印版）实验平台控制台程序1、启动Microsoft VC6.0集成开发环境如图所示：2、单击“文件”菜单，选择“新建”项。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二．例题[问题描述]用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。

数据结构教程上机实验指导第六版数据结构是计算机科学中非常重要的一门课程，它研究的是数据在计算机中的存储和组织方式。

通过学习数据结构，可以更好地理解和利用计算机系统中的数据，提高程序的效率和性能。

在数据结构教程的第六版上，为了帮助学生更好地理解和应用所学知识，设计了一系列的实验指导。

这些实验涵盖了数据结构的各个方面，旨在通过实践来加深对理论知识的理解，并培养学生的问题解决能力和实践能力。

在第六版的实验指导中，首先介绍了数据结构的基本概念和常用的数据结构类型，如数组、链表、栈、队列、树、图等。

然后，通过实验来演示和应用这些数据结构，让学生能够真正地理解它们的特点和用途。

第一章的实验指导是关于数组和链表的，学生需要实现一个简单的数组和链表，并比较它们在插入、删除和查找等操作上的性能差异。

通过这个实验，学生可以明确了解到数组和链表的优缺点，并能够根据实际情况选择合适的数据结构。

第二章的实验指导是关于栈和队列的，学生需要实现一个栈和一个队列，并利用它们解决一些实际问题，如括号匹配、表达式求值等。

通过这个实验，学生可以掌握栈和队列的基本操作和应用场景。

第三章的实验指导是关于树的，学生需要实现一个二叉树和一个二叉查找树，并利用它们实现一些常用的操作，如插入、删除、查找、遍历等。

通过这个实验，学生可以了解到树的基本结构和算法，并掌握二叉查找树的原理和应用。

第四章的实验指导是关于图的，学生需要实现一个图和一个图的遍历算法，并利用它们解决一些实际问题，如最短路径问题、拓扑排序等。

通过这个实验，学生可以了解到图的基本概念和算法，培养解决复杂问题的能力。

除了以上的实验指导，第六版的数据结构教程还包括了一些扩展实验，如动态存储分配、排序算法、查找算法等。

这些实验可以帮助学生进一步巩固和拓展所学知识，并提供更多的实践机会。

第六版的数据结构教程上机实验指导是一份很有价值的学习资料。

通过实验指导，学生可以通过实践来巩固和应用所学的数据结构知识，提高问题解决能力和实践能力。

实验一单链表的基本操作（必做）一、实验目的1.掌握单链表的存储、初始化、插入、删除等操作的程序实现。

2.加深对单链表基本概念,基本理论及相应算法的掌握与理解。

3.了解链表的处理方式，学习体会简单的单链表程序实现相关知识。

二、实验内容1.建立一个链表、设计链表的基本操作实现算法、输出一个链表表，调试并输出结果。

2.编写一个程序实现如下功能：让计算机产生出50个0~9之间的随机数并依次保存到单链表中;输出遍历单链表；从单链表中删除与给定值相等的所有结点；输出遍历单链表；输出单链表长度，调试并输出结果。

三、实验步骤1.定义一个链表结构体。

2.利用插入功能插入一个结点。

3.利用删除功能删除一个结点。

四、程序运行测试1.利用插入功能插入一个结点。

2.利用删除功能删除一个结点。

五、实验报告要求1.绘制链表操作实现的流程图。

2.详细给出程序运行测试结果（包括测试数据和测试结果）。

3.选试验步骤2-3中的任意一个，给出程序的详细注释。

4.参考程序中某一部分功能的改进（选做）5.实验心得与体会6.附录，实验用源程序六、参考源代码#include <iostream.h>#include <malloc.h>typedef struct LNode{int data;struct LNode *next;}Lnode, *LinkList;//假设下面的单链表均为带头结点。

void CreatLinkList(LinkList &L,int j){//建立一个单链表L,数据为整数，数据由键盘随机输入。

LinkList p,q;L=(LinkList )malloc(sizeof(Lnode));L->next=NULL;q=L;cout<<"在单链表内输入整数："<<endl;for(int i=0;i<j;i++) p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data;p->next=q->next;q->next=p;q=p; }int PrintLinkList(LinkList &L){//输出单链表L的数据元素LinkList p;p=L->next;if(L->next==NULL){cout<<"链表没有元素!"<<endl;return 0;}cout<<"单链表的数据元素为:";while(p){cout<<p->data<<" ";p=p->next;}cout<<endl;return 1;}void LinkListLengh(LinkList &L){//计算单链表L的数据元素个数。

程序设计是实践性很强的过程，任何程序最终都必须在计算机上运行，以检验程序的正确与否。

因此在学习程序设计中，一定要重视上机实践环节，通过上机可以加深理解C语言的有关概念，以巩固理论知识，另一方面也可以培养程序调试的能力与技巧。

一．C语言程序的上机步骤按照C 语言语法规则而编写的C 程序称为源程序。

源程序由字母、数字及其它符号等构成，在计算机内部用相应的ASCII 码表示，并保存在扩展名为“．C”的文件中。

源程序是无法直接被计算机运行的，因为计算机的CPU 只能执行二进制的机器指令。

这就需要把A SCII 码的源程序先翻译成机器指令，然后计算机的CPU 才能运行翻译好的程序。

源程序翻译过程由两个步骤实现：编译与连接。

首先对源程序进行编译处理，即把每一条语句用若干条机器指令来实现，以生成由机器指令组成的目标程序。

但目标程序还不能马上交计算机直接运行，因为在源程序中，输入、输出以及常用函数运算并不是用户自己编写的，而直接调用系统函数库中的库函数。

因此，必须把“库函数”的处理过程连接到经编译生成的目标程序中，生成可执行程序，并经机器指令的地址重定位，便可由计算机运行，最终得到结果。

C 语言程序的调试、运行步骤可以用图A-1 表示：图A-1 C 语言程序的调试、运行步骤图A-1 中，虚线表示当某一步骤出现错误时的修改路线。

运行时，无论是出现编译错误、连接错误，还是运行结果不对（源程序中有语法错误或逻辑错误），都需要修改源程序，并对它重新编译、连接和运行，直至将程序调试正确为止。

除了较简单的情况，一般的程序很难一次就能做到完全正确。

在上机过程中，根据出错现象找出错误并改正称为程序调试。

我们要在学习程序设计过程中，逐步培养调试程序目标程序的能力，它不可能靠几句话讲清楚，要靠自己在上机中不断摸索总结，它可以说是一种经验积累。

程序中的错误大致可分为三类：²程序编译时检查出来的语法错误；²连接时出现的错误；²程序执行过程中的错误。

〈数据结构〉上机实验指导数据结构是计算机科学中的一门重要课程，它研究的是数据的组织、存储和管理方式，以及对数据进行操作和处理的算法。

上机实验是数据结构课程的重要组成部分，通过实践操作，能够更好地理解和掌握数据结构的基本概念、算法和应用。

在进行〈数据结构〉上机实验之前，首先需要准备实验环境。

通常情况下，我们会使用一种编程语言来实现数据结构的相关操作，比如C++、Java等。

根据自己的实际情况和实验要求，选择一种合适的编程语言，并确保在实验环境中已经正确安装了相应的编译器或解释器。

接下来，我们可以开始进行具体的上机实验了。

下面以链表为例，介绍一下〈数据结构〉上机实验的指导步骤和要求：1. 实验目的：掌握链表的基本概念、操作和应用，理解链表与数组的区别和联系。

2. 实验原理：链表是一种动态数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。

链表的特点是插入和删除操作的时间复杂度为O(1)，但是查找操作的时间复杂度为O(n)。

3. 实验步骤：3.1 创建链表：首先，我们需要定义一个链表的结构体，包含数据和指针两个成员变量。

然后，通过动态内存分配来创建链表的节点，并将节点之间通过指针连接起来，形成一个完整的链表。

3.2 插入节点：可以在链表的任意位置插入一个新的节点。

插入节点的操作包括：创建一个新的节点，将新节点的指针指向插入位置的下一个节点，将插入位置的前一个节点的指针指向新节点。

3.3 删除节点：可以删除链表中的任意一个节点。

删除节点的操作包括：将要删除的节点的前一个节点的指针指向要删除的节点的下一个节点，然后释放要删除的节点的内存空间。

3.4 遍历链表：可以通过遍历链表来访问链表中的每一个节点，并对节点进行相应的操作。

遍历链表的操作包括：从链表的头节点开始，依次访问每个节点，直到链表的尾节点。

3.5 查找节点：可以根据节点的值来查找链表中的某一个节点。

查找节点的操作包括：从链表的头节点开始，依次比较每个节点的值，直到找到目标节点或者链表结束。

数据结构教程上机实验指导第六版一、引言《数据结构教程上机实验指导》是数据结构课程的实践操作指南，旨在帮助学生通过实际操作加深对理论知识的理解，提高编程技能和解决问题的能力。

本书适用于高等院校计算机专业的学生，也可供数据结构爱好者参考。

二、实验内容本书包含了一系列实验，涵盖了各种常见的数据结构，如数组、链表、栈、队列、树、图等。

每个实验都包括实验目的、实验环境、实验步骤和实验报告四个部分。

1.实验目的：每个实验都有明确的目的，旨在帮助学生掌握特定数据结构的实现方法、操作技巧和性能分析。

2.实验环境：提供了实验所需的环境配置和软件版本，确保学生在合适的环境下进行实验。

3.实验步骤：详细说明了实验的步骤和方法，引导学生逐步完成实验。

4.实验报告：要求学生提交实验报告，包括对实验结果的总结和分析，以及遇到的问题和解决方案。

三、实验示例本书提供了多个实验示例，包括各种数据结构的实现和应用。

以下是一个简单的链表插入操作的示例：假设我们有一个简单的链表，包含节点A、B和C。

现在要求在B 节点后插入一个新的节点D。

按照链表插入操作的规则，我们需要找到B的下一个节点（即C），然后将D连接到C后面即可。

具体步骤如下：（1）创建一个新的节点D；（2）找到B的下一个节点C；（3）将D连接到C后面，即修改C的下一个节点指针指向D；（4）返回链表。

通过这个示例，学生可以更好地理解链表插入操作的原理和实现方法。

四、实验总结通过本书的实验，学生可以加深对数据结构理论知识的理解，提高编程技能和解决问题的能力。

同时，学生还可以通过实践发现自己的不足之处，及时调整学习策略，提高学习效果。

五、参考文献在本书的最后，列出了与数据结构相关的参考文献，包括教材、论文、网站等。

这些参考文献为学生提供了更多的学习资源，有助于他们进一步了解数据结构的相关知识。

六、结语《数据结构教程上机实验指导》是一本非常实用的实践指南，对于学习数据结构的学生来说非常有帮助。

数据结构实验指导书数据结构实验指导书目录数据结构实验指导书 (1)目录 (1)实验指导书概述 (2)上机实验题目 (3)实验一 C语言相关知识复习 (3)一、实验目的 (3)二、实验内容 (3)实验二单链表的插入、删除 (3)一、实验目的 (3)二、实验内容 (3)三、实现提示 (4)实验三栈及其应用 (5)一、实验目的 (5)二、实验内容 (5)实验四二叉树的递归算法 (6)一、实验目的 (6)二、实验内容 (6)实验五图的遍历 (7)一、实验目的 (7)二、实验内容 (7)实验六有序表的查找 (7)一、实验目的 (7)二、实验内容 (7)实验七哈希表 (7)一、实验目的 (7)二、实验内容 (7)实验八内部排序算法的应用 (8)一、实验目的 (8)二、实验内容 (8)实验指导书概述“数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。

本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。

本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。

由于以下原因，使得掌握这门课程具有较大难度：∙内容多，时间短，给学习带来困难；∙贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点；∙隐含在各部分的技术和方法丰富，也是学习的重点和难点；∙先修课程中所介绍的专业性知识不多，加大了学习难度。

由于数据结构课程的技术性与实践性，《数据结构课程实验》的设置十分必要。

为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。

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

通过上机实践，使学生在可能短的时间内对数据结构知识的实践和应用有一个比较全面和系统的认识，达到理论与实践相结合的目的。

数据结构上机实验报告学院：电子工程学院专业：信息对抗技术姓名：学号：教师：饶鲜日期：目录实验一线性表 ........................................................................................................ - 4 -一、实验目的.................................................................................................... - 4 -二、实验代码.................................................................................................... - 4 -三、实验结果.................................................................................................. - 14 -四、个人思路.................................................................................................. - 15 - 实验二栈和队列 .................................................................................................. - 15 -一、实验目的.................................................................................................. - 15 -二、实验代码.................................................................................................. - 16 -三、实验结果.................................................................................................. - 24 -四、个人思路.................................................................................................. - 25 - 实验三数组 .......................................................................................................... - 26 -一、实验目的.................................................................................................. - 26 -二、实验代码.................................................................................................. - 26 -三、实验结果.................................................................................................. - 28 -四、个人思路.................................................................................................. - 28 - 实验四树 .............................................................................................................. - 29 -一、实验目的.................................................................................................. - 29 -二、实验代码.................................................................................................. - 29 -三、实验结果.................................................................................................. - 39 -四、个人思路.................................................................................................. - 39 -实验一线性表一、实验目的1．熟悉线性表的顺序和链式存储结构2．掌握线性表的基本运算3．能够利用线性表的基本运算完成线性表应用的运算二、实验代码1．设有一个线性表E={e1, e2, … , e n-1, e n}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ e n, e n-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。

数据结构上机实验指导书计算机系第一部分数据结构课程实验概述一. 实验目的《数据结构》是计算机专业的主干课程和必修课程之一，其目的是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表示方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法，要求掌握算法的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复杂程序设计的技能。

在计算机科学领域，尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程序编制水平有很大的帮助。

二. 实验要求2.1实验步骤设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有效地减少错误，提高工作效率。

因此必须严格执行良好的实验步骤规范（包括上机操作规范）。

本课程实验的基本步骤是：2.1.1问题分析充分地分析和理解问题本身，明确问题要求做什么。

对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。

例如;输入、输出数据的类型、值的范围以及形式等。

同时为调试程序准备好测试数据，包含合法的输入数据和非法形式输入的数据。

2.1.2设计和编码设计即是对问题描述中涉及的操作对象定义相应的数据类型, 序模块定义主程和各抽象数据类型；定义相应的存储结构并写出各过程和函数的伪码算法。

在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。

编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程序。

对程序中的疑问应作出记号，以便上机时注意解决。

每个明确的功能模块程序一般不超过60行，程序的每一行不得超过60个字符，否则要进一步划分。

2.1.3上机前程序静态检查上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓错误。

静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。

实验1 线性表顺序存储结构实现3.1实验目的和要求掌握线性表的结构性质及其链式存储结构各种操作的实现；3.2实验内容用C#编程实现线性表的链式存储结构及各种操作，尤其要实现任意位置元素的插入和删除操作。

3.3实验指导1、建立控制台应用程序，创建结点类Node<T>和链式顺序表类SepLinkedList<T>，结点类Node<T>包括两个字段成员_data和_next，分别表示该结点的结点元素和下一结点；包括两个属性成员Data和Next，分别完成对_data和_next读写；3个构造函数 Node()、Node(T data)、Node(Node<T> next)，分别表示创建无参数的对象、参数为T类型数据的对象、参数为Node<T>类型结点的对象。

链式顺序表类SepLinkedList<T>包括1个私有字段成员_head-头指针；包括1个属性成员Head，完成对_head读写；包括一系列操作方法成员；2、在主入口函数中创建类的实例，对该实例完成各种操作，每次操作完结果进行输出。

3.4部分程序参考代码结点类Public class Node<T>{private T _data;public T Data{get { return _data; }set { _data = value; }}private Node<T> _next;public Node<T> Next{get { return _next; }set { _next = value; }}public Node(){_data = default(T);_next = null;}public Node(T data){_data = data;_next = null;}public Node(Node<T> next) {_next = next;}}单链表类Public class SepLinkedList<T>{private Node<T> _head;///头指针public Node<T> Head{get { return _head; }set { _head = value; }}///获取单链表长度public int GetLength(){Node<T> p = _head;int length = 0;while (p != null){length++;p = p.Next;}return length;}///清空单链表public void Clear(){_head = null;}判断链表是否为空public bool IsEmpty(){if (_head == null){return true;}else{return false;}}///链表末尾追加数据元素public void Append(T item){Node<T> p = new Node<T>();Node<T> q = new Node<T>(item);if (_head == null){_head = q;return;}p = _head;while (p.Next != null){p = p.Next;}p.Next = q;}///删除第i个数据元素public T Delete(int i){该部分代码自己实现}Node<T> p = _head;int j = 1;while (p.Next != null && j < i) {j++;q = p;p = p.Next;}if (j == i){q.Next = p.Next;return p.Data;}else{Console.WriteLine("该位置不存在结点");return default(T);}}///在第i个位置前插入数据元素public void Insert(T item, int i){该部分代码自己实现}///读取第i位置元素public T GetElem(int i){if (IsEmpty()){Console.WriteLine("链表为空");return default(T);}Node<T> p = new Node<T>();p = _head;int j = 1;while (p.Next != null && j < i){p = p.Next;j++;}if (j == i){return p.Data;}else{Console.WriteLine("未找到该序号的结点");return default(T);}///按值查找数据元素public int Locate(T item){if (IsEmpty()){Console.WriteLine("链表为空");return -1;}Node<T> p = new Node<T>();p = _head;int i = 1;while ( p != null && !item.Equals(p.Data)) {p = p.Next;i++;}if (p != null){return i;}else{Console.WriteLine("单链表中不存在指定数据元素");return -1;}}}2.2.3 单链表的建立:第一种方式:(采用从尾部加入结点的方式)///建立单链表static SepLinkedList<int> CreateLinkedList(){SepLinkedList<int> result = new SepLinkedList<int>(); Node<int> r = new Node<int>();r = result.Head;int elem = Int32.Parse(Console.ReadLine());while (elem != -1)//以-1做为结束标志{Node<int> p = new Node<int>(elem);if (result.Head == null){result.Head = p;}else{r.Next = p;//加入链表}r = p; //记下最后一个结点elem = Int32.Parse(Console.ReadLine());}if (r != null){r.Next = null;//最后一个节点地址域置空}return result;}第二种方式:(采用在头部加入结点的方式)static SepLinkedList<int> CreateSepLinkedList(){SepLinkedList<int> result = new SepLinkedList<int>();int d = Int32.Parse(Console.ReadLine());while (d != -1){Node<int> elem = new Node<int>(d);elem.Next = result.Head;result.Head = elem;d = Int32.Parse(Console.ReadLine());}return result;}。

《数据结构》上机实验的目的和要求通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写及调试程序的能力。

要求所编的程序能正确运行，并提交实验报告。

实验报告的基本要求为：1、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：（1）输入的形式和输出值的范围；（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输入输出结果和错误的输入及输出结果。

2、概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。

3、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。

4、调试分析：（1）调试过程中所遇到的问题及解决方法；（2）算法的时空分析；（3）经验与体会。

5、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。

6、测试结果：列出对于给定的输入所产生的输出结果。

若有可能，测试随输入规模的增长所用算法的实际运行时间的变化。

实验一 C++程序设计基础一、目的：回顾C++程序设计的基本知识，掌握算法时间复杂性和空间复杂性分析。

二、要求：掌握指针和函数调用的基本用法，为后续课程内容做准备。

三、示例程序：#include <iostream>#include <cmath>using namespace std;void main(){int a[2][2]={1,2,3,4};int b[2][2]={2,1,4,5};int c[2][2]={0,0,0,0};int i,j,k;for (i=0; i<2; ++i)for (j=0; j<2; ++j)for (k=0; k<2; ++k)c[i][j]+=a[i][k]*b[k][j];for (i=0; i<2; ++i)for (j=0; j<2; ++j)cout<<c[i][j]<<endl;}实验二线性表、链表程序设计一、目的：掌握线性、链表的基本算法及相关的时间性能分析。

计算机系第一部分数据结构课程实验概述一．实验目的《数据结构》是计算机专业的主干课程和必修课程之一，其目的是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表示方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法，要求掌握算法的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复杂程序设计的技能。

在计算机科学领域，尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程序编制水平有很大的帮助。

二．实验要求2.1实验步骤设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有效地减少错误，提高工作效率。

因此必须严格执行良好的实验步骤规范（包括上机操作规范）。

本课程实验的基本步骤是：2.1.1问题分析充分地分析和理解问题本身，明确问题要求做什么。

对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。

例如；输入、输出数据的类型、值的范围以及形式等。

同时为调试程序准备好测试数据，包含合法的输入数据和非法形式输入的数据。

2.1.2设计和编码设计即是对问题描述中涉及的操作对象定义相应的数据类型，定义主程序模块和各抽象数据类型；定义相应的存储结构并写出各过程和函数的伪码算法。

在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。

编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程序。

对程序中的疑问应作出记号，以便上机时注意解决。

每个明确的功能模块程序一般不超过60行，程序的每一行不得超过60个字符，否则要进一步划分。

2.1.3上机前程序静态检查上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓错误。

静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。

把程序中的明显错误事先排除。

目录实验一线性表 (1)(一) 实验目的 (1)(二) 实验内容 (1)(三) 实验报告 (22)实验二堆栈 (23)(一) 实验目的 (23)(二) 实验内容 (23)(三) 实验报告 (41)实验三队列 (43)(一) 实验目的 (43)(二) 实验内容 (43)(三) 实验报告 (50)实验四模式匹配 (51)(一) 实验目的 (51)(二) 实验内容 (51)(三) 实验报告 (57)实验五二叉树 (58)(一) 实验目的 (58)(二) 实验内容 (58)(三) 实验报告 (85)实验六查找 (86)(一) 实验目的 (86)(二) 实验内容 (86)(三) 实验报告 (95)实验七内部排序 (96)(一) 实验目的 (96)(二) 实验内容 (96)(三) 实验报告 (113)实验八图和图的遍历 (114)(一) 实验目的 (114)(二) 实验内容 (114)(三) 实验报告 (131)数据结构课程设计（2007级用，仅做参考） (132)(一) 数据结构课程设计安排 (132)(二) 图算法实验题目 (132)(三) 团队题目（各种排序算法效率分析） (132)《数据结构》模拟试卷一 (136)《数据结构》模拟试卷二 (139)附录1：实验报告及习题 (142)实验名称：线性表（一） (142)实验名称：堆栈（二） (144)实验名称：队列（三） (146)实验名称：模式匹配（四） (149)实验名称：二叉树（五） (151)实验名称：查找（六） (153)实验名称：内部排序（七） (155)实验名称：图和图的遍历（八） (159)设计性、综合性实验 (161)附录2 数据结构课程设计完成情况登记表 (162)附录3 图的应用 (163)实验一线性表(一) 实验目的（1）掌握线性表的顺序存储（2）掌握线性表的链式存储（3）掌握基本算法（建表、插入、删除）的实现(二) 实验内容1. 线性表的顺序存储：掌握线性表的顺序存储结构及其基本操作、合并、逆置等算法设顺序表的存储结构定义如下：（同学们可扩展考虑其他形式的存储结构定义）#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量#define LISTINCREMENT 10 // 线性表存储空间的分配增量typedef struct{int *elem; // 存储空间基址int length; // 当前长度int listsize; // 当前分配的存储容量（以sizeof(int)为单位）}SqList;[题目1：编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。

数据结构上机实验编程指南为了更好地帮助同学们做好数据结构实验，在此给出数据结构上机编程的一般思路和程序的基本框架结构。

具体程序结构按先后顺序可分为以下3个部分：1．预定义常量及类型对于相关的常量与类型（如状态类型）进行定义，如：#define OK 1#define ERROR 0#define OVERFLOW –2#define TRUE 1#define FALSE 0typedef int Status;2．相关数据结构类型定义此部分包括对所使用的数据结构给出其类型定义及其基本操作函数定义。

（具体内容可参见实验一）3．主调程序的定义此部分给出相关的主调程序，在此程序中定义相关数据结构变量，并通过调用其操作函数，实现设计目的。

（具体内容可参见实验一）实验二链表一、实验目的1．掌握链表的类型定义；2．掌握链表及其基本操作的实现；3．掌握利用C编程语言实现数据结构的编程方法；4．掌握链表的复杂操作的实现算法；5．通过上机实践加强利用数据结构解决实际问题的能力。

二、实验要求1．实验前做好充分准备，事先预习好本次实验内容；2．实验时记录实验结果，按要求完成各题；3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。

三、实验题目与要求1．实验题目一：单链表的类型定义及其相关操作算法的实现要求：编程实现单链表的类型定义及单链表的求长度操作、取元素值操作、创建操作、插入操作、删除操作等，并对其进行验证。

2．实验题目二：链表的应用要求：编程实现单链表的拆分、求单链表的倒数第k个结点以及用循环单链表求解约瑟夫环问题的算法。

3. 实验题目三：链表上的算法设计编程实现单链表的逆置操作算法4. 特别注意：在DEV C++编译环境中，不要建立C工程，因为在C语言中不支持引用传递方式，只需建立C++源程序文件即可！！！四、实验程序示例本指导书所给出的示例程序均为DEV C++环境下完成的，若使用其它C开发环境，则部分语句要进行少许修改。

淮海工学院数据结构实验指导书计算机软件教研室实验1线性表的抽象数据类型的实现实验目的1）掌握线性表的顺序存储结构和链式存储结构；2）熟练掌握顺序表和链表基本算法的实现；3）掌握利用线性表数据结构解决实际问题的方法和基本技巧；4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；5）按时提交实验报告。

实验环境计算机、C语言程序设计环境实验学时2学时，必做实验。

实验内容一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。

按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；2）打印（遍历）该线性表（依次打印出表中元素值）；3）在线性表中查找第i个元素，并返回其值；4）在线性表中第i个元素之前插入一已知元素；5）在线性表中删除第i个元素；6）求线性表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。

按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内；2）打印（遍历）该链表（依次打印出表中元素值）；3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；5）在链表中按照有序方式插入一已知字符元素；6）在线性表中删除第i个结点；7）计算链表的长度。

实验步骤一、顺序表的源程序#include<stdlib.h>#include<stdio.h>#include<malloc.h>int list[25];int i,n,a,sum=0,k,l;int eleminsert;/*------------------创建函数--------------*/void initlist(){printf("Please input the total of the elems:");scanf("%d",&n);if(n>25||n<1) {printf("ERROE!");return;}printf("Please input the elems:...\n");for(i=0;i<n;i++){scanf("%d",&list[i]);}return;}/*------------------打印函数--------------*/void Print(int list[],int n){int j;for(j=0;j<n;j++)printf("%d\t",list[j]);printf("\n");return;}/*------------------查找函数------------*/int Search(int list[],int n,int m){if(m<1||m>n){printf("ERROR!\n"); return ;}else printf("The elem is %d at %d place\n",list[m-1],m); return;}/*----------------插入函数------------*/void Insert(int list[],int n,int m,int elem){int j;if(m<1||m>n){printf("ERROR!\n"); return ;}for(j=n-1;j>=m-1;i--){list[j+1]=list[j];}list[m-1]=elem;n=n+1;printf("The new list are:" );Print(list,n);return;}/*---------------删除函数-----------*/void Delete(int list[],int n,int m){int q;int j;if(m<1||m>n){printf("ERROR!\n"); return ;}j=list[m-1];for(q=m-1;q<=n;q++){list[q]=list[q+1];}printf("The new list are:");Print(list,n-1);free(j);return;}/*-------------求和函数------------*/void Sum(int list[],int n,int sum){int j;for(j=0;j<n;j++){sum=sum+list[j];}printf("The sum is :%d",sum);return;}void menu(){int j;/*------------菜单函数------------*/menulab:printf("********************** MENU ******************\n\n"); printf("Create a new int list :...................press 1\n\n"); printf("Print the whole list :....................press 2\n\n"); printf("Search by order :........................press 3\n\n"); printf("Insert the elem in the place i:...........press 4\n\n"); printf("Delete the elem by order :................press 6\n\n"); printf("Sum all elem in the list :................press 7\n\n"); printf("exit the programe :.......................press 0\n\n"); printf("********************** END *******************\n\n"); printf("Please choose the number from (0~7).....");checklabel: scanf("%1d",&j);getchar();if(j<0||j>7){printf("Error! Please choose again......");goto checklabel;}printf("\n\tYou choose the number %d\n ",j);printf("\n\tPress any key to continue.....");getchar();clrscr(); /*clear screen*/{case 1:/*创建任意整数线性表*/initlist();clrscr(); /*clear screen*/goto menulab;case 2: /*打印（遍历）该线性表*/printf("The original list is:");Print(list,n);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 3:/*在线性表中查找第i个元素，并返回其值*/printf("Input which LNode you want to Search(Input number):"); scanf("%d",&a);getchar();Search(l,n,a);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 4:/*在线性表中第i个元素之前插入一已知元素*/printf("Please input the elem's place where you want to insert"); scanf("%d",&k);printf("Input the elem which you want to insert:");scanf("%d",&eleminsert);Insert(list,n,k,eleminsert);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 5:/*在线性表中删除第i个元素*/printf("Please input the elem you want to delete:");scanf("%d",&l);n=n+1;Delete(list,n,l);n=n-1;printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 6:/*求线性表中所有元素值（整数）之和*/Sum(list,n,sum);printf("Press any key to continue.....");clrscr(); /*clear screen*/goto menulab;case0:/*退出程序*/printf("Press any key to continue.....");getchar();exit(0);}}void main(){void menu();menu();}二、链表（带头结点）的源程序#include<stdlib.h>#include<stdio.h>struct LNode{char elem;struct LNode* next;}*l,*p,*new;int i,a,k,n;char c,s;/*----------------创建函数-------------*/void intilist(void){l=(struct LNode *)malloc(sizeof(struct LNode));l->next=NULL;clrscr();printf("Input the total of the elems:.....");scanf("%d",&n);getchar();if(n>15)printf("Error!");for(i=n;i>0;i--){new=(struct LNode *)malloc(sizeof(struct LNode)); new->next=l->next;l->next=new;}p=l;while(p->next!=NULL) p=p->next;p->next=l;printf("Input elems:.......\n");p=l->next;for(i=1;i<=n;i++){scanf("%c",&p->elem);getchar();p=p->next;}return;}/*----------------排序函数-------------*/ void Sequence(struct LNode * l, int n) {int i;char swap,*e,*f;for(i=1;i<=n-1;i++){ p=l->next;while(p->next!=l){if(p->elem>p->next->elem) {e=&p->elem;f=&p->next->elem;swap=*e;*e=*f;*f=swap;} p=p->next;}}return;}/*----------------打印函数-------------*/void Print(struct LNode * l, int n){int i;p=l->next;for(i=1;i<=n;i++){printf("%c\t",p->elem);p=p->next;}printf("\n");return;}/*----------------查找函数-------------*/ void Locate(struct LNode * l, int n,int m) {int i;if(m>n) { printf("FALSE!\t");return; }else { p=l;for(i=1;i<=m;i++){p=p->next;}printf("The elem is:%c\n",p->elem);}return;}/*------已知字母匹配首结点查找函数------*/void LocateLNode(struct LNode * l, int n,char m){int i;p=l;for(i=1;i<=n;i++){p=p->next; if(p->elem==m) {printf("TRUE!\n");return;}} if(i>n) printf("FALSE!\n");return;}/*----------------插入函数-------------*/void Insert(struct LNode * l, int n,char m){new=(struct LNode *)malloc(sizeof(struct LNode));new->next=l->next;l->next=new;new->elem=m;n=n+1;Sequence(l,n);Print(l,n);return;}/*----------------删除函数-------------*/void Delete(struct LNode * l, int n,int m){int i;p=l;for(i=1;i<m;i++){p=p->next;}p->next=p->next->next;n=n-1;printf("The new list is:");Print(l,n);return;}/*----------------求表长函数-------------*/void Length(int n){int i;int length=0;for(i=1;i<=n+1;i++){length=length+sizeof(struct LNode);}printf("The length of the list is:%d",length);return;}/*----------------菜单函数-------------*/void menu(){int j;menulab:printf("********************** MENU ******************\n\n"); printf("Create the new list :..................press 1\n\n"); printf("Sequence the list :...................press 2\n\n"); printf("Search the Lnode by order :............press 3\n\n"); printf("Search the Lnode by elem :.............press 4\n\n"); printf("Insert the elem :......................press 5\n\n"); printf("Delete the elem by order :.............press 6\n\n"); printf("Return the length of the list :........press 7\n\n"); printf("exit the programe :....................press 0\n\n"); printf("********************** END *******************\n\n"); printf("Please choose the number from (0~7)....."); checklabel: scanf("%1d",&j);getchar();if(j<0||j>7){printf("Error! Please choose again......");goto checklabel;}printf("\n\tYou choose the number %d\n ",j);printf("\n\tPress any key to continue.....");getchar();clrscr(); /*clear screen*/switch(j){case 1:/*创建链表并输入元素*/intilist();clrscr(); /*clear screen*/goto menulab;case 2: /*排序并打印链表*/Sequence(l,n);printf("The orignal list is:\n");Print(l,n);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 3:/*查找第i个元素*/printf("Input which LNode you want to locate(Input number):"); scanf("%d",&a);getchar();Locate(l,n,a);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 4:/*查找与已知字符相同的第一个结点*/printf("Input the elem you want to search ");scanf("%c",&c);getchar();LocateLNode(l,n,c);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 5:/*插入已知字符的结点*/printf("Input the elem you want to insert:");scanf("%c",&s);getchar();Insert(l,n,s);n=n+1;printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 6:/*删除第i个结点*/printf("Input which one you want to delete:");scanf("%d",&k);if(k<1||k>n)printf("ERROR!");else{Delete(l,n,k);}n=n-1;getchar();clrscr(); /*clear screen*/goto menulab;case 7:/*计算链表长度*/Length(n);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case0:/*退出链表程序*/printf("Press any key to continue.....");getchar();exit(0);}}/*------------------主函数---------------*/main(){void menu(void);menu();}测试数据与实验结果（可以抓图粘贴）一、顺序表程序抓图及其简要说明菜单选项如下图所示：该菜单由八个函数组成，实现八项功能。