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

8/8/2023

1第2章表

学习要点:理解表是由同一类型的元素组成的有限序列的概念。熟悉定义在抽象数据类型表上的基本运算。掌握实现抽象数据类型的一般步骤。掌握用数组实现表的步骤和方法。掌握用指针实现表的步骤和方法。掌握用间接寻址技术实现表的步骤和方法。掌握用游标实现表的步骤和方法。掌握单循环链表的实现方法和步骤。掌握双链表的实现方法和步骤。熟悉表的搜索游标的概念和实现方法。7/29/20231第2章表学习要点:学生成绩登记表姓名英语数据结构高数学号丁一9678870101李二8790780102张三6786860103孙红6981960104王冬8774660105学生成绩登记表姓名英语数据结构高数学号丁一967887线性结构的特点法学院8523101

国贸学院8522105工商学院8523150计算机学院8521088会计学院8525789统计学院8528136……外语学院8523026

例：“第一个”数据元素“最后一个”数据元素直接前驱直接后继存在唯一一个被称作“第一个”的数据元素；存在唯一一个被称作“最后一个”的数据元素；除第一个之外的数据元素均只有一个直接前驱；除最后一个之外的数据元素均只有一个直接后继。数据元素的非空有限集线性结构的特点法学院85231018/8/2023

42.1ADT表(List)2.1.1ADT表的数据模型

表是由n(n0)个同一类型(通常记为datatype类型)的元素(结点)a(1)，a(2)，…，a(n)组成的有限序列。1.有限性：线性表中数据元素的个数是有穷的。2.相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1,ai)，即ai-1是ai的前驱，ai是ai-1的后继；a1

无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。

7/29/202342.1ADT表(List)2.1.12.1.2有关的概念与术语表的长度（Length）：表的元素的个数即数据模型中的n。空（Empty）表：n=0的表。表中元素(结点)的位置（Position）：当n1时，说k是表中第

k个元素a(k)的位置，k=1，2，…，n。表中元素(结点)的前驱：当n>1时，说a(k)是a(k+1)的前驱

(k=1，2，…，n-1)。表中元素(结点)的后继：当n>1时，说a(k+1)是a(k)的后继(k=1，2，…，n-1)。2.1.2有关的概念与术语非空表记为：L＝（a1,a2,…,ai-1,ai,…,an)a1a3a4ana2非空表记为：L＝（a1,a2,…,ai-1,ai8/8/2023

72.1ADT表（List）2.1.3ADT表的逻辑特征非空表有且仅有一个开始元素a(1)，它没有前驱。当n>1时，它有一个后继a(2)。非空表有且仅有一个结束元素a(n)，它没有后继。当n>1时，它有一个前驱a(n-1)。当n>2时，表的其余元素a(k)(2kn-1)都有一个前驱和一个后继。表中元素按其位置的顺序关系是它们之间的逻辑关系。7/29/202372.1ADT表（List）2.1.3线性表的基本操作： （1）初始化（置空表）—可由构造函数实现 （2）求表长（Length）

（3）查找或定位（Find） （4）插入（Insert）

（5）删除（Remove） （6）排序（Sort）

（7）判空（IsEmpty）线性表的抽象数据类型线性表的基本操作：线性表的抽象数据类型8/8/2023

92.1ADT表（List）2.1.4ADT表上定义的常用的基本运算(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():注意：运算名称的取法、需要的形式参数的个数、各参数的取名和含义、具体运算的约定、各参数取值（特别是边界值）和返回值的约定、各参数取值和返回值的类型的确定。

7/29/202392.1ADT表（List）2.1.4进一步说明:（1）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。进一步说明:线性表的抽象数据类型应用扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。线性表的抽象数据类型应用扩大线性表LA，将存在于线性表思路：

1．从LB中取出一个数据元素；2．依值在LA中进行查询；3．若不存在，则插入之。重复上述三步直至LB中的数据元素取完为止。其中的每一步能否利用抽象数据类型线性表中定义的基本操作来完成呢？思路：其中的每一步能否利用抽象数据类型线性表中定义

在实际的程序设计中要引用线性表的基本操作，必须先实现线性表类型。确定存储结构实现基本操作在实际的程序设计中要引用线性表的基本操作，确实在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构或顺序映象。用这种方法存储的线性表称作顺序表。在计算机中用一组地址连续的存储单例：线性表(1,2,3,4,5,6)的存储结构：123456是一个典型的线形表顺序存储结构。不是一个线形表顺序存储结构。123456依次存储，地址连续——中间没有空出存储单元。

存储结构：地址不连续——中间存在空的存储单元。例：线性表(1,2,3,4,5,6)的存储如何实现顺序表的内存分配？顺序表一维数组用一维数组表示顺序表类型相同用一变量表示顺序表的长度属性线性表长可变（删除）顺序表（元素）地址连续随机存取依次存放数组（元素）数组长度不可动态定义如何实现顺序表的内存分配？顺序表一维数组用一维数组类型相同8/8/2023

172.2用数组(data)实现ADT表（List）

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

19a1a2an01n-112n内存data数组下标元素位置MaxSize-1备用空间7/29/202319a1a2an01n-112n内存da8/8/2023

202.2.2用数组实现的ADT表（List）的定义template<classT>classList{private:intn;intMaxSize;

T

*data;//表元素数组

public:List(intMax=10); //构造函数

~List(){delete[]data;} //析构函数，复杂性O（1）

boolEmpty()const{returnn==0;} //复杂性O（1）

intSize()const{returnn;} //复杂性O（1）

intLocate(constT&x)const；

//返回表中元素x位置

boolRetrieve(intk,T&x)const;//返回表中第k个元素，存于x中

List<T>&Insert(intk,constT&x);//在表的位置k处之后插入元素x

List<T>&Erase(intk,T&x);//从表中删除位置k处的元素，存入x中

voidPrintList(ostream&out)const;}；

7/29/2023202.2.2用数组实现的ADT表（Li8/8/2023

212.2.3ADT表（List）的定义中未实现的函数的实现与分析（1）构造函数:List(intMax)template<classT>List<T>::List(intMax) //构造函数{MaxSize=Max;data=newT[MaxSize];n=0;}

最坏情况时间复杂性O（1）7/29/2023212.2.3ADT表（List）的定内存分配

MaxSizedatan内存分配MaxSizedatan8/8/2023

232.2.3ADT表（List）的定义中未实现的函数的实现与分析（续）（2）为元素x定位:intLocate(constT&x)consttemplate<classT>intList<T>::Locate(constT&x)const{ for(inti=0;i<n;i++) if(data[i]==x)return++i; return0;}

最坏情况时间复杂性O（n）7/29/2023232.2.3ADT表（List）的定8/8/2023

242.2.3ADT表（List）的定义中未实现的函数的实现与分析（续）（3）检索第k个元素给x:boolRetrieve(intk,T&x)const;template<classT>boolList<T>::Retrieve(intk,T&x)const{if(k<1||k>n)returnfalse;x=data[k-1];returntrue;

}最坏情况时间复杂性O（1）7/29/2023242.2.3ADT表（List）的8/8/2023

25插入定义：线性表的插入是指在第k（0k

n）个元素之后插入一个新的数据元素x，使长度为n的线性表

变成长度为n+1的线性表

需将第k+1至第n共（n-k)个元素后移2.2.3ADT表（List）的定义中未实现的函数的实现与分析（续）（4）在位置k后插入元素x:List<T>&Insert(intk,constT&x);图示算法：复杂性分析7/29/202325插入定义：线性表的插入是指在第k（0ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反33例：（35，12，24，42），在i=2的位置上插入33。435122442a1a2a3a401234422412335什么时候不能插入？注意边界条件33例：（35，12，24，42），在i=2的位置上插入338/8/2023

28内存data数组下标元素位置a1a2akak+1an01k-1n-1kn12kk+1nn+1内存data数组下标元素位置a1a2akak+1an01k-1n-1kn12kk+1nn+1an-1x7/29/202328内存data数组下标元素位置a1a2template<classT>List<T>&List<T>::Insert(intk,constT&x){

if(k<0||k>n) cout<<"out_bounds"; elseif(n==MaxSize) cout<<"no_mem"; else {

for(inti=n-1;i>=k;i--) data[i+1]=data[i];

data[k]=x; n++; }

return*this;}template<classT>8/8/2023

30算法时间复杂度T(n)最坏情况时间复杂性：O(n)平均情况时间复杂性：设Pk是在第k个元素之后插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：7/29/202330算法时间复杂度T(n)8/8/2023

31删除定义：线性表的删除是指将第k（1kn）个元素删除，使长度为n的线性表

变成长度为n-1的线性表

需将第k+1至第n共（n-k)个元素前移2.2.3ADT表（List）的定义中未实现的函数的实现与分析（续）（5）删除位置k处的元素给x:List<T>&Erase(intk,T&x);

图示算法：复杂性分析7/29/202331删除定义：线性表的删除是指将第k（1ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反例：（35,33,12,24,42），删除i=2的数据元素。535a1a2a3a401234422412334a5122442例：（35,33,12,24,42），删除i=2的数8/8/2023

34内存a1a2akak+1an01k-1data数组下标n-1kn12k元素序号k+1nn+1内存a1a2ak+1data数组下标01k-1n-1kn12k元素序号k+1nn+1anak+2n-2n-17/29/202334内存a1a2akak+1an01k-template<classT>List<T>&List<T>::Erase(intk,T&x){

if(Retrieve(k,x)) {

for(inti=k;i<n;i++) data[i-1]=data[i];

n--;

return*this; } else { cout<<"outbounds";

return*this; }}template<classT>8/8/2023

36故在顺序表中插入或删除一个元素时，平均移动表中约一半的元素，当n很大时，效率很低算法时间复杂度T(n)最坏情况时间复杂性：O(n)平均情况时间复杂性：设Qk是删除第k个元素的概率，则在长度为n的线性表中删除一个元素时，所需移动的元素次数的平均次数为：7/29/202336故在顺序表中插入或删除一个元素时，平8/8/2023

372.2用数组(data)实现ADT表（List）2.2.3ADT表（List）的定义中未实现的函数的实现与分析(续）（6）输出所有元素:voidPrintList(ostream&out)const;template<classT>voidList<T>::PrintList(ostream&out)const{for(inti=0;i<n;i++)out<<data[i]<<"";}

最坏情况时间复杂性O（n）

7/29/2023372.2用数组(data)实现ADT8/8/2023

382.2.4用数组(data)实现ADT表（List）的优缺点优点逻辑相邻，物理相邻=>无须为表示表中元素之间的 逻辑关系而增加额外的存储空间可随机存取任一元素缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充2.2用数组(data)实现ADT表（List）7/29/2023382.2.4用数组(data)实现AD8/8/2023

392.3用指针实现ADT表（List）2.3.0用指针实现ADT表动因和构想动因：用数组实现表存在两个缺点。构想：表的每一个元素(data)存放在随时向操作系统申请到的单元（结点）内，前后结点靠一个指针来链接（单链）。结构如下图：7/29/2023392.3用指针实现ADT表（List8/8/2023

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

只需指向表的第一个结点的指针（first）便可表示单链表。数据域指针域结点7/29/2023402.3.1用指针实现ADT表的特征8/8/2023

41例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)4313103771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331first第一个元素指针ZHAOQIANSUNLIZHOUWUZHENGWANG0first7/29/202341例线性表(ZHAO,QIAN有几个节点?第一个节点的地址存储在哪个指针里?除了首元结点外，任一结点的存储位置由______________指示每个节点包括哪两部分?有几个节点?434344current=head;44current=head;45current=current->link;45current=current->link;4646建立包含三个结点的链表。#include<iostream.h>classNode{

public:intdata;Node*next;};建立包含三个结点的链表。voidmain(){ Node*first,*a,*b,*c,*q; a=newNode; b=newNode; c=newNode;

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) { cout<<q->data<<"";

q=q->next; }}voidmain()q=first;8/8/2023

492.3用指针实现ADT表(List)2.3.2结点模板类的定义template<classT>classList; //前视声明template<classT>classNode{friendclassList<T>; private:Tdata;Node<T>*next;};7/29/2023492.3用指针实现ADT表(List8/8/2023

502.3.3用指针实现的ADT表（List）的定义template<classT>classIterator; //前视声明(去掉)template<classT>classList{

friendclassIterator<T>; private:Node<T>*first;public:List(){first=0;}~List();boolEmpty()const{returnfirst==0;}intLength()const;boolRetrieve(intk,T&x)const;intLocate(constT&x)const;List<T>&Insert(intk,constT&x);List<T>&Delete(intk,T&x);voidPrintList(ostream&out)const;};7/29/2023502.3.3用指针实现的ADT表（8/8/2023

512.3用指针实现ADT表(List)2.3.4表（List）的定义中未实现的函数的实现与分析（1）析构函数:~List();template<classT>List<T>::~List(){Node<T>*next;while(first){next=first->next;deletefirst;first=next;}}

最坏情况时间复杂性7/29/2023512.3用指针实现ADT表(List8/8/2023

522.3用指针实现ADT表(List)2.3.4表（List）的定义中未实现的函数的实现与分析（续）（2）求表长:intLength()const;template<classT>intList<T>::Length()const{Node<T>*current=first;

intlen=0;while(current){len++;

current=current->next;}returnlen;}最坏情况时间复杂性7/29/2023522.3用指针实现ADT表(List8/8/2023

532.3用指针实现ADT表(List)2.3.4表（List）的定义中未实现的函数的实现与分析（续）（3）为元素x定位:intLocate(constT&x);template<classT>intList<T>::Locate(constT&x)const{Node<T>*current=first;

intindex=1; //indexofcurrentwhile(current&¤t->data!=x){

current=current->next;index++;}if(current)returnindex;return0;

}

最坏情况时间复杂性O（n）7/29/2023532.3用指针实现ADT表(List核心操作（关键操作）：工作指针后移。从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。firsta1pa2pan∧aipp检索成功p检索失败检索第k个元素给x:boolRetrieve(intk,T&x)const;firsta1pa2pan∧aipp检索成功p检索失败检索第1.工作指针current初始化;累加器index初始化;2.1工作指针current后移;2.2累加器index加1;2.循环直到current为空或current指向第i个结点3.若current为空，则第i个元素不存在，抛出查找位置异常；否则查找成功，返回结点current的数据元素；1.工作指针current初始化;累加器index初始化8/8/2023

562.3用指针实现ADT表(List)2.3.4ADT表（List）的定义中未实现的函数的实现与分析（续）（4）检索第k个元素给x:boolRetrieve(intk,T&x)const;template<classT>boolList<T>::Retrieve(intk,T&x)const{if(k<1)returnfalse;Node<T>*current=first;intindex=1;while(index<k&¤t){

current=current->next;index++;}if(current){x=current->data;returntrue;}returnfalse;

}

时间复杂性Current++能否完成指针后移？a1a27/29/2023562.3用指针实现ADT表(List8/8/2023

572.3用指针实现ADT表(List)2.3.4ADT表（List）的定义中未实现的函数的实现与分析（续）（5）在位置k后插入元素x:

List<T>&Insert(intk,constT&x);

函数的运算步骤是：先扫描链表找到插入位置p，然后建立一个存储待插入元素的新结点y，再将结点y插入到结点p之后。插入的示意图如下

yyy->next=first;firstfirst=y;py->next=p->next;p->next=y;7/29/2023572.3用指针实现ADT表(List1.工作指针p初始化；累加器j清零；2.查找第i-1个结点并使工作指针p指向该结点；3.若查找不成功，说明插入位置不合理，抛出插入位置异常；否则，3.1生成一个元素值为x的新结点s；3.2将新结点s插入到结点p之后；1.工作指针p初始化；累加器j清零；8/8/2023

592.3.4（5）（续）template<classT>List<T>&List<T>::Insert(intk,constT&x){if(k<0)throwOutOfBounds();Node<T>*p=first;//找插入位置for(intindex=1;index<k&&p;index++)p=p->next;if(k>0&&!p)throwOutOfBounds();

Node<T>*y=newNode<T>;y->data=x;if(k){//在位置p处插入

y->next=p->next; p->next=y;}else{//在表首插入需要特殊处理（若引入表头结点则可纳入一般情况）

y->next=first; first=y;}return*this;

}

时间复杂性O（k）7/29/2023592.3.4（5）（续）8/8/2023

602.3用指针实现ADT表(List)2.3.4ADT表（List）的定义中未实现的函数的实现与分析（续）（6）删除位置k处的元素给x:

List<T>&Delete(intk,T&x);

函数的运算步骤是：依次处理以下3种情况。（ⅰ）k<1或链表为空；（ⅱ）删除的是表首元素，即k=1；（ⅲ）删除的是非表首元素，即k>1。其删除的示意图如下p=q->next;q->next=p->next;deletep;7/29/2023602.3用指针实现ADT表(List8/8/2023

612.3.4（6）（续）template<classT>List<T>&List<T>::Delete(intk,T&x){if(k<1||!first)throwOutOfBounds();Node<T>*p=first;if(k==1)//删除表首元素需要特殊处理（若引入哨兵结点则可纳入一般情况）

first=first->next;else{//找表中第k-1个元素所在结点qNode<T>*q=first;for(intindex=1;index<k-1&&q;index++)q=q->next;if(!q||!q->next)throwOutOfBounds();p=q->next;//让p指向

第k个元素所在结点

q->next=p->next;}//删除结点px=p->data;//第k个元素存入x并释放结点pdeletep;return*this;}

时间复杂性O（k）？？？!q=>因为q为空而退出for循环=>index<k-1，即：表中不存在第k个元素；!q->next=>找到index=k-1的位置，但该位置已是表尾， 即：q->next=0。7/29/2023612.3.4（6）（续）？？？!q在链表中设置头结点在链表中设置头结点线性表的链接存储结构及实现单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表头指针：指向第一个结点的地址。尾标志：终端结点的指针域为空。线性表的链接存储结构及实现单链表020002080302.3线性表的链接存储结构及实现单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表空表和非空表不统一，缺点？如何将空表与非空表统一？2.3线性表的链接存储结构及实现单链表02000208头结点：在单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。2.3线性表的链接存储结构及实现单链表非空表firsta1a2an∧空表first∧头结点：在单链表的第以一个元素结点之前附设一个类型相同的结点头结点：在单链表的第一个结点之前人为地附设的一个结点。数据域La1a2an^…L^头指针

头结点头指针存放头结点的地址。头结点不存放任何数据存放附加信息（链表的结点个数等）。指针域存放第一个结点的地址（若线性表为空表，则“空”，用^表示。）头结点：在单链表的第一个结点之前人为地附设的一个结点。数据问题：在链表中设置头结点有什么好处？作用：可以对空表、非空表进行统一处理；可以对首元结点及其他结点统一处理。结论：编程更方便。问题：在链表中设置头结点有什么好处？作用：结论：编程更方8/8/2023

682.3用指针实现ADT表(List)2.3.4ADT表（List）的定义中未实现的函数的实现与分析（续）（7）输出所有元素:voidPrintList(ostream&out)const;template<classT>voidList<T>::PrintList(ostream&out)const{Node<T>*current;for(current=first;current;current=current->next)out<<current->data<<"";

}

时间复杂性O（n）7/29/2023682.3用指针实现ADT表(List8/8/2023

692.3用指针实现ADT表(List)2.3.6用指针实现ADT表（List）的优缺点优点：

避免了数组要求连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。(当元素的粒度很大时，移动元素是很费时的。)缺点：

需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间，为获得上述优点付出代价。7/29/2023692.3用指针实现ADT表(List补充#include<iostream.h>classNode{public:intdata;Node*next;};classList{private:Node*first;public:List(){first=0;}~List();boolEmpty()const{returnfirst==0;}intLength()const;boolRetrieve(intk,int&x)const;intLocate(constint&x)const;List&Insert(intk,constint&x);List&Delete(intk,int&x);voidPrintList()const;};先写这些代码，然后编译看是否有问题？能不能链接？补充#include<iostream.h>先写这些代码，然voidmain(){ Listl1;}如果想能运行，调用了什么函数？需加哪个函数的实现？voidmain()如果想能运行，调用了什么函数？需加哪个voidmain(){ Listl1; l1.Insert(0,3); l1.PrintList();}如果想能运行，又调用了什么函数？需加哪个函数的实现？voidmain()如果想能运行，又调用了什么函数？需加哪List&List::Insert(intk,constint&x){if(k<0){ cout<<"outbounds"; return*this; }Node*p=first;//找插入位置

for(intindex=1;index<k&&p;index++)p=p->next;if(k>0&&!p){ cout<<"outbounds"; return*this; }Node*y=newNode;y->data=x;if(k){//在位置p处插入

y->next=p->next; p->next=y;}else{//在表首插入需要特殊处理（若引入表头结点则可纳入一般情况）

y->next=first; first=y;}return*this;}voidList::PrintList()const{Node*current;for(current=first;current;current=current->next)cout<<current->data<<"";}List&List::Insert(intk,cons如何建立链表？使用构造函数?（1）从无到有创建；（2）利用原始数据直接建立非空链表；头插法建单链表尾插法建表看相关动画如何建立链表？数据结构第2章线性表链表部分课件数据结构第2章线性表链表部分课件

从单链表中某结点p出发如何找到其前驱？firsta1a2an∧

从单链表中某结点p出发如何找到其前驱？firsta1a2a8/8/2023

782.6用单循环链实现表

2.6.1用单循环链实现表的动因和构想动因：在用指针实现表时，表尾结点中的指针为空指针

NULL。人们希望把这个指针用起来，提高查找的效率。构想：引入哨兵结点，并将尾结点的空指针改为指向哨兵结点的指针，使整个链表形成一个环。然后，用指向最后结点的指针表征我们的ADT表，结构如下图。

(a)非空表(b)空表

7/29/2023782.6用单循环链实现表2.6.1firsta1ai-1anai如何查找开始结点和终端结点？开始结点：first->next终端结点：将单链表扫描一遍，时间为O(n)firsta1ai-1anai如何查找开始结点和终端结点？开照此，找最后元素只需O(1),找首元素仍只需O(1)。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。

一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方在循环链表上实现各种运算与链表的情形类似，不同之处：循环终止条件不是p或p->next是否为空，而是判断是否指向表首；在循环链表上实现各种运算与链表的情形类似，不同之处：8/8/2023

822.6用单循环链实现表2.6.2用单循环链实现的表的特征数据及其类型表的元素的类型：同指针实现的类T。表的结点类型：同指针实现的类Node<T>。用单循环链实现的表本身需要的数据

intn;//表的长度

Node<T>*last;//指向表尾的指针7/29/2023822.6用单循环链实现表2.6.28/8/2023

832.6.3单循环链表List的模板类的定义template<classT>classIterator;template<classT>classList{friendclassIterator<T>;private:

intn;//表的长度

Node<T>*last;//指向表尾的指针

public:List();~List();boolEmpty()const{returnn==0;}intLength()const{returnn;}boolRetrieve(intk,T&x)const;intLocate(constT&x)const;List<T>&Insert(intk,constT&x);List<T>&Delete(intk,T&x);voidPrintList(ostream&out)const;};区别于单链表中无表长的定义！7/29/2023832.6.3单循环链表List的8/8/2023

842.6用单循环链实现表2.6.4ADT表（List）的定义中未实现的函数的实现与分析（1）构造函数List();//初始化一个空表template<classT>List<T>::List(){Node<T>*y=newNode<T>;

y->next=y;last=y;//表中只有一个哨兵结点

n=0;}

//时间复杂性为O（1）7/29/2023842.6用单循环链实现表2.6.48/8/2023

852.6用单循环链实现表2.6.4表的定义中未实现的函数的实现与分析（2）析构函数:~List();template<classT>List<T>::~List(){Node<T>*next;while(!Empty()){ //非空表的释放

next=last->next;deletelast;

n--;last=next;}

deletelast;

//空表的释放

}

//时间复杂性为O（n）7/29/2023852.6用单循环链实现表2.6.48/8/2023

862.6.4表的定义中未实现的函数的实现与分析（续）（3）为元素x定位:intLocate(constT&x);template<classT>intList<T>::Locate(constT&x)const{Node<T>*current=last->next->next;intindex=1;

last->next->data=x;//技巧

while(current->data!=x){//找元素x所在的结点

current=current->next;index++;}return((current==last->next)?0:index);

}

//最坏情况时间复杂度为O（n）7/29/2023862.6.4表的定义中未实现的函数8/8/2023

872.6.4表的定义中未实现的函数的实现与分析（续）（4）检索第k个元素给x:boolRetrieve(intk,T&x)const;template<classT>boolList<T>::Retrieve(intk,T&x)const{if(k<1||k>n)returnfalse;//k值越界

Node<T>*current=last->next->next;//工作指针的初始化

intindex=1;//元素序号初始化

while(index<k){//找第k个元素所在的结点

current=current->next;index++;}x=current->data;returntrue;

}

//时间复杂性为O（k）7/29/2023872.6.4表的定义中未实现的函数8/8/2023

882.6用单循环链实现表2.6.4表的定义中未实现的函数的实现与分析（续）（5）在位置k后插入元素x:

List<T>&Insert(intk,constT&x);template<classT>List<T>&List<T>::Insert(intk,constT&x){if(k<0||k>n)throwOutOfBounds();//k值越界

Node<T>*p=last->next;//借助p搜索第k个元素

for(intindex=1;index<=k;index++)p=p->next;Node<T>*y=newNode<T>;//申请新结点，之后插入表中

y->data=x;

y->next=p->next;p->next=y;if(k==n)last=y;n++;//表长增1return*this;

}//时间复杂性为O（k）7/29/2023882.6用单循环链实现表2.6.48/8/2023

892.6用单循环链实现表2.6.4表的定义中未实现的函数的实现与分析（续）（6）删除位置k处的元素给x:

List<T>&Delete(intk,T&x);template<classT>List<T>&List<T>::Delete(intk,T&x){if(k<1||k>n)throwOutOfBounds();//k值越界

Node<T>*q=last->next;//借助q搜索第k-1个元素

for(intindex=1;index<＝

k-1;index++)

q=q->next;Node<T>*p=q->next;//q和p分别指向第k－1和k个元素所在的结点

q->next=p->next;//表中的第k个元素被删除

if(k==n)last=q;//如果k=n，则第k－1元素所在的结点成为新表尾结点

x=p->data;//将原表的第k个元素赋予xdeletep;

n--;return*this;

}

//时间复杂度为O（k）7/29/2023892.6用单循环链实现表2.6.48/8/2023

902.6用单循环链实现表2.6.4表的定义中未实现的函数的实现与分析（续）（7）输出表中所有元素:voidPrintList(ostream&out)const;template<classT>voidList<T>::PrintList(ostream&out)const{Node<T>*current;for(current=last->next->next;current!=last->next;

current=current->next)//从第1个元素开始逐个输出

out<<current->data<<"";

}

//时间复杂度为O（n）7/29/2023902.6用单循环链实现表2.6.48/8/2023

912.6用单循环链实现表2.6.5与单链表相比，用单循环链实现表的优点：可在O(1)的时间里找到表首元素和表尾元素。7/29/2023912.6用单循环链实现表2.6.5用双链实现表如何求结点p的直接前驱，时间性能？firsta1ai-1anai为什么可以快速求得结点p的后继？如何快速求得结点p的前驱？用双链实现表如何求结点p的直接前驱，时间性能？firsta18/8/2023

932.7用双链实现表

2.7.1用双链实现表的动因和构想动因：无论在用指针实现表还是在用单循环链实现表时，对于表中任一元素x,都不可能在O（1）时间里找到它的前驱。为了能在O（1）时间里既能找到前驱又能找到后继，提出了双链表。构想：在用指针实现表的每一个结点中增加一个指向前驱的指针。结构如下图7/29/2023932.7用双链实现表2.7.18/8/2023

942.7用双链实现表2.7.2用双链实现的表的特征数据及其类型表的元素的类型：同指针实现的类T表的结点类型：DNode<T>

template<classT>classDouble;template<classT>classDNode{friendclassDouble<T>;private:Tdata;DNode<T>*left,*right;}用双链实现的表本身需要的数据

intn;//表的长度

DNode<T>*LeftEnd,*RightEnd;//指向表的首、尾指针7/29/2023942.7用双链实现表2.7.2用8/8/2023

952.7.3双链表List的模板类的定义。

template<classT>classDouble{public:Double(){LeftEnd=RightEnd=0;};~Double();boolEmpty()const{returnn==0;}intLength()const{returnn;}boolRetrieve(intk,T&x)const;intLocate(constT&x)const;Double<T>&Insert(intk,constT&x);Double<T>&Delete(intk,T&x);voidPrintList(ostream&out)const;private:intn;DNode<T>*LeftEnd,*RightEnd;};7/29/2023952.7.3双链表List的模板类8/8/2023

962.8用双循环链实现表2.8.1用双循环链实现表的动因和构想动因：从双链到双循环链类似于从单链到单循环链。构想：引入哨兵结点，并将双链表的首、尾结点的空指针改为指向哨兵结点的指针，而哨兵结点的左、右指针分别指向尾元素、首元素所在的结点，使整个链表形成一个双链环。然后，用指向哨兵结点的指针表征我们的ADT表。结构如下图。7/29/2023962.8用双循环链实现表2.8.18/8/2023

972.8用双循环链实现表2.8.2用双循环链实现的表的特征数据及其类型表的元素的类型：同指针实现的类T。表的结点类型：同双链表的类DNode<T>用双循环链实现的表本身需要的数据

intn;//表的长度

DNode<T>*header;//指向表的哨兵结点的指针7/29/2023972.8用双循环链实现表2.8.28/8/2023

982.8.3双循环链表List的模板类的定义。template<classT>classDouble{public:Double();~Double();boolEmpty()const{returnn==0;}intLength()const{returnn;}boolRetrieve(intk,T&x)const;intLocate(constT&x)const;Double<T>&Insert(intk,constT&x);Double<T>&Delete(intk,T&x);voidPrintList(ostream&out)const;private:intn;DNode<T>*header;};

7/29/2023982.8.3双循环链表List的模8/8/2023

992.8用双循环链实现表2.8.4表的定义中未实现的函数的实现与分析（1）构造函数:List()template<classT>Double<T>::Double(){DNode<T>*y=newDNode<T>;y->left=y;y->right=y;header=y;n=0;}//时间复杂度为O（1）

7/29/2023992.8用双循环链实现表2.8.48/8/2023

1002.8.4表的定义中未实现的函数的实现与分析（2）析构函数:~List();template<classT>Double<T>::~Double(){DNode<T>*current;DNode<T>*next;current=header->right;while(!Empty()){//从第一个元素开始逐个地释放

next=current->right;deletecurrent;n--;current=next;}deleteheader;//最后释放哨兵结点

}

//时间复杂度为O（n）

7/29/20231002.8.4表的定义中未实现的8/8/2023

1012.8用双循环链实现表2.8.4表的定义中未实现的函数的实现与分析（3）检索第k个元素给x:boolRetrieve(intk,T&x)const;template<classT>boolDouble<T>::Retrieve(intk,T&x)const{if(k<1||k>n)returnfalse;//k值越界

DNode<T>*current=header->right;intindex=1;while(index<k){//找表中第k个元素

current=current->right;index++;}x=current->data;//找到表中第k个元素赋予xreturntrue;

}//时间复杂度为O（k）7/29/20231012.8用双循环链实现表2.8.8/8/2023

1022.8用双循环链实现表2.8.4表的定义中未实现的函数的实现与分析（4）为元素x定位:intLocate(constT&x);template<classT>intDouble<T>::Locate(constT&x)const{DNode<T>*current=header->right;intindex=1;header->data=x;//技巧：将x放入哨兵结点

while(current->data!=x){//找元素x所在的结点

current=current->right;index++;}return((current==header)?0:index);

}

//最坏情况时间复杂度为O（n）7/29/20231022.8用双循环链实现表2.8.8/8/2023

1032.8.4表的定义中未实现的函数的实现与分析（5）在位置k后插入元素x:

List<T>&Insert(intk,constT&x);template<classT>Double<T>&Doub