Chapter02 线性表_3

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

1、1/90第二章线性表内容：2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示及相加1线性表的链式存储结构是把线性表的数据元素存放在结点中,通过结点的地址域把结点链接起来，结点间的链接关系体现了线性表中数据元素间的顺序关系。用链式存储结构实现的线性表称为线性链表或链表。线性表的链式存储结构2线性表的链式存储结构为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构，如图所示。datanext图2-2链表结点结构da

2、ta：数据域，存放结点的值。next：指针域，存放结点的直接后继的地址。3/22结点(node)：线性表中一个数据元素所占用的存储空间。它由数据域与指针域两部分组成，数据域用来存储用户的有效数据；指针域用来存储直接后继数据元素所在结点的地址。王二麻子0x99fc数据域指针域结点4/22线性表的链式存储结构链式存储：用一组任意的存储单元存储线性表中的数据元素。存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中结点的逻辑顺序和物理顺序不一定相同,如下例。5/226/901536元素21400元素11346元素3∧元素4134

3、5h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h6ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针7/22线性链表可分为单向链表和双向链表：线性表的链式存储结构8单链表9单向链表在线性链表中，如果每个结点只有一个链（指针），则称为单向链

4、表（singlylinkedlist）。单向链表各结点的链通常指向其后继结点。10单向链表为操作方便，总是在链表的第一个结点之前附设一个头结点head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。头结点的指针指向第一个结点的位置。若线性表为空表，则头结点的指针域为“空”！11/22单向链表3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfathat⋀head图带头结点的单链表的逻辑状态、物理存储方式单链表是由表头唯一确定，因此单链表可以用头指针的名字来命

5、名。例1、线性表L=(bat，cat，eat，fat，hat)其带头结点的单链表的逻辑状态和物理存储方式如图所示。12/22单向链表1结点的描述（Page28）C语言中用带指针的结构体类型来描述typedefstructLnode{ElemTypedata;/*数据域，保存结点的值*/structLnode*next;/*指针域*/}LNode;/*结点的类型*/13/22单向链表2结点的实现结点是通过动态分配和释放来实现的，即需要时分配，不需要时释放。实现时是分别使用C语言提供的标准函数：malloc()，realloc()，sizeof()，free()。14/22单向链表动

6、态分配p=(LNode*)malloc(sizeof(LNode));函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。动态释放free(p);系统回收由指针变量p所指向的内存区。P必须是最近一次调用malloc函数时的返回值。15/22单向链表3最常用的基本操作及其示意图⑴结点的赋值LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;p20NULL16/22单向链表⑵常见的指针操作①q=p;pa……操作前pa……q操作后②q=p->next;bpa……操作前操作后

7、qbpa……③p=p->next;bpa……操作前操作后pba……17/22单向链表操作前ypx……bqa…操作后ypx……bqa…(b)④q->next=p;c…pbqa……操作前操作后qb……ac…p(a)18/22单向链表⑤q->next=p->next;(a)xy…pbqa……操作前操作后qb……axy…p操作前ypx……bqa…操作后ypx……bqa…(b)19/22单向链表（3）结点分量的访问利用结点变量的名字*p访问结点分量方法一：(*p).data和(*p).ne