資料結構概念篇

工作已經找好,看到以前的學習筆記竟然有人看,就把記憶中(過了3個月,不知道記得多少)的自己筆試面試中碰到過,與朋友碰到的重點內容相關的題註釋在旁邊,希望對大家面試有用。只是個人觀點和經驗

(好久沒有寫部落格了,近期開始找工作,想把以前學過的課程複習一下,把大綱和基本的概念記下,方便後面的複習。)


1、緒論

資料結構的內容:邏輯結構、儲存結構、運算集合。
資料型別:一個值的集合和定義在此集合上的一組操作的總稱。
抽象資料型別:abstract data type,使用者經行軟體設計時從問題的數學模型中抽象出來的邏輯資料結構和邏輯資料結構上的運算,而不考慮計算機具體儲存結構和運算的具體實現演算法。此模組包含定義、表示和實現。也就是資料物件的定義、資料關係的定義、基本操作的定義。

演算法特徵:有窮性、確定性、可行性、輸入、輸出
演算法設計的要求:正確性、可讀性、健壯性、高效率和低儲存的要求。
時間複雜度,空間複雜度。給一個程式要會算,常考。
這裡寫圖片描述

2、線性表

筆試面試重點 :
筆試選擇題經常出,要牢記順序表和連結串列的定義、性質、優缺點,考題很活但不難;
程式設計題面試筆試都會有:有頭結點和無頭結點的連結串列的反轉、2個連結串列或陣列的合併、3個陣列歸併……

定義:一個線性表示具有n個資料元素的有限序列
特點:同一性、有窮性、有序性
順序表特點

  • 無需為表示元素間的邏輯關係而增加額外的儲存空間
  • 可隨機取表的任一個元素
  • 插入或刪除元素,需平均移動表的一半元素。
  • 儲存分配只能預先進行分配
  • 將2個各有n個元素的有序表歸併為一個有序表,其最少的比較次數是:n

線性錶鏈式儲存結構的特點:

  • 任意的儲存單元儲存元素,不要去邏輯上相鄰的元素在物理位置上也相鄰。
  • 插入刪除時不需要移動大量元素
  • 失去順序表可隨機存取的優點

靜態連結串列(陣列表示和實現)

  • 在單連結串列中,不能從當前結點出發訪問到任一結點。
  • 刪除某一結點,必須找到該結點的前驅結點
  • 此結構是一種順序存取的存取結構,不具有隨機訪問任一元素的特點。
  • 設定頭結點的作用,使用在連結串列的第一個位置上的操作和表中其他位置上的操作一致,無需進行特殊處理,對空表和非空表的處理統一。

其他連結串列: 迴圈連結串列、雙連結串列要了解

3、限定性線性表——棧和佇列

筆試面試重點 :
筆試選擇題經常出,一般都是從佇列的進出順序上做文章;
程式設計題一般出在筆試,相對難一點:如迷宮、深搜、廣搜

  • 棧是一種具有線性結構的資料結構,是操作受限的線性表
  • 棧的特點是後進先出,只能在棧頂進行插入和刪除操作,入棧、出棧
  • 順序棧中,棧空標誌:S.top=S.base;
    棧滿標誌:S.top-S.base>=S.stacksize;
  • 鏈棧中,不設頭結點,頭結點就是棧頂指標,棧空S=NULL。
  • 用於:數值轉換,括號匹配檢驗、行編輯程式,迷宮問題、算數表示式求值(2個棧),遞迴的實現

遞迴(演算法設計方法):後呼叫先返回

 特點:分而知之、把複雜問題分解為簡單問題的求解方法;時間效率低。

佇列

  • 一種具有線性結構的資料結構,是操作受限的線性表;
  • 先進先出,只能在隊尾插入元素和隊頭刪除元素,稱為入佇列和出佇列;
    隊滿標誌:(Q.rear 1)%MAXOQSIZE==Q.front
  • 鏈佇列中,隊空標誌:Q.front=Q.rear
    空間範圍內不會出現隊滿的情況。
  • 其他,瞭解定義:雙端佇列、輸出受限的雙端佇列,輸入受限的雙端佇列

4、串

筆試重點 :
筆試選擇題:好像有運算元串的個數吧,方正不多;
程式設計題筆試偏多偏簡單,算送分題多,就是那種一版會程式設計的讀了題就能做的,eg,字串區域性位旋轉,單詞顛倒等

(字串):是零個或多個字元組成的有限序列,一般記為S=‘a1a2…..an’,屬於取值受限的線性表
子串:串中任意個連續的字元組成的子序列稱為該串的子串。“ ϕ\phi ”為任意串的子串。
主串:包含子串的串相應地稱為主串
位置:字元在串中的序號稱為該字元在串中的位置。
串相等:只有兩個串的長度相等,且每個對應的字元都相等時才相等。
空格串:由一個或多個空格組成的串,非空串。

儲存

  • 定長順序串:儲存分配是在編譯時完成的,用一組地址連續的儲存單元儲存串的字元序列。(開始下標:0,;結束標誌字“\0”)
  • 堆分配儲存(堆串),用稱為“堆”的自由儲存空間,並可用malloc()和free()函式完成動態儲存管理。
  • 串的塊鏈儲存表示(連結串列)這裡寫圖片描述

串的模糊匹配演算法:樸素模式匹配演算法(Brute-Force演算法,簡單匹配演算法)、KMP演算法

5、陣列和廣義表

見過相關的選擇題,出的不多,瞭解概念就好
陣列定義:n(n>1)個相同型別資料元素a0,a1,…,an-1構成的有限序列,且該有限序列儲存在一塊地址連續的記憶體單元中。是線性表在元素上的擴充套件。
矩陣的壓縮儲存:特殊儲存(對稱矩陣、三角矩陣、對角矩陣)

廣義表
定義:是線性表的推廣,是由零個或多個單元素或子元素所組成的有限序列
廣義表的長度:表中所含元素的個數n
廣義表的深度:廣義表展開後所含的括號的最大層數
表頭:非空時,稱第一個元素a1為廣義表的表頭,可能是原子,也可能是廣義表;
表位:其餘元素組成的表(a2,a3…….an)稱為廣義表的表尾,一定是廣義表。
儲存:頭尾連結串列儲存表示、擴充套件線性儲存表示、

6、樹

筆試重點 :
筆試選擇題:考題種類多,主要集中在遍歷方法和二叉樹上;
程式設計題筆試多,遍歷樹,構建二叉樹,早最長路徑,找公共祖先,找葉子結點等,多刷刷leetcode就好

定義:n(n>0)個結點的有限制,n==0為空樹;非空樹滿足(有且只有一個特定的稱為root的結點,其餘n-1個結點可以劃分成m個互不相交的有限集,沒一部分又是一棵樹)
表示方法:樹形表示法;文氏圖表示法;凹入表示法;括號表示法(廣義表表示法)
基本術語:結點,結點的度,樹的度,葉子,分支結點,孩子、雙親、兄弟、堂兄弟,路徑與路徑長度,結點的祖先和子孫,層次與高度,有序樹和無序樹,森林。
儲存:雙親表示法、孩子表示法、孩子兄弟表示法
遍歷方法:先根遍歷、後跟遍歷

二叉樹

要求:每個結點的度都不大於2,每個結點的孩子結點次序不能任意顛倒。
性質

  • 二叉樹的第i層至多有2i-1個結點
  • 深度為k 的二叉樹至多有2k-1個結點
  • 對任意一個二叉樹,若終端結點數為n0,度為2的結點數為n2,則n0=n2 1。
  • 具有n個結點的完全二叉樹的深度為

特殊樹:滿二叉樹,完全二叉樹
儲存:順序儲存,鏈式儲存結構

森林

(多顆樹組成森林)
遍歷方法:先根遍歷、後跟遍歷
哈夫曼樹:最小帶權路徑長度的二叉樹稱為哈夫曼樹。
路徑長度:一個結點到另一個結點之間的分支數目稱為路徑長度。
樹的路徑長度(樹根到每個結點的路徑長度之和),結點的權,帶權路徑長度
樹的帶權路徑長度WPL:樹中所有葉子結點的帶權路徑長度之和。
注意

  • 給定樹的先根遍歷序列和後根遍歷序列可唯一畫出一棵樹。
  • 給定森林的先序遍歷序列和中序遍歷序列可唯一確定一森林
  • 任何n個不同結點的二叉樹,都可以由它的中序序列和先序序列(中序和後序)唯一地確定

7、圖

筆試重點 :
筆試選擇題:考題種類多,像遍歷、拓撲結構,關鍵路勁等;
面試中被問過概念:關鍵路徑和最短路徑的區別
程式設計題很少有,記得在微軟的上機筆試中見過,

定義:兩個集合V、E組成,記為G=(V,E),其中V是頂點的有限集合,E是連線V中兩個不同頂點(頂點對)的邊的有限集合,記為E(G)。
基本術語:完全圖、稀疏圖、稠密圖、子圖、頂點的度(入度、出度)、權與網、路徑和圖、連通圖、強連通圖(來回都連通)、連通分量等
儲存結構:鄰接矩陣表示法(陣列表示法)、鄰接表儲存方法、十字連結串列(有向圖的鄰接表和逆鄰接表結合在一起)、鄰接多重表
遍歷:深度優先搜尋、廣度優先搜尋

最小生成樹
– prim演算法,從點出發,每次遍歷,在連通的邊中尋找權值最小的邊。
– Kruskal演算法,從邊出發,每次尋找權值最小的且不會生成圖的邊。

AVO網:用頂點表示活動,邊表示活動的順序關係的有向圖稱為AOV網。
拓撲排序:在一個有向圖中找一個拓撲序列(當且僅當該頂點序列滿足: 若<vi,vj>是圖中的弧,則在序列中頂點vi必須排在頂點vj之前)的過程稱為拓撲排序。
關鍵路徑:從源點(唯一的入度為0的點)到匯點(出度為0的點)的最長路徑路徑的長度即為完成整個工程任務所需的時間,該路徑叫做關鍵路徑。
最短路徑
– Dijkstra(迪傑斯特拉),貪心演算法,按路徑長度遞增的次序產生最短路徑。
– Floyd(弗洛伊德) D(k) [i][j] = Min { D(k-1)[i][j], D(k-1)[i][k] D(k-1)[k][j] }, k = 0,1,…, n-1

8、動態儲存管理

新使用者請求分配記憶體:一,系統繼續從地址的空閒中分配地址,直到無法分配,才回收不在使用的空閒塊。二,執行結束,就把它所佔的記憶體釋放成空閒塊。
分配策略:首次擬合發,最佳擬合法(適用最廣),最差擬合法。

9、查詢

面試筆試重點 :
筆試選擇題、簡答題都有,要會畫查詢的雜湊表、會計算平均查詢時間;
面試程式設計:折半查詢;
面試經常考:可能因為我研究生的方向是與資料查詢有關的,經常被問到解決雜湊衝突的方法,問的細了,還問各個的優缺點,一般何時用

基本術語:檔案,記錄、欄位(資料的最小單位)、關鍵字、主關鍵字、次關鍵字
靜態查詢表:查詢某個特定的元素是否在表中;檢索某個特定的元素的各種屬性。查詢方法為 順序查詢、折半查詢、索引順序表查詢
動態查詢表:若在查詢的同時對錶做修改運算(如插入和刪除)

  • 二叉排序樹,有序表,和折半查詢類似;中序遍歷此樹得到有序序列
  • 平衡二叉樹,二叉排序樹中每個結點的左、右子樹的高度至多相差1。
  • B樹:多路平衡查詢樹,一種組織和維護外存檔案系統非常有效的資料結構。B-樹的查詢過程是一個順指標查詢結點和在結點的關鍵字中進行查詢交叉進行的過程。B 樹是B-樹的一種變形,應用更普遍。
    平均查詢長度ASL:確定資料元素在表中的位置,需和給定值進行比較的關鍵字個數的期望值 。

雜湊表

  • 別名:雜湊法,雜湊法或關鍵字地址計演算法等,稱為雜湊表或雜湊表。
  • 基本思想,p=H(key),H稱為雜湊函式,是從關鍵字空間到儲存地址空間的一種對映。
  • 構造方法:直接定地址法、數字分析法、平方取中法、摺疊法、除留餘數法、偽隨機數法
  • 處理衝突的方法:開放地址法(線性探測再雜湊,二次探測再雜湊,隨機探測在雜湊)、在hash法、建立公共溢位區、鏈地址法

10、排序

面試筆試重點,重中之重呀!!!!! :
筆試選擇題:一般偏概念,要熟練各個排序演算法的步驟、時間複雜度、空間複雜度、穩定性、會算移動次數等;
面試經常考:現場程式設計,讓寫過遞迴與非遞迴的快排、遞迴與非遞迴的歸併排序、堆排序,所以這章真的真的很重要

概念:將一組雜亂無章的資料按一定的規律順序排列起來,使之按關鍵字遞增(0或遞減)有序排列。瞭解穩定排序的意義
排序時間開銷:演算法執行中關鍵字比較次數和記錄移動次數來衡量。
內部排序:待排序記錄存放在計算機隨機儲存中進行的排序過程。
外部排序:待排序記錄數量大,在排序過程中尚需對外存進行訪問的排序過程。
方法分類
這裡寫圖片描述

插入排序:將待排序記錄按其關鍵字大小插入到前面已經排好序的子表中的適當位置,知道全部插入完全為止。包括:直接插入排序、折半插入排序、2-路插入排序、表插入排序、希爾排序(縮小增量排序,多趟)。主要應用“比較”和“移動”。
交換排序:通過不斷比較相鄰元素大小,進行交換來實現排序。氣泡排序、快排。
選擇排序:每一趟都選出一個最大或最小的元素,並放在合適的位置。有簡單選擇排序、樹形選擇排序、堆排序。
歸併排序:將2個或兩個以上的有序表合成一個新的有序表。
基數排序:通過“分配”和“收集”過程來實現排序,是一種藉助於多關鍵字排序的思想對單關鍵字排序的方法。包括多關鍵字排序,鏈式基數排序,
各個排序演算法比較
這裡寫圖片描述