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

算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 1第第2 2章章 表表 学习要点学习要点:理解表是由同一类型的元素组成的有限序列的概念。理解表是由同一类型的元素组成的有限序列的概念。熟悉定义在抽象数据类型表上的基本运算。熟悉定义在抽象数据类型表上的基本运算。掌握实现抽象数据类型的一般步骤。掌握实现抽象数据类型的一般步骤。掌握用数组实现表的步骤和方法。掌握用数组实现表的步骤和方法。掌握用指针实现表的步骤和方法。掌握用指针实现表的步骤和方法。掌握用间接寻址技术实现表的步骤和方法。掌握用间接寻址技术实现表的步骤和方法。掌握用游标实现表的步骤和方法。掌握用游标实现表的步骤和方法。掌握单循环链表的实现方法和步骤。掌握单循环链表的实现方法和步骤。掌握双链表的实现方法和步骤。掌握双链表的实现方法和步骤。熟悉表的搜索游标的概念和实现方法。熟悉表的搜索游标的概念和实现方法。8/13/2023 1第2章 表 学习要点:算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures学生成绩登记表学生成绩登记表姓姓 名名英语英语数据结构数据结构高数高数学号学号丁一丁一9678870101李二李二8790780102张三张三6786860103孙红孙红6981960104王冬王冬8774660105学生成绩登记表姓 名英语数据结构高数学号丁一967887 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures线性结构的特点 法学院法学院 85231018523101 国贸学院 8522105工商学院 8523150计算机学院 8521088会计学院 8525789统计学院 8528136 外语学院 8523026 例：“第一个第一个”数据元素数据元素 “最后一个”数据元素 直接前驱 直接后继 存在唯一一个被称作“第一个”的数据元素；存在唯一一个被称作“最后一个”的数据元素；除第一个之外的数据元素均只有一个直接前驱；除最后一个之外的数据元素均只有一个直接后继。数据元素的 非空非空有限集 线性结构的特点 法学院 8523101 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 42.1 ADT2.1 ADT表表(List)(List)2.1.1 ADT表的表的数据模型数据模型 表是由表是由n(n 0)个同一类型个同一类型(通常记为通常记为 datatype类型类型)的元素的元素(结点结点)a(1)，a(2)，a(n)组成的有限序列。组成的有限序列。1.有限性有限性：线性表中数据元素的个数是有穷的。：线性表中数据元素的个数是有穷的。2.相同性相同性：线性表中数据元素的类型是同一的。：线性表中数据元素的类型是同一的。3.顺序性顺序性：线性表中相邻的数据元素：线性表中相邻的数据元素ai-1和和ai之间存在之间存在序偶关系序偶关系(ai-1,ai)，即，即ai-1是是ai的前驱，的前驱，ai是是ai-1的后继；的后继；a1 无前驱，无前驱，an无后继，其它每个元素有且仅有一个前无后继，其它每个元素有且仅有一个前驱和一个后继。驱和一个后继。8/13/2023 42.1 ADT表(List)2.1.1 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures2.1.2 有关的概念与术语有关的概念与术语表的长度（表的长度（Length）：表的元素的个数即数据模型中的）：表的元素的个数即数据模型中的n。空（空（Empty）表：）表：n=0的表。的表。表中元素表中元素(结点结点)的的位置（位置（Position）：当：当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)。2.1.2 有关的概念与术语 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures非空表非空表记为：记为：L（a1,a2,ai-1,ai,an)a1a3a4ana2非空表记为：L（a1,a2,ai-1,ai 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 72.1 ADT2.1 ADT表（表（ListList）2.1.3 ADT表的逻辑特征表的逻辑特征非空表有且仅有一个开始元素非空表有且仅有一个开始元素a(1)，它没有前驱。，它没有前驱。当当n1时，它有一个后继时，它有一个后继a(2)。非空表有且仅有一个结束元素非空表有且仅有一个结束元素a(n)，它没有后继。，它没有后继。当当n1时，它有一个前驱时，它有一个前驱a(n-1)。当当n2时，表的其余元素时，表的其余元素a(k)(2 k n-1)都有一个都有一个前驱和一个后继。前驱和一个后继。表中元素按其位置的顺序关系是它们之间的逻辑表中元素按其位置的顺序关系是它们之间的逻辑关系关系。8/13/2023 72.1 ADT表（List）2.1.3 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures线性表的基本操作：（1）初始化（置空表）可由构造函数实现（2）求表长（Length）（3）查找或定位（Find）（4）插入（Insert）（5）删除（Remove）（6）排序（Sort）（7）判空（IsEmpty）线性表的抽象数据类型线性表的基本操作：线性表的抽象数据类型 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 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/13/2023 92.1 ADT表（List）2.1.4 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures进一步说明进一步说明:（1）线性表的基本操作根据实际应用是而定；）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来）复杂的操作可以通过基本操作的组合来实现；实现；（3）对不同的应用，操作的接口可能不同。对不同的应用，操作的接口可能不同。进一步说明:算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures线性表的抽象数据类型应用扩大线性表 LA，将存在于线性表 LB 中而不存在于 线性表 LA 中的数据元素插入到线性表 LA 中去。线性表的抽象数据类型应用扩大线性表 LA，将存在于线性表 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures思路：1从 LB 中取出一个数据元素；2依值在 LA 中进行查询；3若不存在，则插入之。重复上述三步直至 LB 中的数据元素取完为止。其中的每一步能否利用抽象数据类型线性表其中的每一步能否利用抽象数据类型线性表中定义中定义 的基本操作来完成呢的基本操作来完成呢？思路：其中的每一步能否利用抽象数据类型线性表中定义 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures 在实际的程序设计中要引用要引用线性表的基本操作，必须先实现先实现线性表类型。确 定 存 储 结 构 实 现 基 本 操 作 在实际的程序设计中要引用线性表的基本操作，确 实 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures在计算机中用一组地址连续的存储单 元依次存储线性表的各个数据元素，称作 线性表的顺序存储结构或顺序映象。用这 种方法存储的线性表称作顺序表。在计算机中用一组地址连续的存储单 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures例：线性表 (1,2,3,4,5,6)的存储结构：1 2 3 4 5 6 是是一个典型的线形表顺序存储结构线形表顺序存储结构。不是不是一个线形表顺序存储结构线形表顺序存储结构。1 2 3 4 5 6 依次存储，地址连续 中间没有空出存储单元。存储结构：地址不连续 中间存在空的存储单元。例：线性表 (1,2,3,4,5,6)的存储 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures如何实现顺序表的内存分配？如何实现顺序表的内存分配？顺序表顺序表一维数组一维数组用一维数组 表示顺序表 类型相同 用一变量表示顺序表的长度属性 线性表长可变（删除）顺序表（元素）地址连续 随机存取 依次存放 数组（元素）数组长度不可动态定义 如何实现顺序表的内存分配？顺序表一维数组用一维数组 类型相同 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 172.2 2.2 用数用数组组(data)(data)实现实现ADTADT表（表（ListList）2.2.1 用数用数组实现组实现的的ADT表的特征数据及其类型表的特征数据及其类型表的元素的类型：表的元素的类型：为了适应表元素类型（为了适应表元素类型（datatype）的变化，应将表类的变化，应将表类List定义为一个模板类。在该模板类定义为一个模板类。在该模板类中，用中，用T来表示用户指定的元素类型（来表示用户指定的元素类型（datatype）。表的长度表的长度:n(约定约定n=0为空表为空表)数组能容纳的表的最大长度数组能容纳的表的最大长度:MaxSize约定数组下标为约定数组下标为k-1的分量存放表的第的分量存放表的第k个元素，个元素，k=1,2,3,n。其结构如下图。其结构如下图8/13/2023 172.2 用数组(data)实现ADT 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures用什么属性来描述顺序表？用什么属性来描述顺序表？存储空间的起始位置存储空间的起始位置顺序表的容量（最大长度）顺序表的容量（最大长度）顺序表的当前长度顺序表的当前长度用什么属性来描述顺序表？存储空间的起始位置顺序表的容量（最大 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 19a1a2an01n-112n内存内存data数组下标数组下标元素位置元素位置MaxSize-1备用空间备用空间8/13/2023 19a1a2an01n-112n内存da 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 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;/复杂性复杂性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;；8/13/2023 202.2.2用数组实现的ADT表（Li 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 212.2.3 ADTADT表（表（ListList）的定义中未实现的函数的实现）的定义中未实现的函数的实现 与分析与分析（1）构造函数构造函数:List(int Max)templateList:List(int Max)/构造函数构造函数 MaxSize=Max;data=new TMaxSize;n=0;最坏情况时间复杂性最坏情况时间复杂性最坏情况时间复杂性最坏情况时间复杂性OO（1 1）8/13/2023 212.2.3 ADT表（List）的定 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures内存分配 MaxSizeMaxSizedatadatann内存分配 MaxSizedatan 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 232.2.3 ADTADT表（表（ListList）的定义中未实现的函数的）的定义中未实现的函数的实现与分析（续）实现与分析（续）（2）为）为元素元素x定位定位:int Locate(const T&x)consttemplateint List:Locate(const T&x)constfor(int i=0;i n;i+)if(datai=x)return+i;return 0;最坏情况时间复杂性最坏情况时间复杂性最坏情况时间复杂性最坏情况时间复杂性OO（n n）8/13/2023 232.2.3 ADT表（List）的定 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 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;最坏情况时间复杂性最坏情况时间复杂性最坏情况时间复杂性最坏情况时间复杂性OO（1 1）8/13/2023 242.2.3 ADT表（List）的 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 25插入定义：线性表的插入是指在插入定义：线性表的插入是指在第第k k（0 0 k k n n）个元素个元素之之后后插入一个新的数据元素插入一个新的数据元素x x，使使长度为长度为n n的线性表的线性表 变成变成长度为长度为n+1n+1的线性表的线性表 需将第需将第k+1k+1至第至第n n共（共（n-k)n-k)个个元素后移元素后移2.2.3 ADT2.2.3 ADT表（表（表（表（ListList）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）（4 4）在）在）在）在位置位置位置位置k k后插入后插入后插入后插入元素元素元素元素x:List&Insert(int k,const T&x);x:List&Insert(int k,const T&x);图示图示算法：算法：复杂性分析复杂性分析8/13/2023 25插入定义：线性表的插入是指在第k（0 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structuresai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures33例：例：（35，12，24，42），），在在i=2的位置上插入的位置上插入33。435122442a1a2a3a40 1 2 3 4422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件33例：（35，12，24，42），在i=2的位置上插入33 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 28内存内存data数组下标数组下标元素位置元素位置a1a2akak+1an01k-1n-1kn12kk+1nn+1内存内存data数组下标数组下标元素位置元素位置a1a2akak+1an01k-1n-1kn12kk+1nn+1an-1x8/13/2023 28内存data数组下标元素位置a1a2 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data StructurestemplateList&List:Insert(int k,const T&x)if(kn)cout out_bounds;else if(n=MaxSize)cout=k;i-)datai+1=datai;datak=x;n+;return*this;template 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 30算法时间复杂度算法时间复杂度T(n)最坏情况时间复杂性：最坏情况时间复杂性：O(n)平均情况时间复杂性：平均情况时间复杂性：设设Pk是在第是在第k个元素之后插入个元素之后插入一个元素的概率，则在长度为一个元素的概率，则在长度为n的线性表中插入一个的线性表中插入一个元素时，所需移动的元素次数的平均次数为：元素时，所需移动的元素次数的平均次数为：8/13/2023 30算法时间复杂度T(n)算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 31删除定义：线性表的删除是指将删除定义：线性表的删除是指将第第k k（1 1 k k n n）个个元素元素删除，使删除，使长度为长度为n n的线性表的线性表 变成变成长度为长度为n-1n-1的线性表的线性表 需将第需将第k+1k+1至第至第n n共（共（n-k)n-k)个个元素前移元素前移2.2.3 2.2.3 ADTADT表（表（表（表（ListList）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）（5 5）删除位置删除位置删除位置删除位置k k处处处处的元素给的元素给的元素给的元素给x:List&Erase(int k,T&x);x:List&Erase(int k,T&x);图示图示算法：算法：复杂性分析复杂性分析8/13/2023 31删除定义：线性表的删除是指将第k（1 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structuresai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures例：（例：（35,33,12,24,42），），删除删除i=2的数据元素。的数据元素。535a1a2a3a40 1 2 3 4422412334a5122442例：（35,33,12,24,42），删除i=2的数 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 34内存内存a1a2akak+1an01k-1data数组下标数组下标n-1kn12k元素序号元素序号k+1nn+1内存内存a1a2ak+1data数组下数组下标标01k-1n-1kn12k元素序号元素序号k+1nn+1anak+2n-2n-18/13/2023 34内存a1a2akak+1an01k-算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data StructurestemplateList&List:Erase(int k,T&x)if(Retrieve(k,x)for(int i=k;in;i+)datai-1=datai;n-;return*this;elsecoutout bounds;return*this;template 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 36故在顺序表中插入或删除一个元素时，平均移动表中约一半的元素，当n很大时，效率很低算法时间复杂度算法时间复杂度T(n)最坏情况时间复杂性：最坏情况时间复杂性：O(n)平均情况时间复杂性：平均情况时间复杂性：设设Qk是删除第是删除第k个元素的概率，则在长度个元素的概率，则在长度为为n的线性表中删除一个元素时，所需移动的元素次数的平均次的线性表中删除一个元素时，所需移动的元素次数的平均次数为：数为：8/13/2023 36故在顺序表中插入或删除一个元素时，平 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 372.2 2.2 用数用数组组(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=无须为表示表中元素之间的 逻辑关系而增加额外的存储空间可随机存取任一元素缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充2.2 用数组用数组(data)实现实现ADT表（表（List）8/13/2023 382.2.4用数组(data)实现AD 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 392.3 用指针实现用指针实现ADTADT表（表（ListList）2.3.0 2.3.0 用指针实现用指针实现ADTADT表动因和构想表动因和构想动因：动因：用用数数组组实现实现表表存在存在两个两个缺点缺点。构想：构想：表的每一个表的每一个元素元素(data)存放在随时向操作系存放在随时向操作系统申请到的单元（统申请到的单元（结点结点）内，前后结点靠）内，前后结点靠一个指一个指针来链接（单链）针来链接（单链）。结构如下图：。结构如下图：8/13/2023 392.3 用指针实现ADT表（List 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 402.3.1 用指针实现用指针实现ADT表的特征数据及其表的特征数据及其类型类型表的元素的类型：表的元素的类型：为了适应表元素类型（为了适应表元素类型（datatype）的变的变化，应将表类化，应将表类List定义为一个模板类。在该模板类中，用定义为一个模板类。在该模板类中，用T来表示用户指定的元素类型（来表示用户指定的元素类型（datatype）。表的结点类型：表的结点类型：一个结点存放一个元素和一个指针一个结点存放一个元素和一个指针，用类，用类Node表示。表示。指针指向指针指向类类Node的结点。的结点。单链表单链表的结构如下图：的结构如下图：只需指向表的第一个结点的指针（只需指向表的第一个结点的指针（first）便可）便可表示单链表表示单链表。数据域数据域 指针域指针域结点结点8/13/2023 402.3.1 用指针实现ADT表的特征 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 41例例 线性表线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)4313103771925数据域数据域指针域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址存储地址1713192531374331first第一个元第一个元素指针素指针ZHAOQIANSUNLIZHOUWUZHENGWANG0first8/13/2023 41例 线性表 (ZHAO,QIAN 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures有几个节点?第一个节点的地址存储在哪个指针里?除了首元结点外，任一结点的存储位置由除了首元结点外，任一结点的存储位置由_指示指示每个节点包括哪两部分?有几个节点?算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures4343 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures44current=head;44current=head;算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures45current=current-link;45current=current-link;算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures4646 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures建立包含三个结点的链表。#includeclass Node public:int data;Node*next;建立包含三个结点的链表。算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structuresvoid 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;void main()q=first;算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 492.3 用指针实现用指针实现ADTADT表表(List)(List)2.3.2 2.3.2 结点模板类的定义结点模板类的定义template class List;/前前视视声明声明template class Node friend class List;private:T data;Node*next;8/13/2023 492.3 用指针实现ADT表(List 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 502.3.3 用指针实现的用指针实现的ADTADT表（表（ListList）的定义）的定义template class Iterator;/前前视声明声明 (去掉去掉)templateclass List friend class Iterator;private:Node*first;public:List()first=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;8/13/2023 502.3.3 用指针实现的ADT表（算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 512.3 用指针实现用指针实现ADTADT表表(List)(List)2.3.4 表（表（ListList）的定义中未实现的函数的实现与分析）的定义中未实现的函数的实现与分析（1 1）析构函数）析构函数:List();templateList:List()Node*next;while(first)next=first-next;delete first;first=next;最坏情况时间复杂性最坏情况时间复杂性8/13/2023 512.3 用指针实现ADT表(List 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 522.3 用指针实现用指针实现ADTADT表表(List)(List)2.3.4 表（表（ListList）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）（2 2）求表长）求表长:int Length()const;templateint List:Length()const Node*current=first;int len=0;while(current)len+;current=current-next;return len;最坏情况时间复杂性最坏情况时间复杂性8/13/2023 522.3 用指针实现ADT表(List 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 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 index=1;/index of current while(current¤t-data!=x)current=current-next;index+;if(current)return index;return 0;最坏情况时间复杂性最坏情况时间复杂性O O（n n）8/13/2023 532.3 用指针实现ADT表(List 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures核心操作（关键操作）：核心操作（关键操作）：工作指针后移工作指针后移。从头结点（或开始结点）出发，通过工作从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链表指针的反复后移而将整个单链表“审视审视”一遍的方法称为一遍的方法称为扫描扫描（或遍历）。（或遍历）。firsta1pa2panaipp检索成功检索成功p检索失败检索失败检索第检索第k个元素给个元素给x:bool Retrieve(int k,T&x)const;firsta1pa2panaipp检索成功p检索失败检索第 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures1.工工作作指指针针current初初始始化化;累累加加器器index初初始始化化;2.1 工作指针工作指针current后移后移;2.2 累加器累加器index加加1;2.循环直到循环直到current为空或为空或current指向第指向第i个结点个结点3.若若current为为空空，则则第第i个个元元素素不不存存在在，抛抛出出查查找找位位置置异异常常；否否则则查查找找成成功功，返返回回结结点点current的的数数据元素；据元素；1.工作指针current初始化;累加器index初始化 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 562.3 用指针实现用指针实现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;return false;时间复杂性时间复杂性Current+Current+能否完成指针后移？能否完成指针后移？能否完成指针后移？能否完成指针后移？a1a28/13/2023 562.3 用指针实现ADT表(List 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 572.3 用指针实现用指针实现ADTADT表表(List)(List)2.3.4 ADTADT表（表（ListList）的定义中未实现的函数的实现与分析（续）的定义中未实现的函数的实现与分析（续）（5 5）在位置在位置k后后插入元素插入元素x:List&Insert(int k,const T&x);函数的运算步骤是：函数的运算步骤是：先扫描链表找到插入位置先扫描链表找到插入位置p，然后建立一个，然后建立一个存储待插入元素的新结点存储待插入元素的新结点y，再将结点，再将结点y插入到结点插入到结点p之后。插入之后。插入的的示意图如下示意图如下 yyy-next=first;firstfirst=y;py-next=p-next;p-next=y;8/13/2023 572.3 用指针实现ADT表(List 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures1.工作指针工作指针p初始化；累加器初始化；累加器j清零；清零；2.查找第查找第i-1个结点并使工作指针个结点并使工作指针p指向该指向该结点；结点；3.若查找不成功，说明插入位置不合理，若查找不成功，说明插入位置不合理，抛出插入位置异常；否则，抛出插入位置异常；否则，3.1 生成一个元素值为生成一个元素值为x的新结点的新结点s；3.2 将新结点将新结点s插入到结点插入到结点p之后；之后；1.工作指针p初始化；累加器j清零；算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 592.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=first;first=y;return*this;时间复杂性时间复杂性O O（k k）8/13/2023 592.3.4（5）（续）算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 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;q-next=p-next;q-next=p-next;delete p;delete p;8/13/2023 602.3 用指针实现ADT表(List 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures7/11/2024 612.3.4 （6 6）（续）（续）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个元素所在个元素所在结结点点 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。8/13/2023 612.3.4 （6）（续）？!q 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures在链表中设置头结点在链表中设置头结点 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表头指针：头指针：指向第一个结点的地址。指向第一个结点的地址。尾标志：尾标志：终端结点的指针域为空。终端结点的指针域为空。线性表的链接存储结构及实现单链表02000208030 算算算算 法法法法 与与与与 数数数数 据据据据 结结结结 构构构构 Algorithms and Data StructuresAlgorithms and Data Structures2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta