2.1线性表类型定义-第二章 线性表

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章,线性表,线性结构的,基本特征,为,:,1,集合中必存在唯一的一个,“第一元素”,；,2,集合中必存在唯一的一个,“最后元素”,；,3,除最后元素在外，均有,唯一的后继,；,4,除第一元素之外，均有,唯一的前驱,。,线性结构,是一个数据元素的,有序,(,次序,),集,线性表,是一种最简单的,线性结构,2.1,线性表的类型定义,2.3,线性表的链式表示和实现,2.4,一元多项式的表示,2.2,线性表的顺序表示和实现,2.1,线性表的类型定义,一、线性表的逻辑结构,线性表是,n,个数据元素,a1,a2,an,的有限序列，记为,(a1,a2,ai,an),其中，,ai,可以是一个数、一个字母、一串字符、一页书，甚至更复杂的信息,例如：英文字母表（,A,B,C,Z,）,在校生人数变化情况表,（,800,，,1500,，,2400,，,4100,，,，,20000,）,在稍复杂的线性表中，一个数据元素可以由若干个数据项组成，如职工花名册表,编号,姓名,性别,年龄,月收入,1,王小林,男,51,2200,2,陈红,女,47,1800,3,孙丽丽,女,35,1760,4,赵京,男,27,1650,在这种情况下，通常把数据元素称为记录，把含有大量记录的线性表称为文件。,综上所述：,线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同的特性,即属同一数据对象，相邻数据元素之间存在着序偶关系。,若将线性表记为,（,a1,ai-1,ai,ai+1,an,），则,ai-1,是,ai,的,直接前趋元素,；,ai+1,是,ai,的,直接后继元素,；,当,i=1,2,n-1,时，,ai,有且仅有一个直接后继；,当,i=2,3,，,n,时，,ai,有且仅有一个直接前趋；,即：第一个元素无前趋；最后一个元素无后继；,其它元素仅有一个直接前趋和一个直接后继。,线性表中元素的个数,n,（,n0,）定义为线性表的,长度,；,n=0,时，称为,空表,；,在非空表中的每个数据元素,ai,都有一个确定的位置，称,i,为数据元素在线性表中的,位序,。,二、抽象数据类型线性表的定义,ADT List ,数据对象,：,D, a,i,| a,i,ElemSet, i=1,2,.,n, n0 ,数据关系：,R1, | a,i-1,a,i,D, i=2,.,n ,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作, ADT,List,InitList( &L ),操作结果：,构造一个空的线性表,L,。,初始化操作,结构销毁操作,DestroyList( &L ),初始条件：,操作结果：,线性表,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( ),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, compare( ) ),初始条件：,操作结果：,线性表,L,已存在，,e,为给定值，,compare( ),是元素判定函数。,返回,L,中第,1,个,与,e,满足,关系,compare( ),的元素的位序。若这样的元素不存在，则返回值为,0,。,（定位函数）,ListTraverse(L, visit( ),初始条件：,操作结果：,线性表,L,已存在，,Visit(),为某个访问函数。,依次,对,L,的每个元素调用函数,visit( ),。一旦,visit( ),失败，则操作失败。,（遍历线性表）,加工型操作,ClearList( &L ),PutElem( &L, i, &e ),ListInsert( &L, i, e ),ListDelete(&L, i, &e),ClearList( &L ),初始条件：,操作结果：,线性表,L,已存在。,将,L,重置为空表。,（线性表置空）,PutElem( &L, i, &e ),初始条件：,操作结果：,线性表,L,已存在，,且,1iLengthList(L),。,L,中第,i,个元素赋值同,e,的值。,（改变数据元素的值）,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,。,（删除数据元素）,对上述定义的抽象数据类型线性表，还可以进行一些更复杂的运算，如：,将两个或两个以上的线性表合并成一个线性表；,把一个线性表拆成两个或两个以上的线性表；,重新复制一个线性表；,对线性表中的数据元素按某个数据项递增或递减的顺,序进行重新排列，从而得到有序表。,这些运算均可利用上述基本运算来实现。,线性表是一个相当灵活的数据结构，它的长度可依据需要进行增减，对数据元素不仅可以访问，还可以进行插入和删除等操作。运算的具体实现一般依赖所采用的存储结构，所以，这里给出的只是定义在逻辑结构上的抽象运算，即只关心这些运算是“,做什么,”的，至于“,怎样实现,”则依赖于所选定的存储结构。,利用上述定义的,线性表,可以实现其它更复杂的操作,例,2-2,例,2-3,例,2-1,假设,:,有两个,集合,A,和,B,分别用两个,线性表,LA,和,LB,表示，即：线性表中的数据元素即为集合中的成员。,现要求一个新的集合,A,AB,。,例,2-1,要求对线性表作如下操作：,扩大线性表,LA,，将,存在于线性表,LB,中,而,不存在于线性表,LA,中,的数据元素,插入到线性表,LA,中,去。,上述问题可演绎为：,LA,：,(c,p,t,a,q,d),LB: (a,d,b,e,p,r),结果,LA: (c,p,t,a,q,d,b,e,r),1.,从线性表,LB,中依次察看每个数据元素,;,2.,依值在线性表,LA,中进行查访,;,3.,若不存在，则插入之。,GetElem(LB, i),e,LocateElem(LA, e, equal( ),ListInsert(LA, n+1, e),操作步骤：,GetElem(Lb, i, e),;,/,取,Lb,中第,i,个数据元素赋给,e,if,(,!,LocateElem(La, e, equal( ),),ListInsert(La, +La_len, e),;,/ La,中不存在和,e,相同的数据元素，则插入之,void,union(List,&,La, List Lb),La_len =,ListLength(La),;,Lb_len =,ListLength(Lb),;,/,求线性表的长度,for,(i = 1; i = Lb_len; i+),/ union,已知,一个,非纯集合,B,，试,构造,一个,纯集合,A,，,使,A,中只包含,B,中所有值各不相 同的数据元素,。,仍选用,线性表,表示集合。,例,2-2,集合,B,集合,A,从集合,B,取出物件放入集合,A,要求集合,A,中,同样物件不能有两件以上,因此，,算法的策略应该和例,2-1,相同,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,若线性表中的数据元素相互之间可以,比较,，并且数据元素在线性表中,依值非递减或非递增有序,排列，即,a,i,a,i-1,或,a,i,a,i-1,(i = 2,3, n),则称该线性表为,有序表,(Ordered List),。,试改变结构，以,有序表,表示集合。,例如,：,（,2,，,3,，,3,，,5,，,6,，,6,，,6,，,8,，,12,）,对集合,B,而言，,值相同的数据元素必定相邻；,对集合,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,(ListEmpty(La) | !equal (en, e),/ en,为表,La,中当前最后一个元素,ListInsert(La, +La_len, e);,en = e,;,/ La,中不存在和,e,相同的数据元素，则插入之,已知线性表,LA,和,LB,中的数据元素按值非递减有序排列，现要求将,LA,和,LB,归并为一个新的线性表,LC,，且,LC,中的数据元素仍按值非递减有序排列。,例如，设,LA=(3,5,8,11),i,LB=(2,6,8,9,11,15,20),j,则,LC=(2, 3, 5,6,8,8,9,11,11,15,20),k,例,2-3,Void,MergeList,(List La , List Lb, List &Lc), INITIATE(Lc);,i=j=1; k=0;,/,初始化,La_len= LENGTH (La) ; Lb_len= LENGTH (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),/,插入,La,表中剩余元素,GetElem(La, i+,ai); ListInsert(LC,+k,ai);,while (j=Lb_len),/,插入,Lb,表中剩余元素,GetElem(Lb, j+,bj); ListInsert(LC,+k,bj);, /,MergeList,2.2,线性表的顺序表示和实现,一、线性表的顺序存储结构,顺序映象,二、顺序存储结构的特点,三、线性表的顺序存贮结构示意图及描述,四、线性表的基本操作在顺序表中的实现,五、顺序存储结构的优缺点,一、线性表的顺序存储结构,顺序映象,最简单的一种顺序映象方法是：,令,y,的存储位置和,x,的存储位置相邻,。,以,x,的存储位置和,y,的存储位置之间某种关系表示逻辑关系,。,顺序存储结构：,用一组,地址连续,的存储单元,依次存放,线性表中的数据元素。,a,1,a,2,a,i-1,a,i,a,n,线性表的,起始地址,称作线性表的,基地址,假设线性表的每个数据元素要占,c,个存储单元，则,LOC(,a,i+1,)=LOC(,a,i,)+c,所有数据元素的存储位置均取决于第一个数据元素的存储位置，即,LOC(,a,i,)=LOC(,a,1,)+(i-1)*c,起始地址（基地址）,以“,存储位置相邻,”表示有序对,二、顺序存储结构的特点,表中相邻的两个元素其物理存储位置也相邻。,即以元素在计算机内物理位置上的相邻来表示线性表中数据元素之间相邻的逻辑关系。每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数；只要确定了起始位置，线性表中任一数据元素都可随机存取。,顺序存储结构是一种随机存取的存储结构。,三、线性表的顺序存贮结构示意图及描述,ai,a2,a1,内存状态,序号,存储地址,Loc(a1),Loc(a1) + C,Loc(a1) + C * (i-1),1,2,i,an,n,Loc(a1) + C * (n-1),空闲,Loc(a1) + (maxlen-1)*c,顺序映像的,C,语言描述,typedef struct ,SqList;,/,俗称顺序表,#define,LIST_INIT_SIZE 80,/,线性表存储空间的初始分配量,#define,LISTINCREMENT 10,/,线性表存储空间的分配增量,ElemType,*elem,;,/,存储空间基址,int,length,;,/,当前长度,int,listsize,;,/,当前分配的存储容量,/,(,以,sizeof(ElemType),为单位,),四、线性表的基本操作在顺序表中的实现,InitList(&L),/,结构初始化,LocateElem(L, e, compare(),/,查找,ListInsert(&L, i, e),/,插入元素,ListDelete(&L, i),/,删除元素,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;,/,空表长度为零,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;,线性表,操作,ListInsert,(&L, i, 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 =,&,(L.elemi-1);,/,q,指示插入位置,for,(p =,&,(L.elemL.length-1); p = q; -p),*,(p+1) =,*,p;,/,插入位置及之后的元素右移,*,q = e;,/,插入,e,+L.length;,/,表长增,1,return,OK;,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;,/,插入位置不合法,Status,ListInsert_Sq(SqList,&,L, int i, ElemType e),/,在顺序表,L,的第,i,个元素之前插入新的元素,e,/ i,的合法范围为,1,iL.length+1,/ ListInsert_Sq,算法,时间复杂度,为,:,O( ListLength(L) ),q =,&,(L.elemi-1);,/,q,指示插入位置,for,(p =,&,(L.elemL.length-1); p = q; -p),*,(p+1) =,*,p;,/,插入位置及之后的元素右移,*,q = e;,/,插入,e,+L.length;,/,表长增,1,return,OK;,考虑移动元素的平均情况,:,假设在第,i,个元素之前插入的概率为 ，,则在长度为,n,的线性表中,插入一个元素所需移动元素次数的期望值,为：,若,假定,在线性表中任何一个位置上进行,插入的概率,都是,相等,的，则,移动元素的期望值,为,：,21 18 30 75 42 56 87,21 18 30 75,例如：,ListInsert_Sq(L, 5, 66),L.length-1,0,p,p,p,q,87,56,42,66,q =,&,(L.elemi-1);,/ q,指示插入位置,for,(p =,&,(L.elemL.length-1); p = q; -p),*,(p+1) =,*,p;,p,线性表操作,ListDelete,(&L, i, &e),的实现,：,首先分析：,删除元素时，,线性表的逻辑结构发生什么变化？,(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 =,&,(L.elemi-1);,/ p,为被删除元素的位置,e = *p;,/,被删除元素的值赋给,e,q = L.elem+L.length-1;,/,表尾元素的位置,if,(i L.length),return,ERROR;,/,删除位置不合法,考虑移动元素的平均情况,:,假设删除第,i,个元素的概率为,则在长度为,n,的线性表中,删除一个元素,所需,移动元素次数的期望值,为：,若假定在线性表中任何一个位置上进行删除的,概率,都是,相等,的，则,移动元素的期望值,为,：,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 = q; +p) *(p-1) = *p;,例如：,ListDelete_Sq(L, 5, e),p,在顺序存储结构的线性表中插入或删除一个数据元素时，其时间主要耗费在移动元素上，移动次数不仅依赖于线性表的长度,L.length,，还依赖于元素插入或删除的位置,i,。,当,i=1,时，全部元素参加移动，移动次数为,n;,当,i= L.length +1,（插入）或,L.length,（删除）时，不需移动元素。,算法的时间复杂度为,O(n),。,五、顺序存储结构的优缺点, 无需为表示数据元素之间的关系而增加额外存储空间，存储密度高；, 可以随机存取表中任一元素，它的存储位置可用一个简单直观的公式来表示；, 插入和删除运算时，必须移动大量元素，尤其是当线性表的数据元素含有复杂信息时，移动工作量很大，效率较低；, 必须预先为线性表分配空间，表容量难以扩充，必须按线性表最大可能长度分配空间。若是线性表长度变化较大时，则使存储空间不能得到充分利用；且有时难以准确估计线性表最大长度，估计过小导致溢出，估计过大又会造成存储空间浪费。,