數(shù)據(jù)結(jié)構(gòu)第一章

1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（DataStructure）是計(jì)算機(jī)及相關(guān)專業(yè)的技術(shù)基礎(chǔ)課，是十分重要的核心課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。

只要我們建立了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，按照某種算法編寫了相關(guān)程序，就可以實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)檢索。

問題：

通過計(jì)算機(jī)查找某個(gè)學(xué)生的有關(guān)情況或者想查詢某個(gè)專業(yè)或年級(jí)的學(xué)生的有關(guān)情況。分析：建立一張按學(xué)號(hào)順序排列的學(xué)生信息表和分別按姓名、專業(yè)、年級(jí)順序排列的索引表，便可實(shí)現(xiàn)相關(guān)的查詢學(xué)生信息檢索系統(tǒng)案例1

學(xué)號(hào)姓名性別專業(yè)年級(jí)980001吳承志男計(jì)算機(jī)科學(xué)與技術(shù)98級(jí)980002李淑芳女信息與計(jì)算科學(xué)98級(jí)990301劉麗女?dāng)?shù)學(xué)與應(yīng)用數(shù)學(xué)99級(jí)990302張會(huì)友男信息與計(jì)算科學(xué)99級(jí)990303石寶國(guó)男計(jì)算機(jī)科學(xué)與技術(shù)99級(jí)000801何文穎女計(jì)算機(jī)科學(xué)與技術(shù)2000級(jí)000802趙勝利男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2000級(jí)000803崔文靖男信息與計(jì)算科學(xué)2000級(jí)010601劉麗女計(jì)算機(jī)科學(xué)與技術(shù)2001級(jí)010602魏永鳴男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2001級(jí)學(xué)生信息表計(jì)算機(jī)科學(xué)與技術(shù)1，5，6，9信息與計(jì)算科學(xué)2，4，8數(shù)學(xué)與應(yīng)用數(shù)學(xué)3，7，102000級(jí)6，7，82001級(jí)9，1098級(jí)1，299級(jí)3，4，5專業(yè)索引表年級(jí)索引表記錄號(hào)

1

2

3

4

5

6

7

8

9

10學(xué)生信息檢索系統(tǒng)案例1崔文靖8何文穎6李淑芳2劉麗3，9石寶國(guó)5魏永鳴10吳承志1趙勝利7張會(huì)有4姓名索引表學(xué)號(hào)姓名性別專業(yè)年級(jí)980001吳承志男計(jì)算機(jī)科學(xué)與技術(shù)98級(jí)980002李淑芳女信息與計(jì)算科學(xué)98級(jí)990301劉麗女?dāng)?shù)學(xué)與應(yīng)用數(shù)學(xué)99級(jí)990302張會(huì)友男信息與計(jì)算科學(xué)99級(jí)990303石寶國(guó)男計(jì)算機(jī)科學(xué)與技術(shù)99級(jí)000801何文穎女計(jì)算機(jī)科學(xué)與技術(shù)2000級(jí)000802趙勝利男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2000級(jí)000803崔文靖男信息與計(jì)算科學(xué)2000級(jí)010601劉麗女計(jì)算機(jī)科學(xué)與技術(shù)2001級(jí)010602魏永鳴男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2001級(jí)學(xué)生信息表記錄號(hào)

1

2

3

4

5

6

7

8

9

10教學(xué)計(jì)劃編排問題案例2問題：如何通過計(jì)算機(jī)編排教學(xué)計(jì)劃？算法分析：一個(gè)教學(xué)計(jì)劃包含許多課程，在教學(xué)計(jì)劃包含的許多課程之間，有些必須按規(guī)定的先后次序進(jìn)行，有些則沒有次序要求。即有些課程之間有先修和后續(xù)的關(guān)系，有些課程可以任意安排次序。這種各個(gè)課程之間的次序關(guān)系可用一個(gè)稱作圖的數(shù)據(jù)結(jié)構(gòu)來表示課程編號(hào) 課程名稱 先修課程 C1

計(jì)算機(jī)導(dǎo)論 無 C2

數(shù)據(jù)結(jié)構(gòu) C1，C4

C3

匯編語言 C1

C4 C程序設(shè)計(jì)語言C1

C5

計(jì)算機(jī)圖形學(xué)C2，C3，C4

C6

接口技術(shù) C3

C7

數(shù)據(jù)庫原理 C2，C9

C8

編譯原理 C4

C9

操作系統(tǒng) C2

（a）計(jì)算機(jī)專業(yè)的課程設(shè)置C1C2C3C6C4C5C9C7C8（b）表示課程之間優(yōu)先關(guān)系的有向圖圖1.2教學(xué)計(jì)劃編排問題的數(shù)據(jù)結(jié)構(gòu)由以上兩個(gè)例子可見，描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，可以說數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。目的是為了了解計(jì)算機(jī)處理對(duì)象的特性，將實(shí)際問題中所涉及的處理對(duì)象在計(jì)算機(jī)中表示出來并對(duì)它們進(jìn)行處理。1.2基本概念和術(shù)語數(shù)據(jù)（Data）：信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。數(shù)據(jù)元素（DataElement）：數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。數(shù)據(jù)對(duì)象（DataObject）或數(shù)據(jù)元素類（DataElementClass）：具有相同性質(zhì)的數(shù)據(jù)元素的集合。

數(shù)據(jù)結(jié)構(gòu)是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有下列四類基本的結(jié)構(gòu)：集合結(jié)構(gòu)。在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。樹型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。（a）集合結(jié)構(gòu)（b）線性結(jié)構(gòu)（c）樹型結(jié)構(gòu)（d）圖形結(jié)構(gòu)圖1.3四類基本結(jié)構(gòu)的示意圖集合結(jié)構(gòu)如:

整數(shù)集合1、3、-5、200、0字母集合A、b、C、z線性結(jié)構(gòu)

A,B,C,·······，X,Y,Z學(xué)生成績(jī)表86胡孝臣986110395劉忠賞9861107100張卓9861109成績(jī)姓名學(xué)號(hào)線性表——結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié)線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式計(jì)算機(jī)程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu)ABCDEFGH樹形結(jié)構(gòu)——結(jié)點(diǎn)間具有分層次的連接關(guān)系HBCDEFGA1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213D={1,2,3}R={(1,2),(2,3),(3,2),(1,3)}

圖形結(jié)構(gòu)——節(jié)點(diǎn)間的連結(jié)是任意的一個(gè)數(shù)據(jù)結(jié)構(gòu)有兩個(gè)要素。一個(gè)是數(shù)據(jù)元素的集合，另一個(gè)是關(guān)系的集合?？梢圆捎靡粋€(gè)二元組來表示。Data_Structure＝（D，R）有限個(gè)數(shù)據(jù)元素的集合有限個(gè)元素間關(guān)系的集合數(shù)據(jù)的邏輯結(jié)構(gòu)形式如：集合結(jié)構(gòu):松散式前后數(shù)據(jù)元素沒有關(guān)聯(lián),如整數(shù)類型的數(shù)據(jù)；線性式：數(shù)據(jù)元素按一定順序排列,元素間存在一對(duì)一關(guān)系；樹狀結(jié)構(gòu)：像自然界的樹,元素間存在一對(duì)多關(guān)系,如文件夾；圖狀網(wǎng)絡(luò):數(shù)據(jù)元素間多對(duì)多關(guān)系,如城市交通網(wǎng)。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)（LogicalStructure）和數(shù)據(jù)的物理結(jié)構(gòu)（PhyicalStructure）。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)（LogicalStructure）和數(shù)據(jù)的物理結(jié)構(gòu)（PhyicalStructure）。計(jì)算機(jī)管理圖書問題在圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排如何將查詢圖書的這些信息存入計(jì)算機(jī)中既要考慮查詢時(shí)間短，又要考慮節(jié)省空間也叫存儲(chǔ)結(jié)構(gòu)。每一個(gè)數(shù)據(jù)元素的存放形式及邏輯結(jié)構(gòu)機(jī)內(nèi)表示形式，元素的表示及元素間關(guān)系

最簡(jiǎn)單的辦法之一是建立一張表，每一本書的信息在表中占一行，如

有四種存儲(chǔ)方式：順序方式：數(shù)據(jù)元素邏輯上相連物理上也相連；鏈?zhǔn)酱鎯?chǔ)方式：數(shù)據(jù)元素邏輯上相連物理通過指針相連；索引存儲(chǔ)方式：數(shù)據(jù)元素通過索引表相連系；散列存儲(chǔ)方式：數(shù)據(jù)元素通過散列函數(shù)相連系；數(shù)據(jù)元素在計(jì)算機(jī)中的表示,又稱數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)（LogicalStructure）和數(shù)據(jù)的物理結(jié)構(gòu)（PhyicalStructure）。1.3算法的描述1.3.1算法算法是對(duì)某一特定問題求解步驟的一種描述。在計(jì)算機(jī)系統(tǒng)中，算法是由若干條指令組成的有窮序列，其中每一條指令表示計(jì)算機(jī)的一個(gè)或多個(gè)操作。算法具有以下5個(gè)性質(zhì):輸入:一個(gè)算法可以有0個(gè)或多個(gè)輸入量，在算法執(zhí)行之前提供給算法。輸出:一個(gè)算法的執(zhí)行結(jié)果要有一個(gè)或多個(gè)輸出量，它是算法對(duì)輸入數(shù)據(jù)處理的結(jié)果。有窮性:一個(gè)算法必須在執(zhí)行有窮步驟之后結(jié)束，并且每一步驟也都必須在有限的時(shí)間之內(nèi)完成。確定性:算法中的每一步驟都有明確的含義，沒有二義性。可行性:算法中描述的每一個(gè)操作，都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算，執(zhí)行有限次后來完成。1.3算法的描述1.3.2算法的設(shè)計(jì)要求一般來說，算法必須具有以下幾個(gè)方面的基本特征:（1）正確性正確性是設(shè)計(jì)一個(gè)算法的首要條件，所設(shè)計(jì)的算法要滿足具體問題的要求。在給算法輸入合理的數(shù)據(jù)后，能在有限的時(shí)間內(nèi)得出正確的結(jié)果。（2）可讀性算法是對(duì)特定問題求解步驟的一種描述，它要轉(zhuǎn)變成計(jì)算機(jī)可執(zhí)行的程序，同時(shí)必須可以供他人使用。為了閱讀與交流，所設(shè)計(jì)的算法要讓他人能看懂，在算法或程序中可以增加一些注釋來提高可讀性。（3）健壯性當(dāng)輸入的數(shù)據(jù)不符合要求時(shí)，算法應(yīng)能判斷出數(shù)據(jù)的非法性，并能進(jìn)行適當(dāng)?shù)奶幚?。比如，暫停或終止程序的執(zhí)行，顯示錯(cuò)誤信息等。不允許產(chǎn)生不可預(yù)料的結(jié)果。1.3算法的描述1.3.2算法的設(shè)計(jì)要求（4）高效性算法的效率是指算法執(zhí)行的時(shí)間和占用的存儲(chǔ)空間。如果對(duì)于同一個(gè)問題有多個(gè)算法可供選擇，應(yīng)盡可能選擇執(zhí)行時(shí)間短、占用空間少的算法。1.3.3算法的評(píng)價(jià)一個(gè)好的算法首先要具備正確性，然后是可讀性和健壯性。在具備了這三個(gè)條件后，就應(yīng)考慮算法的效率問題，即算法的時(shí)間效率和空間效率兩個(gè)方面。1.3.4算法的描述語言為了更好地表達(dá)算法的各個(gè)步驟，必須掌握對(duì)于算法的描述方法。1.3算法的描述1.3.3算法的評(píng)價(jià)（1）時(shí)間效率時(shí)間效率就是考慮一個(gè)算法運(yùn)行時(shí)所需時(shí)間的多少。上面這句話粗看起來似乎并無大錯(cuò)，但仔細(xì)分析其中卻包含三個(gè)嚴(yán)重問題：第一、算法只是對(duì)某一特定問題求解步驟的一種描述，算法在轉(zhuǎn)變成程序前是不能上機(jī)運(yùn)行的；第二、程序總是針對(duì)一定規(guī)模的問題的而運(yùn)行的，解決不同規(guī)模的問題所需要的時(shí)間沒有可比性；第三、即使是對(duì)同一規(guī)模的問題，運(yùn)行時(shí)間還與機(jī)器的配置和檔次有關(guān)。所以算法的運(yùn)行時(shí)間不能作為評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)。那么什么才能作為評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)呢？一般情況下，一個(gè)算法中會(huì)有很多個(gè)操作，其中必然有一或兩種操作被重復(fù)執(zhí)行，而且其重復(fù)執(zhí)行的次數(shù)基本上正比于問題的規(guī)模，這種操作就可以作為基本操作，而基本操作被重復(fù)執(zhí)行的次數(shù)與問題規(guī)模之間的函數(shù)關(guān)系，就可以作為評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)，這個(gè)標(biāo)準(zhǔn)就是所謂的算法的時(shí)間復(fù)雜度。

1.3算法的描述例1.6

求下列4個(gè)程序段的語句頻度（a） i++; x=0;（b）for（i=1;i<=n;i++）

x=x+1;（c）for（i=1;i<=n;i++）

for（j=1;j<=n;j++）

x=x+1;（d）for（i=1;i<=n;i++）

for（j=1;j<=n;j++）

for（k=1;k<=n;k++）

x=x+1;1.3算法的描述（a）是一個(gè)沒有循環(huán)算法的基本操作，它的語句頻度與問題規(guī)模沒有關(guān)系，記作T(n)=O(1)，也稱為常量階。（b）是一個(gè)一重循環(huán)的算法，它的語句頻度隨問題規(guī)模n的增大而呈線性增大，這種線性關(guān)系記作T(n)=O(n)，也稱線性階。（c）是一個(gè)二重循環(huán)的算法，它的語句頻度為n2，記作T(n)=O(n2)，稱為平方階。（d）是一個(gè)三重循環(huán)的算法，它的語句頻度為n3

，記作T(n)=O(n3)，稱為立方階。常見的時(shí)間復(fù)雜度還有對(duì)數(shù)階O(log2n)、O(nlog2n)，指數(shù)階O(2n)等。等式T(n)=O(n)的含義是，在n增大的過程中T(n)與n是同階的。這里T(n)是時(shí)間復(fù)雜度，其含義是算法中基本操作被重復(fù)執(zhí)行的次數(shù)。兩個(gè)變量是同階的其含義是，這兩個(gè)變量的比值始終是一個(gè)常數(shù)。例如，變量n與kn是同階的，這里k是任意的常數(shù)。1.3算法的描述（2）空間效率一個(gè)算法在執(zhí)行過程中所占用的存儲(chǔ)空間大小，稱為空間效率或空間復(fù)雜度。與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)臨時(shí)占用的存儲(chǔ)空間大小。算法的空間復(fù)雜度一般以數(shù)量級(jí)形式給出。提高算法空間復(fù)雜度的措施有原地工作和壓縮存儲(chǔ)。1.3.4算法的描述語言自然語言描述法流程圖描述法偽代碼描述法高級(jí)語言描述法素性判別素性判別就是給定一個(gè)正整數(shù)，判定其是否為素?cái)?shù)素?cái)?shù)的定義：一個(gè)大于1的整數(shù)，如果它的正因數(shù)只有1和它本身，就叫做素?cái)?shù)，否則就叫合數(shù)。如何判定給定正整數(shù)n是否為素?cái)?shù)呢？根據(jù)定義。從2開始找n的因子，若能找到一個(gè)介于2和n-1之間的n的因子，說明n不是素?cái)?shù)；否則，n是素?cái)?shù)。素性判別YNK←2K不能整除n?K←K+1輸出n是素?cái)?shù)

輸入n的值開始結(jié)束YNK等于n?輸出n不是素?cái)?shù)求最大公約數(shù)設(shè)有兩個(gè)正整數(shù)m和n，如何求其最大公約數(shù)？有多種方法，例如求解速度最快的方法是輾轉(zhuǎn)相除法。輾轉(zhuǎn)相除法(歐幾里得算法)：給定兩個(gè)正整數(shù)m和n，求它們的最大公約數(shù)(公因子)。步驟1:【求余數(shù)】以n除m并令r為所得余數(shù)(0≤r＜n)步驟2:【余數(shù)為0?】若r=0，算法結(jié)束；n即為答案步驟3:【互換】置m←n，n←r，轉(zhuǎn)向步驟1。求最大公約數(shù)流程圖YNr←m被n除的余數(shù)r不等于0?n←r輸出n的值輸入正整數(shù)m和n開始結(jié)束m←n結(jié)構(gòu)不好！這次課的主要內(nèi)容結(jié)構(gòu)化方法的基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)其他算法描述方法N-S盒圖方法偽代碼方法三種基本結(jié)構(gòu)三種基本結(jié)構(gòu)1966年，Bohra和Jacopini提出了以下三種基本結(jié)構(gòu)，作為構(gòu)造算法的基本單元順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)和選擇結(jié)構(gòu)的流程圖如下圖所示AB順序結(jié)構(gòu)abpAB成立不成立ab選擇結(jié)構(gòu)1pA成立不成立ab選擇結(jié)構(gòu)2三種基本結(jié)構(gòu)循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)(while型循環(huán)）如圖循環(huán)結(jié)構(gòu)1所示直到型循環(huán)結(jié)構(gòu)(Until型循環(huán))如圖循環(huán)結(jié)構(gòu)2所示pA成立不成立ab循環(huán)結(jié)構(gòu)2pA成立不成立ab循環(huán)結(jié)構(gòu)1基本結(jié)構(gòu)小結(jié)只有一個(gè)入口只有一個(gè)出口結(jié)構(gòu)中的每一部分都存在一條從入口到出口的路徑結(jié)構(gòu)內(nèi)不存在“死循環(huán)”AB死循環(huán)apAB成立不成立ab計(jì)算1+2+…+100的流程圖

YNI←1S←0I<=100?S←S+I輸出S的值開始結(jié)束I←I+1ABCABC判斷閏年的流程圖

k能被4整除？輸入一個(gè)年份值k開始結(jié)束輸出k不是閏年輸出k是閏年YNk能被100整除？Yk能被400整除？YNN輸出k是閏年輸出k不是閏年判斷閏年的流程圖

k能被4整除？輸入一個(gè)年份值k開始結(jié)束輸出k不是閏年YNk能被100整除？Yk能被400整除？YNN輸出k是閏年輸出k是閏年輸出k不是閏年ABCApBC成立不成立ab判斷閏年的流程圖

k能被4整除？輸入一個(gè)年份值k開始結(jié)束輸出k不是閏年輸出k是閏年YNk能被100整除？Yk能被400整除？YNN結(jié)構(gòu)不好！ABABab無法劃分基本單元！求最大公約數(shù)流程圖YNr←m被n除的余數(shù)r不等于0?n←r輸出n的值輸入正整數(shù)m和n開始結(jié)束m←n結(jié)構(gòu)不好！pA成立不成立ab循環(huán)結(jié)構(gòu)2pA成立不成立ab循環(huán)結(jié)構(gòu)1求最大公約數(shù)流程圖成立不成立abYNr不等于0?輸出n的值輸入正整數(shù)m和n開始結(jié)束m←n;n←rr←m被n除的余數(shù)r←m被n除的余數(shù)ABCDABCD求最大公約數(shù)流程圖YNr不等于0?輸出m的值輸入正整數(shù)m和n開始結(jié)束r←m被n除的余數(shù)m←n;n←rABCABC成立不成立流程圖的優(yōu)缺點(diǎn)優(yōu)點(diǎn)直觀形象，比較清楚地表現(xiàn)了各個(gè)框圖的邏輯關(guān)系缺點(diǎn)占用篇幅較多對(duì)流程線的使用沒有限制，允許隨意轉(zhuǎn)向可能造成流程混亂，理解困難其他算法描述方法用N-S盒圖表示算法用偽代碼描述算法用PAD圖描述算法(略)用計(jì)算機(jī)語言描述算法(程序)...用N-S盒圖描述算法N-S盒圖的基本符號(hào)AB順序結(jié)構(gòu)選擇結(jié)構(gòu)ABp成立不成立AB順序結(jié)構(gòu)ab流程圖符號(hào)pAB成立不成立ab選擇結(jié)構(gòu)用N-S盒圖描述算法N-S盒圖的基本符號(hào)流程圖符號(hào)A當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)p成立A直到型循環(huán)結(jié)構(gòu)直到p成立pA成立不成立ab循環(huán)結(jié)構(gòu)1pA成立不成立ab循環(huán)結(jié)構(gòu)2求最大公約數(shù)流程圖YNr不等于0?輸出n的值輸入正整數(shù)m和n開始結(jié)束m←n;n←rr←m被n除的余數(shù)r←m被n除的余數(shù)輸入正整數(shù)m和nr←m被n除的余數(shù)m←n;n←rr←m被n除的余數(shù)當(dāng)r不等于0輸出n的值N-S盒圖表示法小結(jié)與流程圖相比，N-S盒圖保留了流程圖方式直觀、形象和易于理解的優(yōu)點(diǎn)去掉了流程線，形式上更緊湊避免了流程的隨意跳轉(zhuǎn)，確保了結(jié)構(gòu)化技術(shù)用偽代碼表示算法規(guī)定一些基本符號(hào)運(yùn)算符號(hào)簡(jiǎn)單算術(shù)運(yùn)算符號(hào)：+、-、×、/、mod(整除取余)關(guān)系運(yùn)算符號(hào):＞、≥、＜、≤、＝、≠邏輯運(yùn)算符號(hào):and、or、not括號(hào):(、)用于表示某種對(duì)象名字的符號(hào)以英文字母開頭的字母、數(shù)字符號(hào)串例如：sum,price,i,m,k,n,a1,a2其他(處理、語句)賦值:←，例如i←1如果p成立則A否則B:ifpthenAelseB當(dāng)p成立時(shí)，則A:whilepdoAdoAwhilep輸入和輸出(打印)：input、print基本塊起、止符號(hào):{、}算法開始和結(jié)束：BEGIN、END偽代碼算法中基本符號(hào)的使用運(yùn)算符號(hào)（a←5；b←3）簡(jiǎn)單算術(shù)運(yùn)算符號(hào)：+、-、×、/、mod(整除取余)例如：a+b、a-b、a×b、a/b、amodb關(guān)系運(yùn)算符號(hào):＞、≥、＜、≤、＝、≠成立：true(Yes、Y)不成立：false(No、N)括號(hào):(、)偽代碼算法中基本符號(hào)的使用邏輯運(yùn)算邏輯運(yùn)算符號(hào):and、or、not并且：and或者：or非(不是)：not因此，給定一個(gè)年號(hào)k，判斷是否為閏年的條件是：((kmod4=0)and(kmod100≠0))or((kmod100=0)and(kmod400=0))例如，判斷閏年的條件(給定一個(gè)年號(hào)k)能被4整除，但是不能被100整除的年份是閏年(kmod4=0)and(kmod100≠0)能同時(shí)被100和400整除的年份是閏年(kmod100=0)and(kmod400=0)偽代碼算法中基本符號(hào)的使用選擇結(jié)構(gòu)如果p成立則A否則B:ifpthenAelseBpAB成立不成立ab選擇結(jié)構(gòu)例如ifa>bthenmax←aelsemax←b例如：

if((kmod4=0)and(kmod100≠0))or((kmod100=0)and(kmod400=0))thenprint“kisaleapyear.”elseprint“kisnotaleapyear.”偽代碼算法中基本符號(hào)的使用循環(huán)結(jié)構(gòu)當(dāng)p成立時(shí)，則A:whilepdoAYNI<=100?S←S+II←I+1pA成立不成立ab循環(huán)結(jié)構(gòu)1例如whilea>bdoa←a-b

whileI<=100do{S←S+I;I←I+1;}偽代碼描述計(jì)算1+2+…+100的算法算法1：計(jì)算1+2+…+100BEGINS←0;I←1;while(I≤100)do{S←S+I;I←I+1;}printS；ENDYNI←1S←0I<=100?S←S+I輸出S的值開始結(jié)束I←I+1偽代碼算法：求最大公約數(shù)YNr不等于0?輸出n的值輸入正整數(shù)m和n開始結(jié)束m←n;n←rr←m被n除的余數(shù)r←m被n除的余數(shù)算法2：輾轉(zhuǎn)相除法求最大公約數(shù)BEGINinputm,n;/*輸入正整數(shù)m和n*/r←mmodn;/*求m被n除的余數(shù)*/while(r≠0)do{m←n;n←r;r←mmodn;}printn；/*輸出最大公約數(shù)*/END偽代碼算法：求最大公約數(shù)算法3：輾轉(zhuǎn)相除法求最大公約數(shù)BEGINinputm,n;/*輸入正整數(shù)m和n*/do{r←mmodn;m←n;n←r;}whiler≠0;printm；/*輸出最大公約數(shù)*/ENDYNr不等于0?輸出m的值輸入正整數(shù)m和n開始結(jié)束r←m被n除的余數(shù)m←n;n←r偽代碼算法：素性判別Y

NK←2K不能整除n?K←K+1輸出n是素?cái)?shù)

輸入n的值開始結(jié)束YNK等于n?算法2：素性判別BEGINinputn;/*輸入正整數(shù)n*/k←2;while(nmodk≠0)do{k←k+1;}if(k=n)thenprint“n是素?cái)?shù)”

elseprint“n不是素?cái)?shù)”END輸出n不是素?cái)?shù)描述算法的程序語言3.描述算法的語言選擇

(1)預(yù)定義常量和類型。本書中用到以下常量符號(hào)，如True、False、MAXSIZE等，約定用如下宏定義預(yù)先定義：＃defineTRUE1

＃defineFALSE0

＃defineMAXSIZE100

＃defineOK1

＃defineERROR0

(2)本書中所有的算法都以如下的函數(shù)形式加以表示，其中的結(jié)構(gòu)類型使用前面已有的定義。［數(shù)據(jù)類型］函數(shù)名（［形式參數(shù)及說明］）

{內(nèi)部數(shù)據(jù)說明；執(zhí)行語句組；

}/*函數(shù)名*/

函數(shù)的定義主要由函數(shù)名和函數(shù)體組成，函數(shù)體用花括號(hào)“{”和“}”括起來。函數(shù)中用方括號(hào)括起來的部分如“［形式參數(shù)］”為可選項(xiàng)，函數(shù)名之后的圓括號(hào)不可省略。

(3)賦值語句。■簡(jiǎn)單賦值;

（1）〈變量名〉=〈表達(dá)式〉，它表示將表達(dá)式的值賦給左邊的變量；（2）〈變量〉++，它表示變量加1后賦值給變量；（3）〈變量〉--，它表示變量減1后賦值給變量?！龃?lián)賦值#;〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達(dá)式〉；■成組賦值#;

（〈變量1〉，〈變量2〉，〈變量3〉，…,〈變量k〉)=（〈表達(dá)式1〉，〈表達(dá)式2〉，〈表達(dá)式3〉，…,〈表達(dá)式k〉）；

〈數(shù)組名1〉［下標(biāo)1］［下標(biāo)2］=〈數(shù)組名2〉［下標(biāo)1］［下標(biāo)2］；■

條件賦值;〈變量名〉=〈條件表達(dá)式〉？〈表達(dá)式1〉:〈表達(dá)式2〉；

(4)條件選擇語句?！鰅f（〈表達(dá)式〉）語句；■if（〈表達(dá)式〉）語句1；

else語句2；switch(<表達(dá)式>）

{case判斷值1:

語句組1；

break;case判斷值2:

語句組2；

break;...case判斷值n:

語句組n;break;

［d