2线性表第的二部分.pdf

知识点回顾  线性表的定义：由n(n ≧0)个数据元素组成的有限序列。 线性表是一个序列。若所含数据元素存在多个，则： ①存在一个唯一的被称为“第一个”的数据元素； ②存在一个唯一的被称为“最后一个”的数据元素； ③除第一个元素外，每个元素均有唯一一个直接前驱； ④除最后一个元素外，每个元素均有唯一一个直接后继。 线性表中的数据元素是有限的。  一对一的逻辑关系 数据结构 知识点回顾  线性表的顺序存储 （顺序表）：把线性表的结点按逻辑顺序 依次存放在一组地址连续的存储单元里。  采用结构类型来定义线性表的顺序存储结构： # define MaxSize 100 //表容量 typedef int DataType; // 以int为例 MaxSize个 data struct Sqlist{ ……….. DataType data[MaxSize]; int length;// 当前表中元素数 }; length  线性表存取、插入和删除的时间复杂度： Sqlist  存取：O(1)  插入和删除：O(n) 。时间主要耗费在表中结点的移动操作。 数据结构 知识点回顾  线性表的链式存储 （线性链表）：用一组任意的存储单元存 储线性表中的数据元素。线性链表通过每个结点的指针域将 线性表的n个结点按其逻辑次序链接在一起。  每一个结点只包含一个指针域的链表，称为单链表。 data next 链表结点结构 data ：数据域，存放结点的值。 next ：指针域，存放结点的直接后继的地址。 p p-next a a i-1 i p-data p-next-data 数据结构 知识点回顾  用带指针的结构体类型来描述线性表的单链表存储结构： typedef struct Lnode { ElemType data; /*数据域，保存结点的值*/ struct Lnode *next; /*指针域*/ }LNode; /*结点的类型*/ typedef struct Lnode * LinkList ；/*定义LinkList*/  单链表的存取、插入和删除的时间复杂度：  存取：O(n) 。时间主要耗费在工作指针后移。  插入和删除：  未知插入或删除的结点的指针位置：O(n) 。  已知插入或删除的结点的指针位置：O( 1) 。 数据结构 单链表的基本操作: 建表 4. 建立单链表 建立单链表的过程就是一个动态生成单链表的过程：从一个空表开 始，重复读入数据，生成新结点，将读入数据存放到新结点的数据 域中，然后将新结点插入到当前链表中，直到读入结束标志为止。 (1) 头插入法 建表 头插入法是指每次插入新结点总是在表的前端进行，即新结点作为链 表的第一个结点。头插入法生成的链表中结点的逻辑顺序和输入数据的顺序 正好相反。 数据结构 5 数据结构 单链表的建立: 头插入法 算法思路 ① 声明一个结点p ； ② 初