第九節課：8.25：哈希
一、課前回顧：用c++的方式寫了單連結清單：
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//單連結清單：
/*
1.單連結清單由結點構成：資料資訊的資料域和存儲下一結點位置的指針域組成結點
2.有頭結點，頭結點不存儲資料資訊
3.一般有頭指針和尾指針分别指向第一個或者是最後一個結點
*/
template <class T>
class CMy_LinkList
{
struct node
{
T data;
node* pnext;
};
node* list_head_node;
public:
CMy_LinkList();
~CMy_LinkList();
void Print();
void clear();//删除整個連結清單
bool insert(T const& insert_data, size_t pos);
bool find(T const& find_data);
void init(size_t n);
bool del(size_t pos);
size_t getLength();//包含頭結點
};
template <class T>
void CMy_LinkList<T>::Print()
{
node* phead = list_head_node->pnext;
while (phead)
{
printf("%d ",phead->data);
phead = phead->pnext;
}
printf("\n");
}
template <class T>
void CMy_LinkList<T>::init(size_t length)
{
//先删除連結清單
clear();
//建立頭結點
if (list_head_node == nullptr)
{
list_head_node = new node;
if (list_head_node == nullptr)
return;
list_head_node->data = length;
}
//初始化時間種子
srand(time(0));//time(0)：從0時0分0秒開始經過了多少秒傳回去
//定義尾指針，用于尾插
node* prear = list_head_node;
//尾插法：
for (size_t i = 0; i < length - 1; i++)//除去一個頭結點
{
node* newnode = new node;
prear->pnext = newnode;//建立連接配接
prear = newnode;//尾指針移動到尾結點這裡是尾插法
newnode->data = rand()%100 + 1;//100以内的數
}
//插入結束，尾結點的指針域的值為nullptr
prear->pnext = nullptr;
}
template <class T>
bool CMy_LinkList<T>::find(T const& find_data)
{
node* pfirst = list_head_node -> pnext;
while (pfirst)
{
if (pfirst->data == find_data)
{
return true;
}
pfirst = pfirst->pnext;
}
return false;
}
/*
1.删除pos不合适，return false;
2.定義頭指針，便于周遊
2.周遊找到pos - 1位置的結點,用phead儲存
3.将要删除結點的位址儲存下來：ptemp = phead->pnext;
4.标準操作：phead->pnext = phead->next->next//指向删除結點的下一節點
5..标準操作：free(ptemp); ptemp = nullptr;
*/
template <class T>
bool CMy_LinkList<T>::del(size_t pos)
{
//删除位置不正确
if (pos < 1 || pos > getLength())
{
return false;
}
//定義頭指針便于周遊
size_t j = 0;
node* phead = list_head_node;
while (phead && j < pos - 1)
{
phead = phead->pnext;
}
//至此為止：phead指向pos - 1的位置
//删除結點前的保障工作
node* pdelete = phead->pnext;//将要删除結點的位址儲存下來
phead->pnext = pdelete->next;//指向删除結點的下一節點
delete pdelete;
pdelete = nullptr;
}
template <class T>
size_t CMy_LinkList<T>::getLength()//不包括頭結點
{
node* phead = list_head_node->pnext;
size_t count = 0;
while (phead)
{
phead = phead->pnext;
count++;
}
return count;
}
/*
1.插入pos不合适，return false;
2.這裡采用前插法，在pos前插入該節點
3.周遊找到pos - 1位置的結點,用pnow儲存
沒有找到該位置或者是找到尾結點結束了，
4.建立新結點newnode
5.标準操作：newnode->pnext = pnow->pnext; pnow->next = newnode;
6.插入完成
*/
template <class T>
bool CMy_LinkList<T>::insert(T const& insert_data, size_t pos)//前插法，插入pos前面
{
//插入位置不合适
if (pos < 1 || pos > getLength())//length不包括頭結點
{
return false;
}
//建立頭指針便于周遊
node* phead = list_head_node;//頭指針指向頭結點
size_t j = 0;
while (phead && j < pos - 1)//j=0,phead指向頭結點;j=1;指向第一個結點;剛好對應起來
{
phead = phead->pnext;
j++;
}
//至此為止：phead指向第pos - 1的結點的位置
//建立新結點
node* newnode = new node;
newnode->data = insert_data;
//标準插入操作：
newnode->pnext = phead->pnext;
phead->pnext = newnode;
return 1;
}
template <class T>
CMy_LinkList<T>::CMy_LinkList()
{
list_head_node = nullptr;
}
template <class T>
CMy_LinkList<T>::~CMy_LinkList()
{
clear();
}
//不删除頭結點
/*
1.隻有頭結點不用清空
2.建立一個指針pdelete儲存要删除的結點的位址
2.建立一個指針pnext_node儲存要删除的結點的下一個位址
3.删除該節點
4.接着往下删除，
*/
template <class T>
void CMy_LinkList<T>::clear()
{
//隻有頭結點，不用清空
if (list_head_node == nullptr)
return;
//要删除的節點總是頭結點後面的結點
node* pdelete = list_head_node -> pnext;
//儲存下一個要删除的結點的位址
node* pnext_node;
while (pdelete)
{
pnext_node = pdelete->pnext;
delete pdelete;
pdelete = pnext_node;//接着往下删除，如果為空，表明是尾結點，删除尾結點後，删除結束
}
list_head_node->pnext = nullptr;
list_head_node->data = 0;
}
二、哈希
1.定義：
哈希法是一種特殊查照方法，又名散列法，希望不通過任何比較，一次存取就能夠得到元素
2.怎麼去設計哈希表：
1.确定表的空間範圍，确定哈希值域
2.構造一個合适的哈希函數；這個函數要確定表中的元素經過該函數的計算之後，函數的傳回值的範圍在值域之内
3.選擇處理沖突的方法（用鍊式結構）
比如：一個遊戲道具的編号，第一個數字代表種類：0表示武器，1表示武器，2表示飾品；
而一把刀和一把槍的編号的第一個都是0，要進行沖突處理；連結清單。
3.哈希函數：定義好哈希函數是哈希表的設計的關鍵
1.自身函數
2.數字分析法（數字疊加法，數字求餘法）
4.哈希示例（c）
#include <stdio.h>
#include <string.h>
#define size 10
//節點
struct Node
{
int data;
Node* pnext;
};
//哈希表
struct Hash
{
Node* Hashtable[size];//0~9
};
//哈希函數
int GetVal(int data)
{
return data % 10;
}
//哈希表初始化函數
Hash* CreateTable()
{
Hash* ptable = new Hash;//40個位元組
for (size_t i = 0; i < size; i++)
{
ptable->Hashtable[i] = nullptr;
}
return ptable;
}
//哈希插入函數
bool Table_Insert(Hash* ptable, int insert_data)
{
//哈希表是否建立了？
if (ptable == nullptr)
return false;
//插入：1.無沖2.有沖突
//定義一個臨時的位置指針，pos,看即将要存的位置上面是否已經存有元素
Node* pos = ptable->Hashtable[GetVal(insert_data)];
Node* tempnode = new Node;
//1.無沖突
if (pos == nullptr)
{
tempnode->data = insert_data;
tempnode->pnext = nullptr;
//pos = tempnode;//函數結束後pos釋放，最終ptable->Hashtable[GetVal(insert_data)]還是nullptr
ptable->Hashtable[GetVal(insert_data)] = tempnode;
}
else//2.有沖突
{
while (pos->pnext)
{
pos = pos->pnext;
}
pos->pnext = tempnode;
tempnode->pnext = nullptr;
tempnode->data = insert_data;
}
return true;
}
//哈希查找函數
Node* Table_Find(Hash ptable, int find_data)//将目标值的位址指針拷貝過來
{
if (&ptable == nullptr) return nullptr;
//找到對應的表範圍：
Node* pos = ptable.Hashtable[GetVal(find_data)];
if (pos == nullptr)
{
return nullptr;
}
else
{
while (pos)
{
if (pos->data == find_data)
{
return pos;
}
pos = pos->pnext;
}
}
return nullptr;
}
//哈希删除單個值函數
bool Table_Del(Hash* ptable, int delete_data)
{
//該值不在表内：
Node* pos = Table_Find(*ptable, delete_data);
if (pos == nullptr)
return false;
//隻有一個節點
if (ptable->Hashtable[GetVal(delete_data)] == pos)
{
//要使執行pos的指針指派為空
ptable->Hashtable[GetVal(delete_data)] = nullptr;
delete[]pos;
pos = nullptr;
}
//中間的節點或者使最後的節點:重新周遊查找：
else
{
pos = ptable->Hashtable[GetVal(delete_data)];
while (pos ->pnext)//該沖突表的第二個節點,第一個節點為1，第二個節點為11
{
if (pos->pnext->data == delete_data)
{
break;
}
pos = pos->pnext;
}
//tempdelete儲存要删除的節點
Node* tempdelete = pos->pnext;
//第一個節點指向第三個節點
pos->pnext = tempdelete->pnext;
//删除第二個節點
delete[]tempdelete;
tempdelete = nullptr;
}
return true;
}
//哈希删除整個哈希表
bool Table_Clear(Hash* ptable)
{
if (ptable == nullptr) return false;
//
for (size_t i = 0; i < size; i++)
{
Node* phead = ptable->Hashtable[i];//頭指針
Node* pdelete;//要删除的節點
while (phead)
{
pdelete = phead;
phead = phead->pnext;//指向下一個要删除的節點
delete[] pdelete;
pdelete = nullptr;
}
ptable->Hashtable[i] = nullptr;
}
return true;
}
int main()
{
//Hash* table = CreateTable(table);//這裡傳參數時候會進行拷貝，但是table還沒有初始化
Hash* table = CreateTable();
printf("insert success = %d\n", Table_Insert(table, 1));
printf("insert success = %d\n", Table_Insert(table, 11));
printf("insert success = %d\n", Table_Insert(table, 111));
printf("%x\n",Table_Find(*table,2));
printf("delete success = %d\n", Table_Del(table, 11));
printf("clear success = %d\n", Table_Clear(table));
int a = 0;
return 0;
}
哈希示例：（c++）
#pragma once
#include <stdio.h>
/*
1.确定哈希表的範圍
2.設計好哈希函數，（數學分析法）使表中的資料用過計算之後能夠在值域範圍之内
也就是說，函數的傳回值在值域範圍内
3.處理好沖突（連結清單）
*/
class CMy_hash
{
struct Hash
{
int data;
Hash* pnext;
};
Hash* hash_arr[10];//這裡設計為0~9
public:
CMy_hash();
~CMy_hash();
void clear();
public:
void store(int arr[], int length);//存儲函數
bool find(int find_data);
void insert(int insert_data);//插入單個元素
bool del(int delete_data);
private:
int hash(int data);//哈希函數
Hash* _find(int find_data);//以後根據這個函數來做變化
};
#include "CMy_hash.h"
bool CMy_hash::del(int delete_data)//注意：自己的了解：如果删除操作較多的話，建議以空間換取時間，用雙向連結清單就可以免去找上一節點的時間
{
Hash* pos = _find(delete_data);//找到删除的節點
if (pos == nullptr) return false;
else
{
if (pos->pnext == nullptr)
{
delete pos;
pos = nullptr;
}
else
{
Hash* temp = hash_arr[hash(delete_data)];
while (temp->pnext != pos) temp = temp->pnext;//找到上一個節點
temp->pnext = pos->pnext;
delete pos;
pos = nullptr;
}
}
}
void CMy_hash::insert(int insert_data)
{
int index = 0;
//當沒有沖突時：
index = hash(insert_data);
//建立一個節點
Hash* tempnode = new Hash;
tempnode->data = insert_data;
tempnode->pnext = nullptr;
if (hash_arr[index] == nullptr)//空哈希表
{
hash_arr[index] = tempnode;
}
else
{
//找到最後一個節點開始存儲
Hash* temp = hash_arr[index];//第一個節點
while (temp->pnext) temp = temp->pnext;//找到temp為最後一個節點
//建立連接配接
temp->pnext = tempnode;
temp = nullptr;
}
}
bool CMy_hash::find(int find_data)
{
if (_find(find_data) == nullptr) return false;
else return true;
}
CMy_hash::Hash* CMy_hash::_find(int find_data)
{
int index = 0;
for (size_t i = 0; i < 10; i++)
{
index = hash(find_data);
if (hash_arr[index]->data == find_data)
{
return hash_arr[index];
}
else if (hash_arr[index]->pnext != nullptr)
{
Hash* temp = hash_arr[index]->pnext;
while (temp)
{
if (temp->data == find_data)
{
return temp;
}
temp = temp->pnext;
}
}
return nullptr;
}
}
void CMy_hash::store(int arr[], int length)
{
for (size_t i = 0; i < length; i++)
insert(arr[i]);
}
/*
哈希函數：傳回元素的值的個位數，按個位數大小找标号
*/
int CMy_hash::hash(int data)
{
return (data % 10);
}
CMy_hash::CMy_hash()
{
for (size_t i = 0; i < 10; i++)
{
hash_arr[i] = nullptr;
}
}
CMy_hash::~CMy_hash()
{
clear();
}
void CMy_hash::clear()
{
for (size_t i = 0; i < 10; i++)
{
if (hash_arr[i] != nullptr)
{
//從最後一個節點開始删除
Hash* temp_delete = hash_arr[i];//頭指針後面的第一個節點
Hash* temp_pnext;
while (temp_delete)
{
temp_pnext = temp_delete->pnext;
delete temp_delete;
temp_delete = temp_pnext;
}
}
}
}
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)