《数据结构》课件第2章 线性表

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,2,章 线性表,学习要点,:,了解线性表的逻辑结构特性,熟练掌握线性表的,顺序存储,结构和,链式存储,结构的描述方法,熟练掌握线性表在这两种存储结构上实现的基本操作,查找、插入和删除,能够从时间和空间复杂度的角度综合比较线性表的两种存储结构的不同特点及其适用场合,线性表,是一种最简单的,线性结构,。,线性结构,是,一个数据元素的,有序,(,次序,),关系,存在,唯一,的一个“,第一个,”的数据元素；,存在,唯一,的一个“,最后一个,”的数据元素；,除第一个数据元素外，均有,唯一,的,前驱,；,除最后一个数据元素外，均有,唯一,的,后继,。,2.1,线性表的类型定义,线性表,是最常用而且最简单的一种数据结构。,定义：线性表是,n,个数据元素的,有限序列,。记为：,(,a,1, .,a,i,-1,a,i,a,i,+1, .,a,n,),26,个字母表,：,(A,，,B,，,C,，,，,Z),是一个线性表,例如：,某校近,4,年计算机拥有量,：,(,120,，,340,，,510,，,720),记录,文件,特征：,元素个数,n,表长度,；,n,=0,空表,1,i,n,时,a,i,的直接,前驱,是,a,i,-1,，,a,1,无直接前驱,a,i,的直接,后继,是,a,i,+1,，,a,n,无直接后继,元素,同构,，且不能出现缺项,抽象数据类型,线性表,的定义如下：,ADT List ,数据对象,：,D,a,i,|,a,i,ElemSet,i,=1,2,.,n,n,0 ,称,n,为线性表的,表长,;,称,n,=0,时的线性表为,空表,。,数据关系：,R1,|,a,i,-1,a,i,D,i,=2,.,n,设线性表为,(,a,1,，,a,2, . . .,，,a,i,，,. . .,，,a,n,),称,i,为,a,i,在线性表中的,位序,。,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作, ADT List,初始化操作：,InitList( &L ),操作结果：,构造一个空的线性表,L,。,结构撤销操作：,引用型操作：,ListEmpty( L ),ListLength( L ),PriorElem( L, cur_e, &pre_e ),NextElem( L, cur_e, &next_e ),GetElem( L, i, &e ),LocateElem( L, e, compare( ) ),ListTraverse(L, visit( ),DestroyList( &L ),初始条件：,操作结果：,线性表,L,已存在。,销毁线性表,L,。,加工型操作：,ClearList( &L ),PutElem( &L, i, e ),改变数据元素的值,初始条件：,线性表,L,已存在，且,1iLengthList(L),操作结果：,L,中第,i,个元素赋值为,e,。,ListInsert( &L, i, e ),ListDelete(&L, i, &e),例,2-1:,假设,:,有两个,集合,A,和,B,分别用两个线性表,LA,和,LB,表示，即：线性表中的数据元素即为集合中的成员。现要求一个,新的集合,A,=AB,。,GetElem(Lb, i, e),; /,取,Lb,中第,i,个数据元素赋给,e,if (!,LocateElem(La, e, equal( ),),ListInsert(La, +La_len, e),;,/ La,中不存在和,e,相同的数据元素，则插入之,La_len =,ListLength(La),; /,求线性表的长度,Lb_len =,ListLength(Lb),;,for (i = 1; i = Lb_len; i+) ,/for, / union,void union(List &La, List Lb) ,分析：操作步骤：,从线性表,LB,中依次取出每个数据元素,;,依值在线性表,LA,中进行查访,;,若不存在，则插入之。,GetElem(LB, i),e,LocateElem(LA, e, equal( ),ListInsert(LA, n+1, e),( n,表示线性表,LA,当前长度,),例,2-2:,已知一个非纯集合,B,，试构造一个纯集合,A,，使,A,中只包含,B,中所有值各不相同的数据元素。,分析：算法的策略应该和例,2-1,基本相同,差别仅在于集合,A,的,初始状态是“空集”,。,集合,B,集合,A,void union(List &La, List Lb) ,La_len=ListLength(La); Lb_len=ListLength(Lb);, / union,GetElem(Lb, i, e); /,取,Lb,中第,i,个数据元素赋给,e,if (!LocateElem(La, e, equal( ) ),ListInsert(La, +La_len, e);,/ La,中不存在和,e,相同的数据元素，则插入之,for (i = 1; i = Lb_len; i+) ,InitList(La); /,构造,(,空的,),线性表,LA,思考,：改变结构，以,有序表,表示集合。则算法有什么不同？,例如：集合,B,: (,2,，,3,，,3,，,5,，,6,，,6,，,6,，,8,，,12),对构造集合,A,而言，数据元素,两两不同,，且依值,从小至大,的顺序插入。,void purge(List &La, List Lb) ,InitList(LA); La_len = ListLength(La);,Lb_len =ListLength(Lb); /,求线性表的长度,for (i = 1; i = Lb_len; i+) , / purge,GetElem(Lb, i, e); /,取,Lb,中第,i,个数据元素赋给,e,if,(,),ListInsert(La, +La_len, e);,en = e; /,记录刚插入的元素, / La,中不存在和,e,相同的数据元素，则插入之,ListEmpty(La)|!equal(en, e),例,2-3:,（,P20,，例,2-2,）,归并两个“数据元素按值非递减有序排列”的有序表,La,和,Lb,，求得有序表,Lc,也具有同样特性。,设,La = (,a,1, ,a,i, ,a,n,), Lb = (,b,1, ,b,j, ,b,m,),Lc = (,c,1, ,c,k, ,c,m+n,),且已由,(,a,1, ,a,i,-1,),和,(,b,1, ,b,j,-1,),归并得,(,c,1, ,c,k,-1,),则,k,= 1, 2, ,m,+,n,基本操作：,初始化,Lc,为空表；,分别从,La,和,Lb,中,取得当前元素,a,i,和,b,j,；,若,a,i,b,j,，则将,a,i,插入,到,Lc,中，否则将,b,j,插入到,Lc,中；,重复,2,和,3,两步,直至,La,或,Lb,中元素被取完为止；,将,La,表或,Lb,表中剩余元素,复制插入,到,Lc,表中。,/ La,和,Lb,均不空，,i,=,j,= 1,k,= 0,GetElem(La, i, a,i,);,GetElem(Lb, j, b,j,);,if (a,i,= b,j,) /,将,a,i,插入到,Lc,中,ListInsert(Lc, +k, a,i,); +i; ,else /,将,b,j,插入到,Lc,中,ListInsert(Lc, +k, b,j,); +j; ,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); /,构造空的线性表,Lc,i = j = 1; k = 0;,La_len = ListLength(La);,Lb_len = ListLength(Lb);,while (i = La_len) /,当,La,不空时,GetElem(La, i+, a,i,);,ListInsert(Lc, +k, a,i,);,/,插入,La,表中剩余元素,while (j = Lb_len) /,当,Lb,不空时,GetElem(Lb, j+, b,j,);,ListInsert(Lc, +k, b,j,);,/,插入,Lb,表中剩余元素,定义：,用一组,地址连续,的存储单元,依次存放,线性表中的数据元素。,以,“,存储位置相邻,”,表示有序对,，则有：,LOC,(,a,i,) =,LOC,(,a,i,-1,) +,l,2.2,线性表类型的实现,顺序映像,a,1,a,2,a,i,-1,a,i,a,n,线性表的起始地址,称作线性表的,基地址,LOC,(,a,i,) =,LOC,(,a,1,),+ (,i,-1,),l,基地址,一个数据元素所占,存储量,特点：,实现,逻辑上相邻,物理地址相邻,实现,随机存取,实现：,可用,C,语言的一维数组实现,typedef struct , SqList; /,顺序表,#define LIST_INIT_SIZE 80,/,线性表存储空间的初始分配量,#define LISTINCREMENT 10,/,线性表存储空间的分配增量,ElemType,*elem,;,/,存储空间基址,int,length,; /,当前长度,int,listsize,; /,当前分配的存储容量,/ (,以,sizeof(ElemType),为单位,),数组指针,线性表的基本操作在顺序表中的实现,结构初始化：,Status,InitList_Sq( SqList& L ),/,构造一个空的线性表, / InitList_Sq,算法时间复杂度：,O,(1),线性阶,L.elem = (ElemType*) malloc (LIST_,INIT_SIZE,sizeof (ElemType);,if (!L.elem) exit(OVERFLOW); /,存储分配失败,L.length = 0; /,空表长度为,0,L.listsize = LIST_INIT_SIZE; /,初始存储容量,return OK;,查找：,例如：有一个,顺序表,如下,23 75 41 38 54 62 17,L.elem,L.length,L.listsize,e =,38,p,p,p,p,p,i,1,2,3,4,1,8,50,p,可见，基本操作是：将顺序表中的元素逐个和给定值,e,相比较。,int LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType) ,/,在顺序表中查询第一个满足判定条件的数据元素，,/ 若存在，则返回它的位序，否则返回 0, / LocateElem_Sq,O,( ListLength(L) ),算法的,时间复杂度,为：,i = 1;,/ i,的初值为第,1,元素的,位序,(,注意：不是数组下标值！,),p = L.elem;,/ p,的初值为第,1,元素的存储位置,while,(i = L.length &,!(*compare)(*p+, e),+i;,if (i = L.length) return i;,else return 0;,(*compare)(*p+, e),插入元素：,分析：,插入元素时，线性表的,逻辑结构,发生什么变化,？,(,a,1, ,a,i,-1,a,i, ,a,n,),改变为,(,a,1, ,a,i,-1,e,a,i, ,a,n,),a,1,a,2,a,i,-1,a,i,a,n,a,1,a,2,a,i,-1,a,i,e,a,n, ,表的长度增加,Status ListInsert_Sq(SqList &L, int i, ElemType e) ,/,在顺序表,L,的第,i,个元素之前插入新的元素,e,/ i,的合法范围为,1,iL.length+1, / ListInsert_Sq,算法时间复杂度,为,:,O,( ListLength(L) ),q = / q,指示插入位置,for (p = -p),*(p+1) = *p; /,插入位置及之后的元素右移,*,q = e; /,插入,e,+L.length; /,表长增,1,return OK;,元素右移,插入元素算法时间复杂度的进一步讨论：,考虑移动元素的,平均情况,:,假设在第,i,个元素之前插入的概率为 ，则在长度,为,n,的线性表中插入一个元素所需,移动元素次数的期望值,为：,若假定在线性表中任何一个位置上进行,插入的概率,p,i,都是,相等,的，则,移动元素的期望值,为：,T,(,n,)=,O,(,n,),O,( ListLength(L) ),if (L.length = L.listsize) ,/,当前存储空间已满，增加分配,newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);,if (!newbase) exit(OVERFLOW);,/,存储分配失败,L.elem = newbase; /,新基址,L.listsize += LISTINCREMENT; /,增加存储容量,if (i L.length+1) return ERROR;,/,插入位置不合法,例如：,ListInsert_Sq(L, 5, 66),21 18 30 75 42 56 87,21 18 30 75,L.length-1,0,p,p,p,q,87,56,42,66,q = / q,指示插入位置,for (p = -p),*(p+1) = *p;,p,删除元素：,分析：,删除元素时，线性表的,逻辑结构,发生什么变化,？,(,a,1, ,a,i,-1,a,i,a,i,+1, ,a,n,),改变为,(,a,1, ,a,i,-1,a,i,+1, ,a,n,),a,i,+1,a,n, ,表的长度减少,a,1,a,2,a,i,-1,a,i,a,i,+1,a,n,a,1,a,2,a,i,-1,Status ListDelete_Sq (SqList &L, int i, ElemType &e) , / ListDelete_Sq,for (+p; p = q; +p) *(p-1) = *p;,/,被删除元素之后的元素左移,-L.length; /,表长减,1,return OK;,算法时间复杂度,为,:,O,( ListLength(L),p = / p,为被删除元素的位置,e = *p; /,被删除元素的值赋给,e,q = L.elem+L.length-1; /,表尾元素的位置,if (i L.length) return ERROR;,/,删除位置不合法,元素左移,删除元素算法时间复杂度的进一步讨论：,考虑移动元素的,平均情况,:,假设删除第,i,个元素的概率为 ，则在长度为,n,的线性表中,删除一个元素,所需,移动元素次数的期望值,为：,若假定在线性表中任何一个位置上进行删除的,概率,都是,相等,的，则,移动元素的期望值,为：,T,(,n,)=,O,(,n,),例如：,ListDelete_Sq(L, 5, e),21 18 30 75 42 56 87,21 18 30 75,L.length-1,0,p,p,p,q,87,56,p = ,q = L.elem+L.length-1;,for (+p; p next; j = 1;,/,p,指向第一个结点，,j,为计数器,while (p ,/,顺指针向后查找，直到,p,指向第,i,个元素,/,或,p,为空,if ( !p | ji ),return ERROR; /,第,i,个元素不存在,e = p-data; /,取得第,i,个元素,return OK;,插入数据元素,ListInsert(&L, i, e),：,将有序对,改变为,和,可见，在链表中插入结点,只需要修改指针,。但同时，若要在第,i,个结点之前插入元素，修改的是第,i,-1,个结点的指针。,因此，在单链表中第,i,个结点之前进行插入的基本操作为：,找到线性表中第,i,-1,个结点，然后,修改其指向后继,的指针,。,a,i-1,e,a,i,a,i-1,?,Status ListInsert_L(LinkList L, int i, ElemType e) ,/ L,为带头结点的单链表的头指针，本算法,/,在链表中第,i,个结点之前插入新的元素,e, / LinstInsert_L,算法的,时间复杂度,为,:,O,(,n,),/,修改指针,p = L; j = 0;,while (p & j next; +j; ,/,寻找第,i-1,个结点,if (!p | j i-1),return ERROR;,/,i,大于表长或者小于,1,s = (LinkList) malloc ( sizeof (LNode);,/,生成新结点,s-data = e;,s-next = p-next; p-next = s;,/,插入,return OK;,e,a,i-1,a,i,a,i-1,s,p,删除数据元素,ListDelete(&L, i, e),：,将有序对,和,改变为,在单链表中删除第,i,个结点的基本操作为,:,找到链表中第,i,-1,个结点,，,修改其,指向后继,的指针,。,a,i-1,a,i,a,i+1,a,i-1,a,i-1,a,i,a,i+1,a,i-1,q = p-next; p-next = q-next;,e = q-data;,free(q);,p,q,?,Status ListDelete_L(LinkList L, int i, ElemType &e) ,/,删除以,L,为头指针,(,带头结点,),的单链表中第,i,个结点, / ListDelete_L,算法的,时间复杂度,为,:,O,(,n,),p = L; j = 0;,while (p-next ,/,寻找第,i,个结点，并令,p,指向其前趋,if (!(p-next) | j i-1),return ERROR; /,删除位置不合理,q = p-next; p-next = q-next;,/,删除并释放结点,e = q-data;,free(q);,return OK;,重置线性表为空表,ClearList(&L),：,void ClearList(&L) ,/,将单链表重新置为一个空表,while (L-next) ,p=L-next; L-next=p-next;, / ClearList,free(p);,算法,时间复杂度,：,O,(,n,),注意,：操作结束后，只剩一个头结点，且它的指针域为空！,生成含,n,个数据元素的链表,CreateList(&L,n,),：,例如：逆位序输入,n,个数据元素的值，建立带头结点的单链表。,操作步骤：,1.,建立一个“空表”；,2.,输入数据元素,a,n,，建立结点并插入；,3.,输入数据元素,a,n,-1,，建立结点并插入；,4.,依次类推，直至输入,a,1,为止。,a,n,a,n,a,n,-1,a,n,a,n,-1,a,n,-2,.,void CreateList_L(LinkList &L, int n) ,/,逆序输入,n,个数据元素，建立带头结点的单链表, / CreateList_L,算法的,时间复杂度,为,:,O,(,n,),L = (LinkList) malloc (sizeof (LNode);,L-next = NULL;,/,先建立一个带头结点的单链表,for (i = n; i 0; -i) ,p = (LinkList) malloc (sizeof (LNode);,scanf( /,输入元素值,p-next = L-next; L-next = p;,/,插入,比较：例,2-1,、,2-2,、,2-3,中的算法，当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？,void union(List &La, List Lb) ,La_len = ListLength(La); Lb_len =ListLength(Lb);,for (i = 1; i = Lb_len; i+) ,GetElem,(Lb, i, ,if (!,LocateElem,(La, e, equal( ),ListInsert,(La, +La_len, e);,/for, / union,控制结构：,基本操作：,for,循环,GetElem, LocateElem,和,ListInsert,当以,顺序映像,实现抽象数据类型线性表时为,:,O( ListLength(La),ListLength(Lb) ),当以,链式映像,实现抽象数据类型线性表时为,:,O( ListLength(La),ListLength(Lb) ),例,2-1,算法时间复杂度,void purge(List &La, List Lb) ,InitList(LA),;,La_len = ListLength(La); Lb_len =ListLength(Lb);,for (i = 1; i = Lb_len; i+) ,GetElem,(Lb, i, ,if (ListEmpty(La) |,!equal (en, e),ListInsert,(La, +La_len, e); en = e; ,/for, / purge,控制结构：,基本操作：,for,循环,GetElem,和,ListInsert,当以,顺序映像,实现抽象数据类型线性表时为,:,O( ListLength(Lb) ),当以,链式映像,实现抽象数据类型线性表时为,:,O( ListLength(Lb),例,2-2,算法时间复杂度,void MergeList(List La, List Lb, List &Lc) ,InitList(Lc); i = j = 1; k = 0;,La_len = ListLength(La); Lb_len = ListLength(Lb);,while (i = La_len) & (j = Lb_len) ,GetElem,(La, i, &a,i,);,GetElem,(Lb, j, &b,j,);,if (a,i,next = p-next; p-next = s;,s-next-prior = s; s-prior = p;,p,s,a,i-1,a,i,插入：,a,i-1,删除：,a,i,a,i+1,p-next = p-next-next;,p-next-prior = p;,p,a,i-1,本章小结,线性表的逻辑结构特性是数据元素之间存在着线性关系,顺序存储结构,链式存储结构,两类存储结构的描述方法，以及线性表的各种基本操作的实现。,从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,课后作业,P15: 2.8,、,2.9(2),