下载文档原格式
线性表知识点总结线性表的特点：1. 有序性：线性表中的元素是有序排列的，每个元素都有唯一的前驱和后继。
2. 可变性：线性表的长度是可变的，可以进行插入、删除操作来改变表的元素数量。
3. 线性关系：线性表中的元素之间存在明确的前驱和后继关系。
4. 存储结构：线性表的存储结构有顺序存储和链式存储两种方式。
线性表的操作：1. 查找操作：根据元素的位置或值来查找线性表中的元素。
2. 插入操作：将一个新元素插入到线性表中的指定位置。
3. 删除操作：将线性表中的某个元素删除。
4. 更新操作：将线性表中的某个元素更新为新的值。
线性表的顺序存储结构：顺序存储结构是将线性表的元素按照其逻辑顺序依次存储在一块连续的存储空间中。
线性表的顺序存储结构通常采用数组来实现。
数组中的每个元素都可以通过下标来访问，因此可以快速的进行查找操作。
但是插入和删除操作会导致元素位置的变动，需要进行大量数据搬移，效率较低。
线性表的链式存储结构：链式存储结构是将线性表的元素通过指针相连，形成一个链式结构。
每个元素包含数据和指向下一个元素的指针。
链式存储结构不需要连续的存储空间，可以动态分配内存，适合插入和删除频繁的场景。
但是链式结构的元素访问不如顺序结构高效，需要通过指针来逐个访问元素。
线性表的应用场景：1. 线性表适用于数据元素之间存在明确的前后关系，有序排列的场景。
2. 顺序存储结构适用于元素的插入和删除操作较少，对元素的随机访问较频繁的场景。
3. 链式存储结构适用于插入和删除操作较频繁的场景，对元素的随机访问较少。
线性表的操作的时间复杂度：1. 查找操作：顺序存储结构的时间复杂度为O(1)，链式存储结构的时间复杂度为O(n)。
2. 插入和删除操作：顺序存储结构的时间复杂度为O(n)，链式存储结构的时间复杂度为O(1)。
线性表的实现：1. 顺序存储结构的实现：使用数组来存储元素，通过下标来访问元素。
2. 链式存储结构的实现：使用链表来实现，每个元素包含数据和指向下一个元素的指针。
计算机二级公共基础部分：线性表及其顺序存储结构:1.3.1线性表的基本概念：线性表:由n(n≥20)个相同类型数据元素构成的有限序列n定义为线性表的表长;n=时的线性表被称为空表。
称i为在线性表中的位序。
例如:英文大写字母表(A,B,C,D,E,F,...X,Y,Z)同一花色的13张扑克牌。
(2,3,4,5,6,7,8,9,10,J,Q,K,A)线性表的结构特征:数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；对于一个非空线性表，有且只有一个根节点a1,它无前件，有且只有一个终端结点a n, 它无后件，除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表的存储结构：顺序存储链式存储两个基本特点:线性表中所有元素所占的存储空间是连续的。
线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
该内容考点：重点：插入，删除，查找，排序难点：1分多分解，合并n合1，copy,逆转顺序表的插入和删除分析插入算法的分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动的元素个数为：E is=1n+1∑p i(n−i+1)=n2 n+1i=1删除算法的分析在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：E dl=1n∑p i(n−i)=n+12 ni=1分析结论顺序存储结构表示的线性表，在做插入或删除时，平均需要移动大约一半的数据元素。
当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点值得考虑。
线性表知识点总结线性表是数据结构中最基本、最简单的数据结构之一，它在计算机科学和程序设计中有着广泛的应用。
接下来，让我们一起深入了解线性表的相关知识。
一、线性表的定义线性表是由零个或多个数据元素组成的有限序列。
其中，每个数据元素的类型相同，并且在逻辑上是线性排列的。
也就是说，除了第一个元素外，每个元素都有且仅有一个直接前驱；除了最后一个元素外，每个元素都有且仅有一个直接后继。
例如，一个整数序列 10, 20, 30, 40, 50 就是一个线性表。
在这个序列中，10 是第一个元素，没有前驱；50 是最后一个元素，没有后继；而 20 的前驱是 10，后继是 30 。
二、线性表的特点1、元素个数有限：线性表中的元素个数是确定的，不能是无限的。
2、元素具有相同的数据类型：这使得对线性表的操作可以统一进行，方便编程实现。
3、元素之间的顺序是线性的：元素按照一定的顺序排列，每个元素都有确定的前驱和后继关系（除了首元素和尾元素）。
三、线性表的存储结构线性表有两种常见的存储结构：顺序存储结构和链式存储结构。
1、顺序存储结构顺序存储结构是指用一组地址连续的存储单元依次存储线性表中的数据元素。
在顺序存储结构中，逻辑上相邻的元素在物理位置上也相邻。
优点：（1）可以随机访问表中的任意元素，时间复杂度为 O(1)。
（2）存储密度高，不需要额外的指针来表示元素之间的关系。
缺点：（1）插入和删除操作需要移动大量元素，时间复杂度为 O(n)。
（2）存储空间大小需要预先分配，如果分配过大，会造成空间浪费；如果分配过小，可能导致溢出。
2、链式存储结构链式存储结构是通过指针将各个数据元素链接起来存储。
每个节点包含数据域和指针域，数据域用于存储数据元素的值，指针域用于指向下一个节点的地址。
优点：（1）插入和删除操作不需要移动大量元素，只需修改指针，时间复杂度为 O(1)。
（2）存储空间可以动态分配，不会造成空间浪费或溢出。
缺点：（1）不能随机访问，只能通过指针顺序访问，时间复杂度为O(n)。
线性表的存储结构定义及基本操作(实验报告)线性表的存储结构定义及基本操作一掌握线性表的逻辑特征掌握线性表顺序存储结构的特点熟练掌握顺序表的基本运算熟练掌握线性表的链式存储结构定义及基本操作理解循环链表和双链表的特点和基本运算加深对顺序存储数据结构的理解和链式存储数据结构的理解逐步培养解决实际问题的编程能力二一基本实验内容顺序表建立顺序表完成顺序表的基本操作初始化插入删除逆转输出销毁置空表求表长查找元素判线性表是否为空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。
一、实验目的：. 掌握线性表的逻辑特征. 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算. 熟练掌握线性表的链式存储结构定义及基本操作. 理解循环链表和双链表的特点和基本运算. 加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二、实验内容：（一）基本实验内容（顺序表）：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；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；分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。
线性表的顺序存储——顺序表之前我们讲了线性表, 本篇来阐述下线性表的顺序存储——顺序表定义线性表的顺序存储⼜称为顺序表, 它是⽤⼀组地址连续的存储单元依次存储线性表中的数据元素. 逻辑上相邻的两个数据元素在物理位置上同样相邻.规律顺序表中逻辑顺序与物理顺序相同L = ($a_{1}$, $a_{2}$, ..., $a_{i}$, $a_{i + 1}$, ..., $a_{n}$)其中在逻辑上相邻的两个数据元素，在顺序表中也存放在相同的存储单元当中，每⼀个⼩格⼦就代表⼀个存储单元。
注线性表中的元素的位序是从1开始, ⽽数组中元素下标是从0开始的若线性表存储的起始位置为Loc(A), sizeof(ElemType)为每个数据元素所占⽤的存储空间⼤⼩, 那么根据这⼀特点，我们可以计算出每⼀个数据元素存储的地址。
第⼀个元素的地址是 LOC(A)，计算第⼆个元素的地址就可以⽤第⼀个元素的地址加上第⼀个数据元素 $a_{1}$ 所消耗的存储空间，⽤ sizeof 可求得该数据元素所消耗的存储空间⼤⼩。
这⾥需要注意的⼀点是，n 与 MaxSize 是有含义上的不同的，其中 $a_{n}$ 代表的是顺序表中最后⼀个数据元素，⽽ MaxSize 代表的是数组的最后⼀个存储单元。
顺序表的两种实现⽅法顺序表可以⽤数组来实现。
根据数组的两种分配⽅式，也就有两种描述顺序表的⽅法。
分别是静态描述分配顺序表的⽅法和动态描述分配顺序表的⽅法。
⾸先来看数组静态分配时时如何描述⼀个顺序表的。
静态描述分配顺序表#define MaxSize 50typedef struct{ElemType data[MaxSize];int length;}SqList;这就是描述顺序表的语句。
第⼀句是定义了⼀个宏，也就是定义线性表的最⼤长度为 50，同时这也是数组的最⼤容量。
接着定义了⼀个结构体。
结构体就是把多个基本数据类型组合到⼀起构成⼀个新的数据类型。
线性表顺序存储结构上的基本运算
实验项目名称：线性表的顺序存储结构上的基本运算
（所属课程：数据结构--用C语言描述）
院系：计算机科学与信息工程学院专业班级：网络工程
姓名：000000 学号：0000000000 实验日期：2016.10.20 实验地点：A-06 406 合作者：指导教师：
孙高飞
本实验项目成绩：教师签字：日期：
（以下为实验报告正文）
一、实验目的
本次实验的目的掌握顺序表的存储结构形式及其描述和基本运算的实现；掌握动
态链表结构及相关算法设计
实验要求：输入和验证程序例题。
正确调试程序，记录程序运行结果。
完成实验
报告。
二、实验条件
Windows7系统的电脑，vc++6.0软件，书本《数据结构--用c语言描述》
三、实验内容
3.1 根据41页代码，用c语言定义线性表的顺序存储结构。
3.2 根据42页算法2.1实现顺序表的按内容查找。
3.3 根据43页算法2.2实现顺序表的插入运算。
3.4 根据45页算法2.3实现顺序表的删除运算。
四、实验步骤
3.2实验步骤
（1）编写头文件，创建ElemType。
（2）根据根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。
（3）根据42页算法2.1实现顺序表的按内容查找，创建Locate函数。
（4）创建main函数，输入SeqList L的数据元素。
（5）输入要查找的数据元素的值，调用Locate函数，输出结果。
3.3实验步骤
（1）编写头文件，创建ElemType。
（2）根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。
（3）根据43页算法2.2实现顺序表的插入运算，创建InsList函数。
（4）创建printList函数，逐项输出顺序表内的元素及顺序表元素的个数。
（5）创建main函数，输入插入的元素和其位置，调用printLinst函数输出顺序表，调用IntList函数，再次调用printLinst函数输出顺序表。
3.4实验步骤
（1）编写头文件，创建ElemType。
（2）根据根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。
（3）根据45页算法2.3实现顺序表的删除运算，创建DelList函数。
（4）创建printList函数，逐项输出顺序表内的元素及顺序表元素的个数。
（5）创建main函数，输入删除元素的位置，调用printLinst函数输出顺序表，调用DelList函数，再次调用printLinst函数输出顺序表。
五、实验结果
（1）实验3.2顺序表的按内容查找
# include <stdio.h>
typedef int Elemtype;
typedef struct{
Elemtype elem[100];
int last;
}SeqList;
int Locate(SeqList L,Elemtype e){ int i;
i=0;
while((i<=st)&&(L.elem[i]=e))
i++;
if(i<=st)
return(i+1);
else
return(-1);
}
void main(){
SeqList s={{1,2,3,6,8,10,5,3},7};
int e=5;
int pos=Locate(s,e);
printf("Locate to %d\n",pos);
}
（2）实验3.3顺序表的插入运算
# include <stdio.h>
typedef int Elemtype;
typedef struct{
Elemtype elem[100];
int last;
}SeqList;
#define OK 1
#define ERROR 0
int IntList(SeqList*L,int i,Elemtype e) {
int k;
if((i<1)||(i>L->last+2))
{
printf("插入位置i值不合法");
return(ERROR);
}
if(L->last>=100-1)
{
printf("表已满，无法插入");
return(ERROR);
}
for(k=L->last;k>=i-1;k--)
L->elem[k+1]=L->elem[k];
L->elem[i-1]=e;
L->last++;
return(OK);
}
void printList(SeqList s)
{
for(int i=0;i<=st;i++)
printf("%d\t",s.elem[i]);
printf("\n");
}
void main(){
SeqList L={{1,2,4,6,8,10,5,11},8};
printList(L);
IntList(&L,3,10);
printList(L);
}
（3）实验3.4顺序表的删除运算
# include <stdio.h>
typedef int Elemtype;
typedef struct{
Elemtype elem[100];
int last;
}SeqList;
int DelList(SeqList * L,int i,ElemType * e) {
int k;
if((i<=1)||(i>L->last+1))
{
printf("删除位置不合法！");
return(ERROR);
}
* e=L->elem[i-1];
for(k=i;i<=L->last;k++)
L->elem[k-1]=L->elem[k];
L->last--;
return(OK);
}
void printList(SeqList s){
printf("%d",st);
for (int i=0;i<=st;i++){
printf("%d\t",s.elem[i]);
}
printf("\n");
}
void main(){
SeqList L={{1,2,9,8,4,5,3,6,2},9};
int * h;
printList(L);
DelList(&L,3,h);
printList(L);
}
六、讨论
1.在实现顺序表的插入与删除运算时，不懂的创建printList函数，把顺序表的元素逐项输出。
2.在实现3个算法时，不会编写main函数。
3.在编写程序时，在语法上出现了很多错误，包括一些细节问题。
七、参考文献
列举自己在本次准备实验、进行实验和撰写实验报告过程中用到的参考文献资料。
格式如下:
耿国华张德全周明全等编著，《数据结构--用C语言描述》，高等教育出版社，2015年7月，41-45页。
