《軟件技術(shù)基礎(chǔ)》全冊配套精品完整課件

《軟件技術(shù)基礎(chǔ)》全冊配套精品完整課件

教材習(xí)題參考第

0

章緒論

（有*號的標(biāo)題表示最基本的內(nèi)容）

0.1

課程的目的與任務(wù)0.2

課程基本要求0.3

學(xué)習(xí)軟件的重要作用0.4

軟件課程學(xué)習(xí)方法0.5考核方法0.1課程的目的和任務(wù)《軟件基礎(chǔ)》是電類專業(yè)的一門專業(yè)基礎(chǔ)課。涉及算法、計算機(jī)操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫技術(shù)和軟件工程五門課程的經(jīng)典內(nèi)容。通過該課程的學(xué)習(xí)，使學(xué)生掌握應(yīng)用軟件開發(fā)所必需的基礎(chǔ)知識，為今后結(jié)合本專業(yè)開發(fā)應(yīng)用軟件打下必要的基礎(chǔ)。0.2課程基本要求了解常用的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)算法，初步掌握對不同類型的問題求解選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。掌握操作系統(tǒng)的基本概念和基本功能，了解計算機(jī)系統(tǒng)硬、軟件資源如何控制管理。了解如何以近代軟件工程的觀點(diǎn)開發(fā)應(yīng)用軟件的基本概念和方法。了解數(shù)據(jù)庫的基本概念，初步掌握數(shù)據(jù)庫系統(tǒng)的開發(fā)方法。0.3學(xué)習(xí)軟件的重要作用社會對“軟件”的需求激增。美國國家將軟件列為六大關(guān)鍵技術(shù)之一；歐盟將“軟件和信息處理”列為關(guān)鍵技術(shù)；我國把信息產(chǎn)業(yè)放在優(yōu)先發(fā)展的地位，看作是中國發(fā)展高新技術(shù)、趕超世界先進(jìn)水平的一次千載難逢的機(jī)遇。0.4課程內(nèi)容

軟件技術(shù)基礎(chǔ)是一門從事計算機(jī)軟件開發(fā)及應(yīng)用程序設(shè)計的必不可少的基礎(chǔ)課?！端惴ā贰稊?shù)據(jù)結(jié)構(gòu)》（重點(diǎn)內(nèi)容）《軟件工程》《操作系統(tǒng)》《數(shù)據(jù)庫系統(tǒng)》0.4.1數(shù)據(jù)結(jié)構(gòu)

從以下三個方面入手學(xué)習(xí)邏輯結(jié)構(gòu)+存儲結(jié)構(gòu)學(xué)習(xí)基于這種數(shù)據(jù)結(jié)構(gòu)的基本操作這種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用0.4.2操作系統(tǒng)學(xué)習(xí)方法學(xué)習(xí)操作系統(tǒng)從這幾個方面入手如何能夠提高系統(tǒng)資源的利用率更有效地組織、協(xié)調(diào)、管理計算機(jī)內(nèi)部的工作流程為用戶提供更友好、便捷的操作界面0.4.3數(shù)據(jù)庫系統(tǒng)學(xué)習(xí)方法學(xué)習(xí)數(shù)據(jù)庫系統(tǒng)從這幾個方面入手（1）如何設(shè)計數(shù)據(jù)表（數(shù)據(jù)依賴、規(guī)范化）（2）如何查找（投影、聯(lián)結(jié)、并、交、補(bǔ)等關(guān)系運(yùn)算）（3）這些操作如何用數(shù)學(xué)的方法運(yùn)算0.4.4軟件工程學(xué)習(xí)學(xué)習(xí)軟件工程從這幾個方面入手（1）軟件工程是如何解決軟件開發(fā)中的管理和技術(shù)問題。（2）軟件生命周期，包括階段劃分、文檔、評審等概念。（3）掌握幾種軟件工程新方法如：原形法、結(jié)構(gòu)化、面向?qū)ο蟆?.5考核方法（1）平時考勤+5次作業(yè)（20%）（2）期末考試（80%）。第一章算法1.1

算法的基本概念

1.1.1

算法的基本特征

1.1.2

算法的要素1.2

算法描述語言1.3

算法設(shè)計基本方法1.4

算法復(fù)雜度分析

1.4.1

時間復(fù)雜度

1.4.2

空間復(fù)雜度

教學(xué)目標(biāo)

了解算法的基本概念、算法描述語言，掌握幾種常見算法的基本實現(xiàn)，并能分析算法的時間和空間復(fù)雜度。學(xué)習(xí)要點(diǎn)

⑴掌握算法的基本概念和基本特征

⑵理解常用的幾種算法的思想例如：列舉法， 遞推法，遞歸法和減半遞推。

⑶算法復(fù)雜度的概念和意義（時間復(fù)雜度與空 間復(fù)雜度）。引出算法行為特性的設(shè)計

將解決實際問題的每個細(xì)節(jié)準(zhǔn)確地加以定義，并且還應(yīng)當(dāng)將全部解題過程完整地描述出來。這就是算法的設(shè)計。

結(jié)構(gòu)特性的設(shè)計

確定合適的數(shù)據(jù)結(jié)構(gòu)。

1.1算法基本概念算法（Algorithm）是對特定問題求解步驟的一種描述；是一組指令的有限集合。算法的基本特征

能行性：算法中描述的操作都是可通過已經(jīng)實現(xiàn)的基本運(yùn)算、執(zhí)行有限次實現(xiàn)的；

確定性：算法中的每一條指令必須有明確的含義，不能有二義性；

有窮性：一個算法必須總是在執(zhí)行有窮步后結(jié)束，且每一步都可在合理的執(zhí)行時間內(nèi)完成；

擁有足夠情報：一個算法應(yīng)有0個或多個輸入；結(jié)論：

所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的、明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。

1.1.2算法的基本要素算法中對數(shù)據(jù)的運(yùn)算和操作

（1）算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)算。（2）邏輯運(yùn)算：主要包括“與”、“或”、“非”等運(yùn)算。（3）關(guān)系運(yùn)算：主要包括“大于”、“小于”、“等于”、“不等 于”等運(yùn)算。（4）數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。算法的控制結(jié)構(gòu)給出了算法的基本框架，算法一般都可以用順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組合而成1.2算法的描述

算法的描述方式（常用的）：算法描述自然語言

流程圖特定的表示算法的圖形符號偽語言包括程序設(shè)計語言的三大基本 結(jié)構(gòu)及自然語言的一種語言類語言類似高級語言的語言，例如，類PASCAL，類c語言本課程采用的算法描述語言1.符號與表達(dá)式2.賦值語句3.控制轉(zhuǎn)移語句4.循環(huán)語句

5.其他語句

1.符號與表達(dá)式符號

是以字母開頭的字母和數(shù)字的有限串，主要用以表示變量名、數(shù)組名等，必要時也用來表示語句標(biāo)號。

在語句標(biāo)號后應(yīng)跟隨一個冒號，然后是語句。例如loop：i＝i＋1算法中一般對變量或數(shù)組的數(shù)據(jù)類型不作說明算術(shù)運(yùn)算符沿用數(shù)學(xué)中的表示法（1）關(guān)系運(yùn)算符用：=、≠、＜、＞、≤、≥等表示。（2）邏輯運(yùn)算符用and(與)、or(或)、not（非）等表示。

2.賦值語句普通賦值

例如：a=e內(nèi)容交換

例如：a←→b多個變量同時賦值例如：a=b=e表示將表達(dá)式e的計算結(jié)果同時賦給a與b。

3.控制轉(zhuǎn)移語句

無條件轉(zhuǎn)移語句

GOTO標(biāo)號

條件轉(zhuǎn)移語句有以下兩種形式

IFCTHENS或

IFCTHENS1ELSES2C是一個邏輯表達(dá)式，S、S1和S2是單一的語句或者是用一對括號{}括起來的語句組。4.循環(huán)語句

WHILE語句的形式為形式：WHILECDOSFOR語句的形式為

FORi＝initTOlimitBYstepDOS5.其他語句

EXIT語句主要用于退出某個循環(huán)。RETURN語句用于結(jié)束算法的執(zhí)行。READ（或INPUT）和WRITE（或PRINT，或OUTPUT）語句分別用于輸入和輸出。1.3算法設(shè)計基本方法列舉法歸納法遞推遞歸減半遞推技術(shù)回溯法1.列舉法基本思想

根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦切枰?，哪些是不需要的。因此，列舉法常用于解決“是否存在”或“有多少種可能”等類型的問題，例如求解不定方程的問題。

例題：設(shè)每只母雞值3元，每只公雞值2元，每只小雞值0.5元?，F(xiàn)要用100元錢買100只雞，設(shè)計買雞方案，這就是經(jīng)典的求解百雞問題。PROCEDUREBAIJIFORI=0TO100DOFORJ=0TO100DOFORK=0TO100DO{M＝I+J+KN＝3I十2J+0.5KIF（（M＝100）and（N＝100））THENOUTPUTI，J，K}RETURN總循環(huán)次數(shù)為1013＝1030301

首先，考慮到母雞為3元一只，因此，母雞最多只能買33以，即算法中的外循環(huán)沒有必要從0到100．而只需要從0到33就可以了。其次，考慮到公雞為2元一只，因此，公雞最多只能頭50只。又考慮到對公雞的列舉是在算法的第二層循環(huán)中，此時已經(jīng)買了I只母雞，且買一只母雞的價錢相當(dāng)于買1.5只公雞。因此，由第一層循環(huán)已經(jīng)確定買I只母雞的前提下，公雞最多只能買50-1.5I只，即第二層對J的循環(huán)只需從0到50-1.5I就可以了。最后，考慮到買的總雞數(shù)為100，而由第一層循環(huán)已確定買I只母雞，由第二層循環(huán)已確定買J只公雞，因此，買小雞的數(shù)量只能是K=100-I-J，即第三層循環(huán)已經(jīng)沒有必要了。改進(jìn)后的算法算法描述語言PROCEDUREBAIJIFORI＝0TO33DOFORJ=0TO50-1.5IDO {K=100-I-J IF（3I+2J+0.5K=100）THEN OUTPUTI，J，K}RETURN總循環(huán)次數(shù)為C語言算法：#include“stdio.h”main（）{inti,j,k;for(i=0;i<=33;i++)for(j=0;j<=50-1.5*i;j++){k=100-i-j; if(3*i+2*j+0.5*k==100.0) printf（”%5d%5d%5d\n”,i,j,k）; }}列舉法改進(jìn)后的算法（C語言）2.歸納法歸納法的基本思想

通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。歸納是一種抽象

即從特殊現(xiàn)象中找出一般關(guān)系。但由于在歸納的過程中不可能對所有的情況進(jìn)行列舉，因此，最后由歸納得到的結(jié)論還只是一種猜測，還需要對這種猜測加以必要的證明。3.遞推法基本思想

從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。其中初始條件或是問題本身已經(jīng)給定，或是通過對問題的分析與化簡而得到確定。

例題遞推法例題分析發(fā)現(xiàn)相鄰兩個積分之間存在以下關(guān)系:

只要知道In-1

就可以算出In

，也就是說，只要知道了I0，就可以通過這個遞推公式計算出所有的積分值In（n=1，2，…，20）。

這個關(guān)系就可以得到如下遞推公式遞推法例題分析相鄰兩個積分之間除了具有遞推關(guān)系式:以外，還滿足下列不等式因而，I20

應(yīng)比I0小。且所有的積分值都不可能為負(fù)。因此，由遞推算法(1.3)得到的結(jié)果（表1.1）是不可靠的。遞推法

例題分析--改進(jìn)方法根據(jù)遞推關(guān)系式可以改進(jìn)成另一個遞推公式：

遞推關(guān)系如下：遞推法總結(jié):

例題分析--改進(jìn)前后在老遞推算法中，初值是近似的，即實際上存在一個誤差；老遞推算法遞推過程中，當(dāng)計算到I20時，其誤差是初值誤差的520倍。在新遞推算法中，雖然初值I30是近似的，而且誤差可能很大。但在用新遞推算法遞推過程中，每遞推計算一次，后一個計算值的誤差是前一個計算值誤差的1/5，因此，當(dāng)計算到I20時，其誤差是初值I30誤差的1/510。4.遞歸法基本思想（1）為了降低問題的復(fù)雜程度，總是將問題逐層 分解，最后歸結(jié)為一些最簡單的問題。（2）這種將問題逐層分解的過程，實際上并沒有 對問題進(jìn)行求解，而只是當(dāng)解決了最后那些 最簡單的問題后，再沿著原來分解的逆過程 逐步進(jìn)行綜合，這就是遞歸的基本思想。（3）因此，遞歸的基礎(chǔ)也是歸納。遞歸法舉例說明例：編寫一個過程，對于輸入的參數(shù)n，依次打印輸 出自然數(shù)1到n。非遞歸算法。PROCEDUREWRT(n)FORk=1TOnDOOUTPUTkRETURN遞歸算法。PROCEDUREWRT1（n）IF（n≠0）THEN{WRT1（n-1）

OUTPUTn}RETURN

總結(jié)：遞歸是構(gòu)造計算機(jī)算法的一種基本方法。如果一個過程直接或間接地調(diào)用它自身，則稱該過程是遞歸的，遞歸過程必須有一個遞歸終止條件，即存在“遞歸出口”。無條件的遞歸是毫無意義的。遞歸分為直接遞歸與間接遞歸兩種。如果一個算法P顯式地調(diào)用自己則稱為直接遞歸，例如算法1.4是一個直接遞歸的算法。如果算法P調(diào)用另一個算法Q，而算法Q又調(diào)用算法P，則稱為間接遞歸調(diào)用。遞歸過程能將一個復(fù)雜的問題歸結(jié)為若干個較簡單的問題，然后將這些較簡單的每一個問題再歸結(jié)為更簡單的問題，這個過程可以一直做下去，直到最簡單的問題為止。遞歸與遞推是既有區(qū)別又有聯(lián)系的兩個概念。遞推是從已知的初始條件出發(fā)，逐次遞推出最后所求的值。遞歸則是從需求的函數(shù)本身出發(fā)，逐次上溯調(diào)用其本身求解過程，直到遞歸的出口，然后再從里向外倒推回來，得到最終的值。一般說來，一個遞推算法總可以轉(zhuǎn)換為一個遞歸算法。5.減半遞推技術(shù)舉例說明：兩個n階矩陣相乘，通常需要作n3次乘法。那么兩個二階矩陣相乘需要作8次乘法。其乘積矩陣C＝AB為：對于低階的矩陣相乘問題，如二階矩陣相乘，減少乘法次數(shù)是有可能的。令：

減半遞推技術(shù)舉例乘積矩陣C中的各元素可用以上7個量的線性組合來表示：上述方法計算兩個二階矩陣相乘只需要7次乘法就夠了，比通常的方法減少了1次乘法。以此類推，最后可以歸結(jié)為計算一階矩陣相乘的問題，而一階矩陣相乘只需要一次乘法。減半遞推技術(shù)舉例根據(jù)以上分析，假設(shè)，且階矩陣相乘所需要的乘法次數(shù)為M（k），則有減半遞推技術(shù)

例題分析因此有減半遞推技術(shù)

總結(jié)：對問題分而治之。工程上常用的分治法是減半遞推技術(shù)。這個技術(shù)在快速算法的研究中有很重要的實用價值。所謂“減半”，是指將問題的規(guī)模減半，而問題的性質(zhì)不變，所謂“遞推”，是指重復(fù)“減半”的過程。例題設(shè)方程f(x)=0在區(qū)間[a,b]上有實根，且f(a)與f(b)異號。利用二分法求該方程在區(qū)間[a,b]上的一個實根。分析：首先取給定區(qū)間的中點(diǎn)c=(a+b)/2。然后判斷f(c)是否為0。若f(c)=0，則說明c即為所求的根，求解過程結(jié)束；如果f(c)≠0，則根據(jù)以下原則將原區(qū)間減半：

若f(a)f(c)<0，則取原區(qū)間的前半部分；若f(b)f(c)<0，則取原區(qū)間的后半部分。最后判斷減半后的區(qū)間長度是否已經(jīng)很小。若|a-b|<ε，則過程結(jié)束，?。╝+b）/2為根的近似值；否則，則重復(fù)上述的減半過程。doubleroot(a，b，eps，f)doublea,b,exp,(*f)()f0＝f(a)while(|a－b|≥eps)DO{c＝(a＋b)/2；

f1＝(*f)(c)if(f1==0){returnc}if(f0*f1＞0)a＝celseb＝c;}c＝(a＋b)/2；

return(c)6.回溯法

基本思想在工程上，有些實際問題卻很難歸納出一組簡單的遞推公式或直觀的求解步驟，并且也不能進(jìn)行無限的列舉。一種有效的方法是“試”。通過對問題的分析，找出一個解決問題的線索；然后沿著這個線索逐步試探。對于每一步試探，若試探成功，就得到問題的解；若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。這種方法稱為回溯法。例：n皇后問題（n=4）1.4算法的復(fù)雜度分析算法評價的標(biāo)準(zhǔn)：時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度指在計算機(jī)上運(yùn)行該算法所花費(fèi)的時間。常以基本運(yùn)算的重復(fù)次數(shù)來衡量。用“O（數(shù)量級）”來表示，稱為“階”。常見的時間復(fù)雜度有：

O(1)，O(logn)，O(n)，O(n2)，O(2n)

常數(shù)階對數(shù)階線性階平方階指數(shù)階空間復(fù)雜度指算法在計算機(jī)上運(yùn)行所占用的存儲空間的大小。（程序、輸入、額外輔助）

平均性態(tài)所謂平均性態(tài)分析，是指用各種特定輸入下的基本運(yùn)算次數(shù)的帶權(quán)平均值來度量算法的工作量。設(shè)x是所有可能輸入中的某個特定輸入，p(x)是x出現(xiàn)的概率（即輸入為x的概率），t(x)是算法在輸入為x時所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為：最壞情況復(fù)雜性所謂最壞情況分析，是指在規(guī)模為n時，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為：例題例：采用順序搜索法，在長度為n的一維數(shù)組中查找值為x的元素。即從數(shù)組的第一個元素開始，逐個與被查值x進(jìn)行比較。基本運(yùn)算為x與數(shù)組元素的比較。平均性態(tài)分析

設(shè)被查項x在數(shù)組中的概率為q

如果已知需要查找的x一定在數(shù)組中，此時q＝1，則A(n)=（n＋l）／2。如果已知需要查找的x有一半的機(jī)會在數(shù)組中，此時q＝1／2；則A(n)=[(n+1)/4]+n/2≈3n/4最壞情況分析在這個例子中，最壞情況發(fā)生在需要查找的x是數(shù)組中的最后一個元素，或x不在數(shù)組中的時候，此時顯然有：算法的最優(yōu)性衡量算法的好壞主要依據(jù)算法的復(fù)雜度，特別是時間復(fù)雜度。通?？偸窃谧顗牡那闆r下分析算法的工作量。最優(yōu)算法是指在解決一個問題時，如果在被研究的算法類中，沒有一個算法比現(xiàn)有算法執(zhí)行更少的基本運(yùn)算，則稱此算法是最優(yōu)的。

總結(jié)：算法的基本概念算法的基本特征算法的要素算法描述語言算法設(shè)計基本方法算法復(fù)雜度分析第二章

基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

第

2

章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

（有*號的標(biāo)題表示最基本的內(nèi)容）

2.1數(shù)據(jù)結(jié)構(gòu)的基本概念*2.1.1

什么是數(shù)據(jù)結(jié)構(gòu)2.2線性表

2.2.1

線性表的基本概念

2.2.2

線性順序表及其運(yùn)算

2.2.3

線性鏈表及其運(yùn)算

2.2.4

棧及其應(yīng)用

2.2.5

隊列及其應(yīng)用教學(xué)內(nèi)容一、數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、 物理結(jié)構(gòu)、算法、特征、評價二、順序表 線性表、順序表、描述、創(chuàng)建、插入、刪除等算法三、鏈表單鏈表、循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表判空、插入、刪除、定位等操作指針域、數(shù)據(jù)域、頭節(jié)點(diǎn)、頭指針2.1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)（Data）能存于計算機(jī)、并被計算機(jī)處理的符號的集合。它是客觀事物的符號表示。數(shù)據(jù)元素（Element）

是數(shù)據(jù)的基本單位、數(shù)據(jù)集合中的個體。數(shù)據(jù)結(jié)構(gòu)（DataStructure）是帶有結(jié)構(gòu)特征的數(shù)據(jù)元素的集合；它有三個要素：

DS=數(shù)據(jù)的邏輯結(jié)構(gòu)+存儲結(jié)構(gòu)+數(shù)據(jù)的運(yùn)算一.基本概念二.數(shù)據(jù)的邏輯結(jié)構(gòu)概念：客觀事物本身存在的結(jié)構(gòu)形式及關(guān)系。特點(diǎn)：描述數(shù)據(jù)間的順序（邏輯）關(guān)系，抽象地反映數(shù)據(jù)元素的結(jié)構(gòu)，而不管它們在計算機(jī)中如何存放。

與物理存放位置無關(guān)描述方法：用二元組來描述：

DS=（D，R）其中：

D：是數(shù)據(jù)元素的有限集合；

R：是數(shù)據(jù)元素之間關(guān)系的集合。成員：由1名教師、1~3名研究生、1~6名本科生組成；成員關(guān)系是：教師指導(dǎo)研究生、研究生指導(dǎo)1~2名本科生。數(shù)據(jù)結(jié)構(gòu)的形式化描述：定義DS如下：

Group=（D，R）其中：D={T，G1，…,Gn,S11,…Snm}1≤n≤3,1≤m≤2R={R1,R2}R1={<T,Gi>|1≤i≤n,1≤n≤3}R2={<Gi,Sij>|1≤

i≤

n,1≤

j≤m,1≤n≤3,1≤m≤2}1.數(shù)據(jù)的邏輯結(jié)構(gòu)-舉例（1）線性結(jié)構(gòu)：一對一次序關(guān)系（2）樹形結(jié)構(gòu)：一對多層次關(guān)系（3）圖或網(wǎng)狀結(jié)構(gòu)：多對多關(guān)系（4）集合：屬性相同，元素間沒有關(guān)系2.數(shù)據(jù)邏輯結(jié)構(gòu)的類別三、數(shù)據(jù)的存儲結(jié)構(gòu) ~是指數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示(又稱映象)，即數(shù)據(jù)在計算機(jī)中的存放形式。 邏輯結(jié)構(gòu)在存儲器中的映射。又稱物理結(jié)構(gòu)數(shù)據(jù)存儲結(jié)構(gòu)分類1.順序存儲結(jié)構(gòu)2.鏈?zhǔn)酱鎯Y(jié)構(gòu)3.索引存儲結(jié)構(gòu)（略）4.散列存儲結(jié)構(gòu)（略）1.順序存儲結(jié)構(gòu)概念：把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存 儲單元中的存儲形式。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu):

d1d2……dn數(shù)據(jù)域特點(diǎn):

連續(xù)存放;邏輯上相鄰,物理上也相鄰。結(jié)構(gòu)簡單，易實現(xiàn)。插入、刪除操作不便（需大量移動元素）。2.鏈?zhǔn)酱鎯Y(jié)構(gòu)概念：以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元 中，可連續(xù)存放，也可以不連續(xù)存放，以指 針實現(xiàn)鏈表間的聯(lián)系。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu):

d1...

d2dn

^特點(diǎn):

非連續(xù)存放,借助指針來表示元素間的關(guān)系;插入、刪除操作簡單，只要修改指針即可；結(jié)構(gòu)較復(fù)雜，需要額外存儲空間。數(shù)據(jù)域指針域

總結(jié)：

（1）邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨(dú)立于計算機(jī)的；可以在理論上、形式上進(jìn)行研究、推理、運(yùn)算等各種操作。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機(jī)中的實現(xiàn)，是依賴于計算機(jī)的；離開了機(jī)器，則無法進(jìn)行任何操作。任何一個算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)；而算法的最終實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)：獨(dú)立于計算機(jī)。存儲結(jié)構(gòu)：依賴于計算機(jī)算法設(shè)計考慮邏輯結(jié)構(gòu)，算法實現(xiàn)依賴存儲結(jié)構(gòu)。總結(jié)：

（2）數(shù)據(jù)結(jié)構(gòu)分類線性表堆棧隊列串?dāng)?shù)組樹二叉樹圖線性結(jié)構(gòu)非線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)DS2.2線性表

2.2.1線性表基本概念線性表是指數(shù)據(jù)元素之間的關(guān)系為一一對應(yīng)的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。

例如，一星期七天的英文縮寫表示：

（Sun，Mon，Tue，Wed，Thu，F(xiàn)ri，Sat）是一個線性表，其中的元素是字符串，表的長度為7。線性表雖然簡單，但是應(yīng)用范圍非常廣泛。非空線性表的結(jié)構(gòu)特征有且只有一個根結(jié)點(diǎn)a1，它無前件；有且只有一個終端結(jié)點(diǎn)an，它無后件；除根結(jié)點(diǎn)和終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個前件，也有且只有一個后件。一、線性表的邏輯結(jié)構(gòu)定義：線性表是n（n≥0）個元素a1,a2,…,an

的有限序列；表中每個數(shù)據(jù)元素，除第一個外，有且只有一個前件；除最后一個外，有且只有一個后件。即線性表或是一個空表，或可以表示為例如：一星期七天的英文縮寫表示：（Sun，Mon，Tue，Wed，Thu，F(xiàn)ri，Sat）是一個線性表，其中的元素是字符串，表的長度為7。二、元素關(guān)系描述1）L的長度為n（n≥0），當(dāng)n為0時，表示是空表；

2）每個元素（除了第1個和最后一個元素外），有唯一的前件和后件；3）線性表中各元素間存在著線性關(guān)系；4）均勻性；各元素數(shù)據(jù)類型必須相同；5）有序性；各元素是有序的，不可交換次序。2.2.2線性順序表存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)

將表中元素一個接一個的存入一組連續(xù)的存儲單元中，這種存儲結(jié)構(gòu)是順序結(jié)構(gòu)。順序表

采用順序存儲結(jié)構(gòu)的線性表簡稱為“順序表”。順序表的存儲特點(diǎn)：只要確定了起始位置，表中任一元素的地址都通過下列公式得到：

LOC（ai）=LOC（a1）+（i-1）*L1in

其中，L是每個元素占用存儲單元的長度。一、定義二、線性表元素存儲示意圖

a1a2….ai….元素序號內(nèi)存狀態(tài)存儲地址2

i1….….LOC(a1)LOC(a1)+1L….LOC(a1)+(i-1)L….三、線性表的基本操作Setnull（L）置空表Length（L）求表長度；求表中元素個數(shù)Get（L，i）取表中第i個元素（1in）Prior（L，i）取i的前件元素Next（L，i）取i的后件元素Locate（L，x）返回指定元素在表中的位置Insert（L，i，x）插入元素Delete（L，x）刪除元素Empty（L）判別表是否為空順序表(SeqList)類的定義template<classType> classSqList{Type*v;//順序表存儲數(shù)組

intmm; //最大允許長度

intnn; //當(dāng)前線性表的長度public: Sq_LList(){mm=0;nn=0}; Sq_LList(int);

intPrt_sq_list(Type&x);//前驅(qū)

intflag_sq_LList();voidins_sq_LList(int,T);voiddel_sq_LLIst()}1.插入算法線性表的存放形式：采用一維數(shù)組存放。操作要求：將X插入線性表（a1,a2,……,an）中 的第i個位置算法步驟:

step1將第n至第i個元素后移一個存儲位置;

step2將x插入到ai-1之后;

step3表的長度加1。表項的插入2534571648096301234567data50插入x253457501648096301234567data50i長度為n的線性表中的第i個元素之前插入新元素b。PROCEDUREINSL（V，m，n，i，b）IF（n=m）THEN{OVERFLOW；RETURN}IF(i>n)THENi＝n＋1IF（i＜1)THENi＝1FORj=nTOiBY–1DOV（j+1）=V（j）V(i)=bn＝n＋1RETURNtemplate<classT>intSq_LList<T>::Ins_sq_LList(T*v,int*n;inti;Tb)//在表中第

i個位置插入新元素

b

{intk;if(*n==m){cout<<“overflow”<<endl;return;}if(i>*n)i=*n+1;if(i<1)i=1;for(k=*n;k>=i;k--)v[k]=v[k-1];v[i-1]=b;*n=*n+1;return;}2.刪除算法線性表的存放形式：采用一維數(shù)組存放。操作要求：刪除線性表(a1,a2,……,an)中的第i個元素算法步驟:step1判別指定的位置是否合法；

step2若合法，則將位置i+1至n上的元素前移一個存儲位置;

step3表的長度減1。表項的刪除253457501648096301234567data16刪除

x2534575048096301234567data在長度為n的線性表中刪除第i個元素PROCEDUREINSL（V，m，n，i）IF（n=0）THEN{UNDERFLOW；RETURN}IF((i<1)or(i>n))THEN{“Notthiselementinthelist”;RETURN}FORj=iTOn-1DOV（j）=V（j+1）n＝n-1RETURN

template<classT>voiddel_sq_LList(T&v,intm,int*n,inti){//在表中刪除已有第i元素

intk;if(*n==0){cout<<“underflow”<<endl; return; }if(i<1||i>*n){cout<<“underflow”<<endl; return; }for(k=i;k<*n;k++)v[k-1]=v[k];*n=*n-1;return0;

}總結(jié)：

順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)數(shù)據(jù)連續(xù)存放、隨機(jī)存取邏輯上相鄰，物理上也相鄰存儲結(jié)構(gòu)簡單、易實現(xiàn)插入、刪除操作不便存儲密度大，空間利用率高結(jié)論：

順序存儲結(jié)構(gòu)適合于表中元素變動較少的情況。2.2.3線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)容易實現(xiàn)，可以隨機(jī)存取表中的任意元素。順序表缺點(diǎn)是：難于插入、刪除操作；需要預(yù)先分配空間，不管這些空間能否最大限度地利用。鏈表存儲結(jié)構(gòu)在這兩個方面恰好是優(yōu)點(diǎn)：容易插入、刪除操作不需要預(yù)分空間。一、鏈表有關(guān)基本概念定義：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表

結(jié)點(diǎn)（NODE）：表中元素的存儲單元。由數(shù)據(jù)域和指針域組成。數(shù)據(jù)域存放元素數(shù)據(jù)，指針域存放指向下一結(jié)點(diǎn)位置的指針。結(jié)點(diǎn)形式為：

datanext數(shù)據(jù)域指針域鏈表（Link）：由結(jié)點(diǎn)組成的表。頭指針（head）：指向鏈表中第1個結(jié)點(diǎn)的指針。頭結(jié)點(diǎn)：為方便操作，在頭指針和第1個結(jié)點(diǎn)之 間設(shè)置的結(jié)點(diǎn)。首元結(jié)點(diǎn)

第一個結(jié)點(diǎn)（a1）。head頭指針a1首元結(jié)點(diǎn)

ai...第i個結(jié)點(diǎn)頭結(jié)點(diǎn)舉例由食品組成的單鏈表（biscuit,butter,cheese,eggs,grapes,jam)

不帶頭結(jié)點(diǎn)。grapesbiscuitbuttercheesejameggs^head

頭指針單鏈表的物理存儲

存儲地址數(shù)據(jù)域（data）指針域（next）grapes60biscuit61cheese13eggs1jamNULLbutter121111213606111頭指針

head（biscuit,butter,cheese,eggs,grapes,jam)二、C++語言實現(xiàn)Template<classT>structnode{Tdata;node*next;};Template<classT>classlinked_list{private:node<T>*head;public:linked_list();//建立空鏈表

intflag_linked_list();//判斷鏈表狀態(tài)

{if(head==NULL)return0;return1;}voidprt_linked_list();//從頭指針開始輸出

voidins_linked_list(T);//插入到鏈表頭

Tdel_linked_list();//刪除鏈頭}空表和非空表表示形式在頭結(jié)點(diǎn)上得到統(tǒng)一空表的形式

:head->next=NULL

head^頭結(jié)點(diǎn)head頭結(jié)點(diǎn)非空表的形式:head->Next=Address頭節(jié)點(diǎn)與無頭節(jié)點(diǎn)三、單鏈表的操作1.指針的基本操作

2.鏈表的動態(tài)生成

3.單鏈表的查找4.單鏈表的的插入insert5.單鏈表的刪除delete1.指針的基本操作設(shè)指針變量p、q的定義為：NODE*p，*q；對鏈表的操作實際上是對指針的操作。例如，要刪除結(jié)點(diǎn)ai，首先要使指針p指向ai，即：a1......headaian^p指針p是存儲單元的地址，地址內(nèi)的內(nèi)容可以通過V(p)得到，指向下個元素的指針用next(p)得到

指針的基本操作列表p=（NODE*）malloc（sizeof（NODE））申請一個結(jié)點(diǎn)空間，并將地址送入p中。free（p）釋放p指針?biāo)附Y(jié)點(diǎn)的空間p=q指針p指向指針q所指的結(jié)點(diǎn)p=q->next指針p指向指針q所指結(jié)點(diǎn)的后件p=p->next指針p向后移動一個結(jié)點(diǎn)p->next=q將指針q所指結(jié)點(diǎn)改接為指針p所指結(jié)點(diǎn) 的后件p->next=NULL將指針p所指結(jié)點(diǎn)與后件結(jié)點(diǎn)斷開

指針操作的舉例p=q->nextp指向q所指結(jié)點(diǎn)的后件操作前狀態(tài)aiai-1ai-1qpaiai-1ai+1qp操作后狀態(tài)2、鏈表的動態(tài)生成鏈表是一種動態(tài)存儲結(jié)構(gòu)。因此，建立鏈表的過程是動態(tài)生成的過程。按鏈表結(jié)點(diǎn)建立的順序、方向不同，分為兩種方法：從前往后的動態(tài)生成法 將元素插入鏈表的末尾從后往前的動態(tài)生成法 總是將元素插入到鏈表的第一個位置從后往前1)使p指向新生成的結(jié)點(diǎn)，2)p->d=x，p->next=head3)修改頭指針head=p

head

...

pai-1aianai-1template<classT>voidlinked_llist<T>::ins_linked_list(Tx){node<T>*p;p=newnode<T>;p->d=x;p->next=head;head=p;return;}從前往后算法操作步驟：

1)使p指向新生成的結(jié)點(diǎn)，p->d=x2)若head=NULL(第1個結(jié)點(diǎn))，head=p3)否則循環(huán)到最后一個節(jié)點(diǎn)，s->next=p4)頭指針不變...head

^ai-1a2a1p2s34

ai1template<classT>voidlinked_llist<T>::ins_linked_list1(Tx){node<T>*p;p=newnode<T>;p->d=x;p->next=NULLs=head;q=s->next;while(q!=NULL){q=q->next;s=s->next;}s->next=p;return;}4.單鏈表的查找算法查找第i個元素，返回指向它的指針?biāo)惴ú僮鞑襟E:step1初始化，指針P指向頭指針，計數(shù)器置0；step2P非空且計數(shù)器小于i循環(huán)；step3每循環(huán)一次，P后移一個位置，計數(shù)器加1；step4循環(huán)結(jié)束，返回指向ai的指針P。

NODE*get(NODE*head,intｉ）(無頭結(jié)點(diǎn))｛NODE*p;intcounter=0;//計數(shù)器

p=head;//p指向第1個結(jié)點(diǎn)

while((p!=NULL)&&(counter<i)){p=p->next;counter++;}//查找

if((p!=NULL)&&(counter==i))returnp;//找到

elsereturnNULL;//沒找到

}template<classT>ListNode<T>*List<T>::Find(Tvalue){//在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)

p=head->next;

//當(dāng)前指針

p

指示第一個結(jié)點(diǎn)

while(p!=NULL)if(p->d==value)break;elsep=head->next;returnp;}5.單鏈表插入算法在第i個位置插入算法操作步驟:step1找到ai-1的位置，使指針p指向ai-1step2申請并生成新結(jié)點(diǎn)sstep3使s插入到ai-1和ai之間

s->next=p->nextp->next=ss->data=x（3）（2）pxai-1ais（1）

insert(NODE*head,inti,intx){NODE*p,*s;if(i==1)p=head;elsep=get(head,i-1);if(p==NULL){printf(“插入位置錯\n”);exit(0);}else{s=(NODE*)malloc(sizeof(NODE));s->data=x; s->next=p->next;p->next=s;}}

/*令P指向Ai-1*//*若i=1，P指向頭指針*//*P為空，說明找不到i位置*//*P定位成功*//*P定位操作*/5.單鏈表插入算法在x之前插入b算法操作步驟:step1找到x的位置，使指針p指向x前一結(jié)點(diǎn)step2申請并生成新結(jié)點(diǎn)sstep3使s插入s->next=p->nextp->next=ss->data=x（3）（2）pbxs（1）template<classT>voidlinked_llist<T>::ins_linked_llist(Tx){node<T>*p,*q;p=newnode<T>;p->d=b;if(head==NULL){head=p;p->next=NULL;return;}if(head->d==x){p->next=head;head=p;return;}

q=head;while((q->next!=NULL)&&((q->next)->d)!=x))q=q->next;p->next=q->next;q->next=p;return;}6.單鏈表刪除算法刪除第i個元素的算法操作步驟:step1找到ai-1的位置，使指針p指向ai-1；step2使指針t指向p所指結(jié)點(diǎn)的后繼；step3使t所指結(jié)點(diǎn)ai脫鏈；step4釋放t。ai-1aiai+1t=p->nextp->next=t->nextfree(t)p1t23

delete(NODE*head,inti){NODE*p,*t;if(i==1)p=head;elsep=get(head,i-1);if(p==NULL){printf(“i<1或i>表長+1,無此結(jié)點(diǎn)\n”);exit(0);}if(p->next==NULL){printf(“i=表長+1,無此結(jié)點(diǎn)\n”);exit(0);}else{t=p->next;p->next=t->next;free(t);}}/*P定位操作*//*P定位成功*/

刪除元素x算法操作步驟:step1找到x的前一個結(jié)點(diǎn)位置，使指針p指向它；step2使指針t指向p所指結(jié)點(diǎn)的后件；step3使t所指結(jié)點(diǎn)x

脫鏈；step4釋放t。ai-1aiai+1t=p->nextp->next=t->nextfree(t)p1t23template<classT>intlinked_llist<T>::ins_linked_llist(Tx){node<T>*p,*q;if(head==NULL)return0;if(head->d==x){p=head->next;deletehead;head=p;return1}q=q->next;while((q->next!=NULL)&&(q->next->d!=x))q=q->next;if(q->next==NULL)return0;p=q->next;q->next=p->next;deletep;return1;}四、循環(huán)單鏈表和雙向鏈表鏈表檢索只能從頭指針開始，且只能順鏈表方向移動。在單鏈表中，從表的任一結(jié)點(diǎn)ai找其前趨結(jié)點(diǎn)，時間復(fù)雜度是O（n）。如果讓鏈表首尾相接，構(gòu)成環(huán)形，這就是單循環(huán)鏈表。如果在結(jié)點(diǎn)中增加一個指向前一個結(jié)點(diǎn)的指針域，鏈表可以從兩個方向檢索，效果更佳；這就是雙向循環(huán)鏈表。1.循環(huán)單鏈表(1)單循環(huán)鏈表表示形式：headhead...a1a2an單循環(huán)鏈表為空的條件:head->next=head表示形式為:(2)單循環(huán)鏈表特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)，均可以找到表中其它結(jié)點(diǎn)。找其前趨結(jié)點(diǎn)的時間復(fù)雜度是O（n）。2.雙向循環(huán)鏈表在單向循環(huán)鏈表中，也存在檢索前趨結(jié)點(diǎn)費(fèi)時的問題（所需時間是O（n））。雙向循環(huán)鏈表，其存儲結(jié)構(gòu)：template<classT>structnode{Td; node*next，*prior；

}；其它定義與單向鏈表相同。（1）雙向循環(huán)鏈表結(jié)點(diǎn)結(jié)構(gòu)指向后繼結(jié)點(diǎn)指針域數(shù)據(jù)域指向前趨結(jié)點(diǎn)指針域

priordatanext（2）雙向循環(huán)鏈表表示形式雙向循環(huán)鏈表表示形式：head^^head......ana2a1雙向循環(huán)鏈表為空的條件:

head->prior=head->next=head表示形式為:總結(jié):

雙向循環(huán)鏈表特點(diǎn)

適合于兩個方向的移動。找其前趨結(jié)點(diǎn)的時間復(fù)雜度是O(1)。五、鏈表存儲結(jié)構(gòu)的特點(diǎn)插入、刪除操作極為方便數(shù)據(jù)非連續(xù)存放、順序存取邏輯上相鄰，物理上不一定相鄰存儲結(jié)構(gòu)較復(fù)雜、需要額外的存儲空間結(jié)論：鏈表存儲結(jié)構(gòu)適合于表中元素頻繁變動的線性表?？偨Y(jié)：

1.單鏈表

結(jié)點(diǎn)、指針域、數(shù)據(jù)域、頭指針、頭結(jié)點(diǎn)。

2.單鏈表的描述

3.單鏈表的操作（1）指針操作、指針說明、分配存儲空間、判空、判滿、釋放空間（2）查找操作（3）插入（4）刪除

4.單鏈表的特點(diǎn)及適用場合

5.單循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表描述、建立、判空、查找、插入、刪除2.2.4棧及其應(yīng)用

內(nèi)容提要一、棧棧、棧頂指針 順序存儲、共享棧、鏈棧、入棧、出棧操作二、隊列隊列、順序存儲、隊頭指針、隊尾指針、約定循環(huán)隊列、鏈?zhǔn)疥犃校◣ь^結(jié)點(diǎn)）、入隊、出隊三、數(shù)組：行、列優(yōu)先順序存儲，矩陣的壓縮存儲2.2.4棧及其應(yīng)用1.棧及相關(guān)概念

堆棧(Stack)棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。棧結(jié)構(gòu)也稱為后進(jìn)先出表（LIFO）。棧、棧頂、棧底、空棧后進(jìn)先出表棧底固定，而棧頂浮動一、基本概念2.現(xiàn)實中的例子物料倉庫中的儲存機(jī)器零部件的裝配與拆卸3.棧有關(guān)概念棧頂指針在棧操作過程中，有一個專門的棧指針(習(xí)慣上稱它為TOP)，指出棧頂元素所在的位置。?？盏臈l件：top=0(top=-1)棧滿的條件：top=MAXSIZE（MAXSIZE-1）棧上溢棧空間是有限的，若棧已滿，再進(jìn)行入棧操作時，就要產(chǎn)生上溢棧下溢若?？?，再要執(zhí)行出棧操作，則會發(fā)生下溢。二、棧的順序存儲結(jié)構(gòu)（1）棧的順序存儲結(jié)構(gòu)：實際上是一維數(shù)組。（2）順序棧：棧的順序存儲結(jié)構(gòu)稱為順序棧。棧的操作只能在一端進(jìn)行；即棧頂位置隨進(jìn)棧和出棧而變化。（3）順序棧的C語言描述為：

三、棧的基本運(yùn)算SetNull（Stack）置棧為空；Empty（Stack）判定棧是否為空；Push（Stack，x）進(jìn)棧操作，在棧頂插入元素；Pop（Stack）出棧操作，刪除棧頂元素；Gettop（Stack）取棧頂元素template<classT>classsq_stack{private:int

top; //棧頂指針

T*s; //棧元素數(shù)組

intmm; //棧最大容量public:intPrt_sq_stack(T&x);//前驅(qū)

intflag_sq_stack();

棧的數(shù)組表示—順序棧TPop();//出棧

TRead_sq_stack();//取棧頂

voidpush();//}template<classT>sq_stack<T>::sq_stack(ints):top(0),mm(s){elements=newT[mm]; return;}舉例（1）有三個元素的進(jìn)棧序列是1，2，3。寫出可能的出棧序列。

出棧序列操作序列

123sxsxsx132sxssxx213ssxxsx231ssxsxx321sssxxx棧操作舉例（2）棧底棧頂a1a2……anMAXSIZETOPtop=-11.(空棧)

ABC2.top=2(A、B、C進(jìn)棧）AB3.top=1(C出棧）4.ABCDEFtop=MAXSIZE-1(棧滿）1.進(jìn)棧算法算法步驟:step1

判別棧滿否，若滿，則顯示棧溢出信息，停止執(zhí)行；否則，執(zhí)行step2；Step2

棧頂指針top上移(加1)；Step3

在top所指的位置插入元素x。voidsq_Stack<T>::push（Tx）{if(top＝＝m）{cout<<(“Stack－overflow＼n”)；

return；}top＝top＋l；

s[top－1］=x；

return；}2.出棧算法算法步驟:step1判別棧是否為空；若空，則輸出棧下溢信息，并停止執(zhí)行；否則，執(zhí)行step2；

step2彈出（刪除）棧頂元素；

step3棧頂指針top下移(減1)。

step4返回出棧元素Tsq_Stack<T>::pop（）{if(top==0){cout<<“Stack-underflow\n”；return；}y=s[top-1]；top=top-1；return；

}四、多棧共享問題如何充分利用棧空間，這是解決存儲空間緊張這樣一個實際矛盾所要考慮的問題。作為一種策略，就是多棧共享一個?？臻g。具體作法是：對兩棧共享情況來說，將兩個棧底分別設(shè)在兩端，兩個棧頂指針top1和top2相對中間位置動態(tài)移動，兩個棧之間的分界線是不定的。棧1、棧2均有若干元素top1top2top1=0top2=MAXSIZE+1

空棧top1top2棧滿的情況五、棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)由前面介紹的鏈表結(jié)構(gòu)可知，鏈結(jié)構(gòu)操作靈活。對棧結(jié)構(gòu)也是一樣的。順序棧最多可用于2個棧的共享，對于更多的棧就難于表達(dá)了。對于最大空間需要量事先不知的情況，就不能使用順序棧了。這時，就需要采用鏈棧。鏈棧：棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)Template<classT>structnode{Td;node*next;};template<classT>classsq_stack{private:

int

top;

//棧頂指針

T*s;

//棧元素數(shù)組

intmm;

//棧最大容量棧的數(shù)組表示—順序棧public:intPrt_link_stack(T&x);//前驅(qū)

intflag_link_stack();voidpush();Tpop();}

鏈棧為空的條件：

top=NULL

鏈棧為滿的條件(無法繼續(xù)申請新結(jié)點(diǎn)):

t=NULL

t為申請的結(jié)點(diǎn),為NULL表示失敗。2.鏈棧示意圖a1a2a3^棧底top棧頂…...ai3.鏈棧進(jìn)棧操作操作步驟:step1：申請一個鏈棧結(jié)點(diǎn)，若t=NULL，則表示鏈滿；否則，執(zhí)行step2；step2：在top所指結(jié)點(diǎn)之前插入新結(jié)點(diǎn)，并將top指向新申請的結(jié)點(diǎn)t。template<classT>

voidlinked_Stack<T>::

push(Tx){node<T>*p=newnode<T>;p->data=x;p->next=top;top=p;}鏈棧進(jìn)棧算法4.鏈棧出棧操作操作步驟:step1若鏈棧為空，則輸出棧溢出信息；否則，執(zhí)行step2。step2(保存top)并使top指向被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)，刪除top所指結(jié)點(diǎn)。step3釋放被刪除結(jié)點(diǎn)的存儲空間。返回出棧元素值。template<classT>

Tlinked_Stack<T>::

pop(Tx){Ty;node<T>*q;if(top==NULL){cout<<“空?！?lt;<endl；

return0;}q=top;y=q->d;top=q->next;deleteq;returny;}六、棧的應(yīng)用1.例1：表達(dá)式計算計算表達(dá)式，首先要正確地定義運(yùn)算規(guī)則：為了讓計算機(jī)能識別表達(dá)式，規(guī)定：表達(dá)式由操作數(shù)（Operand）和操作符（Operator）和定界符（Delimiter）組成。例如，#3*（7-2）#；實際處理表達(dá)式是用兩個棧結(jié)構(gòu)OPTR（運(yùn)算符）和OPND（操作數(shù)）加運(yùn)算規(guī)則組成；四則運(yùn)算先乘除、后加減從左到右先括號內(nèi)，再括號外2.計算表達(dá)式算法步驟Step1初始化，清空OPTR和OPND，將左定界符壓OPTR棧；Step2循環(huán)輸入表達(dá)式中的每個字符若輸入操作數(shù)，則進(jìn)OPND棧若是算符，則和OPTR棧頂元素進(jìn)行比較，按規(guī)則進(jìn)行相應(yīng)操作操作服從優(yōu)先關(guān)系表Q1<Q2Q2入OPTR棧，再讀入下一個元素Q1=Q2Q1出OPTR棧，脫括號，再讀一個元素Q1>Q2Q1出OPTR棧，從OPND中取兩個數(shù)運(yùn)算Step3直到出現(xiàn)右定界符為止。舉例，計算：3*（7-2）輸入：#3*（7-2）#1#3PUSH（OPND，3）

2#3*PUSH（OPTR，‘*’）

3#*3（PUSH（OPTR，‘（’）

4#*（37PUSH（OPND，7）

5#*（37-PUSH（OPTR，‘-’）

6#*（-372PUSH（OPND，2）

7#*（-372）Operate（7，‘-’，2）

8#*（

35

POP（OPTR，‘（’）

9#*

35#Operate（3，‘*’，5）10#15

RETURN（GETTOP（OPND））步驟OPTR棧OPND棧輸入字符主要操作例2（遞歸過程實現(xiàn)）（2）遞歸過程的實現(xiàn)計算5的階乘（5！=5×4×3×2×1）

intf(n){if(n==1)return(1);elsereturn(n*f(n-1));}f(1)f(2)f(3)f(4)f(5)top1