数据结构-从概念到C++实现（第4版）课件 第二章 线性表

2-1引言v第二章线性表学籍管理问题学号姓名性别出生日期籍贯15041001王军男吉林省图们市15041002李明男吉林省吉林市15041003汤晓影女吉林省长春市………200201022003032820031116……抽象学籍管理问题，数据元素是什么？元素之间的关系？完成什么功能？二维表线性结构Page01工资管理问题工资管理问题，数据元素是什么？元素之间的关系？完成什么功能？职工号000826000235000973…姓名王一梅李明郑浩…性别女男男…基本工资348038602850…岗位津贴190024001600…业绩津贴138016001050…抽象所有二维表抽象的数据模型都是线性结构吗？研究如何存储线性结构，并实现增、删、改、查等基本操作。二维表线性结构约瑟夫环问题【问题】约瑟夫环问题由古罗马史学家约瑟夫（Josephus）提出，他参加并记录了公元66—70年犹太人反抗罗马的起义。在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。这些起义者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。【想法——数据模型】设

n(n>0)个人围成一个环，n个人的编号分别为1，2，…，n，从第1个人开始报数，报到

m时停止报数，报

m的人出环，再从他的下一个人起重新报数，报到

m时停止报数，报m的人出环，……，如此下去，直到所有人全部出环为止。对于任意给定

n和

m，求

n个人出环的次序。如何存储这种环状线性结构，并求解约瑟夫环的出环次序呢？12354出环的顺序是：31524例如，n=5,m=3，则约瑟夫环问题随处可见的线性结构关于线性结构什么是线性结构？在逻辑上有什么特点？如何存储线性结构？在不同的存储结构上，如何实现插入、删除、查找等基本操作？在不同的存储结构上，基本操作的时空性能如何？2-2线性表的逻辑结构v第二章线性表线性表的定义线性表的逻辑特征线性表的抽象数据类型定义学什么？2-2-1线性表的定义v第二章线性表线性表的定义线性表（表）：n（n≥0）个具有相同类型的数据元素的有限序列（a1,a2,…,ai,…,an）线性表的长度：线性表中数据元素的个数空表：长度等于零的线性表ai（1≤i≤n）称为数据元素下角标

i表示该元素在线性表中的位置或序号线性表的逻辑特征1.数据元素个数的有限性a1ai-1aiana22.数据元素类型的相同性3.数据元素类型的抽象性4.相邻数据元素的序偶性，且a1无前驱，an无后继序偶：两个具有固定次序的元素组成的序列，记作(a，b)，且称a是b

的前驱，b是a

的后继L1=(1,3,5,7,9)L2=('a','e','i','o','u')L3=((Li,8,3),(Wang,7,4),(Zhang,5,5))不确定、任意2-2-2线性表的抽象数据类型定义v第二章线性表线性表的抽象数据类型定义ADTListDataModelOperationendADT线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系InitList：表的初始化，建一个空表CreateList：建立具有n个元素的线性表DestroyList：销毁表，释放表所占用的存储空间Length：求表的长度Get：在表中取序号为i

的数据元素Locate：在线性表中查找值等于x

的元素Insert：在表的第i

个位置处插入一个新元素xDelete：删除表中的第i

个元素Empty：判断表是否为空InitList

输入：无功能：表的初始化，建一个空表输出：无CreateList

输入：n个数据元素

功能：建立一个线性表

输出：具有n个元素的线性表DestroyList输入：无功能：销毁表，释放表所占用的存储空间输出：无Locate输入：数据元素x

功能：在线性表中查找值等于x

的元素输出：查找成功返回x

在表中的序号，否则返回0线性表的抽象数据类型定义（a1,a2,…,ai,…,an）Get输入：元素的序号i

功能：在表中取序号为i

的数据元素输出：若i合法，返回序号为i的元素值Length

输入：无功能：求表的长度输出：表中数据元素的个数Insert输入：插入位置i，待插x功能：在表的第i

个位置处插入一个新元素x输出：若插入成功，表中增加一个新元素；否则给出失败信息Delete

输入：删除位置i功能：删除表中的第i

个元素输出：若删除成功，表中减少一个元素；否则给出失败信息Empty输入：无功能：判断表是否为空输出：若是空表，返回1，否则返回0线性表的抽象数据类型定义（a1,a2,…,ai,…,an）（1）线性表的基本操作根据实际应用而定（2）复杂的操作可以通过基本操作的组合来实现（3）对不同的应用，操作的接口可能不同2-3线性表的顺序存储结构及实现v第二章线性表顺序表的存储结构顺序表的实现学什么？顺序表的类定义、构造函数、析构函数顺序表的判空、取长度操作：Empty、Length顺序表的查找操作：Get、Locate顺序表的插入、删除操作：Insert、Delete2-3-1顺序表的存储结构v第二章线性表顺序表的存储方法顺序表（向量）：线性表的顺序存储结构某些内存单元可能是空吗？例：（34,23,67,43）342367434存储要点用一段地址连续的存储单元依次存储线性表中的数据元素用什么属性来描述顺序表？342367434存储空间的起始位置顺序表的容量（最大长度）顺序表的当前长度例：（34,23,67,43）Page03顺序表的存储方法顺序表（向量）：线性表的顺序存储结构0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

长度数组的长度MaxSize线性表的长度lengthMaxSize≥length（a1,

…,ai-1

,ai,…,an）Page04顺序表的存储方法顺序表（向量）：线性表的顺序存储结构存取访问0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

长度（a1,

…,ai-1

,ai,…,an）如何求得任意元素的存储地址？cLoc(ai)Loc(a1)Loc(ai)=Loc(a1)+(i-1)×cPage07存取时间是O(1)随机存取2-3-2顺序表的实现v第二章线性表顺序表的实现——类定义InitList：表的初始化，建一个空表CreateList：建立具有n个元素的线性表DestroyList：销毁表，释放表所占用的存储空间Length：求表的长度Get：在表中取序号为i

的数据元素Locate：在线性表中查找值等于x

的元素Insert：在表的第i

个位置处插入一个新元素xDelete：删除表中的第i

个元素Empty：判断表是否为空线性表的抽象数据类型定义？constint

MaxSize=100;template<typename

DataType>classSeqList{public:

SeqList();

SeqList(DataTypea[],intn);

~SeqList();

intLength();

DataTypeGet(int

i);

intLocate(DataTypex);

voidInsert(int

i,DataTypex);

DtaTypeDelete(int

i);intEmpty();

intEmpty();

voidPrintList();private:

DataTypedata[MaxSize];

intlength;};顺序表的实现——初始化初始化顺序表的函数原型是什么？InitList

输入：无功能：表的初始化，建一个空表输出：无0…MaxSize-1

0SeqList<DataType>::SeqList(){Length=0;}SeqList<DataType>::SeqList(DataTypea[],intn){

}顺序表L

数组a35122433425if(n>MaxSize)throw“参数非法”;顺序表的实现——建立for(inti=0;i<n;i++)data[i]=a[i];length=n;3512243342顺序表的实现——判空intSeqList<DataType>::Empty(){if(length==0)return1;elsereturn0;}0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

nintSeqList<DataType>::Length(){returnlength;}求顺序表的长度？顺序表的实现——按位查找template<typenameDataType>DataTypeSeqList<DataType>::Get(inti){

if(i<1&&i>length)throw"查找位置非法";elsereturndata[i-1];}按位查找的时间复杂度？0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

lengthO(1)随机存取template<typenameDataType>intSeqList<DataType>::Locate(DataTypex){for(inti=0;i<length;i++)if(data[i]==x)returni+1;//返回其序号i+1return0;//退出循环，说明查找失败}0…i…n-1MaxSize-1a1…x…an

length按值查找的时间复杂度？O(n)顺序表的实现——按值查找顺序表的实现——插入33例1

对于线性表（35，12，24，42），在i=2的位置上插入元素33435122442a1a2a3a4012345什么情况下插入无法进行？注意边界条件表满：length>=MaxSize合理的插入位置：1≤i≤length+1（注意：i

指的是元素的序号）template<typenameDataType>voidSeqList<DataType>::Insert(inti,DataTypex){if(length==MaxSize)throw"上溢";

if(i<1||i>length+1)throw"插入位置错误";for(intj=length;j>=i;j--)data[j]=data[j-1];//第j个元素存在数组下标为j-1处data[i-1]=x;length++;}基本语句？执行多少次？顺序表的实现——插入

for(intj=length;j>=i;j--)data[j]=data[j-1];最好情况（i=n+1）：执行0次，时间复杂度为O(1)最坏情况（i=1）：执行n+1次，时间复杂度为O(n)平均情况（1≤i≤n+1）：时间复杂度为O(n)顺序表的实现——插入基本语句？执行多少次？例2

对于线性表（35,33,12,24,42），删除位置i=2的数据元素535a1a2a3a401234422412334a5

x请仿照顺序表的插入算法，完成删除算法：1.分析边界条件2.分别给出伪代码和C++语言实现3.分析时间复杂度顺序表的实现——删除2-4线性表的链式存储结构及实现v第二章线性表单链表的引入静态存储分配顺序表事先确定容量单链表动态存储分配运行时分配空间连续不连续零散分布单链表：线性表的链接存储结构存储思想：用一组任意的存储单元存放线性表单链表的存储结构单链表的实现学什么？双链表循环链表2-4-1单链表的存储结构v第二章线性表0200020803000325…………a1a2a3a4例：(a1,a2,a3,a4)的存储示意图0200

03250300∧存储特点：逻辑次序和物理次序不一定相同2.元素之间的逻辑关系用指针表示单链表的存储方法观察1：单链表由若干结点构成观察2：单链表的结点只有一个指针域datanext单链表的结点结构数据域data：存储数据元素指针域next：存储指向后继结点的地址0200020803000325…………a1a2a3a40200

03250300∧头指针：指向第一个结点的存储地址尾标志：终端结点的指针域为空firsta1a2an∧非空表first=NULL空表空表和非空表不统一，有什么缺点？first单链表的存储方法头结点：在第一个元素结点之前附设一个类型相同的结点firsta1a2an∧first∧非空表空表头结点简化了对边界的处理——插入、删除、构造等头指针：指向第一个结点的存储地址尾标志：终端结点的指针域为空单链表的存储方法structNode{data;structNode*next;}Node;template<typenameDataType>DataType单链表的结点结构定义firsta1a2an∧指针的相关问题如何引用结点p的数据域（指针域）？firsta1a2an∧p该结点用*p来表示，*p为结点变量。将“指针p所指结点”简称为“结点p”p->data*p.datap->next*p.next*p*(p->next)如何表示结点p的下一个结点？设指针p指向某个Node类型的结点2-4-2单链表的实现v第二章线性表单链表的类定义template<typenameDataType>classLinkedList{public:

LinkedList();//无参构造函数，建立只有头结点的空链表LinkedList(DataTypea[],intn);//有参构造函数，建立有n个元素的单链表~LinkedList();//析构函数intLength();//求单链表的长度DataTypeGet(inti);//按位查找。查找第i个结点的元素值intLocate(DataTypex);//按值查找。查找值为x的元素序号voidInsert(inti,DataTypex);//插入操作，第i个位置插入值为x的结点DataTypeDelete(inti);//删除操作，删除第i个结点intEmpty();//判断线性表是否为空voidPrintList();//遍历操作，按序号依次输出各元素private:Node<DataType>*first;//单链表的头指针};单链表的实现——初始化∧first初始化一个单链表要完成哪些工作呢？template<typenameDataType>LinkedList<DataType>::LinkedList(){

first=newNode<DataType>;

first->next=nullptr;}空单链表满足什么条件呢？template<typenameDataType>int

LinkedList<DataType>::Empty(

){if(first->next==nullptr)return1elsereturn0;}单链表的实现——遍历firsta1a2an∧pp核心操作：工作指针后移如何实现工作指针后移？p++能正确实现后移吗？a1a2pp++p->nextp=p->nextfirsta1a2an∧first为什么设置工作指针？通过头指针后移扫描单链表会有什么后果？first修改前：(a1,a2,…,an)first修改后：(a2,…,an)单链表头指针的作用是标识单链表的开始，通常不修改头指针first指向头结点单链表的实现——遍历firsta1a2an∧输入：无功能：遍历单链表PrintList输出：单链表的各个数据元素1.工作指针p初始化;2.重复执行下述操作，直到指针p为空：

2.1输出结点p的数据域;2.2工作指针p后移;如何描述遍历的基本过程？伪代码——梳理思路的好工具！p单链表的实现——遍历template<typenameDataType>voidLinkedList<DataType>::PrintList(){Node<DataType>*p=first->next;//工作指针p初始化while(p!=nullptr){cout<<p->data<<"\t";

p=p->next;//工作指针p后移，注意不能写作p++}cout<<endl;}firsta1a2an∧p单链表的实现——遍历单链表算法的设计模式

访问结点p进行的操作

退出循环的操作firsta1a2an∧p单链表算法的设计模式：通过工作指针的反复后移扫描链表p=first->next;//或p=first;，工作指针p初始化while(p!=nullptr)//或p->next!=nullptr，扫描单链表{}p=p->next;//工作指针后移单链表的实现——长度pintLinkedList<DataType>::Length(){

returncount;}first∧注意count的初值和返回值之间的关系Node*p=first->next;while(p!=nullptr){p=p->next;}intcount=0;count++;firsta1a2an∧pcount=1pcount=2pcount=n单链表的实现——按位查找firsta1aian∧pcount=1pcount=ipi>nDataTypeLinkedList<DataType>::Get(inti){

Node<DataType>*p=first->next;//工作指针p初始化intcount=1;//累加器count初始化

while(p!=nullptr&&count<i){p=p->next;//工作指针p后移count++;}if(p==nullptr)throw"查找位置错误";elsereturnp->data;}firsta1xan∧pppintLinkedList<DataType>::Locate(DataTypex){

Node<DataType>*p=first->next;//工作指针p初始化intcount=1;//累加器count初始化

while(p!=nullptr){if(p->data==x)returncount;//查找成功，结束函数并返回序号p=p->next;count++;}return0;//退出循环表明查找失败}单链表的实现——按值查找单链表的实现——插入pxs如何实现结点ai-1、x和ai之间逻辑关系的变化？s=newNode;s->data=x;firsta1ai-1an∧ai算法描述：s->next=p->next;p->next=s;pxsfirsta1ai-1an∧ai注意分析边界情况——表头、表尾？pxspxs∧单链表没有特殊说明，都带头结点s->next=p->next;p->next=s;单链表的实现——插入如果不带头结点，会怎么样呢？pxsfirsta1ai-1anais->next=first;first=s;xspxss->next=p->next;p->next=s;操作不一致会导致算法增加处理步骤，而且容易出错∧单链表的实现——插入算法：Insert输入：单链表的头指针first，插入位置i，待插值x输出：如果插入成功，返回新的单链表，否则返回插入失败信息1.工作指针p初始化为指向头结点；2.查找第i-1个结点并使工作指针p指向该结点；

3.若查找不成功，说明插入位置不合理，返回插入失败信息；否则，生成元素值为x的新结点s，将结点s插入到结点p之后；pxsfirsta1ai-1an∧aipxspxs∧单链表的实现——插入voidLinkedList<DataType>::Insert(inti,DataTypex){Node<DataType>*p=first,*s=nullptr;//工作指针p初始化intcount=0;while(p!=nullptr&&count<i-1)//查找第i–1个结点{p=p->next;//工作指针p后移count++;}

if(p==nullptr)throw"插入位置错误";//没有找到第i-1个结点else{

s=newNode<DataType>;s->data=x;//申请结点s，数据域为xs->next=p->next;p->next=s;//将结点s插入到结点p之后}}时间复杂度？O(n)O(1)已知指针p单链表的实现——插入单链表的实现——建立操作接口：Node*LinkedList(DataTypea[],intn)数组a3512243342头插法：插在头结点的后面first=newNode;first->next=nullptr;初始化first∧s=newNode;s->data=a[0];s->next=first->next;first->next=s;插入第一个元素结点35s∧操作接口：Node*LinkedList(DataTypea[],intn)数组a3512243342头插法：插在头结点的后面依次插入每一个结点12sfirst35∧单链表的元素顺序有什么特点？s=newNode;s->data=a[i];s->next=first->next;first->next=s;单链表的实现——建立template<typenameDataType>LinkedList<DataType>::LinkedList(DataTypea[],intn){

first=newNode<DataType>;first->next=nullptr;//初始化一个空链表for(inti=0;i<n;i++){Node<DataType>*s=nullptr;s=newNode<DataType>;

s->data=a[i];

s->next=first->next;first->next=s;//将结点s插入到头结点之后}}单链表的实现——建立操作接口：Node*LinkedList(DataTypea[],intn)数组a3512243342尾插法：插在尾结点的后面初始化firstrearfirst=newNode;rear=first;为方便在尾结点后面插入结点，设指针rear指向尾结点单链表的实现——建立操作接口：Node*LinkedList(DataTypea[],intn)尾插法：插在尾结点的后面依次插入每一个结点first

35rear

12ss=newNode;s->data=a[i];rear->next=s;rear=s;∧first

35

42srear数组a3512243342单链表的元素顺序有什么特点？单链表的实现——建立template<typenameDataType>LinkedList<DataType>::LinkedList(DataTypea[],intn){first=newNode<DataType>;//生成头结点Node<DataType>*r=first,*s=nullptr;//尾指针初始化for(inti=0;i<n;i++){s=newNode<DataType>;

s->data=a[i];

r->next=s;r=s;//将结点s插入到终端结点之后}

r->next=nullptr;//单链表建立完毕，将终端结点的指针域置空}单链表的实现——建立循环不变式外提！p如何实现结点ai-1、ai和ai+1

之间逻辑关系的变化？firsta1ai-1an∧aiai+1qq=p->next;x=q->data;p->next=q->next;deleteq;pq注意分析边界情况——删除表头和表尾！

pq表尾的特殊情况：虽然被删结点不存在，但其前驱结点却存在！算法描述：单链表的实现——删除pfirsta1ai-1an∧aiai+1qpqpq算法：Delete输入：单链表的头指针first，删除的位置i输出：如果删除成功，返回被删除的元素值，否则返回删除失败信息1.工作指针p初始化；累加器count初始化；2.查找第i-1个结点并使工作指针p指向该结点；3.若p不存在或p的后继结点不存在，则出现删除位置错误，删除失败；否则，3.1存储被删结点和被删元素值；3.2摘链，将结点p的后继结点从链表上摘下；3.3释放被删结点；单链表的实现——删除DataTypeLinkedList<DataType>::Delete(inti){DataTypex;intcount=0;Node<DataType>*p=first,*q=nullptr;//工作指针p指向头结点while(p!=nullptr&&count<i-1)//查找第i-1个结点{p=p->next;count++;}if(p==nullptr||p->next==nullptr)throw"删除位置错误";else{q=p->next;x=q->data;//暂存被删结点p->next=q->next;//摘链deleteq;returnx;}}单链表的实现——删除将p!=nullptr修改为p->next!=nullptr是否可以？template<typenameDataType>LinkedList<DataType>::~LinkedList(){Node<DataType>*p=first;while(first!=nullptr)//释放单链表的每一个结点的存储空间{

first=first->next;//first指向被释放结点的下一个结点deletep;p=first;//工作指针p后移}}单链表的实现——析构函数单链表需要释放哪些存储空间？为什么？2-4-3双链表v