单链表的基本概念.

Presentation on theme: "单链表的基本概念."— Presentation transcript:

1 单链表的基本概念

2 顺序表的优点：随机存取，操作方便。 顺序表的缺点：在做插入和删除操作的时候，需要移动大量的数据元素。此外，由于数组长度相对固定，当表中元素个数变化较大时，必然导致空间的浪费。
链式存储结构的引入 链式存储结构，它客服了顺序表插入和删除时需要移动大量元素的缺点，但同时也失去了随机存取的优点。

3  线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。

4 这两部分信息组成数据元素ai的存储映像，称为结点(node)。 链式存储结构
 因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。 这两部分信息组成数据元素ai的存储映像，称为结点(node)。 链式存储结构

5 它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。
链式存储结构 数据域 指针域 n个结点(ai(1≤i≤n))链结成一个链表，即为线性表 (a1,a2,…,an)的链式存储结构。 又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

6 单链表实例 1 LI 43 7 QIAN 13 SUN 19 WANG NULL 25 WU 37 31 ZHENG ZHOU 头指针H
存储地址 数据域 指针域 1 LI 43 7 QIAN 13 SUN 19 WANG NULL 25 WU 37 31 ZHENG ZHOU 头指针H 31 单链表实例 线性表中第一个结点的位置是在存储地址31的位置上。 ZHAO 7 说明ZHAO之后的结点位置是在地址7的位置，依次类推，可以得到这个单链表所表达的线性表是： (ZHAO,QIAN,SUN,LI,ZHOU, WU,ZHENG, WANG)

7 如何将链表画成用箭头相链接的结点的序列？
H ● 如何将链表画成用箭头相链接的结点的序列？ ZHAO ● QIAN ● SUN ● LI ● ZHOU ● WU ● ZHENG ● WANG ^

8 typedef struct LNode{ ElemType data; //数据域 struct LNode
typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; 单链表的存储结构 类型 LNode* LinkList p; Lnode *p;

9 一般情况下，为了能方便进行链表的一些操作，比如结点的插入、删除等，我们通常在单链表的第一个结点之前附设一个结点，称之为头结点。头结点可以不存储任何信息，也可以存放线性表的长度等附加信息。头结点的指针域存储指向第一个结点的指针，或者说第一个结点的存储地址。 单链表的存储结构 … L ● a1 ● a2 ● an ^ 空表的结构 L ^