0-軟件技術(shù)基礎(chǔ)-數(shù)據(jù)結(jié)構(gòu)(L1-3)-sxdai

1數(shù)據(jù)結(jié)構(gòu)成都理工高校工程技術(shù)學(xué)院計科系代世雄2010年３月８日數(shù)據(jù)結(jié)構(gòu)與算法的基本概念的基本概念什么是數(shù)據(jù)？

數(shù)據(jù)就是是信息的載體,它可以用計算機(jī)表示并加工?？梢钥闯?，數(shù)據(jù)這個概念本身是隨著計算機(jī)的發(fā)展而不斷擴(kuò)展的概念。在計算機(jī)發(fā)展的初期，由于計算機(jī)主要用于數(shù)值計算，數(shù)據(jù)指的就是數(shù)值。計算機(jī)硬件和軟件技術(shù)的不斷發(fā)展，擴(kuò)大了計算機(jī)的應(yīng)用領(lǐng)域，諸如字符、文字、表格、圖形、圖像、聲音等也屬于數(shù)據(jù)的范疇2數(shù)據(jù)結(jié)構(gòu)與算法的基本概念的基本概念什么是數(shù)據(jù)元素？數(shù)據(jù)元素是數(shù)據(jù)集合中的一個個體，它是數(shù)據(jù)的基本單位。例如：全部學(xué)生的學(xué)籍登記卡組成學(xué)生的學(xué)籍?dāng)?shù)據(jù)，每個學(xué)生的學(xué)籍登記卡就是學(xué)籍?dāng)?shù)據(jù)的一個數(shù)據(jù)元素。數(shù)據(jù)元素可以是一個數(shù)或字符串，也可以由若干數(shù)據(jù)項組成(數(shù)據(jù)的最小單位)。在這種狀況下，通常把數(shù)據(jù)元素稱為記錄。34表2-1學(xué)生學(xué)籍登記表學(xué)號姓名性別民族籍貫專業(yè)1王安男漢北京計算機(jī)通信2李華男回河北軟件3張莉女漢山西計算機(jī)應(yīng)用4張平女漢廣東軟件數(shù)據(jù)結(jié)構(gòu)與算法的基本概念的基本概念什么是數(shù)據(jù)結(jié)構(gòu)？（１）數(shù)據(jù)結(jié)構(gòu)就是探討數(shù)據(jù)及數(shù)據(jù)元素之間關(guān)系的一門學(xué)科。（２）數(shù)據(jù)結(jié)構(gòu)的基本單位是數(shù)據(jù)元素，它可以是基本類型，也可以是結(jié)構(gòu)類型。數(shù)據(jù)結(jié)構(gòu)的三個方面：數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的操作集合。561.數(shù)據(jù)的邏輯結(jié)構(gòu)2.數(shù)據(jù)的存儲結(jié)構(gòu)3.數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。A.線性結(jié)構(gòu)B.非線性結(jié)構(gòu)A.依次存儲B.鏈?zhǔn)酱鎯€性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面反映數(shù)據(jù)元素之間的邏輯關(guān)系數(shù)據(jù)元素在計算機(jī)內(nèi)部的組織方式C.散列結(jié)構(gòu)（散列表）D.索引結(jié)構(gòu)（索引表）數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)就是它是描述數(shù)據(jù)間的依次（邏輯）關(guān)系，只是抽象地反映數(shù)據(jù)元素的結(jié)構(gòu)，而不管它們在計算機(jī)中如何存放。一般用下列二元組來描述：DS=（D，R）其中：D：是數(shù)據(jù)元素的有限集合；R：是數(shù)據(jù)元素之間關(guān)系的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)在計算機(jī)中的存放的物理位置無關(guān)7數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)又稱物理結(jié)構(gòu)，是指數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示(又稱映象)，即數(shù)據(jù)在計算機(jī)中的存放。常用的存儲結(jié)構(gòu)包括依次結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系１、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系（某種依次）上視察數(shù)據(jù)，它是獨立于計算機(jī)的；可以在理論上、形式上進(jì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)。8數(shù)據(jù)的操作集合數(shù)據(jù)的操作集合：是指對存放在物理結(jié)構(gòu)上的數(shù)據(jù)，按定義的邏輯結(jié)構(gòu)進(jìn)行的各種操作。常見操作有：輸入、檢索、插入、刪除、修改、排序等。9數(shù)據(jù)結(jié)構(gòu)與算法算法：為解決一個問題而實行的方法和步驟，就稱為算法。算法的基本特性：１、有窮性：一個算法必需總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。２、確定性：每一步的依次與內(nèi)容必需是唯一確定的。３、可行性：可以通過基本運算執(zhí)行有限次來實現(xiàn)。４、數(shù)據(jù)輸入：可以有０個或多個輸入５、數(shù)據(jù)輸出：必需至少有１個輸出10算法和程序的區(qū)分算法是解決問題的一種方法或過程，考慮的是如何將輸入轉(zhuǎn)換為輸出。一個問題可以有多種算法。程序是某種程序設(shè)計語言對算法的具體實現(xiàn)。算法和程序的主要區(qū)分在于：有窮性，正確性，和描述方法。１、程序可以是無窮的，如OS，算法是有窮的。２、程序可以是錯誤的，算法必需是正確的。３、程序是用程序設(shè)計語言描述，可在計算機(jī)上執(zhí)行；算法還可以用框圖、自然語言等形式來描述。11算法優(yōu)劣的評價標(biāo)準(zhǔn)評價算法優(yōu)劣的標(biāo)準(zhǔn)：時間困難度和空間困難度頻度：是指該語句重復(fù)執(zhí)行的次數(shù)。算法的時間困難度：指在計算機(jī)上運行該算法所花費的時間。用“O（數(shù)量級）”來表示，稱為“階”。常見的時間困難度有：O(1)O(logn)O(n)O(n2)空間困難度：指算法在計算機(jī)上運行所占用的存儲空間。度量同時間困難度。時間與空間是一對沖突，要節(jié)約空間往往要消耗較多的時間，反之亦然。目前，內(nèi)存空間足夠，應(yīng)重點考慮時間。12數(shù)據(jù)結(jié)構(gòu)與算法－課堂練習(xí)131.數(shù)據(jù)在計算機(jī)內(nèi)存中的表示是指數(shù)據(jù)的存儲結(jié)構(gòu)。 (Ｙ/N)3.以下（14）不是數(shù)據(jù)結(jié)構(gòu)探討的主要問題。(A)數(shù)據(jù)元素之間的邏輯關(guān)系 (B)數(shù)據(jù)元素之間的存儲結(jié)構(gòu)(C)軟件開發(fā)方法 (D)實現(xiàn)操作的算法4.數(shù)據(jù)的基本單位是數(shù)據(jù)元素。5.數(shù)據(jù)類型是具有共同屬性的一類變量的抽象。6.在數(shù)據(jù)結(jié)構(gòu)中，一個存儲結(jié)點存放一個（）。(A)數(shù)據(jù)項(B)數(shù)據(jù)元素(C)數(shù)據(jù)結(jié)構(gòu)(D)數(shù)據(jù)類型7.數(shù)據(jù)類型是某種程序設(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。8.數(shù)據(jù)在計算機(jī)內(nèi)在中的表示是指數(shù)據(jù)的存儲結(jié)構(gòu)。9.以下特征中哪個不是算法的特征 ()。(A)可行性 (B)確定性(C)有窮性(D)唯一性10.算法指的是（15）。（A）計算機(jī)程序（B）解決問題的有限運算序列（C）排序算法（D）解決問題的計算方法11.數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位。線性結(jié)構(gòu)線性結(jié)構(gòu)：是最常用的數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)的基本特點：數(shù)據(jù)元素是有序且有限的。線性結(jié)構(gòu)的邏輯特征：在線性結(jié)構(gòu)中１、有且僅有一個無干脆前趨而僅有一個干脆后繼的起始元素２、有且僅有一個無干脆后繼而僅有一個干脆前趨的終點元素３、其余元素均為內(nèi)部元素常用的線性結(jié)構(gòu)包括：線性表、堆棧、隊列、數(shù)組、串。14線性表線性表是由ｎ個(n>=0)相同類型元素構(gòu)成的集合。15線性表的邏輯結(jié)構(gòu)線性表是由n個數(shù)據(jù)元素組成的有限序列。記作：L=(a1，a2，…an)數(shù)據(jù)元素之間的關(guān)系ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1ai-1是ai的干脆前驅(qū)元素，ai＋1是ai的干脆后繼元素除a1外，每個元素有且只有一個干脆前驅(qū)元素。除an外，每個元素有且只有一個干脆后繼元素。線性表中數(shù)據(jù)元素的個數(shù)n(n>＝0)稱為表的長度。n=0時稱為空表16線性表的基本運算17Setnull（L）置空表Length（L）求表長度；求表中元素個數(shù)Get（L，i）取表中第i個元素（1≤i≤n）Prior（L，i）取i的前趨元素Next（L，i）取i的后繼元素Locate（L，x）返回指定元素在表中的位置Insert（L，i，x）插入元素Delete（L，x）刪除元素Empty（L）判別表是否為空線性表的依次存儲結(jié)構(gòu)線性表的依次存儲結(jié)構(gòu)將表中元素一個接一個的存入一組連續(xù)的存儲單元中，這種存儲結(jié)構(gòu)是依次結(jié)構(gòu)。接受依次存儲結(jié)構(gòu)的線性表簡稱為“依次表”。依次表的存儲特點是：只要確定了起始位置，表中任一元素的地址都通過下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L1≤i≤n其中，L是元素占用存儲單元的長度。18線性表元素存儲示意圖19線性表依次存儲結(jié)構(gòu)的特點線性表依次存儲結(jié)構(gòu)的特點：(1)占用連續(xù)的內(nèi)存；(2)數(shù)據(jù)元素的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)保持一樣；(3)只要確定存儲依次表的起始位置，表中隨意元素可隨機(jī)存??；故該結(jié)構(gòu)亦稱隨機(jī)存儲結(jié)構(gòu)。線性表依次存儲結(jié)構(gòu)的缺點：(1)在插入或刪除操作時，需移動大量的元素；(2)在給長度變更較大的線性表支配空間時，必需按最大空間支配；使存儲空間不能得到充分利用；(3)表的容量難以擴(kuò)容。20依次存儲結(jié)構(gòu)的插入運算21依次存儲結(jié)構(gòu)的插入運算22當(dāng)在依次存儲結(jié)構(gòu)的線性表中某個位置上插入或刪除一個數(shù)據(jù)元素時，其時間主要耗費在移動元素上，而移動元素的個數(shù)取決于插入或刪除元素的位置。假設(shè)在第i個元素之前插入一個新元素的概率為1/(n+1)，即在表的任何位置(包括an之后)插入新元素的概率是相等的，則插入操作中元素的平均移動次數(shù)(事實上就是時間困難度)為： T=依次存儲結(jié)構(gòu)的特點小結(jié)依次存儲結(jié)構(gòu)的特點數(shù)據(jù)連續(xù)存放、隨機(jī)存取邏輯上相鄰，物理上也相鄰存儲結(jié)構(gòu)簡潔、易實現(xiàn)插入、刪除操作不便存儲密度大，空間利用率高結(jié)論：依次存儲結(jié)構(gòu)適合于表中元素變動較少的狀況。23線性鏈表(LinkedList)線性表的依次存儲結(jié)構(gòu)簡潔實現(xiàn)，可以隨機(jī)存取表中的隨意元素。依次表缺點是：–難于插入、刪除操作；–須要預(yù)先支配空間，不管這些空間能否最大限度地利用。鏈表存儲結(jié)構(gòu)在這兩個方面恰好是優(yōu)點：–簡潔插入、刪除操作–不須要預(yù)分空間。24線性鏈表(LinkedList)鏈表：是指用一組隨意的存儲單元來依次存放線性表的結(jié)點，這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的隨意位置上的。結(jié)點：數(shù)據(jù)元素ai的存儲映象，它包括兩個域：數(shù)據(jù)域：存儲每個結(jié)點值；指針域：存儲指示其后繼結(jié)點的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)：25線性鏈表(LinkedList)結(jié)點（NODE）表中元素的存儲單元。鏈表存儲結(jié)構(gòu)形式為：數(shù)據(jù)域指針域鏈表結(jié)構(gòu)的C語言描述為：structnode{intdata;structnode*next;};typedefstructnodeNODE；26線性鏈表(LinkedList)基本概念鏈表（Link）:由結(jié)點組成的表。頭指針（head）:指向鏈表中第1個結(jié)點的指針。頭結(jié)點:為便利操作，在頭指針和首元結(jié)點之間設(shè)置的結(jié)點。首元結(jié)點:第一個結(jié)點（a1）。27線性鏈表(LinkedList)可以認(rèn)為利用小的零散空間“串”起來，表示線性表，即把線性表的元素分散插入到系統(tǒng)所限制的零散空間中，然后用“指針”串起來，組成一個有序的線性表，用指針表示數(shù)據(jù)元素的邏輯關(guān)系。元素的存儲，可以是連續(xù)的，也可以不是連續(xù)的。結(jié)點至少包括數(shù)據(jù)元素和指針兩個區(qū)域。28a[0]a[2]a[3]a[1]300020001000單鏈表結(jié)構(gòu)圖示單鏈表的頭指針為H：29160H160110a5200…

…150a2190160a1150…

…190a3210200a6260210a4110…

….240a8NULL

…

...

260a7240線性鏈表可以看出，用線性鏈表表示線性表時，數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點中的指針指示的，邏輯上相鄰的兩個數(shù)據(jù)元素其存儲的物理位置不要求相鄰，因此，這種存儲結(jié)構(gòu)為非依次映像或鏈?zhǔn)接诚?。在運用中，我們只關(guān)切數(shù)據(jù)元素的邏輯次序而不必關(guān)切它的真正存儲地址。通常，我們在單鏈表第一個元素所在的結(jié)點之前附設(shè)一個結(jié)點——頭結(jié)點（增加的目的是統(tǒng)一空表與非空表的處理）。頭結(jié)點的指針域存儲第一個元素所在結(jié)點的存儲位置；頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，也可以存儲如線性表的長度等附加信息。若線性表為空表，則頭結(jié)點的指針域為“空”。30帶頭結(jié)點的單鏈表通常狀況下，為了運算的統(tǒng)一，常在第一個結(jié)點前附設(shè)一個結(jié)點，稱為“頭結(jié)點”，頭指針具有標(biāo)識作用，因而，常用作鏈表的名字31LNode*p;p=（LNode*）malloc(sizeof(LNode))；則完成了申請一塊LNode類型的存儲單元的操作，并將其地址賦值給指針變量p?！腍空表a1a2an∧H

非空表…Pp->datap->next帶頭結(jié)點單鏈表的插入操作32線性鏈表操作：插入元素3333p指向當(dāng)前結(jié)點，pre表示前一個結(jié)點(的指針)。在*p前(*pre后)插入元素s的語句序列：

s->next=pre->next; pre->next=s;aknextai-1nextainextpre帶頭結(jié)點單鏈表的刪除操作34圖2-8帶頭結(jié)點的單鏈表圖2-9在單鏈表中刪除一個結(jié)點線性鏈表操作：刪除元素35ai-1nextainextai+1next*p表示當(dāng)前結(jié)點,*pre表示*p的前驅(qū)結(jié)點刪除*p結(jié)點的語句序列為：

pre->next=p->next;free(p); 循環(huán)鏈表假如鏈表最終一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)，這樣的鏈表稱為循環(huán)鏈表。這樣，從表中任一結(jié)點動身均可找到表中其它結(jié)點，其邏輯狀態(tài)圖如圖2-1036圖2-10循環(huán)單鏈表循環(huán)鏈表循環(huán)鏈表一般設(shè)表頭結(jié)點，這樣鏈表將永不為空，這將使空表和非空表的邏輯狀態(tài)及運算統(tǒng)一起來。循環(huán)鏈表的操作和線性鏈表基本一樣，差別僅在于算法中的循環(huán)條件不是p或p->next是否為空，而是它們是否等于頭指針。與單鏈表比較，循環(huán)鏈表有以下特點：(1)在循環(huán)單鏈表中，從表中任何一個結(jié)點動身都能訪問到其它全部的結(jié)點；而單鏈表一般把頭指針作為入口點，從某一結(jié)點動身，只能訪問到其全部后繼結(jié)點。(2)循環(huán)單鏈表的空表判定條件是：head->next=head。37雙向鏈表前面探討的鏈?zhǔn)酱鎯Y(jié)構(gòu)中只有一個指示干脆后繼的指針域，所以從某結(jié)點動身只能順指針往后查找其它結(jié)點。若要查找結(jié)點的干脆前趨，則應(yīng)從頭指針動身(或在循環(huán)單鏈表中從p結(jié)點動身)始終往后找，直到結(jié)點q滿足q->next=p，那么q是p的前趨結(jié)點。為克服鏈表這種單向性的缺點，為有更大的靈敏性來操作線性鏈表，可接受雙向鏈表存儲結(jié)構(gòu)。38雙向鏈表在每個結(jié)點上增加另一個指向線性表中每個元素的前趨結(jié)點的指針域prior，就得到雙向鏈表。其結(jié)點的結(jié)構(gòu)如下圖所示。其中，prior是指向前趨結(jié)點的指針域；data是數(shù)據(jù)域；next是指向后繼結(jié)點的指針域。39雙向鏈表結(jié)點結(jié)構(gòu)雙向鏈表將雙向鏈表的頭結(jié)點和尾結(jié)點鏈接起來組成雙向循環(huán)鏈表。雙向鏈表的幾種不同狀態(tài)如圖2-12，圖2-13，圖2-14和圖2-15所示。40圖2-12帶頭結(jié)點的空雙向鏈表圖2-13帶頭結(jié)點的非空雙向鏈表雙向循環(huán)鏈表41圖2-14空的雙向循環(huán)鏈表

圖2-15非空雙向循環(huán)鏈表雙向鏈表在非空雙向循環(huán)鏈表中，設(shè)p是指向鏈表中任一結(jié)點的指針，則有：p->next->prior=p->prior->next=p這個等式反映了這種鏈表的本質(zhì)，在此鏈表上進(jìn)行插入或刪除操作是特殊便利的。雙向鏈表雖然多花了存儲空間，但卻換得了操作上的更大靈敏性。雙向鏈表的運算如LENGTH(Head)，GET(Head,i)，LOCATE(Head,x)等操作，僅涉及一個方向的指針，操作類似單鏈表。但插入INSERT、刪除DELETE時要同時修改兩個方向的指針。42雙向鏈表的插入操作43圖2-16在雙向鏈表中插入結(jié)點插入時相關(guān)操作序列為：①s->prior=p->prior;②(p->prior)->next=s;③s->next=p;④p->prior=s。雙向鏈表的刪除操作44圖2-17在雙向鏈表中刪除結(jié)點刪除時相關(guān)操作序列為：①(p->prior)->next=p->next;②(p->next)->prior=p->prior;

線性表－課堂練習(xí)451.數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)，是獨立于計算機(jī)的。(Ｙ/N)2.在線性表中，數(shù)據(jù)的存儲方式有依次和鏈接兩種。3.線性鏈表的地址()。(A)必需連續(xù) (B)部分地址必需連續(xù)(C)確定不連續(xù) (D)連續(xù)與否均可以4.線性表接受鏈?zhǔn)酱鎯r，結(jié)點的存儲地址必需是連續(xù)的5.依次表和線性鏈表的物理存貯形式都是依次存貯6.數(shù)組也是一種數(shù)據(jù)結(jié)構(gòu)，一維數(shù)組就是一種依次表結(jié)構(gòu)。7.線性表不具有的特點是（11）。(A)隨機(jī)訪問 (B)無須事先估計所需存儲空間大小(C)插入時不必移動元素(D)所需空間與純屬表長度成正比8.數(shù)據(jù)在計算機(jī)內(nèi)存中的表示是指數(shù)據(jù)的存儲結(jié)構(gòu)。9.鏈表可以隨機(jī)訪問隨意一個結(jié)點，而依次表則不能。線性表－課堂練習(xí)46下述哪一條是依次存儲結(jié)構(gòu)的優(yōu)點？（）A．插入運算便利B．可便利地用于各種邏輯結(jié)構(gòu)的存儲表示C．存儲密度大D．刪除運算便利下面關(guān)于線性表的敘述中，錯誤的是哪一個？（）A．線性表接受依次存儲，必需占用一片連續(xù)的存儲單元B．線性表接受依次存儲，便于進(jìn)行插入和刪除操作C．線性表接受鏈接存儲，不必占用一片連續(xù)的存儲單元D．線性表接受鏈接存儲，便于插入和刪除操作。若某線性表最常用的操作是存取任一指定序號的元素和在最終進(jìn)行插入和刪除運算，則利用（）存儲方式最節(jié)約時間。A．依次表B．雙鏈表C．帶頭結(jié)點的雙循環(huán)鏈表D．單循環(huán)鏈表線性表－課堂練習(xí)47鏈表不具有的特點是（）A．插入、刪除不須要移動元素B．可隨機(jī)訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比棧和隊列棧(stack)和隊列(queue)是常常遇到的兩種數(shù)據(jù)結(jié)構(gòu)，它們都是特殊狀況下的線性表。前面介紹的線性表的向量及鏈表存儲，進(jìn)行插入、刪除時是比較麻煩的。向量導(dǎo)致數(shù)據(jù)元素的大量移動，而鏈表中則要順鏈找尋指定位置。假如能夠把插入、刪除操作都限制在線性表的端部進(jìn)行，則運算效率可以大大提高。本節(jié)要探討的就是這種限制存取位置的線性表——棧和隊列。48棧棧（也稱堆棧）1．棧的定義棧（stack）是限定只能在表的同一端進(jìn)行插入和刪除操作的線性表。其中允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，而表中固定的一端稱為棧底(bottom)。棧中元素個數(shù)為零時稱為空棧。由于棧中元素的插入和刪除只能在棧頂進(jìn)行，所以總是后進(jìn)棧的元素先出來，即棧具有后進(jìn)先出(LastInFirstOut，縮寫為LIFO)的特性，故棧又稱為“后進(jìn)先出表”(LIFO表)。49棧在日常生活中，有不少類似棧的例子。例如食堂中盤子的疊放，假如限定一次疊放一只，那么每次都是疊放到原來一疊盤子的頂上，這相當(dāng)于入棧操作；而當(dāng)取用一只盤子時，也是從這一疊盤子的頂上取用，這相當(dāng)于出棧操作。50棧棧的五種基本運算：(1)Inistack(S)。初始化棧S為空棧。(2)Empty(S)。判定S是否為空棧。若S是空棧則返回值為真(Ture)，否則返回值為假(False)。(3)Push(S，x)。進(jìn)棧操作。在棧S的棧頂插入數(shù)據(jù)元素x。(4)Pop(S)。出棧操作。若棧S不是空棧，則刪除棧頂元素。(5)Gettop(S)。取棧頂元素。它只讀取棧頂元素，不變更棧中的內(nèi)容。51棧52例2-9

有三個元素的進(jìn)棧序列是1，2，3，舉出此三個元素可能的出棧序列，并寫出相應(yīng)的進(jìn)棧和出棧操作序列如圖2-18所示(假設(shè)以I和O表示進(jìn)棧和出棧操作)。圖2-18三個元素可能的出棧序列棧的表示和實現(xiàn)因為棧是線性表的一種特例，所以線性表的存儲結(jié)構(gòu)對它都適用。一般稱接受依次存儲結(jié)構(gòu)的棧為依次棧；接受鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧為鏈棧。1)棧的依次存儲結(jié)構(gòu)——依次棧利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時設(shè)指針top指示棧頂元素的當(dāng)前位置?？諚５臈ｍ斨羔樦禐?1。設(shè)用數(shù)組Stack[MAXSIZE]表示棧，則對非空棧，Stack[0]為最早進(jìn)入棧的元素，Stack[top]為最遲進(jìn)入棧的元素，即棧頂元素。當(dāng)top=MAXSIZE-1時意為棧滿，此時若有元素入棧則將產(chǎn)生“數(shù)組越界”的錯誤，稱為棧的“上溢”(overflow)；反之，top=-1意為棧空，若此時再作退棧操作，則發(fā)生“下溢”(underflow)。圖2-19展示了依次棧中數(shù)據(jù)元素和棧頂指針之間的對應(yīng)關(guān)系，設(shè)MAXSIZE=m。53棧的表示和實現(xiàn)54圖2-19棧頂指針和棧中元素之間的關(guān)系

55棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)—鏈棧棧的運用特殊廣泛，常常會出現(xiàn)在一個程序中須要同時運用多個棧的情形，為了不因棧上溢而產(chǎn)生錯誤中斷，必需給每個棧預(yù)分一個較大的空間，但這并不簡潔做到，因為各個棧實際所用空間很難估計?？紤]到在實際進(jìn)程中，當(dāng)一個棧發(fā)生上溢時，其它?？赡苓€留有很多空間，所以可設(shè)法動態(tài)地加以調(diào)整，以達(dá)到多個棧共享內(nèi)存時，只要有一個棧未滿，其它任何棧的入棧操作均不會發(fā)生上溢。2)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)——鏈棧接受依次存儲結(jié)構(gòu)，對于一個棧、兩個?？梢郧逦匀坏乇磉_(dá)，但當(dāng)遇到多個棧共享空間的問題或棧的最大容量事先不能估計時，接受鏈?zhǔn)酱鎯Y(jié)構(gòu)是有效的方法。56鏈棧存儲結(jié)構(gòu)的C語言描述structsnode{intdata;structsnode*link;};typedefstructsnodeSNODE;SNODE*top；鏈棧為空的條件：top=NULL鏈棧為滿的條件：t=NULLt為申請的結(jié)點，為NULL表示失敗。57棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)58圖2-21鏈棧示意圖棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，它是運算是受限的單鏈表。棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)對于鏈棧，不會產(chǎn)生單個棧滿而其余?？盏那樾?，只有當(dāng)整個可用空間都被占滿，malloc函數(shù)無法實現(xiàn)時才會發(fā)生上溢。因此多個鏈棧共享空間也就是