第4單元 數(shù)據(jù)結(jié)構(gòu)與線(xiàn)性問(wèn)題處理

大學(xué)文科計(jì)算機(jī)4.1數(shù)據(jù)結(jié)構(gòu)概述計(jì)算機(jī)解決問(wèn)題的一般步驟問(wèn)題數(shù)學(xué)模型設(shè)計(jì)算法編寫(xiě)程序數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的組織、存儲(chǔ)和運(yùn)算。能被計(jì)算機(jī)程序處理的符號(hào)的集合。數(shù)據(jù)數(shù)據(jù)元素以及元素之間的關(guān)系。組織元素及其關(guān)系在計(jì)算機(jī)中的表示。存儲(chǔ)對(duì)數(shù)據(jù)元素進(jìn)行的操作處理(插入、刪除、修改、查找、排序)。運(yùn)算數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)科學(xué)的核心內(nèi)容之一。介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間。不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)的地位問(wèn)題的抽象：基本構(gòu)成（元素），以及它們之間的關(guān)系。邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)：存儲(chǔ)元素以及元素之間的關(guān)系。如何解決問(wèn)題，滿(mǎn)足管理需求。研究三個(gè)問(wèn)題

邏輯結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)

運(yùn)算數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的關(guān)系。邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)的概念數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。有時(shí)一個(gè)數(shù)據(jù)元數(shù)可由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱(chēng)結(jié)點(diǎn)或記錄。數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)可描述為：Group=（D，R）邏輯數(shù)據(jù)結(jié)構(gòu)的描述有限個(gè)數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間關(guān)系的集合。

D

R例：1.一年四季的數(shù)據(jù)結(jié)構(gòu)

B=(D,R)D={春，夏，秋，冬}R={(春，夏),(夏，秋),(秋，冬)}2.家庭成員的數(shù)據(jù)結(jié)構(gòu)

B=(D,R)D={父親，兒子，女兒}R={(父親，兒子),(父親，女兒)}春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖形表示父親兒子女兒（1）線(xiàn)性結(jié)構(gòu)A,B,C,·······，X,Y,Z學(xué)生成績(jī)表86胡敏201816110395劉雨涵201816110787張卓2018161109成績(jī)姓名學(xué)號(hào)結(jié)點(diǎn)間是線(xiàn)性關(guān)系。常見(jiàn)的邏輯結(jié)構(gòu)（2）樹(shù)形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式ABCDEFGH樹(shù)形結(jié)構(gòu)——

結(jié)點(diǎn)間具有分層關(guān)系HBCDEFGA1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(2,4),(3,4)}213D={1,2,3}R={(1,2),(2,3),(3,2),(1,3)}

（3）圖形結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)指邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的具體實(shí)現(xiàn)。存儲(chǔ)所有元素；存儲(chǔ)元素之間的關(guān)系一種邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)的概念順序存儲(chǔ)散列存儲(chǔ)索引存儲(chǔ)常見(jiàn)存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)常見(jiàn)的存儲(chǔ)結(jié)構(gòu)一種邏輯結(jié)構(gòu)：可以表示成一種或多種存儲(chǔ)結(jié)構(gòu)。4.2順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)采用連續(xù)存儲(chǔ)空間存儲(chǔ)數(shù)據(jù)元素；元素之間的關(guān)系通過(guò)存儲(chǔ)位置的關(guān)系來(lái)表示。元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容順序存儲(chǔ)有關(guān)鍵字序列：327570634894253618a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]32757063489425361832186382590i2i2i+150a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]73218638255090父節(jié)點(diǎn)左孩子右孩子不足之處：作插入或刪除操作時(shí)，需移動(dòng)大量元素。長(zhǎng)度變化較大時(shí)，需按最大空間分配。容量難以擴(kuò)充。Loc(a)=Lo+（i-1)*m每個(gè)元素所占用的存儲(chǔ)單元個(gè)數(shù)優(yōu)點(diǎn)：易于定位每個(gè)結(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素本身的數(shù)據(jù)，指針域存放下一個(gè)結(jié)點(diǎn)的地址。數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來(lái)體現(xiàn)。鏈?zhǔn)酱鎯?chǔ)1536851400100134673∧351345h邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。插入、刪除靈活(不必移動(dòng)節(jié)點(diǎn)，只要改變結(jié)點(diǎn)中的指針)。不能直接定位，必須從頭向后遍歷。鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn)：4.3索引存儲(chǔ)與散列存儲(chǔ)存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，建立附加的索引表。索引表中的每一項(xiàng)稱(chēng)為一個(gè)索引項(xiàng)，索引項(xiàng)的一般形式：關(guān)鍵字：能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。地址：同值關(guān)鍵字結(jié)點(diǎn)的起始位置。稠密索引：每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)。稀疏索引：一組結(jié)點(diǎn)在索引表中只對(duì)應(yīng)一個(gè)索引項(xiàng)關(guān)鍵字地址索引方式分配連續(xù)存儲(chǔ)空間，元素的存儲(chǔ)位置由元素的關(guān)鍵字計(jì)算得到。有關(guān)鍵字序列：327570634894253618存儲(chǔ)空間大?。?1地址計(jì)算規(guī)則：L=KMOD11沖突解決機(jī)制：L+1散列方式K327570634894253618L1094846337A10948?A012345678910K70637532計(jì)算存儲(chǔ)位置：K327570634894253618L1094846337A109485A012345678910K7048637532K327570634894253618L1094846337A10948563?A012345678910K25704894637532K327570634894253618L1094846337A109485637A012345678910K2570489436637532K327570634894253618L1094846337A109485637?A012345678910K2570489436637532K327570634894253618L1094846337A1094856370A012345678910K182570489436637532K327570634894253618L1094846337A1094856370N111121155A012345678910K1825704894366375324.4算法算法概念算法是程序設(shè)計(jì)的核心算法是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則。算法是解題的過(guò)程。形成解題思路(推理實(shí)現(xiàn)的算法)，編寫(xiě)程序(操作實(shí)現(xiàn)的算法)，都是在實(shí)施某種算法。算法以存儲(chǔ)結(jié)構(gòu)為基礎(chǔ)算法特征保證執(zhí)行有限步之后結(jié)束有窮性每一步驟必須有確切的定義確定性有0個(gè)或多個(gè)輸入，0輸入是指算法本身設(shè)定了初始條件有輸入有一個(gè)或多個(gè)輸出，沒(méi)有輸出的算法毫無(wú)意義有輸出能夠在有限時(shí)間、有限空間內(nèi)完成可行性算法設(shè)計(jì)的要求能夠正確的解決問(wèn)題。正確性①不含語(yǔ)法錯(cuò)誤；②對(duì)于幾組輸入數(shù)據(jù)，結(jié)果正確；③對(duì)于精心選擇的幾組數(shù)據(jù)，結(jié)果正確；④對(duì)一切合法的輸入數(shù)據(jù)，結(jié)果正確。應(yīng)容易供人閱讀和交流?？勺x性好的算法有助于對(duì)算法的理解和修改?？勺x性應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí)，算法應(yīng)能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理健壯性應(yīng)具有一般性。即算法的處理結(jié)果對(duì)于一般的數(shù)據(jù)集合都成立。通用性算法的表示需要使用一些語(yǔ)言形式。傳統(tǒng)描述-------圖形法:“流程圖”和N-S圖。常用描述-------使用偽碼描述算法。算法描述INPUTrS=3.14*r*rPTINTS開(kāi)始輸入RS=3.14*

R*R輸出S結(jié)束問(wèn)題：輸入園的半徑，計(jì)算圓的面積。算法性能分析執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量。時(shí)間復(fù)雜度執(zhí)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間來(lái)度量?？臻g復(fù)雜度基本語(yǔ)句執(zhí)行次數(shù)，而非時(shí)間。計(jì)算最壞情況。常數(shù)階O(1)

對(duì)數(shù)階O(log2n)

線(xiàn)性階O(n)

線(xiàn)性對(duì)數(shù)階O(nlog2n)

k次方階O(nK)

指數(shù)階O(2n)

時(shí)間復(fù)雜度隨著問(wèn)題規(guī)模n的不斷增大，時(shí)間復(fù)雜度不斷增大。intx=1,s=0;while(x<10){s+=x;x++;}執(zhí)行10次，時(shí)間復(fù)雜度表示是O(1)。

inti,j,s=1;for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{s=s+i*j}}時(shí)間復(fù)雜度是O（n2）運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度。

計(jì)算方法：

①忽略常數(shù)，用O(1)表示

②遞歸算法的空間復(fù)雜度=遞歸深度N*每次遞歸所要的輔助空間

空間復(fù)雜度intfun(intn){intk=10;if（n==k)

returnn;else

returnfun(++n);}

遞歸實(shí)現(xiàn)，調(diào)用fun函數(shù)每次都創(chuàng)建1個(gè)變量k。調(diào)用n次，空間復(fù)雜度O（n*1）=O(n)。二分查找的時(shí)間復(fù)雜度及空間復(fù)雜度以查找68為例：二分查找的時(shí)間復(fù)雜度及空間復(fù)雜度非遞歸：每次都對(duì)原查找內(nèi)容進(jìn)行二分，所以時(shí)間復(fù)雜度為O（log2n）。

變量值創(chuàng)建一次，所以空間復(fù)雜度為O（1）。遞歸：時(shí)間復(fù)雜度為O（log2n）。

每進(jìn)行一次遞歸都會(huì)創(chuàng)建變量，所以空間復(fù)雜度為O（log2n）。算法：是一組邏輯步驟。程序：用計(jì)算機(jī)語(yǔ)言描述的算法。開(kāi)始輸入RS=3.14*

R*R輸出S結(jié)束main(){floatr,s;scanf(“%f”,&r);if(r<0)printf(“err,r<0”);else{s=r*r*3.14;printf(“s=%f”,s);}算法和程序的區(qū)別4.5線(xiàn)性表線(xiàn)性表、棧和隊(duì)列都是線(xiàn)性結(jié)構(gòu)；樹(shù)、圖、網(wǎng)屬于非線(xiàn)性結(jié)構(gòu)。一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)若滿(mǎn)足下面的幾個(gè)條件：①有且僅有一個(gè)根結(jié)點(diǎn)；②除第一個(gè)結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接前驅(qū)結(jié)點(diǎn)；③除最后一個(gè)結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接后繼結(jié)點(diǎn)。線(xiàn)性結(jié)構(gòu)由n（n≥0）個(gè)數(shù)據(jù)元素a1，a2，…，ai，…，an組成的一個(gè)有限序列。20183230767890657034線(xiàn)性表的概念線(xiàn)性表的特點(diǎn)：（1）線(xiàn)性表中所有元素的性質(zhì)相同。（2）除第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。第一個(gè)數(shù)據(jù)元素?zé)o前驅(qū)，最后一個(gè)數(shù)據(jù)元素?zé)o后繼。（3）數(shù)據(jù)元素在表中的位置只取決于它自身的序號(hào)。線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線(xiàn)性表上常用的操作有：初始化、求長(zhǎng)度、取元素、修改、插入、刪除、檢索、排序。ai-1…..a2a1aiai+1alength…ai+1aix分配連續(xù)存儲(chǔ)空間，依次存儲(chǔ)所有元素。邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里；只存儲(chǔ)結(jié)點(diǎn)的值，不存儲(chǔ)結(jié)點(diǎn)間的關(guān)系；結(jié)點(diǎn)間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)為順序表線(xiàn)性表的順序存儲(chǔ)在程序設(shè)計(jì)語(yǔ)言中，通常利用數(shù)組來(lái)表示線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)。（1）數(shù)組中的元素間的地址是連續(xù)的；（2）數(shù)組中所有元素的數(shù)據(jù)類(lèi)型相同。inta[10];系統(tǒng)將在內(nèi)存中分配連續(xù)的40個(gè)字節(jié)（VC中整數(shù)占4個(gè)字節(jié)），存放10個(gè)整數(shù)。a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]a0a1a2a3……ai……an存儲(chǔ)空間Loc(a0)Loc(a0)+dLoc(a0)+2*dLoc(a0)+i*dLoc(a0)+n*d存儲(chǔ)地址a[0]a[1]a[2]a[3]……a[i]……a[n]元素Loc（ai）=Loc（a0）+i*d直接定位，實(shí)現(xiàn)隨機(jī)存取插入運(yùn)算ai-1…..a2a1alength…ai+1aixai-1…..a2a1aiai+1alength…ai+1aixai-1…..a2a1

aiai+1…alengthalength……ai+1aiai從后向前依次后移刪除運(yùn)算4171528303242516341715303242516363從前向后依次前移隊(duì)尾元素插入算法性能分析假設(shè)線(xiàn)性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個(gè)位置上插入元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：時(shí)間復(fù)雜度為O(n)。刪除算法的分析在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：時(shí)間復(fù)雜度為O(n)。表中數(shù)據(jù)元素類(lèi)型一致，只有數(shù)據(jù)域，存儲(chǔ)空間利用率高；各數(shù)據(jù)元素在存儲(chǔ)空間中按邏輯順序依次存放，占有連續(xù)存儲(chǔ)空間，可以直接定位；做插入、刪除時(shí)需移動(dòng)大量元素，若表長(zhǎng)為n，則插入算法的時(shí)間復(fù)雜度都為O(n)?？臻g估計(jì)不清楚時(shí)，應(yīng)按最大空間分配。順序存儲(chǔ)總結(jié)4.6線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)數(shù)據(jù)存在結(jié)中，不要求邏輯上相鄰的數(shù)據(jù)元素物理位置也相鄰；各數(shù)據(jù)元素的存儲(chǔ)順序任意；數(shù)據(jù)元素的先后關(guān)系是由結(jié)點(diǎn)的指針域指示。

數(shù)據(jù)域指針域鏈?zhǔn)酱鎯?chǔ)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線(xiàn)性鏈表5AB036F200AB350018C300AC210CD00A1180CF0026100UNLLp帶頭節(jié)點(diǎn)的鏈表P->data：5P->nextP->next->data：第一個(gè)元素200

0NULLp空表5AB036F200AB350018C300AC210CD00A1180CF0026100UNLLp在210的后面插入300q=p->next;從q開(kāi)始向后遍歷，找210若q->data!=210，則q=q->next;q插入運(yùn)算5AB036F200AB350018C300AC210CD00A1180CF0026100UNLLp申請(qǐng)結(jié)點(diǎn)rr->data=300;r->next=q-next;將r和q的后繼結(jié)點(diǎn)鏈接q300CD00A1r6AB036F200AB350018C300AC210CD00A1180CF0026100UNLLpq->next=r;將q和r鏈接起來(lái)修改節(jié)點(diǎn)數(shù)為6q300CD00A1r5AB036F200AB350018C300AC210CD00A1180CF0026100UNLLp刪除180從前向后找到180的前驅(qū)結(jié)點(diǎn)q=p;若q->next->data!=180，則q=q->next;q刪除運(yùn)算5AB036F200AB350018CF0026210CD00A1180CF0026100UNLLps=q->next;保存180所在節(jié)點(diǎn)位置q->next=s->next;將S從鏈中刪除qs4AB036F200AB350018CF0026210CD00A1100UNLLpfree(s);釋放s所指向的節(jié)點(diǎn)修改節(jié)點(diǎn)數(shù)為4q表中數(shù)據(jù)元素類(lèi)型一致，結(jié)點(diǎn)由數(shù)據(jù)域和指針域構(gòu)成；按需申請(qǐng)結(jié)點(diǎn)，結(jié)點(diǎn)空間不連續(xù)；不可直接定位，需從頭遍歷；便于插入、刪除。鏈?zhǔn)酱鎯?chǔ)總結(jié)循環(huán)鏈表：最后一個(gè)節(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)。單向鏈表的改進(jìn)5AB036F200AB350018C300AC210CD00A1180CF0026100A00035p從任意一個(gè)節(jié)點(diǎn)開(kāi)始都可向后進(jìn)行遍歷。雙向鏈表：可以克服單鏈表的單向性的缺點(diǎn)。在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域：其一指向直接后繼，另一指向直接前趨。priordatanext從任意一節(jié)點(diǎn)開(kāi)始，既可向前(q->prior)，也可向后(q->next)進(jìn)行遍歷。4.7隊(duì)列的存儲(chǔ)與處理隊(duì)列是操作位置受限的線(xiàn)性表隊(duì)的概念只能在表的一端插入，另一端進(jìn)行刪除的線(xiàn)性表。此種結(jié)構(gòu)稱(chēng)為先進(jìn)先出表。a1,

a2,

a3,

a4,…………

an-1,

an隊(duì)首隊(duì)尾（1）設(shè)置一個(gè)空隊(duì)列；（2）插入一個(gè)新的元素（隊(duì)尾），稱(chēng)為入隊(duì)；（3）刪除隊(duì)頭素（隊(duì)首），稱(chēng)為出隊(duì)；（4）讀取隊(duì)頭元素；隊(duì)的基本操作用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素，指針front和rear分別指示隊(duì)頭元素和隊(duì)尾元素的位置。隊(duì)的順序存儲(chǔ)1242582674630123456789frontrear隊(duì)空：令rear=front=-1；元素入隊(duì)：rear=rear+1;a[rear]=m;元素出隊(duì)：front=front+1;m=a[front];

故在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素前一個(gè)位置，而尾指針始終指向隊(duì)尾元素的位置124258267463900123456789frontrear42出隊(duì)90入隊(duì)一定會(huì)出現(xiàn)假溢出現(xiàn)象124258267463906258710123456789frontrear隊(duì)中只有一個(gè)元素71，若有元素入隊(duì)則溢出。A[0]--------------------------a[8]空閑解決方法：存入a[0]864258267463906258710123456789frontrear86入隊(duì)可以將為隊(duì)列分配空間看成為一個(gè)首尾相接的圓環(huán)，并稱(chēng)這種隊(duì)列為循環(huán)隊(duì)列。本質(zhì)：rear和front在結(jié)尾處完成向開(kāi)始的跳轉(zhuǎn)。90864258267463906258710123456789frontrear86入隊(duì)入隊(duì)：rear=（rear+1）modQSize;a[rear]=m;出隊(duì)：front=（front+1）modQSize;m=a[front];864258267463906258710123456789frontrear隊(duì)空：rear==front;出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空時(shí)頭尾指針相等。866567897060879096830123456789frontrear隊(duì)滿(mǎn)：（rear+1）modQSize==front;Front所指空間永遠(yuǎn)為空。入隊(duì)時(shí)尾指針向前追趕尾指針，此時(shí)不能再入隊(duì)，否則rear==front,滿(mǎn)隊(duì)、空隊(duì)無(wú)法區(qū)分。

隊(duì)列具有的先進(jìn)先出的固有特性，使得隊(duì)列成為程序設(shè)計(jì)中常用的工具。隊(duì)列的應(yīng)用任務(wù)調(diào)度事件被觸發(fā)，產(chǎn)生消息，存入系統(tǒng)的消息隊(duì)列。線(xiàn)程從隊(duì)列中取出消息，通過(guò)操作系統(tǒng)發(fā)送到對(duì)應(yīng)的窗口過(guò)程去處理。OS從系統(tǒng)消息隊(duì)列中取出一個(gè)消息，送往處理該消息的線(xiàn)程消息隊(duì)列。對(duì)短作業(yè)不利改進(jìn)……先來(lái)先服務(wù)4.8棧的存儲(chǔ)與處理?xiàng)Ｊ遣僮魑恢檬芟蓿褐荒茉跅ｍ斶M(jìn)行插入和刪除。棧的概念設(shè)棧s=（a1，a2，...,ai，...，an），其中a1是棧底元素，an是棧頂元素。棧頂（top)：允許插入和刪除的一端；棧底（bottom):不允許插入和刪除的一端。a1a2….an入棧出棧棧頂棧底棧也稱(chēng)為稱(chēng)為后進(jìn)先出表第一個(gè)進(jìn)棧的元素在棧底；

最后一個(gè)進(jìn)棧的元素在棧頂；第一個(gè)出棧的元素為棧頂元素；最后一個(gè)出棧的元素為棧底元素。不含元素的棧稱(chēng)為空棧。a1a2….an入棧出棧棧頂棧底a1a2top棧的順序存儲(chǔ)順序棧用一組連續(xù)的存儲(chǔ)單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素。一般用一維數(shù)組表示，設(shè)置簡(jiǎn)單變量top指示棧頂位置，稱(chēng)為棧頂指針，它始終指向待插入元素的位置。即：棧頂元素在top-1處。top空棧：top==0321032106543210入棧Top=0空棧inta[7],top;top=0;a[top]=m;top=top+1;106543210Top=110入棧978563420106543210Top=620,12,34,56,78,9入棧269785634