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

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

1、第二章基本数据公安海警学院2021/9/14主讲：胡云琴结构及运算第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"(表示"空地址"),链表到此结束。head12491356147510

3、21135614751021NULL1249ABCD2.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号地址空间中，每个结点由数据（占2个字节）和指针（

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

6、表常用头指针来命名，如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），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIA