數據結構與算法
1 算法
算法:是指解題方案的準確而完整的描述。
算法不等於程序,也不等計算機方法,程序的編制不可能優於算法的設計。
算法的基本特征:是壹組嚴謹地定義運算順序的規則,每壹個規則都是有效的,是明確的,此順序將在有限的次數下終止。特征包括:
(1)可行性;
(2)確定性,算法中每壹步驟都必須有明確定義,不充許有模棱兩可的解釋,不允許有多義性;
(3)有窮性,算法必須能在有限的時間內做完,即能在執行有限個步驟後終止,包括合理的執行時間的含義;
(4)擁有足夠的情報。
算法的基本要素:壹是對數據對象的運算和操作;二是算法的控制結構。
指令系統:壹個計算機系統能執行的所有指令的集合。
基本運算和操作包括:算術運算、邏輯運算、關系運算、數據傳輸。
算法的控制結構:順序結構、選擇結構、循環結構。
算法基本設計方法:列舉法、歸納法、遞推、遞歸、減鬥遞推技術、回溯法。
算法復雜度:算法時間復雜度和算法空間復雜度。
算法時間復雜度是指執行算法所需要的計算工作量。
算法空間復雜度是指執行這個算法所需要的內存空間。
2 數據結構的基本基本概念
數據結構研究的三個方面:
(1)數據集合中各數據元素之間所固有的邏輯關系,即數據的邏輯結構;
(2)在對數據進行處理時,各數據元素在計算機中的存儲關系,即數據的存儲結構;
(3)對各種數據結構進行的運算。
數據結構是指相互有關聯的數據元素的集合。
數據的邏輯結構包含:
(1)表示數據元素的信息;
(2)表示各數據元素之間的前後件關系。
數據的存儲結構有順序、鏈接、索引等。
線性結構條件:
(1)有且只有壹個根結點;
(2)每壹個結點最多有壹個前件,也最多有壹個後件。
非線性結構:不滿足線性結構條件的數據結構。
3 線性表及其順序存儲結構
線性表由壹組數據元素構成,數據元素的位置只取決於自己的序號,元素之間的相對位置是線性的。
在復雜線性表中,由若幹項數據元素組成的數據元素稱為記錄,而由多個記錄構成的線性表又稱為文件。
非空線性表的結構特征:
(1)且只有壹個根結點a1,它無前件;
(2)有且只有壹個終端結點an,它無後件;
(3)除根結點與終端結點外,其他所有結點有且只有壹個前件,也有且只有壹個後件。結點個數n稱為線性表的長度,當n=0時,稱為空表。
線性表的順序存儲結構具有以下兩個基本特點:
(1)線性表中所有元素的所占的存儲空間是連續的;
(2)線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。
ai的存儲地址為:adr(ai)=adr(a1)+(i-1)k,,adr(a1)為第壹個元素的地址,k代表每個元素占的字節數。
順序表的運算:插入、刪除。 (詳見14--16頁)
4 棧和隊列
棧是限定在壹端進行插入與刪除的線性表,允許插入與刪除的壹端稱為棧頂,不允許插入與刪除的另壹端稱為棧底。
棧按照“先進後出”(filo)或“後進先出”(lifo)組織數據,棧具有記憶作用。用top表示棧頂位置,用bottom表示棧底。
棧的基本運算:(1)插入元素稱為入棧運算;(2)刪除元素稱為退棧運算;(3)讀棧頂元素是將棧頂元素賦給壹個指定的變量,此時指針無變化。
隊列是指允許在壹端(隊尾)進入插入,而在另壹端(隊頭)進行刪除的線性表。rear指針指向隊尾,front指針指向隊頭。
隊列是“先進行出”(fifo)或“後進後出”(lilo)的線性表。
隊列運算包括(1)入隊運算:從隊尾插入壹個元素;(2)退隊運算:從隊頭刪除壹個元素。
循環隊列:s=0表示隊列空,s=1且front=rear表示隊列滿
5 線性鏈表
數據結構中的每壹個結點對應於壹個存儲單元,這種存儲單元稱為存儲結點,簡稱結點。
結點由兩部分組成:(1)用於存儲數據元素值,稱為數據域;(2)用於存放指針,稱為指針域,用於指向前壹個或後壹個結點。
2008-2-21 10:07 回復 鬥牛士 黛石Sara 2樓在鏈式存儲結構中,存儲數據結構的存儲空間可以不連續,各數據結點的存儲順序與數據元素之間的邏輯關系可以不壹致,而數據元素之間的邏輯關系是由指針域來確定的。
鏈式存儲方式即可用於表示線性結構,也可用於表示非線性結構。
線性鏈表,head稱為頭指針,head=null(或0)稱為空表,如果是兩指針:左指針(llink)指向前件結點,右指針(rlink)指向後件結點。
線性鏈表的基本運算:查找、插入、刪除。
6 樹與二叉樹
樹是壹種簡單的非線性結構,所有元素之間具有明顯的層次特性。
在樹結構中,每壹個結點只有壹個前件,稱為父結點,沒有前件的結點只有壹個,稱為樹的根結點,簡稱樹的根。每壹個結點可以有多個後件,稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中,壹個結點所擁有的後件的個數稱為該結點的度,所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
二叉樹的特點:(1)非空二叉樹只有壹個根結點;(2)每壹個結點最多有兩棵子樹,且分別稱為該結點的左子樹與右子樹。
二叉樹的基本性質:
(1)在二叉樹的第k層上,最多有2k-1(k≥1)個結點;
(2)深度為m的二叉樹最多有2m-1個結點;
(3)度為0的結點(即葉子結點)總是比度為2的結點多壹個;
(4)具有n個結點的二叉樹,其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分;
(5)具有n個結點的完全二叉樹的深度為[log2n]+1;
(6)設完全二叉樹***有n個結點。如果從根結點開始,按層序(每壹層從左到右)用自然數1,2,….n給結點進行編號(k=1,2….n),有以下結論:
①若k=1,則該結點為根結點,它沒有父結點;若k>1,則該結點的父結點編號為int(k/2);
②若2k≤n,則編號為k的結點的左子結點編號為2k;否則該結點無左子結點(也無右子結點);
③若2k+1≤n,則編號為k的結點的右子結點編號為2k+1;否則該結點無右子結點。
滿二叉樹是指除最後壹層外,每壹層上的所有結點有兩個子結點,則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。
完全二叉樹是指除最後壹層外,每壹層上的結點數均達到最大值,在最後壹層上只缺少右邊的若幹結點。
二叉樹存儲結構采用鏈式存儲結構,對於滿二叉樹與完全二叉樹可以按層序進行順序存儲。
二叉樹的遍歷:
(1)前序遍歷(dlr),首先訪問根結點,然後遍歷左子樹,最後遍歷右子樹;
(2)中序遍歷(ldr),首先遍歷左子樹,然後訪問根結點,最後遍歷右子樹;
(3)後序遍歷(lrd)首先遍歷左子樹,然後訪問遍歷右子樹,最後訪問根結點。
7 查找技術
順序查找的使用情況:
(1)線性表為無序表;
(2)表采用鏈式存儲結構。
二分法查找只適用於順序存儲的有序表,對於長度為n的有序線性表,最壞情況只需比較log2n次。
8 排序技術
排序是指將壹個無序序列整理成按值非遞減順序排列的有序序列。
交換類排序法:(1)冒泡排序法,需要比較的次數為n(n-1)/2; (2)快速排序法。
插入類排序法:(1)簡單插入排序法,最壞情況需要n(n-1)/2次比較;(2)希爾排序法,最壞情況需要o(n1.5)次比較。
選擇類排序法:(1)簡單選擇排序法,
最壞情況需要n(n-1)/2次比較;(2)堆排序法,最壞情況需要o(nlog2n)次比較。