數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)培訓(xùn)課件

1、數(shù) 據(jù) 結(jié) 構(gòu)第一章 緒 論1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 有關(guān)概念和術(shù)語1.3 算法和算法分析 1.3.1 算法 1.3.2 算法設(shè)計的要求 1.3.3 算法效率的度量 1.3.4 算法的存儲空間的需求第一章 緒 論 計算機(jī)是一門研究利用計算機(jī)進(jìn)行信息表示和處理的科學(xué)。涉及： 信息的表示 信息的處理 而信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著計算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。1.1 什么是數(shù)據(jù)結(jié)構(gòu) 眾

2、所周知，計算機(jī)的程序是對信息進(jìn)行處理。在大多數(shù)情況下，這些信息并不是沒有組織的，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。什么是數(shù)據(jù)結(jié)構(gòu)呢？例子： 例1、電話號碼查詢系統(tǒng) 設(shè)有一個電話號碼薄，它記錄了N個人的名字和其相應(yīng)的電話號碼，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn)其中(ai，bi)(i=1，2n) 分別表示某人的名字和對應(yīng)的電話號碼。要求設(shè)計一個算法，當(dāng)給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的信息。數(shù)據(jù)結(jié)構(gòu)含義： 就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系

3、，并對這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。 所有能被輸入到計算機(jī)中，且能被計算機(jī)處理的符號的集合。數(shù)據(jù):是計算機(jī)操作的對象的總稱。 是計算機(jī)處理的信息的某種特定的符號表示形式。1.2 有關(guān)概念和術(shù)語是數(shù)據(jù)（集合）中的一個“個體”數(shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：一、集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。二、線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。三、樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)

4、元素之間存在多對多的關(guān)系。 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)(Data Structure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 數(shù)據(jù)在計算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu)。 數(shù)據(jù)對象可以是有限的，也可以是無限的。數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關(guān)系。數(shù)據(jù)類型：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類。例1、 在FORTRAN語言中，變量的數(shù)據(jù)類型有整型、實(shí)型、和復(fù)

5、數(shù)型 例2、在C+語言中數(shù)據(jù)類型：基本類型和構(gòu)造類型基本類型：整型、浮點(diǎn)型、字符型構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義數(shù)據(jù)對象：某種數(shù)據(jù)類型元素的集合。例3、整數(shù)的數(shù)據(jù)對象是-3，-2，-1，0，1，2，3，英文字符類型的數(shù)據(jù)對象是A，B，C，D，E，F(xiàn)，1.3 算法和算法分析1.3.1 算法： 是對特定問題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。 算法具有以下五個特性：（1）有窮性 一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。（2）確定性 算法中每一條指令必須有確切的含義。不存在二義性。（3）可行性 一個算法是可行的。即算法描

6、述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。（4）輸入 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。（5）輸出 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。1.3.2 算法設(shè)計的要求設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)：1正確性2. 可讀性3健壯性4高效率與低存儲量需求1正確性 首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式給出的需求。 其次，對算法是否“正確”的理解可以有以下四個層次：a程序中不含語法錯誤；b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； c程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 通常以第 c

7、 層意義的正確性作為衡量一個算法是否合格的標(biāo)準(zhǔn)。 d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；2. 可讀性 算法主要是為了人的閱讀與交流，其次才是為計算機(jī)執(zhí)行，因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調(diào)試。3健壯性 當(dāng)輸入的數(shù)據(jù)非法時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4高效率與低存儲量需求通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間，兩者都與問題的規(guī)模有關(guān)。1.3.3 算法效率的

8、度量通常有兩種衡量算法效率的方法:事后統(tǒng)計法事前分析估算法缺點(diǎn)：1必須執(zhí)行程序 2其它因素掩蓋算法本質(zhì)和算法執(zhí)行時間相關(guān)的因素：1算法選用的策略2問題的規(guī)模3編寫程序的語言4編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5計算機(jī)執(zhí)行指令的速度 一個特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。 假如，隨著問題規(guī)模 n 的增長，算法執(zhí)行時間的增長率和 f(n) 的增長率相同，則可記作：T (n) = O(f(n)稱T(n)為算法的(漸近)時間復(fù)雜度。如何估算 算法的時間復(fù)雜度？算法 = 控制結(jié)構(gòu) + 原操作 （固有數(shù)據(jù)類型的操作）算法的執(zhí)行時間 =原操作(i

9、)的執(zhí)行次數(shù)原操作(i)的執(zhí)行時間 算法的執(zhí)行時間 與 原操作執(zhí)行次數(shù)之和 成正比 從算法中選取一種對于所研究的問題來說是 基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行的次數(shù) 作為算法運(yùn)行時間的衡量準(zhǔn)則。void mult(int a, int b, int c ) for (i=1; i=n; +i) for (j=1; j=n; +j) cij = 0; for (k=1; k=n; +k) cij += aik*bkj; /for /mult基本操作: 乘法操作時間復(fù)雜度: O(n3)例1例 +x;s=0; 將x自增看成是基本操作，則語句頻度為，即時間復(fù)雜度為(1) 如果將s=0也

10、看成是基本操作，則語句頻度為1，其時間復(fù)雜度仍為(1)，即常量階。例 for(i=1;i=n;+i) +x;s+=x; 語句頻度為：n其時間復(fù)雜度為：O(n) 即時間復(fù)雜度為線性階。i=0: 賦值次i=1: 賦值 2 次i=2: 賦值3次i=n-1:賦值n次.+1+2+3+n=(1+n)n/2=n2/2+n/2例 for(i=1;i=n;+i)for(j=1;j=n;+j) +x;s+=x; 語句頻度為：n2其時間復(fù)雜度為：O(n2) 即時間復(fù)雜度為平方階。例 for(i=0;i=n-1;+i) for(j=0;j1=n0，n為正整數(shù)時，xn+1xn，所以：|an|*|xn|+|an-1|*|

11、xn-1|+|a1|*|x1|+|a0|*|x0| |an|*|xn|+|an-1|*|xn|+|a1|*|xn|+|a0|*|xn|=(|an|+|an-1|+|a1|+|a0|)|xn|=c|xn|其中：n0=1, c= |an|+|an-1|+|a1|+|a0|, g(n)=xn 一個算法時間為O(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即零次多項(xiàng)式）來限界。而一個時間為O(n2)的算法則由一個二次多項(xiàng)式來限界。 以下六種計算算法時間的多項(xiàng)式是最常用的。其關(guān)系為： O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指數(shù)時間的關(guān)系為： O(2n

12、)O(n!)0 ;i-) for(j=0;jaj+1) aj aj+1; 最好情況：0次 最壞情況：每次都換， (n2) 例7： 遞歸程序的分析int fact( int n) if(n=1) return 1; else return n*fact(n-1);f(n)=c+f(n-1) =c+(c+f(n-2) =2c+f(n-2) =(n-1)c+f(1) =(n-1)c+c01.3.4 算法的存儲空間的需求算法的空間復(fù)雜度定義為: 表示隨著問題規(guī)模 n 的增大，算法運(yùn)行所需存儲量的增長率與 g(n) 的增長率相同。S(n) = O(g(n)算法的存儲量包括:1輸入數(shù)據(jù)所占空間2程序本身所

13、占空間3輔助變量所占空間 若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。 若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。 若所需存儲量依賴于特定的輸入，則通常按最壞情況考慮。注意：時間與空間往往是對矛盾，要綜合考慮。作業(yè)：. 計算時間復(fù)雜度 sum=1; for(i=0;sumn;i+) sum+=i;2.設(shè)給定若干n值，比較兩函數(shù)n2和50nlog2n的增長趨勢，并確定在什么范圍內(nèi)，函數(shù)n2的值大于50nlog2n的值。答案: (自做)1.sum=0+1+2+m=m*(m+1)/2n m*(m+1)2n m*m2n m

14、50nlog2n =n 50log2n =2 n n50 =n439 第二章 線性表2.1 線性表的類型定義2.2 線性表的順序表示和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 2.3.1 線性鏈表 2.3.2 循環(huán)鏈表 2.3.3 雙向鏈表 2.4 一元多項(xiàng)式的表示及相加2.1 線性表的邏輯結(jié)構(gòu) 線性表：由n(n0)個數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2， an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n0)記作： (a1，a2，an) 這里的數(shù)據(jù)元素ai(1in)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例1、26個英文字母組成的字母表 （A，B

15、，C、Z）例2、某校從1978年到1983年各種型號的計算機(jī)擁有量的變化情況。 （6，17，28，50，92，188） . . . 神經(jīng)衰弱 17 男790634張立立 健康 21 男790633劉建平 一般 20 女790632陳 紅 健康 18 男790631王小林 健康情況年齡性 別學(xué) 號姓 名例3、學(xué)生健康情況登記表如下： 從以上例子可看出線性表的邏輯特征是：(1) 對非空的線性表，有且僅有一個開始結(jié)點(diǎn)a1，它沒有直接前趨，而僅有一個直接后繼a2；(2) 有且僅有一個終端結(jié)點(diǎn)an，它沒有直接后繼，而僅有一個直接前趨a n-1；(3) 其余的內(nèi)部結(jié)點(diǎn)ai(2in-1)都有且僅有一個直接前

16、趨a i-1和一個直接后繼ai+1。 線性表是一種典型的線性結(jié)構(gòu)。 數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲結(jié)構(gòu)上進(jìn)行的。2.2 線性表的順序存儲結(jié)構(gòu)2.2.1 線性表 把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。 假設(shè)線性表的每個元素需占用m個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置作為參考點(diǎn)。則線性表中第i+1個數(shù)據(jù)元素的存儲位置Loc(ai+1)和第i個數(shù)據(jù)元素的存儲位置Loc(ai)之間滿足下列關(guān)系： Loc(ai+1)=Loc(ai)+m aiai+1Loc(ai+1)m個字節(jié)Loc(ai)線性

17、表的第i個數(shù)據(jù)元素ai的存儲位置為 : a1a2aianLoc(a1)i-1個元素Loc(ai)=(i-1)*m+Loc(a1)=Loc(a1)-m+i*m由于Loc(a1)和m都是已知的所以：V0= Loc(a1)-mLoc(ai)=V0+i*m 由于在高級語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。又因?yàn)槌擞脭?shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，利用C+語言的結(jié)構(gòu)類型來定義順序表類型。 # define ListSize 100 /表容量 typedef int DataType;/以int為例 struct Sqlist Da

18、taType dataListSize; int lenth;/當(dāng)前表中元素數(shù) ;lenth.SqlistdataListSize個2.2.2 順序表上實(shí)現(xiàn)的基本操作 在順序表存儲結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。 注意：C/C+語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素位置是L.datai-1。 線性表的插入和刪除兩種運(yùn)算。 1、插入 線性表的插入運(yùn)算是指在表的i(1in+1)個位置上，插入一個新結(jié)點(diǎn)x，使長度為n的線性表 (a1，a i-1，ai，an) 變成長度為n+1的線性表 (a1，a i-1，x，ai，a

19、n)注：可用memmove(L.data+i+1,L.dada+i,(L.lenth-i+1)*sizeof(DataType)代替for循環(huán)（包含文件： string.h,一般格式格式： memmove(目的地址，源地址，移動字節(jié)數(shù))void InsertList(L,x,i)/在線性表L中第i個位置插入元素x if(iL.length+1) cout“插入序號錯誤”=ListSize) 溢出處理；else for(j=L.length-1;j=i-1;j-) /第i個元素（下標(biāo)為i-1)開始 L.dataj+1=L.dataj;/順序后移 L.datai-1=x; L.length+; m

20、emcpy(目的地址,源地址，字節(jié)數(shù)）memset(目的地址,字符，字節(jié)數(shù)）int a5050,b5050;a清0for(i=0;i50;i+) for(j=0;j50;j+) aij=0;拷貝：for(i=0;i50;i+) for(j=0;j最好情況； 當(dāng)=1時，需移動表中所有結(jié)點(diǎn)-最壞情況，a1，a i-1，ai，anx移動數(shù)據(jù)：n-i+1算法的平均移動 由于插入可能在表中任何位置上進(jìn)行，在長度為n的線性表中第i個位置上插入一個結(jié)點(diǎn)，令Eis(n)表示移動結(jié)點(diǎn)的期望值（即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點(diǎn)的移動次數(shù)為n-i+1。 Pi代表在第i個位置插入概率，則 Eis(n)

21、= p1 * n+p2*(n-1)+ .+ pn*1+pn+1*0 若表中任何位置(1in+1)上插入結(jié)點(diǎn)的概率是均等的，則 p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情況下： Eis(n)=1/(n+1)n+(n-1)+1+0=n/2a1，a i-1，ai，an可能的插入點(diǎn)有n+1處結(jié)論：在順序表上做插入運(yùn)算，平均要移動表上一半結(jié)點(diǎn)。當(dāng)表長 n較大時，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時間復(fù)雜度為O(n)。 2、刪除 線性表的刪除運(yùn)算是指將表的第i(1in)結(jié)點(diǎn)刪除，使長度為n的線性表： (a1，a i-

22、1，ai，a i+1，an)變成長度為n-1的線性表 (a1，a i-1，a i+1，an)void deleteList(L,i)/表L中刪除第i個元素 if(iL.length) cout“刪除序號錯”endl; return ERROR; for(j=i; jch; while (ch!=$)p=new LNode;pdata=ch; pnext=h; h=p; cin ch; LNode *CreateList( ) char ch; LNode *h,*p; h=NULL; cinch; while (ch!=$) p=new LNode; pdata=ch; pnext=h; h=

23、p; cin ch; return h; #include struct LNode char data; LNode *next;LNode *CreateList( ) char ch; LNode *h,*p; h=NULL; cinch; while (ch!=$) p=new LNode; pdata=ch; pnext=h; h=p; cin ch; return h; void CreateList1( LNode *&h) char ch; LNode *p; h=NULL; cinch; while (ch!=$) p=new LNode; pdata=ch; pnext=h

24、; h=p; cin ch; void print(LNode *h) LNode *p; while(p!=NULL) coutdatanext; coutch; while(ch!=$) p=new LNode; pdata=ch; if(head=NULL) head=p; else r-next=p; r=p;cinch;if(r!=NULL) r-next=NULL; return head;頭結(jié)點(diǎn)（哨兵結(jié)點(diǎn)）引入： 增加一個表頭結(jié)點(diǎn)，數(shù)據(jù)域可根據(jù)需要使用或不用。特點(diǎn)：a、表中第一個結(jié)點(diǎn)和在表的其它位置上的操作一致，無需進(jìn)行特殊處理；b、無論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)。因此空

25、表和非空表的處理統(tǒng)一。NULLhead有頭結(jié)點(diǎn)的空表head= 無頭結(jié)點(diǎn)的空表LNode *creat() LNode *r,*h; char ch; h=new LNode; r=h; cinch;while(ch!=$) r-next=new LNode; r=r-next; r-data=ch; cinch;r-next=NULL; 上述算法里動態(tài)申請新結(jié)點(diǎn)空間時未加錯誤處理，在實(shí)際使用時間，可作下列判定與處理： p= new LNode; if(p= =NULL) 錯誤處理； 二、查找運(yùn)算 1、按序號查找 在鏈表中，即使知道被訪問結(jié)點(diǎn)的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點(diǎn)，

26、而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點(diǎn)往下搜索，直到搜索到第i個結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。 設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點(diǎn)，僅當(dāng)1=inext & jnext; j+; if (i=j) return p; else return NULL;2、按值查找 按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)，若有，則返回首次找到的其值為key的結(jié)點(diǎn)的存儲位置；否則返回NULL。查找過程從開始結(jié)點(diǎn)出發(fā)，順著鏈表逐個將結(jié)點(diǎn)的值和給定值key作比較。其算法如下：LNode *locatenode(head，key) p=headnext; while( p &

27、pdata!=key) p=pnext; return p; 該算法的執(zhí)行時間亦與輸入實(shí)例中的的取值key有關(guān)，其平均時間復(fù)雜度的分析類似于按序號查找。三、插入運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，并令q指針指向該新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化xai-1ai三、插入運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域?yàn)?/p>

28、x的新結(jié)點(diǎn)，并令q指針指向該新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aix三、插入運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，并令q指針指向該新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aix三、插入運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，并令q指

29、針指向該新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq-next=p-next;三、插入運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，并令q指針指向該新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq-next=p-next;p-next=q;三、插入運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到

30、ai-1的存儲位置p，然后生成一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，并令q指針指向該新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq-next=p-next;p-next=q;三、插入運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，并令q指針指向該新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq-next=p-next;p-next=q;定位ai-1并將指針p指向它；三、插

31、入運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，并令q指針指向該新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq = new LNode;q-data=x;q-next=p-next;p-next=q;定位ai-1并將指針p指向它；三、插入運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，并令q指針指向該新結(jié)

32、點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq = new LNode;q-data=x;q-next=p-next;p-next=q;p=getnode(head，i-1);功能：在頭指針為head的鏈表中定位第i-1個結(jié)點(diǎn),并返回結(jié)點(diǎn)位置。三、插入運(yùn)算 void insertnode(head， x， i) LNode * p，*q; p=getnode(head，i-1); if(p=NULL) cout“position error”data=x; qnext=pnext; pnext=q; LNode * getnode(

33、head ，i) p=head; j=0; /計數(shù)用 while(pnext & jnext; j+; if (i=j) return p;else return NULL;四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間。此過程為：ai-1aiai+1四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中，所以必須首先找到ai-1的

34、存儲位置p。然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間。此過程為：ai-1aiai+1四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間。此過程為：ai-1aiai+1四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)

35、點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間。此過程為：ai-1aiai+1pp-next=p-next-next;四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間。此過程為：ai-1aiai+1pp-next=p-next-next;問題：鏈表的邏輯結(jié)構(gòu)已正確了，但結(jié)點(diǎn)ai空間丟了。四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域ne

36、xt中，所以必須首先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間。此過程為：ai-1aiai+1pp-next=p-next-next;r=p-next;p-next=r-next;delete r;四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間。此過程為：ai-1aiai+1pp-next=p-next-next;r=p-next;p

37、-next=r-next;delete r;r四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間。此過程為：ai-1aiai+1pp-next=p-next-next;r=p-next;p-next=r-next;delete r;r四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令pn

38、ext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間。此過程為：ai-1aiai+1pp-next=p-next-next;p=getnode(head，i-1);r=p-next;p-next=r-next;delete r;r四、刪除運(yùn)算void deletelist(head， i) LNode *p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; delete r; 從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無須移動結(jié)點(diǎn)，僅需修改

39、指針。作業(yè)： （1） 鏈表是有序的，現(xiàn)在插入數(shù)據(jù)x，要求插入后仍然有序 （2）鏈表是有序的，現(xiàn)在刪除數(shù)據(jù)x，若x不存在，輸出一段提示信息。 要求：按鏈表有頭結(jié)點(diǎn)和無頭結(jié)點(diǎn)兩種情況分別寫出并上機(jī)調(diào)試通過。五、靜態(tài)鏈1、靜態(tài)鏈表的概念 用一維數(shù)組來實(shí)現(xiàn)線性鏈表，這種用一維數(shù)組表示的線性鏈表，稱為靜態(tài)鏈表。靜態(tài)：體現(xiàn)在表的容量是一定的。（數(shù)組的大?。╂湵恚翰迦肱c刪除同前面所述的動態(tài)鏈表方法相同2、靜態(tài)鏈表的類型定義#define MAXSIZE 1000 / 鏈表的最大長度struct Component ElemType data; int cur; ; Component VListMAXSIZ

40、E;SLinkList類型的數(shù)組變量是結(jié)構(gòu)數(shù)組，每一數(shù)組分量包括兩個域：data：用于存儲線性表元素；cur： 用于存儲直接后繼元素在數(shù)組中的位置靜態(tài)鏈表圖示0h=5數(shù)組下標(biāo)靜態(tài)鏈表與線性鏈表的區(qū)別？線性鏈表圖示地址a18a22a4-1a30123456789101010a11026a21014a40a310101012101410221024102610281030102010181016h=1020例：靜態(tài)鏈表的操作 設(shè)插入和刪除只在表的頭上進(jìn)行（棧）h=7（5，7，2，3）（8，5，7，2，3）h=0表中加入x01234793-15123567891001234793-151235678

41、9102.(1)VListi.data=x;1.在VList中找空位置 i(比如0)(2)VListi.cur=h; x7 (3)h=i; 空位置的標(biāo)識：將所有空位置構(gòu)成鏈表，用av表示鏈?zhǔn)?12342793-11058451-12365678910av=02.(1)Vlisti.data=x;1.在VList中找空位置 i(2)Vlisti.cur=h; (3)h=i; if(av= -1) 無空間處理elsei=av;av=VListi.curVListi.data=x; VListi.cur=h; h=i;刪除：if(h!=-1) x=VListh.data;i=h;h=VListi.c

42、ur; VListi.cur=av; av=i; h=7空表初始化：開始，表是空的，所以：for(i=0;inextnext和rear，顯然，查找時間都是O(1)。因此，實(shí)際中也常采用尾指針表示單循環(huán)鏈表.。 a1anrear 由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p或pnext是否為空，而是判斷它們是否等于某一指定指針，如頭指針或尾指針等。2.3.3 雙向鏈表 雙向鏈表(Double linked list):在單鏈表的每個結(jié)點(diǎn)里再增加一個指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。形式描述為：str

43、uct DuLNode datatype data; DuLNode *prior，*next; ;結(jié)點(diǎn)存儲前趨結(jié)點(diǎn) 的地址存儲數(shù)據(jù)元素存儲后繼結(jié)點(diǎn) 的地址指針域數(shù)據(jù)域指針域 雙鏈表一般由頭指針唯一確定的，將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表。 設(shè)指針p指向某一結(jié)點(diǎn)，則雙向鏈表結(jié)構(gòu)的對稱性可用下式描述： ppriornext=p=pnextprior L（c）非空的雙向循環(huán)鏈表 (b)空的雙向循環(huán)鏈表Lpabc雙向鏈表結(jié)點(diǎn)p前的插入數(shù)據(jù)x的操作：pqxai-1aiq= new DuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-

44、next=q;p-prior=q;雙向鏈表結(jié)點(diǎn)p前的插入數(shù)據(jù)x的操作：pqxq= new DuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;ai-1ai雙向鏈表結(jié)點(diǎn)p前的插入數(shù)據(jù)x的操作：pqxai-1aiq= new DuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;ai+1aippriornext=pnext;pnextprior=pprior; delete p;p刪除p指針?biāo)傅慕Y(jié)點(diǎn)：ai-1ai+1aippriorne

45、xt=pnext;pnextprior=pprior; delete p;p刪除p指針?biāo)傅慕Y(jié)點(diǎn)：ai-1ai+1aippriornext=pnext;pnextprior=pprior; delete p;p刪除p指針?biāo)傅慕Y(jié)點(diǎn)：ai-1 雙向鏈表的插入、刪除靈活；鏈表維護(hù)的工作量大，所需的存儲空間較大。24 一元多項(xiàng)式的表示及相加P n (x) = pn xn + pn-1 xn-1 + p1 x + p0 Q m (x) = qm xm + qm-1 xm-1+ q1x + q0一、一元多項(xiàng)式的表示 多項(xiàng)式的操作是表處理的典型用例。數(shù)學(xué)上,一元多項(xiàng)式可按降冪寫成：（指數(shù)為正整數(shù)的情況）其

46、中：pn 、qm不為0 存儲結(jié)構(gòu)：用線性鏈表表示。增加頭結(jié)點(diǎn)，每個結(jié)點(diǎn)有coef:系數(shù) exp指數(shù) next：指針其中，頭結(jié)點(diǎn)的exp為-1。coefexpnext多項(xiàng)式 A (x) = 5 x 17 + 9 x 8 + 3x +7ha517983170-1例：求兩多項(xiàng)式的和多項(xiàng)式 A (x) = 5 x 17 + 9 x 8 +3x+7 B (x) = 9 x 8 +22 x 7 +8 x二、一元多項(xiàng)式的相加算法一元多項(xiàng)式相加運(yùn)算規(guī)則：指數(shù)相同的項(xiàng)系數(shù)相加A (x) B (x)相加的和多項(xiàng)式為 C (x) = A (x) + B (x) = 5 x 17+ 22 x 7 + 11x +7 設(shè)

47、多項(xiàng)式A (x) ，B (x)分別用帶表頭結(jié)點(diǎn)的線性鏈表pa,pb表示,完成:ha=ha+hb一元多項(xiàng)式加法算法主要步驟 分別對兩個鏈表ha 、hb進(jìn)行掃描，設(shè) 工作指針pa 、 pb分別指向兩個多項(xiàng)式當(dāng)前進(jìn)行比較的結(jié)點(diǎn)，q指針指向pa的前驅(qū)，初始： q=ha; pa=ha-next; pb=hb-next;若pa,pb都不為空：則比較兩者指數(shù)： pa-exp pb-exp： q,pa后移；pa-exp = pb-exp：將pb所指結(jié)點(diǎn)的系數(shù)“加”到pa所指結(jié)點(diǎn) 的系數(shù)上；若和為0，則pa所指結(jié)點(diǎn)刪除。 q , pa, pb調(diào)整pa-exp exp ： 從表hb中復(fù)制pb所指結(jié)點(diǎn)的coef,e

48、xp，并將其插入到 ha表pa所指結(jié)點(diǎn)之前；若pb不空：hb表中從pb開始的結(jié)點(diǎn)插入到ha表尾上int comp(int a,int b) if(ab) return -1; if(a=b) return 0; else return 1; PloyAdd(ha,hb) q=ha;pa=ha-next; pb=hb-next; while(pa!=NULL & pb!=NULL) switch(comp(pa-exp,pb-exp) -1: q=pa; pa=pa-next;break; 0: pa-coef+=pb-coef; if(pa-coef=0) q-next=pa-next; de

49、lete pa; pa=q; else q=pa; pa=pa-next; pb=pb-next; break; 1: r=new Node;r-coef=pb-coef;r-exp=pb-exp;q-next=r;r-next=pa;q=r;pb=pb-next;break; while(pb!=NULL) r=new Node; r-coef=pb-coef; r-exp=pb-exp; q-next=r; r-next=pa; q=r; pb=pb-next; while改成：while(pb!=hb)在改成循環(huán)鏈后，此while可省去。1、線性表v的數(shù)據(jù)遞增有序，試將x插入表中并保持有

50、序性（1）表順序表示（2）鏈表表示（3）帶有頭結(jié)點(diǎn)的鏈表2、寫一個線性表的轉(zhuǎn)置算法（順序和鏈表表示兩種情況） （a1,a2,.,an)變?yōu)椋╝n,an-1,.,a1)實(shí)習(xí)題目： hc=ha*hb第三章 棧和隊(duì)列3.1 棧 3.1.1 棧的定義 3.1.2 棧的表示和實(shí)現(xiàn)3.2 棧的應(yīng)用舉例 3.1 棧3.1.1 棧的定義及基本運(yùn)算 棧(Stack)是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧。 假設(shè)棧S=(a1，a2，a3，an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，an

51、的次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。因此，棧的修改是按后進(jìn)先出的原則進(jìn)行的，所以，棧稱為后進(jìn)先出（先進(jìn)后出）表（LIFO，F(xiàn)ILO）。3.1.2 順序存儲棧 棧是線性表的特例，因此線性表的存儲結(jié)構(gòu)對棧也適應(yīng)。 棧的順序存儲結(jié)構(gòu)簡稱為順序棧，可用數(shù)組來實(shí)現(xiàn)順序棧。因?yàn)闂５孜恢檬枪潭ú蛔兊?，所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個端點(diǎn)；棧頂位置是隨著進(jìn)棧和退棧操作而變化的，故需用一個整型變量top（棧頂指針）來指出棧頂。棧頂 棧底例、一疊盤子、彈夾等。 anan-1.a2a1入出-1 空棧top016 為指示當(dāng)前棧頂?shù)奈恢?，需top為棧頂指針（ MAXSIZE代表?xiàng)Ｈ萘浚?。初始?x進(jìn)棧

52、：退棧：top=-1;if(top= =MAXSIZE-1 上溢處理； else top+; stacktop=x;if(top=-1) 下溢處理； else y=stacktop; top-;3.1.3 鏈棧 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，插入和刪除操作僅限制在鏈頭位置上進(jìn)行。棧頂指針就是鏈表的頭指針。 初始化：top=NULLX進(jìn)棧：p= new StackNode;p-data=x; p-next=top;top=p;退棧:if(top = = NULL) 下溢處理；else y= top-data; p=top;top=p-next;delete p; top3.2 棧的應(yīng)用舉例 由于棧結(jié)

53、構(gòu)具有的后進(jìn)先出的固有特性，致使棧成為程序設(shè)計中常用的工具。以下是幾個棧應(yīng)用的例子。 3.2.1 數(shù)制轉(zhuǎn)換 十進(jìn)制N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計算機(jī)實(shí)現(xiàn)計算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理: N=(n / d)*d+n % d例如 (1348)10=(2504)8，其運(yùn)算過程如下： n n /8 n % 8 1348 168 4 168 21 0 21 2 5 2 0 2 void conversion( ) initstack(s); cinn; while(n) push(s,n%8); n=n/8; while(! Stackempty(s) pop(s,e);cout

54、next=NULL;x進(jìn)隊(duì)：r=new Node; r-data=x; r-next=NULL; rear-next=r;rear=r;退隊(duì)：if(front = rear) 隊(duì)空處理；else p=front-next;y=p-data;front-next=p-next;delete p; if(front-next= =NULL) rear=front;fr習(xí)題1、鏈棧中為何不設(shè)頭指針？2、循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判斷它的空和滿？3、設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則怎樣進(jìn)行入隊(duì)和出隊(duì)操作；若只設(shè)尾指針呢？4、利用棧的基本操作，寫一個返回棧s中結(jié)點(diǎn)個數(shù)的算法int s

55、tacksize(seqstack s)，并說明s為何不用作為指針參數(shù)？5、利用棧的基本操作，寫一個將棧中所有結(jié)點(diǎn)均刪除算法，并說明S為何要作為指針參數(shù)？6、用第二種方法，即少用一個元素空間的方法來區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿，試設(shè)計置空隊(duì)、判隊(duì)空、判隊(duì)滿、出隊(duì)、入隊(duì)及取隊(duì)頭元素等六個基本操作。 第四章 串4.1 串類型的定義4.2 串的表示和實(shí)現(xiàn) 4.2.1 定長順序存儲表示 4.2.2 堆分配存儲表示 4.2.3 串的塊鏈存儲表示4.1 串類型的定義一、串和基本概念 串(String)是零個或多個字符組成的有限序列。一般記作S=“a1a2a3an”，其中S是串名，雙引號括起來的字符序列是串值；

56、ai(1in)可以是字母、數(shù)字或其它字符；串中所包含的字符個數(shù)稱為該串的長度。長度為零的串稱為空串(Empty String)，它不包含任何字符。 通常將僅由一個或多個空格組成的串稱為空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分別表示長度為1的空白串和長度為0的空串。 串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時的該子串的首字符在主串中的位置，定義為子串在主串中的序號（或位置）。例如，設(shè)A和B分別為 A=“This is a string” B=“is”則B是A的子串，A為主串。B在A中出現(xiàn)了兩次，其

57、中首次出現(xiàn)所對應(yīng)的主串位置是3。因此，稱B在A中的序號（或位置）為3 特別地，空串是任意串的子串，串總是其自身的子串。 通常在程序中使用的串可分為兩種：串變量和串常量。串常量和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能改變其值，即只能讀不能寫。通常串常量是由直接量來表示的，例如語句cout“overflow”中“overflow”是直接量。但有的語言允許對串常量命名，以使程序易讀、易寫。如C+中，可定義 const char path=“dir/bin/appl”;這里path是一個串常量，對它只能讀不能寫。串變量和其它類型的變量一樣，其取值是可以改變的。二、串的基本操作 對于串的基本操作，

58、許多高級語言均提供了相應(yīng)的運(yùn)算或標(biāo)準(zhǔn)庫函數(shù)來實(shí)現(xiàn)。C/C+語言中常用的串運(yùn)算如下： 定義下列幾個變量： char s120=“dirtreeformat”,s220=“test.cpp”; char s330,*p; int result;（1）求串長(length) int strlen(char *s); /求串的長度（2）串復(fù)制(copy) char *strcpy(char *to,char *from); 該函數(shù)將串from復(fù)制到串to中，并且返回一個指向串to的開始處的指針。 例如：strcpy(s3,s1); /s3=“dirtreeformat”(3)聯(lián)接(concatenat

59、ion) char strcat(char *to,char *from) 該函數(shù)將串from復(fù)制到串to的末尾，并且返回一個指向串to的開始處的指針。 例如：strcat(s3,”/”) strcat(s3,s2); /s3=“dirtreeformat/test.cpp”例1、求子串 求子串的過程即為復(fù)制字符序列的過程，將串s中的第pos個字符開始的連續(xù)的len個字符復(fù)制到串sub中。 void substr(string sub,string s,int pos,int len) if(posstrlen(s)-1 | len0) n=strlen(s); m=strlen(t); i=

60、pos; while(in-m+1) substr(sub,s,i,m); if(strcmp(sub,t)!=0) +i; else return i; return 0; 4.2 串的表示和實(shí)現(xiàn) 因?yàn)榇翘厥獾木€性表，故其存儲結(jié)構(gòu)與線性表的存儲結(jié)構(gòu)類似。只不過由于組成串的結(jié)點(diǎn)是單個字符。串有三種表示方法。4.2.1定長順序存儲表示 定長順序存儲表示,也稱為靜態(tài)存儲分配的順序表。用一組連續(xù)的存儲單元來存放串中的字符序列。所謂定長順序存儲結(jié)構(gòu)，是直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出： #define MAXSTRLEN 256 typedef char sstringMAXSTRL