本章學習要點1.了解線性表邏輯結構的特征;2.重點掌握線性表的順序存儲結構和鏈式存儲結構，它們如何表達線性表中數據元素之間的結構關系；如何用C語言描述它們的類型定義；3.掌握在順序存儲結構下，線性表的基本操作的算法；4.掌握在鏈式存儲結構下，線性表的基本操作算法；5.能夠從時間復雜度的角度，比較線性表兩類存儲結構不同特點及適用場合；,第2章線性表,線性結構的基本特征為:,線性結構是一個數據元素的有序（次序）集合。1集合中必存在唯一的一個“第一元素”；2集合中必存在唯一的一個“最后元素”；3除最后元素在外，均有唯一的后繼；4除第一元素之外，均有唯一的前驅。,2.1線性表的類型定義,2.3線性表類型的實現鏈式映象,2.4一元多項式的表示,2.2線性表類型的實現順序映象,2.1線性表的類型定義,線性表是n個類型相同數據元素的有限序列，通常記作（a1,a2,a3,an）。,例1、數學中的數列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,EZ）。例3、某單位的電話號碼簿。,一、線性表的邏輯結構,電話號碼簿是數據元素的有限序列，每一數據元素包括兩個數據項，一個是用戶姓名，一個是對應的電話號碼。,說明：設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的位序。,二、線性表的抽象數據類型定義：,ADTList,數據對象：,Dai|aiElemSet,i=1,2,.,n,n0,數據關系：,R1|ai-1,aiD,i=2,.,n,基本操作：,結構初始化操作結構銷毀操作引用型操作加工型操作,ADTList,InitList(/取Lb中第i個數據元素賦給eif(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和e相同的數據元素，則插入之,voidunion(List,for(i=1;i=Lb_len;i+),/union,例2-2已知線性表LA和LB中的元素按值非遞減有序，現要求將它們歸并成一個新的線性表LC，且LC的元素也按值非遞減有序。解題思路：建立空線性表LC，將LA、LB表中的元素逐個插入到LC中，插入規則為：在LA、LB中分別設立指針i、j，比較i,j位置上的元素（設它們分別為a,b)。則C繼續往下比較以下是算法。,voidMergeList(ListLa,ListLb,List/構造空的線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);,代碼見下頁（1）,代碼見下頁（2）,代碼見下頁（3）,/La和Lb均非空，i=j=1,k=0GetElem(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表中剩余元素,代碼（1）,代碼（2）,代碼（3）,例一和例二的算法時間復雜度分析：上述算法中基本操作GetElem和ListInstert的執行時間，它們與表長無關，LocateElem與表長成正比。所以例一的時間復雜度為：O(ListLength(LA)ListLength(LB)例二的時間復雜度為：O(ListLength(LA)+ListLength(LB),2.2線性表的實現順序映象,用一組地址連續的存儲單元依次存放線性表中的數據元素,a1a2ai-1aian,線性表的起始地址稱作線性表的基地址,以“存儲位置相鄰”表示有序對即：LOC(ai)=LOC(ai-1)+C一個數據元素所占存儲量,所有數據元素的存儲位置均取決于第一個數據元素的存儲位置LOC(ai)=LOC(a1)+(i-1)C基地址,順序映像的C語言描述,typedefstructSqList;/俗稱順序表,#defineLIST_INIT_SIZE80/線性表存儲空間的初始分配量#defineLISTINCREMENT10/線性表存儲空間的分配增量,ElemType*elem;/存儲空間基址,intlength;/當前長度,intlistsize;/當前分配的存儲容量(以sizeof(ElemType)為單位),線性表的基本操作在順序表中的實現,InitList(if(!L.elem)exit(OVERFLOW);,L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;,順序表中查找數據元素,e=,38,i,1,2,3,4,1,8,50,可見，基本操作是：將順序表中的元素逐個和給定值e相比較。,intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)/在順序表中查詢第一個滿足判定條件的數據元素，/若存在，則返回它的位序，否則返回0/LocateElem_Sq,O(ListLength(L),算法的時間復雜度為：,i=1;/i的初值為第1元素的位序p=L.elem;/p的初值為第1元素的存儲位置,while(ii)/第i個元素不存在returnERROR;e=p-data;/取得第i個元素returnOK;,2.單鏈表中ListInsert(/生成新結點s-data=e;s-next=p-next;p-next=s;/插入returnOK;,p=L;j=0;while(p/i大于表長或者小于1,3.單鏈表中ListDelete(p-next=q-next;e=q-data;free(q);,p,q,StatusListDelete_L(LinkListL,inti,ElemTypej=0;while(p-next/刪除位置不合理,q=p-next;p-next=q-next;/刪除并釋放結點e=q-data;free(q);returnOK;,4.單鏈表中ClearList(,算法時間復雜度：,O(ListLength(L),鏈表是一個動態的結構，從線性表得到單鏈表它不需要預分配空間，因此生成鏈表的過程是一個結點“逐個插入”的過程。例如：逆位序輸入n個數據元素的值，建立帶頭結點的單鏈表。,一、建立一個“空表”；,二、輸入數據元素an，建立結點并插入；,三、輸入數據元素an-1，建立結點并插入；,四、依次類推，直至輸入a1為止。,an,an,an-1,voidCreateList_L(LinkListL-next=NULL;/先建立一個帶頭結點的單鏈表,for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(/插入,線性鏈表歸并操作算法（直接對原鏈表進行操作）算法2.12voidMergeList_L(LinkList/釋放Lb的頭結點/MergeList_L,四靜態鏈表,1.靜態鏈表的概念用一維數組來實現線性鏈表，用一維數組表示的線性鏈表，稱為靜態鏈表。2.靜態鏈表的類型定義,SLinkList：數組的類型名；SLinkList類型的數組變量是結構數組，每一數組分量包括兩個域：data用于存儲線性表元素；cur用于存儲直接后繼元素在數組中的位置（下標）。,#defineMAXSIZE1000/鏈表的最大長度typedefstructElemTypedata;intcur;component,SLinkListMAXSIZE;,靜態鏈表圖示,數組下標,地址,插入前,3.靜態鏈表插入操作圖示,插入后,刪除前,刪除sun,刪除后,4.靜態鏈表刪除插入操作圖示,5.靜態鏈表的空間管理,初始化：,voidInitSpace_SL(Slinklist/InitSpace_SL,intMalloc_SL(Slinklist/返回值i為0表示分配不成功/Malloc_SL,voidFree_SL(Slinklist/Malloc_SL,分配：,回收：,1.循環鏈表的概念循環鏈表是線性表的另一種鏈式存儲結構，它的特點是將線性鏈表的最后一個結點的指針指向鏈表的第一個結點2.循環鏈表圖示,五循環鏈表,(a)非空表（b）空表,注意：在解決某些實際問題時循環鏈表可能要比線性鏈表方便些。如將一個鏈表鏈在另一個鏈表的后面；對循環鏈表，有時不給出頭指針，而是給出尾指針，設立尾指針可以很方便的找到線性表的第一個元素和最后一個元素結點，可使某些操作易于實現；例如將兩個鏈表首尾相連的操作；循環鏈表與線性鏈表操作的主要差別是算法中循環結束的條件；,給出尾指針的循環鏈表,是什么呢？,1.雙向鏈表的概念雙向鏈表中，每個結點有兩個指針域，一個指向直接后繼元素結點，另一個指向直接前趨元素結點。,六雙向鏈表,(a)結點圖示,存儲數據元素,存儲后繼結點的地址,存儲前趨結點的地址,2.雙向鏈表圖示,（c）非空的雙向循環鏈表,(b)空的雙向循環鏈表,3.雙向鏈表的基本操作算法,在雙向鏈表中插入一個結點時指針的變化情況,在雙向鏈表中刪除結點時指針變化情況,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,p,s,插入若P定位在i的前驅上,插入操作算法（算法2.18）StatusListInsert_DuL(DuLinkList/LinstInsert_DuL,刪除若P定位在i的前驅上,p-next=p-next-next;p-next-prior=p;,p,刪除操作算法（算法2.19）StatusListDelete_DuL(DuLinkList/LinstDelete_DuL,七一個帶頭結點的線性鏈表類型,typedefstructLNode/結點類型ElemTypedata;structLNode*next;*Link,*Position;,StatusMakeNode(Link/分配由p指向的值為e的結點，并返回OK，/若分配失敗，則返回ERROR,voidFreeNode(Link/釋放p所指結點,typedefstruct/鏈表類型Linkhead,tail;/分別指向頭結點和/最后一個結點的指針intlen;/指示鏈表長度Linkcurrent;/指向當前被訪問的結點/的指針，初始位置指向頭結點LinkList;,鏈表的基本操作:,結構初始化和銷毀結構,StatusInitList(LinkList/構造一個空的線性鏈表L，其頭指針、/尾指針和當前指針均指向頭結點，/表長為零。,StatusDestroyList(LinkList/銷毀線性鏈表L，L不再存在。,O(1),O(n),引用型操作,StatusListEmpty(LinkListL);/判表空,intListLength(LinkListL);/求表長,StatusPrior(LinkListL);/改變當前指針指向其前驅,StatusNext(LinkListL);/改變當前指針指向其后繼,ElemTypeGetCurElem(LinkListL);/返回當前指針所指數據元素,O(1),O(1),O(n),O(1),O(1),StatusLocatePos(LinkListL,inti);/改變當前指針指向第i個結點,StatusLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType);/若存在與e滿足函數compare()判定關系的元素，/則移動當前指針指向第1個滿足條件的元素的/前驅，并返回OK;否則返回ERROR,StatusListTraverse(LinkListL,Status(*visit)();/依次對L的每個元素調用函數visit(),O(n),O(n),O(n),加工型操作,StatusClearList(LinkList/重置L為空表,StatusSetCurElem(LinkList/更新當前指針所指數據元素,StatusAppend(LinkList/在表尾結點之后鏈接一串結點,StatusInsAfter(LinkList/將元素e插入在當前指針之后,StatusDelAfter(LinkList/刪除當前指針之后的結點,O(1),O(n),O(s),O(1),O(1),StatusInsAfter(LinkList/否則返回ERROR。/InsAfter,if(!L.current)returnERROR;if(!MakeNode(s,e)returnERROR;s-next=L.current-next;L.current-next=s;if(L.tail=L.current)L.tail=s;L.current=s;returnOK;,StatusDelAfter(LinkList否則返回ERROR。/DelAfter,if(!(L.current,例一StatusListInsert_L(LinkListL,inti,ElemTypee)/在帶頭結點的單鏈線性表L的第i個元素之前插入元素e/ListInsert_L,利用上述定義的線性鏈表如何完成線性表的其它操作,if(!LocatePos(L,i-1)returnERROR;/i值不合法，第i-1個結點不存在if(InsAfter(L,e)returnOK;/完成插入elsereturnERROR;,StatusMergeList_L(LinkList/存儲空間分配失敗,while(!(a=MAXCLocatePos(Lb,0);/當前指針指向頭結點,if(DelAfter(La,e)a=e;/取得La表中第一個元素aelsea=MAXC;/MAXC為常量最大值if(DelAfter(Lb,e)b=e;/取得Lb表中第一個元素belseb=MAXC;/a和b為兩表中當前比較元素,DestroyList(La);DestroyList(Lb);/銷毀鏈表La和LbreturnOK;,if(*compare)(a,b)=0)/abInsAfter(Lc,a);if(DelAfter(La,e1)a=e1;elsea=MAXC;,else/abInsAfter(Lc,b);if(DelAfter(Lb,e1)b=e1;elseb=MAXC;,2.4一元多項式的表示,在計算機中，可以用一個線性表來表示:P=(p0,p1,，pn),但是對于形如S(x)=1+3x100002x20000的多項式，上述表示方法是否合適？,一般情況下的一元稀疏多項式可寫成Pn(x)=p1xe1+p2xe2+pmxem其中：pi是指數為ei的項的非零系數，0e1e2em=n,可以下列線性表表示：（p1,e1）,(p2,e2),(pm,em)）,例如:P999(x)=7x3-2x12-8x999可用線性表(7,3),(-2,12),(-8,999)表示,ADTPolynomial數據對象：數據關系：,抽象數據類型一元多項式的定義如下：,Dai|aiTermSet,i=1,2,.,m,m0TermSet中的每個元素