《第二章线性表.ppt》由会员分享，可在线阅读，更多相关《第二章线性表.ppt（78页珍藏版）》请在三一办公上搜索。
1、第二章 线性表,第二章 线性表2.1 线性表概念及基本操作2.2 线性表的顺序存储和实现2.3 线性表的链式存储和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表2.4 一元多项式的表示及相加,线性表是n 个类型相同数据元素的有限序列，通常记作（a1,a2,a3,an）。,2.1 线性表的类型定义,例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,E Z）。例3、某单位的电话号码簿。,一 线性表的逻辑结构,电话号码簿是数据元素（记录）的有限序列，每一数据元素包括两个数据项，一个是用户姓名，一个是对应的电话号码。大量记录的线性表为文件
2、,说明：设 A=（a1,a2,.,ai-1,ai,ai+1,an）是一线性表1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2）在表中 ai-1 领先于ai，ai 领先于ai+1，称ai-1 是ai 的直接前趋，ai+1 是ai 的直接后继；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；5）ai是线性表的第i 个元素，称i 为数据元素ai 的序号，每一个元素在线性表中的位置，仅取决于它的
3、序号；,2.1 线性表的类型定义,ADT List 数据对象：D=ai|aiElemSet,i=1,2,3,n,n=0 数据关系：R=|ai-1,ai D,i=2,3,.n 基本操作：InitList(&L)操作结果：建立空的线性表L；DetroyList(&L)初始条件：线性表L已存在；操作结果：销毁线性表L。ClearList(&L)初始条件：线性表L已存在，操作结果：重新将其置成空表；,二 线性表的抽象数据类型定义,2.1 线性表的类型定义,ListEmpty(L)初始条件：线性表L已存在；操作结果：若线性表L为空表，返回TRUE，否则返回ALSE；ListLength(L)初始条件：线
4、性表L已存在；操作结果：返回L中数据元素的个数。GetElem(L,i,操作结果：将线性表L中第i 个元素赋值给 e；LocateElem(L,e,compare()初始条件：线性表L已经存在，compare()是数据元素判定函数 操作结果：返回L中第一个与元素e满足关系compare()数据元 素元素位置，若表中不存在这样的元素，则返回0；,2.1 线性表的类型定义,2.1 线性表的概念,PriorElem(L,cur_e,ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1=i=ListLength(L)操作结果：删除线性表L的第i个元素，并用e返回，L的长度减1；AD
5、T list,如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？,？,2.2 线性表的顺序存储和实现 一 线性表的顺序存储结构顺序表 1 线性表的顺序存储结构 2 顺序表的类型定义 二 顺序表的基本操作算法 三 利用基本操作实现线性表的其他操作,为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；,2.2 线性表的顺序存储和实现,在计算机内部可以采用不同的方式来存储一个线性表，其中最简单的方式就是本节要讲的线性表的顺序存储结构。,线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。,线性表（a1,a2,a3,.an）,2.
6、2 线性表的顺序存储和实现,一 线性表的顺序存储结构顺序表,1 线性表的顺序存储结构,1000,1001,1000+i-1,1000+i,1000+n,高级语言中反映线性表存储顺序的常用方法就是数组,存储地址,内存状态,2.2 线性表的顺序存储和实现,顺序表的类型定义#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量typedef structElemType*elem;/线性表存储空间基址int length;/当前线性表长度int listsize;/当前分配的线性表存储空间大小/（以s
7、izeof(ElemType)为单位）SqList;,SqList：类型名，SqList 类型的变量是结构变量，它的三个域分别是：*elem：存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配；length：存放线性表的表长；listsize：用于存放当前分配（存放线性表元素）的存储空间的大小。,2.2 线性表的顺序存储和实现,顺序表图示,存放线性表元素 的一维数组,设 A=（a1,a2,a3,.an）是一线性表，L是SqList 类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：,2.2 线性表的顺序存储和实现,二、顺序表的基本操作算法 现在，我们已为线性表
8、设计好了一种存储结构，下面将看到用这种存储方式存储线性表时，线性表的各种基本操作算法。,1）初始化操作 InitList_Sq(SqList/InitList_Sq,2.2 线性表的顺序存储和实现,L.length,L.listsize,L.elem,0LIST_INIT_SIZE,2 插入操作 ListInsert_Sq(,2.2 线性表的顺序存储和实现,插入操作示意图：,线性表插入算法：Status ListInsert_Sq(SqList/ListInsert,2.2 线性表的顺序存储和实现,一般情况下，在第i（1 in+1）个元素之前插入一个元素时，需将第n至第i个元素向后移动一个位置
9、，共n-i+1个元素。算法分析：基本语句：*(p+1)=*p，问题规模n 时间复杂度T（n）=O（n）在第i个元素之前插入一个元素所需移动元素次数的平均次数（期望值）：,2.2 线性表的顺序存储和实现,2.2 线性表的顺序存储和实现,3 删除操作 ListDelete_sq(SqList&L,int i,ElemType&e)功能：删除顺序表L的第i个元素，并用e返回删除操作图示,n-1,n-2,ListDelete_sq(SqList ListDelete 时间复杂度 T（n）=O（n）,2.2 线性表的顺序存储和实现,2.2 线性表的顺序存储和实现,例：将两个有序线性表归并成一个有序线性表
10、；设线性表A、B分别用La、Lb 的两个顺序表存储，两顺序表中元素按非递减顺序排列，编写算法：将La、Lb归并得到顺序表Lc,Lc中的元素也按值非递减顺序排列。,三、利用基本操作实现线性表的其他操作 现在来回答2.1中提到的问题,如何利用已有基本操作实现线性表的其他操作。请看下例。,2.2 线性表的顺序存储和实现,顺序表的归并图示（算法2.7a),0199,2356889,100,建空表Lc,0,La,Lb归并,7,2.2 线性表的顺序存储和实现,Void MergeList_Sq(SqList La,SqList Lb,SqList,2.2 线性表的顺序存储和实现,while(i=La_le
11、n)GetElem_Sq(La,.i+,ai);ListInsert_Sq(Lc,+k,ai);while(j=Lb_len)GetElem_Sq(Lb,.j+,bj);ListInsert_Sq(Lc,+k,bj);/MergeList_Sq 算法2.7,2.2 线性表的顺序存储和实现,顺序表是线性表最简单的一种存储结构,2.3 线性表的链式存储和实现,线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。,用顺序表存储线性表时，线性表的插入删除操作要移动大量的元素，平
12、均的来看要移动线性表中一半的元素，因此对于应用经常要进行进行插入，删除操作的线性表，一般不使用顺序表存储，下面我们来看线性表的另一种存储结构链式存储结构。,2.3 线性表的链式存储和实现 2.3.1 线性链表 一 线性链表的概念 二 线性链表的基本操作算法 三 静态链表 四 线性链表的其它操作 2.3.2 循环链表 2.3.3 双向链表 一 双向链表的概念 二 双向链表的基本操作算法,一 线性链表的概念1 线性链表,2.3.1 线性链表,用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。,2.3.1 线性链表,2 线性链表图示 一般来
13、说，我们并不需要写出直接后继的实际地址，为直观起见，通常用如下所示的图表示链表，其中，箭头表示相应单元中保存的是它所指向结点的存储地址。,结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；结点的数据域：结点中用于保存数据元素的部分;结点的指针域：结点中用于保存数据元素直接后继存储地址的部分;,3 线性链表有关术语,2.3.1 线性链表,存储数据元素,存储后继结点 存储地址,2.3.1 线性链表,头指针：用于存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性链表最后一个结点的指针通常是指针;头结点：线性链表的第一元素结点前面的一个附加结点，称为头结
14、点；带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为 带头结点的线性链表；,L是头指针,头结点,空指针,L,线性链表的每个结点中只有一个指针域故也称为单链表,2.3.1 线性链表,怎样在计算机上实现线性链表？,？,2.3.1 线性链表,结点变量图示,typedef struct Lnode ElemType data;Struct LNode*next;LNode,*LinkList;,LNode：结构类型名；LNode类型结构变量有两个域：data：用于存放线性表的数据元素，next：用于存放元素直接后继结点的地址；该类型结构变量用于表示线性链表中的一个结点；LinkLis
15、t：指针类型名；LinkList类型指针变量用于存放LNode类型结构变量的地址；,data next,Lnode类型 结构变量,LinkList类型 指针变量L,4 线性链表的结点类型定义,2.3.1 线性链表,以L为头指针的线性链表称为线性链表L,二 线性链表基本操作的算法 假设线性表用带头结点的线性链表L的存储。下面讨论在这种存储方式下，线性表各种基本操作的算法。当线性表用线性链表存储时，对线性表各种基本操作实际上就是对存储在内存中的线性链表进行操作。,2.3.1 线性链表,L,算法：Status InitList_L(LinkList/InitList_L,1）初始化操作InitLis
16、t_L(LinkList&L)功能：建空线性链表L参数：L为线性链表的头指针主要步骤：调用malloc()分配一结点的空间,并将其地址 赋值给L；,？,LinkList,2.3.1 线性链表,2 取元素操作 GetElem_L(LinkList L,int i,ElemType,2.3.1 线性链表,取元素操作算法：Status GetElem_L(LinkList L,int I,ElemType/GetElem_L 算法 2.8,2.3.1 线性链表,例，取第i=3个元素。,e=p-data=Sun,3 插入操作 ListInsert_L(LinkList&L,int i,ElemType
17、 e)功能：在线性链表L的第i个元素结点之前插入一个新元素结点；插入操作图示：,2.3.1 线性链表,插入前,插入后,2.3.1 线性链表,插入操作主要步骤：1）查找链表L的第 i-1个元素结点；2）为新元素建立结点；3）修改第 i-1个元素结点的指针和新元素结点指针完成插入；,ai-1,ai,生成一个数据域为e的结点。,p,e,s,data,next,3.插入运算,用C语句描述为：s=(LinkList)malloc(sizeof(LNode);s-data=e;,ai-1,ai,将数据元素x插在a和b元素之间。,p,data,next,s,用C语言描述为：s-next=p-next;p-n
18、ext=s;,2.3.1 线性链表,插入操作算法：Status ListInsert_L(LinkList/LinstInsert_L 算法 2.9,4 删除操作 ListDelete_L(LinkList&L,int i,ElemType&e)功能：在线性链表L中删除第i个元素，并且用e 返回其值,2.3.1 线性链表,删除操作主要步骤：1）查找链表的第 i-1个元素结点；2）修改第 i-1个元素结点指针，删除第i个元素结点；3)将第i个元素结点中的数据元素赋值给e;4）回收被删除结点空间；,2.3.1 线性链表,a,b,p,c,data,next,b,用C语言语句描述为：p-next=p-
19、next-next;,2.3.1 线性链表,a,b,p,c,data,next,b,步骤1：用循环找到被删除节点i的前驱 即：p=p-next;,2.3.1 线性链表,a,b,p,c,data,next,b,步骤2：将b的地址记录下来 即：q=p-next;,q,2.3.1 线性链表,a,b,p,c,data,next,b,步骤3：让p-next指向b后第一个结点即：p-next=q-next;,q,2.3.1 线性链表,a,b,p,c,data,next,b,q,步骤4：释放b结点即：free(q),2.3.1 线性链表,删除操作算法：Status ListDelete_L(LinkList
20、/LinstDelete_L 算法：2.10,2.3.1 线性链表小结,线性链表是线性表的一种链式存储结构,线性链表的特点 1 通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系；2 插入删除操作通过修改结点的指针实现；3 不能随机存取元素；,23 线性表的链式存储和实现,单线性链表的缺点之一，是无法从指定的某结点到达该结点的前趋结点，这可能会给某些应用带来一些不便，下面介绍线性表的另外两种链式存储结构 循环链表和双向链表。,1 循环链表的概念 循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点（头节点）2 循环链表图示,2.3.2 循
21、环链表,(a)非空表（b）空表,1 双向链表的概念,2.3.3 双向链表,(a)结点图示,存储数据元素,存储后继结点 的地址,存储前趋结点 的地址,双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。,typedef struct DulNode ElemType data;struct DulNode*prior;struct DulNode*next;DulNode,*DuLinkList;,双向链表的存储类型描述,2.3.3 双向链表,2 双向循环链表图示,（c）非空的双向循环链表,(b)空的双向循环链表,在双向链表中删除结点时指针变化情况,在双向链表
22、中插入一个结点时指针的变化情况,2.3.3 双向链表,3、双向链表的基本操作算法,S,2.3.3 双向链表,1）插入操作算法 Status ListInsert_DuL(DuLinkList/LinstInsert_DuL 算法2.18,2.3.3 双向链表,2）删除操作算法Status ListDelete_DuL(DuLinkList/LinstDelete_DuL 算法2.19,24 一元多项式的表示及相加（候补）,线性表是最简单常用的数据结构。本节介绍一个线性表的典型应用 一元多项式的运算。,24 一元多项式的表示及相加,它由个系数唯一确定。多项式基本运算有加法减法乘法，为了用计算机实
23、现多项式运算，可用一个由系数构成的线性表来表示一元多项式：P=(p0,p1,p2,pn)Q=(q0,q1,q2,qm)不失一般性，设mn，则两个多项式相加的结果可用线性表R表示：R=(p0+q0,p1+q1,pm+qm,pm+1,pn)显然可以对P，Q，R 采用顺序结构存储，这样一元多项式相加运算很容易实现。,P n(x)=p0+p1 x+p2 x2+pn xnQ m(x)=q0+q1 x+q2 x2+qm xm,一、一元多项式的表示 多项式的操作是表处理的典型用例。数学上,一元多项式可按升幂写成：,24 一元多项式的表示及相加,以下用非0项（系数，指数）构成的线性表表示一元多项式。用这种方式
24、表示一元多项式时，一元多项式运算经常要对线性表进行插入删除操作，所以采用线性链表存储结构它们。,然而，应用中一元多项式往往幂次很高，且有大量项的系数为零。例：S(x)=1+3 x 10000+2 x 20000 如果用系数构成的线性表表示该多项式，就要用一长度为20001的线性表表示，可表中只有三个非零项，这显然很浪费内存空间。可采用另一种方式，即用非0项（系数，指数）构成的线性表表示一元多项式，S=(1,0),(3,10000),(2,20000),24 一元多项式的表示及相加,*链表中结点指针的类型定义typedef struct LNodeElemType data;Struct LNo
25、de*next;*Link,*Position;,1）线性链表的类型定义,二 一元多项式的链式存储结构1 重新定义线性链表 一元多项式运算，将利用线性链表的基本操作实现。为了实现多项式的加减乘等运算需要重新定义线性链表和基本操作。,24 一元多项式的表示及相加,*链表的类型定义（链表表头结点的类型定义）typedef struct Link head,tail;int len;LinkList;,表头结点是一结构,24 一元多项式的表示及相加,2）新定义线性链表图示,表头结点,头结点,L是Linklist类型的结构变量,24 一元多项式的表示及相加,3）在原线性链表的基础上，增加如下的基本操作
26、：（1）取表头操作Position GetHead(LinkList L)功能：L为线性链表的表头结点，该操作返回链表的头结点指针；（2）求后继操作Position Nextpos(LinkList L,Link p)功能：p指向线性链表L的某个结点，返回p所指结点的后继的指针；（3）求前趋操作Position Prior(LinkList L,Link p)功能：p指向线性链表L的某个结点，返回p所指结点的前趋的指针；（4）取当前结点值的操作 ElemType GetCurElem(Link p)功能：p指向线性链表L的某一结点，返回p的所指结点的值；,head tail len,n,L是表
27、头结点,头结点,24 一元多项式的表示及相加,插入首结点 Status InsFirst(Link h,Link s)图示,（5）为当前结点赋值 Status SetCurElem(Link&p,ElemType e)功能：p指向线性链表L的某个结点,用e 更新p 所指结点中数据元素的值（6）插入首结点 Status InsFirst(Link h,Link s)功能：h指向线性链表L的头结点,在线性链表的第一元素结点之前插入s 所指结点；,24 一元多项式的表示及相加,（7）删除首结点 Status DelFirst(Link h,Link q)功能：h指向线性链表L的头结点,删除线性链表的
28、第一元素结点，并用q返回其指针；（8）连接链表 Status Append(LinkList&L,Link s)功能：将s所指的链表链接在线性链表L的尾部,删除首结点 Status DelFirst(Link h,Link q)图示,24 一元多项式的表示及相加,1）元素的类型定义typedef struct float coef;/存储项系数int expn;/存储项指数 ElemType;,2）一元多项式链表的类型定义typedef LinkList polynomail;/用带表头结点的线性链表表示/一元多项式，为类型重命名/是为增加算法的可读性,coef expn,2 一元多项式链式存
29、储结构为用线性链表表示一元多项式，我们要给出ElemType的类型定义,24 一元多项式的表示及相加,3）一元多项式链式存储结构图示,S是表头结点,头结点,24 一元多项式的表示及相加,例：求两多项式的和多项式 A(x)=7+3 x+9 x 8+5 x 17 B(x)=8 x+22 x 7 9 x 8,三、一元多项式的相加算法,设多项式A(x)，B(x)分别用带表头结点的线性链表Pa,Pb表示，和多项式C(x)用带表头结点的线性链表Pc表示（如下图所示,Pa Pb Pc分别是三个表的表头结点）,A(x)B(x)相加的和多项式为 C(x)=A(x)+B(x)=7+11x+22 x 7+5 x 1
30、7,一元多项式相加运算规则：指数相同的项系数相加,1 一元多项式的相加,24 一元多项式的表示及相加,和多项式链表,24 一元多项式的表示及相加,如何实现用这种线性链表表示的多项的加法运算？,5 17,24 一元多项式的表示及相加,3 一元多项式加法算法主要步骤分别对两个链表Pa、Pb进行扫描，设qa、qb 分别指向线性链表Pa、Pb的当前进行比较的某个结点，比较两个结点的指数项，有下列三种情况：qa-expn expn：qa所指结点应为和多项式中的结点；qa-expn=qb-expn：将qb所指结点的系数“加”到qa所指结点 的系数上相加；qa-expn expn：从表Pb中删除qb所指结点
31、，并将其插入到 Pa表qa所指结点之前；,2 一元多项式加法算法功能“将多项式Pb加到多项式Pa上”Pa=Pa+Pb,利用两个多项式的结点构成“和多项式”利用两个多项式的结点构成和多项式的结点,“和多项式”存储在线性链表Pa中；,24 一元多项式的表示及相加,4 一元多项式的相加算法图示,22 7,-1,7 0,11 1,5 17,Pb,Pa,24 一元多项式的表示及相加,5 一元多项式的相加算法（算法2.23）void AddPolyn(polynomial/a和b为两表中当前比较元素（接下页）,注：ha,hb分别指向pa,pb所指结点的前趋结点,续,switch(*cmp(a,b)case
32、 1:/多项式PA中当前结点的指数值小 ha=qa;qa=NextPos(Pa,qa);break;case 0:/两者的指数值相等 sum=a.Coef+b.Coef;if(sum!=0.0)/修改多项式PA中当前结点的系数值 SetCurElem(qa,sum);ha=qa;Else/删除多项式PA中当前结点 DelFirst(ha,qa);FreeNode(qa);DelFirst(hb,qb);FreeNode(qb);qb=NextPos(Pb,hb);qa=NextPos(Pa,ha);break;case1:/多项式PB中当前结点的指数值小 DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(Pb,hb);break;/switch/while if(!Empty(Pb)Append(Pa,qb);/链接Pb中剩余结点 FreeNode(hb):/释放Pb的头结点/AddPolyn,第二章结束,
