数据结构线性表PPT.ppt

第二章 线性表,线性结构的特点：在数据元素的非空有限集合中：存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继,2.1 线性表的类型定义,2.3 线性表类型的实现 链式映象,2.4 一元多项式的表示,2.2 线性表类型的实现 顺序映象,2.5 小结及习题,2.1 线性表的类型定义,定义：一个线性表是n个数据元素的有限序列,例1 英文字母表（A,B,C,Z)是一个线性表,特征：元素个数n(n0)称为表长度，n=0空表,记为（）或1in时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构（属于同一数据对象),抽象数据类型线性表的定义如下：,ADT List,数据对象：,D ai|ai ElemSet,i=1,2,.,n,n0 其中n 为线性表的表长;,数据关系：,R1|ai-1,aiD,i=2,.,n,设线性表为(a1，a2,.，ai，.，an),称 i 为 ai 在线性表中的位序。,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,ADT List,InitList(&L),操作结果：,构造一个空的线性表L。,初始化操作,结构销毁操作,DestroyList(&L),初始条件：操作结果：,线性表 L 已存在。,销毁线性表 L。,ListEmpty(L),初始条件：操作结果：,线性表L已存在。,若L为空表，则返回TRUE，否则FALSE。,（线性表判空）,引用型操作,ListLength(L),初始条件：操作结果：,线性表L已存在。,返回L中元素个数。,（求线性表的长度）,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无定义。,（求数据元素的后继）,GetElem(L,i,&e),初始条件：操作结果：,线性表L已存在，且 1iLengthList(L),用 e 返回L中第 i 个元素的值。,（求线性表中某个数据元素）,LocateElem(L,e),初始条件：操作结果：,线性表L已存在，e为给定值。,返回L中第1个与e相等的元素的位序。若这样的元素不存在，则返回值为0。,（定位函数）,ListTraverse(L,visit(),初始条件：操作结果：,线性表L已存在。Visit()为某个访问函数。,依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。,（遍历线性表）,ClearList(&L),初始条件：操作结果：,线性表L已存在。,将L重置为空表。,（线性表置空）,加工型操作,ListInsert(&L,i,e),初始条件：操作结果：,线性表L已存在，且 1iLengthList(L)+1,在L的第i个元素之前插入新的元素e，L的长度增1。,（插入数据元素）,ListDelete(&L,i,&e),初始条件：操作结果：,线性表L已存在且非空，1iLengthList(L),删除L的第i个元素，并用e返回其值，L的长度减1。,（删除数据元素）,假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合AAB。,例 2-1,要求对线性表作如下操作：扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,上述问题可演绎为：,1从线性表LB中依次察看每个数据元素;,2对其查看在线性表LA中是否存在;,3若不存在，则插入之。,GetElem(LB,i,e),LocateElem(LA,e),ListInsert(LA,+n,e),操作步骤：,GetElem(Lb,i,e);/取Lb中第i个数据元素赋给e if(!LocateElem(La,e)ListInsert(La,+laLen,e);/La中不存在和 e 相同的数据元素，则插入之,void union(List,for(i=1;i=lbLen;i+),/union,算法时间复杂度：,O(m*n),已知一个非纯集合 B，试构造一个纯集合 A，使 A 包含 B 中所有出现过的数据元素。,仍选用线性表表示集合。,例 2-2,集合 B,集合 A,从集合 B 取出物件放入集合 A且集合A中同样物件不能有两件以上,因此，算法的策略应该和例2-1相似,void purge(List/union,GetElem(Lb,i,e);/取Lb中第 i 个数据元素赋给 e if(LocateElem(La,e)=0)ListInsert(La,+La_len,e);/La中不存在和 e 相同的数据元素，则插入之,for(i=1;i=lbLen;i+),InitList(La);/构造(空的)线性表LA,算法时间复杂度：,O(m2),若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 aiai-1 或 aiai-1(i=2,3,n)，则称该线性表为有序表(Ordered List)。,试改变结构，以有序表表示集合。,例如:（2，3，3，5，6，6，6，8，12）,对集合 B 而言，值相同的数据元素必定相邻,对集合 A 而言，数据元素依值从小至大的顺序插入,因此，数据结构改变了，解决问题的策略也相应要改变。,例 2-2 已知一个非纯集合 B，试构造一个纯集合 A，使 A 包含 B 中所有出现过的数据元素。（用非递减有序的顺序表表示A、B）,void purge(List i+)/purge,GetElem(Lb,i,e);/取Lb中第i个数据元素赋给 eif(en!=e)ListInsert(La,+La_len,e);en=e;/La中不存在和 e 相同的数据元素，则插入之,算法时间复杂度：,O(m),则,归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB，求得有序表 LC 也具有同样特性。,设 La=(a1,ai,an),Lb=(b1,bj,bm)Lc=(c1,ck,cm+n)且已由(a1,ai-1)和(b1,bj-1)归并得(c1,ck-1),例 2-3,k=1,2,m+n,1初始化 LC 为空表；,基本操作：,2分别从 LA和LB中取得当前元素 ai 和 bj；,3若 aibj，则将 ai 插入到 LC 中，否则将 bj 插入到 LC 中；,4重复 2 和 3 两步，直至 LA 或 LB 中元素 被取完为止；,5将 LA 表或 LB 表中剩余元素复制插入到 LC 表中。,void MergeList(List La,List Lb,List&Lc)/本算法将非递减的有序表 La 和 Lb 归并为 Lc/merge_list,while(i=La_len)&(j=Lb_len)/La 和 Lb 均不空 while(i=La_len)/若 La 不空while(j=Lb_len)/若 Lb 不空,InitList(Lc);/构造空的线性表 Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);,/La 和 Lb 均非空，i=j=1,k=0 GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)/将 ai 插入到 Lc 中 ListInsert(Lc,+k,ai);+i;else/将 bj 插入到 Lc 中 ListInsert(Lc,+k,bj);+j;,while(i=La_len)/当La不空时 GetElem(La,i+,ai);ListInsert(Lc,+k,ai);/插入 La 表中剩余元素,while(j=Lb_len)/当Lb不空时 GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/插入 Lb 表中剩余元素,线性表类型的实现-顺序映象,2.2,2.2 线性表的顺序表示和实现,用一组地址连续的存储单元依次存储线性表的数据元素。,a9,线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。,线性表的顺序表示(图示),动态分配的一维数组来表示顺序表,以“存储位置相邻”表示有序对 即：LOC(ai)=LOC(ai-1)+L 一个数据元素所占存储量,所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai)=LOC(a1)+(i-1)L 基地址,可随机存取,顺序映象的 C 语言描述,typedef struct SqList;/也称 顺序表,#define LIST_INIT_SIZE 80/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量,int*elem;/存储空间基址,int length;/当前长度,int listsize;/当前分配的存储容量/(以sizeof(ElemType)为单位),typedef int ElemType；,ElemType*elem;/存储空间基址,线性表的基本操作在顺序表中的实现,InitList_Sq(&L)/结构初始化,LocateElem_Sq(L,e)/查找,ListInsert_Sq(&L,i,e)/插入元素,ListDelete_Sq(&L,i)/删除元素,Status InitList_Sq(SqList&L,int maxsize)/构造一个最大容量为 maxsize 的顺序表/InitList_Sq,算法时间复杂度：,O(1),L.elem=new ElemTypemaxsize;/为顺序表分配大小为 maxsize 的数组空间if(!L.elem)return ERROR;,L.length=0;L.listsize=maxsize;return OK;,顺序表的查找 例如：,e=,38,i,1,2,3,4,1,50,查找的基本操作是:将顺序表中的 元素逐个和给定 值e相比较。,查找成功，返回i值！,查找不成功，返回0！,7,8,int LocateElem_Sq(SqList L,ElemType e)/在顺序表中查询第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回 0/LocateElem_Sq,O(ListLength(L),算法的时间复杂度为：,i=1;/i 的初值为第 1 元素的位序p=L.elem;/p 的初值为第 1 元素的存储位置,while(i=L.length,if(i=L.length)return i;else return 0;,线性表操作 ListInsert_Sq(&L,i,e)的实现：,首先分析:,插入元素时，线性表的逻辑结构发生什么变化？,(a1,ai-1,ai,an)改变为,(a1,ai-1,e,ai,an),Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1/ListInsert_Sq,算法时间复杂度为:,O(ListLength(L),q=,（合法性检查、分配空间满需追加空间等）,if(L.length=L.listsize)/当前存储空间已满，增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)return ERROR;/存储分配失败 L.elem=newbase;/新基址 L.listsize+=LISTINCREMENT;/增加存储容量,if(i L.length+1)return ERROR;/插入位置不合法,线性表操作 ListDelete_Sq(&L,i,&e)的实现：,首先分析：,删除元素时，线性表的逻辑结构发生什么变化？,(a1,ai-1,ai,ai+1,an)改变为,ai+1,an,表的长度减少,(a1,ai-1,ai+1,an),Status ListDelete_Sq(SqList&L,int i,ElemType&e)/ListDelete_Sq,for(p;p q;+p)*p=*(p+1);/被删除元素之后的元素左移-L.length;/表长减1return OK;,算法时间复杂度为:,O(ListLength(L),p=/表尾元素的位置,if(i L.length)return ERROR;/删除位置不合法,L.length-1,0,87,56,p=,例如：ListDelete_Sq(L,5,e),线性表-顺序存储,优点:随机存取。,缺点:插入删除操作需移动较多 数据元素。空间浪费。,特点：以数据元素物理位置的相邻 表示逻辑关系的相邻。,2.3 线性表类型的实现-链式映象,一、单链表,二、结点和单链表的 C 语言描述,三、线性表的操作在单链表中的实现,四、其它形式的链表,用一组地址任意的存储单元存放线性表中的数据元素。,一、单链表,数据域(数据的映象)+指针域(关系的映象)=结点(数据元素的映象：表示数据元素),N个结点通过指针域组成的表 称作线性链表（单链表）,例：线性表(zhao,qian,sun,li,zhou,wu,zheng,wang),顺序存储结构：,链式存储结构：,以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。,空指针,线性表为空表时，头结点的指针域为空,typedef struct LNode ElemType data;/数据域 struct Lnode*next;/指针域 LNode,*LinkList;,二、结点和单链表的 C 语言描述,LinkList L；/L 为单链表的头指针,三、单链表操作的实现,GetElem(L,i,&e)/取第i个数据元素,ListInsert(&L,i,e)/插入数据元素,ListDelete(&L,i,&e)/删除数据元素,ClearList(&L)/重置线性表为空表,CreateList(&L,n)/生成含 n 个数据元素的链表,线性表的操作 GetElem(L,i,&e)在单链表中的实现:,j,1,2,3,i=3,因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i.,分析：单链表是一种 顺序存取 的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。,Status GetElem_L(LinkList L,int i,ElemType&e)/L是带头结点的链表的头指针，以 e 返回第 i 个元素/GetElem_L,算法时间复杂度为:,O(ListLength(L),p=L-next;j=1;/p指向第一个结点，j为计数器,while()p=p-next;+j;/顺指针向后查找，直到 p 指向第 i 个元素/或 p 为空,if()return ERROR;/第 i 个元素不存在e=p-data;/取得第 i 个元素return OK;,!p|i1,p&ji,（5）listinsert_L(Linklist L,int i,elemtype e):插入结点操作。,要求:在ai-1和ai之间插入一个数据元素e:,P指针指向结点ai-1;,P,(2)生成数据域为e的结点;s=(Linklist)malloc(sizeof(Lnode);s-data=e;,(3)修改有关指针;s-next=p-next;,P-next=s;,Status ListInsert_L(LinkList L,int i,ElemType e)/L 为带头结点的单链表的头指针，本算法/在链表中第i 个结点之前插入新的元素 e/LinstInsert_L,算法的时间复杂度为:,O(ListLength(L),p=L;j=0;while()p=p-next;+j;/寻找第 i-1 个结点if(!p|i 1)return ERROR;/i 大于表长或者小于1,p&j i-1,s=new LNode;/生成新结点s-data=e;s-next=p-next;p-next=s;/插入return OK;,线性表的操作ListDelete(&L,i,&e)在链表中的实现:,有序对 和 改变为,在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。,q=p-next;p-next=q-next;e=q-data;free(q);,p,q,操作 ClearList(&L)在链表中的实现:,void ClearList(/ClearList,free(p);,算法时间复杂度：,O(ListLength(L),L-next,如何从线性表得到单链表？,链表是一个动态的结构，它不需要预分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。,1、由表头插入：得到逆序-头插法2、由表尾插入：得到正序-尾插法,例如：逆位序输入 n 个数据元素的值，建立带头结点的单链表。,操作步骤：,一、建立一个“空表”；,二、输入数据元素an，建立结点并插入；,三、输入数据元素an-1，建立结点并插入；,an,an,an-1,四、依次类推，直至输入a1为止。,void HCreateList_L(LinkList&L,int n)/逆序输入 n 个数据元素，建立带头结点的单链表/HCreateList_L,算法的时间复杂度为:,O(n),L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的空单链表,for(i=n;i 0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(/插入,练习：写出表尾插入法建立单链表的算法。,四、其它形式的链表,1.循环链表,循环链表是另一种形式的链式存储结构。它的特 点是表中最后一个结点的指针域指向头结点。,(a)非空表,(b)空表,循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p-next是否为空，而是它们是否等于头指针。,2.双向链表,(a)非空表,(b)空表,双向链表的表示：typedef struct DuLnode ElemType data;Struct DuLnode*prior;Struct DuLnode*next;DuLnode,*DuLinklist;,双向链表的操作特点：,“查询”和单链表相同,“插入”和“删除”时需要同时 修改两个方向上的指针。,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,p,s,插入,s-prior=p-prior;p-prior=s;s-next=p;s-prior-next=s;,p,若在指针p所指结点之前插入结点,如何实现此插入算法？,s,双向链表插入结点时算法有多种，关键是不要断链：只要不先执行 p-prior=s 语句 即可。,删除,p-next=p-next-next;p-next-prior=p;,p,如何删除指针p所指结点？,p,p,p-next-next-prior=p;p-next=p-next-next;,在双向链表中删除结点b:,算法:（1）指针P指向结点b;（2）修改有关指针：p-prior-next=;p-next-prior=;free(P);,在双向链表中结点b之前插入元素X:,S,算法：（1）指针P指向结点b;（2）建立结点X：s=(duLinklist)malloc(sizeof(duLnode);s-data=x;,P,（3）修改有关指针：s-prior=p-prior;p-prior-next=s;s-next=;p-prior=;,本章小结,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。,2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。,3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,作 业,已知:线性表LA、线性表LB:数据元素按值非递减有序排列.求:线性表LC:将LA和LB归并,且数据元素仍按值有序排序.,Lc,LC,例如：LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)则 LC=(2,3,5,6,8,8,9,11,11,15,20),算法分析:,i,j,2,j,3,i,5,i,顺序表情况,