下载文档原格式
数据结构中常用的逻辑结构和存储结构一、概念数据是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。
结构是元素之间的关系的集合。
数据结构是在整个计算机科学与技术领域上广泛被使用的术语。
数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。
它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。
数据结构有逻辑上的数据结构和物理上的数据结构之分。
逻辑上的数据结构反映成分数据之间的逻辑关系即逻辑结构，而物理上的数据结构反映成分数据在计算机内部的存储安排即存储结构。
数据结构是数据存在的形式。
数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。
因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。
通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。
因而研究数据结构的逻辑结构与存储结构显得十分重要。
二、结构分析（一）逻辑结构数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。
逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。
逻辑结构元素决定输入、存储、发送、处理和信息传递的基本操作功能，常将逻辑结构元素称为逻辑模块。
逻辑结构元素可以是计算机操作系统、终端模块、通信程序模块等。
逻辑结构元素还可以是相关的几个逻辑模块联合起来的更复杂的实体。
分析逻辑结构元素的相互作用，应考虑整个系统的操作，研究处理与信息流有关的进程（操作系统中的一个概念，表示程序的一次执行），并决定系统的逻辑资源。
逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。
表和树是最常用的两种高效数据结构，许多高效的算法能够用这两种数据结构来设计实现。
线性表的存储结构定义及基本操作(实验报告)线性表的存储结构定义及基本操作一掌握线性表的逻辑特征掌握线性表顺序存储结构的特点熟练掌握顺序表的基本运算熟练掌握线性表的链式存储结构定义及基本操作理解循环链表和双链表的特点和基本运算加深对顺序存储数据结构的理解和链式存储数据结构的理解逐步培养解决实际问题的编程能力二一基本实验内容顺序表建立顺序表完成顺序表的基本操作初始化插入删除逆转输出销毁置空表求表长查找元素判线性表是否为空1 问题描述利用顺序表设计一组输入数据假定为一组整数能够对顺序表进行如下操作创建一个新的顺序表实现动态空间分配的初始化根据顺序表结点的位置插入一个新结点位置插入也可以根据给定的值进行插入值插入形成有序顺序表根据顺序表结点的位置删除一个结点位置删除也可以根据给定的值删除对应的第一个结点或者删除指定值的所有结点值删除利用最少的空间实现顺序表元素的逆转实现顺序表的各个元素的输出彻底销毁顺序线性表回收所分配的空间对顺序线性表的所有元素删除置为空表返回其数据元素个数按序号查找根据顺序表的特点可以随机存取直接可以定位于第 i 个结点查找该元素的值对查找结果进行返回按值查找根据给定数据元素的值只能顺序比较查找该元素的位置对查找结果进行返回判断顺序表中是否有元素存在对判断结果进行返回编写主程序实现对各不同的算法调用2 实现要求对顺序表的各项操作一定要编写成为C C 语言函数组合成模块化的形式每个算法的实现要从时间复杂度和空间复杂度上进行评价初始化算法的操作结果构造一个空的顺序线性表对顺序表的空间进行动态管理实现动态分配回收和增加存储空间位置插入算法的初始条件顺序线性表L已存在给定的元素位置为i且1≤i ≤ListLength L 1操作结果在L中第i个位置之前插入新的数据元素eL的长度加1位置删除算法的初始条件顺序线性表L已存在1≤i≤ListLength L 操作结果删除L的第i个数据元素并用e返回其值L的长度减1逆转算法的初始条件顺序线性表L已存在操作结果依次对L的每个数据元素进行交换为了使用最少的额外空间对顺序表的元素进行交换输出算法的初始条件顺序线性表L已存在操作结果依次对L的每个数据元素进行输出销毁算法初始条件顺序线性表L已存在操作结果销毁顺序线性表 L置空表算法初始条件顺序线性表L已存在操作结果将L重置为空表求表长算法初始条件顺序线性表L已存在操作结果返回L中数据元素个数按序号查找算法初始条件顺序线性表 L 已存在元素位置为 i且 1≤i≤ListLength L 操作结果返回 L 中第 i 个数据元素的值按值查找算法初始条件顺序线性表 L 已存在元素值为 e 操作结果返回 L 中数据元素值为 e 的元素位置判表空算法初始条件顺序线性表 L 已存在操作结果若 L 为空表则返回 TRUE否则返回 FALSE分析修改输入数据预期输出并验证输出的结果加深对有关算法的理解二基本实验内容单链表建立单链表完成链表带表头结点的基本操作建立链表插入删除查找输出求前驱求后继两个有序链表的合并操作其他基本操作还有销毁链表将链表置为空表求链表的长度获取某位置结点的内容搜索结点1 问题描述利用线性表的链式存储结构设计一组输入数据假定为一组整数能够对单链表进行如下操作初始化一个带表头结点的空链表创建一个单链表是从无到有地建立起一个链表即一个一个地输入各结点数据并建立起前后相互链接的关系又分为逆位序插在表头输入 n 个元素的值和正位序插在表尾输入 n 个元素的值插入结点可以根据给定位置进行插入位置插入也可以根据结点的值插入到已知的链表中值插入且保持结点的数据按原来的递增次序排列形成有序链表删除结点可以根据给定位置进行删除位置删除也可以把链表中查找结点的值为搜索对象的结点全部删除值删除输出单链表的内容是将链表中各结点的数据依次显示直到链表尾结点编写主程序实现对各不同的算法调用其它的操作算法描述略2 实现要求对链表的各项操作一定要编写成为 C C 语言函数组合成模块化的形式还要针对每个算法的实现从时间复杂度和空间复杂度上进行评价初始化算法的操作结果构造一个空的线性表 L产生头结点并使 L 指向此头结点建立链表算法初始条件空链存在操作结果选择逆位序或正位序的方法建立一个单链表并且返回完成的结果链表位置插入算法初始条件已知单链表 L 存在操作结果在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e链表位置删除算法初始条件已知单链表 L 存在操作结果在带头结点的单链线性表 L 中删除第 i 个元素并由 e 返回其值输出算法初始条件链表 L 已存在操作结果依次输出链表的各个结点的值三扩展实验内容顺序表查前驱元素查后继元素顺序表合并等1 问题描述根据给定元素的值求出前驱元素根据给定元素的值求出后继元素对已建好的两个顺序表进行合并操作若原线性表中元素非递减有序排列要求合并后的结果还是有序有序合并对于原顺序表中元素无序排列的合并只是完成 A A∪B 无序合并要求同样的数据元素只出现一次修改主程序实现对各不同的算法调用2 实现要求查前驱元素算法初始条件顺序线性表 L 已存在操作结果若数据元素存在且不是第一个则返回前驱否则操作失败查后继元素算法初始条件顺序线性表 L 已存在操作结果若数据元素存在且不是最后一个则返回后继否则操作失败无序合并算法的初始条件已知线性表 La 和 Lb操作结果将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中有序合并算法的初始条件已知线性表 La 和 Lb 中的数据元素按值非递减排列操作结果归并 La 和 Lb 得到新的线性表 LcLc 的数据元素也按值非递减排列四扩展实验内容链表1 问题描述求前驱结点是根据给定结点的值在单链表中搜索其当前结点的后继结点值为给定的值将当前结点返回求后继结点是根据给定结点的值在单链表中搜索其当前结点的值为给定的值将后继结点返回两个有序链表的合并是分别将两个单链表的结点依次插入到第 3 个单链表中继续保持结点有序2 实现要求求前驱算法初始条件线性表 L 已存在操作结果若 cur_e 是 L 的数据元素且不是第一个则用 pre_e 返回它的前驱求后继算法初始条件线性表 L 已存在操作结果若 cur_e 是 L 的数据元素且不是最后一个则用 next_e 返回它的后继两个有序链表的合并算法初始条件线性表单链线性表 La 和 Lb 的元素按值非递减排列操作结果归并 La 和 Lb 得到新的单链表三实验环境和实验步骤实验环境利用CodeBlocks1005集成开发环境进行本实验的操作实验步骤――顺序表的定义与操作1启动CodeBlocks1052按Create a new project 通过file 按CC source选择c然后GO储存文件D\c语言\顺序表c3进行编代码4编好之后搞ctrlshiftF9进行编译然后按ctrlF105如果编译出问题然后进行调试实验步骤――链表的定义与操作1启动CodeBlocks1052按Create a new project 通过file 按CC source选择c然后GO储存文件D\c语言\单链表c3进行编代码4编好之后搞ctrlshiftF9进行编译然后按ctrlF105如果编译出问题然后进行调试四 includeinclude "stdlibh"includedefine LIST_INIT_SIZE 100define ok 1define ERROR 0define OVERFLOW -1define Num 3typedef int DataTypetypedef int Statustypedef structDataType elemint Lengthint ListsizeSeqListSeqList LStatus InitSeqList SeqList LL- elem Da。
《数据结构》课程标准学时：72学时（其中：讲课学时：36 上机学时：36 ）先修课程：高等数学、C语言程序设计后续课程：软件开发相关的应用性课程（Android应用开发、软件工程等）适用专业：软件技术、移动应用开发、软件与信息服务等开课部门：信息工程与大数据学院一、课程的性质《数据结构》是面向软件技术相关专业的一门专业基础课，课程要求：熟练掌握线性表、栈和队的存储结构及基本操作，并能在相应的应用中正确地选用，培养学生用链式结构编写程序的能力；了解串和广义表的定义和存储结构；掌握数组的存储结构，熟悉稀疏矩阵的两种压缩存储方法的特点及适用范围；了解树的存储结构及特点，掌握二叉树和图的存储结构及其相应算法，培养学生用非线性结构解决实际问题的能力；掌握各种查找、排序方法，培养学生灵活应用已有排序方法的能力，开拓思路编写新的排序算法。
二、课程设计理念数据结构是计算机存储、组织数据的方式。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
精心选择的数据结构可以带来更高的运行或存储效率，数据结构往往同高兴的检索算法和索引技术有关。
1、课程地位理念在许多类型的程序设计中，数据结构的选择是一个基本的设计考虑因素。
许多大型的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。
许多时候，确定了数据结构后，算法就容易得到了。
有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。
不论哪种情况，选择合适的数据结构都是非常重要的。
选择了数据结构，算法随之确定，是数据而不是算法是系统构造的关键因素。
2、课程学情理念本课程开设在嵌入式系统工程专科第一学期，学生在学习本课程前已具备计算机基础、C语言基础等知识，本课程力图让学生学会在C语言环境下，运用面向对象的思想编写规范的代码，实现经典的数据结构和算法。
熟悉常用的数据结构和算法，使学生初步具备一个优秀的软件开发人员所应有的基本能力。
数据结构课程标准课程目标1：理解线性表、栈和队列、串、树和二叉树和图的逻辑结构，掌握在各种逻辑结构上的各种基本操作的实现，培养学生进行复杂程序设计的能力和数据抽象的能力。
课程目标2：熟练掌握常用的静态查找和动态查找算法，深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。
课程目标3：能够从时间和空间复杂性的角度综合比较各种算法的复杂度，并能分析顺序存储和链式存储两种常用存储结构的不同特点及适用场合。
三、课程目标与毕业要求的关系1、课程目标与毕业要求的对应关系课程目标2课程目标3注：H表示高支撑，M表示中支撑，1表示低支撑。
参考《数学学院课程目标达成度评价方法》进行评价。
九、本课程各个课程目标的权重依据第八部分中的课程目标达成度评价方法，计算得到本课程的各个课程目标的权重如下:根据学生的课堂表现、作业、平时测验和期末考试情况及教学督导的反馈，检验学生对本课程涉及的学科素养和学会反思的达成情况，及时对教学中的不足之处进行改进，调整教学指导策略；根据学生的课堂表现、作业、平时测验及期末考试成绩，检验本课程所支撑的毕业要求分解指标点的达成度情况;根据本课程所支撑的毕业要求分解指标点的达成度情况，在本学院教学指导委员会指导下，重新修订本课程大纲，实现持续改进。
十一、推荐教材及参考书目1.教材1.孙丽云.数据结构（C语言版）[M].武汉：华中科技大学出版社,2017.2.参考书目2.孙丽云.数据结构实验指导与习题解析（C语言版）[M].北京：华中科技大学出版社,2017.3.严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2012.4.高一凡，数据结构算法解析[M].北京：清华大学出版社，2015.。
一、实验目的：. 掌握线性表的逻辑特征. 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算. 熟练掌握线性表的链式存储结构定义及基本操作. 理解循环链表和双链表的特点和基本运算. 加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二、实验内容：（一）基本实验内容（顺序表）：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：. 创建一个新的顺序表，实现动态空间分配的初始化；. 根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；. 根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)；. 利用最少的空间实现顺序表元素的逆转；. 实现顺序表的各个元素的输出；. 彻底销毁顺序线性表，回收所分配的空间；. 对顺序线性表的所有元素删除，置为空表；. 返回其数据元素个数；. 按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；. 按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；. 判断顺序表中是否有元素存在，对判断结果进行返回；. 编写主程序，实现对各不同的算法调用。
2．实现要求：对顺序表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价；. “初始化算法”的操作结果：构造一个空的顺序线性表。
对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；. “位置插入算法”的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1；. “位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ；操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ；. “逆转算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换；. “输出算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行输出；. “销毁算法”初始条件：顺序线性表L 已存在；操作结果：销毁顺序线性表L；. “置空表算法”初始条件：顺序线性表L 已存在；操作结果：将L 重置为空表；. “求表长算法”初始条件：顺序线性表L 已存在；操作结果：返回L 中数据元素个数；. “按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L)操作结果：返回L 中第i 个数据元素的值. “按值查找算法”初始条件：顺序线性表L 已存在，元素值为e；操作结果：返回L 中数据元素值为e 的元素位置；. “判表空算法”初始条件：顺序线性表L 已存在；操作结果：若L 为空表，则返回TRUE，否则返回FALSE；分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。
数据结构复习笔记作者: 网络转载发布日期: 无数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。
数据项是具有独立含义的最小标识单位。
如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。
数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。
这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。
比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。
那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。
而存储结构则是指用计算机语言如何表示结点之间的这种关系。
如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。
(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。
)第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。
弄清了以上三个问题，就可以弄清数据结构这个概念。
--------------------------------------------------------------------------------通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解)数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。
各章主要内容及知识结构
一、线性表
1.线性表的逻辑结构定义、特点及抽象数
据机构类型定义
2.各种存储结构的描述方法：
顺序表、链接表、循环链表、双向链表
3.线性表的应用——多项式的加法
二、栈、队列和串
1.栈和队列的抽象类型定义
2.栈与队列的结构特点
3.栈的实现：顺序栈与链接栈
4.队列的实现：链式、循环队列
5.栈的应用：表达式求值、数制转换、括
号匹配、递归转化为非递归。
6.队列的应用：图的深度优先遍历。
7.串的基本操作、模式匹配算法
三、数组和稀疏矩阵
1.数组的类型定义
2.数组的顺序表示与实现：
有两种顺序存储方法——行序和列序，
由这两种方式决定的数组元素位置的
计算公式。
3.稀疏矩阵与特殊矩阵
压缩存储及元素定位计算
4.十字链表
四、二叉树
1.树与二叉树的基本概念；
2.二叉树的遍历-递归和非递归算法；
3.线索二叉树；
4.树的遍历及树的转化为二叉树
5.哈夫曼树
6.递归算法的应用
五、图
1.图的定义
2.图的存储结构：
1)邻接矩阵；
2)邻接表。
3.图的两种遍历算法
1)深度优先算法（DFS）
2)广度优先算法（BFS）
4.最小生成树
1)PRIM算法
2)KRUSKAL算法
5.拓扑排序、关键路径与最短路径。
“数据结构和算法II”课程实验报告实验名称：线性表的存储结构定义及基本操作班级姓名学号实验日期：实验机时：2 学时实验成绩：-------------------------------------------------------------------------------一.实验目的：1.掌握线性表的逻辑特征2.掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算3.熟练掌握线性表的链式存储结构定义及基本操作4.理解循环链表和双链表的特点和基本运算5.加深对栈结构的理解，培养解决实际问题的编程能力。
6.加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二.实验内容：（1）基本实验内容：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。
（2）扩展实验内容：查前驱元素、查后继元素、顺序表合并，两个有序单链表的合并操作等。
三.程序及注释：1.顺序表：#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int status ;typedef int ElemType ;typedef struct{ElemType *elem;int length,listsize;}SqList;status InitList(SqList &L)//初始化{L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem) exit(OVERFLOW);L.listsize=LIST_INIT_SIZE;L.length=0;return OK;}status Build(SqList &L)//建立表{int i,n;printf("请输入元素个数n和n个元素\n");scanf("%d",&n);if(n>LIST_INIT_SIZE)//如果n大于当前空间{L.elem=(ElemType *)realloc(L.elem,(n+LISTINCREMENT)*sizeof(ElemType));if(!L.elem) exit(OVERFLOW);L.listsize=n+LISTINCREMENT;}for(i=0;i<n;i++)scanf("%d",L.elem+i);L.length=n;return OK;}void Print(SqList &L)//输出表中元素和长度{int i;for(i=0;i<L.length;i++)printf("%d ",*(L.elem+i));printf("\n长度为:%d\n\n",L.length);}void Tips()//提示函数{printf("请选择你的想要的操作：\n");printf("<1> 输出顺序表及顺序表的长度\n");printf("<2> 删除值为x的结点\n");printf("<3> 删除给定位置i的结点\n");printf("<4> 将顺序表逆置\n");printf("<5> 将顺序表按升序排序\n");printf("<6> 将x插入到顺序表的适当位置上\n");printf("<7> 将两个有序表合并\n");printf("<0> 退出\n\n");}status ListDelete1(SqList &L,int x)//删除值为X的元素{int i;for(i=0;i<L.length;i++)if(*(L.elem+i)==x)break;if(i==L.length)return ERROR;for(i++;i<L.length;i++)*(L.elem+i-1)=*(L.elem+i);L.length--;return OK;}status ListDelete2(SqList &L,int x)//删除第X个元素{int i;if(x<0||x>=L.length)return ERROR;for(i=x+1;i<L.length;i++)*(L.elem+i-1)=*(L.elem+i);L.length--;return OK;}void Inverse(SqList &L)//逆置函数{int i,t;for(i=0;i<L.length/2;i++){t=*(L.elem+i);*(L.elem+i)=*(L.elem+L.length-i-1);*(L.elem+L.length-i-1)=t;}}void Sort(SqList &L)//冒泡排序（升序）{int i,j,t;for(i=1;i<L.length;i++)for(j=0;j<L.length-i;j++){if(*(L.elem+j)>*(L.elem+j+1)){t=*(L.elem+j);*(L.elem+j)=*(L.elem+j+1);*(L.elem+j+1)=t;}}printf("已按升序排列\n\n");}status ListInsert(SqList &L,int x)//将X插入，使仍然有序{int i,k;if(L.length>=L.listsize){L.elem=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW);L.listsize+=LISTINCREMENT;}for(i=0;i<L.length;i++)if(x<*(L.elem+i))break;k=i;for(i=L.length;i>k;i--)*(L.elem+i)=*(L.elem+i-1);*(L.elem+k)=x;L.length++;return OK;}status Merger(SqList &L,SqList &Lb)//合并两个线性表{int i,j,k;SqList Lc;InitList(Lc);if(Lc.listsize<L.length+Lb.length){Lc.elem=(ElemType *)realloc(Lc.elem,(L.length+Lb.length+LISTINCREMENT)*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW);Lc.listsize=L.length+Lb.length+LISTINCREMENT;}i=j=k=0;while(i<L.length && j<Lb.length){if(*(L.elem+i) < *(Lb.elem+j)){*(Lc.elem+k)=*(L.elem+i);k++;i++;}else{*(Lc.elem+k)=*(Lb.elem+j);k++;j++;}}while(i<L.length){*(Lc.elem+k)=*(L.elem+i);k++;i++;}while(j<Lb.length){*(Lc.elem+k)=*(Lb.elem+j);k++;j++;}Lc.length=L.length+Lb.length;L=Lc;return OK;}int main(){int op,x,flag;SqList L,Lb;InitList(L);Build(L);Tips();scanf("%d",&op);while(op){switch(op){case 1:Print(L);case 2:printf("请输入要删除的数据X:\n");scanf("%d",&x);flag=ListDelete1(L,x);if(flag)printf("删除成功!!\n\n");elseprintf("元素不存在,删除失败!!\n\n");break;case 3:printf("请输入要删除的位置i:\n");scanf("%d",&x);flag=ListDelete2(L,x-1);//第i个元素对应的下标为i-1 if(flag)printf("删除成功!!\n\n");elseprintf("元素不存在,删除失败!!\n\n");break;case 4:Inverse(L);break;case 5:Sort(L);break;case 6:printf("请输入要插入的数据X:\n");scanf("%d",&x);flag=ListInsert(L,x);if(flag)printf("插入成功!!\n\n");elseprintf("插入失败!!\n\n");break;case 7:printf("请输入Lb的内容:\n");InitList(Lb);Build(Lb);flag=Merger(L,Lb);if(flag)printf("合并成功!!\n\n");break;}Tips();scanf("%d",&op);}2.单链表typedef int ElementType;#ifndef _List_H#define _List_Hstruct Node;typedef struct Node *PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;List MakeEmpty( List L );int IsEmpty( List L );int IsLast( Position P, List L );Position Find( ElementType X, List L );void Delete( ElementType X, List L );Position FindPrevious( ElementType X, List L );void Insert( ElementType X, List L, Position P );void DeleteList( List L );Position Header( List L );Position First( List L );Position Advance( Position P );ElementType Retrieve( Position P );#endif#include <stdio.h>#include <stdlib.h>#define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 ) struct Node{ElementType Element;Position Next;};List MakeEmpty( List L ) //创建空链表{if( L != NULL )DeleteList( L );L = malloc( sizeof( struct Node ) );if( L == NULL )FatalError( "Out of memory!" );L->Next = NULL;return L;}int IsEmpty( List L )//判断链表是否为空{return L->Next == NULL;}int IsLast( Position P, List L ){return P->Next == NULL;}Position Find( ElementType X, List L )//精确查找函数{Position P;P = L->Next;while( P != NULL && P->Element != X ){P = P->Next;n++;}if(P==NULL)printf("查找的成员不存在！！\n\n");elseprintf("查找的成员位于链表第%d位\n\n",n); }void Delete( ElementType X, List L )//精确删除函数{Position P, TmpCell;P = FindPrevious( X, L );if( !IsLast( P, L ) ){TmpCell=P->Next;P->Next=TmpCell->Next;free( TmpCell );}}Position FindPrevious( ElementType X, List L )//前驱查找函数{Position P;P = L;while( P->Next != NULL && P->Next->Element != X )P = P->Next;return P;}void Insert( ElementType X, List L, Position P )//元素插入函数{Position TmpCell;TmpCell = malloc( sizeof( struct Node ) );if( TmpCell == NULL )FatalError( "Out of space" );TmpCell->Element = X;TmpCell->Next = P->Next;P->Next = TmpCell;}void DeleteList( List L )//清空链表函数{Position P, Tmp;P = L->Next;L->Next = NULL;while( P != NULL ){Tmp = P->Next;free( P );P = Tmp;}if(IsEmpty(L))printf("链表清空成功！\n\n");}Position Header( List L )//表头调用函数{return L;}Position First( List L )//首元素调用函数{return L->Next;}Position Advance( Position P )//元素递进函数{return P->Next;}void show(List L)//显示链表函数{if(!IsEmpty(L)){Position p;p=First(L);printf("当前链表成员如下：\n");while(p!=NULL){printf("%d ",p->Element);if(Advance(p))p=Advance(p);else{printf("\n\n");break;}}}elseprintf("当前链表为空！！\n\n"); }void join(List L) //插入函数调用函数{int x,n,i;Position p=Header(L);printf("请输入需要插入的成员：\n");scanf("%d",&x);printf("需要将成员插入到第几位呢？\n");scanf("%d",&n);for(i=1;i<n;i++){p=p->Next;}Insert(x,L,p);show(L);}void find(List L)//查找函数调用函数{printf("请输入需要查找的成员：\n");int x;scanf("%d",&x);Find(x,L);}void count(List L)//链表长度统计函数{Position p;p=First(L);int n=0;while(p!=NULL){n++;if(Advance(p))p=Advance(p);elsebreak;}printf("当前链表长度为：%d\n\n",n);}void direction(List L)//位置访问函数{int n,i;Position p=Header(L);printf("请输入n的值：\n");scanf("%d",&n);for(i=0;i<n;i++){p=p->Next;}printf("第%d位成员为：%d\n\n",n,p->Element);}void change(List L)//修改元素函数{printf("请输入n的值：\n");int x,n,i;scanf("%d",&n);printf("请输入修改后的值：\n");scanf("%d",&x);Position p=Header(L);for(i=0;i<n;i++){p=p->Next;}p->Element=x;show(L);}void deletion(List L)//删除函数调用函数{printf("你要删除的成员是：\n");int x;scanf("%d",&x);Delete(x,L);show(L);}void main(){ List L;L=MakeEmpty(NULL);printf("请输入需要插入的成员个数：\n");int n;scanf("%d",&n);printf("请输入需要插入的成员以空格隔开：\n");int i;Position p;p=Header(L);for(i=0;i<n;i++){int x;scanf("%d",&x);Insert(x,L,p);p=Advance(p);}show(L);printf("请选择需要进行的操作：\n 1.计算链表长度\n 2.取第n个位置成员\n 3.修改第n个位置成员\n 4.在第n位插入新成员\n 5.删除成员\n 6.搜索成员\n 7.销毁链表\n 8.退出\n你输入的选项是：");scanf("%d",&n);while(n!=8){switch(n){case 1:count(L);break;case 2:direction(L);break;case 3:change(L);break;case 4:join(L);break;case 5:deletion(L);break;case 6:find(L);break;case 7:DeleteList(L);break;}printf("请选择需要进行的操作：\n 1.计算链表长度\n 2.取第n个位置成员\n 3.修改第n个位置成员\n 4.在第n位插入新成员\n 5.删除成员\n 6.搜索成员\n 7.销毁链表\n 8.退出\n你输入的选项是：");scanf("%d",&n);}}四.运行结果：1.顺序表：3.单链表：五.实验心得：通过这次写实验报告，我深切的理解了这门课的本质。
《数据结构》学习指导说明：本指导以《数据结构》(C语言版)(严蔚敏等编著,清华大学出版社1997年出版，国家级优秀教材特等奖)和《数据结构题集》(严蔚敏等编著,清华大学出版社1999年出版)为教学主要参考书。
一、绪论1、学习目的：明确数据结构课程在本专业知识结构中的地位，作用。
课程的特点，教学的要求，方法。
明确数据结构所研究的问题以及有关基本概念。
初步掌握抽象数据类型的表示与实现，初步明确算法分析的作用与分析的重点，初步掌握算法分析的方法。
2、学习重点：数据的逻辑结构、存储结构及其算法，数据结构的有关概念，抽象数据类型及其表示与实现，算法，算法设计的要求，算法的时间复杂度和算法的空间复杂度。
3、学习难点：数据结构的有关概念，抽象数据类型的表示与实现；算法的时间复杂度分析。
4、课程内容与基本要求(一) 数据结构的引入(1) 三个世界：现实世界，信息世界，机器世界。
数据结构要解决的就是实现从现实世界到信息世界，再由信息世界到机器世界的转换，从而实现用计算机来解决问题的目的。
(2) 非数值问题(结合三个世界讲)：控制，管理，数据处理(3) 数值问题：数值计算(4)数据结构：从学科角度讲，数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及他们之间的关系和操作等等的学科。
(二) 课程的地位，性质，作用。
(1) 地位: 计算机专业的核心课程之一。
(2) 性质: 算法理论基础和软件设计的技术基础课。
(3) 作用: 程序设计的基础，编译程序，操作系统，数据库系统及软件系统和应用程序的基础(三) 数据结构的产生和发展(四) 课程的特点，学习的要求教材：《数据结构》(C语言版)严蔚敏等编著北京清华大学出版社1997年参考书：《数据结构》许卓群等编著北京高等教育出版社1987年数据结构实用教程》（C/C++描述）徐孝凯北京清华大学出版社1999年《数据结构题集》严蔚敏等编著北京清华大学出版社1999年《数据结构导学》苏光奎等编著北京清华大学出版社20XX年《数据结构》(C语言篇)－习题与解析李春葆编著北京清华大学出版社20XX年《数据结构》实验指导书唐开山自编讲义20XX年(五) 基本概念和术语数据数据元素数据对象(4)数据结构:按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它存储到计算机的存储器中，并在这些数据上定义了一个运算的集合，叫做一个数据结构。
