《数据结构课件代码》第2章 线性表.ppt

《《数据结构课件代码》第2章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性表(二)张成文北京邮电大学计算机学院主要内容2.7线性表的链式存储结构表示2.8单链表2.9循环链表2.10双向链表2.11各种链式存储结构的比较2.12顺序表与链表的比较2.13小结线性表的链式存储结构表示结点(Node):既要存储线性表的每个数据元素值,又要存储指示其后继结点的地址(或位置)信息,以表示结点间的逻辑关系。这两部分信息组成的存储映象叫做结点(Node)。1线性表的链式存储结构表示让每个存储结点都包含两部分：数据域和指针域指针数据指针数据指针或样式：数据域：存储元素的值指针域：存储直接后继或直接前驱元素的存储地址设计思想：牺牲空间效

2、率换取时间效率其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现！链式存储结构特点La1a2a3与链式存储有关的术语1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双向链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域（直接前驱和直接后继）的链表，称为双向链表；首尾相接的链表称为循环链表。a1heada2an……循环链表示意图：head4）头指针、头结点和首元结点的区别示意

3、图如下：头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a1的结点。下面举例说明。头指针L头指针L头结点首元结点首元结点空表：L=NULLL^1264126440164016头结点的作用：插入和删除第一个数据元素时不必对头指针进行特殊处理。^^与链式存储有关的术语一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG）

4、，其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例1：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31称：头指针H的值是31例2：线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。其中指针X，Y，Z的

5、值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？Z47Y31V23X17U05100119答：X=Y=Z=,首址=末址=.104108116112116NULL/0100108112单链表单链表:链表中的每个结点只有一个指针域,我们将这种链表称为单链表。单链表包括两个域:数据域用来存储结点的值;指针域用来存储数据元素的直接后继的地址(或位置)。从链表的整体结构上看，链表可以是空链，也可以由一个或多个结点组成。每条链有一个入口的头结点，该结点仅指示链中第一个结点的地址。如是空链，则可表示为“0”或“∧”，它类似于一个常量。每条链的最后一个

6、结点的链指针为“0”，也可用“∧”作为链的结束标志。下图给出了链表的示意形式。图(a)中有一个头结点和具有A、B、C、D数据元素的链，图(b)所示为线性链表的一般表示，结点与结点之间用箭头链接。单链表链表图示(a)链表的图示；(b)链表的一般表示以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。头结点a1a2…...an^头指针头指针有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空讨论:链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结

7、点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。答：以26个字母的链表为例，每个结点都有两个分量：字符型指针型假设每个结点用变量node表示，结点指针用p表示，其中两个分量分别用data和*next表示，该如何书写？p*nextdatanode方式1：直接表示为node.data＝'a'；node.next=q方式2：p指向结点首地址，然后p->data='a';p->next=q;方式3：p指向结点首地址，然后(*p).data='a'；(*p).next＝q‘a’‘b’qp单链表的存储结构描述typedefstructNode//结点类型

8、定义{ElemTypedata；structNode