軟件技術(shù)基礎(chǔ) (2)數(shù)據(jù)結(jié)構(gòu)、順序表幻燈片.ppt

1、NO：1,常用數(shù)據(jù)結(jié)構(gòu),第二章,NO：2,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,目 錄,21 數(shù)據(jù)結(jié)構(gòu),22 線(xiàn)性表,23 棧與隊(duì),25 數(shù)組,26 樹(shù)與二叉樹(shù),27 圖,28 查 找和排 序,NO：3,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 數(shù)據(jù)結(jié)構(gòu),當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn)： a) 所處理的數(shù)據(jù)量大且具有一定的關(guān)系； b) 對(duì)其操作不再是單純的數(shù)值計(jì)算，而更多地是需要對(duì)其進(jìn)行組織、管理和檢索。 應(yīng)用舉例1學(xué)籍檔案管理 假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。,NO：4,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 數(shù)據(jù)結(jié)構(gòu),特點(diǎn)： i ) 每個(gè)學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號(hào)順序依次排列構(gòu)成

2、一張表格； ii ) 表中每個(gè)學(xué)生的信息依據(jù)學(xué)號(hào)的大小存在著一種前后關(guān)系，這就是我們所說(shuō)的線(xiàn)性結(jié)構(gòu)； iii ) 對(duì)它的操作通常是插入某個(gè)學(xué)生的信息，刪除某個(gè)學(xué)生的信息，更新某個(gè)學(xué)生的信息，按條件檢索某個(gè)學(xué)生的信息等等。 應(yīng)用舉例2輸出n個(gè)對(duì)象的全排列 輸出n個(gè)對(duì)象的全排列可以使用下圖所示的形式描述。,NO：5,特點(diǎn)： i ) 在求解過(guò)程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們所說(shuō)的樹(shù)形結(jié)構(gòu)； ii ) 對(duì)它的操作有：建立樹(shù)形結(jié)構(gòu)，輸出最低層結(jié)點(diǎn)內(nèi)容等等。,NO：6,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 數(shù)據(jù)結(jié)構(gòu),應(yīng)用舉例3制定教學(xué)計(jì)劃 在制定教學(xué)計(jì)劃時(shí)，需要考慮各門(mén)課程的開(kāi)設(shè)順序。有些課程

3、需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計(jì)算機(jī)專(zhuān)業(yè)課程的開(kāi)設(shè)情況如下表所示：,NO：7,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 數(shù)據(jù)結(jié)構(gòu),特點(diǎn): i ) 課程之間的先后關(guān)系用圖結(jié)構(gòu)描述； ii ) 通過(guò)實(shí)施創(chuàng)建圖結(jié)構(gòu)，然后對(duì)該有向圖結(jié)構(gòu)中的頂點(diǎn)進(jìn)行拓?fù)渑判颉?課程先后關(guān)系的圖形描形式：,NO：8,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 數(shù)據(jù)結(jié)構(gòu),結(jié)論 計(jì)算機(jī)的操作對(duì)象的關(guān)系更加復(fù)雜，操作形式不再是單純的數(shù)值計(jì)算，而更多地是對(duì)這些具有一定關(guān)系的數(shù)據(jù)進(jìn)行組織管理，我們將此稱(chēng)為非數(shù)值性處理。要使計(jì)算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必須弄清楚這些操作對(duì)象的特點(diǎn)，在計(jì)算

4、機(jī)中的表示方式以及各個(gè)操作的具體實(shí)現(xiàn)手段。這些就是數(shù)據(jù)結(jié)構(gòu)個(gè)章節(jié)研究的主要內(nèi)容。,NO：9,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 數(shù)據(jù)結(jié)構(gòu),一、什么是數(shù)據(jù)結(jié)構(gòu),數(shù)值型與非數(shù)值型數(shù)據(jù),數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單來(lái)說(shuō)，就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 如線(xiàn)性關(guān)系、層次關(guān)系、網(wǎng)狀關(guān)系等。,NO：10,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,二、有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ),數(shù)據(jù)(data)：是信息的載體，它可以用計(jì)算機(jī)表示并加工，如數(shù)、字符、符號(hào)等的集合。分為數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)兩類(lèi)。,數(shù)據(jù)元素(data element)：是數(shù)據(jù)集合中的一個(gè)個(gè)體，是數(shù)據(jù)的基本單位。如數(shù)據(jù)集合N=1

5、，2，3，4，5中整數(shù)1至5均為數(shù)據(jù)元素。 數(shù)據(jù)元素不一定是單個(gè)的數(shù)字或字符，也可能是若干個(gè)數(shù)據(jù)項(xiàng)的組合，如學(xué)生信息。學(xué)生（學(xué)號(hào)，姓名，性別，成績(jī)） 數(shù)據(jù)元素有時(shí)也稱(chēng)結(jié)點(diǎn)或記錄。,NO：11,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,數(shù)據(jù)對(duì)象(data object)：是具有相同性質(zhì)的數(shù)據(jù)元素的集合。如大寫(xiě)字母字符的數(shù)據(jù)對(duì)象是集合：C= A，B，.，Z 。,數(shù)據(jù)結(jié)構(gòu)(data structure)：是指同一數(shù)據(jù)對(duì)象中各數(shù)據(jù)元素間存在的關(guān)系。用集合論方法定義數(shù)據(jù)結(jié)構(gòu)為：S =（D，R） 數(shù)據(jù)結(jié)構(gòu)S是一個(gè)二元組，D是一個(gè)數(shù)據(jù)元素的非空有限集合，R是定義在D上的關(guān)系的非空有限集合。 例如一個(gè)向量

6、x=(x1,x2,xn)，D=x1,x2,xnR=,。,NO：12,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,邏輯結(jié)構(gòu)：是對(duì)數(shù)據(jù)元素之間邏輯關(guān)系（拋開(kāi)具體的關(guān)系含義以及存儲(chǔ)方式等）的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的幾個(gè)關(guān)系來(lái)表示。通?？捎脠D形表示，圓圈表示數(shù)據(jù)元素，箭頭表示關(guān)系： 物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的具體表示和實(shí)現(xiàn)，又稱(chēng)存儲(chǔ)結(jié)構(gòu),E i+1,數(shù)據(jù)元素,數(shù)據(jù)元素,關(guān)系,E i,NO：13,按邏輯結(jié)構(gòu)分類(lèi)： 純集合型結(jié)構(gòu):數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”這一 關(guān)系外，別無(wú)其他關(guān)系 線(xiàn)性結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一個(gè)跟著一個(gè)”的序列關(guān)系 樹(shù)型結(jié)構(gòu)：數(shù)據(jù)元素之間存在“每

7、個(gè)元素只能跟著一個(gè)元素 但可以有多個(gè)元素跟著它”的層次關(guān)系 圖狀結(jié)構(gòu)：任意兩個(gè)數(shù)據(jù)元素之間都可能存在關(guān)系 按存儲(chǔ)結(jié)構(gòu)分類(lèi)： 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 索引存貯結(jié)構(gòu),2.1 概 述,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,NO：14,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,數(shù)據(jù)結(jié)構(gòu)與算法 算法是解決某一特定類(lèi)型問(wèn)題的有限運(yùn)算序 列。 算法的實(shí)現(xiàn)必須借助于程序設(shè)計(jì)語(yǔ)言中提供 的數(shù)據(jù)類(lèi)型及其運(yùn)算。 數(shù)據(jù)結(jié)構(gòu)的選擇對(duì)數(shù)據(jù)處理的效率起著至關(guān) 重要的作用。 程序算法數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)分線(xiàn)性和非線(xiàn)性?xún)煞N。,NO：15,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,三、算法描述語(yǔ)言, 算法是由一套計(jì)算規(guī)則組成的

8、一個(gè)過(guò)程； 組成算法的規(guī)則是確定的、可執(zhí)行的； 算法必須有確定的結(jié)果，有一個(gè)或多個(gè)輸出； 每個(gè)算法必須有0個(gè)或多個(gè)輸入； 解答必須在有限步內(nèi)得到,不能出現(xiàn)“死循環(huán)”。 我們可以得出如下的結(jié)論：算法是一個(gè)過(guò)程，這個(gè)過(guò)程由一套明確的規(guī)則組成，這些規(guī)則指定了一個(gè)操作的順序，以便用有限的步驟提供特定類(lèi)型問(wèn)題的解答。,NO：16,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,舉例 問(wèn)題：按從小到大的順序重新排列x，y，z三個(gè)數(shù)值的內(nèi)容。 算法： （1）輸入x，y，z三個(gè)數(shù)值； （2）從三個(gè)數(shù)值中挑選出最小者并換到x中； （3）從y，z中挑選出較小者并換到y(tǒng)中； （4）輸出排序后的結(jié)果。,NO：17,第二

9、章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,四、算法分析技術(shù)初步, 一個(gè)可執(zhí)行的算法不一定是一個(gè)好算法，算法的分析是一個(gè)復(fù)雜的問(wèn)題，通常用計(jì)算機(jī)執(zhí)行時(shí)在時(shí)間和空間兩方面的消耗多少作為評(píng)價(jià)該算法優(yōu)劣的標(biāo)準(zhǔn)。 這兩個(gè)標(biāo)準(zhǔn)分別稱(chēng)為時(shí)間復(fù)雜度和空間復(fù)雜度。一般時(shí)間復(fù)雜度考慮的較多。 度量一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法： 事后統(tǒng)計(jì)和事前分析估算,NO：18,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述, 事后統(tǒng)計(jì)方法：利用計(jì)算機(jī)內(nèi)部的定時(shí)器(如調(diào)用QueryPerformanceCounter() Api函數(shù) ）對(duì)函數(shù)運(yùn)行時(shí)間進(jìn)行計(jì)數(shù) 缺點(diǎn)：1. 必須執(zhí)行程序 2. 其它因素掩蓋算法本質(zhì) 事前分析估算：

10、運(yùn)行時(shí)間取決于下列因素 a) 選擇何種算法； b) 問(wèn)題的規(guī)模，例如求100以?xún)?nèi)還是1000以?xún)?nèi)的素?cái)?shù) c) 書(shū)寫(xiě)程序的語(yǔ)言：語(yǔ)言級(jí)別越高，執(zhí)行效率越低 d) 編譯程序所產(chǎn)生機(jī)器代碼的質(zhì)量； e) 機(jī)器執(zhí)行指令的速度,NO：19,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,時(shí)間復(fù)雜度 頻度：指一條語(yǔ)句重復(fù)執(zhí)行的次數(shù)。 記作：F(n) 時(shí)間復(fù)雜度：T(n)=O(F(n) 下面舉例說(shuō)明如何求時(shí)間復(fù)雜度？,NO：20,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,1. for (i=0; in; i+)2. for (j=0; jn; j+)3. cij=0;4. for (k=0; kn; k+

11、)5. cij=cij+aik*bkj;6. 我們以執(zhí)行次數(shù)最多的語(yǔ)句（第5句）進(jìn)行計(jì)算： 語(yǔ)句頻度為：F(n)=n3 時(shí)間復(fù)雜度：T(n)=O(F(n)=O(n3),兩個(gè)n階方陣的乘積C = A x B,NO：21,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,4）思考下列程序段的時(shí)間復(fù)雜度 1、x=x+1;,T(n)=O(1),T(n)=O(n),T(n)=O(n2),T(n)=O(n2),4、for (j=2; j=n; j+) for (k=2; k=j-1; k+) x=x+1;,3、for (j=0; jn; j+) for (k=0; kn; k+) x=x+1;,2、for (

12、j=0; jn; j+) x=x+1;,計(jì)算方法：對(duì)于外層循環(huán)中的j，從2到n循環(huán)，計(jì)算出j每取一個(gè)值時(shí)，內(nèi)層循環(huán)執(zhí)行的次數(shù)0、1、2、.、n-2，然后累加起來(lái)，得到一個(gè)n的多項(xiàng)式(n-1)(n-2)/2，取出次數(shù)最高的項(xiàng)即可。,NO：22,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述, 常見(jiàn)的時(shí)間復(fù)雜度 1）O(1)：常量型 2）O(n)、O(n2)、.、O(nk)：多項(xiàng)式型 3）O(log2n)、O(2log2n)：對(duì)數(shù)型 4）O(2n)、O(en)：指數(shù)型,log2n n nlog2n n2 n3 2n 3n n!, 常用的時(shí)間復(fù)雜度比較:,NO：23,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.

13、2 線(xiàn) 性 表,在計(jì)算語(yǔ)句頻度的時(shí)候，通常只估算到F(n)的最高項(xiàng)的階，既不考慮低階項(xiàng)，也不考慮常系數(shù)。 如，有一個(gè)算法A，其語(yǔ)句頻度為 F1(n) = 20n2+100n 另一個(gè)算法B，其語(yǔ)句頻度為 F2(n) = 0.5n2-3n+18 這二個(gè)算法的時(shí)間復(fù)雜度都是一樣的O(n2),時(shí)間復(fù)雜度計(jì)算,NO：24,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,在數(shù)學(xué)上，如果 f(n) = O( g(n) ), 則稱(chēng)為f(n)和g(n)同階，或稱(chēng)為f(n)和g(n)為同一數(shù)量級(jí)，即有：,C是一個(gè)常數(shù),當(dāng) n - 時(shí)，f(n)=(n-1)(n-2)/2 與n2成正比，即程序運(yùn)行時(shí)間的量度與n2為

14、同一數(shù)量級(jí)，因此即為O(n2).,NO：25,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,常用的時(shí)間復(fù)雜度: O(1) 常數(shù)時(shí)間，即算法時(shí)間用量和輸入數(shù)據(jù)量無(wú)關(guān) O(logn) 對(duì)數(shù)時(shí)間，對(duì)數(shù)階通常不寫(xiě)底數(shù)，在計(jì)算 機(jī)科學(xué)中，一般以2為底 O(n) 線(xiàn)性時(shí)間，即算法時(shí)間用量與n成正比 O(nlogn) O(n2) O(n3) 。,以上都屬于多項(xiàng)式階，在算法理論中，如果某算法的時(shí)間用量的階超過(guò)多項(xiàng)式階，達(dá)到指數(shù)時(shí)間O(2n)，或階乘時(shí)間O(n!)，那么這個(gè)算法就是一個(gè)無(wú)效算法，因?yàn)橹灰獢?shù)據(jù)量n稍大，算法就不可能在“有限步”內(nèi)完成。相應(yīng)地，多項(xiàng)式時(shí)間階的算法屬于有效算法。,NO：26,第二章

15、 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.1 概 述,空間復(fù)雜度 空間復(fù)雜度是指在算法中所需的輔助空間單元而不包括問(wèn)題的原始數(shù)據(jù)占用的空間（因?yàn)檫@些單元與算法無(wú)關(guān)），記作：S(n) 時(shí)間與空間是一對(duì)矛盾。要節(jié)約空間往往就要消耗較多時(shí)間，反之亦然，而目前由于計(jì)算機(jī)硬件的發(fā)展，一般都有足夠的內(nèi)存空間，因此在分析中著重考慮時(shí)間的因素。,NO：27,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,一、線(xiàn)性表的定義和運(yùn)算,線(xiàn)性表的概念 由相同種類(lèi)的數(shù)據(jù)元素組成的一個(gè)有窮序列稱(chēng)為一個(gè)線(xiàn)性表?！耙粋€(gè)跟著一個(gè)”,符號(hào)表示法：L（a1,a2,an） 圖形表示法：,a2,an,a1,NO：28,其中： ai -表示線(xiàn)性表 L

16、 的第 i 個(gè)數(shù)據(jù)元素 n -表示線(xiàn)性表 L 的表長(zhǎng)（n=0） n=0 時(shí)的線(xiàn)性表稱(chēng)為空表 ai-1 稱(chēng)為 ai 的前驅(qū)，ai+1 稱(chēng)為 ai 的后繼,線(xiàn)性表的結(jié)構(gòu)特點(diǎn),數(shù)據(jù)元素之間是線(xiàn)性關(guān)系，即在線(xiàn)性表中必存在唯一的一個(gè)稱(chēng)為“第一個(gè)”的元素；必存在唯一的一個(gè)稱(chēng)為“最后一個(gè)”的元素；,NO：29,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,除第一個(gè)元素外，每個(gè)元素都有且只有一個(gè)前驅(qū)元素；除最后一個(gè)元素外，每個(gè)元素都有且只有一個(gè)后繼元素。所有數(shù)據(jù)元素ai在同一個(gè)線(xiàn)性表中必須是相同的數(shù)據(jù)類(lèi)型。 線(xiàn)性表的定義 L=（D，R）,有序?qū)?NO：30,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表

17、,有序表與無(wú)序表的概念 若線(xiàn)性表中的數(shù)據(jù)元素相互之間可以比較，且aiai-1 ，i=2，3，.，n 則稱(chēng)該線(xiàn)性表為有序表，否則稱(chēng)為無(wú)序表。 線(xiàn)性表的基本運(yùn)算 插入、刪除、查找、排序等。,NO：31,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,二、順序存儲(chǔ)線(xiàn)性表,順序存儲(chǔ)結(jié)構(gòu)（順序表） 要實(shí)現(xiàn)在計(jì)算機(jī)內(nèi)表示一個(gè)數(shù)據(jù)結(jié)構(gòu)，要解決兩種信息的存貯問(wèn)題： 數(shù)據(jù)元素本身的存貯 數(shù)據(jù)元素之間關(guān)系的存貯 定義：利用內(nèi)存物理結(jié)構(gòu)上的鄰接特點(diǎn)，實(shí)現(xiàn)線(xiàn)性表的“一個(gè)跟著一個(gè)”這一序列關(guān)系的存貯方式，稱(chēng)為線(xiàn)性表的順序存貯結(jié)構(gòu)，其上的線(xiàn)性表稱(chēng)為順序表。,NO：32,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,

18、 地址計(jì)算：設(shè)每個(gè)元素占k個(gè)單元，線(xiàn)性表在內(nèi)存中的首地址為：addr(a1)，則線(xiàn)性表中第i個(gè)元素的存儲(chǔ)地址為： addr(ai)=addr(a1)+(i-1)*k 特點(diǎn)：這種存儲(chǔ)結(jié)構(gòu)只要知道元素的序號(hào)，就很容易找到第i個(gè)數(shù)據(jù)元素，且無(wú)論序號(hào)i為何值，找到第i個(gè)元素所需時(shí)間相同。所以，這種存儲(chǔ)結(jié)構(gòu)亦稱(chēng)為隨機(jī)存儲(chǔ)結(jié)構(gòu)。,NO：33,在順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置也是相鄰的，因此，數(shù)據(jù)元素之間的前后件關(guān)系可以由它們?cè)诖鎯?chǔ)結(jié)構(gòu)中前后位置的鄰接關(guān)系唯一確定。 順序存儲(chǔ)主要用于線(xiàn)性結(jié)構(gòu)，不能用于非線(xiàn)性結(jié)構(gòu),2.2 線(xiàn) 性 表,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算, 該結(jié)構(gòu)用高級(jí)語(yǔ)

19、言中的一維數(shù)組類(lèi)型表示。數(shù)組中的分量下標(biāo)即為元素在線(xiàn)性表中的序號(hào)。例如：可用一維數(shù)組An來(lái)存儲(chǔ)線(xiàn)性表：（a1, a2 ,.，an）。 這里需要聲明：C語(yǔ)言中，數(shù)組下標(biāo)從0開(kāi)始。,NO：34,順序表之整體概念：,data,0,1,n,Maxsize,n,數(shù)組下標(biāo),數(shù)組,變量,操作算法,Maxsize-1,初始化操作,插入操作,刪除操作,查找操作,排序操作,. . . . . .,. . .,. . .,. . .,Maxsize 是為判斷順序表是否為滿(mǎn)而設(shè)，n是為便于判斷順序表是否為空、求表長(zhǎng)、置空表,NO：35,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,順序存儲(chǔ)結(jié)構(gòu)的插入、刪除運(yùn)算 插

20、入 1）問(wèn)題描述：有線(xiàn)性表(a1,a2 ,.，an)，長(zhǎng)度為n，要在第i-1與第i個(gè)元素之間插入一個(gè)新元素。 2）插入過(guò)程：先將第i至第n個(gè)元素依次向后移動(dòng)一個(gè)位置，然后將新元素插入在第i個(gè)位置上，線(xiàn)性表的長(zhǎng)度變?yōu)閚+1。,NO：36,NO：37,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,3）算法描述（順序表插入） int InsertSList(int L,int n,int i,int x) /n:表長(zhǎng)度 i:在位置i處插入 x:插入元素x int j; if (in)/插入位置非法 printf(nCant insert!n); else for (j=n-1;j=i;j-) L

21、j+1=Lj;/后移 Li=x;/插入 n+;/表長(zhǎng)加1 return(n);/返回表長(zhǎng) ,NO：38,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表, 刪除 1）問(wèn)題描述：有線(xiàn)性表(a1,a2 ,.，an)，長(zhǎng)度為n，要將第i個(gè)元素刪除。 2）刪除過(guò)程：將第i+1至第n個(gè)元素依次向前移動(dòng)一個(gè)位置，線(xiàn)性表的長(zhǎng)度變?yōu)閚-1。,1,2,. . .,0,i-1,i,i+1,n-1,n,1,. . .,. . .,. . .,. . .,. . .,NO：39,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,3）算法描述（順序表刪除） int DeleteSList(int L,int n,int

22、 i) int j; if (in-1) /刪除位置非法 printf(nCant delete!n); else for (j=i;j=n-2;j+)Lj=Lj+1;/前移 n-; /表長(zhǎng)減1 return(n); /返回表長(zhǎng) ,NO：40,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,運(yùn)算的時(shí)間分析 在插入和刪除運(yùn)算中，時(shí)間主要消耗在移動(dòng)元素上，所需移動(dòng)的元素個(gè)數(shù)與線(xiàn)性表的長(zhǎng)度n和被插入或刪除的元素在線(xiàn)性表中的位置有關(guān)，我們來(lái)求平均性能。 設(shè)pi是將一個(gè)元素插入在第i個(gè)位置的概率，則在長(zhǎng)度為n的線(xiàn)性表中插入一個(gè)元素所需的平均移動(dòng)次數(shù)為：,NO：41,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2

23、 線(xiàn) 性 表,在等概率情況下，pi=1/(n+1)，則有：, 同理，刪除時(shí)有：,在等概率情況下，qi=1/n，則有：,NO：42,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表, 從上述分析可以看出：無(wú)論是插入或刪除一個(gè)元素，平均需要移動(dòng)表中一半的元素，這在表長(zhǎng)n較大時(shí)是相當(dāng)可觀(guān)的，因此這種存儲(chǔ)結(jié)構(gòu)僅適用于不經(jīng)常進(jìn)行插入和刪除運(yùn)算以及表中元素相對(duì)穩(wěn)定的場(chǎng)合。 最大表長(zhǎng)難以估計(jì)，太大了浪費(fèi)空間，太小 了容易溢出,NO：43,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,三、線(xiàn)性鏈表,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn) 1）插入和刪除時(shí)需移動(dòng)大量的元素； 2）要求存放元素的存儲(chǔ)單元連續(xù)； 3）

24、有時(shí)會(huì)造成空間浪費(fèi)或溢出。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 1）存儲(chǔ)單元不要求連續(xù)，插入和刪除方便。,NO：44,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,2）每個(gè)元素至少包含兩個(gè)域：數(shù)據(jù)域(data)和指針域(next)，數(shù)據(jù)域用來(lái)存放元素的值，指針域用來(lái)存放后繼元素的存儲(chǔ)地址。 3）指示鏈表中第一個(gè)結(jié)點(diǎn)的指針?lè)Q為頭指針（head），最后一個(gè)結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)，它的指針域?yàn)榭?記為NULL或)。如下圖：,NO：45,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,線(xiàn)性鏈表的基本運(yùn)算 基本操作（見(jiàn)下頁(yè)圖示）,線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖,NO：46,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,1）指針

25、賦值：s=p；q=p-next；,2）指針移動(dòng)：p=p-next；,3）后插：s-next=p-next；p-next=s；,4）前插：q=head；while(q-next!=p) q=q-next;q-next=s；s-next=p；,NO：47,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表, 插入運(yùn)算 1）問(wèn)題描述：在頭指針為head的鏈表中，在值為a的結(jié)點(diǎn)前面插入一個(gè)值為x的結(jié)點(diǎn)。若鏈表為空，則x成為其頭結(jié)點(diǎn)；若表中無(wú)a元素，則將x插入鏈表末尾。,q-next=s;,s-next=q-next;,2）算法描述,NO：48,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,NODE

26、*InsertList(NODE *head,int a,int x)NODE *s,*q;s=GetListNode(x); if (!s) return(head);if (head=NULL)/表為空時(shí) head=s; return(head);if (head-data=a)/第一個(gè)結(jié)點(diǎn)滿(mǎn)足 s-next=head; head=s; return(head);q=head;/其它情況，進(jìn)行查找 while (q-next!=NULL /返回頭指針 ,NODE *GetListNode(int x)NODE *s;s=(NODE *)malloc(NODESIZE);if (s) s-d

27、ata=x; s-next=NULL; return(s);,NO：49,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表, 刪除運(yùn)算 1）問(wèn)題描述：在頭指針為head的鏈表中， 將值為a的結(jié)點(diǎn)刪除。,p=q-next;,q-next=p-next;,free(p);,2）算法描述,NO：50,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,NODE *DeleteList(NODE *head,int a)NODE *p,*q;if (head=NULL) return(NULL);if (head-data=a) /第一個(gè)結(jié)點(diǎn)滿(mǎn)足 p=head; head=head-next; free

28、(p); return(head);q=head; /其它情況，進(jìn)行查找 while (q-next!=NULL /返回頭指針 ,NO：51,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表, 具有頭結(jié)點(diǎn)的線(xiàn)性鏈表 1）如果在鏈表的第一個(gè)結(jié)點(diǎn)之前附加一個(gè)頭結(jié)點(diǎn)，該結(jié)點(diǎn)的結(jié)構(gòu)和鏈表中其它結(jié)點(diǎn)相同，只是它的數(shù)據(jù)域中不存放線(xiàn)性表的元素，它的指針域指向線(xiàn)性表的第一個(gè)元素。當(dāng)表空時(shí)只有一個(gè)頭結(jié)點(diǎn)，它的指針域?yàn)榭?，如下圖：,NO：52,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,2）在線(xiàn)性鏈表中附加一個(gè)頭結(jié)點(diǎn)后便可以使算法在形式上得以簡(jiǎn)化，例如在以上的插入運(yùn)算中，當(dāng)表空時(shí)尚有頭結(jié)點(diǎn)存在，因此頭指針?lè)?/p>

29、空，這與表中不存在a元素的算法相同，當(dāng)a為表中第一個(gè)元素時(shí)，因有頭結(jié)點(diǎn)存在，則在a結(jié)點(diǎn)之前插入一元素時(shí)不必修改頭指針。 算法可仿照無(wú)頭結(jié)點(diǎn)鏈表的操作自行寫(xiě)出。,NO：53,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,線(xiàn)性鏈表的其它形式 循環(huán)鏈表 特點(diǎn)：表中最后一個(gè)結(jié)點(diǎn)的指針域不為空，而是指向表頭，整個(gè)鏈表形成一個(gè)環(huán)。與一般鏈表不同之處在于只要給定循環(huán)鏈表中任一結(jié)點(diǎn)的地址，就可以查遍表中所有的結(jié)點(diǎn)，而不必從頭指針開(kāi)始。如下圖：,NO：54,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表, 雙向鏈表 特點(diǎn)：表中每個(gè)結(jié)點(diǎn)有兩個(gè)指針域：一個(gè)指向直接后繼，一個(gè)指向直接前驅(qū)，那么從表中任一結(jié)點(diǎn)都可

30、以隨意向前或向后查找。但在作插入、刪除運(yùn)算時(shí)，需同時(shí)修改兩個(gè)方向上的指針。如下圖：,NO：55,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,應(yīng)用實(shí)例一元多項(xiàng)式相加 問(wèn)題描述 一個(gè)一元多項(xiàng)式可以表示為：,其中每一項(xiàng)由系數(shù)Pi及x的指數(shù)i組成。若多項(xiàng)式按升冪排列，則它由n+1個(gè)系數(shù)唯一確定，因此可以用一個(gè)線(xiàn)性表P表示：,其指數(shù)i隱藏在系數(shù)Pi的序號(hào)內(nèi)。,NO：56,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表, 問(wèn)題分析 1）存儲(chǔ)結(jié)構(gòu)：多項(xiàng)式相加時(shí)，常要合并同類(lèi)項(xiàng)，由此就要改變多項(xiàng)式的系數(shù)和指數(shù)，而且在實(shí)際問(wèn)題中，時(shí)常會(huì)出現(xiàn)多項(xiàng)式的次數(shù)很高但又存在大量零系數(shù)的項(xiàng)，因此宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

31、 2）結(jié)點(diǎn)結(jié)構(gòu)：每一個(gè)非零項(xiàng)構(gòu)成鏈表中的一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)由兩個(gè)數(shù)據(jù)域和一個(gè)指針域構(gòu)成，如下圖：,NO：57,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,3）鏈表結(jié)構(gòu)：采用帶頭結(jié)點(diǎn)的線(xiàn)性鏈表表示多項(xiàng)式A(x)、B(x)，相加后結(jié)果在線(xiàn)性鏈表C(x)中。 4）運(yùn)算過(guò)程：設(shè)指針ha、hb分別為多項(xiàng)式鏈表A(x)、B(x)的頭指針，指針p、q的初始位置分別指向A(x)、B(x)中的第一項(xiàng)。過(guò)程為：比較p、q所指結(jié)點(diǎn)中的指數(shù)項(xiàng)。 若：p-expexp，那么p所指的結(jié)點(diǎn)為C(x)中的一項(xiàng)，令p指針后移一個(gè)結(jié)點(diǎn)；,NO：58,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,若：p-expq-exp，則

32、q所指的結(jié)點(diǎn)為C(x)中的一項(xiàng)，將q結(jié)點(diǎn)插入p結(jié)點(diǎn)之前，并令q指針后移一個(gè)結(jié)點(diǎn)； 若p-exp=q-exp，則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，當(dāng)和不為零時(shí)，修改p結(jié)點(diǎn)中的系數(shù)，釋放q結(jié)點(diǎn)；否則，刪去p結(jié)點(diǎn)，同時(shí)釋放p、q結(jié)點(diǎn)。 這種方法實(shí)際上是將B(x)加到A(x)中，最后形成C(x)，因此C(x)中的結(jié)點(diǎn)不需要重新生成。, 算法描述（一元多項(xiàng)式加法）,NO：59,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,EXPNODE *AddPoly(EXPNODE *ha,EXPNODE *hb) p=ha-next; q=hb-next; pre=ha; hc=ha; while (p!=NULL ,

33、NO：60,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,四、順序表和鏈表的比較, 順序表 插入、刪除運(yùn)算時(shí)間代價(jià)O(n) 預(yù)先申請(qǐng)固定長(zhǎng)度的數(shù)組 如果整個(gè)數(shù)組元素很滿(mǎn)，則沒(méi)有結(jié)構(gòu)性存儲(chǔ)開(kāi)銷(xiāo) 鏈表 插入、刪除運(yùn)算時(shí)間代價(jià)O(1) 但找到第i個(gè)刪除元素運(yùn)算時(shí)間代價(jià)O(n) 存儲(chǔ)利用指針，動(dòng)態(tài)地按照需要為表中新的元素分配存儲(chǔ) 空間 每個(gè)元素都有結(jié)構(gòu)性存儲(chǔ)開(kāi)銷(xiāo),NO：61,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表, 線(xiàn)性表的長(zhǎng)度是否固定 向量的存儲(chǔ)空間是靜態(tài)分配的，執(zhí)行期間上下界固定，適用于表長(zhǎng)固定的場(chǎng)合；鏈表的存儲(chǔ)空間是在執(zhí)行過(guò)程中動(dòng)態(tài)分配的，適用于表長(zhǎng)不固定的場(chǎng)合。 線(xiàn)性表的主要操作

34、是什么 向量是連續(xù)存放的，適用于頻繁查找操作的表。鏈表適用于經(jīng)常進(jìn)行插入和刪除的表。 采用的算法語(yǔ)言：鏈表要求指針類(lèi)型變量。,NO：62,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,單鏈表的存儲(chǔ)映像,NO：63,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,3. 線(xiàn)性表的查找 1) 順序查找法：最簡(jiǎn)單直觀(guān)的一種方法，從表的一端（表頭或表尾作為查找起點(diǎn)），向另一個(gè)端點(diǎn)（查找終點(diǎn)），逐一檢測(cè)是否是要查找的結(jié)點(diǎn)。,for (i=0; in; i+) if( ai = x) return(i); return(-1); 從左到右 查找,for (i=n-1; i=0; i-) if( ai

35、= x) return(i); return(-1); 從右到左查找,NO：64,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表, 分析：用查找長(zhǎng)度（查找時(shí)需要檢測(cè)的結(jié)點(diǎn)數(shù)目）描述查找算法的效率。 最大查找長(zhǎng)度是表長(zhǎng)n，在等概率條件下，平均查找長(zhǎng)度是表長(zhǎng)的一半，即n/2，從時(shí)間復(fù)雜度上看，都為O(n). 2) “監(jiān)督元”技術(shù): 在查找終點(diǎn)設(shè)置一個(gè)監(jiān)督元結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)表的實(shí)際元素，而使存儲(chǔ)一個(gè)能夠?qū)Τ绦虻倪\(yùn)行起到監(jiān)督控制作用的特殊元素。 監(jiān)督元的設(shè)立可以簡(jiǎn)化程序結(jié)構(gòu)，查找的速度也會(huì)提高些。,NO：65,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.2 線(xiàn) 性 表,例：帶表頭監(jiān)督元的線(xiàn)性表順序查找算法

36、輸入：順序存儲(chǔ)在數(shù)組am的a1到an單元中長(zhǎng)度為n的線(xiàn)性表(0nm) 和 待查元素值 x 輸出：值為x的結(jié)點(diǎn)地址(下標(biāo))i, 若x不在表中，則返回i=0(假定”0”為無(wú)效地址),int search( element_type a , element_type x, int n) int i = n; a0 = x; /預(yù)置監(jiān)督元 while( ai != x) i-; return(i); ,由于監(jiān)督位a0上預(yù)先放置待查元素x，所以while循環(huán)每次執(zhí)行只需要測(cè)試一個(gè)條件(ai是否等于x)，而不必像前面程序那樣需要測(cè)試二個(gè)條件(是否找到x /棧滿(mǎn)top+; stop=x;/指示器加1，入棧

37、return(top); /成功，返top ,NO：72,NO：73,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì), 順序棧的刪除（退棧）：只要將top減“1”即可。算法： int PopS(int s,int top,int *y) if (top=0) stack_empty(); /?？?*y=stop; /棧頂元素由y返回 top-; /指示器減1 return(top); /成功，返top ,NO：74,NO：75,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì),順序存儲(chǔ)下的進(jìn)棧和出棧算法都不帶循環(huán)語(yǔ)句，故其運(yùn)行速度(即消耗時(shí)間)都是O(1)，插入和刪除的工作量與表長(zhǎng)度(即棧中

38、元素的個(gè)數(shù))無(wú)關(guān)，比一般線(xiàn)性表插入和刪除速度快。所以，在程序設(shè)計(jì)中，如果能夠用棧表示的線(xiàn)性表一定要用棧來(lái)表示。,性能分析：,NO：76,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì),鏈棧 鏈棧是用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，top為棧頂指針，指示棧頂元素位置，若top=NULL,則表示棧空。鏈棧一般不會(huì)出現(xiàn)上溢，除非內(nèi)存中已不存在可用空間。如下圖：,NO：77,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì), 鏈棧的插入：修改top值即可。算法如下： 1）插入算法 NODE *PushL(NODE *top,int x)NODE *s;s=GetListNode(x); /申請(qǐng)結(jié)點(diǎn) if (s

39、)/申請(qǐng)成功，插入 s-next=top; top=s;return(top); /返回棧頂指針 ,NO：78,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì), 鏈棧的刪除：修改top值，返回頭結(jié)點(diǎn)即可。算法如下： 1）刪除算法 NODE *PopL(NODE *top) NODE *s;if (top!=NULL) s=top; top=top-next; free(s);return(top);,NO：79,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì),棧的應(yīng)用 將從鍵盤(pán)輸入的字符序列逆置輸出 比如，從鍵盤(pán)上輸入：tset a si sihT；算法將輸出： This is a tes

40、t. 下面給出解決這個(gè)問(wèn)題的算法。 void ReverseRead( ) STACK S; /定義一個(gè)棧結(jié)構(gòu)S char ch; InitStack( /初始化棧,棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在C語(yǔ)言中可用下列類(lèi)型定義實(shí)現(xiàn)： type struct node /鏈棧的結(jié)點(diǎn)結(jié)構(gòu) StackEntry item; /棧的數(shù)據(jù)元素類(lèi)型 struct node *next; /指向后繼結(jié)點(diǎn)的指針 NODE; typedef struct stack NODE *top; STACK;,NO：80,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì),while (ch=getchar()!=n) /從鍵盤(pán)輸入字符，

41、直到輸入換行符為止 Push( ,NO：81,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì), 十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制 使用展轉(zhuǎn)相除法將一個(gè)十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制數(shù)值。 即用該十進(jìn)制數(shù)值除以2，并保留其余數(shù)；重復(fù)此操作，直 到該十進(jìn)制數(shù)值為0為止。最后將所有的余數(shù)反向輸出就是 所對(duì)應(yīng)的二進(jìn)制數(shù)值。 比如：(692)10 = (1010110100)2，其展轉(zhuǎn)相除的過(guò)程如 下圖所示：,NO：82,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì),下面給出解決這個(gè)問(wèn)題的算法。 void Decimal_Binary( ) STACK S; /定義棧結(jié)構(gòu)S InitStack( /被除數(shù)data整

42、除以2，得到新的被除數(shù) ,NO：83,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì),while (!StackEmpty(S) /依次從棧中彈出每一個(gè)余數(shù)，并輸出之 Pop( ,NO：84,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì), 表達(dá)式求值 1）高級(jí)語(yǔ)言中的表達(dá)式是用人們熟悉的公式形式書(shū)寫(xiě)的，編譯系統(tǒng)要根據(jù)表達(dá)式的運(yùn)算順序?qū)⑺g成機(jī)器指令序列。 2）為解決運(yùn)算順序問(wèn)題，把運(yùn)算符分成若干等級(jí)，稱(chēng)為優(yōu)先數(shù)。 3）為進(jìn)行表達(dá)式的翻譯，需設(shè)立兩個(gè)棧，分別存放操作數(shù)(NS)和運(yùn)算符(OS)。,NO：85,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì),4）首先在OS中放入表達(dá)式結(jié)束符

43、“；”，然后自左至右掃描表達(dá)式，根據(jù)掃描的每一個(gè)符號(hào)作如下不同處理： 若為操作數(shù)，將其壓入NS棧 若為運(yùn)算符，需看當(dāng)前OS的棧頂元素： 若OS棧頂運(yùn)算符小于當(dāng)前運(yùn)算符的優(yōu)先數(shù)，則將當(dāng)前運(yùn)算符壓入OS棧。 若OS棧頂運(yùn)算符大于等于當(dāng)前運(yùn)算符的優(yōu)先數(shù)，則從NS棧中彈出兩個(gè)操作數(shù)，,NO：86,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì),設(shè)為x、y，再?gòu)腛S棧中彈出一個(gè)運(yùn)算符，設(shè)為，由此構(gòu)成一條機(jī)器指令：y x T，并將結(jié)果T送入NS棧。 若當(dāng)前運(yùn)算符為“；”，且OS棧頂也為“；”，則表示表達(dá)式處理結(jié)束，此時(shí)NS棧頂?shù)脑丶礊榇吮磉_(dá)式的值。 算法描述,NO：87,第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算,2.3 棧 與 隊(duì),Exp(OS,topO,NS,topN) Push(OS,topO,;); /在OS棧中壓入結(jié)束符 t=0; /t=0表示掃描下一個(gè)符號(hào) while (t!=2) /當(dāng)處理沒(méi)有結(jié)束時(shí)循環(huán)if (t=0) w=getchar(); /讀取一個(gè)符號(hào)if (w為操作數(shù)) Push(NS,topN,w); /操作數(shù)壓NS棧else Top(OS,topO,q); /查看OS棧頂元素