第二章线性表2.ppt

《第二章线性表2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章排序目录1第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例22.3线性表的链式表示和实现2.3.1链表的表示2.3.2链表的实现2.3.3链表的运算效率分析3链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现！让每个存储结点都包含两部分：数据域和指针域指针数据指针数据指针或样式：数据域：存储元素数值数据指针域：存储直接后继或者直接

2、前驱的存储位置设计思想：牺牲空间效率换取时间效率2.3.1链表的表示4例：请画出26个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：解：该字母表的逻辑结构为：（a,b,…,y,z）链表存放示意图如下：a1heada2/an……讨论1：每个存储结点都包含两部分：数据域和。讨论2：在单链表中，除了首元结点外，任一结点的存储位置由指示。其直接前驱结点的链域的值指针域(链域)51）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双

3、链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……循环链表示意图：head(2)与链式存储有关的术语：64）头指针、头结点和首元结点的区别头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a1的结点

4、。示意图如下：7答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；^头指针无头结点^头指针头结点有头结点有头结点时，当头结点的指针域为空时表示空表。头结点不计入链表长度！8一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针

5、的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31称：头指针H的值是31（3）举例例1：9上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/WANGH②ZHAOQIANLISUNZHOUWUZHENG/WANGH区别：①无头结点②有头结点头结点不计入链表长度！10线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五

6、个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？Z47Y31V23X17U05100119104108116112116NULL(0)100108112答：X=Y=Z=,首址=末址=。例2：11讨论:链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。答：以26个

7、字母的链表为例，每个结点都有两个分量：字符型指针型设每个结点用变量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’qp12设p为指向链表的第i个元素的指针,则第i个元素的数据域写为，指针域写为。练习：p->dataai的值p->nextai+1的地址附1

8、：介绍C的三个有用的库函数/算符（都在中）：sizeof(x)——计算变量