02 第2章 线性表.pptx

第1页：第二章线性表

第二章线性表

第2页：线性结构的特点

线性结构的特点

• 存在唯一的一个被称为“第一个”的数据元素
• 存在唯一的一个被称为“最后一个”的数据元素
• 除第一个元素之外每个元素都有且只有一个前驱
• 除最后一个元素之外每个元素都有且只有一个后继

第3页：第二章内容提要

内容提要:

• 第一节线性表的定义
• 第二节线性表的顺序表示和实现
• 第三节线性表的链式表示和实现
• 本章重点

第4页：第一节线性表的定义

第一节线性表的定义

第5页：1.1线性表的定义

1.1线性表的定义

• 是n(n>=0)个数据元素的有限序列
• 数据元素可以是：数字、符号、记录或复杂结构，例如
• 单个字母线性表{A,B, C, …,Z}O整数线性表{6，17，28，59，199}O复杂时，数据元素就是记录，含有大量记录的线性表构成文件，例如

第6页：数据项、记录与文件示例

O数据项->记录->文件……………好商业120.0王磊1003好商业145.2李明1002面积类别使用情况地块号户主记录数据项文件

第7页：1.2线性表特性

1.2线性表特性

• 数据元素各式各样、但具有相同的特性
• 相邻元素之间存在着序偶关系D例如（a1, … ,ai-1,ai,ai+1,…,an）Dai-1领先于ai,ai领先于ai+1Dai-1是ai是的前驱，ai+1是ai是的后继Di=1,2,…,n-1,ai是有且仅有一个直接后继Di=2,…,n,ai是有且仅有一个直接前驱

第8页：1.3线性表相关概念

1.3线性表相关概念

• 长度：元素的个数n心空表:n=0
• 非空表：n!=0心a1是第1个元素，an是最后一个元素，ai是第i个元素心i为数据元素在线性表中的位序
• 操作：访问、插入、删除

第9页：1.4抽象数据类型线性表的定义

1.4抽象数据类型线性表的定义

• ADTList{
• 数据对象：D={ai|aiElemset,i=1,2,…,n,n0}
• 数据关系：R={<ai-1,ai>|ai,ai+1D,i=2,…,n}
• 基本操作：InitList(&L)//构造一个空的线性表LDestroyList(&L)//消毁线性表LListLength(L)//返回L中数据元素的个数ListInsert(&L,i,e)//1≤i≤ListLength(L)+1,在L中第i个位置之前插入数据元素e,L长度加1ListDelete(&L,i,&e)//1≤i≤ListLength(L),删除L中的第i个元素，并用e返回ListTraverse(L,visit())//依次对L的每个元素调用函数visit()…………
• }ADTList

第10页：1.5线性表的复杂操作

1.5线性表的复杂操作

• 两个或两个以上的线性表合并
• 一个线性表分成两个或两个以上的线性表
• 重新复制一个线性表等等
• 例2-1合并A、B两个线性表(P20)
• 例2-2合并两个非递减有序排列的线性表

第11页：算法2.2两非递减有序线性表归并

算法2.2两非递减有序线性表归并

• VoidMergeList(ListLa,ListLb,List&Lc){
• 定义有关变量
• InitList(Lc);//初始化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);//得到La、Lb中的一个元素if(ai<=bj){ListInsert(Lc,++k,ai);++i}//ai插入Lc,i,k都增加1else{ListInsert(Lc,++k,bj); ++j}//bj插入Lc,j,k都增加1
• }//La或Lb两个之中必定有一个操作到了最后一个元素

第12页：算法2.2续：剩余元素插入

while(i<=La_len){//La表还有元素，将剩余元素顺序插入LcGetElem(La,i++,ai);ListInsert(Lc,++k,ai);

• }
• while(j<=Lb_len){//Lb表还有元素，将剩余元素顺序插入LcGetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);
• }
• }基本操作是插入元素，时间复杂度为O(ListLength(La)+ListLength(Lb))

第13页：第二节线性表的顺序表示和实现

第二节线性表的顺序表示和实现

第14页：2.1顺序表示的含义

2.1顺序表示的含义

• 线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素
• 特点：
• 第i个元素ai的存储位置可以用公式计LOC(ai)=LOC(a1)+(i-1)*L其中LOC(a1)第一个元素a1的存储位置，L每个元素需占的存储单元
• 表中相邻的元素ai和ai+1赋以相邻的存储位置LOC(ai)和LOC(ai+1)
• 是一种随机存储结构：只要知道线性表的起始位置就可随机存取线性表中的任一元素

第15页：2.2顺序存储结构示意图

内存状态a1a2…ai…anbb+(n-1)L…b+(i-1)L…b+L存储地址１n…i…２元素序号2.2顺序存储结构示意图

第16页：2.3顺序存储结构的高级语言定义

2.3顺序存储结构的高级语言定义

• 固定长度
• VB:
• VC:DimGrade(100)asIntegerfloatX[100];
• 动态分配顺序存储空间
• #defineLIST_INIT_SIZE100//初始分配量
• ＃defineLISTINCREMENT10//分配增量
• Typedefstruct{ElemType*elem;//存储空间基址length;//当前长度listsize;//当前分配的存储容量intint
• ｝SqList;

第17页：算法2.3线性表初始化

算法２.３:线性表初始化 StatusInitList_Sq(SqList&L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)) if(!L.elem)exit(OVERFLOW);L.length=0;L.Listsize=LIST_INIT_SIZE;returnOK }

第18页：算法2.4插入元素e

算法２.４:在第i个元素之前插入元素e StatusListInsert_Sq(SqList&L,inti,ElemTypee){ if(i<1||i>L.length+1)returnERROR;if(L.length>=L.Listsize){if(!newbase)exit(OVERFLOW);//新基址L.Listsize+=LISTINCREMENT;} q<-p新空间0p+1e第i个元素i-1L.length-1p

第19页：顺序表插入位置示意图

q= &(L.elem[i-1])//q为插入位置（第i个元素之前）

• for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置之后的元素右移
• *q=e;
• ++L.length;
• returnOK;
• }q<-p新空间0i-1L.length-1pp=&a;将a的地址赋给pp+1e第i个元素

第20页：算法2.5删除第i个元素

算法２.5:删除第i个元素并返回给ee第i个元素 StatusListDelete_Sq(SqList&L,inti,ElemType&e){ if( (i<1)||(i>L.length))returnERROR;p= &(L.elem[i-1])//p为删除元素的位置 e=*p; q = L.elem+L.length-1;for(++p; p<=q; ++p)*(p-1)=*p//被删除元素之后的元素左移 --L.length; returnOK; L.elemp->q0i-1L.length-1 }

第21页：2.4顺序存储结构的讨论

2.４顺序存储结构的讨论

• 由于逻辑相邻元素，物理位置也相邻，所以进行插入与删除操作时元素要进行移动处理
• 插入和删除操作的主要耗时是移动元素
• 平均的情况下，插入和删除元素的时间是表中长度的一半，所以时间复杂度为O(n),如插入：n2(ni1)1n1n1i1EispEn1p(ni1)iin1i11is

第22页：算法2.6按值查找元素位序

算法２.６:在线性表中查找第１个值与e满足compare()的元素的位序 intLocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)){ i =1; p=L.elem; while(i<=L.length&&!(*compare)(*p++,e))++i; if(i<L.length)returni; elsereturn0; } 基本操作为两元素之间的比较 时间复杂度为O(L.length)先比较*p和e，然后p++

第23页：算法2.7顺序表的合并

算法２.7:顺序表的合并 VoidMergeList_Sq(SqListLa,SqListLb,SqList_Lc&Lc){ pa=La.elem; pb=Lb.elem; Lc.Listsize=Lc.length=La.length+Lb.length; pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType)); if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1;

第24页：算法2.7续：剩余元素处理

while(pa<=pa_last&&pb<=pb_last){//归并if(*pa<=*pb)*pc++ =*pa++;else*pc++=*pb++

• }//插入La剩余元素//插入Lb剩余元素
• while(pa<=pa_last)*pc++=*pa++;
• while(pb<=pb_last)*pc++=*pb++;
• }
• 基本操作为元素赋值
• 时间复杂度为O(La.length+ Lb.length)

第25页：2.5顺序存储结构的特点

2.5顺序存储结构的特点

• 优点：
• 逻辑上相邻，物理位置也相邻
• 可以随机存取表中任一元素
• 缺点：
• 插入和删除元素时需要移动大量元素

第26页：第三节线性表的链式表示和实现

第三节线性表的链式表示和实现

第27页：3.1链式表示的含义

3.1链式表示的含义

• 线性链表
• 循环链表
• 双向链表
• 利用一组任意的存储单元存储线性表的元素
• 存储单元除包含数据元素本身外，还包含指向前驱结点或后继结点的指针
• 链式存储单元也叫结点，包含数据域、指针域
• 逻辑上相邻、物理位置不一定相邻
• 不能随机存取
• 三种形式：结点前驱指针数据域后继指针

第28页：3.2线性链表

3.2线性链表

• 结点包含数据域和后继指针域结点数据域指针域
• n个结点(ai(1≤i≤n)的存储映象)链接成一个链表
• 每个结点只包含一个后继指针，又称线性链表或单链表
• 设有线性表:（a1,a2,…,ai,…,an)，则可用下图表示La1a2an
• 空表非空表L空表单链表第1个结点前附设头结点可以不存任何信息，也可存储表的长度

第29页：3.2.1单链表的链式存储结构

3.2.1单链表的链式存储结构 TypedefstructLNode{ ElemTypedata; StructLnode*next; } LNode,*LinkList 单链表任意两个元素的存储位置没有固定的关系 但每个元素的位置都包含在其直接前驱结点的信息之中 若p->data=ai，则p->next->data=ai+1 查找第i个元素必须从头指针开始

第30页：算法2.8单链表取元素

算法2.8GetElem函数在单链表中的实现 StatusGetElem_L(LinkListL,inti,ElemType&e){ p=L->next; j=1;while(p&&j<i){++j; } if(!p||j>i)returnERROR;e=p->data; returnOK; } 
第31页：算法2.9单链表插入
算法2.9插入函数在单链表中的实现 StatusListInsert_L(LinkList&L,inti,ElemTypee){p=L; j =0;while(p&&j<i-1){ p= p->next; ++j}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e; s->next= p->next;p->next=s; returnOK; } 算法的时间复杂度为O(n)spP->next
第32页：算法2.10单链表删除
算法2.10删除函数在单链表中的实现 StatusListDelete_L(LinkList&L,inti,ElemType&e){p=L; j =0;while(p->next&&j<i-1){ p=p->next; ++j }if(!(p->next) ||j>i-1)returnERROR;q=p->next; p->next= q->next;e=q->data; free(q); returnOK; } 算法的时间复杂度为O(n)P(i-1)qq->next
第33页：3.2.2单链表的一维数组表示
3.2.2单链表的一维数组表示 #defineMAXSIZE1000//链表的最大长度 typedefstruct{ ElemTypeintdata; cur; } Component,SLinkList[MAXSIZE]; 适合不便设“指针”的高级程序设计语言中使用链表结构 数组的第0号元素可看成是头结点，其指针指向第一个结点 需要预先分配一个较大的空间，但插入、删除操作不需移动元素
第34页：静态链表示例
实例：静态链表示例1002ZHAO123QIAN34SUN45LI56ZHOU67WU78ZHENG80WANG91012ZHAO3QIAN4SUN9LI6ZHOU8WU8ZHENG0WANG5SHI线性表：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)在LI后插入SHI、删除ZHENG012345678910插入SHI修改后12ZHAO3QIAN4SUN9LI6ZHOU7WU8ZHENG0WANG5SHI修改前
第35页：3.2循环链表与特点
3.2循环链表与特点
最后一个结点的指针指向头结点，整个链形成一个环
可以从任何一个结点出发找到其他点
头指针作为循环判断条件（p->next=head）
两个线性表合并时，一个表的表尾和另一个表的表头连接非空表H空表H
第36页：3.3双向链表
3.3双向链表
目的：克服单链表的单向寻查的缺点
有两个指针域：一个指向直接后继，另一个指向直接前驱L空表非空表LABC前驱指针数据元素后继指针结点
第37页：3.3.1双向链表的C描述
3.3.1双向链表的C描述 TypedefstructDuLNode{ ElemTypedata; StructDuLNode*prior; StructDuLNode*next; } DuLNode,*DuLinkList; 若d为指向某一结点的指针，则有d->next->prior=d->prior->next=d 插入和删除操作需要同时修改两个方向上的指针
第38页：3.3.2双向链表的插入操作
3.3.2双向链表的插入操作 StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee){if(!(p=GetElemP_Dul(L,i)))//在L中确定第i个元素的位置指针 returnERROR; 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 } sp
第39页：3.3.3双向链表的删除操作
3.3.3双向链表的删除操作 StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){e =p->data; p->prior->next =p->next; p->next->prior=p->prior; free(p); returnOK } ep
第40页：3.4带头结点的线性链表定义
3.4带头结点的线性链表定义
链表尽管在插入、删除时不需要移动元素
但在求链表长度时不如顺序存储结构
typedefstructLnode{typedefstruct{ElemTypedata;StructLnode*next;Linkhead,tail;intlen;
}*Link,*position;}LinkList;
基本操作见P37-38
存储头结点和最后一个结点的指针，操作方便
记录线性表数据元素的个数
第41页：带头结点线性链表的基本操作
带头结点的线性链表基本操作见P37-38
StatusMakeNode(Link&p,ElemTypee);//分配由p指向的值为e的结点，并返回OK，否则返回ERROR
StatusInitList(LinkList&L);//构造一个空的线性链表
StatusDestroyList(LinkList&L);//销毁线性链表L
StatusInsFirst(Linkh,Links);//h为指向线性链表的头结点，将s所指的结点插入在第一个结点之前
StatusAppend(LinkList&L,Links);//将s所指的一串结点连接在线性链表L的最后一个结点
StatusRemove(LinkList&L,Link&q);//删除线性链表L的尾结点,并以q返回
Status LocatePos(LinkList L, inti, Link&p);//返回p指示线性链表L中第I个结点的位置并返回OK，否则i值不合法时返回ERROR
………………………………..
第42页：算法2.20带头结点单链表插入
算法2.20带头结点的单链线性表的插入StatusListInsert_L(LinkList&L,inti,ElemTypee){ if(!LocatePos(L,i-1,h))returnERROR;//h为L的第i-1个结点，也是从第i个结点开始链表的头结点 if( !MakeNode(s,e))returnERROR;InsFirst(h,s)；//将s插入以h（第i-1个结点）为头结点线性表的第1个结点之前 } hsi-1i
第43页：算法2.21两非递减链表归并
算法2.21两非递减线性链表归并成非递减表
StatusMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){
if(!InitList(Lc))returnERROR;//初始化
ha=GetHead(La);hb=GetHead(Lb);//获得指向线性表的头结点
pa=NextPos(ha);pb=NextPos(hb);//指向各自的第1个结点
while(!Empty(La)&&!(Empty(Lb)){//La,Lb均非空a=GetCurElem(pa);b=GetCurElem(pb);//a,b为两表当前元素if((*compare)(a,b)<=0{//比较a,b大小，a<=bDelFirst(ha,q);Append(Lc,q);pa=NextPos(La,pa); }//删除ha指向链表的头结点并返回给q,然后追加到Lc表后面，La结点后移else{
第44页：算法2.21续：剩余结点链接
else{DelFirst(hb,q);Append(Lc,q);pb=NextPos(Lb,pb);}
}//while
if(!Empty(La))Append(Lc,pa);//链接La剩余结点
elseAppend(Lc,pb);//链接Lb剩余结点
freeNode(ha);freeNode(hb);//释放La,Lb的头结点
returnOK;
}//La,Lb归并为Lc,均为非递减
第45页：3.5链式存储结构的特点
3.5链式存储结构的特点
优点：
插入、删除元素时不需要移动元素
缺点：
逻辑上相邻，物理位置不一定相邻
不能随机存取表中元素，需要依次查找
求线性表的长度时不如顺序存储结构方便，需要逐个结点搜索计算，或设置带头结点的线性链表
第46页：第四节一元多项式的表示及相加
第四节一元多项式的表示及相加
第47页：4.1一元多项式及其线性表表示
4.1一元多项式Pn(x)及其操作
一个一元多项式Pn(x)P(x)ppxpx2...pxnn012n
n+1个系数，用线性表P来表示P= (p0,p1,p2, …,pn)
另一个一元多项式Qm(x)Q= (q0,q1,q2, …,qm)
假设m<n,执行Rn(x)=Pn(x)+ Qm(x)操作时，可用线性表R表示R=(p0+q0,p1+q1,…,pm+qm,pm+1,…,pn)
可以利用顺序存储结构定义P,Q,R
第48页：稀疏多项式的存储问题
问题：当多项式次数很高且变化较大时，最大长度难以确定，很难用顺序存储结构表示，例如S(x)13x100002x20000
要用长度为20001的线性表来表示，但只有三个非零元素，浪费内存空间
可以采用存储系数项和指数项的方法节省存储空间，对如下一元m次多项式meee...px122mPn(x)p1xpx
可以采用一个长度为m的每个元素有两个数据项的线性表表示（(p1,e1),(p2,e2),…,(pm,em))
该线性表可以用顺序存储结构和链式存储结构来表示，前者适合运算后不改变多项式的系数和指数的情况，否则采用后者
第49页：4.2抽象数据类型一元多项式的定义
4.2抽象数据类型一元多项式的定义
}ADTPolynomial
ADTPolynomial{
数据对象：D={ai|aiElemset,i=1,2,…,m,m0Elemset中每个元素包含系数实数和指数整数}
数据关系：R={<ai-1,ai>|ai,ai+1D,且ai-1的指数小于ai的指数,i=2,…,n}
基本操作：
CreatePolyn(&P,m)//输入m项的系数和指数，建立一元多项式
DestroyPolyn(&p)//消毁一元多项式
PolynLength(P)//返回一元多项式P中的项数
AddPolyn(&Pa,&Pb)//多项式相加
SubtractPolyn(&Pa,&Pb)//多项式相减，并销毁Pb
…………
第50页：4.3一元多项式ADT的实现
4.3抽象数据类型Polynomial的实现
typedefstruct{Floatcoef;//系数Intexpn;//指数
}term,ElemType;
typedefLinkListpolynomial;//用带表头结点的有序链表表示多项式
基本操作：CreatPolyn();//创建PolynLength();//长度DestroyPolyn();//销毁AddPolyn();//相加SubtractPolyn();//相减MultiPolyn();//相乘
第51页：算法2.22建立有序链表P
算法2.22建立有序链表P
voidCreatPolyn(Polynomial&P,intm){
InitList(P);h=GetHead(P);
e.coef=0.0;e.expn=-1;SetCurElem(h,e);
//设置表头数据
for(i=1; i<=m;++i){//依次输入m个非零项Scanf(e.coef,e.expn;)if(!LocateElem(P,e,q,(*cmp))){//当前P中不存在该项的指数if(MakeNode(s,e))InsFirst(q,s);//生成结点并插入}
}
}//输入m项的系数和指数，建立表示一元多项式的有序链表P
第52页：算法2.23多项式相加
VoidAddPolyn(polynomial&Pa,polynomial&Pb){
ha=GetHead(Pa);hb= GetHead(Pb);//获得指向线性表的头结点
qa=NextPos(ha);qb=NextPos(hb);//指向各自的第1个结点
while(!Empty(Pa)&&!(Empty(Pb)){//Pa,Pb均非空
a=GetCurElem(qa);b=GetCurElem(qb);//a,b为两表当前元素
switch(*cmp(a,b)){
case–1://Pa当前指数小，Pa指针往后移
ha=qa;qa=NextPos(Pa,qa);break;
case0://Pa与Pb当前指数相等，相加
Sum=a.coef+b.coef;
if(sum!=0.0){//不为零时修改
SetCurElem(qa,sum);ha=qa;}算法2.23多项式相加
第53页：算法2.23续：指数比较处理
续算法2.23
else{//为零时删除
DelFirst(ha,qa);FreeNode(qa);}
DelFirst(hb,qb);FreeNode(qb);qb=NextPos(Pb,hb);//删除Pb的当前结点，并移向下一个结点
qa=NextPos(Pa,ha);break;//Pa结点后移
case1://Pb当前指数小，Pb当前结点插入Pa
DelFirst(hb,qb);InsFirst(ha,qb);//删除Pb当前结点，将Pb结点内容插入Pa
qb=NextPos(Pb,hb);//Pb往后一个结点移
}
}
if(!Empty(Pb))Append(Pa,qb);//链接Pb剩余结点
FreeNode(hb);//释放Pb的头结点
}//求Pa=Pa+Pb
第54页：本章重点
本章重点
线性表的表示形式：顺序、链式
链式表示的各种形式
两种形式的优缺点
存储结构
操作方法：合并、插入、删除
了解一元多项式表示与实现，如何节省空间
第55页：习题（一）
习题：
1、在一个长度为n的线性链表中第i个元素（1in）之前插入一个元素时，需向后移动n-i+1个元素。
2、在一个长度为n的线性链表中删除第i个元素（1in）时，需向前移动n-i个元素。
3、单链表是线性表的链式存储结构。
4、在一个双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。
5、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=p->next和p->next=s的操作。
6、在单链表中，插入或删除一个结点元素时，仅需要修改指针而不需要移动元素。
第56页：习题（二）
7、非空的循环单链表head的尾结点（有p所指向）满足条件p->next=head。
8、在一个具有n个结点的有序单链表中，插入一个新结点并仍然有序的时间复杂度为O(n)。
9、给定有n个元素的向量，建立一个有序单链表的时间复杂度是O(n2)。
10、有一个单链表（不同结点的数据域可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。
11、已知一个单链表，编写一个函数将该单链表复制一个拷贝。习题：