数据结构.第2章.线性表.1.链式ppt课件.ppt

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

1、数据结构DataStructures张凯计算机学院软件工程系2011年3月12日一元多项式的表示及相加第2章线性表线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现§2.3线性表的链式表示及实现线性表的链式表示线性表的链式实现链表的运算效率分析线性表的链式表示逻辑上相邻，物理上不一定相邻§2.3线性表的链式表示及实现‘a’201BH‘b’1087H…………‘z’NULLa1a2…………an/HeadHeadDataLinkDataLinkDataLinkDataLink链表存放示意图如下：(a，b，c，d，e…,z)线性

2、表的链式表示线性表的链式存储结构，也称为链表。数据元素通过指针表示数据元素之间的关系。§2.3线性表的链式表示及实现a1a2……an/Head特点1：每个存储结点都包含两部分：数据和。特点2：在单链表中，除了首元结点外，任一结点的存储位置由指示。其直接前驱结点的链域的值指针域(链域)线性链表的有关术语结点:数据元素的存储映像。由数据域和指针域两部分组成；链表:n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为链式存储结构§2.3线性表的链式表示及实现信息域指针域结点的结构infonexta1a2……an/Head线性链

3、表的有关术语头指针:是指向链表中第一个结点(或为头结点或为首元结点)的指针。单链表可由一个头指针唯一确定。§2.3线性表的链式表示及实现a1a2……an/Head头指针线性链表的有关术语头结点:是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点:存储第一个数据元素a1的结点§2.3线性表的链式表示及实现a1……an/Head首元结点头结点线性链表的有关术语链表设置头结点的作用插入或删除表中任何结点，都需修改前一结点的指针域。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除结点时需单独

4、处理，操作较复杂。带头结点的链表，链表指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。§2.3线性表的链式表示及实现一个线性表的逻辑结构为:§2.3线性表的链式表示及实现（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。ZHAO7Head

5、DataLink31上例链表的逻辑结构示意图有以下两种形式§2.3线性表的链式表示及实现①②区别：①无头结点②有头结点ZHAOQIANSUNLIHeadZHOUWUZHENGWANG/ZHAOQIANSUNLIHeadZHOUWUZHENGWANG/线性表的单链表存储结构§2.3线性表的链式表示及实现TypedefstructLnode{ElemTypedata;//数据域structLnode*next;//指针域}Lnode,*LinkList;//*LinkList为Lnode类型的指针线性链表的实现1.单链表的建立2.单

6、链表的查找3.单链表的插入4.单链表的删除5.其它链表形式§2.3线性表的链式表示及实现单链表的建立难点分析：每个数据元素在内存中是“零散”存放的，其首地址怎么找？又怎么一一链接？实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的指针。§2.3线性表的链式表示及实现单链表的建立§2.3线性表的链式表示及实现操作步骤：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入；an四、依次类推，直至输入a1为止。anan-1单链表的建立§2.3线性表的链式

7、表示及实现VoidCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值,建立带表头结点的单链线性表L.L=(LinkList)malloc(sizeof(LNode));L→next=NULL;//先建立一个带头结点的单链表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新结点scanf(&p→data);//输入元素值p→next=L→next;L→next=p;//插入到表头}}//CreateList_L单链表的查找难点：单链表中想

8、取得第i个元素，必须从头指针出发寻找(顺藤摸瓜)，不能随机存取。思路：要修改第i个数据元素，关键是要先找到该结点的指针p，然后用p->data=new_value即可。§2.3线性表的链式表示及实现单链表的查找例1：单链表中GetEl