数据结构第2章线性表链表部分课件.ppt

1、4/27/2023 1第第2 2章章 表表 学习要点学习要点:理解表是由同一类型的元素组成的有限序列的概念。理解表是由同一类型的元素组成的有限序列的概念。熟悉定义在抽象数据类型表上的基本运算。熟悉定义在抽象数据类型表上的基本运算。掌握实现抽象数据类型的一般步骤。掌握实现抽象数据类型的一般步骤。掌握用数组实现表的步骤和方法。掌握用数组实现表的步骤和方法。掌握用指针实现表的步骤和方法。掌握用指针实现表的步骤和方法。掌握用间接寻址技术实现表的步骤和方法。掌握用间接寻址技术实现表的步骤和方法。掌握用游标实现表的步骤和方法。掌握用游标实现表的步骤和方法。掌握单循环链表的实现方法和步骤。掌握单循环链表的实

2、现方法和步骤。掌握双链表的实现方法和步骤。掌握双链表的实现方法和步骤。熟悉表的搜索游标的概念和实现方法。熟悉表的搜索游标的概念和实现方法。学生成绩登记表学生成绩登记表姓姓 名名英语英语数据结构数据结构高数高数学号学号丁一丁一9678870101李二李二8790780102张三张三6786860103孙红孙红6981960104王冬王冬8774660105线性结构的特点 国贸学院 8522105工商学院 8523150计算机学院 8521088会计学院 8525789统计学院 8528136 外语学院 8523026 例：“最后一个”数据元素 直接前驱 直接后继 存在唯一一个被称作“第一个”的数

3、据元素；存在唯一一个被称作“最后一个”的数据元素；除第一个之外的数据元素均只有一个直接前驱；除最后一个之外的数据元素均只有一个直接后继。数据元素的 有限集 4/27/2023 42.1 ADT2.1 ADT表表(List)(List)2.1.1 ADT表的表的数据模型数据模型 表是由表是由n(n 0)个同一类型个同一类型(通常记为通常记为 datatype类型类型)的元素的元素(结点结点)a(1)，a(2)，a(n)组成的有限序列。组成的有限序列。1.有限性有限性：线性表中数据元素的个数是有穷的。：线性表中数据元素的个数是有穷的。2.相同性相同性：线性表中数据元素的类型是同一的。：线性表中数据

4、元素的类型是同一的。3.顺序性顺序性：线性表中相邻的数据元素：线性表中相邻的数据元素ai-1和和ai之间存在之间存在序偶关系序偶关系(ai-1,ai)，即，即ai-1是是ai的前驱，的前驱，ai是是ai-1的后继；的后继；a1 无前驱，无前驱，an无后继，其它每个元素有且仅有一个前无后继，其它每个元素有且仅有一个前驱和一个后继。驱和一个后继。2.1.2 有关的概念与术语有关的概念与术语 表的长度（表的长度（Length）：表的元素的个数即数据模型中的）：表的元素的个数即数据模型中的n。空（空（Empty）表：）表：n=0的表。的表。表中元素表中元素(结点结点)的的位置（位置（Position）

5、：当：当n 1时，说时，说k是表中是表中第第 k个元素个元素a(k)的位置，的位置，k=1，2，n。表中元素表中元素(结点结点)的前驱的前驱：当：当n1时，说时，说a(k)是是a(k+1)的前驱的前驱 (k=1，2，n-1)。表中元素表中元素(结点结点)的后继：当的后继：当n1时，说时，说a(k+1)是是a(k)的后继的后继(k=1，2，n-1)。非空表非空表记为：记为：L（a1,a2,ai-1,ai,an)a1a3a4ana24/27/2023 72.1 ADT2.1 ADT表（表（ListList）2.1.3 ADT表的逻辑特征表的逻辑特征非空表有且仅有一个开始元素非空表有且仅有一个开始元

6、素a(1)，它没有前驱。，它没有前驱。当当n1时，它有一个后继时，它有一个后继a(2)。非空表有且仅有一个结束元素非空表有且仅有一个结束元素a(n)，它没有后继。，它没有后继。当当n1时，它有一个前驱时，它有一个前驱a(n-1)。当当n2时，表的其余元素时，表的其余元素a(k)(2 k n-1)都有一个都有一个前驱和一个后继。前驱和一个后继。表中元素按其位置的顺序关系是它们之间的逻辑表中元素按其位置的顺序关系是它们之间的逻辑关系关系。线性表的基本操作：（1）初始化（置空表）可由构造函数实现（2）求表长（Length）（3）查找或定位（Find）（4）插入（Insert）（5）删除（Remove

7、）（6）排序（Sort）（7）判空（IsEmpty）线性表的抽象数据类型4/27/2023 92.1 ADT2.1 ADT表（表（ListList）2.1.4 ADT表上定义的常用的基本运算表上定义的常用的基本运算(1)Empty():(2)Size():(3)Locate(x):(4)Retrieve(k,x):获取表中位置获取表中位置k处的元素，存入处的元素，存入x中中(5)Insert(k,x):在表的在表的位置位置k之后之后插入元素插入元素x(6)Erase(k,x):从表中删除位置从表中删除位置k处的元素，存入处的元素，存入x中中(7)PrintList():注意：运算名称的取法、需

8、要的形式参数的个数、各注意：运算名称的取法、需要的形式参数的个数、各参数的取名和含义、具体运算的约定、各参数取值参数的取名和含义、具体运算的约定、各参数取值（特别是边界值）和返回值的约定、各参数取值和（特别是边界值）和返回值的约定、各参数取值和返回值的类型的确定。返回值的类型的确定。进一步说明进一步说明:（1）线性表的基本操作根据实际应用是而定；）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来）复杂的操作可以通过基本操作的组合来实现；实现；（3）对不同的应用，操作的接口可能不同。对不同的应用，操作的接口可能不同。线性表的抽象数据类型应用 扩大线性表 LA，将存在于

9、线性表 LB 中而不存在于 线性表 LA 中的数据元素插入到线性表 LA 中去。1从 LB 中一个数据元素；2依值在 LA 中进行；3若不存在，则之。重复上述三步直至 LB 中的数据元素取完为止。其中的每一步能否利用抽象数据类型线性表中定义 的基本操作来完成呢？在实际的程序设计中线性表的基本操作，必须线性表类型。确 定 存 储 结 构 实 现 基 本 操 作 在计算机中用一组的存储单 元线性表的各个数据元素，称作 线性表的顺序存储结构或顺序映象。用这 种方法存储的线性表称作顺序表。例：线性表 (1,2,3,4,5,6)的存储结构：1 2 3 4 5 6 一个典型的。一个。1 2 3 4 5 6

10、 依次存储，地址连续 中间没有空出存储单元。存储结构：地址不连续 中间存在空的存储单元。如何实现顺序表的内存分配？如何实现顺序表的内存分配？顺序表顺序表一维数组一维数组用一维数组 表示顺序表 类型相同 用一变量表示顺序表的长度属性 线性表长可变（删除）顺序表（元素）地址连续 随机存取 依次存放 数组（元素）数组长度不可动态定义 4/27/2023 172.2 2.2 用数组用数组(data)(data)实现实现ADTADT表（表（ListList）2.2.1 用数组实现用数组实现的的ADT表的特征数据及其类型表的特征数据及其类型表的元素的类型：表的元素的类型：为了适应表元素类型（为了适应表元素

11、类型（datatype）的变化，应将表类的变化，应将表类List定义为一个模板类。在该模板类定义为一个模板类。在该模板类中，用中，用T来表示用户指定的元素类型（来表示用户指定的元素类型（datatype）。表的长度表的长度:n(约定约定n=0为空表为空表)数组能容纳的表的最大长度数组能容纳的表的最大长度:MaxSize约定数组下标为约定数组下标为k-1的分量存放表的第的分量存放表的第k个元素，个元素，k=1,2,3,n。其结构如下图。其结构如下图用什么属性来描述顺序表？用什么属性来描述顺序表？存储空间的起始位置存储空间的起始位置顺序表的容量（最大长度）顺序表的容量（最大长度）顺序表的当前长度顺

12、序表的当前长度4/27/2023 19a1a2an01n-112n内存内存data数组下标数组下标元素位置元素位置MaxSize-1备用空间备用空间4/27/2023 202.2.2用数组实现用数组实现的的ADTADT表（表（ListList）的定义）的定义templateclass List private:int n;int MaxSize;T *data;/表元素数组表元素数组 public:List(int Max=10);/构造函数构造函数 List()delete data;/析构函数析构函数，复杂性，复杂性O（1）bool Empty()const return n=0;/复杂性

13、复杂性O（1）int Size()const return n;/复杂性复杂性O（1）int Locate(const T&x)const；/返回表中元素返回表中元素x位置位置 bool Retrieve(int k,T&x)const;/返回表中第返回表中第k个元素，存于个元素，存于x中中 List&Insert(int k,const T&x);/在表的位置在表的位置k处之后插入元素处之后插入元素x List&Erase(int k,T&x);/从表中删除位置从表中删除位置k处的元素，存入处的元素，存入x中中 void PrintList(ostream&out)const;；4/27/2

14、023 212.2.3 ADTADT表（表（ListList）的定义中未实现的函数的实现）的定义中未实现的函数的实现 与分析与分析（1）构造函数构造函数:List(int Max)templateList:List(int Max)/构造函数构造函数 MaxSize=Max;data=new TMaxSize;n=0;内存分配 MaxSizedatan4/27/2023 232.2.3 ADTADT表（表（ListList）的定义中未实现的函数的）的定义中未实现的函数的实现与分析（续）实现与分析（续）（2）为）为元素元素x定位定位:int Locate(const T&x)consttempl

15、ateint List:Locate(const T&x)constfor(int i=0;i n;i+)if(datai=x)return+i;return 0;4/27/2023 242.2.3 ADTADT表（表（ListList）的定义中未实现的函数的）的定义中未实现的函数的实现与分析（续）实现与分析（续）（3 3）检索）检索第第k个元素个元素给给x:bool Retrieve(int k,T&x)const;templatebool List:Retrieve(int k,T&x)const if(k n)return false;x=datak-1;return true;4/27

16、/2023 25插入定义：线性表的插入是指在插入定义：线性表的插入是指在第第k k（0 0 k k n n）个元素个元素之之后后插入一个新的数据元素插入一个新的数据元素x x，使使长度为长度为n n的线性表的线性表nkkaaaaa,1,21 变成变成长度为长度为n+1n+1的线性表的线性表nkkaaxaaa,1,21 需将第需将第k+1k+1至第至第n n共（共（n-kn-k)个个元素后移元素后移图示图示算法：算法：复杂性分析复杂性分析ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要

17、反映这个变化33例：例：（35，12，24，42），），在在i=2的位置上插入的位置上插入33。435122442a1a2a3a40 1 2 3 4422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件4/27/2023 28内存内存data数组下标数组下标元素位置元素位置a1a2akak+1an01k-1n-1kn12kk+1nn+1内存内存data数组下标数组下标元素位置元素位置a1a2akak+1an01k-1n-1kn12kk+1nn+1an-1xtemplateList&List:Insert(int k,const T&x)if(kn)cout out_bou

18、nds;else if(n=MaxSize)cout=k;i-)datai+1=datai;datak=x;n+;return*this;4/27/2023 30算法时间复杂度算法时间复杂度T(n)最坏情况时间复杂性：最坏情况时间复杂性：O(n)平均情况时间复杂性：平均情况时间复杂性：设设Pk是在第是在第k个元素之后插入个元素之后插入一个元素的概率，则在长度为一个元素的概率，则在长度为n的线性表中插入一个的线性表中插入一个元素时，所需移动的元素次数的平均次数为：元素时，所需移动的元素次数的平均次数为：nkkINknPE0)(nOnTnknPnEnPnkkINk 02)(1111则若认为4/27

19、/2023 31删除定义：线性表的删除是指将删除定义：线性表的删除是指将第第k k（1 1 k k n n）个个元素元素删除，使删除，使长度为长度为n n的线性表的线性表nkkkaaaaaa,11,21 变成变成长度为长度为n-1n-1的线性表的线性表nkkaaaaa,11,21 需将第需将第k+1k+1至第至第n n共（共（n-kn-k)个个元素前移元素前移图示图示算法：算法：复杂性分析复杂性分析ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化例：（例：（35,33,1

20、2,24,42），），删除删除i=2的数据元素。的数据元素。535a1a2a3a40 1 2 3 4422412334a51224424/27/2023 34内存内存a1a2akak+1an01k-1data数组下标数组下标n-1kn12k元素序号元素序号k+1nn+1内存内存a1a2ak+1data数组下数组下标标01k-1n-1kn12k元素序号元素序号k+1nn+1anak+2n-2n-1templateList&List:Erase(int k,T&x)if(Retrieve(k,x)for(int i=k;in;i+)datai-1=datai;n-;return*this;else

21、coutout bounds;return*this;4/27/2023 36nkkDEknQE1)(nOnTnknnEnQnkDEk121)(11则若认为故在顺序表中插入或删除一个元素时，平均移动表中约一半的元素，当n很大时，效率很低算法时间复杂度算法时间复杂度T(n)最坏情况时间复杂性：最坏情况时间复杂性：O(n)平均情况时间复杂性：平均情况时间复杂性：设设Qk是删除第是删除第k个元素的概率，则在长个元素的概率，则在长度为度为n的线性表中删除一个元素时，所需移动的元素次数的平均的线性表中删除一个元素时，所需移动的元素次数的平均次数为：次数为：4/27/2023 372.2 2.2 用数组用

22、数组(data)(data)实现实现ADTADT表（表（ListList）2.2.3 ADTADT表（表（ListList）的定义中未实现的函数的实现与分析）的定义中未实现的函数的实现与分析(续）续）（6 6）输出所有元素）输出所有元素:void PrintList(ostream&out)const;templatevoid List:PrintList(ostream&out)const for(int i=0;i n;i+)out datai=无须为表示表中元素之间的 逻辑关系而增加额外的存储空间可随机存取任一元素缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充

23、分表容量难以扩充2.2 用数组用数组(data)实现实现ADT表（表（List）4/27/2023 392.3 用指针实现用指针实现ADTADT表（表（ListList）2.3.0 2.3.0 用指针实现用指针实现ADTADT表动因和构想表动因和构想动因：动因：用用数组数组实现表实现表存在存在两个两个缺点缺点。构想：构想：表的每一个表的每一个元素元素(data)存放在随时向操作系存放在随时向操作系统申请到的单元（统申请到的单元（结点结点）内，前后结点靠）内，前后结点靠一个指一个指针来链接（单链）针来链接（单链）。结构如下图：。结构如下图：4/27/2023 402.3.1 用指针实现用指针实现

24、ADT表的特征数据及其表的特征数据及其类型类型表的元素的类型：表的元素的类型：为了适应表元素类型（为了适应表元素类型（datatype）的变的变化，应将表类化，应将表类List定义为一个模板类。在该模板类中，用定义为一个模板类。在该模板类中，用T来表示用户指定的元素类型（来表示用户指定的元素类型（datatype）。表的结点类型：表的结点类型：一个结点存放一个元素和一个指针一个结点存放一个元素和一个指针，用类，用类Node表示。表示。指针指向指针指向类类Node的结点。的结点。单链表单链表的结构如下图：的结构如下图：只需指向表的第一个结点的指针（只需指向表的第一个结点的指针（first）便可）

25、便可表示单链表表示单链表。数据域数据域 指针域指针域结点结点4/27/2023 41例例 线性表线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)4313103771925数据域数据域指针域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址存储地址1713192531374331first第一个元第一个元素指针素指针ZHAOQIANSUNLIZHOUWUZHENGWANG0first有几个节点?第一个节点的地址存储在哪个指针里?除了首元结点外，任一结点的存储位置由除了首元结点外，任一结点的存储位置由_指示指示每个节点包括哪两部分?4344cu

26、rrent=head;45current=current-link;46 建立包含三个结点的链表。#include class Node public:int data;Node*next;void main()Node*first,*a,*b,*c,*q;a=new Node;b=new Node;c=new Node;first=a;a-data=1;a-next=b;b-data=2;b-next=c;c-data=3;c-next=NULL;q=first;while(q!=NULL)coutdatanext;4/27/2023 492.3 用指针实现用指针实现ADTADT表表(Lis

27、t)(List)2.3.2 2.3.2 结点模板类的定义结点模板类的定义template class List;/前视声明前视声明template class Node friend class List;private:T data;Node*next;4/27/2023 502.3.3 用指针实现的用指针实现的ADTADT表（表（ListList）的定义）的定义template class Iterator;/前视声明前视声明 (去掉去掉)templateclass List friend class Iterator;private:Node*first;public:List()fir

28、st=0;List();bool Empty()const return first=0;int Length()const;bool Retrieve(int k,T&x)const;int Locate(const T&x)const;List&Insert(int k,const T&x);List&Delete(int k,T&x);void PrintList(ostream&out)const;4/27/2023 512.3 用指针实现用指针实现ADTADT表表(List)(List)2.3.4 表（表（ListList）的定义中未实现的函数的实现与分析）的定义中未实现的函数的实现

29、与分析（1 1）析构函数）析构函数:List();templateList:List()Node*next;while(first)next=first-next;delete first;first=next;最坏情况时间复杂性最坏情况时间复杂性(n)4/27/2023 522.3 用指针实现用指针实现ADTADT表表(List)(List)2.3.4 表（表（ListList）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）（2 2）求表长）求表长:int Length()const;templateint List:Length()const Node*cur

30、rent=first;int len=0;while(current)len+;current=current-next;return len;最坏情况时间复杂性最坏情况时间复杂性(n)4/27/2023 532.3 用指针实现用指针实现ADTADT表表(List)(List)2.3.4 表（表（ListList）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）（3 3）为为元素元素x定位定位:int Locate(const T&x);templateint List:Locate(const T&x)const Node*current=first;int in

31、dex=1;/index of current while(current¤t-data!=x)current=current-next;index+;if(current)return index;return 0;最坏情况时间复杂性最坏情况时间复杂性O O（n n）核心操作（关键操作）：核心操作（关键操作）：工作指针后移工作指针后移。从头结点（或开始结点）出发，通过工作从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链表指针的反复后移而将整个单链表“审视审视”一遍的方法称为一遍的方法称为扫描扫描（或遍历）。（或遍历）。firsta1pa2panaipp检索成功检索成

32、功p检索失败检索失败检索第检索第k个元素给个元素给x:bool Retrieve(int k,T&x)const;1.工作指针工作指针current初始化初始化;累加器累加器index初始化初始化;2.1 工作指针工作指针current后移后移;2.2 累加器累加器index加加1;2.循环直到循环直到current为空或为空或current指向第指向第i个结点个结点3.若若current为空，则第为空，则第i个元素不存在，抛出查找个元素不存在，抛出查找位置异常；否则查找成功，返回结点位置异常；否则查找成功，返回结点current的数的数据元素；据元素；4/27/2023 562.3 用指针实

33、现用指针实现ADTADT表表(List)(List)2.3.4 ADTADT表（表（ListList）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）（4 4）检索）检索第第k个元素个元素给给x:bool Retrieve(int k,T&x)const;templatebool List:Retrieve(int k,T&x)const if(k 1)return false;Node*current=first;int index=1;while(index next;index+;if(current)x=current-data;return true;re

34、turn false;时间复杂性时间复杂性(k)Current+能否完成指针后移？能否完成指针后移？a1a24/27/2023 572.3 用指针实现用指针实现ADTADT表表(List)(List)2.3.4 ADTADT表（表（ListList）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）（5 5）在位置在位置k后后插入元素插入元素x:List&Insert(int k,const T&x);函数的运算步骤是：函数的运算步骤是：先扫描链表找到插入位置先扫描链表找到插入位置p，然后建立一个，然后建立一个存储待插入元素的新结点存储待插入元素的新结点y，再将结点，

35、再将结点y插入到结点插入到结点p之后。插之后。插入的入的示意图如下示意图如下 yyy-next=first;firstfirst=y;py-next=p-next;p-next=y;1.工作指针工作指针p初始化；累加器初始化；累加器j清零；清零；2.查找第查找第i-1个结点并使工作指针个结点并使工作指针p指向该指向该结点；结点；3.若查找不成功，说明插入位置不合理，若查找不成功，说明插入位置不合理，抛出插入位置异常；否则，抛出插入位置异常；否则，3.1 生成一个元素值为生成一个元素值为x的新结点的新结点s；3.2 将新结点将新结点s插入到结点插入到结点p之后；之后；4/27/2023 592.

36、3.4（5 5）（续）（续）templateList&List:Insert(int k,const T&x)if(k 0)throw OutOfBounds();Node*p=first;/找插入位置找插入位置for(int index=1;index next;if(k 0&!p)throw OutOfBounds();Node*y=new Node;y-data=x;if(k)/在位置在位置p处插入处插入 y-next=p-next;p-next=y;else/在表首插入需要特殊处理（在表首插入需要特殊处理（若引入表头结点则可纳入一般情况若引入表头结点则可纳入一般情况）y-next=fi

37、rst;first=y;return*this;时间复杂性时间复杂性O O（k k）4/27/2023 602.3 用指针实现用指针实现ADTADT表表(List)(List)2.3.4 ADTADT表（表（ListList）的定义中未实现的函数的实现与分析）的定义中未实现的函数的实现与分析（续）（续）（6 6）删除）删除位置位置k处的元素处的元素给给x:List&Delete(int k,T&x);函数的运算步骤是：依次函数的运算步骤是：依次处理以下处理以下3种情况。（种情况。（）k1。其删除的。其删除的示意图如下示意图如下p=q-next;4/27/2023 612.3.4 （6 6）（续

38、）（续）templateList&List:Delete(int k,T&x)if(k 1|!first)throw OutOfBounds();Node*p=first;if(k=1)/删除表首元素删除表首元素需要特殊处理（需要特殊处理（若若引入哨兵结点引入哨兵结点则可纳入一般情况则可纳入一般情况）first=first-next;else /找表中找表中第第k-1个元素个元素所在结点所在结点q Node*q=first;for(int index=1;index next;if(!q|!q-next)throw OutOfBounds();p=q-next;/让让p指向指向 第第k个元素所

39、在结点个元素所在结点 q-next=p-next;/删除结点删除结点p x=p-data;/第第k个元素存入个元素存入x并释放结点并释放结点p delete p;return*this;时间复杂性时间复杂性O O（k k）？!q=因为因为q为空而退出为空而退出for循环循环=indexnext=找到找到index=k-1的位置，但该位置已是表尾，的位置，但该位置已是表尾，即：即：q-next=0。在链表中设置 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表fir

40、st=NULL空表空表头指针：头指针：指向第一个结点的地址。指向第一个结点的地址。尾标志：尾标志：终端结点的指针域为空。终端结点的指针域为空。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表空表和非空表不统一，缺点？空表和非空表不统一，缺点？如何将空表与非空表统一如何将空表与非空表统一？头结点：头结点：在在单链表的第以一个元素结点之前附设一个单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。类型相同的

41、结点，以便空表和非空表处理统一。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表非空表非空表firsta1a2an空表空表first头结点：在单链表的第一个结点之前人为地附设的一个结点。数据域 L a1a2an L 头结点存放头结点的地址。头结点 不存放任何数据 存放附加信息（链表的结点个数等）。指针域 存放第一个结点的地址 （若线性表为空表，则“空”，用 表示。）问题：在链表中设置有什么好处？作用：可以对空表、非空表进行统一处理；可以对首元结点及其他结点统一处理。结论：编程更方便。4/27/2023 682.3 用指针实现用指针实现ADTADT表表(List)(Lis

42、t)2.3.4 ADTADT表（表（ListList）的定义中未实现的函数的实现与分析）的定义中未实现的函数的实现与分析（续）（续）（7 7）输出所有元素）输出所有元素:void PrintList(ostream&out)const;templatevoid List:PrintList(ostream&out)const Node*current;for(current=first;current;current=current-next)out data ;时间复杂性时间复杂性O O（n n）4/27/2023 692.3 用指针实现用指针实现ADTADT表表(List)(List)2.

43、3.6 2.3.6 用用指针指针实现实现ADTADT表（表（ListList）的优缺点）的优缺点优点：优点：避免了数组要求连续的单元存储元素的缺点避免了数组要求连续的单元存储元素的缺点，因而在执行，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。空缺。(当元素的粒度很大时，移动元素是很费时的。当元素的粒度很大时，移动元素是很费时的。)缺点：缺点：需要在每个单元中设置指针来表示表中元素之间的逻辑关需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而系，因而增加了额外的存储空间增加了额外的存储空间，为获得上述优点付出代，为获

44、得上述优点付出代价。价。补充#includeclass Node public:int data;Node*next;class List private:Node*first;public:List()first=0;List();bool Empty()const return first=0;int Length()const;bool Retrieve(int k,int&x)const;int Locate(const int&x)const;List&Insert(int k,const int&x);List&Delete(int k,int&x);void PrintList(

45、)const;先写这些代码，然后编译看是否有问题？能不能链接？void main()List l1;如果想能运行，调用了什么函数？需加哪个函数的实现？void main()List l1;l1.Insert(0,3);l1.PrintList();如果想能运行，又调用了什么函数？需加哪个函数的实现？List&List:Insert(int k,const int&x)if(k 0)coutout bounds;return*this;Node*p=first;/找插入位置 for(int index=1;index next;if(k 0&!p)coutdata=x;if(k)/在位置p处插入

46、 y-next=p-next;p-next=y;else/在表首插入需要特殊处理（若引入表头结点则可纳入一般情况）y-next=first;first=y;return*this;void List:PrintList()const Node*current;for(current=first;current;current=current-next)cout data next 终端结点：将单链表扫描一遍，时间为终端结点：将单链表扫描一遍，时间为O(n)照此，找最后元素只需照此，找最后元素只需O(1),找首元素仍只需找首元素仍只需O(1)。一个存储结构设计得是否合理，取决于基于该存储一个存储

47、结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。结构的运算是否方便，时间性能是否提高。在循环链表上实现各种运算与链表的情形类似，不同之处：循环终止条件不是p或p-next是否为空，而是判断是否指向表首；4/27/2023 822.6 用单循环链实现表用单循环链实现表2.6.2 用单循环链实现的用单循环链实现的表的特征数据及其表的特征数据及其类型类型表的元素的类型：同指针实现的类表的元素的类型：同指针实现的类T。表的结点类型：同指针实现的类表的结点类型：同指针实现的类Node。用单循环链实现的用单循环链实现的表本身需要的数据表本身需要的数据 int n;/表的长度表的长

48、度 Node*last;/指向表尾的指针指向表尾的指针4/27/2023 83 2.6.3 单循环链表单循环链表List的模板类的定义的模板类的定义templateclass Iterator;templateclass List friend class Iterator;private:int n;/表的长度表的长度 Node*last;/指向表尾的指针指向表尾的指针 public:List();List();bool Empty()const return n=0;int Length()const return n;bool Retrieve(int k,T&x)const;int L

49、ocate(const T&x)const;List&Insert(int k,const T&x);List&Delete(int k,T&x);void PrintList(ostream&out)const;区别于单链表中无表区别于单链表中无表长的定义！长的定义！4/27/2023 842.6 用单循环链实现表用单循环链实现表2.6.4 ADTADT表（表（ListList）的定义中未实现的函数的实）的定义中未实现的函数的实现与分析现与分析（1 1）构造函数）构造函数List();/初始化一个空表初始化一个空表templateList:List()Node*y=new Node;y-ne

50、xt=y;last=y;/表中只有一个哨兵结点表中只有一个哨兵结点 n=0;/时间复杂性为时间复杂性为O O（1 1）4/27/2023 852.6 用单循环链实现表用单循环链实现表2.6.4 表的定义中未实现的函数的实现与分析表的定义中未实现的函数的实现与分析（2 2）析构函数）析构函数:List();templateList:List()Node*next;while(!Empty()/非空表的释放非空表的释放 next=last-next;delete last;n-;last=next;delete last;/空表的释放空表的释放 /时间复杂性为时间复杂性为O O（n n）4/27/