.,1,第一章緒論,.,2,1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇,1.2與數(shù)據(jù)結(jié)構(gòu)相關(guān)的概念,1.3算法和算法的量度,.,3,軟件開發(fā)的過程:,系統(tǒng)分析,系統(tǒng)實現(xiàn),系統(tǒng)維護,系統(tǒng)設(shè)計,系統(tǒng)設(shè)計,確定系統(tǒng)所要達到的目標,確定實現(xiàn)方案并生成系統(tǒng),實地安裝調(diào)試,系統(tǒng)修整完善,.,4,NiklausWirthAlgorithm+DataStructures=Programs,程序設(shè)計:算法:數(shù)據(jù)結(jié)構(gòu):,為計算機處理問題編制一組指令集,處理問題的策略,問題的數(shù)學模型,.,5,例如:,雞兔同籠問題,二元一次代數(shù)方程組,結(jié)構(gòu)靜力分析問題,全球天氣預(yù)報,高次線性代數(shù)方程組,球面坐標系下的環(huán)流模式方程,.,6,非數(shù)值計算的程序設(shè)計問題,例一求一組(n個)整數(shù)中的最大值,例二交叉路口的交通管制問題,例三煤氣管道的鋪設(shè)問題,例四數(shù)據(jù)庫中表格管理問題,.,7,概括地說，,數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實世界實體的數(shù)學模型(非數(shù)值計算)及其上的操作在計算機中如何表示和實現(xiàn)”的學科。,.,8,.,9,一、基本概念和術(shù)語,二、數(shù)據(jù)結(jié)構(gòu),三、數(shù)據(jù)類型和抽象數(shù)據(jù)類型,.,10,所有能被輸入到計算機中，且能被計算機處理的符號(數(shù)字、字符等)的集合。,數(shù)據(jù),是計算機操作的對象的總稱。,是計算機處理的信息的某種特定的符號表示形式。,.,11,是數(shù)據(jù)（集合）中的一個“個體”,在計算機中通常作為一個整體進行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。,數(shù)據(jù)元素,例如，整數(shù)“5”,字符“N”等。-是不可分割的“原子”,.,12,它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。,又如,描述一個學生的數(shù)據(jù)元素由多個款項構(gòu)成，其中每個款項稱為一個“數(shù)據(jù)項”。,稱之為組合項,原子項,.,13,關(guān)鍵字,能識別一個或幾個數(shù)據(jù)元素的數(shù)據(jù)項。若能起唯一識別作用，則被稱為“主”關(guān)鍵字，否則稱為“次”關(guān)鍵字。,數(shù)據(jù)對象,具有相同特性的數(shù)據(jù)元素的集合。如:整數(shù)、實數(shù)等。,.,14,數(shù)據(jù)結(jié)構(gòu),帶結(jié)構(gòu)的數(shù)據(jù)元素的集合,有一個特性相同的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱為一個數(shù)據(jù)結(jié)構(gòu)。,指的是數(shù)據(jù)元素之間存在的關(guān)系,.,15,例如，可用三個4位的十進制數(shù)表示一個含12位數(shù)的“長整數(shù)”。,3214,6587,9345a1(3214),a2(6587),a3(9345),對長整數(shù)進行運算的程序中的操作對象是一個含三個數(shù)據(jù)元素a1,a2,a3的集合，且三者之間存在下列“次序”關(guān)系:a1,a2、a2,a3。,.,16,又如，在2行3列的二維數(shù)組中六個元素a1,a2,a3,a4,a5,a6之間存在著兩個關(guān)系:,“行”的次序關(guān)系:,row=,col=,“列”的次序關(guān)系:,.,17,在含6個數(shù)據(jù)元素a1,a2,a3,a4,a5,a6的集合上存在如下的次序關(guān)系:,|i=1,2,3,4,5,“數(shù)據(jù)結(jié)構(gòu)”是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。,可見，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”,則構(gòu)成“一維數(shù)組”。,.,18,可用如下的數(shù)據(jù)結(jié)構(gòu)描述“班集體”:,班主任，班長1，班長2，舍長1，舍長p,學生1，學生2，學生n,，,，,.,19,數(shù)據(jù)結(jié)構(gòu)的形式定義描述為:,數(shù)據(jù)結(jié)構(gòu)是一個二元組,Data_Structures=(D,S),其中:D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。,.,20,從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:,線性結(jié)構(gòu),樹形結(jié)構(gòu),圖狀結(jié)構(gòu),集合結(jié)構(gòu),.,21,數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個方面(層次):,邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來表示;,物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機中的表示和實現(xiàn)，故又稱“存儲結(jié)構(gòu)”。,.,22,存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在存儲器中的映象,“數(shù)據(jù)元素”的映象？,“關(guān)系”的映象？,用二進制位(bit)的位串表示數(shù)據(jù)元素,(321)10=(501)8=(101000001)2,A=(101)8=(001000001)2,.,23,“關(guān)系”的兩種映象方法：,（表示x,y的方法）,順序映象,以x和y之間相對的存儲位置表示后繼關(guān)系,例如:令y的存儲位置和x的存儲位置之間相差一個預(yù)設(shè)常量C，而C是一個隱含值，,存儲結(jié)構(gòu)中只包含數(shù)據(jù)元素本身的信息,.,24,鏈式映象,以附加信息(指針)表示后繼關(guān)系,需要用一個和x綁定在一起的附加信息(指針)指示y的存儲位置,以“由數(shù)據(jù)元素x的存儲映象和附加的指針合成的結(jié)點”表示數(shù)據(jù)元素。,.,25,存儲結(jié)構(gòu)的描述方法隨編程環(huán)境的不同而不同，,當用高級程序設(shè)計語言進行編程時，通?？捎酶呒壘幊陶Z言中提供的數(shù)據(jù)類型描述之。,typedefintLong_int3,例如，當以“順序映象”表示長整數(shù)時，可定義為:,.,26,定義“日期”為:typedefstructinty;/年號Yearintm;/月號Monthintd;/日號DayDateType;/日期類型,定義“學生”為:typedefstructcharid8;/學號charname16;/姓名charsex;/性別M/F:男/女DateTypebdate;/出生日期Student;/學生類型,.,27,何謂“數(shù)據(jù)類型”？,在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)的每個變量、常量或表達式，明確說明它們所屬的數(shù)據(jù)類型。,例如，C+語言中的基本數(shù)據(jù)類型有:,邏輯型bool、字符型char、整型int和實型(浮點型float和雙精度型double),.,28,數(shù)據(jù)類型是一個“值”的集合和定義在此集合上的“一組操作”的總稱。,對程序員而言，各種語言中的整數(shù)類型都是一樣的，因為它們的數(shù)學特性相同。,從這個意義上可稱“整數(shù)”是一個抽象數(shù)據(jù)類型。,抽象數(shù)據(jù)類型和數(shù)據(jù)類型的實質(zhì)相同，范疇更廣，不局限于語言中的數(shù)據(jù)類型。,.,29,抽象數(shù)據(jù)類型(AbstractDataType簡稱ADT)是指一個數(shù)學模型以及定義在該模型上的一組操作。,通常稱語言中已經(jīng)實現(xiàn)的數(shù)據(jù)類型為固有數(shù)據(jù)類型。,抽象數(shù)據(jù)類型有兩個重要特征:,“數(shù)據(jù)抽象”和“數(shù)據(jù)封裝”,.,30,數(shù)據(jù)抽象,數(shù)據(jù)封裝,用ADT描述程序處理的實體時，強調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。,將實體的外部特性和其內(nèi)部實現(xiàn)細節(jié)分離，并且對外部用戶隱藏其內(nèi)部實現(xiàn)細節(jié),.,31,抽象數(shù)據(jù)類型的描述方法,ADT=（D，S，P）,其中:D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。,數(shù)據(jù)對象是特性相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。,.,32,例如,抽象數(shù)據(jù)類型“復數(shù)”的定義:,R1|e1是復數(shù)的實數(shù)部分,|e2是復數(shù)的虛數(shù)部分,ADTComplex,數(shù)據(jù)對象：,De1,e2e1,e2RealSet,數(shù)據(jù)關(guān)系：,.,33,基本操作：,AssignComplex(floatRealPart,ImagPart;InitComplex(z1,8.0,6.0);InitComplex(z2,4.0,3.0);Add(z1,z2,z3);Multiply(z1,z2,z4);if(Division(z4,z3,z)GetReal(z,RealPart);GetImag(z,ImagPart);/if,.,37,ADT抽象數(shù)據(jù)類型名數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義基本操作：基本操作的定義ADT抽象數(shù)據(jù)類型名,其中基本操作的定義格式為:,基本操作名（參數(shù)表）初始條件：初始條件描述操作結(jié)果：操作結(jié)果描述,.,38,賦值參數(shù)只為操作提供輸入值；引用參數(shù)以in-1;+i),例二選擇排序,基本操作:比較(數(shù)據(jù)元素)操作,時間復雜度:O(n2),j=i;/選擇第i個最小元素for(k=i+1;kn;+k)if(akaj)j=k;,if(j!=i)ajai;,.,62,例三起泡排序,voidbubble_sort(int-i)/bubble_sort,基本操作:賦值操作,時間復雜度:O(n2),change=FALSE;/change為元素進行交換標志for(j=0;jaj+1)ajaj+1;change=TRUE;/一趟起泡,for,for,.,63,算法的空間復雜度定義為:,表示隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。,S(n)=O(g(n),.,64,算法的存儲量包括:,1輸入數(shù)據(jù)所占空間,2程序本身所占空間；,3輔助變量所占空間。,.,65,若輸入數(shù)據(jù)所占空間只取決與問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。,若所需額外空間相對于輸入數(shù)據(jù)量來說是個常量，則稱此算法為原地工作。,若所需存儲量依賴于特定的輸入，則通常按最壞情況考慮。,.,66,1.熟悉各名詞、術(shù)語的含義，掌握基本概念。,2.理解算法五個要素的確切含義。,本章學習要點,3.掌握計算語句頻度和估算算法時間復雜度的方法。,.,67,提幾點要求:,1.課前預(yù)習，了解本堂課內(nèi)容;,2.課后復習，在理解教學內(nèi)容的基礎(chǔ)上做練習題;,3.獨立完成作業(yè);,4.勤答疑，多問“為什么”。,.,68,(n-1)+(n-2)+1=n(n-1)/2=n2/2+n/2,312597,13,23,5,79,12357,519732,15,9,79,39,15,29,7,37,27,15,35,25,13,23,12,9,7,5,3,2,.,69,第二章線性表,.,70,線性結(jié)構(gòu)的基本特征:,1集合中必存在唯一的一個“第一元素”,2集合中必存在唯一的一個“最后元素”,3除最后元素在外，均有唯一的后繼,4除第一元素之外，均有唯一的前驅(qū),線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序（次序）集,.,71,2.1線性表的類型定義,2.3線性表類型的實現(xiàn)鏈式映象,2.4一元多項式的表示,2.2線性表類型的實現(xiàn)順序映象,.,72,ADTList,數(shù)據(jù)對象：,Dai|aiElemSet,i=1,2,.,n,n0稱n為線性表的表長;稱n=0時的線性表為空表。,數(shù)據(jù)關(guān)系：,R1|ai-1,aiD,i=2,.,n,設(shè)線性表為(a1，a2,.，ai，.，an),稱i為ai在線性表中的位序。,.,73,基本操作：,結(jié)構(gòu)初始化操作,結(jié)構(gòu)銷毀操作,引用型操作,加工型操作,ADTList,.,74,結(jié)構(gòu)初始化InitList(,2依值在線性表LA中進行查訪;,3若不存在，則插入之。,ListDelete(Lb,1,e);,LocateElem(LA,e,equal();,ListInsert(LA,n+1,e);(n表示線性表LA當前長度),操作步驟：,.,86,ListDelete(Lb,1,e);/刪除Lb中第1個數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和e相同的數(shù)據(jù)元素，則插入之,La_len=ListLength(La);/求線性表La的長度,while(!ListEmpty(Lb),/while,/union,voidunion(List/取Lb中第i個數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和e相同的數(shù)據(jù)元素，則插入之,for(i=1;i=Lb_len;i+)/for,InitList(La);/構(gòu)造(空的)線性表LA,.,89,例2-3,判別兩個集合是否相等。,集合相等的條件是:兩者所含元素個數(shù)相同，且所有對應(yīng)元素都相等。,仍以線性表表示集合，并假設(shè)這兩個集合是“純集合”。,則算法的策略為:在兩個線性表的長度相等的前提下，只要判別一個表中的元素在另一個表中都存在即可。,.,90,boolisEqual(ListLA,ListLB)/若線性表LA和LB不僅長度相等，且所含數(shù)據(jù)/元素也相同，則返回TRUE,否則返回FALSE/isEqual,La_len=Listlength(LA);Lb_len=Listlength(LB);if(La_len!=Lb_len)returnFALSE;/兩表的長度不等else,.,91,while(i=La_len,GetElem(LA,i,e);/取得LA中一個元素if(LocateElem(LB,e,equal()i+;/依次處理下一個elsefound=FALSE;/LB中沒有和該元素相同的元素,i=1;found=TRUE;,.,92,一、順序表-線性表的順序映象,二、順序表中基本操作的實現(xiàn),三、順序表的其它操作舉例,.,93,最簡單的一種順序映象方法是：令y的存儲位置和x的存儲位置相鄰。,順序映象,以x的存儲位置和y的存儲位置之間某種關(guān)系表示邏輯關(guān)系,.,94,用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素,線性表的起始地址，稱作線性表的基地址,.,95,以“存儲位置相鄰”表示有序?qū)矗篖OC(ai)=LOC(ai-1)+C一個數(shù)據(jù)元素所占存儲量,所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置LOC(ai)=LOC(a1)+(i-1)C,基地址,.,96,順序表的C語言描述,/存儲結(jié)構(gòu)typedefstructSqList;/俗稱順序表,ElemType*elem;/存儲空間基址,intlength;/當前長度,intlistsize;/當前分配的存儲容量/(以sizeof(ElemType)為單位),/基本操作接口,.,97,voidpurge(SqListi+)/依次處理Lb中每個元素/for/purge,.,98,b=GetElem(Lb,i,e);/取Lb中第i個數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()+La_len;b=ListInsert(La,La_len,e);/當La中不存在和e值相同的數(shù)據(jù)/元素時進行插入,.,99,線性表的基本操作在順序表中的實現(xiàn),InitList(/為順序表分配大小為maxsize的數(shù)組空間if(!L.elem)exit(OVERFLOW);,L.length=0;L.listsize=maxsize;returnOK;,.,101,例如：順序表,假設(shè)e=,38,i=,1,2,3,4,1,8,50,可見，基本操作是，將順序表中的元素逐個和給定值e相比較。,.,102,intLocateElem(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)/在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素，/若存在，則返回它的位序，否則返回0/LocateElem,O(ListLength(L),if(i=L.listsize)returnOVERFLOW;/當前存儲空間已滿,if(iL.length+1)returnERROR;/插入位置不合法,.,108,例如：ListInsert(L,5,66),L.length-1,0,87,56,42,66,for(j=L.length-1;j=pos-1;-j)L.elemj+1=L.elemj;,4,.,109,線性表操作ListDelete(jL.length;+j)L.elemj-1=L.elemj;/被刪除元素之后的元素左移-L.length;/表長減1returnTRUE;,if(iL.length)returnERROR;/刪除位置不合法,元素左移,.,112,考慮移動元素的平均情況:,假設(shè)刪除第i個元素的概率為qi,則在長度為n的線性表中刪除一個元素所需移動元素次數(shù)的期望值為：,若假定在線性表中任何一個位置上進行刪除的概率都是相等的，則移動元素的期望值為：,.,113,L.length-1,0,87,56,for(j=pos;jL.length;+j)L.elemj-1=L.elemj;,例如：ListDelete(L,5,e),63,5,.,114,試設(shè)計一個算法，用盡可能少的輔助空間將順序表中前m個元素和后n個元素進行互換，即將線性表(a1,a2,am,b1,b2,bn)改變成(b1,b2,bn,a1,a2,am)。,從b1開始，從原地刪除之后插入到a1之前直至bn。,例2-4,算法1,進行三次“逆轉(zhuǎn)順序表”的操作。,算法2,.,115,1,g,g,g,f,f,f,e,e,e,d,d,d,c,c,c,b,b,b,a,a,a,2,3,1,2,3,a,b,c,d,e,e,f,f,g,1,2,3,4,4,5,c,b,g,a,2,5,1,.,116,voidinvert(ElemTypej=m;ji;k-)A.elemj=A.elemj-1;A.elemi=x;,算法的時間復雜度為:O(mn),.,118,試編寫算法，刪除順序表中“多余”的數(shù)據(jù)元素。,例2-5,從a1開始，檢查在它之后的數(shù)據(jù)元素，如有和它相等的，則從表中刪除之。,算法1,回顧例2-2的算法，試按“構(gòu)造”一個新的順序表的思想來進行，設(shè)想這兩個表“共享”一個存儲空間。,算法2,.,119,3,3,4,2,5,5,7,4,3,7,5,4,3,3,4,5,2,3,4,7,.,120,voidpurge(SqListwhile(jdata;/取得第i個元素returnOK;,p/第i個元素不存在,.,131,線性表的操作ListInsert(j=0;while(p/尋找第i-1個結(jié)點,if(!p|ji-1)returnERROR;/i大于表長或者小于1,.,134,s=newLNode;/生成新結(jié)點if(s=NULL)returnERROR;s-data=e;s-next=p-next;p-next=s;/插入returnOK;,s,p,.,135,線性表的操作ListDelete(p-next=q-next;e=q-data;delete(q);,p,q,.,137,StatusListDelete(LinkListL,inti,ElemTypej=0;while(p-next/尋找第i個結(jié)點，并令p指向其前趨,q=p-next;p-next=q-next;/刪除并釋放結(jié)點e=q-data;delete(q);returnOK;,if(!(p-next)|ji-1)returnERROR;/刪除位置不合理,.,138,操作ClearList(,算法時間復雜度：,O(ListLength(L),.,139,如何從線性表得到單鏈表？,鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個結(jié)點“逐個插入”的過程。,.,140,例如：逆位序輸入n個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。,操作步驟：,一、建立一個“空表”；,二、輸入數(shù)據(jù)元素an，建立結(jié)點并插入；,三、輸入數(shù)據(jù)元素an-1，建立結(jié)點并插入；,四、依次類推，直至輸入a1為止。,.,141,p=newLNode;scanf(/插入,L=newLNode;L-next=NULL;/先建立一個帶頭結(jié)點的單鏈表,.,142,voidCreateList(LinkListL-next=NULL;/先建立一個帶頭結(jié)點的單鏈表,for(i=n;i0;-i)p=newLNode;scanf(/插入,.,143,試設(shè)計算法，將單鏈表中前m個結(jié)點和后n個結(jié)點進行互換，即將線性表(a1,a2,am,b1,b2,bn)改變成(b1,b2,bn,a1,a2,am)。,例2-6,算法設(shè)計:將(b1,b2,bn)從鏈表的當前位置上刪除之后再插入a1到之前，并將am設(shè)為表尾。,.,144,ta-next=NULL;tb-next=L-next;L-next=hb;,.,145,voidexchange(SLink/while/exchange,算法的時間復雜度為:,O(ListLength(L),if(ta/查詢表尾bn/if,修改指針,.,146,例2-7,試編寫算法，刪除單鏈表中“多余”的數(shù)據(jù)元素。,算法一對鏈表中當前考察的每個元素，刪除它之后的“值相同”的結(jié)點;,算法二將新表中尚未存在的“值相同”的結(jié)點插入到新的鏈表中。,.,147,voidpurge(SLink/whilep/purge,算法時間復雜度:O(ListLength2(n),.,148,voidpurge(SLink/繼續(xù)考察下一個結(jié)點/whilep/purge,算法時間復雜度:O(ListLength2(n),.,149,最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表,循環(huán)鏈表,和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。,有時還可以將頭指針設(shè)成指向尾結(jié)點。,.,150,voidexchange(SLink/查詢表尾bn修改指針/if/exchange,-next;,ha=ta-next;,循環(huán),ta-next=L-next;L-next=ha;ta-next-next=hb;L=ta;,.,151,typedefstructDuLNodeElemTypedata;/數(shù)據(jù)域structDuLNode*prior;/指向前驅(qū)的指針域structDuLNode*next;/指向后繼的指針域DuLNode,*DuLinkList;,雙向鏈表,雙向鏈表通常以循環(huán)鏈表的形式出現(xiàn),.,152,雙向循環(huán)鏈表,空表,非空表,.,153,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,p,s,插入,.,154,刪除,p-next=q-next;p-next-prior=p;deleteq;,p,q,.,155,一、有序表類型,二、有序鏈表類型舉例,三、一元稀疏多項式類型的定義,四、一元稀疏多項式類型的實現(xiàn),.,156,ADTOrdered_List數(shù)據(jù)對象:S=xi|xiOrderedSet，i=1,2,n,n0,集合中任意兩個元素之間均可以進行比較,數(shù)據(jù)關(guān)系:R=|xi-1,xiS,xi-1xi,i=2,3,n,基本操作:,ADTOrdered_List,.,157,LocateElem(L,e,對集合A而言，數(shù)據(jù)元素依值從小至大的順序插入。,可見，數(shù)據(jù)結(jié)構(gòu)改變了，解決問題的策略也應(yīng)作相應(yīng)地改變。,.,160,voidunion(List/union,GetElem(Lb,i,e);/取Lb中第i個數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和e相同的數(shù)據(jù)元素，則插入之,for(i=1;inext;succ=p-next;if(raL,ra-next=p;ra=p;,ra-next=NULL;,算法的時間復雜度為:O(L.length2),.,164,例2-9,試編寫算法，以有序表表示集合，試求C=AB。,則,設(shè)La=(a1,ai,an),Lb=(b1,bj,bm)Lc=(c1,ck,cm+n)且已由(a1,ai-1)和(b1,bj-1)歸并得(c1,ck-1),k=1,2,m+n,算法策略分析:,.,165,1初始化LC為空表；,操作步驟：,2分別從LA和LB中取得當前元素ai和bj；,3若aibj，則將ai插入到LC中，否則將bj插入到LC中(相等時只取一個)；,4重復2和3兩步，直至LA或LB中元素被取完為止；,5將LA表或LB表中剩余元素復制插入到LC表中。,.,166,voidMergeList(ListLa,ListLb,Listwhile(inext=pb;pb=Lb-next;Lb-next=La-next;La=Lb;/pb指向B的頭結(jié)點并構(gòu)成C的循環(huán)鏈,if(pa-datadata)/鏈接A的結(jié)點rc-next=pa;rc=pa;pa=pa-next;if(pa-data=pb-data)qb=pb;pb=pb-next;deleteqb;else/鏈接B的結(jié)點rc-next=pb;rc=pb;pb=pb-next;,.,170,線性表的基本操作在兩種存儲結(jié)構(gòu)中的時間性能比較:,O(1),O(1),O(1),O(n),O(1),O(1),O(1),O(n),O(1),O(n),O(1),O(1),O(1),O(n),O(n),O(n),.,171,O(n),O(n),O(1),O(n),O(1),O(n),O(n),O(n),O(n),O(n),鏈表結(jié)構(gòu)的特點:,1.鏈表是一種動態(tài)分配空間的存儲結(jié)構(gòu)，能更有效地利用存儲空間;,.,172,2.鏈表中以“指針”指示元素的后繼，因此在插入或刪除元素時不需要移動元素，但在基本操作中顯示不出它的優(yōu)勢;,引起問題的原因:,1.鏈表的長度是隱含值，給線性表的某些操作帶來不便;,2.在鏈表中，數(shù)據(jù)元素在線性表中的位序不明確，取而代之的是結(jié)點的“位置”;,3.由于鏈表是“順序存取”的結(jié)構(gòu)，給隨機存取元素和在表尾插入等操作帶來不便;,.,173,typedefstructLNode/結(jié)點結(jié)構(gòu)ElemTypedata;structLNode*next;*SLink;,/結(jié)構(gòu)定義,typedefstruct/鏈表結(jié)構(gòu)SLinkhead,/指向有序鏈表中的頭結(jié)點tail,/指向有序鏈表中最后一個結(jié)點curPtr;/指向操作的當前結(jié)點intlen,/指示有序鏈表的長度curpos;/指示當前指針所指結(jié)點的位序OrderedLinkList;,.,174,/基本操作接口(函數(shù)聲明),boolInitList(OrderedLinkList/InitList,.,175,boolGetPos(OrderedLinkListL,intpos)/若1posLengthList(L)，則移動當前指針/指向第pos個結(jié)點且返回函數(shù)值為TRUE,/否則不移動當前指針且返回函數(shù)值為FALSEif(posL.len)returnFALSE;if(posnext;L.curpos=1;while(L.curposnext;+L.curpos;returnTRUE;,.,176,boolLocateElem(OrderedLinkListL,ElemTypee,int(*compare)(ElemType,ElemType)/若有序鏈表L中存在和e相同的數(shù)據(jù)元素，則當前/指針指向第1個和e相同的結(jié)點，并返回TRUE，/否則當前指針指向第一個大于e的元素的前驅(qū)，/并返回FALSEL.current=L.head;L.curpos=0;while(L.current-next/指針后移，繼續(xù)查詢,.,177,if(L.current-next/當前指針所指后繼元素大于e/查找不成功/LocateElem,.,178,boolInsAfter(LinkList/表長增1,.,179,boolDelAfter(LinkList/DelAfter,.,180,在計算機中，可以用一個線性表來表示:P=(p0,p1,，pn),一元多項式,但是對于形如,S(x)=1+3x100002x20000,的多項式，上述表示方法是否合適？,.,181,一般情況下的一元稀疏多項式可寫成Pn(x)=p1xe1+p2xe2+pmxem其中：pi是指數(shù)為ei的項的非零系數(shù)，0e1e2em=n,可以下列線性表表示：（p1,e1）,(p2,e2),(pm,em)）,.,182,ADTPolynomial數(shù)據(jù)對象：數(shù)據(jù)關(guān)系：,抽象數(shù)據(jù)類型一元多項式的定義如下：,Dai|aiTermSet,i=1,2,.,m,m0TermSet中的每個元素包含一個表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù),R1|ai-1,aiD,i=2,.,n且ai-1中的指數(shù)值ai中的指數(shù)值,.,183,CreatPolyn(/系數(shù)intexpn;/指數(shù)term,ElemType;,typedefOrderedLinkListpolynomial;/用帶表頭結(jié)點的有序鏈表表示多項式,結(jié)點的數(shù)據(jù)元素類型定義為:,.,186,StatusCreatPolyn(polynomaile.coef=0.0;e.expn=-1;SetCurElem(h,e);/設(shè)置頭結(jié)點的數(shù)據(jù)元素,for(i=1;idata=e;s-next=NULL;Q.rear-next=s;/修改尾結(jié)點的指針Q.rear=s;/移動隊尾指針+Q.length;/隊列長度增1returnTRUE;,.,236,p,p,Q.rear,出隊列操作,.,237,boolDeQueue(Queue,p=Q.front-next;e=p-data;/返回被刪元素Q.front-next=p-next;/修改頭結(jié)點指針deletep;/釋放被刪結(jié)點returnTRUE;,if(Q.front=Q.rear)/隊列為空returnFALSE;,.,238,二、循環(huán)隊列,隊列的順序映象,typedefstructQElemType*elem;/存儲空間基址intrear;/隊尾指針intfront;/隊頭指針intqueuesize;/允許的最大存儲空間Queue;,/結(jié)構(gòu)定義,/基本操作接口(函數(shù)聲明),.,239,Q.elem,e,f,g,Q.elem,Q.elem,h,j,.,240,boolInitQueue(SqQueueQ.elem=newQElemTypemaxsize;/為循環(huán)隊列分配存儲空間if(!Q.elem)returnFALSE;/存儲分配失敗Q.queuesize=maxsize;Q.front=Q.rear=0;returnTRUE;,.,241,boolDeQueue(Queue,e=Q.elemQ.front;Q.front=(Q.front+1)%Q.queuesize;returnTRUE;,.,242,boolEnQueue(Queue,if(Q.rear+1)%Q.queuesize=Q.front)returnFALSE;,.,243,循環(huán)隊列應(yīng)用舉例,編寫“逐行輸出前n行二項式系數(shù)”的算法。,二項式系數(shù)表第1行11第2行121第3行1331第4行14641,設(shè)第i-1行的值:(a0=0)a1,ai,(ai+1=0),0,則第i行的系數(shù):bj=aj-1+aj,j=1,2,i,0,.,244,利用“循環(huán)隊列”計算二項式系數(shù)的過程,0,1,1,輸出:,1,1,1,1,2,2,1,1,0,1,1,0,0,1,1,1,1,1,2,3,2,2,3,1,1,3,3,1,0,1,1,0,doDeQueue(Q,s);GetHead(Q,e);if(e!=0)cout0)行QueueQ;InitQueue(Q,n+2);EnQueue(Q,0);/添加行界值EnQueue(Q,1);EnQueue_Sq(Q,1);k=1;while(kn)EnQueue(Q,0);/行界值“0”入隊列do/輸出第k行，計算第k+1行while(e!=0);k+;/while/yanghui,.,246,DeQueue(Q,e);/行界值“0”出隊列while(!QueueEmpty(Q)/單獨處理第n行的值的輸出DeQueue_Sq(Q,e);coute0)/ifreturn0;/S中不存在與T相等的子串/Index,n=StrLength(S);m=StrLength(T);i=pos;,while(i=n-m+1)/while,SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)+i;elsereturni;,.,269,S串,T串,V串,V串,sub,news串,sub,tn,實現(xiàn)置換函數(shù)Replace(S,T,V)算法的基本思想為：,.,270,voidreplace(String/剩余串Concat(S,news,sub);,n=StrLength(S);m=StrLength(T);pos=1;StrAssign(news,NullStr);i=1;,.,271,串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。,在線性表的基本操作中，大多以“單個元素”作為操作對象；而在串的基本操作中，通常以“串的整體”作為操作對象。,串的基本操作和線性表有很大差別。,.,272,在早期的程序設(shè)計語言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲此串的串值，即字符序列即可。之后在多數(shù)非數(shù)值處理的程序中，串均以變量的形式出現(xiàn)，因此作為一個數(shù)據(jù)類型也就存在一個存儲表示和實現(xiàn)的問題。,.,273,一、串的定長順序存儲表示,二、串的堆分配存儲表示,三、串的塊鏈存儲表示,.,274,用一組地址連續(xù)的存儲單元存儲串值。,例如，在C語言中可以定義串為charstr10;,這表示，為串變量str分配了一個固定長度為10的數(shù)組空間，而str的實際長度可以在這個定義范圍內(nèi)隨意，但最大長度不得超過9(串的結(jié)束符0也占一個字符的空間，但它不屬串值本身)。,.,275,voidConcat(charT,charS1,charS2)/T串為由S2串聯(lián)接到S1串構(gòu)成的新串j=0;k=0;while(S1j!=0)Tk+=S1j+;/復制串S1j=0;while(S2j!=0)Tk+=S2j+;/接著復制串S2Tk=0;/置結(jié)果串T的結(jié)束標志/Concat,.,276,boolSubString_Sq(charSub,charS,intpos,intlen)/以Sub返回串S中第pos個字符起長度為len的子串if(pos1)returnFALSE;/SubString_Sq,k=0;while(klen,i=0;while(iStrlength(T),T串,T串,或者繼續(xù)重復新一輪匹配過程，如此反復直至(i+j)Strlength(S)表明匹配不成功,.,279,仍以一組地址連續(xù)的存儲空間存儲串值，只是串變量的存儲空間是在程序執(zhí)行過程中利用new進行動態(tài)分配得到的。程序中出現(xiàn)的所有串變量的值都存儲在一個稱之為“堆”的共享空間中。此時的串操作仍基于“字符序列的復制”進行。C語言中提供的串類型就是以這種存儲方式實現(xiàn)的。,.,280,voidConcat(char*T,char*S1,char*S2)/T串為由S2串聯(lián)接到S1串構(gòu)成的新串slen1=StrLength(S1);slen2=StrLength(S2);T=newcharslen1+slen2;j=0;k=0;while(S1j!=0)Tk+=S1j+;/復制串S1j=0;while(S2j!=0)Tk+=S2j+;/接著復制串S2Tk=0;/置結(jié)果串T的結(jié)束標志/Concat,.,281,boolStrInsert(char*S,intpos,char*T)/在串S的第pos(1posStrLength(S)1)個字符/之前插入串Tslen=StrLength(S);tlen=StrLength(T);/求串長charS1slen+1;/設(shè)S1為輔助串空間if(posslen+1)returnFALSE;/插入位置不合法;if(tlen0)/StrInsert,/T非空，則為S重新分配空間并插入T,.,282,i=0;while(S1i=Si)!=0)i+;/暫存串SS=newcharslen+tlen+1;/重新分配空間for(i=0,k=0;ib)max=a;,if(ab)max=a;,284,.,289,假設(shè)該正文串只占一頁，起始行號為100，起始的存儲地址為200,則其行表如下:,284,19,2,.,290,在正文編輯程序中設(shè)立頁指針、行指針和字符指針，分別指示當前操作的頁、行和字符。如果在某行內(nèi)插入或刪除若干字符，則要修改行表中該行的長度，若該行長度因插入而超出了原分配給它的存儲空間，則要為該行重新分配存儲空間，并修改該行的起始位置。,.,291,1.熟悉串的七種基本操作的定義，并能利用這些基本操作來實現(xiàn)串的其它各種操作的方法。2.了解串的各種存儲結(jié)構(gòu)的特點及其適用場合。,.,292,第五章數(shù)組和廣義表,.,293,5.1數(shù)組的類型定義,5.3稀疏矩陣的壓縮存儲,5.2數(shù)組的順序表示和實現(xiàn),5.3廣義表的類型定義,5.4廣義表的表示方法,5.5廣義表操作的遞歸