羅德興老師的教學歷程檔案 - 112-2 資料結構 (2024年) - Unit 10 搜尋 (Searching)
 

企業資訊與管理系
助理教授/日導
羅德興

 歷程檔案 Portfolio

    Unit 10 搜尋 (Searching)


    一、範例與作業 10.1     循序搜尋

    import     random
    '''
    ex10.1-1 請修改以下程式，搜尋不到時，做適當顯示
    ex10.1-2 請修改以下程式，將自動產生10個亂數值 改由人手鍵入數值
    '''
    print("===============程式描述========================")
    print("= 程式名稱：ds-ex10.1(seq_search).ipynb                         =")
    print("= 程式目的：循序搜尋程式                       =")
    print("==============================================")
    A=[]
    def RandomNum():  #自動產生10個亂數值
      for i in range(1,11,1):
         A.append(random.randint(1,100))
      for i in range(0,len(A)):
          print(A[i],end="  ")
      print()  
    def Sequential_search(A,key):  #循序搜尋之副程式
      for i in range(0,10):        #從頭到尾拜訪一次
        if A[i] == key:       #比對陣列內的資料是否等於欲搜尋的條件
            print("陣列中的第 %d 筆" %(i+1))
    print("=======輸入(自動產生10個亂數值)========")
    RandomNum()              #呼叫產生10個亂數值的副程式
    key =int(input("請輸入欲搜尋資料："))
    print("=========輸出結果)==============")
    Sequential_search(A,key)














    二、範例與作業 10.2 Binary Search
    '''
    ex10.2-1 請修改以下程式，列出排序過程
    ex10.2-2 請修改以下程式，列出要搜尋的 健值，以及每次二元搜尋過程中的最低值、最高值，和中間值
    '''
    import random
    print("===============程式描述========================")
    print("= 程式名稱：ds-ex10.2(binarysearch).ipynb                          =")
    print("= 程式目的：二分法搜尋程式                     =")
    print("==============================================")
    A=[]
    def RandomNum():  #自動產生10個亂數值
      for i in range(1,11,1):
         A.append(random.randint(1,100))
      for i in range(0,len(A)):
          print(A[i],end="  ")
      print()  

    def search(A, Key):
        Low = 0
        High = len(A) - 1
        while Low <= High:
            Middle = (Low + High) // 2
            if A[Middle] < Key:
                Low = Middle + 1
            elif A[Middle] > Key:
                High = Middle - 1
            else:
                return Middle
        return -1
    print("=======輸入(自動產生10個亂數值)========")
    RandomNum()
    print("=======排序之後========")
    A.sort()
    for i in range(0,len(A)):
          print(A[i],end="  ")
    Key =int(input("請輸入欲搜尋資料："))
    find = search(A, Key)
    print("找到數值於索引 " + str(find) if find >= 0 else "找不到數值")



    三、

    搜尋 : 雜湊搜尋法

    (資料來源：http://puremonkey2010.blogspot.com/2010/12/blog-post_05.html)
     

    前言 :
    雜湊法這個主題通常被放在和搜尋法一起討論, 主要原因是雜湊法不僅被用於資料搜尋外, 在資料結構的領域中, 你還能將它用在資料的建立, 插入, 刪除與更新. 例如符號表在電腦上的應用很廣泛, 包含組譯程式, 編譯程式與資料庫使用的資料字典等, 都是利用提供的名稱來找到對應的屬性. 符號表依其特性可以分成兩類 : 靜態表 和動態表. 而雜湊表則是屬於靜態表的一種, 我們將相關資料與鍵值儲存在一個固定大小的表格中.

    雜湊法簡介 :
    基本上, 所謂雜湊法就是將本身的鍵值, 經由特定的數學運算或使用其他的方法, 轉換成相對應的資料儲存位址. 而雜湊所使用的數學函數就稱為 "雜湊函數". 現在我們來介紹有關雜湊函數的相關名詞 :
    * Bucket (桶) :
    雜湊表中儲存資料的位址, 每一個位置定應到唯一的一個位址 (Bucket Address). 桶就好像一筆記錄.

    * Slot (槽) :
    每一筆紀錄中可能包含好幾個欄位, 而Slot 就是指 "桶" 中的欄位.

    * Collision (碰撞) :
    若兩筆不同資料, 經過雜湊運算後, 對應到相同位址時, 稱為碰撞.

    * 溢位 :
    如果資料經過雜湊函數運算後, 所對應的 Bucket 已滿, 則會使 Bucket 發生溢位.

    * 雜奏表 :
    儲
    存紀錄的連續記憶體. 雜湊表是一種類似資料表的索引表格, 其中可分為 n 個 Bucket, 每個 Bucket 又可以分為 m 個 Slot, 如下圖所示 :

    * 同義字 :
    當兩個識別字 I1 及 I2, 經過雜湊函數運換後所得到的數值相同, 及 f(I1) = f(I2), 則稱 I1 與 I2 對於雜湊函數 f 是同義字.

    * 載入密度 (Loading Factor) :
    所謂載入密度是指識別字的使用數目除於雜湊表內槽的總數 :

    如果載入密度越大, 則表示雜湊空間的使用率越高, 碰撞或溢位的機率越高

    * 完美雜湊 :
    指沒有碰撞又沒有溢位的雜湊函數.

    在此建議在設計雜湊函數應遵循底下幾個原則 :


    1. 降低碰撞及溢位的產生.
    2. 雜湊函數不宜過於複雜, 越容易計算越佳.
    3. 盡量把文字的鍵值轉換成數字的鍵值, 以利雜湊函數的運算.
    4. 所設計的雜湊函數計算所得的值, 盡量能均勻分布在每一桶中. 不要過度集中在某些桶內, 這樣就可以降低碰撞與減少溢位的處理.






    三、範例與作業 10.3 Hashing (雜湊、碎映) Search

    '''
    ds-ex10.3(hash).ipynb by L.D.S on 2023/06
    本程式為建立雜湊表
    ex10.3-1 請修改以下程式，做雜湊搜尋，並列出每次的搜尋過程
    ex10.3-2 請修改以下程式，將 38~43 行的設定值 改由人手鍵入 資料
    '''

    # Function to display hashtable
    def display_hash(hashTable):
      print ('目前建立的雜湊表 \n')
      for i in range(len(hashTable)):
        print(i, end = " ")
       
        for j in hashTable[i]:
          print("-->", end = " ")
          print(j, end = " ")
         
        print()

    # Creating Hashtable as
    # a nested list.
    HashTable = [[] for _ in range(10)]

    # Hashing Function to return
    # key for every value.
    def Hashing(keyvalue):
      return keyvalue % len(HashTable)


    # Insert Function to add
    # values to the hash table
    def insert(Hashtable, keyvalue, value):
      print ('將 鍵值', keyvalue, '內容 ', value, '建到雜湊表中...\n')
      hash_key = Hashing(keyvalue)
      Hashtable[hash_key].append(value)

    # Driver Code
    insert(HashTable, 10, 'Allahabad')
    insert(HashTable, 25, 'Mumbai')
    insert(HashTable, 20, 'Mathura')
    insert(HashTable, 9, 'Delhi')
    insert(HashTable, 21, 'Punjab')
    insert(HashTable, 21, 'Noida')

    display_hash (HashTable)


    全部共 3則留言
    周育賢06-26 10:42:10-2https://colab.research.google.com/drive/1LhGhc6H5odFw2_P2KdrngR2WgofsRzdz
    周育賢06-26 10:43:10-1https://colab.research.google.com/drive/1PCmtDAqmLvD3THgw6ghhajpyZsLc6-3K
    廖翊如06-26 11:07:10-2https://colab.research.google.com/drive/15-kGtzmv_5Z-RQET2rgT6r7M7SMvknB6
    登入帳號密碼代表遵守學術網路規範

    		文章分類 Labels

    		最新文章 Top10

    中華科技大學數位化學習歷程 - 意見反應