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

邏輯結構

存儲結構

運算數據結構的研究內容數據的邏輯結構是指反映數據元素之間邏輯關系的數據結構。數據的邏輯結構包含：（1）表示數據元素的信息；（2）表示各數據元素之間的關系。邏輯結構邏輯結構的概念數據元素是數據的基本單位，即數據集合中的個體。有時一個數據元數可由若干數據項(DataItem)組成。數據項是數據的最小單位。數據元素亦稱結點或記錄。數據元素數據項數據結構可描述為：Group=（D，R）邏輯數據結構的描述有限個數據元素的集合。數據元素之間關系的集合。

D

R例：1.一年四季的數據結構

B=(D,R)D={春，夏，秋，冬}R={(春，夏),(夏，秋),(秋，冬)}2.家庭成員的數據結構

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

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

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

對數階O(log2n)

線性階O(n)

線性對數階O(nlog2n)

k次方階O(nK)

指數階O(2n)

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

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

{

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

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

計算方法：

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

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

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

returnn;else

returnfun(++n);}

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

變量值創建一次，所以空間復雜度為O（1）。遞歸：時間復雜度為O（log2n）。

每進行一次遞歸都會創建變量，所以空間復雜度為O（log2n）。算法：是一組邏輯步驟。程序：用計算機語言描述的算法。開始輸入RS=3.14*

R*R輸出S結束main(){floatr,s;scanf(“%f”,&r);if(r<0)printf(“err,r<0”);else{s=r*r*3.14;printf(“s=%f”,s);}算法和程序的區別4.5線性表線性表、棧和隊列都是線性結構；樹、圖、網屬于非線性結構。一個非空的數據結構若滿足下面的幾個條件：①有且僅有一個根結點；②除第一個結點外，每一個結點最多有一個直接前驅結點；③除最后一個結點外，每一個結點最多有一個直接后繼結點。線性結構由n（n≥0）個數據元素a1，a2，…，ai，…，an組成的一個有限序列。20183230767890657034線性表的概念線性表的特點：（1）線性表中所有元素的性質相同。（2）除第一個和最后一個數據元素之外，其它數據元素有且僅有一個前驅和一個后繼。第一個數據元素無前驅，最后一個數據元素無后繼。（3）數據元素在表中的位置只取決于它自身的序號。線性表的存儲結構順序存儲結構鏈式存儲結構線性表上常用的操作有：初始化、求長度、取元素、修改、插入、刪除、檢索、排序。ai-1…..a2a1aiai+1alength…ai+1aix分配連續存儲空間，依次存儲所有元素。邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元里；只存儲結點的值，不存儲結點間的關系；結點間的關系由存儲單元的鄰接關系來體現。線性表的順序存儲結構稱為順序表線性表的順序存儲在程序設計語言中，通常利用數組來表示線性表的順序存儲結構。（1）數組中的元素間的地址是連續的；（2）數組中所有元素的數據類型相同。inta[10];系統將在內存中分配連續的40個字節（VC中整數占4個字節），存放10個整數。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直接定位，實現隨機存取插入運算ai-1…..a2a1alength…ai+1aixai-1…..a2a1aiai+1alength…ai+1aixai-1…..a2a1

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

數據域指針域鏈式存儲線性表的鏈式存儲結構稱為線性鏈表5AB036F200AB350018C300AC210CD00A1180CF0026100UNLLp帶頭節點的鏈表P->data：5P->nextP->next->data：第一個元素200

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

a2,

a3,

a4,…………

an-1,

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

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

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

最后一個進棧的元素在棧頂；第一個出棧的元素為棧頂元素；最后一個出棧的元素為棧底元素。不含元素的棧稱為空棧。a1a2….an入棧出棧棧頂棧底a1a2top棧的順序存儲順序棧用一組連續的存儲單元存放自棧底到棧頂的數據元素。一般用一維數組表示，設置簡單變量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