基本数据结构及其运算3线性链表.ppt

《基本数据结构及其运算3线性链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章基本数据公安海警学院2021/10/3主讲：胡云琴结构及运算第2章基本数据结构及运算2.1数据结构的基本概念2.2线性表及其顺序存储结构2.3线性链表2.4线性表的索引存储结构2.5数组2.6树与二叉树2.7图复习提问1：线性表顺序存储结构具有哪些优点？1）线性表顺序存储结构具有简单、运算方便等优点,随机存取（时间复杂度为O(1)）；2）无需为表示表中元素之间的逻辑关系而增加额外的存储空间；3）适合小规模、长度固定的线性表2.线性表顺序存储结构具有哪些缺点？在插入、删除时要移动大量的节点，效率低表的大小固定，容量难扩充，易出现上溢原因：顺序存储的存储结构与逻

2、辑结构是一致的。解决方法：突破离散存放用指针来表示元素之间的关系。引入线性链表链接存储的线性表用链表实现线性表（非连续存储）线性表元素：a1、a2、a3、a4....链表链点线性关系：a1a2a3a4指针域，指针关系链表概述：链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。“头指针”,以变量head表示,是线性表中第一个数据元素的存储地址；每个结点都应包括两部分:用户需要用的实际数据和下一结点的地址(指针域)；最后一个结点,该结点的指针域不再指向其他结点,它称为"表尾",它的指针域放一个"NULL"(表示"空地址"),链表到此结束。head12

3、49135614751021135614751021NULL1249ABCD2.3.1线性链表的基本概念线性链表2.32.3.2线性链表的基本运算2.3.3带链的栈与队列2.3.4循环链表2.3.5多项式的表示与运算特点：(1)定义：采用链式存储结构的线性表称为链表，其采用一组任意的存储单元来存放线性表的数据元素（可零散的分布于内存单元的任何位置上）。2.3.1线性链表的基本概念结点之间可以连续，可以不连续存储结点的逻辑顺序与物理顺序可以不一致表可扩充(2)结点(Node)组成通过指针域，不论结点的物理次序如何，都可将其按逻辑顺序依次链接在一起构成线性表。数据域—

4、—存储数据元素本身数据域指针域指针域——存储下一元素的存储位置链顺序表存储地址存储状态0031赵0033钱0035孙0037李0039周0041吴0043郑0045王链表存储地址存储状态0001李0007钱0013孙0019王0025吴0031赵0037郑0043周004300130001NULL0037000700190025头指针H数据域0031指针域结点指针链表线性表顺序存储与链表存储比较H赵钱孙李周吴郑王^线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号

5、地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？Z47Y31V23X17U05100119104108116112答：X=Y=Z=首址=末址=。例1：116NULL(0)100112108（3）链表分类①单链表：只设置一个指向后继结点地址的指针域。②循环链表：将其首尾相接构成一个环状结构。③双向链表：有两个指针域，分别指向本结点的前驱结点和后继结点的链表。a1(1）定义：所有结点的指针域中只包含一个指针(存储直接后继结点的存储位置)的链表。a2a

6、n^······空指针头指针头指针头结点带头结点的单链表单链表常用头指针来命名，如La,Head.2.3.2线性链表(单链表)的基本运算(2）头结点在单链表的第一个结点之前人为地附设的一个结点。数据域La1a2an^…L^头指针头结点头指针存放头结点的地址，指向链表中第一个结点（或为头结点或第一个元素）的指针。头结点不存放任何数据存放附加信息(链表的结点个数等)指针域存放第一个结点的地址（若线性表为空表，则“空”，用^表示。）可以看到，空表和非空表不统一heada1a2an∧非空表head=NULL空表带头结点的非空表heada1a2an∧带头结点的空表head∧

7、设置头结点的好处：①起始结点位置存放在头结点指针域中，故在链表第一个位置上操作与表中其他位置上操作一致，无须特殊处理。②头指针Head始终是指向头结点的非空指针，统一了空表与非空表的操作，简化链表操作的实现。请写出该线性链表的逻辑顺序和链表结构图？存储地址数据域指针域1D437B1313C119HNULL25F3731A737G1943E25头指针H31AH^B···C头指针头指针例2：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI4

8、37QIA