上堂课要点回顾.ppt

《上堂课要点回顾.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、上堂课要点回顾线性结构(包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。2.线性表逻辑结构：“一对一”或1:1存储结构：顺序、链式运算：修改、插入、删除3.顺序存储特征：逻辑上相邻，物理上也相邻；优点：随机查找快O(1)缺点：插入、删除慢O(n)12.3线性表的链式表示和实现2.3.1链表的表示2.3.2链表的实现2.3.3链表的运算效率分析本节小结(续上堂课）22.3.1链表的表示链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。

2、如何实现？通过指针来实现注意：每个存储结点都包含两部分：数据域和指针域31.链式存储特点：逻辑上相邻，物理上不一定相邻链表存放示意图如下：a1heada2/an……讨论1：每个存储结点都包含两部分：数据域和。讨论2：在单链表中，除了首元结点外，任一结点的存储位置由指示。其直接前驱结点的链域的值指针域(链域)4例1画出26个英文字母表的链式存储结构。该字母表在内存的链式存放示意图如下：解：该字母表的逻辑结构为：（a,b,…,y,z）aheadb/z……各结点由两个域组成：数据域：存储元素数值数据；指针域：存储直接后

3、继或者直接前驱的存储位置。指针数据指针数据指针或样式：52.与链式存储有关的术语1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。4）头指针、头结点和首元结点以教材P27图2.5和图2.6内容为例说明。64、头指针、头结点和首元结点示意图如下：

4、头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点。7一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG194

5、3ZHOU25例：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是318上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/WANGH②ZHAOQIANLISUNZHOUWUZHENG/WANGH区别：①无头结点②有头结点9答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的

6、情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。^头指针^头指针头结点无头结点有头结点10讨论3.头结点的数据域内装的是什么？头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。答：讨论4.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，所以要采用结构数据类型。答：什么是结构类型？如何书写表达？——补充C语言内容头结点的数据域H113.补充结构数据类型及其C语言表示

7、法①类型定义和变量说明可以合写为：typedefstructzifubiao{//zifubiao是自定义结构类型名称chardata;//定义数据域的变量名及其类型structzifubiao*next;//定义指针域的变量名及其类型}test，*head;/*test是zifubiao结构类型的变量,*head是zifubiao结构类型的头指针*/以26个字母的链表为例，每个结点都有两个分量：字符型指针型假设每个结点用变量test表示，其中两个分量分别用data和*next表示，则：*nextdatatest12

8、设p为指向链表的第i个元素的指针,则第i个元素的数据域写为，指针域写为。至此应可看懂教材P28对于单链表的抽象描述。练习：p->dataai的值p->nextai+1的地址13附2：教材P22关于顺序表的抽象定义：Typedefstruct{//若后面不再用，可省略结构名ElemType*elem;//表基址intlength;//表长（特指元