數(shù)據(jù)結(jié)構(gòu)與算法教案

數(shù)據(jù)結(jié)構(gòu)與算法第一章緒論1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇NiklausWirthAlgorithm+DataStructures=Programs程序設(shè)計(jì):為計(jì)算機(jī)處理問(wèn)題編制一組指令集算法:處理問(wèn)題的策略數(shù)據(jù)結(jié)構(gòu):問(wèn)題的數(shù)學(xué)模型例如:數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題結(jié)構(gòu)靜力分析計(jì)算─━線性代數(shù)方程組全球天氣預(yù)報(bào)─━環(huán)流模式方程非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題例一:求一組(n個(gè))整數(shù)中的最大值算法:基本操作是“比較兩個(gè)數(shù)的大小”模型：？例二：計(jì)算機(jī)對(duì)弈算法：對(duì)弈的規(guī)則和策略模型：？例三：足協(xié)的數(shù)據(jù)庫(kù)管理算法：需要管理的項(xiàng)目？如何管理？用戶界面？模型：？概括地說(shuō)，數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn)1.2基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù):所有能被輸入到計(jì)算機(jī)中，且被計(jì)算機(jī)處理的符號(hào)的集合計(jì)算機(jī)操作的對(duì)象的總稱是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式數(shù)據(jù)元素:數(shù)據(jù)中的一個(gè)“個(gè)體”，數(shù)據(jù)結(jié)構(gòu)中討論的基本單位數(shù)據(jù)項(xiàng)：?/b>數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合例如：運(yùn)動(dòng)員（數(shù)據(jù)元素）姓名俱樂(lè)部名稱出生日期參加日期職務(wù)業(yè)績(jī)其中出生日期年月日是組合項(xiàng)數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合例如,一個(gè)含12位數(shù)的十進(jìn)制數(shù)可以用三個(gè)4位的十進(jìn)制數(shù)表示3214,6587,9345─a1(3214),a2(6587),a3(9345)在a1、a2和a3之間存在“次序”關(guān)系<a1,a2>、<a2,a3>3214，6587，9345≠6587，3214，9345a1a2a3a2a1a3又例，2行3列的二維數(shù)組{a1,a2,a3,a4,a5,a6}a1a2a3a4a5a6行的次序關(guān)系:row={,,,}

列的次序關(guān)系:col={,,}

再例，一維數(shù)組{a1,a2,a3,a4,a5,a6}中存在次序關(guān)系:{i,ai+1>|i=1,2,3,4,5}數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。嚴(yán)格地講，以上定義僅是數(shù)據(jù)的邏輯結(jié)構(gòu)的定義數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)─━邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2關(guān)系的映象方法：（表示<x,y>的方法）順序映象以存儲(chǔ)位置的相鄰表示后繼關(guān)系y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C而C是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法，當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語(yǔ)言中提供的數(shù)據(jù)類型描述之。例如:以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用C語(yǔ)言中提供的整數(shù)數(shù)組類型，定義長(zhǎng)整數(shù)為:typedefintLong_int[3]二、數(shù)據(jù)類型在用高級(jí)程序語(yǔ)言編寫(xiě)的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說(shuō)明它們所屬的數(shù)據(jù)類型。因?yàn)轭愋兔黠@或隱含地規(guī)定了，在程序執(zhí)行期間，變量或表達(dá)式所有可能取值的范圍，以及在這些之上允許進(jìn)行的操作。數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作的總稱。三、抽象數(shù)據(jù)類型(AbstractDataType簡(jiǎn)稱ADT)是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作ADT有兩個(gè)重要特征:數(shù)據(jù)抽象用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）數(shù)據(jù)封裝將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)例如抽象數(shù)據(jù)類型復(fù)數(shù)的定義：ADTComplex{數(shù)據(jù)對(duì)象：D＝{e1,e2｜e1,e2∈RealSet}數(shù)據(jù)關(guān)系：R1＝{|e1是復(fù)數(shù)的實(shí)數(shù)部分,|e2是復(fù)數(shù)的虛數(shù)部分}基本操作：InitComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex假設(shè):z1和z2是上述定義的復(fù)數(shù)，則Add(z1,z2,z3)操作的結(jié)果將得到z3=z1+z2抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉基本操作：〈基本操作的定義〉}ADT抽象數(shù)據(jù)類型名其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為基本操作名（參數(shù)表）初始條件：〈初始條件描述〉操作結(jié)果：〈操作結(jié)果描述〉基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果?！俺跏紬l件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?！安僮鹘Y(jié)果”說(shuō)明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過(guò)固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來(lái)實(shí)現(xiàn)1.3算法和算法衡量一、算法算法是為了解決某類問(wèn)題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：1．有窮性對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成；2．確定性對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；3．可行性算法中的所有操作都必須足夠基本，都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；4．有輸入作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上可以沒(méi)有輸入，實(shí)際上已被嵌入算法之中；5．有輸出它是一組與“輸入”與確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。二、算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1．正確性首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說(shuō)明”方式給出的需求。其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a．程序中不含語(yǔ)法錯(cuò)誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；c．程序?qū)τ诰倪x擇的、典型、苛刻切帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；通常以第c層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。2.可讀性算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行。因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試；3．健壯性當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4．高效率與低存儲(chǔ)量需求通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間。兩者都與問(wèn)題的規(guī)模有關(guān)。三、算法效率的衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法:事后統(tǒng)計(jì)法缺點(diǎn)：1。必須執(zhí)行程序2．其它因素掩蓋算法本質(zhì)事前分析估算法和算法執(zhí)行時(shí)間相關(guān)的因素：1．算法選用的策略2．問(wèn)題的規(guī)模3．編寫(xiě)程序的語(yǔ)言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的速度一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問(wèn)題的規(guī)模（通常用整數(shù)量n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。假如，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時(shí)間復(fù)雜度如何估算算法的時(shí)間復(fù)雜度？算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間與原操作執(zhí)行次數(shù)之和成正比從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則例一for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];}基本操作:乘法操作時(shí)間復(fù)雜度:O(n3)例二voidselect_sort(inta[],intn){//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for(i=0;i<n-1;++i){j=i;for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;if(j!=i)a[j]←→a[i]}//select_sort基本操作:比較(數(shù)據(jù)元素)操作時(shí)間復(fù)雜度:O(n2)例三voidbubble_sort(inta[],intn){//將a中整數(shù)序列重新排列成自小至大//有序的整數(shù)序列。for(i=n-1,change=TRUE;i>1&&change;--i){change=FALSE;for(j=0;j<>if(a[j]>a[j+1]){a[j]←→a[j+1];change=TRUE}}}//bubble_sort基本操作:賦值操作時(shí)間復(fù)雜度:O(n2)四、算法的存儲(chǔ)空間需求算法的空間復(fù)雜度S(n)=O(g(n))表示隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。算法的存儲(chǔ)量包括:1．輸入數(shù)據(jù)所占空間;2．程序本身所占空間；3．輔助變量所占空間。若輸入數(shù)據(jù)所占空間只取決與問(wèn)題本身，和算法無(wú)關(guān)，則只需要分析除輸入和程序之外的額外空間。若所需額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱此算法為原地工作。若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。學(xué)習(xí)要點(diǎn)1.熟悉各名詞、術(shù)語(yǔ)的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系。分清哪些是邏輯結(jié)構(gòu)的性質(zhì)，哪些是存儲(chǔ)結(jié)構(gòu)的性質(zhì)。2.了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。3．理解算法五個(gè)要素的確切含義：①動(dòng)態(tài)有窮性（能執(zhí)行結(jié)束）；②確定性（對(duì)于相同的輸入執(zhí)行相同的路徑）；③有輸入；④有輸出；⑤可行性（用以描述算法的操作都是足夠基本的）。4．掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。

第二章線性表線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集線性結(jié)構(gòu)的基本特征:1．集合中必存在唯一的一個(gè)“第一元素”；2．集合中必存在唯一的一個(gè)“最后元素”；3．除最后元素在外，均有唯一的后繼；4．除第一元素之外，均有唯一的前驅(qū)。2.1線性表的類型定義抽象數(shù)據(jù)類型線性表的定義如下：ADTList{數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{稱n為線性表的表長(zhǎng);稱n=0時(shí)的線性表為空表。}數(shù)據(jù)關(guān)系：R1＝{i-1,ai>|ai-1,ai∈D,i=2,...,n}{設(shè)線性表為(a1，a2,...，ai，...，an),稱i為ai在線性表中的位序。}基本操作：{結(jié)構(gòu)初始化}InitList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L。{銷毀結(jié)構(gòu)}DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。{引用型操作}ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則FALSE。ListLength(L)初始條件：線性表L已存在。操作結(jié)果：返回L中元素個(gè)數(shù)。PriorElem(L,cur_e,&pre_e)初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的元素，但不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義。NextElem(L,cur_e,&next_e)初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的元素，但不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無(wú)定義。GetElem(L,cur_e,&next_e)初始條件：線性表L已存在，1≤i≤LengthList(L)操作結(jié)果：用e返回L中第i個(gè)元素的值。LocateElem(L,e,compare())初始條件：線性表L已存在，compare()是元素判定函數(shù)。操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的元素的位序。若這樣的元素不存在，則返回值為0。ListTraverse(L,visit())初始條件：線性表L已存在。操作結(jié)果：依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。{加工型操作}ClearList(&L)初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。PutElem(L,i,&e)初始條件：線性表L已存在，1≤i≤LengthList(L)操作結(jié)果：L中第i個(gè)元素賦值同e的值。ListInsert(&L,i,e)初始條件：線性表L已存在，1≤i≤LengthList(L)+1操作結(jié)果：在L的第i個(gè)元素之前插入新的元素e，L的長(zhǎng)度增1。ListDelete(&L,i,&e)初始條件：線性表L已存在且非空，1≤i≤LengthList(L)操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L的長(zhǎng)度減1。}ADTList利用上述定義的線性表可以完成其它更復(fù)雜的操作例2-1假設(shè)有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示（即：線性表中的數(shù)據(jù)元素即為集合中的成員），現(xiàn)要求一個(gè)新的集合A＝A∪B。上述問(wèn)題可演繹為，要求對(duì)線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。1．從線性表LB中依次取得每個(gè)數(shù)據(jù)元素;GetElem(LB,i)→e2．依值在線性表LA中進(jìn)行查訪;LocateElem(LA,e,equal())3．若不存在，則插入之。ListInsert(LA,n+1,e)voidunion(List&La,ListLb){//將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長(zhǎng)度f(wàn)or(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal())ListInsert(La,++La_len1,e);//La中不存在和e相同的數(shù)據(jù)元素，則插入之}}//union例2-2已知一個(gè)非純集合B，試構(gòu)造一個(gè)純集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。voidpurge(List&La,ListLb){//已知線性表Lb中的數(shù)據(jù)元素依值非遞減有序排列(Lb是有序表)，//構(gòu)造線性表La，使其只包含Lb中所有值不相同的數(shù)據(jù)元素InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長(zhǎng)度f(wàn)or(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給eif(!equal(en,e)){ListInsert(La,++La_len,e);en=e;}//La中不存在和e相同的數(shù)據(jù)元素，則插入之}}//purge例2-3歸并兩個(gè)“其數(shù)據(jù)元素按值非遞減有序排列的”線性表LA和LB，求得線性表LC也具有同樣特性設(shè)La=(a1,…,ai,…,an)Lb=(b1,…,bj,…,bm)Lc=(c1,…,ck,…,cm+n)則Ck=k=1,2,…,m+n1．分別從LA和LB中取得當(dāng)前元素ai和bj；2．若ai≤bj，則將ai插入到LC中，否則將bj插入到LC中。voidMergeList(ListLa,ListLb,List&Lc){//已知線性表La和Lb中的元素按值非遞減排列。//歸并La和Lb得到新的線性表Lc，//Lc的元素也按值非遞減排列。InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//merge_list2.2線性表類型的實(shí)現(xiàn)?順序映象用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素線性表的起始地址，稱作線性表的基地址以“存儲(chǔ)位置相鄰”表示有序?qū)-1，ai>即：所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置順序映像的C語(yǔ)言描述//-----線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)-----#defineLIST_INIT_SIZE80//線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10//線性表存儲(chǔ)空間的分配增量typedefstruct{ElemType*elem;//存儲(chǔ)空間基址intlength;//當(dāng)前長(zhǎng)度intlistsize;//當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為單位)}SqList;//俗稱順序表線性表的初始化在順序映像中的實(shí)現(xiàn)StatusInitList_Sq(SqList&L){//構(gòu)造一個(gè)空的線性表L。L.elem=(ElemType*)malloc(LISTINCREMENT*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存儲(chǔ)分配失敗L.length=0;//長(zhǎng)度為0L.listsize=LISTINCREMENT;//初始存儲(chǔ)容量returnOK;}//InitList_Sq線性表操作LocateElem(L,e,compare())的實(shí)現(xiàn)：intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在順序線性表L中查找第1個(gè)值與e滿足compare()的元素的位序。//若找到，則返回其在L中的位序，否則返回0。i=1;//i的初值為第1元素的位序p=L.elem;//p的初值為第1元素的存儲(chǔ)位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq此算法的時(shí)間復(fù)雜度為:O(ListLength(L))線性表操作ListInsert(&L,i,e)的實(shí)現(xiàn)：?jiǎn)枺翰迦朐貢r(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an)StatusListInsert_Sq(SqList&L,intpos,ElemTypee){//在順序線性表L的第pos個(gè)元素之前插入新的元素e，//pos的合法值為1≤pos≤Listlength_Sq(L)+1if(pos<1||pos>L.length+1)returnERROR;//插入位置不合法if(L.length>=L.listsize){//當(dāng)前存儲(chǔ)空間已滿，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存儲(chǔ)分配失敗L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存儲(chǔ)容量}q=&(L.elem[pos-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表長(zhǎng)增1returnOK;}//ListInsert_Sq此算法的時(shí)間復(fù)雜度為:O(ListLength(L))線性表操作ListDelete(&L,i,&e)的實(shí)現(xiàn)：?jiǎn)枺簞h除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?a1,…,ai-1,ai+1,…,an)StatusListDelete_Sq(SqList&L,intpos,ElemType&e){//在順序線性表L中刪除第pos個(gè)元素，并用e返回其值。//pos的合法值為1≤pos≤ListLength_Sq(L)if((pos<1)||(pos>L.length))returnERROR;//刪除位置不合法p=&(L.elem[pos-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)*(p-1)=*p;//被刪除元素之后的元素左移--L.length;//表長(zhǎng)減1returnOK;}//ListDelete_Sq此算法的時(shí)間復(fù)雜度為:O(ListLength(L))2.3線性表類型的實(shí)現(xiàn)?鏈?zhǔn)接诚笠?、單鏈表用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素以元素(數(shù)據(jù)元素的映象)+指針(指示后繼元素存儲(chǔ)位置的)=結(jié)點(diǎn)(表示數(shù)據(jù)元素)以“結(jié)點(diǎn)的序列”表示線性表??稱作鏈表以線性表中第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)地址作為線性表的地址，為線性表的頭指針二、結(jié)點(diǎn)和單鏈表的C語(yǔ)言描述typedefstructLNode{ElemTypedata;//數(shù)據(jù)域structLnode*next;//指針域}LNode,*LinkList;三、單鏈表操作的實(shí)現(xiàn)線性表的操作GetElem(L,i,&e)在鏈表中的實(shí)現(xiàn):基本操作為:使指針p始終指向線性表中第j個(gè)數(shù)據(jù)元素StatusGetElem_L(LinkListL,intpos,ElemType&e){//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)線性表中存在第pos個(gè)元素//存在時(shí)，則將第pos個(gè)數(shù)據(jù)元素的值賦給e并返回OK，否則返//回ERRORp=L->next;j=1;//初始化，p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&j{//順指針向后查找，直到p指向第pos個(gè)元素或p為空p=p->next;++j;}if(!p||j>pos)returnERROR;//第pos個(gè)元素不存在e=p->data;//取第pos個(gè)元素returnOK;}//GetElem_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))線性表的操作ListInsert(&L,i,e)在鏈表中的實(shí)現(xiàn):基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針有序?qū)-1,ai>改變?yōu)閕-1,e>和i>

StatusListInsert_L(LinkListL,intpos,ElemTypee){//在帶頭結(jié)點(diǎn)的單鏈表L中第pos個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素ep=L;j=0;while(p&&j<pos-1){p=p->next;++j;}//尋找第pos-1個(gè)結(jié)點(diǎn)if(!p||j>pos-1)returnERROR;//pos小于1或者大于表長(zhǎng)s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)s->data=e;s->next=p->next;//插入L中p->next=s;returnOK;}//LinstInsert_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))線性表的操作ListDelete(&L,i,&e)在鏈表中的實(shí)現(xiàn):

基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針有序?qū)-1,ai>和i,ai+1>改變?yōu)閕-1,ai+1>

StatusListDelete_L(LinkListL,intpos,ElemType&e){//在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第pos個(gè)元素，并由e返回其值p=L;j=0;while(p->next&&j<pos-1){//尋找第pos個(gè)結(jié)點(diǎn)，并令p指向其前趨p=p->next;++j;}if(!(p->next)||j>pos-1)returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)e=q->data;free(q);returnOK;}//ListDelete_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))voidCreateList_L(LinkList&L,intn){//逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)scanf(&p->data);//輸入元素值p->next=L->next;L->next=p;//插入到表頭}}//CreateList_L算法的時(shí)間復(fù)雜度為:O(Listlength(L))例2-1算法的時(shí)間復(fù)雜度控制結(jié)構(gòu)：for循環(huán)基本操作：LocateElem(La,e,equal())當(dāng)以順序映像實(shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:O(ListLength(La)×ListLength(Lb))當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:O(ListLength(La)×ListLength(Lb))例2-2算法的時(shí)間復(fù)雜度控制結(jié)構(gòu)：for循環(huán)基本操作：GetElem(Lb,i,e)當(dāng)以順序映像實(shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:O(ListLength(Lb))當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:O(ListLength2(Lb))例2-3算法的時(shí)間復(fù)雜度控制結(jié)構(gòu)：三個(gè)并列的while循環(huán)基本操作：ListInsert(Lc,++k,e)當(dāng)以順序映像實(shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:O(ListLength(La)+ListLength(Lb))當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:O((ListLength(La)+ListLength(Lb)2)用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問(wèn)題：1．單鏈表的表長(zhǎng)是一個(gè)隱含的值；2．在單鏈表的最后一個(gè)元素最后插入元素時(shí)，需遍歷整個(gè)鏈表；3．在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念強(qiáng)化。改進(jìn)鏈表的設(shè)置：1．增加“表長(zhǎng)”、“表尾指針”和“當(dāng)前位置的指針”三個(gè)數(shù)據(jù)域；2．將基本操作中的“位序i”改變?yōu)椤爸羔榩”四、一個(gè)帶頭結(jié)點(diǎn)的線性鏈表類型typedefstructLNode{//結(jié)點(diǎn)類型ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{//鏈表類型Linkhead,tail;//指向頭結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)intlen;//指示鏈表長(zhǎng)度Linkcurrent;//指向當(dāng)前訪問(wèn)的結(jié)點(diǎn)的指針，//初始位置指向頭結(jié)點(diǎn)}LinkList;StatusMakeNode(Link&p,ElemTypee);//分配由p指向的值為e的結(jié)點(diǎn)，并返回OK；//若分配失敗，則返回ERRORvoidFreeNode(Link&p);//釋放p所指結(jié)點(diǎn)鏈表的基本操作:{結(jié)構(gòu)初始化和銷毀結(jié)構(gòu)}StatusInitList(LinkList&L);//構(gòu)造一個(gè)空的線性鏈表L，//頭指針、尾指針和當(dāng)前指針均指向頭結(jié)點(diǎn)，表長(zhǎng)為零StatusDestroyList(LinkList&L);//銷毀線性鏈表L，L不再存在{引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//求表長(zhǎng)StatusPrior(LinkListL);//改變當(dāng)前指針指向其前驅(qū)StatusNext(LinkListL);//改變當(dāng)前指針指向其后繼ElemTypeGetCurElem(LinkListL);//返回當(dāng)前指針?biāo)笖?shù)據(jù)元素StatusLocatePos(LinkListL,inti);//改變當(dāng)前指針指向第i個(gè)結(jié)點(diǎn)StatusLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));//若存在與e滿足函數(shù)compare()判定關(guān)系的元素，則移動(dòng)當(dāng)前指針//指向第1個(gè)滿足條件的元素，并返回OK;否則返回ERRORStatusListTraverse(LinkListL,Status(*visit)());//依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit(){加工型操作}StatusClearList(LinkList&L);//重置為空表StatusSetCurElem(LinkList&L,ElemTypee);//更新當(dāng)前指針?biāo)笖?shù)據(jù)元素StatusAppend(LinkList&L,Links);//一串結(jié)點(diǎn)鏈接在最后一個(gè)結(jié)點(diǎn)之后StatusInsAfter(LinkList&L,ElemTypee);//將元素e插入在當(dāng)前指針之后StatusDelAfter(LinkList&L,ElemType&e);//刪除當(dāng)前指針之后的結(jié)點(diǎn){這里定義的大部分算法都將結(jié)點(diǎn)和指針的概念封裝在算法中}StatusInsAfter(LinkList&L,ElemTypee){//若當(dāng)前指針在鏈表中，則將數(shù)據(jù)元素e插入在線性鏈表L中//當(dāng)前指針?biāo)附Y(jié)點(diǎn)之后,并返回OK;否則返回ERROR。if(!L.current)returnERROR;if(!MakeNode(s,e))returnERROR;s->next=L.current->next;L.current->next=s;RreturnOK;}//InsAfterStatusDelAfter(LinkList&L,ElemType&e){//若當(dāng)前指針及其后繼在鏈表中，則刪除線性鏈表L中當(dāng)前//指針?biāo)附Y(jié)點(diǎn)之后的結(jié)點(diǎn)，并返回OK;否則返回ERROR。if(!(L.current&&L.current->next))returnERROR;q=L.current->next;L.current->next=q->next;e=q->data;FreeNode(q);returnOK;}//DelAfter{利用上述定義的線性鏈表可以完成線性表的其它操作}例一:StatusListInsert_L(LinkListL,inti,ElemTypee){//在帶頭結(jié)點(diǎn)的單鏈線性表L的第i個(gè)元素之前插入元素eif(!LocatePos(L,i-1))returnERROR;//i值不合法if(InsAfter(L,e))returnOK;//插入在第i-1個(gè)結(jié)點(diǎn)之后elsereturnERROR;}//ListInsert_L例二:voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lcint(*compare)(ElemType,ElemType))){//已知單鏈線性表La和Lb的元素按值非遞減排列，歸并//La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列if(!InitList(Lc))returnERROR;//存儲(chǔ)空間分配失敗LocatePos(La,0);LocatePos(Lb,0);//當(dāng)前指針指向頭結(jié)點(diǎn)if(DelAfter(La,e))a=e;elsea=MAXC;//MAXC為常量最大值if(DelFirst(Lb,e))b=e;elseb=MAXC;//a和b為兩表中當(dāng)前比較元素while(!(a=MAXC&&b=MAXC)){//La或Lb非空if((*compare)(a,b)<=0){//a≤bInsAfter(Lc,a);if(DelAfter(La,e1)a=e1;elsea=MAXC;}else{//a＞bInsAfter(Lc,s);if(DelAfter(Lb,e)b=e1;elseb=MAXC;}}DestroyList(La);DestroyList(Lb);//銷毀鏈表La和LbreturnOK;}//MergeList_L五、其它形式的鏈表1.雙向鏈表//-----線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)-----typedefstructDuLNode{ElemTypedata;//數(shù)據(jù)域structDuLNode*prior;//指向前驅(qū)的指針域structDuLNode*next;//指向后繼的指針域}DuLNode,*DuLinkList;2.循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表2.4一元多項(xiàng)式的表示一元多項(xiàng)式在計(jì)算機(jī)中，可以用一個(gè)線性表來(lái)表示:P=(p0,p1,…，pn)但是對(duì)于形如S(x)=1+3x10000–2x20000的多項(xiàng)式，上述表示也就不恰當(dāng)了。一般情況下的一元多項(xiàng)式可寫(xiě)成Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi是指數(shù)為ei的項(xiàng)的非零系數(shù)，0≤e1<e2<┄<em=n它可以用其數(shù)據(jù)元素為(系數(shù)項(xiàng)，指數(shù)項(xiàng))的線性表來(lái)表示（（p1,e1）,(p2,e2),┄,(pm,em)）例如：線性表（(7,3),(-2,12),(-8,999)）表示多項(xiàng)式P999(x)=7x3-2x12-8x999抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下：ADTPolynomial{數(shù)據(jù)對(duì)象：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0}{TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)}數(shù)據(jù)關(guān)系：R1＝{i-1,ai>|ai-1,ai∈D,且ai-1中的指數(shù)值＜ai中的指數(shù)值，i=2,...,n}基本操作：CreatPolyn(&P,m)操作結(jié)果：輸入m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式P。DestroyPolyn(&P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：銷毀一元多項(xiàng)式P。PrintPolyn(&P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：打印輸出一元多項(xiàng)式P。AddPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即：Pa=Pa＋Pb，并銷毀一元多項(xiàng)式Pb。SubtractPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相減運(yùn)算，即：Pa=Pa－Pb，并銷毀一元多項(xiàng)式Pb。MultiplyPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相乘運(yùn)算，即：Pa=Pa×Pb，并銷毀一元多項(xiàng)式Pb。PolynLength(P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：返回一元多項(xiàng)式P中的項(xiàng)數(shù)。}ADTPolynomial如此定義的多項(xiàng)式可以看成是一個(gè)有序表(對(duì)其數(shù)據(jù)元素中的指數(shù)項(xiàng)而言),則多項(xiàng)式定義中的各個(gè)操作均可利用有序表的操作來(lái)完成。學(xué)習(xí)要點(diǎn)1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性表簡(jiǎn)稱為鏈表。2.熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法，如一維數(shù)組中一個(gè)區(qū)域[i..j]的上、下界和長(zhǎng)度之間的變換公式(L=j-i+1,i=j-L+1,j=i+L-1)，鏈表中指針p和結(jié)點(diǎn)*p的對(duì)應(yīng)關(guān)系(結(jié)點(diǎn)*(p->next)是結(jié)點(diǎn)*p的后繼等)，鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的區(qū)別及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求。3.熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作：查找、插入和刪除的算法。4.熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表操作的基本方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。5.能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。第三章棧和隊(duì)列從數(shù)據(jù)結(jié)構(gòu)的角度看:它們和線性表相同從數(shù)據(jù)類型的角度看:它們和線性表不同線性表?xiàng)ｊ?duì)列Insert(L,i,x)(1<=i<=n+1)Insert(S,n+1,x)Insert(Q,n+1,x)Delete(L,i)(1<=i<=n)Delete(S,n)Delete(Q,1)3.1棧的類型定義ADTStack{數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{i-1,ai>|ai-1,ai∈D,i=2,...,n}約定an端為棧頂，a1端為棧底。基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：棧S被銷毀。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALE。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。GetTop(S,&e)初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。}ADTStack3.2棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題，其解決方法很多，其中一個(gè)簡(jiǎn)單算法基于下列原理：N=(Ndivd)×d+Nmodd(其中：div為整除運(yùn)算，mod為求余運(yùn)算）例如：（1348)10=(2504)8，其運(yùn)算過(guò)程如下：NNdiv8Nmod8134816841682102125202假設(shè)現(xiàn)要編制一個(gè)滿足下列要求的程序：對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。由于上述計(jì)算過(guò)程是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位，而打印輸出，一般來(lái)說(shuō)應(yīng)從高位到低位進(jìn)行，恰好和計(jì)算過(guò)程相反。因此，若將計(jì)算過(guò)程中得到的八進(jìn)制數(shù)的各位順序進(jìn)棧，則按出棧序列打印輸出的即為與輸入對(duì)應(yīng)的八進(jìn)制數(shù)。voidconversion(){//對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出//與其等值的八進(jìn)制數(shù)InitStack(S);//構(gòu)造空棧scanf("%d",N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}//conversion這是利用棧的后進(jìn)先出特性的最簡(jiǎn)單的例子。在這個(gè)例子中，棧操作的序列是直線式的，即先一味地入棧，然后一味地出棧。也許，有的讀者會(huì)提出疑問(wèn)：用數(shù)組直接實(shí)現(xiàn)不也很簡(jiǎn)單嗎？仔細(xì)分析上述算法不難看出，棧的引入簡(jiǎn)化了程序設(shè)計(jì)的問(wèn)題，劃分了不同的關(guān)注層次，使思考范圍縮小了。而用數(shù)組不僅掩蓋了問(wèn)題的本質(zhì)，還要分散精力去考慮數(shù)組下標(biāo)增減等細(xì)節(jié)問(wèn)題。例二、括號(hào)匹配的檢驗(yàn)假設(shè)表達(dá)式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或(()])均為不正確的格式。檢驗(yàn)括號(hào)是否匹配的方法可用"期待的急迫程度"這個(gè)概念來(lái)描述。例如考慮下列括號(hào)序列：[([][])]12345678分析可能出現(xiàn)的不匹配的情況:到來(lái)的右括弧非是所“期待”的;到來(lái)的是“不速之客”;直到結(jié)束，也沒(méi)有到來(lái)所“期待”的。statusmatching(string&exp){//檢驗(yàn)表達(dá)式中所含括弧是否正確嵌套，若是，則返回//OK，否則返回ERRORintstate=1;while(i<=length(exp)&&state){swithofexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case")":{if(NOTStackEmpty(S)&&GetTop(S)="("){Pop(S,e);i++;}else{state=0}break;}……}}if(state&&StackEmpty(S))returnOKelsereturnERROR;}例三、行編輯程序問(wèn)題一個(gè)簡(jiǎn)單的行編輯程序的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。每接受一個(gè)字符即存入用戶數(shù)據(jù)區(qū)”不恰當(dāng)。較好的做法是，設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。例如，可用一個(gè)退格符“#”表示前一個(gè)字符無(wú)效；可用一個(gè)退行符“@”，表示當(dāng)前行中的字符均無(wú)效。例如，假設(shè)從終端接受了這樣兩行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);則實(shí)際有效的是下列兩行：while(*s)putchar(*s++);voidLineEdit(){//利用字符棧S，從終端接收一行并傳送至調(diào)用過(guò)程//的數(shù)據(jù)區(qū)。InitStack(S);//構(gòu)造空棧Sch=getchar();//從終端接收第一個(gè)字符while(ch!=EOF){//EOF為全文結(jié)束符while(ch!=EOF&&ch!=‘\n‘){switch(ch){case‘#‘:Pop(S,c);break;//僅當(dāng)棧非空時(shí)退棧case‘@‘:ClearStack(S);break;//重置S為空棧default:Push(S,ch);break;//有效字符進(jìn)棧，未考慮棧滿情形}ch=getchar();//從終端接收下一個(gè)字符}將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)；ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();}DestroyStack(S);}例四、迷宮求解求迷宮中從入口到出口的所有路徑是一個(gè)經(jīng)典的程序設(shè)計(jì)問(wèn)題。由于計(jì)算機(jī)解迷宮時(shí)，通常用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來(lái)保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中應(yīng)用“棧”也就是自然而然的事了。假設(shè)迷宮如下圖所示:假設(shè)“當(dāng)前位置”指的是“在搜索過(guò)程中某一時(shí)刻所在圖中某個(gè)方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置"可通"，則納入"當(dāng)前路徑"，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來(lái)向”退回到“前一通道塊”，然后朝著除“來(lái)向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。所謂“下一位置”指的是“當(dāng)前位置”四周四個(gè)方向（東、南、西、北）上相鄰的方塊。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”。由此，“納入路徑”的操作即為“當(dāng)前位置入棧”；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“出棧”。求迷宮中一條從入口到出口的路徑的算法可簡(jiǎn)單描述如下：設(shè)定當(dāng)前位置的初值為入口位置；do｛若當(dāng)前位置可通，則｛將當(dāng)前位置插入棧頂；//納入路徑若該位置是出口位置，則結(jié)束；//求得路徑存放在棧中否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；｝否則{若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為:沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊若棧不空，則重新測(cè)試新的棧頂位置，直至找到一個(gè)可通的相鄰塊或出棧至棧空；｝｝while(棧不空）；在此，尚需說(shuō)明一點(diǎn)的是，所謂當(dāng)前位置可通，指的是未曾走到過(guò)的通道塊，即要求該方塊位置不僅是通道塊，而且既不在當(dāng)前路徑上（否則所求路徑就不是簡(jiǎn)單路徑），也不是曾經(jīng)納入過(guò)路徑后又從路徑上刪除的通道塊（否則只能在死胡同內(nèi)轉(zhuǎn)圈）。typedefstruct{intord;//通道塊在路徑上的“序號(hào)”P(pán)osTypeseat;//通道塊在迷宮中的“坐標(biāo)位置”intdi;//從此通道塊走向下一通道塊的“方向”}SElemType;//棧的元素類型StatusMazePath(MazeTypemaze,PosTypestart,PosTypeend){//若迷宮maze中從入口start到出口end的通道，//則求得一條存放在棧中（從棧底到棧頂），并返回//TRUE；否則返回FALSEInitStack(S);curpos=start;//設(shè)定“當(dāng)前位置”為“入口位置”curstep=1;//探索第一步do{if(Pass(curpos)){//當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊FootPrint(curpos);//留下足跡e=(curstep,curpos,1);Push(S,e);//加入路徑if(curpos==end)return(TRUE);//到達(dá)終點(diǎn)（出口）curpos=NextPos(curpos,1);/下一位置是當(dāng)前位置的東鄰curstep++;//探索下一步}else{//當(dāng)前位置不能通過(guò)if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){MarkPrint(e.seat);Pop(S,e);//留下不能通過(guò)的標(biāo)記，并退回一步}//whileif(e.di<4){e.di++;Push(S,e);//換下一個(gè)方向探索curpos=NextPos(curpos,e.di);//設(shè)定當(dāng)前位置是該新方向上的相鄰塊}//if}//if}//else}while(!StackEmpty(S));return(FALSE);}//MazePath例五、表達(dá)式求值限于二元運(yùn)算符的表達(dá)式定義:表達(dá)式::=(操作數(shù))+(運(yùn)算符)+(操作數(shù))操作數(shù)::=簡(jiǎn)單變量|表達(dá)式簡(jiǎn)單變量::=標(biāo)識(shí)符|無(wú)符號(hào)整數(shù)在計(jì)算機(jī)中，表達(dá)式可以有三種不同的標(biāo)識(shí)方法設(shè)Exp=S1+OP+S2則稱OP+S1+S2為表達(dá)式的前綴表示法稱S1+OP+S2為表達(dá)式的中綴表示法稱S1+S2+OP為表達(dá)式的后綴表示法可見(jiàn)，它以運(yùn)算符所在不同位置命名的。結(jié)論:操作數(shù)之間的相對(duì)次序不變;運(yùn)算符的相對(duì)次序不同;中綴式丟失了括弧信息，致使運(yùn)算的次序不確定;前綴式的運(yùn)算規(guī)則為:連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;后綴式的運(yùn)算規(guī)則為:運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式;如何從后綴式求值？先找運(yùn)算符，后找操作數(shù)如何從原表達(dá)式求得后綴式？分析“原表達(dá)式”和“后綴式”中的運(yùn)算符:每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來(lái)定，若當(dāng)前運(yùn)算符的優(yōu)先數(shù)小，則暫不進(jìn)行;否則立即進(jìn)行。從原表達(dá)式求得后綴式的規(guī)律為：設(shè)立操作數(shù)棧;設(shè)表達(dá)式的結(jié)束符為“#”,予設(shè)運(yùn)算符棧的棧底為“#”若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式;若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧;否則，退出棧頂運(yùn)算符發(fā)送給后綴式;“(”對(duì)它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開(kāi)始的表達(dá)式的結(jié)束符。算法描述如下：voidtransform(charsuffix[],charexp[]){//從合法的表達(dá)式字符串exp求得其相應(yīng)的后綴式InitStack(S);Push(S,￠#￠);p=exp;ch=*p;while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);//直接發(fā)送給后綴式else{switch(ch){case￠(￠:Push(S,ch);break;case￠)￠:{Pop(S,c);while(c!=￠(￠){Pass(Suffix,c);Pop(S,c)}break;}defult:{while(!Gettop(S,c)&&(precede(c,ch))){Pass(Suffix,c);Pop(S,c);}if(ch!=￠#￠)Push(S,ch);break;}//defult}//switch}//elseif(ch!=￠#￠){p++;ch=*p;}}//while}//CrtExptree表達(dá)式求值的規(guī)則:設(shè)立運(yùn)算符棧和操作數(shù)棧;設(shè)表達(dá)式的結(jié)束符為“#”,予設(shè)運(yùn)算符棧的棧底為“#”若當(dāng)前字符是操作數(shù)，則進(jìn)操作數(shù)棧;若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧;否則，退出棧頂運(yùn)算符作相應(yīng)運(yùn)算;“(”對(duì)它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開(kāi)始的表達(dá)式的結(jié)束符。算法描述如下:OperandTypeEvaluateExpression(){//算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和OPND//分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合。InitStack(OPTR);Push(OPTR,‘#‘);initStack(OPND);c=getchar();while(c!=‘#‘||GetTop(OPTR)!=‘#‘){if(!In(c,OP)){Push((OPND,c);c=getchar();}//不是運(yùn)算符則進(jìn)棧elseswitch(precede(GetTop(OPTR),c){case‘<‘://棧頂元素優(yōu)先權(quán)低Push(OPTR,c);c=getchar();break;case‘=‘://脫括號(hào)并接收下一字符Pop(OPTR,x);c=getchar();break;case‘>‘#//退棧并將運(yùn)算結(jié)果入棧Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression例六、實(shí)現(xiàn)遞歸在高級(jí)語(yǔ)言編制的程序中，調(diào)用函數(shù)與被調(diào)用函數(shù)之間的鏈接和信息交換必須通過(guò)棧例進(jìn)行。當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三件事:將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存;為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū);將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成:保存被調(diào)函數(shù)的計(jì)算結(jié)果;釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是:后調(diào)用先返回此時(shí)的內(nèi)存管理實(shí)行“棧式管理”遞歸過(guò)程指向過(guò)程中占用的數(shù)據(jù)區(qū)，稱之為遞歸工作棧每一層的遞歸參數(shù)合成一個(gè)記錄，稱之為遞歸工作記錄棧頂記錄指示當(dāng)前層的執(zhí)行情況，稱之為當(dāng)前活動(dòng)記錄棧頂指針，稱之為當(dāng)前環(huán)境指針例如:voidhanoi(intn,charx,chary,charz)//將塔座x上按直徑由小到大且至上而下編號(hào)為1至n//的n個(gè)圓盤(pán)按規(guī)則搬到塔座z上，y可用作輔助塔座。1{2if(n==1)3move(x,1,z);//將編號(hào)為１的圓盤(pán)從x移到z4else{5hanoi(n-1,x,z,y);//將x上編號(hào)為１至n-1的圓//盤(pán)移到y(tǒng),z作輔助塔6move(x,n,z);//將編號(hào)為n的圓盤(pán)從x移到z7hanoi(n-1,y,x,z);//將y上編號(hào)為１至n-1的圓盤(pán)//移到z,x作輔助塔8}9}3.3棧類型的實(shí)現(xiàn)順序棧類似于線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。//-----棧的順序存儲(chǔ)表示-----#defineSTACK_INIT_SIZE100;//存儲(chǔ)空間初始分配量#defineSTACKINCREMENT10;//存儲(chǔ)空間分配增量typedefstruct{SElemType*base;//base的初值為NULLSElemType*top;//棧頂指針intstacksize;//當(dāng)前已分配的存儲(chǔ)空間，以元素為單位}SqStack;//-----基本操作的函數(shù)原型說(shuō)明-----StatusInitStack(SqStack&S);//構(gòu)造一個(gè)空棧SStatusDestroyStack(SqStack&S);//銷毀棧S，S不再存在StatusClearStack(SqStack&S);//把S置為空棧StatusStackEmpty(SqStackS);//將棧S為空棧，則返回TRUE，否則返回FALSEintStackLength(SqStackS);//返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度StatusGetTop(SqStackS,SElemType&e);//若棧不空，則用e返回S的棧頂元素，并返回OK；//否則返回ERRORStatusPush(SqStack&S,SElemTypee);//插入元素e為新的棧頂元素StatusPop(SqStack&S,SElemType&e);//若棧不空，則刪除S的棧頂元素，用e返回其值，//并返回OK；否則返回ERROR鏈棧利用鏈表實(shí)現(xiàn)棧，注意鏈表中指針的方向是從棧頂?shù)綏５住?.4隊(duì)列的類型定義ADTQueue{數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{i-1,ai>|ai-1,ai∈D,i=2,...,n}約定其中a1端為隊(duì)列頭，an端為隊(duì)列尾?；静僮鳎篒nitQueue(&Q)操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。DestroyQueue(&Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷毀，不再存在。ClearQueue(&Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：將Q清為空隊(duì)列。QueueEmpty(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FALSE。QueueLength(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。GetHead(Q,&e)初始條件：Q為非空隊(duì)列。操作結(jié)果：用e返回Q的隊(duì)頭元素。EnQueue(&Q,e)初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。DeQueue(&Q,&e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。}ADTQueue3.5隊(duì)列類型的實(shí)現(xiàn)鏈隊(duì)列——鏈?zhǔn)接诚髏ypedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//隊(duì)頭指針QueuePtrrear;//隊(duì)尾指針}LinkQueue;//-----基本操作的函數(shù)原型說(shuō)明-----StatusInitQueue(LinkQueue&Q){//構(gòu)造一個(gè)空隊(duì)列QStatusDestroyQueue(LinkQueue&Q){//銷毀隊(duì)列Q，Q不再存在StatusClearQueue(LinkQueue&Q){//將Q清為空隊(duì)列StatusQueueEmpty(LinkQueueQ){//若隊(duì)列Q為空隊(duì)列，則返回TRUE，否則返回FALSEintQueueLength(LinkQueueQ){//返回Q的元素個(gè)數(shù)，即為隊(duì)列的長(zhǎng)度StatusGetHead(LinkQueueQ,QElemType&e){//若隊(duì)列不空，則用e返回Q的隊(duì)頭元素，并返回OK；//否則返回ERRORStatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e為Q的新的隊(duì)尾元素StatusDeQueue(LinkQueue&Q,QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值，//并返回OK；否則返回ERROR循環(huán)隊(duì)列——順序映象#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度typedefstruct{QElemType*base;//動(dòng)態(tài)分配存儲(chǔ)空間intfront;//頭指針，若隊(duì)列不空，指向隊(duì)列頭元素intrear;//尾指針，若隊(duì)列不空，指向隊(duì)列尾元素//的下一個(gè)位置}SqQueue;3.6隊(duì)列應(yīng)用舉例——排隊(duì)問(wèn)題的系統(tǒng)仿真一、需求分析和規(guī)格說(shuō)明編制一個(gè)事件驅(qū)動(dòng)仿真程序以模擬理發(fā)館內(nèi)一天的活動(dòng)，要求輸出在一天的營(yíng)業(yè)時(shí)間內(nèi)，到達(dá)的顧客人數(shù)、顧客在館內(nèi)的平均逗留時(shí)間和排隊(duì)等候理發(fā)的平均人數(shù)以及在營(yíng)業(yè)時(shí)間內(nèi)空椅子的平均數(shù)。假設(shè)理發(fā)館內(nèi)設(shè)有N把理發(fā)椅，一天內(nèi)連續(xù)營(yíng)業(yè)T小時(shí)。在T小時(shí)內(nèi)顧客到達(dá)的時(shí)間及顧客理發(fā)所需時(shí)間均隨機(jī)生成，過(guò)了營(yíng)業(yè)時(shí)間，不再有顧客進(jìn)門(mén)，但仍需繼續(xù)為已進(jìn)入店內(nèi)的顧客理發(fā)，直至最后一名顧客離開(kāi)為止。二、概要設(shè)計(jì)1.主程序?yàn)?voidBarberShop_Simulation(intchairNum,intCloseTime){//理發(fā)店業(yè)務(wù)模擬，統(tǒng)計(jì)一天內(nèi)顧客在店內(nèi)逗留的平均時(shí)間//和顧客在等待理發(fā)時(shí)排隊(duì)的平均長(zhǎng)度以及空椅子的平均數(shù)OpenForDay;//初始化whileMoreEventdo{EventDrived(OccurTime,EventType);//事件驅(qū)動(dòng)switch(EventType){case‘A‘:CustomerArrived;break;//處理到達(dá)事件case‘D‘:CustomerDeparture;break;//處理離開(kāi)事件default:Invalid;}//switch}//whileCloseForDay;//計(jì)算平均逗留時(shí)間和排隊(duì)的平均長(zhǎng)度}//BarberShop_Simulation2.數(shù)據(jù)類型為:ADTEvent(事件){數(shù)據(jù)對(duì)象:D={事件的發(fā)生時(shí)刻，事件類型}數(shù)據(jù)關(guān)系:R={}基本操作:Initiate(&E,oT,eT);操作結(jié)果:產(chǎn)生一個(gè)發(fā)生時(shí)間為oT,事件類型為eT的事件E;GetOccurTime(ev);初始條件:事件ev已存在，操作結(jié)果:返回該事件的發(fā)生時(shí)間;GetEventType(ev);初始條件:事件ev已存在;操作結(jié)果:返回該事件的類型;}ADTcustomer(顧客){數(shù)據(jù)對(duì)象:D={進(jìn)門(mén)時(shí)刻，理發(fā)所需時(shí)間};數(shù)據(jù)關(guān)系:R={}基本操作:Initiate(&P,aT,cT);操作結(jié)果:產(chǎn)生一個(gè)進(jìn)門(mén)時(shí)刻為aT,理發(fā)時(shí)間為cT的顧客P;GetArrivalTime(Ps);初始條件:顧客Ps已存在，操作結(jié)果:返回該顧客的進(jìn)門(mén)時(shí)刻;GetCutTime(Ps);初始條件:顧客Ps已存在;操作結(jié)果:返回該顧客的理發(fā)時(shí)間;}ADTOrderedList(有序表){數(shù)據(jù)對(duì)象:是上述定義的事件的集合數(shù)據(jù)關(guān)系:按事件的發(fā)生時(shí)刻自小至大有序基本操作:在線性表的操作的基礎(chǔ)上添加一個(gè)有序表的插入Insert(&OL,x)初始條件:有序表OL已存在;操作結(jié)果:在有序表中插入x,并保持表的有序性;}ADT(數(shù)據(jù)元素為上述定義的顧客的)隊(duì)列一．學(xué)習(xí)要點(diǎn)1.掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法，即兩種存儲(chǔ)結(jié)構(gòu)表示時(shí)的基本操作實(shí)現(xiàn)算法，特別應(yīng)注意棧滿和棧空的條件以及它們的描述方法。3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，特別注意隊(duì)滿和隊(duì)空的描述方法。4.理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。二、思考題3.1若按教科書(shū)3.1.1節(jié)中圖3.1(b)所示鐵道進(jìn)行車廂調(diào)度(注意：兩側(cè)鐵道均為單向行駛道)，則請(qǐng)回答：(1)如果進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么?(2)如果進(jìn)站的車廂序列為123456，則能否得到435612和135426的出站序列，并請(qǐng)說(shuō)明為什么不能得到或者如