[理学]第2章 线性表链表.pptVIP

温故知新环节---顺序表的特点 1、特点：逻辑上相邻物理上也相邻 2、优点： 构造原理简单，易理解 若已知每个数据元素的所占用存储单元的字节数，且知道第1个元素的存储位置，则可以任意随机存取任意元素，存取速度快。 只需存放数据元素本身的信息，无其他额外空间开销。 3、缺点： 需要一片地址连续的空间 存储空间的分配需要事先进行，因而使得应该分配的存储空间大小不易估计。 进行插入或删除操作时，需要事先对插入和删除位置后的所有元素逐个进行移动，操作时间效率低。 针对顺序表的三条缺点 2.3.1 线性表的链式存储—链表 链式存储不要求逻辑上相邻的数据元素在物理位置上也相邻，仅通过指针来映射数据元素之间的逻辑关系。 typedef char ElemType typedef struct LNode { ElemType data; struct LNode *next; } LinkList; 尾插法建立链表 需要两个指针s---指向新结点 r---指向尾结点 LinkList *s,*r; 第一步： r指向尾结点 第二步：申请新结点 第三步：尾插法链接结点 再循环23步骤直到n个结点完成插入 结论 在线性表长度变化较大或难以估计其储存规模时采用动态链表，否则采用顺序存储 对线性表的操作主要是查找而很少做插入和删除操作时，采用顺序存储，否则采用链式存储 总之，两种情况各有优缺点，应看具体情况进行讨论。 * * 第2章 线性表 2.1 线性表的基本概念 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的应用 需要一片地址连续的空间 存储空间大小不易估计 插入或删除操作时间复杂度为O(n) 2.3 线性表的链式存储 2.3.1 线性表的链式存储—链表 2.3.2 单链表基本运算的实现 存储结点包含 数据域：所有存元素本身的信息； 指针域：元素之间逻辑关系的信息；包含有后继结点的地址信息。 2个问题 如何构造链表数据类型？ 链表上可进行什么基本操作？ 在每个结点中除包含有数据域外,只设置一个指针域,用以指向其后继结点,这样构成的链接表称为线性单向链接表,简称单链表； 解决第一个问题---如何构造链表数据类型 每个结点数据类型：用LinkList表示 它的成员： 数据域：用data表示,其类型通用类型标识符ElemType 指针域：这里用next表示。 LinkList类型的定义如下: typedef struct LNode /*定义单链表结点类型*/ { ElemType data; struct LNode *next; /*指向后继结点*/ } LinkList; 数据类型的构造 带头结点单链表示意图 在线性表的链式存储中,为了便于插入和删除算法的实现,每个链表带有一个头结点,并通过头结点的指针惟一标识该链表。 终端节点称为尾结点，尾结点的指针域为NULL 第一个问题解决了 (1) 初始化线性表InitList() (2) 建立单链表CreatList(L) (3) 输出线性表DispList(L) (4) 判线性表是否为空表ListEmpty(L) (5) 求线性表的长度ListLength(L) (6) 求线性表L中指定位置的某个数据元素GetElem(L,i,e) (7) 按元素值查找LocateElem(L,e) (8) 插入数据元素ListInsert(L,i,e) (9) 删除数据元素ListDelete(L,i,e) 解决第二个问题---如何构造链表基本算法 1. 初始化线性表InitList() 该运算建立一个空的单链表,即创建一个头结点。 LinkList * InitList (void) { L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/ L-next=NULL; return L; } 2.3.2 单链表基本运算的实现 DATA NEXT head NULL 2. 建立单链表 先考虑如何建立单链表。假设我们通过一个含有n个数据的数组来建立单链表。建立单链表的常用方法有如下两种: (1) 尾插法建表 该方法是将新结点插到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。采用尾插法建表的算法如下: b c d a i=0 i=1 i=2 i=3 L 头结点 a d c b ∧ b 采用尾插