数据结构课件

1引言数据结构的概念及其研究的问题，是本章中重要的概念，它们贯穿整本书。除了数据结构研究的三个方面，我们对每种数据结构都会给出应用的实例。要学会描述数据结构和算法，分析算法的时、空复杂度。第1章基础知识

数据结构DATASTRUCTURE21.1算法和数据结构瑞士的Wirth博士图灵奖获得者提出：程序＝算法+数据结构31.1算法和数据结构课堂提要第1章基础知识1.1算法和数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法

数据结构和算法是计算机学科的基础之一，更是软件技术的基础。

算法设计通常建立在所处理的数据之上的，精心选择的数据结构可以带来更高效率的算法。程序＝算法+数据结构4精心设计的数据结构真的可以带来更高效率的算法吗？5

图一6，

图二7

数据在计算机中的表示和存储不能是无组织的，是有规律，有结构的。

81.数据：计算机加工处理的对象

2.数据元素：是组成数据的基本单位，在计算机程序中通常作为一个整体来处理。数据元素由若干数据项组成。3.数据项是不可再分割的。1.2什么是数据结构

1.2.1基本概念9表1.1学生情况表学号姓名性别其他信息B02040101王小红女…B02040102林悦女…B02040103陈菁女…B02040104张可可男……………数据项10数据结构的由来

数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究的基本课题之一。

11什么是数据结构定义1----

数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。定义2----按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。12

数据结构包括三个方面逻辑结构：数据元素间的逻辑关系；存储结构：数据在计算机内的表示形式；运算：在数据上执行的操作。13数据结构举例表1.1学生情况表学号姓名性别其他信息B02040101王小红女…B02040102林悦女…B02040103陈菁女…B02040104张可可男……………逻辑结构，存储结构，运算141.2.2数据的逻辑结构

数据结构的逻辑结构可以用一个二元组表示。即DS=（D，R）其中，D是数据元素的有限集合，R是D中数据元素序偶的集合。例如DS={D,R},D={a,b,c,d},R={<a,b>,<b,c>,<c,d>},

其中，序偶<a,b>表示a和b之间的关系，我们称为a是b的直接前驱，b是a的直接后继。小圆圈代表数据元素，两个不同元素的序偶称为边。abcd154种基本的逻辑结构

(a)集合结构(b)线性结构(c)树形结构(d)图结构图1-2四种基本的结构关系对数据元素间逻辑关系的描述称为数据的逻辑结构。根据数据结构中数据元素之间关系的不同特征，可以划分为以下四种基本逻辑结构：16

线性结构：数据元素之间存在一对一的关系。一个前驱，一个后继。树形结构：数据元素之间存在一对多的关系。图结构：数据元素之间存在多对多的关系。每个结点的前驱和后继的数目都不同。集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，没有其它关系。四种逻辑结构也可以分成两类：线性结构和非线性结构。(a)集合结构(b)线性结构(c)树形结构(d)图结构图1-2四种基本的结构关系17

几种存储结构

顺序结构链接结构索引结构散列结构

地址信息称为链。∧表示空链。1.2.3数据的存储表示存储结构:数据结构的实现形式，是数据结构在计算机内的表示，即数据元素及其关系在计算机存储器中的存储方式。其中，顺序和链接是两种最基本的存储表示方法。18

顺序存储顺序（或称连续）表示方法需要一块连续的存储空间，并把逻辑上相关的数据元素一次存储在该连续的存储区中。

例如，由4个元素组成的线性数据结构（a0,a1,a2,a3），存储在某个连续的存储区内，设存储区的起始地址是102，假定每个元素占2个存储单元。Loc(ak)=102+2×k19

链式存储

例如，线性结构（a0,a1,a2,a3

）的链接存储表示。

结点存储块分成两部分，元素本身和该元素后继元素所在结点的存储地址。

DataLink链接存储表示下，为在机内存储一个元素，除了需要存放该元素本身的信息外，还需要存放于该元素相关的其它元素的地址信息。这两部分信息组成一个数据元素的结点。20逻辑结构存储结构概念数据元素之间逻辑关系的描述数据及其关系在计算机内的组织方式面向面向应用问题面向计算机关系存储结构是逻辑结构在计算机内的映像

小结211.2.4数据结构的运算数据结构最常见的运算创建运算:创建一个数据结构；

清除运算:删除数据结构中的全部元素；插入运算:在数据结构的指定位置上插入一个新元素；删除运算:将数据结构中的某个元素删除；……22

静态数据结构和动态数据结构

如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。23

小结

数据结构是一门研究程序设计问题中计算机的操作对象（数据）以及它们之间的关系和运算的学科。241.3数据抽象和抽象数据类型

抽象，封装和信息隐蔽是控制软件开发复杂度，提高软件可靠性的重要手段．

本书采用抽象数据类型的观点讨论数据结构。课堂提要第1章基础知识1.1算法和数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法251.C语言的数据类型(1)基本类型：字符、整型……

(2)构造类型：数组、结构和联合(3)指针类型：指针例如，inta;变量a的取值范围是：-32768

32767对变量a执行的操作有：算术运算+、-、*、/、%

关系运算<、>、<=、>=、==、!=2.数据类型一个数据类型定义了一个值的集合以及作用于该值集的操作的集合。即一组值和一组操作。1.3.3数据类型和抽象数据类型

26抽象数据类型（AbstractDataType,ADT）是一个数据类型，其主要特征是该类型的对象及其操作的规范,与该类型对象的表示和操作的实现分离，实行封装和信息隐蔽，即使用和实现分离。使用和实现分离：使用者通过规范使用该类型的数据，而不必考虑其实现细节；改变实现将不影响使用。例如，C++中的整型int就是抽象数据类型。它的实现是隐蔽的，使用者只能通过整型上定义的一组运算对整型变量执行操作。3.抽象数据类型27规范指明“做什么”，实现解决“怎样做”。规范是实现的准则和依据28一个数据结构包含两个层次：(1)数据结构的规范（抽象层）：逻辑结构和运算的定义组成了数据结构的规范(2)数据结构的实现（实现层）：

存储结构和运算算法实现构成了数据结构的实现1.3.4数据结构和抽象数据类型

一种数据结构被视为一个抽象数据类型。291.4描述数据结构和算法30本书是怎样描述每种数据结构？1.4描述数据结构和算法

首先描述数据结构的规范（逻辑结构和运算的定义）然后介绍数据结构的实现（存储结构和运算的具体程序实现），31

（1）用格式化的自然语言来描述数据结构的规范。（2）用一个C++的抽象模板类描述数据结构的规范。1.4.1数据结构的规范1.4描述数据结构和算法对数据结构的规范的描述：32数据结构描述举例---堆栈1.4.1数据结构的规范33ADT1.1栈抽象数据类型ADTStack{Data:

(描述逻辑结构)0个或多个元素的线性序列（a0，a1，

，an-1)，遵循LIFO原则。

Operations:

(描述运算的定义)Create()：创建一个空栈。

Destroy():撤消一个栈。

Push(x)：元素x插入栈顶。

Pop()：删除栈顶元素。

Top(x)：在x中返回栈顶元素。}

（1）用ADT描述数据结构——堆栈的例子对堆栈的规范的描述：34程序1.1栈的C++模板抽象类template<classT>classStack{public:

virtualvoidPush(Tx)=0;

virtualvoidPop()=0;virtualTTop(T&x)const=0;

…};

除了构造函数，其余成员函数都是纯虚函数。顺序栈类SeqStack是类Stack在顺序存储表示下的一种实现，它是从抽象类Stack派生出来的，它可以实例化。（2）用C++模板抽象类描述数据结构35template<classT>boolSeqStack<T>::Push(T&x){if(IsFull()){cout<<"Overflow"<<endl;returnfalse;}s[++top]=x;returntrue;}1.4.２实现数据结构堆栈的实现：361.5算法分析的基本方法内容提要

算法及其性能分析算法的空间复杂度算法的时间复杂度渐近时间复杂度课堂提要第1章基础知识1.1算法和数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型

1.4描述数据结构和算法1.5算法分析的基本方法371.什么是算法

一个算法(algorithm)是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征：

(1)输入算法有零个或多个输入。

(2)输出算法至少产生一个输出

(3)确定性算法的每一条指令都有确切的定义，没有二义性。

(4)能行性算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。

(5)有穷性算法必须总能在执行有限步之后终止。

1.5.1算法及其性能分析

382.算法描述方法算法可以自然语言、流程图或程序设计语言描述。当一个算法用程序设计语言描述时，便成为程序。本书中，主要使用C++语言描述。3.算法的性能标准正确性：算法的执行结果应当满足预先规定的功能和性能要求。(2)简明性：一个算法应当思路清晰、层次分明、易读易懂。(3)健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果。(4)效率：有效使用存储空间和有高的时间效率。(5)最优性：解决同一个问题可能有多种算法，应进行比较，选择最佳算法。391.5.2算法的时间复杂度

程序步一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。算法的时间复杂度是程序运行从开始到结束所需的时间。40程序1.3求一个数组元素的累加之和floatsum(floatlist[],constintn){floattempsum=0.0;for(inti=0;i<n;i++)tempsum+=list[i];returntempsum;}程序步数为2n+3。411.5.3渐近时间复杂度

大O记号如果存在两个正常数c和n0，使得对所有的n，n

n0

，有f(n)

cg(n)则有f(n)=O(g(n))。渐近时间复杂度使用大O记号表示的算法的时间复杂性，称为算法的渐近时间复杂度,简称时间复杂度。42渐近时间复杂度使用大O记号表示的算法的时间复杂性，称为算法的渐近时间复杂度,简称时间复杂度。

大O记号用以表达一个算法运行时间的上界，可用程序步在数量级上估计算法的执行时间。例如，设

T(n)=3.6n3+2.5n2+2.88.9n3则根据大O记号的定义容易证明

T(n)=O(n3)43例如，程序1.2为求一个数组元素的累加之和的算法。floatsum(floatlist[],constintn){floattempsum=0.0;//1for(inti=0;i<n;i++)//n+1

tempsum+=list[i];//nreturntempsum;//1}（1）总的程序步数为2n+3，则渐近时间复杂性为O(n)。44floatsum(floatlist[],constintn){floattempsum=0.0;//1for(inti=0;i<n;i++)//n+1

tempsum+=list[i];//nreturntempsum;//1}（2）语句tempsum+=list[i]可认为是关键操作，它的执行次数为n次，则渐近时间复杂性为O(n)。很多情况下，可以通过考察一个算法中的关键操作（关键操作被认为是一个执行次数最多的程序步）的执行次数来计算算法的渐近时间复杂性。45常见的渐近时间复杂性从小到大排列有：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)

例如：若某算法程序的总程序步为4,则其渐近时间复杂性为多少？

O(4)是错误写法。应为O(1)46voidMult(inta[n][n],b[n][n],c[n][n],intn){//n

n矩阵a与b相乘得到c。

for(inti=0;i<n;i++)//n+1for(intj=0;j<n;j++)//n(n+1){c[i][j]=0;//n2 for(intk=0;k<n;k++)//n2（n+1)

c[i][j]+=a[i][k]*b[k][j];//n3}}

程序步为：2n3+3n2+2n+1

渐近时间复杂度为：T(n)=O(n3)再看一例：471.5.4最好、最坏和平均情况时间复杂度

对于某些算法，即使问题实例的规模相同，如果输入的数据不同，算法所需的时间开销也会不同。比如在有n个元素的一维数组上查找一个给定元素。48算法的空间复杂度是程序运行从开始到结束所需的存储量。1.5.5算法的空间复杂度

49程序运行所需的存储空间包括两部分：（1）固定部分

这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。（2）可变部分

这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如，分别为100个元素的两个数组相加，与分别为10个元素的两个数组相加，所需的存储空间显然是不同的。内容提要1、定义线性表抽象数据类型；2、讨论线性表的顺序存储表示方法；3、讨论单链表、循环链表等链接存储表示方法；4、线性表的应用实例——多项式的算术运算。

学号 姓名性别

964501 王小红 女

964502 林悦 女

964503 陈菁菁 女

964504 张可可 男

…

…

…表1-1学生情况表1.线性表举例2.1线性表抽象数据类型课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算(a)集合结构(b)线性结构(c)树形结构(d)图结构图1-2四种基本的结构关系

线性表是n(

0)个元素a0，a1，…，an-1的有序集合，记为（a0，a1，…，an-1）其中，n是线性表中元素的个数，称为线性表的长度，n=0时称为空表。

设ai是线性表（a0，a1，…

ai,ai+1，…

an-1）中下标为i的元素，i=0,1,…,n-1，则称ai

是ai+1的直接前驱元素，ai+1是ai的直接后继元素。

线性表是动态数据结构，它的表长可以改变。

2.线性表的定义ADT2.1线性表抽象数据类型ADTLinearList{Data:零个或多个元素的有序集合。(逻辑结构)Operations:（运算的定义）

Create()：创建一个空线性表。

Destroy()：撤消一个线性表。

IsEmpty()：若线性表空，则返回true；否则返回false。

Length()：返回表中元素个数。

Find(i,x)：在x中返回表中下标为i的元素ai(即表中第i+1个元素)。如果不存在，则返回false，否则返回true。

Search(x)：返回x在表中的下标；若x不在表中，则返回-1。

Insert(i,x)：在元素ai之后插入x。若i=-1，则x插在第一个元素a0前。插入成功返回true，否则返回false。

Delete(i)：删除元素ai。删除成功返回true，否则返回false。

Update(i,x)：将元素ai的值修改为x。修改成功返回true，否则返回

false。

Output(out)：把表送至输出流。}

3.线性表抽象数据类型（描述规范）4.线性表的C++模板抽象类（描述规范）程序2.1线性表的C++类template<classT>//使用模板的目的是为了提高通用性classLinearList{public:virtualboolIsEmpty()const=0;virtualintLength()const=0;virtualboolFind(inti,T&x)const=0;virtualintSearch(Tx)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;virtualboolUpdate(inti,Tx)=0;virtualvoidOutput(ostream&out)const=0;proteced:intn;//线性表的长度};2.2线性表的顺序表示

1.线性表的两种存储表示法

(1)

顺序表示法

(2)链接表示法2.线性表的顺序表示法是用一组地址连续的存储单元依次存储线性表中元素。顺序表示的线性表程为顺序表。存储结构是逻辑结构在机内的映象，包括：元素和关系。课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算（1）线性表的顺序表示法

若已知顺序表示的线性表中每个元素占k个存储单元，第一个元素a0在计算机内存中的地址是loc(a0)

，则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k

只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。a0a1…ai

…

an-1

…（2）地址计算公式：

顺序表类SeqList、单链表类SingleList和作为基类的线性表类LinearList三者的结构图2.6SeqList、SingleList和LinearList三者的结构关系SingleListLinearListSeqListNodefriend继承3.顺序表类程序2.1线性表的C++模板抽象类(规范)template<classT>classLinearList{public:virtualboolIsEmpty()const=0;virtualintLength()const=0;virtualboolFind(inti,T&x)const=0;virtualintSearch(Tx)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;virtualboolUpdate(inti,Tx)=0;virtualvoidOutput(ostream&out)const=0;proteced:intn;//线性表的长度，即元素个数};template<classT>classSeqList:publicLinearList<T>//SeqList继承LinearList{public:

SeqList(intmSize);~SeqList(){Delete[]elements;};boolIsEmpty()const;intLength()const;boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);boolUpdate(inti,Tx);voidOutput(ostream&out)const;private:intmaxLength;//顺序表的最大长度

T*elements;//动态一维数组的指针};定义顺序表对象的实例：SeqList<int>L(5);//定义了一个长度为5的顺序表对象Ｌ程序2.2线性表的顺序实现classSeqList:publicLinearList<T>{public:SeqList(intmSize);……private:intmaxLength;T*elements;

//动态一维数组的指针}4.动态一维数组描述顺序表a0a1…ai

…

an-1

…01…i…n-1…maxLength-1顺序表在一维数组中的存储运算的实现(1)构造函数//创建一个顺序表template<classT>SeqList<T>::SeqList(intmSize){maxLength=mSize;elements=newT[maxLength];n=0;}

012…

…

…maxLength-1elements(2)析构函数//撤消一个顺序表template<classT>SeqList<T>::~SeqList(){

delete[]elements;}（1）查找下标为i的元素ai

Find(i,x):

在x中返回表中下标为i的元素ai(即表中

第i+1个元素)。如果不存在，则返回

false，否则返回true。x=elements[i];5.在顺序存储表示下实现线性表上定义的操作a0a1…ai

…

an-1

…01…i…n-1…maxLength-1template<classT>boolSeqList<T>::Find(inti,T&x)const{if(i<0||i>n-1){cout<<"OutofBounds"<<endl;returnfalse;}x=elements[i];returntrue;}

渐近时间复杂度：O(1)

…（2）插入操作

Insert(i,x)：在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功，返回true；

后移n-i-1个元素01…ii+1i+2…n-1…

maxLength-1a0a1…ai

…插入操作an-1x…ai+1…插入操作算法：在表中下标为i的元素ai后插入xtemplate<classT>boolSeqList<T>::Insert(inti,Tx){if(i<-1||i>n-1)//{cout<<"OutOfBounds"<<endl;returnfalse;}if(n==maxLength)

{cout<<"OverFlow"<<endl;returnfalse;}for(intj=n-1;j>i;j--)//后移元素

elements[j+1]=elements[j];elements[i+1]=x;n++;returntrue;}…a0a1…ai

…an-1…ai+1…后移n-i-1个元素分析：设顺序表长度为n，则在位置i（i=-1,0,…,n-1）后插入一个元素要移动n-i-1个元素。设共有n+1个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即Pi=1/(n+1)，则平均情况下在表中插入元素需要移动元素的个数为：渐近时间复杂度：O(n)…a0a1…ai

…an-1…ai+1…后移n-i-1个元素aia0…

ai-1…（3）删除操作

Delete(i)：删除下标为i元素ai。…前移n-i-1个元素

0…i-1ii+1i+2

…n-1

…

maxLength-1删除操作an-1……删除它ai+1删除操作算法：template<classT>boolSeqList<T>::Delete(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){ cout<<"OutOfBounds"<<endl;returnfalse;}for(intj=i+1;j<n;j++)//前移n-i-1个元素

elements[j-1]=elements[j];n--;returntrue;}分析:

设顺序表长度为n,则删除元素ai（i=0,…,n-1）,要移动n-i-1元素。若删除表中每个元素的概率是相等的，即Qi=1/n，则平均情况下从表中删除一个元素需要移动元素的个数为：渐近时间复杂度：O(n)（4）顺序表的应用——集合求“并”求集合A和B的并两集合求并的算法思想是：⑴置i=0；⑵若i小于集合LB的元素个数，则做⑶，否则转⑺；⑶取出集合LB中i位置的元素x；⑷若x不在集合LA中，则将其插入集合LA的最后位置；⑸i++；⑹转⑵继续⑺结束。

求集合A和B的并求集合A和B的并例2.1求集合A和B的并A'＝Ａ∪Ｂ分析：集合可以看成是线性表，用顺序表LA和LB分别表示集合A和B，“并”的结果放在LA中。

用顺序表类SeqList实现集合“并”算法的程序，存入头文件seqlistu.h中。#include"seqlist.h"template<classT>voidUnion(SeqList<T>&LA,SeqList<T>LB){Tx;for(inti=0;i<LB.Length();i++){LB.Find(i,x);//取出集合LB中下标为i的元素放入x中

if(LA.Search(x)==-1)//如果集合LA中不存在x,则将

LA.Insert(LA.Length()-1,x);//其插入集合LA中

}}#include"seqlistu.h"constintSIZE=20;voidmain(){SeqList<int>LA(SIZE);//定义顺序表对象LA，表示集合A

SeqList<int>LB(SIZE);//定义顺序表对象LB，表示集合B

for(inti=0;i<5;i++)//插入元素0~4，构造集合LA={0,1,2,3,4}

LA.Insert(i-1,i);

for(i=5;i<10;i++)//插入5~9，构造集合B={5,6,7,8,9}

LB.Insert(i-6,i);

LB.Insert(-1,0);//LB中插入0，LB={0,5,6,7,8,9}

LB.Insert(3,2);//LB中插入2，LB={0,5,6,7,2,8,9}

LB.Insert(LB.Length()-1,4);//LB中插入4，LB={0,5,6,7,2,8,9,4}

Union(LA,LB);//两集合并，结果放入LA中

LA.Output(cout);//输出最终结果LA={0,1,2,3,4,5,6,7,8,9}}6.线性表的顺序存储表示的优缺点：（1）优点：随机存取；存储空间利用率高。（2）缺点：插入、删除效率低；必须按事先估计的最大元素个数分配连续的存储空间，难以临时扩大。2.3线性表的链接表示

1.线性表的链接存储表示法

(1)

单链表

(2)带表头结点的链表

(3)循环链表

(4)双向链表课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示

2.3.1单链表

2.3.2带表头结点的单链表

2.3.3循环链表

2.3.4双向链表2.4多项式的算术运算2.3.1单链表

单链表存储表示法每个结点只有一个指针域，称为单链表(1)

单链表的结点结构elementlinka0a1a2an-1…first∧课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示

2.3.1单链表

2.3.2带表头结点的单链表

2.3.3单循环链表

2.3.4双向链表2.4多项式的算术运算数据地址a0a1a3a4a2单链表在内存中的示意图(2)单链表结构a0a1a2an-1…first∧非空单链表first

空单链表注意：●头结点：第一个结点●单链表头指针first不能少,指向头结点（第一个结点）●最后一个结点的指针域为

●逻辑上相邻的元素在物理上不一定相邻

●不能出现“断链”现象

NULLfirst头指针绿色为结点的指针域first∧（a0，a1，a2，a3,a4）2.单链表结点类程序2.3线性表的单链表实现#include“linearlist.h”template<classT>classSingleList;template<classT>classNode{private:Telement;

Node<T>*link;

friendclassSingleList<T>;};elementlink数据地址3.单链表类程序2.3线性表的单链表实现template<classT>classSingleList:publicLinearList<T>{public:

SingleList(){first=NULL;n=0;}//构造函数

~SingleList();boolIsEmpty()const;intLength()const;boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);boolUpdate(inti,Tx);voidOutput(ostream&out)const;private:

Node<T>*first;};SingleListLinearListNodefriend继承析构函数template<classT>SingleList<T>::~SingleList(){Node<T>*p;while(first){p=first->link;deletefirst;first=p;}}a0a1firsta2∧单链表pp=∧first=∧如何阅读4.在单链表上实现线性表规范中所定义的操作（1）查找元素ai（2）插入操作（3）删除操作（1）查找元素aia0a1a2an-1…first∧单链表

由于链表失去了随机查找元素的特性,所以必须从头指针开始沿链逐个计数查找。查找元素ai的算法

template<classT>boolSingleList<T>::Find(inti,T&x)const{if(i<0||i>n-1){cout<<"OutOfBounds";returnfalse;}Node<T>*p=first;for(intj=0;j<i;j++)p=p->link;x=p->element;returntrue;}渐近时间复杂度：O(n)a0a1a2an-1…first∧单链表p（2）插入操作在给定元素ai之后插入值为x的元素。(a0,a1,...,ai,ai+1,...,an-1)即在此处插入x插入算法步骤为：①生成数据域为x的新结点，q指向新结点;②从first开始找元素ai，即第i+1个结点，p指向该结点；③将q插入p之后。④表长加1。q插入时只要修改二个指针：

q->link=p->linkp->link=q能否对调上述2语句的执行顺序？

不能，会“断链”现象aiai+1xpaiai+1xqp“断链”现象i>-1時，将q插入p之后:a0a1a2an-1…first∧单链表插入的一般情况firsta0a1a2an-1…∧qx插入时只要修改二个指针：

q->link=first；

first=q;插入在头结点之前的特殊情况i==1時，插入在頭結點之前template<classT>boolSingleList<T>::Insert(inti,Tx){if(i<-1||i>n-1){cout<<"OutOfBounds";returnfalse;}Node<T>*q=newNode<T>;q->element=x;//生成新结点qNode<T>*p=first;for(intj=0;j<i;j++)p=p->link;//找元素aiif(i>-1)

{

q->link=p->link；p->link=q;

//在p之后插入q}else{q->link=first；first=q;

//插在第一个元素之前

}n++;

//表长加１

returntrue;}渐近时间复杂度：O(n)a0a1a2an-1…first∧（3）删除操作删除元素ai。(a0,a1,...,ai...,an-1)即删除该元素删除算法步骤为：①从first开始找第i+1个结点，p指向该结点，q指向p之前驱结点;②从单链表中删除p；③释放p之空间；④表长减1。aiai+1ai-1qp删除时只要修改一个指针：

q->link=p->link删除p:删除结点的一般情况(i>0)firsta0a1a2an-1…∧删除时只要修改一个指针：

first=first->link删除头结点的特殊情况(i==0)template<classT>boolSingleList<T>::Delete(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){cout<<"OutOfBounds"<<endl;returnfalse；}Node<T>*p=first,*q=first;for(intj=0;j<i-1;j++)q=q->link;//q指向要删除结点的前一结点

if(i==0)first=first->link;

//删除的是头结点

else{p=q->link;

//从单链表中删除pq->link=p->link;}deletep;n--;

//表长减一

returntrue;}渐近时间复杂度：O(n)

aiai+1ai-1qp5.单链表的应用——集合求“交”求集合A和B的并两集合求交的算法思想是：⑴置i=0；⑵若i小于集合LA中当前元素的个数，则做⑶，否则转⑹；⑶取出集合LA中i位置的元素x；⑷若x不在集合LB中，则将其从集合LA中删除，否则i++；⑸转⑵继续;⑹结束。

求集合A和B的并例2.2求集合A和B的交A'＝Ａ∩Ｂ分析：集合可以看成是线性表，用单链表LA和LB分别表示集合A和B，“交”的结果放在LA中。#include"singlelist.h"template<classT>voidIntersection(SingleList<T>&LA,SingleList<T>&LB){Tx;inti=0;while(i<LA.Length()){LA.Find(i,x);//取出集合LA中i位置的元素xif(LB.Search(x)==-1)LA.Delete(i);//若x不在集合LB中，则将其从集合LA中删除

elsei++;//否则i++}}2.3.2带表头结点的单链表

上一节介绍的单链表在做插入和删除运算时，要考虑一般情况和特殊情况，用带表头结点的单链表可以简化上述两种算法。课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示

2.3.1单链表

2.3.2带表头结点的单链表

2.3.3单循环链表

2.3.4双向链表2.4多项式的算术运算1.带表头结点的单链表(a0,a1,...,ai...,an-1)

在原单链表中增加一个结点，但它的element域中不存放线性表中的任何元素，称该结点为表头结点。firsta0a1a2an-1…∧非空表first∧空表2.带表头结点单链表HeaderList的构造、插入和删除（1）构造函数SingleList<T>::SingleList()//单链表构造函数{first=NULL;n=0;}HeaderList<T>::HeaderList()//带表头结点单链表构造函数{Node<T>*first=newNode<T>;first->link=NULL;n=0;}first∧空表first

空单链表（2）插入操作template<classT>boolHeaderList<T>::Insert(inti,Tx){if(i<-1||i>n-1){cout<<"OutOfBounds“<<endl;returnfalse;}Node<T>*p=first;for(intj=0;j<=i;j++)p=p->link;Node<T>*q=newNode<T>;q->element=x;

q->link=p->link;p->link=q;n++;returntrue;}a0a1a2an-1…first∧p

（3）删除操作template<classT>boolHeaderList<T>::Delete(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){cout<<"OutOfBounds"<<endl;returnfalse;}Node<T>*q=first,*p;for(intj=0;j<i;j++)q=q->link;p=q->link;q->link=p->link;deletep;n--;returntrue;}q

a0a1a2an-1…first∧p

例如删除a22.3.3单循环链表

1.单循环链表

单循环链表可以从表中任一结点出发访问表中所有结点。课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示

2.3.1单链表

2.3.2带表头结点的单链表

2.3.3单循环链表

2.3.4双向链表2.4多项式的算术运算带表头结点的单循环链表不带表头结点的单循环链表a0a1a2an-1…first空表first非空表a0a1a2an-1…first非空表空表first∧2.3.4双向链表

1.双向链表(1)

双向链表的结点结构lLinkelementrLink课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示

2.3.1单链表

2.3.2带表头结点的单链表

2.3.3单循环链表

2.3.4双向链表2.4多项式的算术运算(2)带表头结点的双向循环链表2.3线性表的链接表示2.3.3双向链表3.双向链表的插入插入操作的核心步骤：

(1)DNode<T>*q=newDNode<T>;q->element=x;(2)①q->llink=p->llink;

②q->rlink=p;

③p->llink->rlink=q;④p->llink=q;

能否颠倒顺序？③p->llink->rlink=q;①q->llink=p->llink;②q->rlink=p;④p->llink=q;xqp

插入操作：在p所指示的结点前插入值为x新结点2.3线性表的链接表示4.双向链表的删除删除操作的核心步骤是：(1)①p->llink->rlink=p->rlink;

②p->rlink->llink=p->llink;(2)deletep;能否颠倒顺序？p

删除操作:删除p所指示的结点2.4多项式的算术运算

线性表是一种最简单、最基本，也是最常用的数据结构，其用途十分广泛。作为线性表应用的一个例子，下面讨论一元整系数多项式的算术运算。从该例中，要学会如何分析元素间的关系、结构的描述、存储方式的选择，如何描述和实现算法。课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算一元整系数多项式

p(x)=3x14-8x8+6x2+2

要求:(1)按降幂排列

(2)做q(x)

q(x)+p(x)1.数据元素该多项式是由一项一项组成的。我们忽略掉各项具体数字的细节，即每一项就是由系数(coef)和指数(exp)组成的：coef·xexp。每一项就是一个要处理的数据元素，即

(coef,exp)

。分析:2.元素间的逻辑关系由于多项式按降幂排列，因此每一项都有一个指数比它高的项，有一个比它低的项，除了最高项没有比它高的项，最后一项没有比踏低的项外。这样，多项式的每一项就组成了一个线性表，线性表中的每个数据元素是多项式的一项(coef,exp)。因此，一元整系数多项式可以视为线性表。3.存储表示(2,10)(4,8)(-6,2)１.用顺序存储：q(x)线性表有顺序和链接存储：q(x)=2x10+4x8-6x2，p(x)=3x14-8x8+6x2+2做q(x)+p(x)q(x)，结果为：q(x)=3x14+2x10-4x8+2(3,14)

(-8,8)(6,2)(2,0)p(x)(3,14)

(2,10)(-4,8)(2,0)结果q(x)

从结果中可以发现，在q(x)上做了插入和删除运算，因此不宜采用顺序存储。p(x)=3x14-8x8+6x2+2

２.用带表头结点的单循环链表表示一元多项式多项式的项coef

xexp结点结构：coefexplink314px-8820620-12.4.1项结点的C++类

(1)项结点的C++类：

classTerm(2)多项式的C++类：

classPolynominal(3)类Polynominal是类Term的友元类。课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算

2.4.1项结点的C++类

2.4.2多项式的C++类

2.4.3多项式的实现程序2.6多项式项结点的C++类classPolynominal；classTerm{public:Term(intc,inte);Term(intc,inte,Term*nxt);Term*InsertAfter(intc,inte);//在this指

//针指示的项后插入新项

private:intcoef;intexp;Term*link;friendostream&operator<<(ostream&,constTerm&);//输出项friendclassPolynominal;};项结点类的两种构造函数Term::Term(intc,inte):coef(c),exp(e){link=0;}Term::Term(intc,inte,Term*nxt):coef(c),exp(e){link=nxt;}项结点类的InsertAfter函数Term*Term::InsertAfter(intc,inte){//函数功能：在调用该函數的项结点对象后插入新的结点

link=newTerm(c,e,link);returnlink;}关于项结点类的InsertAfter函数的执行过程q210-1q1qx申请新项结点存储单元新项结点例如：执行q1->InsertAfter(3,14)//结点q1后面插入新结点Term*Term::InsertAfter(intc,inte){link=;returnlink;}3

14newTerm(c,e,link)先做new

这里要搞清楚一个问题：上述函数中，link是指哪个结点的指针域？

q1的指针域！存放的是指向q1后继的q的地址!关于项结点类的InsertAfter函数的执行过程q210-1q1qx新项结点例如：执行q1->InsertAfter(3,14)Term*Term::InsertAfter(intc,inte){link=;returnlink;}3

14newTerm(c,e,link)再做Term(3,14,q)314q最后执行赋值运算=新项结点的地址赋值给q1的指针域重载输出操作符<<ostream&operator<<(ostream&out,constTerm&val){//函数功能：输出项结点

if(val.coef==0)returnout;out<<val.coef;switch(val.exp){case0:break;case1:out<<"X";break;default:out<<"X^"<<val.exp;}returnout;}

例如：-4x2

将以-4x^2的形式输出2.4.2多项式的C++类

1.多项式类Polynominal的成员函数(1)AddTerms

函数:

通过输入流in，输入多项式的各项(c,e)构造一个多项式。(2)Output

函数:

将多项式的每一项按降幂方式送输出流。(3)PolyAdd

函数:

实现将多项式r加到指针this指示的多项式上。课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算

2.4.1项结点的C++类

2.4.2多项式的C++类

2.4.3多项式的实现程序2.7多项式的C++类classPolynominal{public:Polynominal();~Polynominal();voidAddTerms(istream&in）；

voidOutput(ostream&out)const；

voidPolyAdd(Polynominal&r）；

private:Term*theList;//头指针

friendostream&operator<<(ostream&,constPolynominal&);friendistream&operator>>(istream&,Polynominal&);friendPolynominaloperator+(

Polynominal&,Polynominal&);}2.4.3多项式类的实现

构造函数Polynominal::Polynominal(){theList=newTerm(0,-1); theList->link=theList;}theList0-1课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算

2.4.1项结点的C++类

2.4.2多项式的C++类

2.4.3多项式的实现2.多项式输入、输出程序2.9多项式类的输入和输出函数AddTerms函数从输入流in通过输入各项来构造多项式。voidPolynominal::AddTerms(istream&in){Term*q=theList;intc,e;for(;;){cout<<"Inputaterm(coef,exp):\n"<<endl;in>>c>>e;if(e<0)break;

q=q->InsertAfter(c,e);}}-88theList0-1q-88theList3140-1qp(x)=3x14-8x8+6x2+2

输入多项式的项，建立多项式:

62(3,14)

20(-8,8)(6,2)(2,0)Output函数将多项式按降幂方式送输出流。voidPolynominal::Output(ostream&out)const{//依次输出多项式的每一项

intfirst=1;Term*p=theList->link;cout<<"Thepolynominalis:\n"<<endl;for(;p!=theList;p=p->link){if(!first&&(p->coef>0))out<<"+";first=0;out<<*p;//调用Term类上重载的“<<”操作。

}cout<<"\n"<<endl;}314px-8820620-1pq1314px-8820620-1q210qx48-620-1314qx21020-480-1一元整系数多项式相加3.多项式相加——实现q(x)

q(x)+p(x)3.多项式相加——实现q(x)

q(x)+p(x)

设p和q分别指向多项式p(x)和q(x)的当前正进行比较的项，初始时分别指向两多项式中最高幂次的项。q1指向q的前驱结点。对p(x)进行遍历，根据指针p、q的exp域的大小情