【自考】數據結構第六章查找,期末不掛科指南,第10篇

来源:https://www.cnblogs.com/happymeng/archive/2020/01/12/shujujiegou_10.html
-Advertisement-
Play Games

查找的一些基本概念 查找表 是由同一類型的 數據元素 構成的集合,它是一種以查找為“核心”,同時包括其他運算的非常靈活的數據結構。 上面概念中的集合和數學上的定義是一致的,簡單地說就是由任意一些可分辨的對象構成的整體 作為一個數學概念,集合的元素是沒有任何限制。 作為一種數據結構,查找表的邏輯結構是 ...


查找的一些基本概念

查找表 是由同一類型的數據元素 構成的集合,它是一種以查找為“核心”,同時包括其他運算的非常靈活的數據結構。

上面概念中的集合和數學上的定義是一致的,簡單地說就是由任意一些可分辨的對象構成的整體

作為一個數學概念,集合的元素是沒有任何限制。

作為一種數據結構,查找表的邏輯結構是集合,對查找表進行的操作包括 查找表中的某一元素讀取表中特定數據元素插入和刪除一個數據元素等。

若對查找表只進行前兩項操作,則稱此類查找表為 靜態查找表
若在查找過程中,向表中插入不存在的數據元素,或者從表中刪除某個數據元素,則稱此類查找表為動態查找表

靜態查找表

順序表上的查找

具體的代碼就不實現了,有興趣的可以自行查閱,主要說的是概念與邏輯

對於查找運算,其基本操作是“數據元素的鍵值與給定值的比較”,所以通常用“數據元素的鍵值與給定值的比較次數”作為衡量查找演算法好壞的依據,稱上述比較次數為查找長度。但是查找長度與鍵值在順序表中的位置有關,且差別很大。例如,若鍵值在順序表的第n個位置上,則查找長度為1,而如果鍵值在順序表的第1個位置上,查找長度為n。

基於上述內容引入一個新的概念,叫做“查找成功時的平均查找長度(記作ASL)”

它的定義是這樣的:為找到數據元素在查找表中的位置,與給定值進行比較的鍵值個數的期望值。
當查找表有n個元素時,有

$$ASL=\sum_{r=1}^nP_iC_i$$

其中P~i~為查找第i個元素(即給定值key與順序表中第i個元素的鍵值相等)的概率,且$\sum_{r=1}^nP_i=1$,C~i~表示在找第i個元素時,與給定值已進行比較的鍵值個數。

假設順序表為(b~1~,b~2~,b~3~)查找b~1~,b~2~,b~3~的概率分別是0.2,0.2,0.6,則順序查找法的平均查找長度為 $0.2 * 3+0.22+0.61 = 1.6$ 即平均需要1.6 次鍵值與給定值的比較才能找到待查元素。

由於多種元素P~i~值不好確定,所以通常讓P~i~概率相等,即對所有的i,有 $P_i =\frac{1}{n}$,併在此假設下確定查找演算法的平均查找長度。

$$ASL=\sum_{r=1}^nP_iC_i=\sum_{r=1}^n\frac{1}{n}*(n-i+1)=\frac{n+1}{2}$$

上述內容記住結論即可。

有序表上的查找

如果順序表中數據元素是按照鍵值大小的順序排列的,則稱為有序表。

這種存儲結構,查找運算可以用效率更高的二分查找法

直接看例題即可

現在有一個含有9個數據元素的有序表(關鍵字即為數據元素的值)
(10,13,17,20,30,55,68,89,95)用二分查找演算法查找key=17的過程

第一步,找到查找區間,合計9個數據元素,那麼[1,9]就是區間
(1+9)/ 2 = 5
找到位置5的數據元素30,30>17 進入第二步

第二步,縮小查找區間,合計4個數據元素,那麼[1,4]就是區間
(1+4)/ 2 = 2.5 去尾法 等於2
找到位置2的數據元素13,13<17 進入第三步

第三步,縮小查找區間,那麼[3,4]就是區間
(3+4) / 2 = 3.5 去尾法 等於3
找到位置3的數據元素17,正好是待查元素,查找成功,返回結果為mid=3

索引順序表上的查找

索引順序表由兩部分組成:一個索引表和一個順序表
其中 順序表在組織形式上與普通的順序表完全相同,而索引表本身在組織形式上也是一個順序表。
索引表通過索引將順序表分割為若幹塊,而順序表呈現出“按塊有序”的形式

若靜態查找表用索引順序表表示,則查找操作可用分塊查找來實現,也稱為 索引順序查找
分為兩步進行:
(1)先確定待查數據元素所在的塊
(2)然後在塊內順序查找

結論:
靜態查找表 有順序查找、二分查找、分塊查找
三種特點分別為:

  1. 順序查找效率最低但限制最少
  2. 二分查找效率最高,但限制最多
  3. 分塊查找介於上述二者之間

二叉排序樹

一棵二叉排序樹(又稱二叉查找樹)具備如下性質

  1. 若它的左子樹不空,則左子樹上所有結點的鍵值均小於它的根結點鍵值;
  2. 若它的右子樹不空,則右子樹上所有結點的鍵值均小於它的根結點鍵值;
  3. 根的左、右子樹也分別為二叉排序樹。

二叉排序樹的案例如下圖所示
數據結構自考

關於二叉排序樹,教材中涉及了部分代碼,分別如下

  1. 二叉排序樹上的查找
  2. 二叉排序樹上的插入

二叉排序樹的查找分析

需要記住的一些小點如下

二叉排序樹上的平均查找長度是介於O(n)和O($\log_2n$)之間。

以下兩個樹的平均查找長度分別為

數據結構自考

散列表

一些基本概念要普及一下

數據元素的鍵值和存儲位置之間建立的對應關係H成為散列函數
用鍵值通過散列函數獲取存儲位置的這種存儲方式構造的存儲結構成為散列表,這一映射過程稱為散列
如果選定了某個散列函數H及其對應的散列表L,則對每個數據元素X,函數值H(H.Key)就是X在散列表L中的存儲位置,這個存儲位置也稱為散列地址。

常用的散列法

構造散列函數的方法,瞭解一下

  1. 數字分析法
  2. 除留餘數法
  3. 平方取中法
  4. 基數轉換法

散列表的實現(自考必考,不是考代碼,是考方法)

線性探測法

直接用例題與動畫來解釋吧

題目要求

設散列表長度為11,散列函數H(key) = key mod 11(mod為求餘運算),給定的健值序列為(3,12,13,27,34,22,38,25),試畫出採用線性探測法解決衝突時所構造的散列表,並求出在等概率的情況下查找成功時的平均查找長度。

數據結構自考

線性探測法 就是 求餘數,然後放到對應的位置上,如果位置上有數據元素了,那麼就向後移動,移動到沒有數據元素的位置上,然後占坑

平均查找長度 ASL 就是把元素查找次數加起來總和/散列表長度 = 16/11

二次探測法

二次探測法,核心在於二次上,說白了,就是當你取餘得到的位置由數據元素的時候,需要進行二次的偏移探測

例如,還是上述的題目,當計算到34的時候,發現位置1已經有元素了,接下來就要進行二次探測了

用1的位置分別進行+1^2^,-1^2^,+2^2^,-2^2^...

第一步,探測1+1^2^ = 2 ,位置2是否存在元素,發現有
第二步,探測1-1^2^ = 0,位置0是否存在元素,發現無,那麼好,把34放在位置0那裡,假設位置0也有元素了
第三步,探測1+2^2^ = 5,位置5是否存在元素,發現無,把34放過去。

鏈地址探測法

可以通過一個案例來簡單說明一下

選定一個散列函數H(key) = key mod 13 ,鍵值為26,41,25,05,07,15,12,49,51,31,62

然後我們把求到的餘數,依次對應到鄰接表裡面,如下圖(直接截取教材圖了,就不畫了)

數據結構自考

公共溢出區法(選看)

更多圖示: https://dwz.cn/r4lCXEuL

小結

本章在自考或者期末考試中,核心內容是二分查找方法;二叉排序樹的構建,散列表的查找方法,重點會考察線性探測法和二次探測法,重點看一下吧。

BYEBYE~


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 前提 cat命令是用於連接文件並輸出到標準輸出設備或指定文件中。 EOF為標誌,可以替換為其他字元串 代碼塊 將文件內容作為標準輸出也就是將文件內容輸出到屏幕中,也可寫作 cat filename cat filename 創建文件,將2個EOF中的字元串作為標準輸入輸出到filename文件中 c ...
  • 前提 AWK是一種處理文本文件的語言,是一個強大的文本分析工具。 本文將使用命令awk將具有某個關鍵字的段落提取出來。 準備數據 段落提取 假設我們需要的關鍵字為 nid=0x63ef ...
  • 部署圖書管理系統項目 部署準備 部署圖書管理項目你將使用以下軟體 nginx uWSGI CentOS7 部署圖書管理項目文件 virtualenv supervisor WSGI、uWSGI python web伺服器開發使用WSGI協議(Web Server Gateway Interface) ...
  • ArchLinux下electronssr無法啟動的解決措施 今天重新配置electron ssr時發現閃退(無法啟動)。 於是開始查錯 首先是找到了目錄位置 /usr/electron ssr/electron ssr 並且嘗試在終端里啟動它。 發現缺少 python2 , 安裝 python2 ...
  • 最近在滴滴雲上看到伺服器很便宜,1核2G,1年只需要68塊錢。下麵是我基於Docker部署Javaweb服務的過程。目前我見過的最便宜的伺服器,阿裡雲打折的時候都沒有這麼便宜啊,果斷入手。有需要的話可以通過下麵鏈接購買。 滴滴雲全線標準型雲伺服器限時特惠,新購雲服務包1個月5折,包3個月4折,包6個 ...
  • 部署gitlab 1、配置倉庫源 # vim /etc/apt/sources.listdeb http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiverse deb-src http://mirrors.al ...
  • 背景 By 魯迅 By 高爾基 說明: 1. Kernel版本:4.14 2. ARM64處理器,Contex A53,雙核 3. 使用工具:Source Insight 3.5, Visio 1. 概述 ,連續記憶體分配器,用於分配連續的大塊記憶體。 ,會Reserve一片物理記憶體區域: 1. 設備驅 ...
  • NAS之NFS 為集群中的 Web Server 配置後端存儲NFS:Network File System 網路文件系統,Unix系統之間共用文件的一種協議NFS 的客戶端主要為Linux支持多節點同時掛載以及併發寫入 nas 192.168.122.59web1 192.168.122.85we ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...