數據結構演算法實現及解析

A. 計算機考研：數據結構常用演算法解析(8)

第九章 查找
查找分成靜態查找和動態查找，靜態查找只是找，返回查找位置。而動態查找則不同，若查找成功，返回位置，若查找不成功，則要返回新記錄的插入位置。也就是說，靜態查找不改變查找表，而動態查找則會有插入操作，會改變查找表的。
不同的查找所採用的存儲結構也不同，靜態查找採用順序表，而動態查找由於經常變動，所以用二叉排序樹，二叉平衡樹、B-和B+。
靜態查找有，順序查找，折半查找，分塊查找(索引順序查找)
順序查找(Sequential Search)是最簡單的一種查找方法。
演算法思路
設給定值為k，在表(R1 R2……Rn)中，從Rn即最後一個元素開始，查找key=k的記錄。若存在一個記錄Ri(l≤i≤n)的key為k，則查找成功，返回記錄序號i;否則，查找失敗，返回0。
演算法描述
int sqsearch(sqlist r,keytype k) //對表r順序查找的演算法//
{ int i;
r.data[0].key=k; //k存入監視哨//
i=r.len; //取表長//
while(r.data[i].key!=k)
i--; //順序查找//
return(i);
}
演算法用了一點技巧：先將k存入監視哨，若對某個i(≠0)有r.data[i].key=k，則查找成功，返回i;若i從n遞減到1都無記錄的key為k，i再減1為0時，必有r.data[0].key=k，說明查找失敗，返回i=0。
平均查找成功長度ASL= ，而查找失敗時，查找次數等於n+l。
折半查找演算法及分析
當記錄的key按關系≤或≥有序時，不管是遞增的還是遞減的，只要有序且採用順序存儲。
演算法描述
int Binsearch(sqlist r,keytype k) //對有序表r折半查找的演算法//
{ int low,high,mid;
low=1;high=r.len; //上下界初值//
while(low<=high) //表空間存在時//
{ mid=(low+high)/2; //求當前mid//
if (k==r.data[mid].key)
return(mid); //查找成功，返回mid//
if (k
high=mid-1; //調整上界，向左部查找//
else
low=mid+1; //調整下界，向右部查找//
}
return(0); //low>high，查找失敗//
}
判定樹：用來描述二分查找過程的二叉樹。n個結點的判定樹的深度和n個結點的完全二叉樹深度相同= 。但判斷樹不一定是完全二叉樹，但他的葉子結點所在層次之差不超過1。所以，折半查找在查找成功時和給定值進行比較的關鍵字個數至多為
ASL=
分塊查找演算法及分析
分塊查找(Blocking Search)，又稱索引順序查找(Indexed Sequential Search)，是順序查找方法的一種改進，目的也是為了提高查找效率。
1.分塊
設記錄表長為n，將表的n個記錄分成b= 個塊，每塊s個記錄(最後一塊記錄數可以少於s個)，即：
且表分塊有序，即第i(1≤i≤b-1)塊所有記錄的key小於第i+1塊中記錄的key，但塊內記錄可以無序。
2.建立索引
每塊對應一索引項：
KeymaxLink
其中Keymax為該塊內記錄的最大key;link為該塊第一記錄的序號(或指針)。
3.演算法思路 分塊索引查找分兩步進行：
(1)由索引表確定待查找記錄所在的塊;(可以折半查找也可順序因為索引表有序)
(2)在塊內順序查找。(只能用順序查找，塊內是無序的)

考研有疑問、不知道如何總結考研考點內容、不清楚考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/

B. python數據結構與演算法-哈希map的實現及原理

1-collections.MutableMapping

1.1 概念：這是什麼？

大家可能想知道這一串英文是什麼意思？其實只需要了解在collections庫當中有一個非常重要的抽象基類MutableMappin

g，專門用於實現map的一個非常有價值的工具。後邊我們會用到它。

2-我們的map基類

2.1 實現這個類

這個基類其實也就是確定了鍵值對的屬性，並且存儲了基本的比較方法。它的對象就是一個鍵值對咯。這個很好理解。有點類似object的感覺。

3-通過map基類實現的無序映射

給大家看一個上邊的例子，這個例子來源於網路，自己改了改，能用，更加詳細而已，湊合看.

4-Python哈希表的實現的基類

4.1 咱有話直說：上才（代）藝（碼）

如果還不知道哈希表概念的同xio，請參考 python進階之數據結構與演算法–中級-哈希表（小白piao分享） 。廢話不多說，咱們擼代碼：

OK了，基本的哈希表就實現了，其實仔細想想很容易，但是自己要能實現還是要理解哈希表的本質哦，外加一定量的練習才可以熟練掌握，練習的目的就是為了熟練而已。

5-分離鏈表實現的具體哈希map類

說明：這玩意只是一種降低沖突的手段，上一節提過，降低沖突最好的地方是發生在元組進入桶的時候，所以想必大家猜到了，接下來的分離鏈表也就是為了self._bucket_xxxxxxx系列方法做准備。這里之所以在上邊使用@abstractmethod就是為了繼承實現，目的可以實現多種將沖突的哈希表。分離鏈表的概念上一節也有的。
「見碼入面」（借鑒：見字如面這個電視節目，有興趣可以看看，還不錯的）：

6-用線性探測處理沖突的哈希map類

這種方式的好處不需要再去藉助其他額外的賦值結構來表示桶。結構更加簡單。不會再像上一種方法還要讓桶是一個UnsortedTableMap的對象。
代碼如下：

C. 計算機考研：數據結構常用演算法解析(7)

第七章：
對於無向圖，e的范圍是：
數據結構中所討論的圖都是簡單圖，任意兩結點間不會有雙重的邊。
對於有向圖，e的范圍是：
圖的各種存儲結構
鄰接矩陣很方便訪問任意兩點的邊，但是不方便計算其鄰接點。在深度和廣度遍歷中廣泛的需要求某點的鄰接點。所以鄰接矩陣只在Floyed和Prim和Dijstra中採用。
鄰接表能很方便的求某頂點的鄰接點，索引對於與遍歷有關的演算法大多都採用鄰接表。如深度、廣度、拓撲排序、關鍵路徑。但他也有不足的地方，就是不方便求入度或是那些薯早握點可以到他的操作。所以有人引進逆鄰接表。最後人們把這兩種表結合到一起就是十字鏈表和鄰接多重表。一個是存儲有向圖，另一個是存儲無向圖。
在十字鏈睜歷表和鄰接多重表很方便求鄰接點的操作和對應的逆操作。所以實際應用中，凡是能用鄰接表實現的一定能用十字鏈表和鄰接多重表實現。並且它們的存儲效率更高。
1.鄰接矩陣(有向圖和無向圖和網)又稱為數組表示法
typedef struct
{ vextype vexs[maxn]; ∥頂點存儲空間∥
adjtype A[maxn][maxn]; ∥鄰接矩陣∥
int vexnum,arcnum; //圖的頂點數和邊數
GraphKind Kind; //圖的類型
} mgraph;
2.鄰接表(有向圖和無向圖和網)
typedef struct node ∥邊
{ int adj; int w; ∥鄰接點、權∥
struct node *next; ∥指向下一弧或邊∥
}linknode;
typedef struct ∥頂點類型∥
{ vtype data; ∥頂點值域∥
linknode *farc; ∥指向與本頂點關聯的第一條弧或邊∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥頂點表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
邊結點
datafirstarc
頂點結點
3.十字鏈表(有向圖和有向網)
headvextaivexhlinktlinkinfo
邊結點
datafirstinfirstout
頂點結點
4.鄰接多重表(無向圖)
markivexjvexilinkjlinkinfo
邊結點
datafirstedge
頂點結點
有向無環圖(DAG)：是描述含有公共子式的表達式的有效工具。二叉樹也能表示表達式，但是利用有向無環圖可以實現對相同子式的共享，從而節省存儲空間。
頂點的度：
無向圖：某頂點V的度記為D(V)，代表與V相關聯的邊的條數
有向圖：頂點V的度D(V)=ID(V)+OD(V)
強連通分量:在有向圖中，若圖中任意兩頂點間都存在路徑，則稱其是強連通圖。圖中極大 強連通子圖稱之為強連通分量
「極大」在這里指的是：往一個連通分量中再加入頂點和邊，就構不成原圖中的一個 連通子圖，即連通分量是一個最大集的連通子圖。有向圖的連通就是指該有向圖是強連通的。

考研有疑問、不知道如何總結考研考點內容、不清楚數慶考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/

D. 計算機考研：數據結構常用演算法解析(1)

數據結構是計算機考研408計算機學科專業基礎綜合的重要組成部分，考生需要認真復習，尤其是對於數據結構中一些常用的演算法問題，考生一定要弄懂弄會，理解的去掌握。獵考考研就帶大家一一梳理這些知識點。
第一章
◆ 數據：指能夠被計算機識別、存儲和加工處理的信息載體。
◆ 數據元素：就是數據的基本單位，在某些情況下，數據元素也稱為元素、結點、頂點、記錄。數據元素有時可以由若干數據項組成。
◆ 數據類型：是一個值的集合以及在這些值上定義的一組操作的總稱。
在高級語言程序中又分為：非結構的原子類型和結構類型
◆抽象數據類型(ADT)：是指一個數學模型以及定義在該模型上的一組操作。
一個抽象的數據類型的軟體模塊通常包含定義和表示和實現
用三元組(D，S，P)：數據對象、數據關系、基本操作
◆ 數據結構：指的是數據之間的相互關系，即數據的組織形式。一般包括三個方面的內容:
數據的邏輯結構、存儲結構和數據的運算。
◆ 邏輯結構：指各數據元素之間的邏輯關系。
◆ 存儲結構：就是數據的邏輯結構用計算機語言的實現。
◆ 線性結構：數據邏輯結構中的一類，它的特徵是若結構為非空集，則該結構有且只有一個開始結點和一個終端結點，並且所有結點都最多隻有一個直接前趨和一個直接後繼。線性表就是一個典型的線性結構。
◆ 非線性結構：數據邏輯結構中的另一大類，它的邏輯特徵是一個結點可能有多個直接前趨和直接後繼。
常用的存儲表示方法有四種:
◆ 順序存儲方法：它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的
邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構。
◆ 鏈接存儲方法：它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是
由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構。
◆ 索引存儲方法：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。

◆ 散列存儲方法：就是根據結點的關鍵字直接計算出該結點的存儲地址。
漸近時間復雜度的表示法T(n)=O(f(n))，這里的"O"是數學符號，它的嚴格定義是"若T(n)和f(n)是定義在正整數集合上的兩個函數，則T(n)=O(f(n))表示存在正的常數C和n0 ,使得當n≥n0時都滿足0≤T(n)≤C·f(n)。"用容易理解的話說就是這兩個函數當整型自變數n趨向於無窮大時，兩者的比值是一個不等於0的常數。這么一來，就好計算了吧。
求某一演算法的時間復雜度是關於N的統計，下面的例子很有反面意義
x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++;
◆ T(n)=O(1)
◇ 這個程序看起來有點嚇人，總共循環運行了1000次，但是我們看到n沒有? 沒。
◇ 這段程序的運行是和n無關的，就算它再循環一萬年，我們也不管他，只是一個常數階的函數。

考研有疑問、不知道如何總結考研考點內容、不清楚考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/