数据结构(严蔚敏)第四章

第二章线性表理解线性表的逻辑结构及定义掌握线性表的顺序存储表示和操作实现掌握线性表的链式存储表示和操作实现线性表结构的应用举例内容提要:§2.1线性表的逻辑结构

一、线性表的定义

[线性表(LinearList)]：由n个数据元素(结点)组成的有限序列。数据元素之间具有线性关系.其中数据元素的个数n定义为表的长度。当n=0时称为空表.

常常将非空的线性表(n>0)记作：

(a1，a2,a3，…an)ai是数据元素

除第一个外,每个数据元素均有且只有一个前驱元素;除最后一个外,每个数据元素均有且只有一个后继元素。[线性关系]数据元素之间的关系是它们在数据集合中的相对位置.特点:§2.1线性表的逻辑结构

一、线性表的定义2、数据结构描述:Liner_List=(D,R)D={ai|ai∈

D0i=1,2,......n>=0}R={N}N={<ai-1,ai>|ai-1,ai∈D0i=2,3,4,....}D0是某个数据对象直接前驱:ai-1是ai的前驱i=2,3,4,.....n直接后继:ai+1是ai的后继i=1,2,3,....n-1空表:n=0长度:数据元素个数n3、术语:§2.1线性表的逻辑结构

二、线性表上常见运算InitList(&L)

操作结果:构造一个空的线性表L。

DestroyList(&L)初始条件:线性表L已经存在。操作结果:销毁线性表L。ClearList(&L)

初始条件:线性表L已经存在。操作结果:将线性表L重置为空表。§2.1线性表的逻辑结构

二、线性表上常见运算ListEmpty(L)

初始条件:线性表L已经存在。操作结果:若线性表L为空表，则返回TURE;否则返回FALSE。ListLength(L)

初始条件:线性表L已经存在。操作结果:返回线性表L中的数据元素个数。§2.1线性表的逻辑结构

二、线性表上常见运算GetElem(L,i,&e)；初始条件:线性表L已经存在，1<=i<=ListLength(L)。操作结果:用e返回线性表L中第i个数据元素的值。LocateElem(L,e,compare())初始条件:线性表L已经存在，compare()是数据元素判定函数。操作结果:返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。§2.1线性表的逻辑结构

二、线性表上常见运算PriorElem(L,cur_e,&pre_e)

初始条件:线性表L已经存在。操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败;pre_e无意义。NextElem(L,cur_e,&next_e)初始条件:线性表L已经存在。操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无意义。§2.1线性表的逻辑结构

二、线性表上常见运算ListInsert(&L,i,e)初始条件:线性表L已经存在，1<=i<=ListLength(L)+1。操作结果:在L的第i个位置之前插入新的数据元素e,L的长度加1。插入前（长度为n）:

（a1,a2,…,ai-1,ai,…,an）插入后（长度为n+1）:

（a1,a2,…,ai-1,e,ai,…,an）§2.1线性表的逻辑结构

二、线性表上常见运算ListDelete(&L,i,&e)初始条件:线性表L已经存在，1<=i<=ListLength(L)。操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。删除前（长度为n）:

（a1,a2,…,ai-1,ai,ai+1,…,an）删除后（长度为n-1）:

（a1,a2,…,ai-1,ai+1,…,an）ListTraverse(&L,visited())§2.1线性表的逻辑结构

三、线性表的ADTADTList{

数据对象：D={ai|ai属于Elemset,(i=1,2,…,n,n≥0)}

数据关系：R1={＜ai-1,ai＞|ai-1,ai属于D,(i=2,3,…,n)}

基本操作：

InitList(&L);DestroyList(&L);ListInsert(&L,i,e);ListDelete(&L,i,&e);等等}ADTList§2.1线性表的逻辑结构

四、线性表的分类按数据元素分:

一般线性表字符串数组广义表按实施操作分:一般线性表---可以在任何位置插入,删除堆栈---只能在一端插入,删除队列---出队在一端,删除在另一端双端队列---在两端可以插入,删除§2.1线性表的逻辑结构

五、线性表ADT的应用举例例1:已知有线性表L,要求删除所有X的出现Statusdel(list&L,ElemTypex){k=LocateElem(L,x,equal);

while(k!=0)

{

Listdelete(&L,k,&e);k=LocateElem(L,x,equal);}return(OK);}假设线性表ADT已经实现!§2.1线性表的逻辑结构

五、线性表ADT的应用举例例2:巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB合并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。---归并方法1:合并,再排序O(m+n)2方法2:归并,利用分别有序的特点时间复杂度O(m+n)§2.1线性表的逻辑结构

五、线性表ADT的应用举例voidMergeList(ListLa,ListLb,List&Lc){//已知非递减线性表La,Lb.将所有La和Lb中的数据元素归并//到Lc中,使Lc

的数据元素也是非递减的.InitList(&Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);While((i<=La_len)&&(j<=Lb_len))//La和Lb均非空

{GetElem(La,i,ai);GetElem(Lb,j,bj);

if

(ai<=bj){ListInsert(Lc,++k,ai);++i;}

else{ListInsert(Lc,++k,bj);++j;}}while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while

(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}§2.2线性表的顺序存储表示和实现

一、顺序存储结构1.存储方式:在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素.假设存储每个元素占用L个存储单元,并且以所占的第一个单元的地址作为该元素的存储地址.于是:L§2.2线性表的顺序存储表示和实现

一、顺序存储结构用LOC(ai)表示ai的存储地址,则有:LOC(a2)=LOC(a1)+LLOC(a3)=LOC(a2)+L=LOC(a1)+2L……LOC(ai)=LOC(ai-1)+L=LOC(a1)+(i-1)*LLOC(a1)称为基地址,用base表示.LOC(ai)=BASE+(i-1)*L§2.2线性表的顺序存储表示和实现

一、顺序存储结构2.特点:存储空间必须是连续的,预分配.逻辑顺序与物理顺序一致,用物理上的相邻来表示逻辑上的线性关系.任意相邻元素之间无空闲空间,且相距为L.已知基地址,可以计算出任意元素的存储地址:

LOC(ai)=base+(i-1)*L§2.2线性表的顺序存储表示和实现

一、顺序存储结构3.虚拟实现在高级语言中,数组是采用顺序存储的,因而,我们可以用高级语言中的数组类型来说明上面的存储方式.§2.2线性表的顺序存储表示和实现

二、各个运算在顺序存储下的虚拟实现§2.2线性表的顺序存储表示和实现

二、各个运算在顺序存储下的虚拟实现§2.2线性表的顺序存储表示和实现

二、各个运算在顺序存储下的虚拟实现§2.2线性表的顺序存储表示和实现

二、各个运算在顺序存储下的虚拟实现8.插入

//在顺序线性表L中第i个元素之前插入新元素e考虑空间满的情况§2.2线性表的顺序存储表示和实现

二、各个运算在顺序存储下的虚拟实现§2.2线性表的顺序存储表示和实现

二、各个运算在顺序存储下的虚拟实现

插入算法的分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：删除算法的分析

在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：

§2.2线性表的顺序存储表示和实现小结:线性表的定义及逻辑结构线性表的顺序存储结构及特点线性表在顺序存储结构下操作的实现(如:构造表,取表长,插入,删除等)§2.3线性表的链式存储表示和实现答案是肯定的!----链式存储结构,但是,它有优点,也存在缺点.那么,有没有一种灵活的存储方式呢?从前面看到,顺序存储结构有特点:逻辑顺序与物理顺序一致;随机存取等但是,也存在一些缺点:插入,删除操作要移动元素;存储空间是预分配的,不灵活,空间浪费;表的存储空间难扩充等§2.3线性表的链式存储表示和实现存储一个元素占用的空间称为一个结点存储方式:

用任意存储空间单元来存放线性表的各个元素,为了能体现元素之间的逻辑关系(线性),在存放每个元素的同时,也存放相关元素的信息(相关元素的存储地址),即用指针来表示元素之间的逻辑关系.存放一个数据元素占用的空间为:§2.3线性表的链式存储表示和实现存储空间不一定连续;逻辑关系是由指针来体现的;逻辑上相邻,物理上不一定相邻;非随机存取(顺序存取),即访问任何一个元素的时间不同.特点:§2.3线性表的链式存储表示和实现分类:根据存储相关元素的信息不同,可分为单链式存储结构:存放元素的同时,存放其后继(或前驱)元素的信息;双链式存储结构:存放元素的同时,存放其前驱和后继元素的信息;循环单链式存储结构:在链式存储结构中,由于最后一个元素没有后继,其结点的指针域为空,若在此记下第一个元素的存储地址,则形成循环单链式存储结构:循环双链式存储结构:在双链式存储结构中,最后一个元素结点的后继指针指向第一个元素结点,第一个元素的前驱指针指向最后一个元素结点.§2.3线性表的链式存储表示和实现

一、单链表存储结构1.方式:用任意存储空间单元来存放线性表的各个元素,为了能体现元素之间的后继逻辑关系,在存放每个元素的同时,也存放其后继元素的信息(即后继元素的存储地址),即用指针来表示元素之间的后继逻辑关系.存放一个数据元素占有的空间为:例（赵，钱，孙，李，周，伍，张，王）

的链式表示11319253137437头指针：31(赵的地址)存储地址:钱孙李周赵伍张王H§2.3线性表的链式存储表示和实现

一、单链表存储结构头指针:第一个元素的存储地址;头结点:有时为了方便,增加一个结点,其数据域不存放任何元素,其指针域存放第一个元素的存储地址.头结点指针:指向头结点的指针;§2.3线性表的链式存储表示和实现

一、单链表存储结构2.特点:存储空间不一定连续;元素之间的后继关系是由指针来表现的;逻辑上相邻,物理上不一定相邻;非随机存取(顺序存取),即访问任何一个元素的时间不同§2.3线性表的链式存储表示和实现

一、单链表存储结构§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现时间复杂性:O(n)§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现3.访问第i个元素由于仅仅知道第一个元素的存储地址,第i个元素的地址不像顺序存储那样可以立即计算出来,所以必须利用元素的后继指针去找到指定元素的存储地址,然后访问它!!

即从头开始遍历每个元素,并且记数,看是否是指定元素.§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现访问的元素不同,花的时间不同时间复杂度:O(n)§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现时间复杂度O(1)x§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现新插入元素时间复杂度O(n)§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现时间复杂度O(1)§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现时间复杂度O(n)§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现r时间复杂度O(n)§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现重复n次时间复杂度O(n)方法2:从尾到头,即从最后一个元素结点逐个创建各个元素结点.每次都是链到当前链表的前面,即头结点之后.§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现∧an时间复杂度O(n)§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现7.归并方法:可以在两个表上直接做,不需要开辟新空间,改变指针即可.实现的过程是当两个线性表非空时,不另建新表空间,只需将原来两个链表中的结点之间的关系解除,重新按元素值将所有结点连接成一个链表§2.3线性表的链式存储表示和实现

二、在单链式存储结构下的操作实现时间复杂度O(n)pa;小结线性表的链式存储结构的方式,特点,分类线性表的单链式存储结构的虚拟实现线性表在单链式存储结构下操作的实现(如:初始化,求表长,取表中第i个元素,插入,删除,建立链表,归并等)顺序表与链表的比较基于空间的比较存储分配的方式顺序表的存储空间是静态分配的链表的存储空间是动态分配的存储密度=结点数据本身所占的存储量/结点结构所占的存储总量顺序表的存储密度=1链表的存储密度<1顺序表与链表的比较基于时间的比较存取方式顺序表可以随机存取，也可以顺序存取链表是顺序存取的插入/删除时移动元素个数顺序表平均需要移动近一半元素链表不需要移动元素，只需要修改指针§2.3线性表的链式存储表示和实现

三、循环单链式存储结构方式:与线性表的单链式存储结果基本相同,只是:

单链式存储结果时最后一个元素没有后继,其后继指针为空!现在把它变为指向第一个元素(或头结点)的指针.§2.3线性表的链式存储表示和实现

三、循环单链式存储结构2.特点:具有单链表的特点从任何一个元素都可以访问整个线性表3.虚拟实现:同单链式完全一样!§2.3线性表的链式存储表示和实现

三、循环单链式存储结构二.线性表的各个运算在循环单链存储结构下的虚拟实现

基本与单链式存储结构的相同,但是在处理最后一个元素结点时,要注意!!(自己写出)1ZHANG2WANG6LI5ZHAO5WU-1CHEN31ZHANG2WANG3LI4ZHAO5WU-101234560123456修改前（插入chen,删除zhao)修改后用一维数组描述线性链表四.静态链表定义constintMaxSize=100;//静态链表大小typedefintElemType;typedefstructLNode{//静态链表结点

ElemTypedata;intcur;}SLNode;typedefstruct{//静态链表

SLNode

LNodes[MaxSize];intnewptr; //当前可分配空间首地址}SLinkList;§2.3线性表的链式存储表示和实现

四、双链式存储结构1.方式:用任意存储空间单元来存放线性表的各个元素,为了能体现元素之间的前驱,后继逻辑关系,在存放每个元素的同时,也存放其前驱,后继元素的信息(即前驱和后继元素的存储地址),即用两个指针来表示元素之间的前驱,后继逻辑关系.存放一个数据元素占用的空间为:§2.3线性表的链式存储表示和实现

四、双链式存储结构§2.3线性表的链式存储表示和实现

四、双链式存储结构2.特点:具有单链表的特点前驱操作简单O(1)任何位置插入,删除都简单了(已知该位置指针)§2.3线性表的链式存储表示和实现

四、双链式存储结构插入结点：指针p所指的结点前插入指针s所指的结点(1)s->prior=p->prior;a1a3a2ps插入前：sa1a2p插入后：a3(2)p->prior->next=s;(3)s->next=p;(4)p->prior=s;

二.线性表的各个运算在双链式存储结构下的虚拟实现pai-1x①②③④ai1）插入操作算法

StatusListInsert_DuL(DuLinkList&L,inti,

ElemTypee){//在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1。

if(!p=GetElemP_DuL(L,i)))//在L中确定第i个元素的位置指针p

returnERROR;//p=NULL，即插入位置不合法if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnERROR;

s->data=e;

s->prior=p-prior;p->prior->next=s;//完成插入图示中的①②

s->next=p;p->prior=s;

//完成插入图示中的③④

returnOK;}//LinstInsert_DuL

§2.3线性表的链式存储表示和实现

四、双链式存储结构删除结点：删除指针p所指的结点p删除前：删除后：a1a2a3p->next->proir=p->prior释放结点：free(p);p->prior->next=p->nexta1a2a3paiai+1p①②ai-12)删除操作算法StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){

//删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长

if(!p=GetElemP_DuL(L,i)))//在L中确定第i个元素的位置指针p

returnERROR;//p=NULL，第i个元素不存在

e=p->data;

p->prior->next=p->next;//完成删除图示中的①

p->next->prior=p->prior;//完成删除图示中②

free(p);returnOK;

}//LinstDelete_DuL

§2.3线性表的链式存储表示和实现

四、循环双链式存储结构1.方式:同双链式存储结构基本相同,但最后一个元素的后继指针不空,而是指向第一个元素(或头结点);第一个元素的前驱指针不空,而是指向最后一个元素结点.§2.3线性表的链式存储表示和实现

四、循环双链式存储结构2.特点:相当于两个循环单链即从表的任意结点出发可以通过正向环（或反向环）找到表中其它结点。3.虚拟实现:

与双链式完全相同

(自己写出)二.线性表的各个运算在循环双链存储结构下的虚拟实现

(自己写出)§2.4线性表结构应用举例

------一元n次多项式的处理一.问题的提出符号处理是一类非数值性问题,一元多项式就是符号处理的一类实例.一个一元n次多项式的一般形式如下:

Pn(x)=p1xe1+p2xe2+…+pmxem其中

p1,p2,…,pm为各项的系数,非零;

e1,e2,…,em为各项的指数,满足

0<=e1<=e2<=…<=em在计算机中存储这样的多项式,并对它们进行处理,如:加法,减法,求值,求导等.§2.4线性表结构应用举例

------一元n次多项式的处理二.问题分析这个问题的数据是多项式的”项”,即一个多项式有多个项组成,一个项包括符号X和它的系数,指数.对多项式的处理实际上就是系数,指数的操作(运算),因此,符号X可以不看作数据.一个一元n次多项式如果形式为:Pn(x)=p0+p1x+p2x2+……+pn-1xn-1+pnxn则它可以由n个系数确定,即(p1,p2,……,pn-1,pn)若按幂次从低到高排列,它可以抽象为一个线性表.但是,如果多项式有缺项,特别是缺项比较多时,则线性表的数据元素中会有很多零.例如:

P(x)=1+2x5-x10可抽象为线性表为:(1,0,0,0,0,2,0,0,0,0,-1)无论采用什么存储结构,效率都不高(因为存储了很多零元素).§2.4线性表结构应用举例

------一元n次多项式的处理于是,一个一元n次多项式的一般形式如下:Pn(x)=p1xe1+p2xe2+…+pmxem其中p1,p2,…,pm为各项的系数,非零;

e1,e2,…,em为各项的指数,满足

0<=e1<=e2<=…<=em即,一项由系数和指数组成,它可以抽象为如下的线性表:((p1,e1).(p2,e2),……,(pm,em))注意:如果多项式的各幂次项都不缺,或缺的很少,那么可以抽象为第1种线性表,如果项缺的很多,可抽象为第2种线性表.§2.4线性表结构应用举例

------一元n次多项式的处理三.处理时定义的操作创建:在计算机中存储一个多项式;

输出:以直观的形式输出多项式;

求值:给定一个X0,求多项式的值;

求导:求给定的多项式的一阶导数;