11.1為什么學習數(shù)據(jù)結構

1.2數(shù)據(jù)結構的有關概念和術語

1.3算法和算法描述

1.4算法的時空效率分析方法

1.5小結與習題數(shù)據(jù)結構概述21.1為什么要學習數(shù)據(jù)結構

研究數(shù)據(jù)的特性、數(shù)據(jù)間的相互關系及其對應的存儲表示，并利用這些特性、關系和存儲表示設計出相應的算法和程序。為什么要學習數(shù)據(jù)結構？計算機處理的數(shù)據(jù)量越來越大；數(shù)據(jù)的類型越來越多；數(shù)據(jù)的結構越來越復雜。解決一個問題時幾個步驟：抽象出一個適當?shù)臄?shù)學模型，設計或選擇一個解決此類數(shù)學模型的算法，編寫程序進行調(diào)試、測試，直至得到最終的解答。3【例1-1】學生信息檢索問題。學生信息包括學號、姓名、性別和成績等，一行為一個記錄，表示一個學生的信息（也稱為一個數(shù)據(jù)元素），一列為一個屬性。學號姓名性別成績20050601張三男51820050602李一寧女49620050603吳磊女581.5……………20050636梁磊男529線性關系:對線性表的主要操作有查找、修改、插入和刪除等。

4【例1-2】某大學專業(yè)設置問題。顯然這種關系用“樹”型結構來表示更形象。通常用來表示結點的分層組織，結點之間是一對多的關系。對樹型結構主要操作有查找、修改、插入和刪除等。**大學機械工程系電子工程系計算機與信息工程系機械制造材料科學電子應用電氣自動化計算機應用與維護計算機應用與維護5【例1-3】通信網(wǎng)絡問題。帶圓圈的頂點表示城市，頂點和頂點之間的連線和數(shù)據(jù)表示城市之間的通信線路及其長度。，各頂點之間是多對多的關系，是網(wǎng)狀結構，也稱為圖型結構，操作有：求從一個頂點到另一個頂點的最短路徑等。由以上三個例子可見，描述這類非數(shù)值計算問題的數(shù)學模型有線性表、樹、圖等。所有的計算機系統(tǒng)軟件和應用軟件都要用到各種類型的數(shù)據(jù)結構。

B

CDFEA6045404230408065322661.2數(shù)據(jù)結構的有關概念和術語

1.2.1基本概念和術語1．數(shù)據(jù)（Data）是描述客觀事物的數(shù)值、字符以及所有能被輸入到計算機并能被計算機識別、存儲和處理的符號的集合?？陀^事物包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。數(shù)值數(shù)據(jù)：整數(shù)、實數(shù)或復數(shù)；非數(shù)值數(shù)據(jù)：字符、文字、圖形、圖像和聲音等。2．數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結點、頂點、記錄等。數(shù)據(jù)項：數(shù)據(jù)結構中討論的最小單位。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（DataItem）組成。例如，學生信息表的每一個數(shù)據(jù)元素就是一個學生記錄，它包括學生的學號、姓名、性別、成績等數(shù)據(jù)項。73．數(shù)據(jù)對象（DataObject）是具有相同性質(zhì)數(shù)據(jù)元素的集合。4．數(shù)據(jù)類型(DataType)

在用高級語言編寫的程序中，每個變量、常量或表達式都有一個它所屬的確定的數(shù)據(jù)類型。5．抽象數(shù)據(jù)類型（AbstractDataType，簡稱ADT）是指基于邏輯關系的數(shù)據(jù)類型以及定義在該類型之上的一組操作。ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：（數(shù)據(jù)對象的定義）數(shù)據(jù)關系：（數(shù)據(jù)關系的定義）基本操作：（基本操作的定義）}8【例1-4】線性表的抽象數(shù)據(jù)類型可描述如下：ADTLinear_list{數(shù)據(jù)元素所有ai屬于同一數(shù)據(jù)對象，i=1，2，…，n（n≥1）邏輯結構所有數(shù)據(jù)元素ai存在次序關系（ai，ai+1），a1無前驅(qū)，an無后繼。操作

/*設L為Linear_list類型的線性表*/InitList（L）；/*建立一個空的線性表L*/Length（L）；/*求線性表L的長度*/GetElement（L，i）；/*取線性表L中的第i個元素*/Locate（L，x）；/*確定元素x在線性表L中的位置*/Insert（L，i，x）；/*在線性表L中的第i個位置處插入數(shù)據(jù)元素x*/Delete（L，i）；/*刪除表L中第i個位置的元素*/……}；/*ADTLinear_list*/91.2.2數(shù)據(jù)結構定義數(shù)據(jù)結構（DataStructure）是指互相之間存在著一種或多種關系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的關系稱為結構。數(shù)據(jù)的結構包括邏輯結構和物理結構。（1）邏輯結構：是數(shù)據(jù)元素之間的相互邏輯關系，它與數(shù)據(jù)的存儲無關，是獨立于計算機而存在。數(shù)據(jù)結構是由兩個集合構成的一個二元組：Data_Structure(D，R))Data_Structure是一種數(shù)據(jù)結構，它由同屬一個數(shù)據(jù)對象的數(shù)據(jù)元素的有限集合D和D上二元關系的有限集合R組成。其中：D={di|1≦i≦n,n≧1}R={rj|1≦j≦m,m≧1}10di表示第i個數(shù)據(jù)元素，rj表示第j個關系。D上二元關系R是序偶的集合。對于R中的任一序偶<x,y>(x,y∈D)，x稱為序偶的第一元素，y稱為序偶的第二元素，又稱序偶的第一元素是第二元素的直接前驅(qū)；第二元素為第一個元素的直接后繼。【例1-5】樹型結構中的圓圈代表數(shù)據(jù)元素，帶箭頭的連線表示元素之間的關系，試用二元組表示法表示其邏輯結構。解：二元組為(D,R)其中，D={A,B,C,E,F,G,H,I,J};R={<A,B>,<A,C>,<A,E>,<B,F>,<B,G>,<E,H>,<E,I>,<E,J>}ABCEFGHIJ11通常有下列四種基本的結構：a.集合結構。集合是元素關系極為松散的一種結構。b.線性結構。線性結構的邏輯特征是：若結構是非空集，則有且僅有一個開始結點和一個終端結點，并且所有結點都最多只有一個直接前驅(qū)和一個直接后繼。c.樹型結構。該結構的數(shù)據(jù)元素之間存在著一對多的關系。d.圖型結構。該結構的數(shù)據(jù)元素之間存在著多對多的關系，圖型結構也稱作網(wǎng)狀結構。（2）物理結構（或存儲結構）是數(shù)據(jù)結構在計算機中的表示（又稱映像），它包括數(shù)據(jù)元素的機內(nèi)表示和關系的機內(nèi)表示。具體實現(xiàn)的方法有順序、鏈接、索引、散列等多種，數(shù)據(jù)的具體操作與存儲結構有很密切的聯(lián)系。數(shù)據(jù)結構作為一門學科主要研究數(shù)據(jù)的各種邏輯結構和存儲結構，以及對數(shù)據(jù)的各種操作。同時還要考慮執(zhí)行算法時的時間和空間效率。121.3算法和算法描述⑴有窮性。一個算法必須在有窮步之后結束，即必須在有限時間內(nèi)完成。⑵確定性。算法的每一步必須有確切的定義，無二義性。⑶可行性。算法中的每一步都可以通過已經(jīng)實現(xiàn)的基本運算的有限次執(zhí)行得以實現(xiàn)。⑷輸入。一個算法具有零個或多個輸入，這些輸入取自特定的數(shù)據(jù)對象集合。⑸輸出。一個算法具有一個或多個輸出，這些輸出同輸入之間存在某種特定的關系。1.3.1算法與算法特性算法（Algorithm）是對特定問題求解步驟的一種描述，是指令的有限序列。一個算法應該具有下列特性：13一個好的算法通常要達到以下的要求：正確。執(zhí)行結果應當滿足預先規(guī)定的功能和性能要求。可讀。應當思路清晰、層次分明、簡單明了、易讀易懂。健壯。當輸入不合法數(shù)據(jù)時，應能作適當處理，不至引起嚴重后果。高效。有效使用存儲空間和有較高的時間效率。1.3.2算法描述最簡單的方法是使用自然語言，其優(yōu)點是簡單且便于人們對算法的閱讀；缺點是轉(zhuǎn)換成高級語言困難。類C語言忽略高級程序設計語言中一些嚴格的語法規(guī)則與描述細節(jié)，因此它比程序設計語言更容易描述和被人理解，比自然語言更接近程序設計語言，很容易被轉(zhuǎn)換成高級語言。14本書對所用類C語言作如下約定：1．問題的規(guī)模用MAXSIZE#defineMAXSIZE602．預定義常量和類型：#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1typedefintStatus;3．數(shù)據(jù)結構（存儲結構）的表示用類型定義（typedef）描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時自行定義。例1.學生信息檢索系統(tǒng)中，用一維數(shù)組作存儲n個學生的信息，數(shù)組中的數(shù)據(jù)元素有4個域：學號、姓名、性別和成績：typedefstructstd_info{longintNum;/*學號域*/charName[8];/*姓名域*/charSex;/*性別域*/floatScore;/*成績域*/}ElemType;154．基本操作的算法都用以下形式的函數(shù)描述函數(shù)類型函數(shù)名(函數(shù)參數(shù)表){/*算法說明*/語句序列；}/*函數(shù)名*/5．C語言中的常用語句賦值（=）、選擇（if、if…else、switch…case…default）、循環(huán)（for、while、do…while）、結束（return、break、continue、exit）、輸入和輸出等語句。6．基本運算和基本函數(shù)基本運算有+、-、*、/、%、->、&&和||等。基本函數(shù)有max、min、abs、fabs、eof等。16

例設某班級有n個學生，編寫算法，查找班級中成績最高的學生，并輸出該學生的所有信息。分析：，算法依次查看數(shù)組中的元素，并保存當前最高成績及其下標。使用類C語言編寫：intlargest（ElemTypeS[MAXSIZE]，intn）{floatcurrlarge=0.0;inti,j=0;/*賦初值*/for（i=0;i<n;i++）/*進入循環(huán)*/if(S[i].Score>currlarge){j=i;currlarge=S[i].Score;}printf(“%10ld%10s%10c%10f\n”,S[j].Num,S[j].name,S[j].Sex,S[j].Score);}/*largest*/typedefstructstd_info{longintNum;charName[8];charSex;floatScore;}ElemType;171.4算法時空效率分析方法評價算法的性能用時間復雜度與空間復雜度來度量。1、算法的時間復雜度算法的時間復雜度（Timecomplexity）是指算法轉(zhuǎn)換為程序后(這里仍稱為算法)在計算機上從開始運行到結束所需要的時間。運行所需要的時間取決于下列因素：⑴硬件的速度。與硬件的配置高低有關。⑵書寫程序的語言。語言的級別越高，其執(zhí)行效率就越低。⑶編譯程序所生成目標代碼的質(zhì)量。⑷依據(jù)算法所選用的策略。⑸問題的規(guī)模。一般情況下，處理的數(shù)據(jù)量越大，執(zhí)行的時間相對也越長。18通常的做法是：不考慮不確定的情況，而以算法中簡單操作重復執(zhí)行的次數(shù)作為算法的時間度量。為此，一個特定算法的運行時間長短就只依賴于問題的規(guī)模n，或者說它是問題規(guī)模n的函數(shù)f(n)?！纠?-7】求累加求和intsum(intb[]，intn）｛intsum=0;/*第1條定義并賦初值語句執(zhí)行1次*/for（inti=0；i<n；i++）/*3n+2次*/sum+=b[i];/*n次*/returnsum;｝/*返回語句執(zhí)行1次*/19要精確地計算f(n)是困難的，引入漸進時間復雜度在數(shù)量上估計一個算法的執(zhí)行時間。算法時間的度量記作T(n)=Ο(f(n))它表示隨問題的規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)相同。使用大Ο記號，Ο(f(n))稱為算法的漸進時間復雜度（AsymptoticTimeComplexity），簡稱時間復雜度。例如，一個程序的實際執(zhí)行時間為

T(n)＝2.7n3+3.8n2+5.3。則T(n)＝Ο(n3)。20【例1-8】求下面程序段的時間復雜度。

s=0;for(j=1;j<=n;j++)for(x=1,k=1;k<=n;k++){x=x*k;s+=x;}解：該算法中“s=0;”的頻度為1，后面由兩個“for”語句構成了一個二重循環(huán)結構，其內(nèi)循環(huán)體執(zhí)行的頻度為n2，用最高數(shù)量級n2的表示，則該程序段的時間復雜度為O(n2)。通常將稱Ο(1)為常數(shù)階，Ο(n)為線性階，O(n2)為平方階。算法還可能呈現(xiàn)的復雜度有：對數(shù)階Ο(log2n)，指數(shù)階Ο(2n)等，不同數(shù)量級時間復雜度的關系有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)2101248163264128256nT(n)10245122561286432168421012481632641282565121024nnlog2n2nn2n3nlog2n圖1-7常見函數(shù)的增長率222、算法的空間復雜度一個程序的空間復雜度（Spacecomplexity）是指程序運行從開始到結束所需的最大存儲空間。包括以下三部分：（1）輸入數(shù)據(jù)所占空間；（2）程序本身所占空間；（3）輔助變量所占空間。只需要分析輔助變量所占空間即可。通常以算法的空間復雜度作為算法所占用存儲空間的量度。定義：S(n)=O(g(n))09三月2024第23頁

例2:奇數(shù)序列(1,3,5,7,9,11)

例1:字母序列(A,B,C,D,E,F)

例3：隨機的學生成績序列2.1線性表的邏輯結構

2.1.1線性表的定義問題的引入學

號姓名性

別成績20050601張三男51820050602李一寧女49620050603吳磊女581.5……………20050636梁磊男52909三月2024第24頁3.舉例：A=(１,３,５,７,９)

該線性表的長度為5B=(a1,a2,a3,···，am)

該線性表的長度為mC=(b1,b2,b3,···，bn)

該線性表的長度為n1.定義：具有相同類型的n個數(shù)據(jù)元素組成的有限序列。記為(a1，a2，…ai-1，ai，ai+1，…an)

其中n為表長，當n=0時稱為空表。

關鍵點:

(1)相同類型(2)線性表的長度n(n≥0)(3)有限序列09三月2024第25頁1.線性表的長度線性表中所包含的元素個數(shù)n(n≥0)；2.空線性表線性表的長度n=0；3.（直接）前驅(qū)和后繼在相鄰元素中，ai

是ai+1的前驅(qū)（第一個元素a1無前驅(qū)）在相鄰元素中，ai+1是ai的后繼（最后一個元素an無后繼）4.舉例：長度為10的奇數(shù)序列(1,3,5,7,9,11,13,15,17,19)

線性表可以看作是除第一個元素無前驅(qū)，最后一個元素無后繼外，其余元素都有唯一的直接前驅(qū)和直接后繼的一組元素構成的有序集合。09三月2024第26頁通常將ai的數(shù)據(jù)類型抽象為ElemType。例如，學生信息表中數(shù)據(jù)元素可以定義為一個結構類型：typedefstructstd_info{longintNum;/*學號域*/

charName[8];/*姓名域*/

charSex;/*性別域*/

floatScore;/*成績域*/}ElemType;學

號姓名性別成績20050601張三男51820050602李一寧女49620050603吳磊女581.5……………20050636梁磊男52909三月2024第27頁2.1.2線性表的基本操作

⑴

線性表初始化：Init_List(L)；

——建立一個空的線性表；⑵

求線性表的長度：Length_List(L)；

——返回線性表中數(shù)據(jù)元素的個數(shù)。⑶

取表中元素：Get_Elem(L,i)；

——返回線性表L中第ｉ個數(shù)據(jù)元素的值或地址。⑷

按值查找：Locate_List(L,x)；

——在表L中查找值為ｘ的數(shù)據(jù)元素的位置。⑸

插入操作：Insert_List(L,i,x)；——在線性表L的第i個位置上插入一個值為x的數(shù)據(jù)元素。⑹

刪除操作：Delete_List(L,i)；

——在線性表L中刪除序號為i的數(shù)據(jù)元素。

09三月2024第28頁ADTList{數(shù)據(jù)對象：D={ai|ai∈ELEMTPi=1,2,·

·

·,n,n≥0}數(shù)據(jù)關系：R={<ai,ai+1>|ai,ai+1∈D

i=1,2,·

·

·,n-1,n≥0}基本操作：InitList（&L）：線性表的初始化；ListLength（L）：求線性表的長度；ListInsert（&L,i,e）：

在第i個位置插入元素e；ListDelete（&L,i,e）：

在線性表第i個位置刪除元素e；···

···

···

···

···}09三月2024第29頁2.2線性表的順序存儲結構及運算實現(xiàn)2.2.1順序表

是指在內(nèi)存中用一塊地址連續(xù)的存儲空間按順序存儲線性表的各個數(shù)據(jù)元素。特點：采用連續(xù)的空間來存儲線性表——順序表。順序存儲結構可描述如下：typedefstruct{ElemTypeelem[MAXSIZE];intlength;

/*線性表長度*/}SeqList;

data數(shù)組下標a1a2…ai-1aiai+1…an…12…i-1ii+1…length...MAXSIZE-1bb+d……b+(i-1)d…b+(length-1)d存儲地址09三月2024第30頁線性表的長度及元素在線性表中的位置

已知該線性表的首地址(a1)為Ｂ，那么任意一個元素的地址為:

ai＝Ｂ＋(i-1)×d（其中d為該類型元素所占空間）

定義一個順序表：SeqList*L；順序表的長度為L->length;數(shù)據(jù)元素是L->data[1]～L->data[L->length]。因為在C語言中數(shù)組的下標是從0開始的，為了與線性表中元素的序號保持一致，不使用數(shù)組下標為“0”的單元，下標的取值范圍1≤i≤MAXSIZE-1。

data數(shù)組下標a1a2…ai-1aiai+1…an…12…i-1ii+1…length...MAXSIZE-1bb+d……b+(i-1)d…b+(length-1)d存儲地址09三月2024第31頁(1)將an～ai按從后向前的順序向下移動，為新元素讓出位置；(2)將x置入空出的第i個位置；(3)修改length值。Length+1

2.2.2順序表上基本運算的實現(xiàn)

1．順序表的初始化--構造一個空表

voidinit_SeqList(SeqList*L){L->length=0;}2.插入運算a1a2…ai-1aiai+1…ana1a２…ai-1

xaiai+1…an

12…

i-1ii+1…nn+109三月2024第32頁【算法2.2】在順序表的第i個位置上插入一個值為x的新元素。

intInsert_SeqList(SeqList*L，inti，ElemTypex){intj;if(L->length==MAXSIZE-1){printf(＂表滿＂);returnOVERFLOW;}

if(i<1||i>L->length+1)

/*檢查插位置的正確性*/{printf(＂位置錯＂);returnERROR;}

for(j=L->length;j>=i;j--)L->elem[j+1]=L->elem[j];L->elem[i]=x;

L->length++;returnOK;/*插入成功，返回*/}09三月2024第33頁8660787555909055786086例如：插入元素75，插入位置為4，則90和55兩個元素應向后移。算法說明：在線性表中，按照某順序查找與其給定一致的元素是否存在，如果存在返回其位置，否則給出相關信息。i的取值范圍為：1≤i≤n+1即有n＋1個位置可以插入。09三月2024第34頁插入算法的時間性能分析：

在第i個位置上插入x，從ai到an都要向下移動一個位置，共需要移動n－i＋1個元素，而i的取值范圍為：1<=i<=n+1，即有n＋1個位置可以插入。設在第i個位置上作插入的概率為Pi，則平均移動數(shù)據(jù)元素的次數(shù)：設：Pi=1/(n+1)，即為等概率情況，則：這說明：在順序表上做插入操作需移動表中一半的數(shù)據(jù)元素。顯然時間復雜度為Ｏ(n)。09三月2024第35頁3.刪除運算刪除第i個元素，i的取值范圍為：1≤i≤n。運算的步驟為：先將ai+1～an依次向上移動，然后將length值減1。a1a2…ai-1aiai+1…ana1a２…ai-1ai+1…an

12…

i-1ii+1n-1nn+1刪除算法intDelete_SeqList(SeqList*L,inti){intj;if(i<1||i>L->length){printf(＂不存在第i個元素＂);returnERROR;}for(j=i;j<=L->length-1;j++)L->elem[j]=L->elem[j+1];L->length--;returnOK;}09三月2024第36頁9055786086例如：刪除元素75，則90和55兩個元素應向前移。86605590刪除第i個元素時，其后面的元素ai+1～an都要向上移動一個位置，共移動了n-i個元素，所以平均移動數(shù)據(jù)元素的次數(shù)：在等概率情況下，pi=1/n，則：這說明順序表上作刪除運算時大約需要移動表中一半的元素，顯然該算法的時間復雜度為Ｏ(n)。09三月2024第37頁4．按值查找

【算法2.4】在線性表中查找與給定值x相等的數(shù)據(jù)元素。

intLocation_SeqList(SeqList*L,ElemTypex){inti=1;while(i<=L->length&&L->elem[i]!=x)i++;if(i>L->length)return-1;/*查找失敗*/

elsereturni;/*返回x的存儲位置*/}時間復雜度分析：當

a1==x時，只比較一次；當

an==x時需要比較

n次；平均比較次數(shù)為（n+1）/2，所以時間復雜度為O(n)，即時間復雜度與表長有關。

09三月2024第38頁【例2-3】有兩個順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也是從小到大排列。算法的時間復雜度是O(m+n)，voidmerge(SeqList*A,SeqList*B,SeqList*C){inti,j,k;i=1;j=1;k=1;while(i<=A->length&&j<=B->length)if(A->elem[i]<=B->elem[j])C->elem[k++]=A->elem[i++];elseC->elem[k++]=B->elem[j++];while(i<=A->length)C->elem[k++]=A->length[i++];while(j<=B->length)C->elem[k++]=B->elem[j++];C->length=A->length+B->length;}09三月2024第39頁2.3線性表的鏈式存儲和運算實現(xiàn)

問題的引入：1.順序存儲結構必須在程序編譯前就規(guī)定好數(shù)組元素的多少(即數(shù)組長度)，事先難估計，多了造成浪費存儲空間，少了不夠用；2.順序存儲結構在查找和刪除運算中可能需要大量移動元素，降低程序執(zhí)行效率?；谏鲜鰞牲c，需要引入鏈式存儲結構。注意：與順序存儲結構的不同點是內(nèi)存位置不一定相鄰，即每一個數(shù)據(jù)項都有一個鏈接字段，用來存放下一個數(shù)據(jù)項的地址，形成鏈表結構。09三月2024第40頁鏈式存儲結構結點（數(shù)據(jù)項）最少有兩個域：數(shù)據(jù)域和指針域。采用不連續(xù)空間存儲線性表，使用指針指向下一元素的位置。2.3.1單鏈表

H…a4120…a5NULL…a1240…a3110…a2210…110…120130…160200…210…240

160如果用邏輯狀態(tài)圖表示a1a2an∧···H1datanext結點結構數(shù)據(jù)域指針域∧H2空單鏈表

09三月2024第41頁鏈式存儲結構特點：1.使用任意的存儲單元存儲線性表，不需要空間連續(xù)；2.通過前一個結點得到后一個結點的地址，使它們前后之間建立一一對應的關系（即：前趨和后繼的關系）。結點定義如下：

typedefstructnode{ElemTypedata;/*數(shù)據(jù)域*/

structnode*next;/*指針域*/}LNode，*LinkList；datanext數(shù)據(jù)域指針域【說明】ELEMTP為通用數(shù)據(jù)類型；

next為指向結構體類型的指針，指示下一結點（后繼，除最后一個元素）所在的位置。09三月2024第42頁頭指針變量定義方法如下：LinkListH;算法中用到指向某結點的指針變量時按如下格式進行說明：LNode*p；則語句：

p=(LinkList)malloc(sizeof(LNode))；

聲明后，系統(tǒng)會分配足夠的空間來容納Linklist結構，同時指針p指向新的內(nèi)存位置。pp所指的結點為*p，*p的類型為LNode型，該結點的數(shù)據(jù)域為(*p).data或p->data，指針域為(*p).next或

p->next。free(p)則表示釋放指針p所指向的結點空間。09三月2024第43頁2.3.2單鏈表基本運算的實現(xiàn)

1.建立單鏈表

(1)在鏈表的頭部插入結點建立單鏈表。如（16，20，65，12）的鏈表的建立過程。12∧65H∧H12∧H2012∧65H162012∧65H09三月2024第44頁【算法2.6】在鏈表的頭部插入結點建立單鏈表。

LinkListCreat_LinkList1()

{LinkListH=(LinkList)malloc(sizeof(LNode));/*生成頭結點*/

H->next=NULL；/*空表*/

LNode*s;

intx;/*設數(shù)據(jù)元素的類型為int*/

scanf(＂%d＂,&x);

while(x!=-1)

{s=(LinkList)malloc(sizeof(LNode));

s->data=x;

s->next=H->next;H->next=s;

scanf(＂%d＂,&x);}

returnH;}

09三月2024第45頁(2)在單鏈表的尾部插入結點建立單鏈表。如（16，20，65，12）的鏈表的建立過程。

∧HrHr16∧Hr1620∧Hr162065∧rH16206512∧09三月2024第46頁【算法2.7】在鏈表的尾部插入結點建立單鏈表。LinkListCreat_LinkList2(){LinkListH=(LinkList)malloc(sizeof(LNode));

H->next=NULL；/*空表*/LNode*s,*r=H;intx;/*設數(shù)據(jù)元素的類型為int*/scanf(＂%d＂,&x);while(x!=-1){s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=r->next;r->next=s;r=s;/*r指向新的尾結點*/

scanf(＂%d＂,&x);}returnH;}

09三月2024第47頁2.求表長

算法思路：設一個指針ｐ和計數(shù)器ｊ，初始化使ｐ指向頭結點H，ｊ=0。若ｐ所指結點還有后繼結點，ｐ向后移動，計數(shù)器加1，重復上述過程，直到p->next==NULL為止?！舅惴?.8】設H是帶頭結點的單鏈表，求帶頭結點單鏈表的表長。

StatusLength_LinkList(LinkListH){LNode*p=H;

intj=0;while(p->next){p=p->next;j++；}returnj;}H16206512∧09三月2024第48頁按序號查找第

k個數(shù)據(jù)元素

LinkListGet_LinkList(LinkListH,intk);{LNode*p=H;

intj=0;while(p->next!=NULL&&j<k){p=p->next;j++;}if(j==k)returnp;elsereturnNULL;}

60765590∧

85pH例如：i=3:當p指向85時，j=1；p指向60時，j=2；p指向76時，j=3；退出循環(huán)。例如：k=6。當p指向85時，j=1；……當p指向90時，j=5；再執(zhí)行p=p->next時，

p=NULL，退出循環(huán)?！緯r間復雜度均為O(n)09三月2024第49頁鏈表中查找x的算法實現(xiàn)

LNode*Locate_LinkList(LinkListH,ElemTypex){LNode*p=H->next;while(p!=NULL&&p->data!=x)p=p->next;returnp;}60765590∧

85pL例如：查找76，p指向76結點時，退出while循環(huán)，返回p指向的結點?！緯r間復雜度均為O(n)09三月2024第50頁4．插入操作設p指向單鏈表中某結點，s指向待插入的新結點，將*s插入到*p的后面。

p

xs①②

xspq②①③①

s->next=p->next;②p->next=s;

將新結點*s插入到*p的前面，在插入操作前首先要找到*p的前驅(qū)*q，然后再將*s插入到*q之后。

q=H;while(q->next!=p)q=q->next;s->next=q->next;q->next=s;09三月2024第51頁【算法2.11】將新結點s插入到第i個結點的位置上，即插入到ai-1與ai之間。算法思路：(1)查找第i-1個結點；若存在繼續(xù)(2)，否則結束；(2)創(chuàng)建新結點；(3)將新結點插入，結束。

…Hai-1xai×p①②s③④…09三月2024第52頁intInsert_LinkList(LinkListH,inti,ElemTypex)

/*在單鏈表H的第i個位置上插入值為x的元素*/

{LNode*p,*s;

p=Get_LinkList(H,i-1);

if(p==NULL)

{printf(＂插入位置i錯＂);returnERROR;}

else{

s=(LinkList)malloc(sizeof(LNode));

s->data=x;

s->next=p->next;

p->next=s；

returnOK;

}/*Insert_LinkList*/

時間復雜度為O(n)

09三月2024第53頁5.刪除操作

【算法2.12】刪除鏈表中第i個結點。算法思路：(1)查找第i-1個結點；若存在，則繼續(xù)(2)，否則結束；(2)若存在第i個結點則繼續(xù)(3)，否則結束；(3)刪除第

i個結點，結束。

①

q->next=p->next;②free(p);

x

pq①②…Hai-1ai+1p①②q③④…ai××釋放到存儲池09三月2024第54頁intDel_LinkList(LinkListH，inti)/*刪除單鏈表H上的第i個數(shù)據(jù)結點*/{LinkListp,q;p=Get_LinkList(H,i-1);

if(p==NULL){printf(＂第i-1個結點不存在＂);returnERROR;}else{if(p->next==NULL){printf(＂第i個結點不存在＂);returnERROR;}else{q=p->next;/*q指向第i個結點*/

p->next=q->next;

free(q);returnOK;}}/*Del_LinkList*/

時間復雜度為O(n)

09三月2024第55頁從上面的討論可以看出：

(1)

在單鏈表上插入、刪除一個結點，必須知道其前驅(qū)結點。

(2)單鏈表不具有按序號隨機訪問的特點，只能從頭指針開始依次進行訪問。

(3)鏈表上實現(xiàn)的插入和刪除運算，不用移動結點，僅需修改指針。

考慮的幾個問題：(1)如果在鏈表中第i個結點后插入一個值為y的結點，如果i不存在，則把結點插在表尾。如何實現(xiàn)？(2)如果在不帶頭結點的鏈表中第i（i>=1）個結點前插入一個值為y的結點（在鏈表中值為x的結點前插入一個值為y的結點），如何實現(xiàn)？09三月2024第56頁(2)刪除所有值為x的結點，并返回1值為x的結點個數(shù)。intDelete_Linkst2(LNode*H,Elemtypex){LNode*p,*q;q=H;count=0;while(q->next){p=q->next;if(!p->data==x)

{q->next=p->next;/*逐個判斷結點值，為x則刪除*/

free(p);++count;}/*count+1*/elseq=p;}/*while*/returncount;}/*Delete_Linkst2*/80768090∧

85Hpq例如x=80的情況。時間復雜度為O(n).考慮不帶表頭結點的情況，刪除算法相對考慮的因素要多些。2.3.3循環(huán)鏈表

單鏈表《數(shù)據(jù)結構》第二章線性表*承德石油高專計算機系572003-1-9······a1a2an∧H······a2∧a1a2an∧H雙向鏈表······a1a2anH循環(huán)鏈表*(rear->next)09三月2024第58頁定義：循環(huán)鏈表是另一種形式的鏈表存儲結構，實現(xiàn)方法是將表中最后一個結點的指針域指向單鏈表的表頭結點，這樣就形成了一個環(huán)。這種結構便于查找結點。循環(huán)條件：1.單鏈表的循環(huán)條件是p或p->next是否為空。2.P或p->next是否等于頭結點通常在循環(huán)鏈表中只設尾結點而不設頭結點，這樣尾結點就起到了既指頭又指尾的功能。······a1a2anH非空單向鏈表H空鏈表09三月2024第59頁例如對兩個單循環(huán)鏈表HA、HB的連接操作，：p=RA–>next;RA->next=RB->next->next;free(RB->next);RB->next=p;時間復雜度為O(1)

RBb1

bn…×a1

an…RA×p①④②③存儲池09三月2024第60頁2.3.4雙向鏈表

問題的引出：在單鏈表中，從任何一個結點可以找到它的后繼結點，但是尋找它的前趨結點，就需要從表頭開始順序查找。定義：雙向鏈表的每一個結點除了數(shù)據(jù)域外，還包括兩個指針域，一個指向后繼結點，另一個指針指向前趨結點。雙向循環(huán)鏈表······a2∧a1a2an∧H······a2a1a2anH09三月2024第61頁priordatanext結點結構特點:(1)可從兩個方向搜索某個結點。(2)無論利用向前這一鏈還是向后這一鏈，都可以遍歷這個鏈表。特別是如果一根鏈失效了，還可以利用另一根鏈修復整個鏈表。雙向鏈表結點的定義如下：typedefstructdlnode{ElemTypedata;structdlnode*prior,*next;}DLNode,*DLinkList;…Ha2a1anH空表09三月2024第62頁當p指向雙向循環(huán)鏈表中的某一結點時，則有以下等式：

p->prior->next=p；

p=p->next->prior；

1．雙向鏈表中結點的插入操作設p指向雙向鏈表中某結點，s指向待插入的新結點，將*s插入到*p的前面，插入過程如圖2-17所示，尤其要注意操作順序，操作過程如下：

s->prior=p->prior;②p->prior->next=s;③s->next=p;④

p->prior=s;p××

x①②③④sa2a1a2pa209三月2024第63頁2．雙向鏈表中結點的刪除操作

設p指向雙向鏈表中待刪除的結點。①p->prior->next=p->next;②p->next->prior=p->prior;③free(p);

①p××②2.3.5靜態(tài)鏈表

靜態(tài)鏈表用數(shù)組實現(xiàn)，每個數(shù)據(jù)元素除了存儲數(shù)據(jù)信息外，還要存儲邏輯相鄰的下一個數(shù)據(jù)元素在數(shù)組中的位置，可見，靜態(tài)鏈表雖然是用數(shù)組實現(xiàn)的，但是邏輯相鄰的數(shù)據(jù)元素不一定在物理位置上也相鄰。

a1a2a3a4a54

5

3

1

2

4

01234

56data

next

SL=0

09三月2024第64頁typedefstruct

{ElemTypedata;

intnext;

}SNode;/*結點類型*/

SNodesd[MAXSIZE];

intSL;/*頭指針變量*/

a1a2a3a4a54

5

3

1

2

4

01234

56data

next

SL=0

2.3.6順序表和鏈表的比較

順序存儲有三個優(yōu)點：(1)方法簡單，各種高級語言中都有數(shù)組，容易實現(xiàn)。(2)不用為表示結點間的邏輯關系而增加額外的存儲開銷。(3)順序表具有按元素序號隨機訪問的特點。

但它也有兩個缺點：(1)插入、刪除操作時，平均移動大約表中一半元素，效率低。(2)需要預先分配足夠大的存儲空間。

09三月2024第65頁在實際中怎樣選取存儲結構的幾點考慮：

(2)基于運算的考慮

如果對線性表的主要操作是查找，適宜采用順序表結構。對于頻繁進行插入和刪除操作的線性表，適宜采用鏈表結構。

(3)基于環(huán)境的考慮

順序表的實現(xiàn)基于數(shù)組類型，鏈表的操作是基于指針。(1)基于存儲的考慮

順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定“MAXSIZE”大小，估計過大，造成浪費，過小造成溢出。

鏈表不用事先估計存儲規(guī)模，但鏈表的存儲密度較低。

存儲密度是指一個結點中數(shù)據(jù)元素所占的存儲單元數(shù)和整個結點所占的存儲單元之比。顯然順序表的存儲密度為1，鏈式存儲結構的存儲密度小于１。

09三月2024第66頁2.4線性表的典型應用

在數(shù)學上，一個多項式可寫成下列形式：P(x)=anxn+an-1xn-1+…..+a1x1+a0，其中ai為xi的非零系數(shù)?？刹捎脝捂湵韥肀硎尽６囗検街械拿恳豁棡閱捂湵碇械囊粋€結點，每個結點包含三個域：系數(shù)域、指數(shù)域和指針域。現(xiàn)有多項式：(x)=5x9+8x7+3x2

可表示為：pa∧

237895

expcoefnext

系數(shù)域指數(shù)域指針域09三月2024第67頁現(xiàn)在設有兩個多項式：做相加運算：

A(x)=5x9+8x7+3x2B(x)=6x12+10x9-3x2-12

pb0-12∧

2-3

910126

pa23∧

7895

運算前pa0-12∧

78915

126

運算后09三月2024第68頁核心算法：首先設三個指針變量：pre、qa和qb，其中pre永遠指向“和多項式”鏈表的尾結點，qa和qb分別從多項式pa和pb鏈表的首項開始掃描，比較qa和qb所指結點指數(shù)域的值，可能出現(xiàn)下列三種情況之一：(1)qa->exp大于qb->exp，qa繼續(xù)向后掃描。

(2)qa->exp等于qb->exp，系數(shù)相加。若結果不為零，將結果放人qa->coef中，并刪除qb所指結點，否則同時刪除qa和qb所指結點。然后qa、qb繼續(xù)向后掃描。(3)qa->exp小于qb->exp，則將qb結點插入到qa所指結點之前，然后qb繼續(xù)向后掃描。一直進行到qa或qb有一個為空為止，然后將有剩余結點的鏈表連接到“和多項式”鏈表尾部。09三月2024第69頁掃描過程一直進行到qa或qb有一個為空為止，然后將有剩余結點的鏈表接在結果鏈表上。所得pa指向的鏈表即為兩個多項式之和。算法：Polyadd（voidployadd(PNode*pa,PNode*pb){PNode*qa,*qb,*q,*pre;intsum;pre=pa;qa=pa->next;qb=pb->next;while(qa&&qb){if(qa->exp==qb->exp){sum=qa->coef+qb->coef;09三月2024第70頁if(sum){qa->coef=sum;pre=qa;}

else

{pre->next=qa->next;free(qa);}qa=pre->next;q=qb;qb=qb->next;free(q);}}else{if(qa->exp>qb->exp){pre=qa;qa=qa->next;}else{pre->next=qb;pre=qb;qb=qb->next;pre->next=qa;}}}if(qb)pre->next=qb;free(pb);}/*ployadd*/算法的時間復雜度為O(m+n)

09三月2024第71頁

棧與隊列是兩種特殊的線性結構。從數(shù)據(jù)結構角度看它們是線性表，從操作的角度看它們是操作受限的線性表。在日常生活中我們會經(jīng)常遇到棧與隊列的實例。例如鐵路調(diào)度中用到棧，鐵路購票中用到了隊列。棧和隊列還廣泛應用于各種軟件系統(tǒng)中：（1）計算機對子程序的嵌套、中斷的管理都用到了棧；（2）對鍵盤緩沖區(qū)的管理用到了隊列。09三月2024第72頁3.1棧3.1.1棧的定義及基本運算

a1a2an…進棧出棧棧底棧頂

棧的插入和刪除操作分別稱為進棧和出棧。進棧是將一個數(shù)據(jù)元素存放在棧頂，出棧是將棧頂元素取出。圖中a1稱為棧底元素，an為棧頂元素。1.定義：棧(stack)是限定僅在表尾的一端進行插入或刪除操作的線性表。允許進行插入或刪除操作的一端稱為棧頂(top)，而另一端稱為棧底(bottom)。不含元素的棧稱為空棧。09三月2024第73頁例：棧中元素按a1，a2，a3的次序進棧，見圖1。出(退)棧的第一個元素應為棧頂元素a3。圖2是a3出棧的情況。圖3是一個空棧，即（top=bottom）。換句話說，棧的操作是按后進先出的原則進行的。因此，棧稱為后進先出表（LastInFirstOut,簡稱LIFO）。a3出棧a1a2圖2棧底棧頂出棧進棧棧底棧頂圖3進棧棧底圖1a1a2a3棧頂09三月2024第74頁有關棧的操作主要有以下幾種：⑴棧初始化：Init_Stack(S)；構造一個空棧。⑵判棧空：Empty_Stack(S)；若S為空棧，則返回TRUE或1，否則返回FALSE或0。⑶入棧：Push_Stack(S，x)；若棧不滿，在棧S的頂部插入一個新元素x，x成為新的棧頂元素。⑷出棧：Pop_Stack(S)；若棧不空，將棧S的棧頂元素從棧中刪除，并保存該元素。⑸讀棧頂元素：Top_Stack(s)；若棧不空，返回棧頂元素，棧的狀態(tài)不發(fā)生變化。

09三月2024第75頁3.1.2棧的順序存儲結構及運算實現(xiàn)

棧的順序存儲結構（順序棧）是利用利用一批地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。通常用一維數(shù)組來實現(xiàn)棧的順序存儲，數(shù)組小下標一端做棧底，設一個棧頂指針top指向棧頂元素，它隨著插入和刪除而變化。

top=-1時為空棧，每進棧一個元素，指針top加1；每出棧一個元素，指針top減1。

s.top0123n-1空?！璦1a2非空棧棧底棧頂typedefstruct{ElemTypeelem[MAXSIZE];inttop;}SeqStack；

09三月2024第76頁圖(a)是空棧，s.top=-1；

圖(b)是A入棧，s.top=0，s.elem[0]=A；

圖(c)是B、C、D、E四個元素依次入棧之后，s.top=4，由于棧已滿，若再入棧，則溢出；

圖(d)是E、D相繼出棧，此時棧中還有3個元素，s.top=2，即棧頂指針指向C元素。

s.top43210s.top=-1(a)空棧43210s.topAs.top=0(b)進棧s.top43210ABCDEs.top=4(c)棧滿s.top43210ABCs.top=2(d)出棧09三月2024第77頁(2)進棧：S->top加1（正向增長）。(3)退棧：S->top減1。(4)空棧：S->top=-1。(5)棧滿：S->TOP=MAXSIZE-1。(6)上溢：棧滿時再做進棧運算（一種出錯狀態(tài)，應設法避免）。(7)下溢：?？諘r再做退棧運算將產(chǎn)生溢出，這是一種正常狀態(tài)（因為棧的初態(tài)和終態(tài)都是空棧，下溢常用作程序控制轉(zhuǎn)移的條件）。09三月2024第78頁棧的主要算法實現(xiàn)1.置空棧（初始化棧）：

⑴棧初始化：初始化棧頂指針。voidInit_SeqStack(SeqStack*s){s->top=-1;}

intEmpty_SeqStack(SeqStack*s){if(s->top==-1)returnTRUE;

elsereturnFALSE;}2.判空棧操作：s.top01234空棧09三月2024第79頁3.進棧操作：intPush_SeqStack(SeqStack*s,ElemTypex){if(s->top==MAXSIZE-1)returnOVERFLOW;

else{s->top++;s->elem[s->top]=x;returnOK;}}4.出棧操作：

intPop_SeqStack(SeqStack*s,ElemType*y){if(Empty_SeqStack(s))returnOVERFLOW;

else{*y=s->elem[s->top];s->top--;returnOK}}s.top856074559001234棧滿s.top8560745501234”90”出棧09三月2024第80頁5.取棧頂元素

ElemTypeTop_SeqStack(SeqStack*s){if(Empty_SeqStack(s))returnOVERFLOW;elsereturn(s->elem[s->top]);}

*關于順序棧的約定和主要運算的思考：如果約定順序棧棧空為：s->top=0，則順序棧下述的幾種運算如何描述？置空棧、判?？?、進棧、退棧、取棧頂元素。s.top8560745501234返回“55”09三月2024第81頁

例題：假設有3個元素a，b，c，入棧順序是a，b，c，則它們的出棧順序有幾種可能？1.abc順序進棧則出棧順序為cba;2.a進棧，a出棧，然后b、c進棧，再順序出棧，則出棧順序為acb；3.a進棧，a出棧；b進棧，b出棧；c進棧，c出棧；則出棧順序為abc；4.a、b進棧，a、b出棧然后c進棧，再出棧，則出棧順序為bac；5.a、b進棧,b出棧;c進棧，然后出棧。則出棧順序為bca；思考題：出棧順序有可能出現(xiàn)cab的情況嗎？09三月2024第82頁問題：當程序中同時使用幾個棧時，如何防止棧的上溢？方法一：將棧的容量加到足夠大，但這種方法由于事先難以估計容量，有可能浪費空間。方法二：使用兩個（或多個）棧共享存儲空間辦法。兩棧的棧底分別設在給定存儲空間的兩端，然后各自向中間伸延，當兩棧的棧頂相遇時才可能發(fā)生溢出。S1.buttom0123…………m-4m-3m-2m-1S2.buttoma1a2a3b1b2b3b4S2.topS1.topS1進棧方向09三月2024第83頁3.1.3棧的鏈式存儲結構及運算實現(xiàn)

棧也可以用單鏈表作為存儲結構。一個鏈棧由它的棧頂指針唯一確定。假設top是StackNode*類型的變量，則top指向棧頂結點，top=NULL時，鏈棧為空。棧的鏈式存儲結構描述如下：typedefstructnode{ElemTypedata;structnode*next;}StackNode;

Ctopdatanext

B

A∧

09三月2024第84頁⑴置空棧

voidInit_LS（StackNode*top）{top=NULL;}時間復雜度O(1)⑵判?？読ntEmpty_LS（StackNode*top）{returntop==NULL;}⑶入棧StackNode*Push_LS（StackNode*top,ElemTypex）{StackNode*p=(StackNode*)malloc（sizeof（StackNode））;p->data=x;p->next=top;

top=p;returntop;}09三月2024第85頁

⑷出棧intPop_LS(StackNode*top,ElemType*y){StackNode*p;if（Empty_LS（top））{printf("StackUnderflow.");/*下溢*/

returnOVERFLOW;}else{*y=top->data;p=top;top=top->next;free(p);returnOK;}}

Ctopdatanext

B

A∧

09三月2024第86頁⑸取棧頂元素

intGetTop(StackNode*top,ElemType*y)

{if(Empty_LS(top))

{printf(“Stackunderflow.”);/*下溢*/

returnOVERFLOW;}

else{

*y=top->data;

returnOK;}

}

Ctopdatanext

B

A∧

09三月2024第87頁3.2隊列3.2.1隊列的定義及基本運算

隊列(Queue)也是一種