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

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

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

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

運算數(shù)據(jù)結(jié)構(gòu)的研究內(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ù)集合中的個體。有時一個數(shù)據(jù)元數(shù)可由若干數(shù)據(jù)項(DataItem)組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱結(jié)點或記錄。數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)結(jié)構(gòu)可描述為：Group=（D，R）邏輯數(shù)據(jù)結(jié)構(gòu)的描述有限個數(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）線性結(jié)構(gòu)A,B,C,·······，X,Y,Z學(xué)生成績表86胡敏201816110395劉雨涵201816110787張卓2018161109成績姓名學(xué)號結(jié)點間是線性關(guān)系。常見的邏輯結(jié)構(gòu)（2）樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式ABCDEFGH樹形結(jié)構(gòu)——

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

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

對數(shù)階O(log2n)

線性階O(n)

線性對數(shù)階O(nlog2n)

k次方階O(nK)

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

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

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

{

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

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

計算方法：

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

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

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

returnn;else

returnfun(++n);}

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

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

每進(jìn)行一次遞歸都會創(chuàng)建變量，所以空間復(fù)雜度為O（log2n）。算法：是一組邏輯步驟。程序：用計算機(jī)語言描述的算法。開始輸入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線性表線性表、棧和隊列都是線性結(jié)構(gòu)；樹、圖、網(wǎng)屬于非線性結(jié)構(gòu)。一個非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的幾個條件：①有且僅有一個根結(jié)點；②除第一個結(jié)點外，每一個結(jié)點最多有一個直接前驅(qū)結(jié)點；③除最后一個結(jié)點外，每一個結(jié)點最多有一個直接后繼結(jié)點。線性結(jié)構(gòu)由n（n≥0）個數(shù)據(jù)元素a1，a2，…，ai，…，an組成的一個有限序列。20183230767890657034線性表的概念線性表的特點：（1）線性表中所有元素的性質(zhì)相同。（2）除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個前驅(qū)和一個后繼。第一個數(shù)據(jù)元素?zé)o前驅(qū)，最后一個數(shù)據(jù)元素?zé)o后繼。（3）數(shù)據(jù)元素在表中的位置只取決于它自身的序號。線性表的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表上常用的操作有：初始化、求長度、取元素、修改、插入、刪除、檢索、排序。ai-1…..a2a1aiai+1alength…ai+1aix分配連續(xù)存儲空間，依次存儲所有元素。邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里；只存儲結(jié)點的值，不存儲結(jié)點間的關(guān)系；結(jié)點間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。線性表的順序存儲結(jié)構(gòu)稱為順序表線性表的順序存儲在程序設(shè)計語言中，通常利用數(shù)組來表示線性表的順序存儲結(jié)構(gòu)。（1）數(shù)組中的元素間的地址是連續(xù)的；（2）數(shù)組中所有元素的數(shù)據(jù)類型相同。inta[10];系統(tǒng)將在內(nèi)存中分配連續(xù)的40個字節(jié)（VC中整數(shù)占4個字節(jié)），存放10個整數(shù)。a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]a0a1a2a3……ai……an存儲空間Loc(a0)Loc(a0)+dLoc(a0)+2*dLoc(a0)+i*dLoc(a0)+n*d存儲地址a[0]a[1]a[2]a[3]……a[i]……a[n]元素Loc（ai）=Loc（a0）+i*d直接定位，實現(xiàn)隨機(jī)存取插入運算ai-1…..a2a1alength…ai+1aixai-1…..a2a1aiai+1alength…ai+1aixai-1…..a2a1

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

數(shù)據(jù)域指針域鏈?zhǔn)酱鎯€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表5AB036F200AB350018C300AC210CD00A1180CF0026100UNLLp帶頭節(jié)點的鏈表P->data：5P->nextP->next->data：第一個元素200

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

a2,

a3,

a4,…………

an-1,

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

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

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

最后一個進(jìn)棧的元素在棧頂；第一個出棧的元素為棧頂元素；最后一個出棧的元素為棧底元素。不含元素的棧稱為空棧。a1a2….an入棧出棧棧頂棧底a1a2top棧的順序存儲順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素。一般用一維數(shù)組表示，設(shè)置簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置。即：棧頂元素在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