內(nèi)容提要,了解線性表的定義。掌握線性表的順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)以及相關(guān)的基本操作算法描述。了解雙向鏈表存儲結(jié)構(gòu)。,第二章線性表,Knowledge,第二章線性表,線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序（次序）集。線性結(jié)構(gòu)的特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)，稱為直接前驅(qū)（ImmediatePredecessor）。除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼，稱為直接后繼（ImmediateSuccessor）。,2.1線性表的類型定義一、定義：一個線性表是n個數(shù)據(jù)元素的有限序列,例：英文字母表（A,B,C,.Z)是一個線性表,二、線性表的特征：元素個數(shù)n稱為表長度，n=0，稱為空表1in時ai的直接前驅(qū)是ai1，a1無直接前驅(qū)ai的直接后繼是ai1，an無直接后繼元素同構(gòu)，且不能出現(xiàn)缺項,三、線性表抽象數(shù)據(jù)類型的定義ADTList數(shù)據(jù)對象:D=ai|aiElemSet,i=1,2,.,n,n0數(shù)據(jù)關(guān)系:R1=|ai1,aiD,i=1,2,.,n基本操作：typedefElemTypeET;typedefstructElemType*elem;/動態(tài)空間基址intlength;/實際元素個數(shù)intlistsize;/當(dāng)前分配的存儲容量/(以sizeof(ElemType)為單位)SqList;,聲明結(jié)構(gòu)體類型，SqList是順序表的類型名,動態(tài)申請和釋放內(nèi)存空間L.elem=(ElemType*)malloc(List_Init_Size*sizeof(ElemType);/申請內(nèi)存free(L.elem);/釋放內(nèi)存,typedefstructElemType*elem;intlength;intlistsize;SqList;,intListLength_Sq(SqListL)voidClearList_Sq(SqListGetElem_Sq(SqListL,inti,ElemTypeStatus型的數(shù)據(jù)范圍是:True、False、Ok、Error#defineTrue1#defineFalse0StatusListEmpty(SqListL)/判斷線性表L是否為空表if(L.length=0)returnTrue;returnFalse;,順序表基本操作的算法描述,/構(gòu)造一個空的線性表L#defineList_Init_Size10/存儲空間的初始分配量#defineListIncrement10/存儲空間的分配增量StatusInitList_Sq(SqList,添加（1，3，5，7，9）之后的狀態(tài)：,創(chuàng)建空表之后，表L的狀態(tài)如下：,刪除第3個元素之后的狀態(tài)：,是隨機數(shù)據(jù)也就是無效數(shù)據(jù),順序表的內(nèi)存狀態(tài),問題：在表的第1個位置插入6之后，表L的存儲狀態(tài)如何？,問題：清空L,即ClearList_Sq(L)之后，表L的存儲狀態(tài)如何？,添加（1，3，5，7，9）之后的狀態(tài)：,創(chuàng)建空表之后，表L的狀態(tài)如下：,刪除第3和第4個元素之后的狀態(tài)：,將隨機數(shù)據(jù)想象成空白,順序表的內(nèi)存想象狀態(tài),結(jié)論：凡是定義的或動態(tài)申請的空間內(nèi)，都想象為空白。如:intx,A900;SqListL;ElemType*elem;,二、順序表的插入操作定義：順序表的插入是指在第i個（1in+1）元素之前插入一個新的數(shù)據(jù)元素x，使長度為n的線性表,變成長度為n+1的線性表,需將第i至第n共（ni1)個元素依次后移一個位置。,x,順序表的插入操作,在順序表L中第i個位置上插入一個新的元素e,形式參數(shù)為：(2)將原動態(tài)區(qū)的數(shù)據(jù)拷貝到新動態(tài)區(qū);(3)釋放原動態(tài)存儲區(qū);(4)返回新存儲區(qū)首地址（無類型）。用途：當(dāng)原動態(tài)存儲區(qū)不夠用時，追加動態(tài)存儲區(qū)；,順序表的插入操作算法描述之一,StatusListInsert_Sq(SqList,StatusListInsert_Sq(SqList,順序表的插入操作算法描述之二,順序表插入操作的算法評價設(shè)Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：,三、順序表的刪除操作定義：線性表的刪除是指將第i（1in）個元素刪除，使長度為n的線性表,變成長度為n-1的線性表,需將第i+1至第n共（ni)個元素依次前移一個位置。,順序表的刪除操作,刪除順序表L中第i個位置上的元素，將刪除的元素值賦給e。形式參數(shù)為：structNode*next;LNode,*LinkList;/Lnode是結(jié)點類型名，/LinkList是結(jié)點指針類型名LinkListL;LNode*p;,(*p)表示p所指向的結(jié)點(*p).datapdata表示p指向結(jié)點的數(shù)據(jù)域(*p).nextpnext表示p指向結(jié)點的指針域,生成一個LNode型新結(jié)點：p=(LNode*)malloc(sizeof(LNode);或：p=(LinkList)malloc(sizeof(LNode);系統(tǒng)回收p結(jié)點：free(p),一、線性鏈表1、定義：每個結(jié)點中只含一個指針域的鏈表叫，也叫單鏈表(SingleLinkedList),頭結(jié)點：在單鏈表第一個結(jié)點前附設(shè)加一個結(jié)點叫頭結(jié)點指針域為空表示線性表為空表。,頭指針L是LinkList類型，頭結(jié)點是Lnode類型非空表：空表：注意：頭結(jié)點的位序為0，它不是線性表中的元素，頭結(jié)點的數(shù)據(jù)域可用于存儲線性表的長度。單鏈表是非隨機存取的存儲結(jié)構(gòu)在單鏈表中，任何兩個元素的存儲位置之間沒有固定的聯(lián)系，每個元素的存儲位置都包含在其直接前驅(qū)結(jié)點的指針域中。在單鏈表中，要取得第i個數(shù)據(jù)元素必須從頭結(jié)點出發(fā)尋找。,頭,5,8,3,6,L,頭,L,StatusInitList_L(LinkList時間復(fù)雜度：O(1),L必須是引用型,構(gòu)造一個空的單鏈表的算法描述,1.指針p在鏈表上依次滑動：p=head;while(pnext!=NULL)p=pnext;2.前驅(qū)指針q和當(dāng)前指針p在鏈表上同步滑動：q=head;p=qnext;while(p)q=p;p=qnext;例1：intListLength_L(LinkListL)/求線性表的長度p=L;j=0;while(pnext!=NULL)或while(pnext)+j;p=pnext;return(j);例2：StatusPriorElem_L(LinkListL,ETe,ET例3：StatusNextElem_L(LinkListL,ETe,ET,pnext=s;,StatusListInsert_L(LinkList,單鏈表的基本運算插入,在單鏈表L中刪除第i個結(jié)點，并由e返回其值的操作步驟：(1)尋找第i-1個結(jié)點；/O(n)(2)測試已知量的合法性；/O(1)(3)刪除第i個結(jié)點，并取出數(shù)據(jù)域的值賦給e；/O(1)(4)釋放第i個結(jié)點的存儲空間。/O(1)該算法的時間復(fù)雜度是：O(n),單鏈表的基本運算刪除,pnext=qnext;,StatusListDelete_L(LinkList,單鏈表的基本運算刪除,逆位序輸入n個元素的值，建立帶表頭結(jié)點的單鏈表L。,算法評價：T(n)O(n),動態(tài)建立單鏈表的算法逆向建立,VoidCreateList_L(LinkList/將結(jié)點p插入到表頭,動態(tài)建立單鏈表的算法逆向建立,單鏈表特點它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用不需預(yù)先分配空間，分配的空間連續(xù)與否均可指針占用額外存儲空間不能隨機存取，查找速度慢，便于插入、刪除操作,線性表的順序存儲和鏈式存儲操作上的比較,1編寫程序?qū)崿F(xiàn)單鏈表的下列基本操作：(1)初始化單鏈表La。(2)在單鏈表La中插入一個新結(jié)點。(3)刪除單鏈表La中的某一個結(jié)點。(4)在單鏈表La中查找某結(jié)點并返回其位置。(5)打印輸出單鏈表La中的結(jié)點元素值。2構(gòu)造兩個帶有表頭結(jié)點的有序單鏈表La、Lb，編寫程序?qū)崿F(xiàn)將La、Lb合并成一個有序單鏈表Lc。,上機作業(yè)2單鏈表基本操作（2學(xué)時）,能力培養(yǎng)：掌握對單鏈表的一些基本操作和具體的函數(shù)定義，通過實現(xiàn)兩個有序表歸并，訓(xùn)練單鏈表的一些基本操作。,Engineering,Practice,二、循環(huán)鏈表(CircularLinkedList)循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成一個環(huán)狀特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高了查找效率循環(huán)鏈表操作與單鏈表基本一致，循環(huán)結(jié)束條件不同單鏈表L：pnext=NULL循環(huán)鏈表L：pnext=L非空循環(huán)鏈表空循環(huán)鏈表,僅設(shè)尾指針的兩循環(huán)鏈表的鏈接,存儲池,p,Void*Connect(LinkList,僅設(shè)尾指針的兩循環(huán)鏈表的鏈接算法,三、雙向鏈表（DoubleLinkedList）單鏈表具有單向性的缺點,所以引入雙向鏈表。結(jié)點定義,typedefstructDuLNodeElemTypedata;structDuLNode*prior,*next;DuLNode,*DuLinkList;,ppriornext=p=pnextproir;,算法評價：T(n)=O(n),插入操作,算法描述StatusListInsert_DuL(DuLinkList,sprior=pprior;,ppriornext=s;,snext=p;,pprior=s;,刪除操作,算法評價：T(n)=O(n),ppriornext=pnext;,pnextprior=pprior;,算法描述StatusListDelete_DuL(DuLinkList,比較線性表順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)的異同及優(yōu)缺點思考：如何應(yīng)用線性表的相關(guān)知識完成兩個一元多項式的加法運算？,課堂思考與討論：,Practice,能力培養(yǎng)：學(xué)習(xí)用單鏈表解決實際問題的能力。,Engineering,2.4一元多項式的表示及相加兩個一元多項式可按升冪如下表示,可用線性表P和Q表示,設(shè)mn，則兩個多項式