第1章緒論第1章緒論1.1數(shù)據(jù)結(jié)構(gòu)概述1.2數(shù)據(jù)的邏輯結(jié)構(gòu)

1.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)1.4算法和算法的效率1.5實(shí)驗(yàn)預(yù)備知識(shí) 2重難點(diǎn)數(shù)據(jù)結(jié)構(gòu)中的常用基本概念和術(shù)語

四種邏輯結(jié)構(gòu)及其描述四種存儲(chǔ)結(jié)構(gòu)，及其與算法的關(guān)系算法的描述和復(fù)雜度分析算法時(shí)間和空間復(fù)雜度的計(jì)算方法C++中的引用變量和引用參數(shù)C語言復(fù)習(xí)：指針、結(jié)構(gòu)體、文件、數(shù)字菜單31.1數(shù)據(jù)結(jié)構(gòu)概述1.1.1數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)

——特指數(shù)據(jù)元素，現(xiàn)實(shí)世界中存在的一個(gè)獨(dú)立個(gè)體的相關(guān)信息(結(jié)構(gòu)體變量、對(duì)象、記錄)，也稱之為結(jié)點(diǎn)。結(jié)構(gòu)

——數(shù)據(jù)元素之間存在的關(guān)系。邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。存儲(chǔ)結(jié)構(gòu)：也稱物理結(jié)構(gòu)，指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)。算法

——解決問題方法(步驟)的描述。4數(shù)據(jù)結(jié)構(gòu)＝數(shù)據(jù)＋(邏輯、存儲(chǔ))結(jié)構(gòu)＋少量算法1.1.1數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容所謂數(shù)據(jù)元素，就是C語言中的結(jié)構(gòu)體變量例如：書籍元素——Book結(jié)構(gòu)體類型可以根據(jù)需要，在Book結(jié)構(gòu)體中增加出版社、出版年份、版本號(hào)和印數(shù)等成員。5typedef

struct{

charisbn[16];

chartitle[32];

charauthor[16];

intpages;

doubleprice;}Book;數(shù)據(jù)項(xiàng)1.1.1數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容所謂數(shù)據(jù)元素，就是C語言中的結(jié)構(gòu)體變量例如：學(xué)生元素——Student結(jié)構(gòu)體類型可以根據(jù)需要，將成員score定義為數(shù)組，以便存儲(chǔ)多門課程的成績(jī)；還可以將成員age改名為birthday，將其定義為日期類型等。6typedef

struct{

charstuId[16];

charname[16];

chargender;

intage;

doublescore;}Student;數(shù)據(jù)項(xiàng)1.1.2典型數(shù)據(jù)結(jié)構(gòu)舉例用計(jì)算機(jī)解決具體實(shí)際問題的步驟：(1)從問題抽象出適當(dāng)?shù)臄?shù)學(xué)模型(對(duì)象、關(guān)系)；(2)分析邏輯結(jié)構(gòu)(提取數(shù)據(jù)元素、建立邏輯關(guān)系)(3)根據(jù)邏輯結(jié)構(gòu)的主要操作，確定存儲(chǔ)結(jié)構(gòu)(4)基于選定的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)求解數(shù)學(xué)模型的算法(解決問題的方法)；(5)編寫程序、運(yùn)行并調(diào)試，直到解決問題。71.1.2典型數(shù)據(jù)結(jié)構(gòu)舉例數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的選擇，依賴于邏輯結(jié)構(gòu)；算法的設(shè)計(jì)，必須基于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；例如：81.1.2典型數(shù)據(jù)結(jié)構(gòu)舉例——線性結(jié)構(gòu)【例1-1】學(xué)生入學(xué)情況登記表91.1.2典型數(shù)據(jù)結(jié)構(gòu)舉例——樹形結(jié)構(gòu)【例1-2】井字棋對(duì)弈問題10七橋問題1.1.2典型數(shù)據(jù)結(jié)構(gòu)舉例——圖形結(jié)構(gòu)【例1-3】七橋問題11歐拉回路1.2數(shù)據(jù)的邏輯結(jié)構(gòu)——四種集合結(jié)構(gòu)樹形結(jié)構(gòu)(一對(duì)多)12線性結(jié)構(gòu)(一對(duì)一)圖形結(jié)構(gòu)(多對(duì)多)ABCDEF沒有前驅(qū)，有且僅有一個(gè)后繼。沒有后繼，有且僅有一個(gè)前驅(qū)。ABECDFGRABCDEGHFIJK一個(gè)雙親，多個(gè)孩子。邊為鄰接關(guān)系1.2數(shù)據(jù)的邏輯結(jié)構(gòu)——四種(1)集合結(jié)構(gòu)數(shù)據(jù)元素之間，除了“同屬于一個(gè)集合”的關(guān)系外，別無其它關(guān)系。(2)線性結(jié)構(gòu)(線性表、棧、隊(duì)列、串)數(shù)據(jù)元素之間，存在著“一對(duì)一”的關(guān)系。(3)樹形結(jié)構(gòu)(樹、二叉樹)數(shù)據(jù)元素之間，存在著“一對(duì)多”的關(guān)系。(4)圖形結(jié)構(gòu)(圖、網(wǎng))數(shù)據(jù)元素之間，存在著“多對(duì)多”的關(guān)系。131.2.1基本概念數(shù)據(jù)(Data)數(shù)據(jù)是信息的載體，是對(duì)客觀事物的符號(hào)表示。通俗的說，凡是能被計(jì)算機(jī)識(shí)別、存取和處理的符號(hào)、圖形、圖像、聲音、視頻信號(hào)等都可以稱之為數(shù)據(jù)。數(shù)據(jù)元素(DataElement)數(shù)據(jù)元素是對(duì)現(xiàn)實(shí)世界中，某個(gè)獨(dú)立個(gè)體的數(shù)據(jù)描述，是數(shù)據(jù)的基本單位。數(shù)據(jù)元素俗稱為結(jié)點(diǎn)(Node)，也稱其為記錄(record)，在計(jì)算機(jī)中常作為一個(gè)整體來處理。141.2.1基本概念數(shù)據(jù)項(xiàng)(DataItem)數(shù)據(jù)項(xiàng)是不可分割的、具有獨(dú)立意義的最小數(shù)據(jù)單位，是對(duì)數(shù)據(jù)元素屬性的描述。數(shù)據(jù)項(xiàng)也稱為域，或字段(Field)。數(shù)據(jù)對(duì)象(DataObject)

數(shù)據(jù)對(duì)象是相同數(shù)據(jù)元素的集合；例如：在“學(xué)生入學(xué)情況登記表”中，數(shù)據(jù)對(duì)象是全體學(xué)生記錄(數(shù)據(jù)元素)的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)(DataStructure)相互之間存在特定關(guān)系的數(shù)據(jù)元素的集合。151.2.1基本概念直接前驅(qū)每個(gè)數(shù)據(jù)元素的前面，緊挨著它的那個(gè)元素，稱為它的直接前驅(qū)，可簡(jiǎn)稱為前驅(qū)(precursor)。直接后繼每個(gè)數(shù)據(jù)元素的后面，緊挨著它的那個(gè)元素，稱為它的直接后繼，可簡(jiǎn)稱為后繼(next)。線性結(jié)構(gòu)中，第一條記錄沒有直接前驅(qū)，稱為開始結(jié)點(diǎn)；最后一條記錄沒有直接后繼，稱為終端結(jié)點(diǎn)。16ABCDEF開始結(jié)點(diǎn)終端結(jié)點(diǎn)1.2.2邏輯結(jié)構(gòu)的描述數(shù)據(jù)元素之間的邏輯關(guān)系，稱為邏輯結(jié)構(gòu)。邏輯結(jié)構(gòu)可以用二元組來表示G=(D,R)其中：D是數(shù)據(jù)元素的集合；R是D上所有數(shù)據(jù)元素之間關(guān)系的集合。一種數(shù)據(jù)結(jié)構(gòu)Line=(D,R)其中:D={01,02,03,04,05,06,07,08,09,10}R={<05,01>,<01,03>,<03,08>,<08,02>,<02,07>, <07,04>,<04,06>,<06,09>,<09,10>}17050103080207040609101.2.2邏輯結(jié)構(gòu)的描述一種數(shù)據(jù)結(jié)構(gòu)Tree=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10}R={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>, <02,07>,<03,08>,<03,09>,<04,10>}18010208030706050409101.2.2邏輯結(jié)構(gòu)的描述一種數(shù)據(jù)結(jié)構(gòu)Graph=(D,R)，其中：D={a,b,c,d,e}R={(a,b),(a,d),(b,d),(b,c),(b,e),(c,d),(d,e)}圓括號(hào)表示無向邊(雙向)，尖括號(hào)表示有向邊。19badce1.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)——四種數(shù)據(jù)元素及它們之間的關(guān)系，在計(jì)算機(jī)存儲(chǔ)器中的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有四種:(1)順序存儲(chǔ)順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，是借助元素在存儲(chǔ)器中的相對(duì)位置，來表示數(shù)據(jù)元素之間的邏輯關(guān)系。(2)鏈?zhǔn)酱鎯?chǔ)借助指示元素存儲(chǔ)地址的指針(Pointer)，來表示數(shù)據(jù)元素之間的邏輯關(guān)系。201.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)——四種(3)索引存儲(chǔ)索引存儲(chǔ)是在原有存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上，建立一個(gè)索引表，索引表中的每一項(xiàng)都由關(guān)鍵字和地址組成。索引表的主要作用是為了提高數(shù)據(jù)的檢索速度。漢語字典的組織方式，就是典型的索引存儲(chǔ)。(4)散列存儲(chǔ)(哈希存儲(chǔ))通過構(gòu)造散列(Hash，哈希)函數(shù)的方式，由數(shù)據(jù)元素的關(guān)鍵字計(jì)算確定其存儲(chǔ)或查找地址的方式，稱為散列存儲(chǔ)。211.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)——四種(1)順序存儲(chǔ)——數(shù)組優(yōu)點(diǎn)：可以隨機(jī)訪問(或存取)指定元素；缺點(diǎn)：插入或刪除需移動(dòng)大批元素，效率很低。(2)鏈?zhǔn)酱鎯?chǔ)——鏈表優(yōu)點(diǎn)：插入或刪除非常方便；缺點(diǎn)：所有元素只能順序訪問。(3)索引存儲(chǔ)——類似漢語字典的組織方式查找效率高，但是需要構(gòu)造并維護(hù)索引表。(4)散列/哈希存儲(chǔ)——哈希表效率取決于哈希函數(shù)，數(shù)據(jù)元素可能發(fā)生碰撞。221.4算法和算法的效率算法(Algorithm)算法就是方法(method)，是對(duì)特定問題求解步驟的描述，是指令的有限序列。其中每一條指令(或語句)，表示一個(gè)或多個(gè)操作。算法的特性有窮性：有限步數(shù)，且每步在有限時(shí)間內(nèi)完成確定性：每條指令必須有確切的定義，無二義性可行性：可以通過有限次運(yùn)算實(shí)現(xiàn)，得到正確結(jié)果輸入：有0個(gè)或多個(gè)輸入輸出：有1個(gè)或多個(gè)輸出231.4算法和算法的效率程序、算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系一個(gè)算法必須在有窮步之后結(jié)束；一個(gè)程序不一定滿足有窮性(例如：死循環(huán))。程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令無此限制。算法代表了對(duì)問題的求解過程，而程序則是算法在計(jì)算機(jī)上的實(shí)現(xiàn)；算法用特定的程序設(shè)計(jì)語言來描述，就成了程序。算法與數(shù)據(jù)結(jié)構(gòu)是相輔相承的。241.4算法和算法的效率一個(gè)好算法應(yīng)達(dá)到的目標(biāo)正確性：算法應(yīng)能滿足設(shè)定的功能和要求。可讀性：思路清晰、層次分明、易讀易懂。健壯性：輸入非法數(shù)據(jù)時(shí)，算法應(yīng)能有適當(dāng)?shù)姆磻?yīng)和處理。健壯性也稱為魯棒性(robust)。高效性：解決同一問題時(shí)，所花的時(shí)間越短，算法的效率就越高。低存儲(chǔ)量：完成同一功能，算法占用的存儲(chǔ)空間應(yīng)盡可能少。好算法的首要目標(biāo)——高效性251.4算法和算法的效率算法效率的兩種度量方法事后統(tǒng)計(jì)法必須先運(yùn)行按照算法編寫的程序。運(yùn)行時(shí)間的統(tǒng)計(jì)依賴于計(jì)算機(jī)硬件和軟件的環(huán)境，容易掩蓋算法本身的優(yōu)劣。事先估算法使用何種程序設(shè)計(jì)語言；采取怎樣的算法策略；算法涉及的問題規(guī)模；編譯程序產(chǎn)生的目標(biāo)代碼的質(zhì)量；機(jī)器執(zhí)行指令的速度。算法效率的評(píng)價(jià)——通常只考慮算法策略261.4算法和算法的效率算法效率的評(píng)價(jià)指標(biāo)時(shí)間復(fù)雜度——隨問題規(guī)模的增大，算法所需運(yùn)行時(shí)間增長(zhǎng)的函數(shù)；空間復(fù)雜度——隨問題規(guī)模的增大，算法運(yùn)行時(shí)所占存儲(chǔ)空間增長(zhǎng)的函數(shù)；重點(diǎn)是時(shí)間復(fù)雜度，因此有時(shí)會(huì)用空間換時(shí)間。271.4算法和算法的效率時(shí)間復(fù)雜度(TimeComplexity)把算法中所需執(zhí)行的簡(jiǎn)單操作的次數(shù)T(n)

，稱作算法的時(shí)間復(fù)雜度。沒有必要精確計(jì)算算法的執(zhí)行時(shí)間(即語句條數(shù))，只要大致算出T(n)的數(shù)量級(jí)(Order)即可。若函數(shù)f(n)和T(n)同階，則將算法時(shí)間多項(xiàng)式T(n)的數(shù)量級(jí)記為O(f(n))，通?？捎涀鳎篢(n)=O(f(n))它表示隨著問題規(guī)模n的增長(zhǎng)，執(zhí)行時(shí)間T(n)的增長(zhǎng)率和函數(shù)f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。281.4算法和算法的效率

291.4算法和算法的效率【例1-8】交換變量a和b的值的另一種方法。方法②：a=a+b;b=a-b;a=a-b;方法②的策略，從細(xì)節(jié)上看，是典型的用時(shí)間換空間，通過多做加減運(yùn)算的耗時(shí)，少用了臨時(shí)變量t。30時(shí)間空間時(shí)間復(fù)雜度和空間復(fù)雜度，往往無法同時(shí)達(dá)到最優(yōu)，更多的時(shí)候需要去權(quán)衡，去找到一個(gè)平衡！1.4算法和算法的效率

31T(n)的同階無窮小只要為常數(shù)即可1.4算法和算法的效率對(duì)于足夠大的n，常用的時(shí)間復(fù)雜度關(guān)系如下:32O(1)<O(lgn)<O(n)<O(nlgn)<O(n2)<(n3)<……<O(2n)對(duì)數(shù)階線性階線性對(duì)數(shù)階冪次階指數(shù)階常量階(平行于橫軸)問題規(guī)模需要執(zhí)行的語句條數(shù)1.4算法和算法的效率空間復(fù)雜度(SpaceComplexity)，是指程序從開始運(yùn)行，到運(yùn)行結(jié)束，所需存儲(chǔ)空間的大小。類似于時(shí)間復(fù)雜度，算法所需存儲(chǔ)空間的量，通常記作：S(n)=O(f(n))其中n為問題規(guī)模；如果所需的輔助空間與問題規(guī)模無關(guān)，則空間復(fù)雜度記為O(1)。程序執(zhí)行時(shí)，除了需要存儲(chǔ)空間來存放本身所用的指令、常數(shù)、變量和輸入數(shù)據(jù)以外，進(jìn)行操作時(shí)，可能還需要一些必要的輔助空間。進(jìn)行空間復(fù)雜度分析時(shí)，若所需空間的大小依賴于特定的輸入，一般都按最壞的情況(峰值)來分析。331.5實(shí)驗(yàn)預(yù)備知識(shí)C++中的引用變量34#include<stdio.h>intmain(){

inta=3,b=5;

intm=a,&n=b;printf("a=%3d,m=%3d,b=%3d,n=%3d\n",a,m,b,n);a=33,b=55;printf("a=%3d,m=%3d,b=%3d,n=%3d\n",a,m,b,n);m=333,n=555;printf("a=%3d,m=%3d,b=%3d,n=%3d\n",a,m,b,n);

return

0;}運(yùn)行結(jié)果如下：a=3,m=3,b=5,n=5a=33,m=3,b=55,n=55a=33,m=333,b=555,n=555a和m的值不會(huì)同步變化；b和n的值會(huì)同步變化。1.5實(shí)驗(yàn)預(yù)備知識(shí)C++中的引用參數(shù)35voidswapByValue(inta,intb){

inttmp=a;a=b;b=tmp;}voidswapByPoint(int

*a,int

*b){

inttmp=*a;*a=*b;*b=tmp;}voidswapByRef(int

&a,int

&b){

inttmp=a;a=b;b=tmp;}intmain(){

intx=6,y=8;printf("x=%d,y=%d\n",x,y);swapByPoint(&x,&y);printf("x=%d,y=%d\n",x,y);swapByRef(x,y);printf("x=%d,y=%d\n",x,y);swapByValue(x,y);printf("x=%d,y=%d\n",x,y);

return

0;}運(yùn)行結(jié)果如下：x=6,y=8x=8,y=6x=6,y=8x=6,y=81.5實(shí)驗(yàn)預(yù)備知識(shí)使用引用變量的時(shí)候，需要注意如下幾點(diǎn)：C++中不存在空引用。引用變量在聲明的時(shí)候，就必須初始化，不能先聲明再賦值。也就是說，引用變量在聲明時(shí)就必須指定，它引用的是哪個(gè)變量。引用變量一旦被初始化，就不能再引用其他變量。給引用變量無論是賦值還是傳參，都不能用常量，也就是說引用變量只能引用其他變量的內(nèi)存空間。使用引用變量后源文件的后綴名必須用.cpp(CPlusPlus的簡(jiǎn)稱，C++源文件的后綴名)，不要用.c，否則編譯器將無法識(shí)別。361.5實(shí)驗(yàn)預(yù)備知識(shí)中文亂碼的問題中文字符的常用編碼GB（GuoBiao的拼音，國標(biāo)碼）系列編碼Unicode系列編碼（統(tǒng)一字符編碼）中文字符可能出現(xiàn)的位置源代碼文件（后綴為.c或.cpp）讀寫的數(shù)據(jù)文件（文本文件、二進(jìn)制文件中的字符串）輸入輸出控制臺(tái)亂碼產(chǎn)生的原因不同位置的中文字符，采用了不一致的編碼；不同的文本文件，有些可能有BOM（ByteOrderMark）頭，部分系統(tǒng)或函數(shù)無法自動(dòng)識(shí)別該文件頭。371.5實(shí)驗(yàn)預(yù)備知識(shí)中文亂碼的解決方案所有字符均采用UTF-8編碼，并且文本文件的格式統(tǒng)一采用無BOM頭的文件格式。用system("chcp65001");語句設(shè)置控制臺(tái)的字符編碼為UTF-8。學(xué)會(huì)使用UltraEdit、Notepad++或EditPlus等軟件查看文本文件的BOM頭，分析二進(jìn)制文件的格式。學(xué)會(huì)使用記事本、UltraEdit、Notepad++或EditPlus等軟件對(duì)文本文件做簡(jiǎn)單的編碼轉(zhuǎn)換。對(duì)編譯器在編譯和鏈接過程中的編碼進(jìn)行設(shè)置。381.5實(shí)驗(yàn)預(yù)備知識(shí)1.5.3不安全的C語言函數(shù)VisualStudio編程環(huán)境中提示使用了不安全函數(shù)的編譯警告或錯(cuò)誤，有些并不是源程序的錯(cuò)誤，而是由于C語言的歷史原因。常見的解決方案有如下兩種：（1）在每個(gè)源文件的最開頭添加如下宏定義（只會(huì)在該文件里起作用）#define_CRT_SECURE_NO_WARNINGS（2）項(xiàng)目屬性里，依次選擇：屬性->配置屬性->C/C++->預(yù)處理器->預(yù)處理器定義->編輯，在最下面的框中輸入如下這行（此時(shí)不需要#define）_CRT_SECURE_NO_WARNINGS391.5實(shí)驗(yàn)預(yù)備知識(shí)1.5.4獲取數(shù)據(jù)元素并設(shè)置菜單數(shù)據(jù)結(jié)構(gòu)中，經(jīng)常涉及批量數(shù)據(jù)的操作，需要熟練掌握C語言中文件的讀寫，避免調(diào)試程序時(shí)反復(fù)的從鍵盤重復(fù)輸入數(shù)據(jù)。經(jīng)常要根據(jù)需求，選擇執(zhí)行特定的功能函數(shù)，因此所有功能應(yīng)以數(shù)字菜單的形式列出。實(shí)驗(yàn)程序中可能涉及大量數(shù)據(jù)的連續(xù)輸入，應(yīng)適時(shí)清空內(nèi)存的輸入緩沖區(qū)。Windows系統(tǒng)中，可以用fflush(stdin);語句如果要求具備可移植性，一般采用如下循環(huán)結(jié)構(gòu)while((c=getchar())!='\n'&&c!=EOF);40這一對(duì)小括號(hào)千萬不要漏。End第2章線性表第2章線性表2.1線性表的定義與操作2.1.1線性表的定義2.1.2線性表的基本操作2.2線性表的順序存儲(chǔ)2.2.1順序表的定義和初始化2.2.2順序表的基本操作2.3線性表的鏈?zhǔn)酱鎯?chǔ)2.3.1單向鏈表的結(jié)構(gòu)2.3.2單鏈表的基本操作2.3.3循環(huán)鏈表2.3.4雙向鏈表43重難點(diǎn)順序表的多種定義和初始化方式單鏈表的定義、初始化和相關(guān)操作給鏈表添加頭結(jié)點(diǎn)的目的循環(huán)鏈表的基本操作雙向鏈表插入、刪除操作442.1.1線性表的定義

45沒有前驅(qū)，有且僅有一個(gè)后繼。沒有后繼，有且僅有一個(gè)前驅(qū)。2.1.1線性表的定義——邏輯結(jié)構(gòu)

ABCDEF462.1.2線性表的基本操作線性表上的基本操作有：創(chuàng)建線性表：createList()求表的長(zhǎng)度：intgetListLength(L)按值查找：searchList(L,x)，x是給定的待查找數(shù)據(jù)元素或其屬性（數(shù)據(jù)項(xiàng)的值）。插入操作：insertElem(&L,i,x)刪除操作：deleteElem(&L,i,&x)顯示操作：showList(L)472.2線性表的順序存儲(chǔ)——順序表2.2.1順序表的定義和初始化順序表的定義及特點(diǎn)用一組地址連續(xù)的存儲(chǔ)單元（就是數(shù)組），依次存儲(chǔ)線性表中的數(shù)據(jù)元素，這種存儲(chǔ)形式的線性表就稱為順序表。在順序表中所有數(shù)據(jù)元素的物理/存儲(chǔ)順序和邏輯順序是一致的；因此數(shù)據(jù)元素之間的關(guān)系可以隱含，無需存儲(chǔ)。順序表的優(yōu)點(diǎn)：可以隨機(jī)存取——知道數(shù)組名data

和下標(biāo)i，即可直接訪問data數(shù)組的i

號(hào)單元，比如data[i]。482.2線性表的順序存儲(chǔ)——順序表

492.2線性表的順序存儲(chǔ)——順序表2.2.1順序表的定義和初始化502.2線性表的順序存儲(chǔ)——順序表2.2.1順序表的定義和初始化——方法①和②512.2線性表的順序存儲(chǔ)——順序表2.2.1順序表的定義和初始化——方法①52#defineN40typedef

struct{

DataTypedata[N];

int

last;}SeqList;//定義順序表類型SeqListvoidinit(SeqList&list)//list為引用參數(shù){list.last=-1;

}intmain(){SeqListseqList;//seqList為局部變量，存放于棧內(nèi)存區(qū)init(seqList);//初始化順序表seqList為空////后續(xù)操作

return

0;}偽代碼2-12.2線性表的順序存儲(chǔ)——順序表2.2.1順序表的定義和初始化——方法②53#include<stdlib.h>#defineN40typedef

struct{

ElemTypedata[N];

int

length;}SeqList;//定義順序表類型SeqListvoidinit(SeqList*&pList)//pList為SeqList*類型的引用{pList=(SeqList*)malloc(sizeof(SeqList));pList->length=0;//將表的長(zhǎng)度設(shè)為0，表示表為空}intmain(){SeqList*pSeqList;//定義一個(gè)指向順序表的指針變量

init(pSeqList);////后續(xù)操作

return

0;}偽代碼2-22.2線性表的順序存儲(chǔ)——順序表方法①——適用于順序表空間較小的情況SeqListseqList;//seqList必須定義在main函數(shù)中，程序運(yùn)行時(shí)seqList的空間位于棧內(nèi)存區(qū)缺點(diǎn)：若其中data數(shù)組過大，則會(huì)引起棧內(nèi)存溢出方法②——推薦

SeqList*pSeqList;//指向順序表的指針變量?jī)?yōu)點(diǎn)：pSeqList為指針變量，只占用4個(gè)字節(jié)；malloc函數(shù)開辟的順序表空間位于堆內(nèi)存區(qū)。缺點(diǎn)：其中data數(shù)組的大小固定為N個(gè)單元，若表中元素達(dá)到N個(gè)，則無法繼續(xù)插入新的數(shù)據(jù)元素。542.2線性表的順序存儲(chǔ)——順序表2.2.1順序表的定義和初始化——方法③552.2線性表的順序存儲(chǔ)——順序表2.2.1順序表的定義和初始化——方法③56#include<stdlib.h>#defineN40typedef

struct{ElemType*pData;//動(dòng)態(tài)數(shù)組的起始地址，單元可以擴(kuò)充

int

listSize;//pData所指空間中數(shù)組單元的個(gè)數(shù)

int

length;//表中元素的個(gè)數(shù)（小于單元個(gè)數(shù)）}SeqList;voidinit(SeqList&list)//list為seqList的引用{//給順序表seqList的pData開辟N個(gè)單元的初始空間list.pData=(ElemType*)malloc(N*sizeof(ElemType));list.listSize=N;//記錄順序表中數(shù)組單元的個(gè)數(shù)為Nlist.length=0;//將順序表的長(zhǎng)度設(shè)置為0，表示表為空}偽代碼2-32.2線性表的順序存儲(chǔ)——順序表2.2.1順序表的定義和初始化——方法③57intmain(){SeqListseqList;//定義一個(gè)順序表seqListinit(seqList);////后續(xù)操作

return

0;}偽代碼2-3seqList.pdata所指空間為動(dòng)態(tài)分配，空間不夠時(shí)可以擴(kuò)充！方法③適用于：順序表中的元素個(gè)數(shù)可能存在很大變動(dòng)，不易或無法估算最多元素個(gè)數(shù)的情況。2.2線性表的順序存儲(chǔ)——順序表2.2.2順序表的基本操作插入——在順序表的第i個(gè)位置，插入元素x58

2.2線性表的順序存儲(chǔ)——順序表

592.2線性表的順序存儲(chǔ)——順序表

602.2線性表的順序存儲(chǔ)——順序表2.2.2順序表的基本操作刪除——將表中第i個(gè)元素從表中去掉61

2.2線性表的順序存儲(chǔ)——順序表

622.2線性表的順序存儲(chǔ)——順序表

632.2線性表的順序存儲(chǔ)——順序表2.2.2順序表的基本操作查找——在表中查找與給定值x相等的數(shù)據(jù)元素偽代碼2-6按年齡查找順序表中的指定學(xué)生64int

locateByAge(SeqList*pList,int

age){

inti=0;

while(i<pList->length&&

pList->data[i].age!=age)i++;

if(i>=pList->length)

return-1;//定位失敗

else

returni;//定位成功，返回存儲(chǔ)單元的下標(biāo)}2.2線性表的順序存儲(chǔ)——順序表2.2.2順序表的基本操作查找——在表中查找與給定值x相等的數(shù)據(jù)元素偽代碼2-7按學(xué)號(hào)查找順序表中的指定學(xué)生65int

locateByStuId(SeqList*pList,char

stuId[]){

inti=0;

while(i<pList->length&&

strcmp(pList->data[i].stuId,stuId)!=0)i++;

if(i>=pList->length)

return-1;//定位失敗

else

returni;//定位成功，返回存儲(chǔ)單元的下標(biāo)}2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表單鏈表LinkedList類型的定義形式將存儲(chǔ)一個(gè)數(shù)據(jù)元素的變量data，和指示下一個(gè)元素位置的指針變量next，封裝成結(jié)構(gòu)體LinkedList，作為結(jié)點(diǎn)的類型。662.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表2.3.1單向鏈表的結(jié)構(gòu)67

2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表2.3.1單向鏈表的結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中不要求各結(jié)點(diǎn)的內(nèi)存地址連續(xù)；即，鏈表中各元素的物理/存儲(chǔ)順序和邏輯順序很可能不一致。在每個(gè)結(jié)點(diǎn)內(nèi)部，均用指針成員保存下一個(gè)結(jié)點(diǎn)的地址。68單鏈表的存取必須從頭指針(變量)開始。2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表

69頭結(jié)點(diǎn)頭指針數(shù)據(jù)結(jié)點(diǎn)2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表無頭結(jié)點(diǎn)單鏈表的定義和初始化70偽代碼2-8typedef

struct_LinkNode{

ElemTypedata;

//數(shù)據(jù)域

struct_LinkNode*next;//指針域}LinkNode,*LinkList;

//定義結(jié)點(diǎn)類型LinkNode

//和結(jié)點(diǎn)指針類型LinkListintmain(){

LinkNode*head;//定義頭指針變量head

head=NULL;

//設(shè)置無頭結(jié)點(diǎn)的單鏈表為空表

////在此進(jìn)行后續(xù)的插入和刪除等操作

return

0;}LinkListhead和LinkNode

*head，都是定義頭指針變量head；當(dāng)head的值為NULL時(shí)，表示鏈表為空；否則head的值應(yīng)為第一個(gè)結(jié)點(diǎn)的地址。2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表2.3.2單鏈表的基本操作從表頭插入結(jié)點(diǎn)建立單鏈表71從單鏈表的表頭依次插入線性表(25,45,18,66,24)中的元素，建立單鏈表存儲(chǔ)結(jié)構(gòu)的過程2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表2.3.2單鏈表的基本操作從表尾插入結(jié)點(diǎn)建立單鏈表72尾指針(變量)從單鏈表的表尾依次插入線性表(25,45,18,66,24)中的元素，建立單鏈表存儲(chǔ)結(jié)構(gòu)的過程2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表2.3.2單鏈表的基本操作在單鏈表的中間某個(gè)位置插入一個(gè)新結(jié)點(diǎn)73尾指針(變量)從單鏈表的中間插入結(jié)點(diǎn)時(shí)，必須先找到插入位置的直接前驅(qū)，否則無法插入。2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表插入元素x到單鏈表的第i個(gè)位置，i≥1程序2-1無頭結(jié)點(diǎn)單鏈表的Line51~9074//intinsert(LinkList&h,inti,Studentx)intinsert(LinkNode*&h,inti,Studentx){

LinkNode*pNew,*p=h;

intj=2;

if(i==1)

//如果要在單鏈表的最前面插入

{

//給待插入的新結(jié)點(diǎn)開辟空間

pNew=(LinkNode*)malloc(sizeof(LinkNode));

pNew->data=x;//構(gòu)造新結(jié)點(diǎn)

pNew->next=h;//設(shè)置新結(jié)點(diǎn)的指針域

h=pNew;

//頭指針指向新結(jié)點(diǎn)

return

1;

//插入成功

}

75

//p應(yīng)指向新結(jié)點(diǎn)的直接前驅(qū)

//如果i==2，指針p不用后移，因此j的初始值為2

while(p!=NULL&&j<i)

//尋找插入位置i

{

j++;

p=p->next;//指針p后移，使其指向下一個(gè)結(jié)點(diǎn)

}

if(p!=NULL)

{

//給待插入的新結(jié)點(diǎn)開辟空間

pNew=(LinkNode*)malloc(sizeof(LinkNode));

pNew->data=x;//構(gòu)造結(jié)點(diǎn)

pNew->next=p->next;

//將結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后

p->next=pNew;

return

1;//插入成功

}

else

{

printf("插入位置不合法!\n");

return

0;//插入失敗

}}2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表有頭結(jié)點(diǎn)單鏈表的定義和初始化76typedef

struct_LinkNode{

ElemTypedata;

//數(shù)據(jù)域

struct_LinkNode*next;//指針域}LinkNode,*LinkList;

//定義結(jié)點(diǎn)類型LinkNodeintmain(){

LinkNode*head;//定義頭指針變量head

//給頭結(jié)點(diǎn)開辟空間

head=(LinkNode*)malloc(sizeof(LinkNode));

//設(shè)置有頭結(jié)點(diǎn)的單鏈表為空表，即頭結(jié)點(diǎn)的指針域?yàn)榭?/p>

head->next=NULL;

////后續(xù)的查找、插入和刪除等操作

return

0;}偽代碼2-92.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表有頭結(jié)點(diǎn)的單鏈表，和無頭結(jié)點(diǎn)時(shí)的比較有頭結(jié)點(diǎn)單鏈表的插入、刪除、查找、求表長(zhǎng)、輸出等基本操作，雖然與無頭結(jié)點(diǎn)單鏈表的基本操作大體一致，但在細(xì)節(jié)上會(huì)有些差異?；静僮髦胁糠衷葹閔ead

的地方，需要將其改為head->next772.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表以刪除操作為例，比較有無頭結(jié)點(diǎn)時(shí)的差異假設(shè)指針變量p已指向單鏈表中的待刪除結(jié)點(diǎn)，則刪除*p的操作如下78從單鏈表的中間刪除結(jié)點(diǎn)時(shí)，必須先找到刪除位置的直接前驅(qū)(*pre)，否則無法刪除。2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表偽代碼2-10無頭結(jié)點(diǎn)單鏈表的刪除操作79//刪除學(xué)號(hào)為stuId的元素intdel(LinkNode*&h,charstuId[]){

LinkNode*pre,*p;

if(h==NULL)//如果單鏈表為空

return

0;

//刪除失敗

//如果刪除的是第1個(gè)結(jié)點(diǎn)

if(strcmp(h->data.stuId,stuId)==0)

{

p=h;

//p指向待刪除結(jié)點(diǎn)

h=h->next;//頭指針指向新的第1個(gè)結(jié)點(diǎn)

free(p);

//釋放被刪除結(jié)點(diǎn)

return

1;

//刪除成功

}如果刪除的是第1個(gè)結(jié)點(diǎn)，這種沒有前驅(qū)的特殊情況，需要單獨(dú)處理！

//查找待刪除結(jié)點(diǎn)的直接前驅(qū)，用pre指向

pre=h;

//pre指向第1個(gè)結(jié)點(diǎn)

p=pre->next;//p指向第2個(gè)結(jié)點(diǎn)

while(p!=NULL)

{

//如果p指向了待刪除的結(jié)點(diǎn)

if(strcmp(p->data.stuId,stuId)==0)

{

//從鏈表中斷開待刪除的結(jié)點(diǎn)

pre->next=p->next;

free(p);

//釋放被刪除結(jié)點(diǎn)

return

1;

//刪除成功

}

pre=p;

p=p->next;//p指向下一個(gè)結(jié)點(diǎn)

}

return

0;//刪除失敗}偽代碼2-10無頭結(jié)點(diǎn)單鏈表的刪除操作(續(xù))如果刪除的不是第1個(gè)結(jié)點(diǎn)，統(tǒng)一處理！2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表偽代碼2-11有頭結(jié)點(diǎn)單鏈表的刪除操作81int

del(LinkNode*h,charstuId[]){

LinkNode*pre,*p;

//查找待刪除結(jié)點(diǎn)的直接前驅(qū)，用pre指向

pre=h;

//pre指向頭結(jié)點(diǎn)

p=pre->next;//p指向第1個(gè)數(shù)據(jù)結(jié)點(diǎn)

while(p!=NULL)

{

//如果p指向了待刪除的結(jié)點(diǎn)

if(strcmp(p->data.stuId,stuId)==0)

{

pre->next=p->next;//斷開待刪除的結(jié)點(diǎn)

free(p);

//釋放被刪除結(jié)點(diǎn)

return

1;

//刪除成功

}

pre=p;

p=p->next;//p指向下一個(gè)結(jié)點(diǎn)

}

return

0;//未找到指定結(jié)點(diǎn)，刪除失敗}無論刪除的是不是第1個(gè)元素，都不再需要單獨(dú)處理！因?yàn)榈?個(gè)元素，已經(jīng)是第2個(gè)結(jié)點(diǎn)。2.3線性表的鏈?zhǔn)酱鎯?chǔ)——循環(huán)鏈表2.3.3循環(huán)鏈表822.3線性表的鏈?zhǔn)酱鎯?chǔ)——循環(huán)鏈表2.3.3循環(huán)鏈表普通的單向鏈表，判斷p是否指向最后那個(gè)結(jié)點(diǎn)判斷p所指結(jié)點(diǎn)的指針域是否為空即p->next==NULL單向循環(huán)鏈表，判斷p是否指向最后那個(gè)結(jié)點(diǎn)判斷p所指結(jié)點(diǎn)指針域的值，是否等于頭指針即p->next==head循環(huán)單鏈表也可以只設(shè)一個(gè)尾指針，從表頭或表尾插入都方便832.3線性表的鏈?zhǔn)酱鎯?chǔ)——雙向鏈表2.3.4雙向鏈表單鏈表的缺點(diǎn)：只能順著指針的方向，依次尋找其他結(jié)點(diǎn)；若要尋找某結(jié)點(diǎn)的直接前驅(qū)，則要從頭指針出發(fā)遍歷單鏈表。雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)84typedef

struct_DLinkNode{

ElemTypedata;

//數(shù)據(jù)域

struct_DLinkNode*prior;//指向直接前驅(qū)結(jié)點(diǎn)的指針

struct_DLinkNode*next;

//指向直接后繼結(jié)點(diǎn)的指針}DLinkNode;priornext2.3線性表的鏈?zhǔn)酱鎯?chǔ)——雙向鏈表2.3.4雙向鏈表無頭結(jié)點(diǎn)的雙向鏈表852.3線性表的鏈?zhǔn)酱鎯?chǔ)——雙向鏈表2.3.4雙向鏈表有頭結(jié)點(diǎn)的雙向鏈表862.3線性表的鏈?zhǔn)酱鎯?chǔ)——雙向鏈表2.3.4雙向鏈表無頭結(jié)點(diǎn)的雙向循環(huán)鏈表872.3線性表的鏈?zhǔn)酱鎯?chǔ)——雙向鏈表2.3.4雙向鏈表有頭結(jié)點(diǎn)的雙向循環(huán)鏈表882.3線性表的鏈?zhǔn)酱鎯?chǔ)——雙向鏈表2.3.4雙向鏈表雙向鏈表中刪除結(jié)點(diǎn)的操作89操作描述：

①

p-

prior-

next=p-

next;

②

p-

next-

prior=p-

prior;

③

free(p);建立第①條鏈時(shí)，第③條鏈會(huì)隨之?dāng)嚅_。建立第②條鏈時(shí)，第④條鏈會(huì)隨之?dāng)嚅_。2.3線性表的鏈?zhǔn)酱鎯?chǔ)——雙向鏈表2.3.4雙向鏈表雙向鏈表中插入結(jié)點(diǎn)的操作90操作描述： ①p->prior=q;②p->next=q->next;③q->next->prior=p;④q->next=p;第③條語句要先于第④條語句執(zhí)行。建立第④條鏈時(shí)，第⑥條鏈會(huì)斷開，如果沒有提前建立第②條鏈，則結(jié)點(diǎn)B會(huì)丟失。如果第④條語句在第③條語句之前執(zhí)行，即便能夠通過第②條鏈找到結(jié)點(diǎn)B，第③條語句的寫法也要改變。可以先執(zhí)行②③(不分先后)，再執(zhí)行①④(不分先后)。2.3線性表的鏈?zhǔn)酱鎯?chǔ)

91End第3章隊(duì)列第3章隊(duì)列3.1隊(duì)列的定義和操作隊(duì)列的定義和特性隊(duì)列的基本操作3.2隊(duì)列的存儲(chǔ)和實(shí)現(xiàn)順序隊(duì)列鏈?zhǔn)疥?duì)列3.3隊(duì)列的應(yīng)用舉例94重難點(diǎn)隊(duì)列和線性表的關(guān)系——操作受限的含義循環(huán)順序隊(duì)列的相關(guān)操作鏈?zhǔn)疥?duì)列利用隊(duì)列的特點(diǎn)解決應(yīng)用問題（后續(xù)章節(jié)中樹和圖的遍歷等）953.1隊(duì)列的定義和操作

96

進(jìn)隊(duì)出隊(duì)3.1.1隊(duì)列的定義和特性隊(duì)列的特性隊(duì)列中的元素須按進(jìn)隊(duì)的次序出隊(duì)，也就是說隊(duì)列的操作遵循“先進(jìn)先出”(FirstInFirstOut,

FIFO)的操作原則。應(yīng)用實(shí)例計(jì)算機(jī)處理文件打印食堂排隊(duì)打飯車站排隊(duì)買票973.1.2隊(duì)列的基本操作進(jìn)隊(duì)操作：inQueue(&q,

x)初始條件：隊(duì)列q存在，且未滿。操作結(jié)果：插入一個(gè)元素x到隊(duì)尾，隊(duì)列長(zhǎng)度加1出隊(duì)操作：outQueue(&q,

&x）初始條件：隊(duì)列q存在，且非空。操作結(jié)果：將隊(duì)首元素賦值給x帶回給主調(diào)函數(shù)，然后將隊(duì)首元素從隊(duì)列中刪除，隊(duì)列長(zhǎng)度減1。983.1.2隊(duì)列的基本操作判隊(duì)空操作：isQEmpty(q)初始條件：隊(duì)列q存在操作結(jié)果：隊(duì)列空則返回1，否則返回0判隊(duì)滿操作：isQFull(q)初始條件：隊(duì)列q存在操作結(jié)果：隊(duì)列滿則返回1，否則返回0讀取隊(duì)頭和隊(duì)尾元素：readFrontRear(q,

&x,&y）初始條件：隊(duì)列q存在，且非空。操作結(jié)果：將隊(duì)頭元素賦值給x帶回給主調(diào)函數(shù)，將隊(duì)尾元素賦值給y帶回給主調(diào)函數(shù)，隊(duì)列內(nèi)容不變。993.1.2隊(duì)列的基本操作顯示隊(duì)列中元素showQueue(q)初始條件：隊(duì)列q存在，且非空。操作結(jié)果：顯示隊(duì)列中的所有元素。求隊(duì)列長(zhǎng)度：getQLength(q)

初始條件：隊(duì)列q存在操作結(jié)果：返回隊(duì)列中當(dāng)前元素的個(gè)數(shù)。100#defineN8typedef

struct{

ElemTypedata[N];

int

front;//front指示隊(duì)頭元素的位置

int

rear;

//rear指示隊(duì)尾元素的位置}SeqQueue;

//定義順序隊(duì)列的類型SeqQueue3.2隊(duì)列的存儲(chǔ)和實(shí)現(xiàn)3.2.1順序隊(duì)列用一組地址連續(xù)的存儲(chǔ)單元(即數(shù)組)

存儲(chǔ)隊(duì)中元素10101234567

rear=4front=-1N

正好指在隊(duì)尾元素指在隊(duì)頭元素的前一個(gè)位置data3.2.1順序隊(duì)列順序隊(duì)列的初始化若SeqQueueq;

一般設(shè)置隊(duì)頭和隊(duì)尾q.front=q.rear=-1;進(jìn)隊(duì)時(shí)：先執(zhí)行q.rear++;然后將元素進(jìn)隊(duì)到q.rear所指單元出隊(duì)時(shí)：先執(zhí)行q.front++;然后將q.front所指的元素出隊(duì)若將q.front和q.rear的初值設(shè)為0，進(jìn)隊(duì)和出隊(duì)的細(xì)節(jié)可能會(huì)不同10201234567rear=-1front=-1N正好指在隊(duì)尾元素指在隊(duì)頭元素的前一個(gè)位置3.2.1順序隊(duì)列順序隊(duì)列的初始化如果將q.front和q.rear的初始值設(shè)為0一般先存取元素，再移動(dòng)隊(duì)頭或隊(duì)尾指針進(jìn)隊(duì)時(shí)，先按q.rear指示的位置存入元素，再執(zhí)行q.rear++，q.rear指示隊(duì)尾元素的后一位置。出隊(duì)時(shí)，先將下標(biāo)為q.front的元素取出，再執(zhí)行q.front++，q.front指示隊(duì)頭元素的位置。10301234567rear=2front=0指在隊(duì)尾的后一個(gè)位置指在隊(duì)頭的位置3.2.1順序隊(duì)列進(jìn)隊(duì)前提：隊(duì)列未滿；q.rear++; //先將隊(duì)尾指針加1q.data[q.rear]=x; //元素x進(jìn)隊(duì)10401234567frontN=8指在隊(duì)頭元素的前一個(gè)位置

rear指在隊(duì)尾元素的位置N=8rear正好指在隊(duì)尾元素的位置3.2.1順序隊(duì)列出隊(duì)前提：隊(duì)列非空；q.front++; //先將隊(duì)頭指針加1x=q.data[q.front];//隊(duì)頭元素賦值給x10501234567

front指在隊(duì)頭元素的前一個(gè)位置

3.2.1順序隊(duì)列判隊(duì)空開始隊(duì)列為空，隊(duì)頭指針q.front和隊(duì)尾指針q.rear的初值一樣(同時(shí)為-1或0)；進(jìn)隊(duì)一個(gè)元素時(shí)q.rear++，而出隊(duì)一個(gè)元素時(shí)q.front++；若進(jìn)隊(duì)了m個(gè)元素，又出隊(duì)了m個(gè)元素，則一定有q.front==q.rear因此當(dāng)q.front==q.rear時(shí)(即，隊(duì)頭和隊(duì)尾指針再次指向同一個(gè)單元時(shí))，隊(duì)列肯定為空。106rear=-1front=-1rear=4front=4datadata進(jìn)隊(duì)了5個(gè)元素同時(shí)又出隊(duì)了5個(gè)元素3.2.1順序隊(duì)列判隊(duì)滿顯然，隊(duì)列中的元素個(gè)數(shù)m=q.rear—q.front應(yīng)該是當(dāng)隊(duì)列中的元素個(gè)數(shù)m==N時(shí)，隊(duì)列數(shù)組data中沒有空單元存放進(jìn)隊(duì)元素，隊(duì)列為滿。但是隊(duì)列中可能存在“假溢出”現(xiàn)象。10798765假溢出假溢出的特點(diǎn)：q.rear==N－1&&q.rear－q.front<Nrear=9front=4rear不斷自增，當(dāng)rear到達(dá)N－1后，無法繼續(xù)增加；此時(shí)front可能并非初值。data數(shù)組的左側(cè)有大量空的單元，但新元素卻無法進(jìn)隊(duì)。data3.2.1順序隊(duì)列順序隊(duì)列的幾種常見狀態(tài)1083.2.1順序隊(duì)列假溢出的解決方案①當(dāng)rear達(dá)到上界時(shí)，將隊(duì)列中的數(shù)據(jù)整體左移，使空閑空間移至數(shù)組右側(cè)，并且修改front和rear，然后元素即可繼續(xù)進(jìn)隊(duì)。缺點(diǎn)：要經(jīng)常性地移動(dòng)大量數(shù)據(jù)元素，效率太低。109隊(duì)中元素整體左移之后可以繼續(xù)進(jìn)隊(duì)了98765假溢出rear=9front=4data59876rear=4front=-1data3.2.1順序隊(duì)列假溢出的解決方案②允許q.rear<q.front，即當(dāng)q.rear到達(dá)N-1，再進(jìn)隊(duì)時(shí)，讓q.rear指回到0號(hào)單元；從邏輯上將數(shù)據(jù)區(qū)data[0,

...,N-1]看成首尾相連的環(huán)，形成循環(huán)順序隊(duì)列。110數(shù)據(jù)區(qū)構(gòu)造成環(huán)狀之后可以繼續(xù)進(jìn)隊(duì)了98765假溢出rear=9front=4data1098765rear=0front=4data3.2.1順序隊(duì)列如何形成循環(huán)順序隊(duì)列？111數(shù)據(jù)區(qū)構(gòu)造成環(huán)狀之后可以繼續(xù)進(jìn)隊(duì)了98765假溢出rear=9front=4data1098765rear=0front=4dataq.rear++;if(q.rear==N)q.rear=0;q.front++;if(q.front==N)q.front=0;q.rear=(q.rear+1)%N例如：q.rear=(9+1)%10=0q.front=(q.front+1)%N推薦使用右側(cè)這種求余的方式！簡(jiǎn)單明了、快捷3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列的進(jìn)隊(duì)和出隊(duì)操作類似于時(shí)鐘，但只是從邏輯上構(gòu)成環(huán)狀。即認(rèn)為data[N-1]之后就是data[0]而時(shí)鐘不僅從邏輯上，而且從物理上都是環(huán)狀。112思考：front和rear的初始值，還能不能是-1或者0？圖3-3所示的這種循環(huán)順序隊(duì)列，front和rear的初始值應(yīng)為N–1。csq.rear=(csq.rear+1)%Ncsq.front=(csq.front+1)%N3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列在循環(huán)順序隊(duì)列中front和rear的初始值，應(yīng)該被設(shè)置為N–1其中N為數(shù)組長(zhǎng)度(數(shù)組單元的個(gè)數(shù))front和rear的初值不能設(shè)置為–1，為什么?11306543217front=N-1rear=N-1隊(duì)頭隊(duì)尾“指針”移動(dòng)的方向3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列操作過程中的幾種常見狀態(tài)1143.2.1順序隊(duì)列——循環(huán)順序隊(duì)列隊(duì)列的初始和中間狀態(tài)115先進(jìn)隊(duì)6個(gè)元素，再出隊(duì)4個(gè)a6a5frontrear06543217a4a3a2a1初態(tài):front=rear=N–106543217frontrear若有：CircularSeqQueuecsq;則隊(duì)列為空的條件為：csq.front==csq.rear3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列

116如果隊(duì)列中存入第N個(gè)數(shù)據(jù)元素，那么問題來了——隊(duì)滿的條件也是

csq.front==csq.rear?06543217front=7rear=6a1a2a3a4a5a6a7?當(dāng)隊(duì)列中僅剩一個(gè)空閑單元時(shí)，06543217front=3rear=2a9a10a11a5a6a7a8?3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列

117因此，隊(duì)滿的條件應(yīng)為：(csq.rear+1)%N

==csq.front06543217front=7rear=6a1a2a3a4a5a6a7已隊(duì)滿已隊(duì)滿06543217front=3rear=2a9a10a11a5a6a7a83.2.1順序隊(duì)列——循環(huán)順序隊(duì)列隊(duì)頭隊(duì)尾“指針”的初始值如果將front和rear的初始值，設(shè)置為–111806543217front=–1rear=N–2=6a1a2a3a4a5a6a7此時(shí)已隊(duì)滿，但隊(duì)滿的條件卻仍不成立！此時(shí)：csq.front=–1(csq.rear+1)%N=N–1=7(csq.rear+1)%N

≠csq.front如果隊(duì)列初始化之后一直進(jìn)隊(duì)，直到隊(duì)滿。3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列csq中的元素個(gè)數(shù)，分兩種情況如果csq.rear>csq.front隊(duì)列中的元素個(gè)數(shù)為csq.rear–csq.front如果csq.rear<csq.front隊(duì)列中的元素個(gè)數(shù)為csq.rear–csq.front+Ncsq.rear比csq.front多跨越邊界一次（N-1和0號(hào)單元），因此應(yīng)加上N將上述兩種情況統(tǒng)一隊(duì)列中的元素個(gè)數(shù)為(csq.rear–csq.front+N)%N上式的余數(shù)最大只能為N-1，也就是說N個(gè)單元的存儲(chǔ)空間中，最多只能存放N?1個(gè)元素1191098765rear=0front=40987654321N-13.2.1順序隊(duì)列——循環(huán)順序隊(duì)列普通的順序隊(duì)列，肯定存在“假溢出”的現(xiàn)象，因此順序隊(duì)列必然為循環(huán)順序隊(duì)列；以后會(huì)經(jīng)常將循環(huán)順序隊(duì)列簡(jiǎn)稱為順序隊(duì)列。120如無特別說明，以后一般情況下都直接將循環(huán)順序隊(duì)列，都簡(jiǎn)稱為順序隊(duì)列。3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列的類型定義、初始化——方法①與偽代碼3-1類似121#defineN8typedef

struct{

ElemTypedata[N];

intfront;

//front指示隊(duì)頭元素的位置

intrear;

//rear指示隊(duì)尾元素的位置}CycleSeqQueue;

//定義循環(huán)順序隊(duì)列的結(jié)構(gòu)體類型voidinit(CircularSeqQueue&csq){

csq.front=csq.rear=N

–1;}3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列循環(huán)順序隊(duì)列的類型定義、初始化——方法②程序3-1中使用的方法122typedef

struct{

Student*pData; //指向存放隊(duì)列元素的數(shù)組

int

qSize;

//記錄pData所指數(shù)組的單元個(gè)數(shù)

int

front;

//指示隊(duì)頭元素的位置

int

rear;

//指示隊(duì)尾元素的位置}CycleSeqQueue;

//定義順序隊(duì)列的結(jié)構(gòu)體類型void

init(CycleSeqQueue&q) //初始化順序隊(duì)列q{

q.pData=(Student*)malloc(sizeof(Student)*N);

q.qSize=N;

//設(shè)置順序隊(duì)列的數(shù)組長(zhǎng)度

q.front=q.qSize-1; //設(shè)置隊(duì)頭指針，q.qSize-1相等于N-1

q.rear=q.qSize-1;

//設(shè)置隊(duì)尾指針，q.qSize-1相等于N-1}3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列的基本運(yùn)算判隊(duì)空的條件q.front==q.rear123//判斷隊(duì)列是否為空int

isQEmpty(CycleSeqQueueq){

if(q.front==q.rear)

return

1;

else

return

0;}無論q.front和q.rear的值為多少；只要它們相等，即表示隊(duì)列為空。3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列的基本運(yùn)算判隊(duì)滿的條件——最常用的方法(q.rear+1)%N==q.front124//判斷隊(duì)列是否為滿int

isQFull(CycleSeqQueueq){

//如果隊(duì)尾指針加1，就能追上隊(duì)頭，則隊(duì)滿

if((q.rear+1)%q.qSize==q.front)

return

1;

else

return

0;}q.qSize為隊(duì)列中數(shù)組單元的個(gè)數(shù)，相當(dāng)于前面定義的常量N。

3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列的基本運(yùn)算循環(huán)順序隊(duì)列中，判隊(duì)滿的第2種方法定義結(jié)構(gòu)體時(shí)，設(shè)置一個(gè)存儲(chǔ)隊(duì)列中當(dāng)前元素個(gè)數(shù)的變量count當(dāng)count==0時(shí)，表示隊(duì)空；當(dāng)count==N時(shí)，表示隊(duì)滿。125#defineN8typedef

struct{

ElemTypedata[N];

intfront;

//front指示隊(duì)頭元素的位置

intrear;

//rear指示隊(duì)尾元素的位置

int

count;

//count指示隊(duì)列中的元素個(gè)數(shù)}CycleSeqQueue;

//定義循環(huán)順序隊(duì)列的結(jié)構(gòu)體類型這種方法一般不會(huì)使用，否則每次進(jìn)隊(duì)或出隊(duì)都要修改count變量的值。

3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列的基本運(yùn)算進(jìn)隊(duì)操作，參見程序3-1的第67~77行126//進(jìn)隊(duì)一個(gè)元素x到順序隊(duì)列q中int

inQueue(CycleSeqQueue

&q,Studentx){

if(isQFull(q)) //如果隊(duì)滿，則不能繼續(xù)進(jìn)隊(duì)

return

0; //進(jìn)隊(duì)失敗，返回0

//先將q.rear自增，再將x進(jìn)隊(duì)到q.rear指示的單元

q.rear=(q.rear+1)%q.qSize;

q.pData[q.rear]=x;

return

1; //進(jìn)隊(duì)成功，返回1}q.qSize為隊(duì)列中數(shù)組單元的個(gè)數(shù)，相當(dāng)于前面定義的常量N；pData為隊(duì)列中數(shù)組的起始地址，相當(dāng)于前面定義的數(shù)組名data。3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列的基本運(yùn)算出隊(duì)操作，參見程序3-1的第79~87行127//從順序隊(duì)列q中出隊(duì)一個(gè)元素給xintoutQueue(CycleSeqQueue&q,Student

&x){

if(isQEmpty(q))

//如果隊(duì)列為空

return

0;

//出隊(duì)失敗

//隊(duì)頭指針先自增

q.front=(q.front+1)%q.qSize;

x=q.pData[q.front];

//再通過x帶回出隊(duì)元素

return

1;

//出隊(duì)成功}3.2.1順序隊(duì)列——循環(huán)順序隊(duì)列總結(jié)循環(huán)順序隊(duì)列q中，若隊(duì)頭為front，隊(duì)尾為rear，存儲(chǔ)隊(duì)列元素的數(shù)組為data，該數(shù)組的長(zhǎng)度為N，則有隊(duì)頭隊(duì)尾的初始值：q.front=q.rear=N–1進(jìn)隊(duì)時(shí)：q.rear=(q.rear+1)%N出隊(duì)時(shí)：q.front=(q.front+1)%N隊(duì)空的條件：q.front==q.rear隊(duì)滿的條件：q.front==(q.rear+1)%N隊(duì)中元素個(gè)數(shù)為：(q.rear–q.front+N)%N隊(duì)中最多可存放的元素個(gè)數(shù)為：N–1q.rear和q.front的初始值可設(shè)為0，但操作細(xì)節(jié)不同1283.2.1順序隊(duì)列——循環(huán)順序隊(duì)列總結(jié)循環(huán)順序隊(duì)列q中，若隊(duì)頭為front，隊(duì)尾為rear，存儲(chǔ)隊(duì)列元素的數(shù)組為data，該數(shù)組的長(zhǎng)度為N，則有隊(duì)頭隊(duì)尾的初始值：q.front=q.rear=N–1進(jìn)隊(duì)時(shí)：q.rear=(q.rear+1)%N出隊(duì)時(shí)：q.front=(q.front+1)%N隊(duì)空的條件：q.front==q.rear隊(duì)滿的條件：q.front==(q.rear+1)%N隊(duì)中元素個(gè)數(shù)為：(q.rear–q.front+N)%N隊(duì)中最多可存放的元素個(gè)數(shù)為：N–1q.rear和q.front的初始值可設(shè)為0，但操作細(xì)節(jié)不同129課堂提問3.2.2鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列的結(jié)構(gòu)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為鏈?zhǔn)疥?duì)列；它實(shí)際上是一個(gè)有頭指針(front)和尾指針(rear)的單向鏈表，