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