拉鏈法哈希函數c語言

① hash函數的構造方法

常用的構造哈希（hash）函數的方法有：直接定址法、數字分析法、平方取中法、折疊法、除留余數發、隨機數法。

1、直接定址法

取關鍵字或關鍵字的某個線性函數值為哈希地址。即：H(key)=key或H(key)=akey+b。其中a和b為常數（這種哈希函數叫做自身函數）。

2、數字分析法

假設關鍵字是以r為基的數（如：以10為基的十進制數），並且哈希表中可能出現的關鍵字都是事先知道的，則可取關鍵字的若干數位組成哈希地址。

3、平方取中法

取關鍵字平方後的中間幾位為哈希地址。這是一種較常用的構造哈希函數的方源旅法。通常在選定哈希函數時不一定能知道關鍵字的全部情況，取其中哪幾位也不一定合適，而一個數平方後的中間幾位數和數的每一位都相關。

4、折疊法

將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為哈希地址，這方法稱為折疊法（folding)。關鍵字位數很多，而且關鍵字中每一－位上數字分布大致均勻時，可以採用折疊法得到哈希地粗裂芹址。

5、除留余數發

取關鍵字被某個不大於哈希表表長m的數p除後所得余數為哈希地址。即H(key) = key MOD p, pm。這是一種最簡單，也最常用的構造哈希函數的方法。它不僅可以對關鍵字直接取模（MOD),也可在折疊，平方取中等運算之後取模。

6、隨機數法

選擇一個隨機函數，取關鍵字的隨機函數值為它的哈希地址，即H(key)=random(key),其中random為隨機函數。通常﹐當關鍵字長度不等時採用此法構造哈希函數較恰當。

沖突的處理：

哈希表中，不同的關鍵字值對應到同一個存儲位置的現象。即關鍵字K1≠K2，但H（K1）＝H（K2）。均勻的哈希函數可以減少沖突，但不能避免沖突。發生沖突後，必須解決；也即必須尋找下一個可用地址，解決沖突的方法：

1、鏈接法（拉鏈法）：將具有同一散列地址的記錄存儲在一條線性鏈表中。例，除留余數法中，設關鍵字為（18,14,01,68,27,55,79），除數為13，散列地址為（5,1,1,3,1,3,1）。

2、開放定址法岩畢：如果h(k）已經被佔用，按如下序列探查：（h(k)+p⑴）％TSize,(h(k)+p⑵）％TSize，…，（h(k)+p(i))%TSize，…其中，h(k)為哈希函數，TSize為哈希表長，p(i）為探查函數。

在h(k)+p(i-1)）％TSize的基礎上，若發現沖突，則使用增量p(i)進行新的探測，直至無沖突出現為止。

根據探查函數p(i）的不同，開放定址法又分為線性探查法（p(i) = i : 1,2,3，…），二次探查法（p(i)=(-1)^(i-1)*((i+1)/2)^2，探查序列依次為：1, -1,4, -4, 9…）。

隨機探查法（p(i):隨機數），雙散列函數法（雙散列函數h(key)，hp (key）若h(key）出現沖突，則再使用hp (key）求取散列地址。探查序列為：h(k),h(k)+ hp(k），…，h(k)+ i*hp(k））。

3、桶定址法：桶為一片足夠大的存儲空間。桶定址為表中的每個地址關聯一個桶。如果桶已經滿了，可以使用開放定址法來處理。例如，插入A5,A2,A3,B5,A9,B2,B9,C2，採用線性探查法解決沖突。

② c語言 數據結構中解決沖突的方法是什麼

可以參考如下方法：

1 基本原理
使用一個下標范圍比較大的數組來存儲元素。可以設計一個函數（哈希函數， 也叫做散列函數），使得每個元素的關鍵字都與一個函數值（即數組下標）相對應，於是用這個數組單元來存儲這個元素；也可以簡單的理解為，按照關鍵字為每一個元素"分類"，然後將這個元素存儲在相應"類"所對應的地方。
但是，不能夠保證每個元素的關鍵字與函數值是一一對應的，因此極有可能出現對於不同的元素，卻計算出了相同的函數值，這樣就產生了"沖突"，換句話說，就是把不同的元素分在了相同的"類"之中。後面我們將看到一種解決"沖突"的簡便做法。
總的來說，"直接定址"與"解決沖突"是哈希表的兩大特點。

2 函數構造
構造函數的常用方法（下面為了敘述簡潔，設 h(k) 表示關鍵字為 k 的元素所對應的函數值）：
a) 除余法：
選擇一個適當的正整數 p ，令 h(k ) = k mod p
這里， p 如果選取的是比較大的素數，效果比較好。而且此法非常容易實現，因此是最常用的方法。
b) 數字選擇法：
如果關鍵字的位數比較多，超過長整型範圍而無法直接運算，可以選擇其中數字分布比較均勻的若干位，所組成的新的值作為關鍵字或者直接作為函數值。

3 沖突處理
線性重新散列技術易於實現且可以較好的達到目的。令數組元素個數為 S ，則當 h(k) 已經存儲了元素的時候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲單元為止（或者從頭到尾掃描一圈仍未發現空單元，這就是哈希表已經滿了，發生了錯誤。當然這是可以通過擴大數組范圍避免的）。

4 支持運算
哈希表支持的運算主要有：初始化(makenull)、哈希函數值的運算(h(x))、插入元素(insert)、查找元素(member)。
設插入的元素的關鍵字為 x ，A 為存儲的數組。
初始化比較容易，例如
const empty=maxlongint; // 用非常大的整數代表這個位置沒有存儲元素
p=9997; // 表的大小
procere makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函數值的運算根據函數的不同而變化，例如除余法的一個例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
我們注意到，插入和查找首先都需要對這個元素定位，即如果這個元素若存在，它應該存儲在什麼位置，因此加入一個定位的函數 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//當這個循環停下來時，要麼找到一個空的存儲單元，要麼找到這個元
//素存儲的單元，要麼表已經滿了
locate:=(orig+i) mod S;
end;
插入元素
procere insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函數的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即為發生了錯誤，當然這是可以避免的
end;
查找元素是否已經在表中
procere member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;
這些就是建立在哈希表上的常用基本運算。

4.1 應用的簡單原則
什麼時候適合應用哈希表呢？如果發現解決這個問題時經常要詢問："某個元素是否在已知集合中？"，也就是需要高效的數據存儲和查找，則使用哈希表是最好不過的了！那麼，在應用哈希表的過程中，值得注意的是什麼呢？
哈希函數的設計很重要。一個不好的哈希函數，就是指造成很多沖突的情況，從前面的例子已經可以看出來，解決沖突會浪費掉大量時間，因此我們的目標就是盡力避免沖突。前面提到，在使用"除余法"的時候，h(k)=k mod p ，p 最好是一個大素數。這就是為了盡力避免沖突。為什麼呢？假設 p=1000 ，則哈希函數分類的標准實際上就變成了按照末三位數分類，這樣最多1000類，沖突會很多。一般地說，如果 p 的約數越多，那麼沖突的幾率就越大。
簡單的證明：假設 p 是一個有較多約數的數，同時在數據中存在 q 滿足 gcd(p,q)=d >1 ，即有 p=a*d , q=b*d, 則有 q mod p= q - p* [q div p] =q - p*[b div a] . ① 其中 [b div a ] 的取值范圍是不會超過 [0，b] 的正整數。也就是說， [b div a] 的值只有 b+1 種可能，而 p 是一個預先確定的數。因此 ① 式的值就只有 b+1 種可能了。這樣，雖然mod 運算之後的余數仍然在 [0，p-1] 內，但是它的取值僅限於 ① 可能取到的那些值。也就是說余數的分布變得不均勻了。容易看出， p 的約數越多，發生這種余數分布不均勻的情況就越頻繁，沖突的幾率越高。而素數的約數是最少的，因此我們選用大素數。記住"素數是我們的得力助手"。
另一方面，一味的追求低沖突率也不好。理論上，是可以設計出一個幾乎完美，幾乎沒有沖突的函數的。然而，這樣做顯然不值得，因為這樣的函數設計很浪費時間而且編碼一定很復雜，與其花費這么大的精力去設計函數，還不如用一個雖然沖突多一些但是編碼簡單的函數。因此，函數還需要易於編碼，即易於實現。
綜上所述，設計一個好的哈希函數是很關鍵的。而"好"的標准，就是較低的沖突率和易於實現。

③ 哈希查找演算法

散列表（Hash table，也叫哈希表），是根據鍵（Key）而直接訪問在內存存儲位置的數據結構。也就是說，它通過計算一個關於鍵值的函數，將所需查詢的數據映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數稱做散列函數，存放記錄的數組稱做散列表。

通過某種轉換關系，使關鍵字適度的分散到指定大小的的順序結構中，越分散，則以後查找的時間復雜度越小，空間復雜度越高。

Hash是一種典型以空間換時間的演算法，比如原來一個長度為100的數組，對其查找，只需要遍歷且匹配相應記錄即可，從空間復雜度上來看，假如數組存儲的是byte類型數據，那麼該數組佔用100byte空間。現在我們採用Hash演算法，我們前面說的Hash必須有一個規則，約束鍵與存儲位置的關系，那麼就需要一個固定長度的hash表，此時，仍然是100byte的數組，假設我們需要的100byte用來記錄鍵與位置的關系，那麼總的空間為200byte，而且用於記錄規則的表大小會根據規則，大小可能是不定的。

通過哈希函數，我們可以將鍵轉換為數組的索引(0-M-1)，但是對於兩個或者多個鍵具有相同索引值的情況，我們需要有一種方法來處理這種沖突。

一種比較直接的辦法就是，將大小為M 的數組的每一個元素指向一個鏈表，鏈表中的每一個節點都存儲散列值為該索引的鍵值對，這就是拉鏈法。下圖很清楚的描述了什麼是拉鏈法。

「John Smith」和「Sandra Dee」 通過哈希函數都指向了152 這個索引，該索引又指向了一個鏈表， 在鏈表中依次存儲了這兩個字元串。

單獨鏈表法：將散列到同一個存儲位置的所有元素保存在一個鏈表中（聚集），該方法的基本思想就是選擇足夠大的M，使得所有的鏈表都盡可能的短小，以保證查找的效率。當鏈表過長、大量的鍵都會映射到相同的索引上，哈希表的順序查找會轉變為鏈表的查找，查找時間將會變大。對於開放定址會造成性能的災難性損失。

實現基於拉鏈表的散列表，目標是選擇適當的數組大小M，使得既不會因為空鏈表而浪費內存空間，也不會因為鏈表太而在查找上浪費太多時間。拉鏈表的優點在於，這種數組大小M的選擇不是關鍵性的，如果存入的鍵多於預期，那麼查找的時間只會比選擇更大的數組稍長。另外，我們也可以使用更高效的結構來代替鏈表存儲。如果存入的鍵少於預期，索然有些浪費空間，但是查找速度就會很快。所以當內存不緊張時，我們可以選擇足夠大的M，可以使得查找時間變為常數，如果內存緊張時，選擇盡量大的M仍能夠將性能提高M倍。

線性探測法是開放定址法解決哈希沖突的一種方法，基本原理為，使用大小為M的數組來保存N個鍵值對，其中M>N，我們需要使用數組中的空位解決碰撞沖突。如下圖所示：

對照前面的拉鏈法，在該圖中，「Ted Baker」 是有唯一的哈希值153的，但是由於153被「Sandra Dee」佔用了。而原先「Snadra Dee」和「John Smith」的哈希值都是152的，但是在對「Sandra Dee」進行哈希的時候發現152已經被佔用了，所以往下找發現153沒有被佔用，所以索引加1 把「Sandra Dee」存放在沒有被佔用的153上，然後想把「Ted Baker」哈希到153上，發現已經被佔用了，所以往下找，發現154沒有被佔用，所以值存到了154上。

單純論查找復雜度：對於無沖突的Hash表而言，查找復雜度為O(1)。

原文： 哈希查找 - 賣賈筆的小男孩 - 博客園 (cnblogs.com)

④ C語言中的hash函數

Hash，一般翻譯做"散列"，也有直接音譯為"哈希"的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
HASH主要用於信息安全領域中加密演算法，它把一些不同長度的信息轉化成雜亂的128位的編碼里，叫做HASH值. 也可以說，hash就是找到一種數據內容和數據存放地址之間的映射關系。Hash演算法在信息安全方面的應用主要體現在以下的3個方面：文件校驗、數字簽名、鑒權協議
程程序實現
// 說明：Hash函數（即散列函數）在程序設計中的應用目標 ------ 把一個對象通過某種轉換機制對應到一個
//size_t類型（即unsigned long）的整型值。
// 而應用Hash函數的領域主要是 hash表（應用非常廣）、密碼等領域。
// 實現說明：
// ⑴、這里使用了函數對象以及泛型技術，使得對所有類型的對象（關鍵字）都適用。
// ⑵、常用類型有對應的偏特化，比如string、char*、各種整形等。
// ⑶、版本可擴展，如果你對某種類型有特殊的需要，可以在後面實現專門化。
// ⑷、以下實現一般放在頭文件中，任何包含它的都可使用hash函數對象。
//------------------------------------實現------------------------------------------------
#include <string>
using std::string;
inlinesize_thash_str(const char* s)
{
unsigned long res = 0;
for (; *s; ++s)
res = 5 * res + *s;
returnsize_t(res);
}
template <class Key>
struct hash
{
size_toperator () (const Key& k) const;
};
// 一般的對象，比如：vector< queue<string> >；的對象，需要強制轉化
template < class Key >
size_thash<Key>::operator () (const Key& k) const
{
size_tres = 0;
size_tlen = sizeof(Key);
const char* p = reinterpret_cast<const char*>(&k);
while (len--)
{
res = (res<<1）^*p++;
}
return res;
}
// 偏特化
template<>
size_thash< string >::operator () (const string& str) const
{
return hash_str(str.c_str());
}
typedef char* PChar;
template<>
size_thash<PChar>::operator () (const PChar& s) const
{
return hash_str(s);
}
typedef const char* PCChar;
template<>
size_thash<PCChar>::operator () (const PCChar& s) const
{
return hash_str(s);
}
template<> size_t hash<char>::operator () (const char& x) const { return x; }
template<> size_t hash<unsigned char>::operator () (const unsigned char& x) const { return x; }
template<> size_t hash<signed char>::operator () (const signed char& x) const { return x; }
template<> size_t hash<short>::operator () (const short& x) const { return x; }
template<> size_t hash<unsigned short>::operator () (const unsigned short& x) const { return x; }
template<> size_t hash<int>::operator () (const int& x) const { return x; }
template<> size_t hash<unsigned int>::operator () (const unsigned int& x) const { return x; }
template<> size_t hash<long>::operator () (const long& x) const { return x; }
template<> size_t hash<unsigned long>::operator () (const unsigned long& x) const { return x; }
// 使用說明：
//
// ⑴、使用時首先由於是泛型，所以要加上關鍵字類型。
//
// ⑵、其次要有一個函數對象，可以臨時、局部、全局的，只要在作用域就可以。
//
// ⑶、應用函數對象作用於對應類型的對象。
//----------------------- hash函數使用舉例 -------------------------
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
vector<string> vstr⑵；
vstr[0] = "sjw";
vstr[1] = "suninf";
hash<string> strhash; // 局部函數對象
cout << " Hash value: " << strhash(vstr[0]) << endl;
cout << " Hash value: " << strhash(vstr[1]) << endl;
cout << " Hash value: " << hash< vector<string> >() (vstr) << endl;
cout << " Hash value: " << hash<int>() （100） << endl; // hash<int>() 臨時函數對象
return 0;
}

⑤ C++數據結構設計程序

苦逼的吉大孩子,你幾班的啊，

#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<fstream>
//#include<math>
usingnamespacestd;
voidsearch(int,int,int*,int*);
template<classT>

intFind_s(Tdata[],intn,Tkey,int&icmp)
//順序查找(從n維數組中查找key,並且給出比較的次數icmp
{
icmp=0;
for(inti=0;i<n;i++)
{
icmp++;
if(data[i]==key)
returni;
}
return-1;
}

///以下是二叉查找樹查找法
template<classT>
classBintreeNode
{
public:
Tdata;
BintreeNode*left;
BintreeNode*right;

BintreeNode():left(0),right(NULL){}
BintreeNode(Titem):data(item),left(NULL),right(NULL){}
~BintreeNode(){
if(left!=0)
deleteleft;
if(right!=0)
deleteright;
}
};
template<classT>
classBintree
{
public:
intnum;
BintreeNode<T>*root;
BintreeNode<T>*Find_bt(Tkey,int&icmp,intitype=0)//一個二叉樹查找演算法
{
icmp=0;
if(root==0)
{
icmp++;
if(itype==0)//itype=1時有插入功亮純能（不同的值時）
returnNULL;
else
{
num++;
returnroot=newBintreeNode<T>(key);
}
}
else
{
BintreeNode<T>*ptr=root,*p;
敬搭咐while(ptr!=NULL)
{
icmp++;
p=ptr;
if(ptr->data==key)
returnptr;
else
{
if(ptr->data>key)
ptr=ptr->left;
else
ptr=ptr->right;
}
}
if(itype)
{
num++;
if(p->data>key)
枝旦returnp->left=newBintreeNode<T>(key);
else
returnp->right=new(BintreeNode<T>)(key);
}
returnNULL;
}//else
}//Find_bt
Bintree():root(0),num(0){}
~Bintree(){deleteroot;}
};
/*intcompare(constvoid*a,constvoid*b)
{
return*(int*)a-*(int*)b;
}*/
template<classT>
classLink
{
public:
Tdata;
Link<T>*next;
Link<T>():next(0){}
Link<T>(Titem):data(item),next(0){}
~Link<T>(){if(next)deletenext;}
};
template<classT>
classLinkList
{
public:
Link<T>*first;

LinkList<T>():first(0){}
~LinkList<T>(){if(first)deletefirst;}
Link<T>*Find_hash(Tkey,int&icmp,intntype=0)//查找與插入
{
icmp=0;
if(first==0)
{
icmp++;
if(ntype)
returnfirst=newLink<T>(key);
else
returnNULL;
}
else
{
Link<T>*ptr=first,*p;
while(ptr!=NULL)
{
icmp++;
p=ptr;
if(ptr->data==key)
returnptr;
ptr=ptr->next;
}
if(ntype)
returnp->next=newLink<T>(key);
returnNULL;
}
}
};
template<classT>
classHash
{
public:
LinkList<T>*hashlist;
intsize;
Hash<T>(intn=113):size(n)
{
hashlist=newLinkList<T>[n];
}
~Hash<T>(){delete[]hashlist;}
voidinit_hash(Tdata[],intn)//初始化哈希查找表（拉鏈法）
{
intt;
for(inti=0;i<n;i++)
{
intpos=data[i]%size;
hashlist[pos].Find_hash(data[i],t,1);
}
}
Link<T>*Find_hash(Tkey,int&icmp)//查找關鍵詞除法雜湊函數
{
intpos=key%size;
returnhashlist[pos].Find_hash(key,icmp);
}
};

intcompare1(constvoid*a,constvoid*b)
{
return*(int*)a-*(int*)b;
}
intcompare2(constvoid*a,constvoid*b)
{
return*(int*)b-*(int*)a;
}

//主函數
intmain()
{

intp;
intm;
intn;
while(true)
{
cout<<"請選擇數據類型:1.正序排列2.逆序排列3.隨機排列"<<endl;
cin>>p;
switch(p){
case1:

{
FILE*fp;
char*filename="data.in";
if((fp=fopen(filename,"w+"))==NULL)
{
printf("cannotopenthisflie
");
exit(0);
}


srand(time(0));
cout<<"請輸入數據規模n"<<endl;
cin>>n;
fprintf(fp,"		%d	",n);
cout<<"請輸入查找比較的操作次數m"<<endl;

cin>>m;
fprintf(fp,"		%d	
",m);

int*a=newint[n];
for(inti=0;i<n;i++)
{

a[i]=rand()%1000000001;
fprintf(fp,"		%d	
",a[i]);
}
qsort(a,n,sizeof(int),compare1);//對數組進行升序排序
qsort(a,n,sizeof(int),compare2);//對數組進行降序排序
//隨機生成m個隨機數，並存入data.in
int*b=newint[m];
for(intk=0;k<m;k++)
{
b[k]=rand()%1000000001;
fprintf(fp,"		%d	
",b[k]);
}
fclose(fp);//關閉文件
search(m,n,a,b);
}
break;
case2:

{
FILE*fp;
char*filename="data.in";
if((fp=fopen(filename,"w+"))==NULL)
{
printf("cannotopenthisflie
");
exit(0);
}


srand(time(0));
cout<<"請輸入數據規模n"<<endl;
cin>>n;
fprintf(fp,"		%d	",n);

cout<<"請輸入查找比較的操作次數m"<<endl;

cin>>m;
fprintf(fp,"		%d	
",m);

int*a=newint[n];
for(inti=0;i<n;i++)
{
a[i]=rand()%1000000001;
fprintf(fp,"		%d	
",a[i]);
}
qsort(a,n,sizeof(int),compare2);//對數組進行降序排序
//隨機生成m個隨機數，並存入data.in
int*b=newint[m];
for(intk=0;k<m;k++)
{
b[k]=rand()%1000000001;
fprintf(fp,"		%d	
",b[k]);
}
fclose(fp);//關閉文件
search(m,n,a,b);
}
break;
case3:
{
FILE*fp;
char*filename="data.in";
if((fp=fopen(filename,"w+"))==NULL)
{
printf("cannotopenthisflie
");
exit(0);
}


srand(time(0));
//輸入n,並存入data.in
//intn;
cout<<"請輸入數據規模n"<<endl;
cin>>n;
fprintf(fp,"		%d	",n);
//輸入m,並存入data.in
cout<<"請輸入查找比較的操作次數m"<<endl;
//intm;
cin>>m;
fprintf(fp,"		%d	
",m);
//隨機生成n個隨機數，並存入data.in
int*a=newint[n];
for(inti=0;i<n;i++)
{
a[i]=rand()%1000000001;
fprintf(fp,"		%d	
",a[i]);
}
//隨機生成m個隨機數，並存入data.in
int*b=newint[m];
for(intk=0;k<m;k++)
{
b[k]=rand()%1000000001;
fprintf(fp,"		%d	
",b[k]);
}
fclose(fp);//關閉文件
search(m,n,a,b);
}
}

}
return0;
}

//search函數
voidsearch(intm,intn,int*a,int*b){
FILE*fp;
char*filename="data.out";
if((fp=fopen(filename,"w+"))==NULL)
{
printf("cannotopenthisflie
");
exit(0);
}


clock_tstart1=clock();
for(inth=0;h<m;h++)
{
intkey=b[h];
inticmp;

intj=Find_s(a,n,key,icmp);//使用順序查找法查找key值的位置

if(j==-1)
{
cout<<"數據總數:"<<n<<"	查找關健字key:"<<key<<
"	查找比較次數:icmp
順序查找法：
是否找到:"

<<"no"<<"icmp:"<<icmp<<endl;
fprintf(fp,"		%s	
","no");
}
else
{

cout<<"數據總數:"<<n<<"	查找關健字key:"<<key<<
"	查找比較次數:icmp
順序查找法：
是否找到:"

<<"yes"<<"icmp:"<<icmp<<endl;
fprintf(fp,"		%s	
","yes");
}
}
clock_tend1=clock();

clock_tstart2=clock();
for(intf=0;f<m;f++)
{
intkey=b[f];
inticmp;
Bintree<int>btree;
for(inti=0;i<n;i++)
btree.Find_bt(a[i],icmp,1);//未排序之前插入到二叉查找樹中

qsort(a,n,sizeof(int),compare1);//對數組進行升序排序

cout<<"二叉查找樹："<<endl;
intp=(btree.Find_bt(key,icmp)==NULL?-1:btree.Find_bt

(key,icmp)->data);

if(p==-1)
{

cout<<"數據總數:"<<n<<"	查找關健字key:"<<key<<
"	查找比較次數:icmp
二叉樹查找法：
是否找到:"

<<"no"<<"icmp:"<<icmp<<endl;
fprintf(fp,"		%s	
","no");

}
else
{

cout<<"數據總數:"<<n<<"	查找關健字key:"<<key<<
"	查找比較次數:icmp
二叉樹查找法：
是否找到:"

<<"no"<<"icmp:"<<icmp<<endl;
fprintf(fp,"		%s	
","no");

}

}

clock_tend2=clock();

clock_tstart3=clock();

for(intg=0;g<m;g++)
{
intkey=b[g];
inticmp;
Hash<int>hash(1000);
hash.init_hash(a,n);

cout<<"哈希表查找："<<endl;
intq=((hash.Find_hash(key,icmp)==NULL)?-1:(hash.Find_hash

(key,icmp))->data);

if(q==-1){
cout<<"數據總數:"<<n<<"	查找關健字key:"<<key<<
"	查找比較次數:icmp
哈希查找法：
是否找到:"

<<"no"<<"icmp:"<<icmp<<endl;
fprintf(fp,"		%s	
","no");
}
else{

cout<<"數據總數:"<<n<<"	查找關健字key:"<<key<<
"	查找比較次數:icmp
二叉樹查找法：
是否找到:"

<<"yes"<<"icmp:"<<icmp<<endl;
fprintf(fp,"		%s	
","yes");
}

}

clock_tend3=clock();
cout<<"順序查找時間:"<<(double)(end1-start1)/CLOCKS_PER_SEC<<endl<<endl;//輸出時間
cout<<"二叉樹查找時間:"<<(double)(end2-start2)/CLOCKS_PER_SEC<<endl<<endl;//輸出時間
cout<<"哈希查找時間:"<<(double)(end3-start3)/CLOCKS_PER_SEC<<endl<<endl;//輸出時間
fclose(fp);//關閉文件
}

不過 運行結果 不能排序 只能是隨機的，你看看能改好嗎？改好了 說給我 我11級12班的

⑥ 線性表---解決沖突(c語言)

開放地址法
1.沖突處理方法一---開放地址法
當發生地址沖突後，求解下一個地址用：
ND
=(
D+di）%mi=1,2,…,k(k<=
m-1)
其中:
m為哈希表長度,di為增量序列。增量序列的不同取法，又構成不同的開放地址法。
(1)線性探測再散列
D
=
H(key);
ND
=
(D+di)%m;di取1,2,3,……,m-1
線性探測再散列處理沖突的基本思想:若數據元素在存儲地址D發生沖突，則放到存儲地址（D＋1）%m；若又發生沖突則放到存儲地址（D＋2）%m；若再發生沖突則放到存儲地址（D＋3）%m；…禪銷…；直到碰到第一個為空的存儲地址（D＋i）%m，則將數據元素存放在該存儲空間。
(2)二次探測再散列
D
=
H(key);
ND
=
(D+di)%m;di取1*1,-1*1,2*2,-2*2,……,K*K,-K*K
(K≤m/2)
(3)雙散列法
首先使用第一個散列函數H1(key)及逆行那個散列，一旦發生沖突，則使用第二個函數H2(key)計算改項到達下一個存儲地址的增量，其取值p和key有關，范圍在1和m之間，並且與m互質的正整數。
D
=
H1(key);
p
=
H2(key);
ND
=
(D+p)%m;
值得提醒的是，對利用開放地址法查了沖突所產生的哈希表中刪除一個元素，不能簡單地直接刪除，因為這樣將截斷其它具棚亮有相同哈希地址的元素的查找地址，所以應設定一個特殊的標志鏈襲寬以表明該元素已被刪除。
不知道對你是否有用

⑦ 有關數據結構哈希表的問題

Hash，一般翻譯做"散列"，也有直接音譯為"哈希"的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。
簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

hashing定義了一種將字元組成的字元串轉換為固定長度(一般是更短長度)的數值或索引值的方法，稱為散列法，也叫哈希法。由於通過更短的哈希值比用原始值進行資料庫搜索更快，這種方法一般用來在資料庫中建立索引並進行搜索，同時還用在各種解密演算法中。

設所有可能出現的關鍵字集合記為u(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為k（|k|比|u|小得多）。|k|是集合k中元素的個數。
散列方法是使用函數hash將u映射到表t[0..m-1]的下標上（m=o(|u|)）。這樣以u中關鍵字為自變數，以h為函數的運算結果就是相應結點的存儲地址。從而達到在o(1)時間內就可完成查找。
其中：
① hash：u→{0，1，2，…，m-1} ，通常稱h為散列函數(hash function)。散列函數h的作用是壓縮待處理的下標范圍，使待處理的|u|個值減少到m個值，從而降低空間開銷。
② t為散列表(hash table)。
③ hash(ki)(ki∈u)是關鍵字為ki結點存儲地址(亦稱散列值或散列地址)。
④ 將結點按其關鍵字的散列地址存儲到散列表中的過程稱為散列(hashing).
比如：有一組數據包括用戶名字、電話、住址等，為了快速的檢索，我們可以利用名字作為關鍵碼，hash規則就是把名字中每一個字的拼音的第一個字母拿出來，把該字母在26個字母中的順序值取出來加在一塊作為改記錄的地址。比如張三，就是z+s＝26+19＝45。就是把張三存在地址為45處。
但是這樣存在一個問題，比如假如有個用戶名字叫做：周四，那麼計算它的地址時也是z+s＝45，這樣它與張三就有相同的地址，這就是沖突，也叫作碰撞！
沖突：兩個不同的關鍵字，由於散列函數值相同，因而被映射到同一表位置上。該現象稱為沖突(collision)或碰撞。發生沖突的兩個關鍵字稱為該散列函數的同義詞(synonym)。
沖突基本上不可避免的，除非數據很少，我們只能採取措施盡量避免沖突，或者尋找解決沖突的辦法。影響沖突的因素
沖突的頻繁程度除了與h相關外，還與表的填滿程度相關。
設m和n分別表示表長和表中填人的結點數，則將α=n/m定義為散列表的裝填因子(load factor)。α越大，表越滿，沖突的機會也越大。通常取α≤1。
散列函數的構造方法：
1、散列函數的選擇有兩條標准：簡單和均勻。
簡單指散列函數的計算簡單快速；
均勻指對於關鍵字集合中的任一關鍵字，散列函數能以等概率將其映射到表空間的任何一個位置上。也就是說，散列函數能將子集k隨機均勻地分布在表的地址集{0，1，…，m-1}上，以使沖突最小化。
2、常用散列函數
（1）直接定址法：比如在一個0～100歲的年齡統計表，我們就可以把年齡作為地址。
（2）平方取中法
具體方法：先通過求關鍵字的平方值擴大相近數的差別，然後根據表長度取中間的幾位數作為散列函數值。又因為一個乘積的中間幾位數和乘數的每一位都相關，所以由此產生的散列地址較為均勻。
（3）除留余數法
取關鍵字被某個不大於哈希表表長m的數p除後所得余數為哈希地址。該方法的關鍵是選取m。選取的m應使得散列函數值盡可能與關鍵字的各位相關。m最好為素數（4）隨機數法
選擇一個隨機函數，取關鍵字的隨機函數值為它的散列地址，即
h(key)=random(key)
其中random為偽隨機函數，但要保證函數值是在0到m-1之間。
處理沖突的方法：
1、開放定址法
hi=(h(key)+di) mod m i=1,2,...,k(k<=m-1)
其中m為表長，di為增量序列
如果di值可能為1,2,3,...m-1，稱線性探測再散列。
如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
稱二次探測再散列。
如果di取值可能為偽隨機數列。稱偽隨機探測再散列。開放地址法堆裝填因子的要求
開放定址法要求散列表的裝填因子α≤l，實用中取α為0.5到0.9之間的某個值為宜。
②二次探查法(quadratic probing)
二次探查法的探查序列是：
hi=(h(key)+i*i)％m 0≤i≤m-1 //即di=i2
即探查序列為d=h(key)，d+12，d+22，…，等。
該方法的缺陷是不易探查到整個散列空間。
③雙重散列法(double hashing)
該方法是開放定址法中最好的方法之一，它的探查序列是：
hi=(h(key)+i*h1(key))％m 0≤i≤m-1 //即di=i*h1(key)
即探查序列為：
d=h(key)，(d+h1(key))％m，(d+2h1(key))％m，…，等。
該方法使用了兩個散列函數h(key)和h1(key)，故也稱為雙散列函數探查法。
2、拉鏈法
拉鏈法解決沖突的方法
拉鏈法解決沖突的做法是：將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組t[0..m-1]。凡是散列地址為i的結點，均插入到以t為頭指針的單鏈表中。t中各分量的初值均應為空指針。在拉鏈法中，裝填因子α可以大於1，但一般均取α≤1。
3、建立一個公共溢出區
假設哈希函數的值域為[0,m-1],則設向量hashtable[0..m-1]為基本表，另外設立存儲空間向量overtable[0..v]用以存儲發生沖突的記錄。
性能分析
插入和刪除的時間均取決於查找，故下面只分析查找操作的時間性能。
雖然散列表在關鍵字和存儲位置之間建立了對應關系，理想情況是無須關鍵字的比較就可找到待查關鍵字。但是由於沖突的存在，散列表的查找過程仍是一個和關鍵字比較的過程，不過散列表的平均查找長度比順序查找、二分查找等完全依賴於關鍵字比較的查找要小得多。
（1）查找成功的asl
散列表上的查找優於順序查找和二分查找。
（2） 查找不成功的asl
對於不成功的查找，順序查找和二分查找所需進行的關鍵字比較次數僅取決於表長，而散列查找所需進行的關鍵字比較次數和待查結點有關。因此，在等概率情況下，也可將散列表在查找不成功時的平均查找長度，定義為查找不成功時對關鍵字需要執行的平均比較次數。
注意：
①由同一個散列函數、不同的解決沖突方法構造的散列表，其平均查找長度是不相同的。
②散列表的平均查找長度不是結點個數n的函數，而是裝填因子α的函數。因此在設計散列表時可選擇α以控制散列表的平均查找長度。
③ α的取值
α越小，產生沖突的機會就小，但α過小，空間的浪費就過多。只要α選擇合適，散列表上的平均查找長度就是一個常數，即散列表上查找的平均時間為o(1)。
④ 散列法與其他查找方法的區別
除散列法外，其他查找方法有共同特徵為：均是建立在比較關鍵字的基礎上。其中順序查找是對無序集合的查找，每次關鍵字的比較結果為"="或"!="兩種可能，其平均時間為o(n)；其餘的查找均是對有序集合的查找，每次關鍵字的比較有"="、"<"和">"三種可能，且每次比較後均能縮小下次的查找范圍，故查找速度更快，其平均時間為o(lgn)。而散列法是根據關鍵字直接求出地址的查找方法，其查找的期望時間為o(1)。
例子：例子：選取哈希函數h(k)=(3k)%11,用線性探測再散列法處理沖突。
試在0～10的散列地址空間中，對關鍵序列22,41,53,46,30,13,01,67構造哈希表，並求等概率情況下查找不成功的平均查找長度asl。

⑧ 數據結構課程設計--學生成績管理系統C語言

一、需求分析
1． 系統菜單的主要功能
（1）輸入若干條記錄
（2）查找並修改記錄
（3）查找並刪除記錄
（4）成績排序
（5）查找並顯示一條記錄
（6）將數據載入內存中
（7）將所有數據寫入文件中
（0）退出程序
2． 功能分析
功能1為輸入一條記錄到結構體中去。
功能2、3和5演算法相似，都是先查找成績，2、3在此基礎上再對查找出的信息進行操作。因為學生姓名定義成了字元數組的形式，因此在運用選擇法進行排序的時候，要用到strcmp,strcpy等函數
功能4為成績排序，可按學生學號排序或某單科成績或總分排序，並輸出相關的學生信息等。
功能6和7是對文件的操作，提前准備好數據。
二、總體設計
「學生成績管理系統」包括：成績錄入、修改、刪除、成績統計和信息保存、載入這幾個模塊。
1、 主函數 main()
利用無限次循環while(1)和swithch()實現各函數的調用，系統根據輸入的數字燃掘選項來調用相應的函數。
2、 菜單選擇函數showmenu ();
這是一個無參函數，主要實現「功能選擇」的界面，在這個界面里有顯示系統的各項功能選單，根據每個功能前面的序號進行選擇。等執行完每一個函數功能後，按任一鍵回到主界面也要通過這個函數來實現！3、 輸入記錄函數addstudent (stu *s) 這是一個帶參函數，用來執行第學生成績記錄的輸入，當學生為0時停止輸入。
演算法：利用函數參數s，並將s->next設為NULL。每輸入一個數據就聲明一個新節點p，把p->next設為NULL，並且鏈接到之前列表的尾端。4、 顯示記錄函數showstudent (stu *s) 這是一個不返回值的有參函數，形參為「鏈表頭的指針」，負責對全部學生成績記錄的輸出，不足之處就是不能對學生成績進行分頁顯示。 演算法：先將p結點的指針指向第一個結點，將p結點(即第一個結點)的數據輸出。然後再將p結點的指針指向p指針的的指針(即下一結點)，將p結點(即第一結點)的數據輸出。重復執行此步聚直到p指針指向NULL為止。5、 查找記錄函數findstudent (stu *s) 這是一個不返回值的有參函數，形參為「鏈表頭的指針」，實現按學號對某個學生進行查找，並顯示所查找到的記錄。 演算法：採用線性查找法往下一個節點查找。輸入所要查找的學生的學號s，設一個指針變數p，先指向第一個結點，當strcmp(p->name,s) && p != NULL時，使p後移一個結點，如果p!=NULL，輸出p所指的結點。6、 刪除記錄函數delstudent (stu *s) 這是一個有參函數，形參為「鏈表頭的指針」，先輸入要刪除的學生記錄的學號，找到後顯示該學生信息，等確認後便可按「Y」進行刪除。 演算法：從p指向的第一個結點開始，檢查該結點中的num值是否等於輸入的要求刪除的那個學號。如果相等就將該結點刪除，如不相等，就將p後移一個結點，再如此進行下去，直到遇到表尾為止。7、保存數據到文件函數savestudent (stu *s) 這是一個不返回值的有參函數，形參為「鏈表頭的指針」，可以把學生記錄保存在電腦上由自己任意命名的二進制文件。8、從文件讀數據函數loadstudent (stu *s) 這是一個不返回值的有參函數，形參為「鏈表頭的指針」，根據輸入的文件地址進行讀取。

三、程序流程圖
1）成績統計：

2）廳段薯信息錄入：
3）信息修改：
4）信息刪除：
4）信息查詢：

4）信息保存：5）主函數：
四、程序調試及體會
1）程序演示：

2）程序調試：
（1）剛開始沒有那個初始化函數，程序運行後，沒有輸入任何數據就試得去執行顯示功能，結果顯示的是一些亂碼！加入初始化函數後，這種現象也隨之消失。
（2）剛開始執行輸入函數，按學號順序輸入十個學生的成績,輸完後執行顯示功能，學生成績記錄是按學號的反順序顯示的，試著在其中增加一些語句，希望能把學號按正常順序顯示，但暫時沒有成功，所以在輸入成績時只能按學號反順序輸入，最後就按學號正常順序輸出了。
（3）剛開始時，先把扮者成績按平均分排序，再插入一個學生的成績，執行顯示功能，雖然插入的學生的成績能正常插入，但該學生的名次為0。後來，在插入成績之後，調用排序函數，把所有成績重新排序一次。
（4）在輸入函數中設了一個無限循環，可以輸入無數個學生的成績信息，當學號為0的時候則停止輸入。
（5）輸入太多個學生的成績時，屏幕顯示不能控制為一頁一頁顯示，所以為了方便起見，不要輸入太多記錄，十七左右為最佳。
（6）在沒有輸入任何信息的情況下，去執行排序功能，最後顯示有一個記錄，學號、姓名為空白，成績都為0，名次為1。
（7）在輸入選項時不能輸入字母,否則會死循環，建議不要亂輸字母。

3）心得體會：
經過一個星期的課程設計，感覺自己收獲不少！
首先是：鏈表是數據結構的基本體現，所以這個課程設計裡面主要都是用鏈表，而已要達到這樣的功能，使用鏈表相當方便，但不容易理解，所以在這方面我很了很多的時間看課本和參考課外書，使C語言的知識強化了不少。
其次，在做課程設計的過程中，發現了平時很多沒有注意到的問題，例如：返回值函數和不返回值函數兩者在主函數中的調用是不同的…………
更重要的是，這次課程設計雖然花了我不少時間，但正是這些時間，讓我見識到了要學好C語言，數據的處理是相當重要的。這個學生成績管理系統都是在自己知識范圍內完成的，所以界面清晰簡單，可能不是很好看，但絕對實用！
從這里我也得到一個體會，做一個程序，或者開發一個軟體，應該著重從它的後台製作入手，不能做出一個中看不中用的程序或者軟體。
相信這次的課程設計為我以後繼續從事計算機工作打了一個小小的開頭。

參考書目；

[1]譚浩強. C程序設計(第三版) . 北京：清華大學出版社， 2006
[2]譚浩強. C程序設計上機指導(第三版) . 北京：清華大學出版社， 2005
[3]嚴蔚敏、吳偉民. 數據結構(C語言版) . 北京：清華大學出版社， 2006
計算機科學與技術系課程設計評分表

⑨ c語言數據結構（考題，測試你的能力）－－編寫源代碼

P88 稀疏矩陣十字鏈表相加演算法如下：
/*假設ha為A稀疏矩陣十字鏈表的頭指針，hb為B稀疏矩陣十字鏈表的頭指針*/
#include<stdio.h>
#define maxsize 100
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext
{ int v;
struct linknode *next;} k;
};

struct linknode creatlindmat( ) /*建立十字鏈表*/
{ int x, m, n, t, s, i, j, k;
struct linknode *p , *q, *cp[maxsize],*hm;
printf("請輸入稀疏矩陣的行、列數及非零元個數\n");
scanf("%d%d%d",&m,&n,&t);
if (m>n) s=m; else s=n;
hm=(struct linknode*)malloc(sizeof(struct linknode)) ;
hm->i=m; hm->j=n;
cp[0]=hm;
for (i=1; i<=s;i++)
{ p=(struct linknode*)malloc(sizeof(struct linknode)) ;
p->i=0; p->j=0;
p->rptr=p; p->cptr=p;
cp[i]=p;
cp[i-1]->k.next=p;
}
cp[s]->k.next=hm;
for( x=1;x<=t;x++)
{ printf("請輸入一個三元組(i,j,v)\n");
scanf("%d%d%d",&i,&j,&k);
p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=i; p->j=j; p->k.v=k;
/*以下是將p插入到第i行鏈表中 */
q=cp[i];
while ((q->rptr!=cp[i]) &&( q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
/*以下是將P插入到第j列鏈表中*/
q=cp[j];
while((q->cptr!=cp[j]) &&( q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
}
return hm;
}
/* ha和hb表示的兩個稀疏矩陣相加，相加的結果放入ha中*/
struct linknode *matadd(struct linknode *ha, struct linknode *hb)
{ struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q;
struct linknode *hl[maxsize];
int i , j, n;
if((ha->i!=hb->i)||(ha->j!=hb->j))
printf("矩陣不匹配,不能相加\n");
else
{ p=ha->k.next; n=ha->j;
for (i=1;i<=n; i++)
{ hl[i]=p;
p=p->k.next;
}
ca=ha->k.next; cb=hb->k.next;
while(ca->i==0)
{pa=ca->rptr; pb=cb->rptr;
qa=ca;
while(pb->j!=0)
{ if((pa->j<pb->j)&&(pa->j!=0))
{ qa=pa; pa=pa->rptr;}
else if ((pa->j>pb->j)||(pa->j==0)) /*插入一個結點*/
{ p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=pb->i; p->j=pb->j;
p->k.v=pb->k.v;
qa->rptr=p; p->rptr=pa;
qa=p; pb=pb->rptr;
j=p->j; q=hl[j]->cptr;
while((q->i<p->i)&&(q->i!=0))
{ hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=p; p->cptr=q;
hl[j]=p;
}
else
{pa->k.v=pa->k.v+pb->k.v;
if(pa->k.v==0) /*刪除一個結點*/
{ qa->rptr=pa->rptr;
j=pa->j; q=hl[j]->cptr;
while (q->i<pa->i)
{hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=q->cptr;
pa=pa->rptr; pb=pb->rptr;
free(q);
}
else
{ qa=pa; pa=pa->rptr;
pb=pb->rptr;
}
}
}
ca=ca->k.next; cb=cb->k.next;
}
}
return ha;
}
void print(struct linknode *ha) /*輸出十字鏈表*/
{ struct linknode *p,*q;
p=ha->k.next;
while(p->k.next!=ha)
{ q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
p=p->k.next;
}
q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
}

void main()
{
struct linknode *ha=NULL,*hb=NULL,*hc=NULL;
ha=creatlindmat( ); /*生成一個十字鏈表ha*/
hb=creatlindmat( ); /*生成另一個十字鏈表hb*/
printf("A:\n"); /*輸出十字鏈表ha*/
print(ha);printf("\n");
printf("B:\n"); /*輸出十字鏈表hb*/
print(hb);printf("\n");
hc=matadd(ha,hb); /*十字鏈表相加*/
printf("A+B:\n"); /*輸出相加後的結果*/
print(hc);printf("\n");
}

P94 數據類型描述如下：
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
}

P95 數據類型描述如下：
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}

P96 求廣義表的深度depth(LS)
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}

P96 廣義表的建立creat(LS)
void creat(struct node1 *LS)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node*)malloc(sizeof(struct node));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node*)malloc(sizeof(struct node));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}

P97 輸出廣義表print(LS)
void print(struct node1 *LS)
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c ",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}

P98 該演算法的時間復雜度為O(n)。整個完整程序如下：
#include<stdio.h>
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
};

void creat(struct node1 LS) /*建立廣義表的單鏈表*/
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
void print(struct node1 LS) /*輸出廣義單鏈表*/
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
int depth(struct node1 LS) /*求廣義表的深度*/
{
int max=0;
while(LS!=NULL)
{ if(LS->atom==0)
{ int dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
main()
{ int dep;
struct node1 *p=NULL;
creat(p); /*建立廣義表的單鏈表*/
print(p); /*輸出廣義單鏈表*/
dep=depth(p); /*求廣義表的深度*/
printf("%d\n",dep);
}

第六章 樹
P109 二叉鏈表的結點類型定義如下：
typedef struct btnode
{ anytype data;
struct btnode *Lch,*Rch;
}tnodetype;

P109 三叉鏈表的結點類型定義如下：
typedef struct btnode3
{ anytype data;
struct btnode *Lch,*Rch，*Parent ;
}tnodetype3;

P112 C語言的先序遍歷演算法：
void preorder (tnodetype *t)
/*先序遍歷二叉樹演算法，t為指向根結點的指針*/
{ if (t!=NULL)
{printf("%d ",t->data);
preorder(t->lch);
preorder(t->rch);
}
}

P113 C語言的中序遍歷演算法：
void inorder(tnodetype *t)
/*中序遍歷二叉樹演算法，t為指向根結點的指針*/
{
if(t!=NULL)
{inorder(t->lch);
printf("%d ",t->data);
inorder(t->rch);
}
}

P113 C語言的後序遍歷演算法：
void postorder(tnodetype *t)
/*後序遍歷二叉樹演算法，t為指向根結點的指針*/
{
if(t!=NULL)
{ postorder(t->lch);
postorder(t->rch);
printf("%d ",t->data);
}
}

P114 如果引入隊列作為輔助存儲工具，按層次遍歷二叉樹的演算法可描述如下：
void levelorder(tnodetype *t)
/*按層次遍歷二叉樹演算法，t為指向根結點的指針*/
{tnodetype q[20]; /*輔助隊列*/
front=0;
rear=0; /*置空隊列*/
if (t!=NULL)
{ rear++;
q[rear]=t; /*根結點入隊*/
}
while (front!=rear)
{ front++;
t=q [front];
printf ("%c\n",t->data);
if (t->lch!=NULL) /*t的左孩子不空，則入隊*/
{ rear++;
q [rear]=t->lch;
}
if (t->rch!=NULL) /*t的右孩子不空，則入隊*/
{ rear++;
q [rear]=t->rch;
}
}
}

P115 以中序遍歷的方法統計二叉樹中的結點數和葉子結點數，演算法描述為：
void inordercount (tnodetype *t)
/*中序遍歷二叉樹，統計樹中的結點數和葉子結點數*/
{ if (t!=NULL)
{ inordercount (t->lch); /*中序遍歷左子樹*/
printf ("%c\n",t->data); /*訪問根結點*/
countnode++; /*結點計數*/
if ((t->lch==NULL)&&(t->rch==NULL))
countleaf++; /*葉子結點計數*/
inordercount (t->rch); /*中序遍歷右子樹*/
}
}

P115 可按如下方法計算一棵二叉樹的深度：
void preorderdeep (tnodetype *t,int j)
/*先序遍歷二叉樹，並計算二叉樹的深度*/
{ if (t!=NULL)
{ printf ("%c\n",t->data); /*訪問根結點*/
j++;
if (k<j) k=j;
preorderdeep (t->lch,j); /*先序遍歷左子樹*/
preorderdeep (t->rch,j); /*先序遍歷右子樹*/
}
}

P117 線索二叉樹的結點類型定義如下：
struct nodexs
{anytype data;
struct nodexs *lch, *rch;
int ltag,rtag; /*左、右標志域*/
}

P117 中序次序線索化演算法
void inorderxs (struct nodexs *t)
/*中序遍歷t所指向的二叉樹，並為結點建立線索*/
{ if (t!=NULL)
{ inorderxs (t->lch);
printf ("%c\n",t->data);
if (t->lch!=NULL)
t->ltag=0;
else { t->ltag=1;
t->lch=pr;
} /*建立t所指向結點的左線索，令其指向前驅結點pr*/
if (pr!=NULL)
{ if (pr->rch!=NULL)
pr->rtag=0;
else { pr->rtag=1;
pr->rch=p;
}
} /*建立pr所指向結點的右線索，令其指向後繼結點p*/
pr=p;
inorderxs (t->rch);
}
}

P118 在中根線索樹上檢索某結點的前驅結點的演算法描述如下：
struct nodexs * inpre (struct nodexs *q)
/*在中根線索樹上檢索q所指向的結點的前驅結點*/
{ if (q->ltag==1)
p=q->lch;
else { r=q->lch;
while (r->rtag!=1)
r=r->rch;
p=r;
}
return (p);
}

P119 在中根線索樹上檢索某結點的後繼結點的演算法描述如下：
struct nodexs * insucc (struct nodexs *q)
/*在中根線索樹上檢索q所指向的結點的後繼結點*/
{ if (q->rtag==1)
p=q->rch;
else { r=q->rch;
while (r->ltag!=1)
r=r->lch;
p=r;
}
return (p);
}

P120 演算法程序用C語言描述如下：
void sortBT(BT *t,BT *s) /*將指針s所指的結點插入到以t為根指針的二叉樹中*/
{ if (t==NULL) t=s; /*若t所指為空樹，s所指結點為根*/
else if (s->data < t->data)
sortBT(t->lch,s); /*s結點插入到t的左子樹上去*/
else
sortBT(t->rch,s); /*s結點插入到t的右子樹上去*/
}

P121 二叉排序樹結點刪除演算法的C語言描述如下：
void delnode(bt,f,p)
/*bt為一棵二叉排序樹的根指針，p指向被刪除結點，f指向其雙親*/
/*當p=bt時f為NULL*/
{ fag=0; /*fag=0時需修改f指針信息，fag=1時不需修改*/
if (p->lch==NULL)
s=p->rch; /*被刪除結點為葉子或其左子樹為空*/
else if (p->rch==NULL)
s=p->lch;
else { q=p; /*被刪除結點的左、右子樹均非空*/
s=p->lch;
while (s->rch!=NULL)
{ q=s;
s=s->rch;
} /*尋找s結點*/
if (q=p)
q->lch=s->lch;
else q->rch=s->lch;
p->data=s->data; /*s所指向的結點代替被刪除結點*/
DISPOSE(s);
Fag=1;
}
if (fag=0) /*需要修改雙親指針*/
{ if (f=NULL)
bt=s; /*被刪除結點為根結點*/
else if (f->lch=p)
f->lch=s;
else f->rch=s;
DISPOSE(p); /*釋放被刪除結點*/
}
}

第七章 圖
P134 用鄰接矩陣表示法表示圖，除了存儲用於表示頂點間相鄰關系的鄰接矩陣外，通常還需要用一個順序表來存儲頂點信息。其形式說明如下：
# define n 6 /*圖的頂點數*/
# define e 8 /*圖的邊(弧)數*/
typedef char vextype; /*頂點的數據類型*/
typedef float adjtype; /*權值類型*/
typedef struct
{vextype vexs[n];
adjtype arcs[n][n];
}graph;

P135 建立一個無向網路的演算法。
CREATGRAPH(ga) /*建立無向網路*/
Graph * ga;
{
int i,j,k;
float w;
for(i＝0;i<n;i++ )
ga ->vexs[i]＝getchar(); /*讀入頂點信息，建立頂點表*/
for(i＝0;i<n;i++ )
for(j＝0;j<n;j++)
ga ->arcs[i][j]＝0; /*鄰接矩陣初始化*/
for(k＝0;k<e;k++) /*讀入e條邊*/
(scanf("％d％d％f",&I,&j,&w); /*讀入邊(vi,vj)上的權w */
ga ->arcs[i][j]＝w;
ga - >arcs[j][i]＝w;
}
} /*CREATGRAPH*/

P136 鄰接表的形式說明及其建立演算法：
typedef struct node
{int adjvex; /*鄰接點域*/
struct node * next; /*鏈域*/
}edgenode; /*邊表結點*/
typedef struct
{vextype vertex; /*頂點信息*/
edgenode link; /*邊表頭指針*/
}vexnode; /*頂點表結點*/
vexnode ga[n];

CREATADJLIST(ga) /*建立無向圖的鄰接表*/
Vexnode ga[ ];
{int i,j,k;
edgenode * s;
for(i=o;i<n;i++＝ /*讀入頂點信息*/
(ga[i].vertex＝getchar();
ga[i].1ink＝NULL; /*邊表頭指針初始化*/
}
for(k＝0;k<e;k++＝ /*建立邊表*/
{scanf("％d％d",&i,&j); /*讀入邊(vi , vj)的頂點對序號*/
s＝malloc(sizeof(edgenode)); /*生成鄰接點序號為j的表結點*s */
s-> adjvex＝j;
s- - >next：＝ga[i].Link;
ga[i].1ink＝s; /*將*s插入頂點vi的邊表頭部*/
s＝malloc(size0f(edgende)); /*生成鄰接點序號為i的邊表結點*s */
s ->adjvex＝i;
s ->next＝ga[j].1ink;
ga[j].1ink＝s; /*將*s插入頂點vj的邊表頭部*/
}
} /* CREATADJLIST */

P139 分別以鄰接矩陣和鄰接表作為圖的存儲結構給出具體演算法，演算法中g、g1和visited為全程量，visited的各分量初始值均為FALSE。
int visited[n] /*定義布爾向量visitd為全程量*/
Graph g; /*圖g為全程量*/

DFS(i) /*從Vi+1出發深度優先搜索圖g，g用鄰接矩陣表示*/
int i;
{ int j;
printf("node：％c＼n" , g.vexs[i]); /*訪問出發點vi+1 */
Visited[i]＝TRUE; /*標記vi+l已訪問過*/
for (j＝0;j<n;j++) /*依次搜索vi+1的鄰接點*/
if((g.arcs[i][j]＝＝1) ＆＆(! visited[j]))
DFS(j); /*若Vi+l的鄰接點vj+l未曾訪問過，則從vj+l出發進行深度優先搜索*/
} /*DFS*/
vexnode gl[n] /*鄰接表全程量*/

DFSL(i) /*從vi+l出發深度優先搜索圖g1，g1用鄰接表表示*/
int i;
{ int j;
edgenode * p;
printf("node：％C\n" ,g1[i].vertex);
vistited[i]＝TRUE;
p＝g1[i].1ink; /*取vi+1的邊表頭指針*/
while(p !＝NULL) /*依次搜索vi+l的鄰接點*/
{
if(! Vistited[p ->adjvex])
DFSL(p - >adjvex); /*從vi+1的未曾訪問過的鄰接點出發進行深度優先搜索*/
p＝p - >next; /*找vi+l的下一個鄰接點*/
}
} /* DFSL */

P142 以鄰接矩陣和鄰接表作為圖的存儲結構，分別給出寬度優先搜索演算法。
BFS(k) /＊從vk+l出發寬度優先搜索圖g，g用鄰接矩陣表示，visited為訪問標志向量*/
int k;
{ int i,j;
SETNULL(Q); /*置空隊Q */
printf("％c＼n"，g.vexs[k]); /*訪問出發點vk+l*x/
visited[k]＝TRUE; /*標記vk+l已訪問過*/
ENQUEUE(Q，K); /*已訪問過的頂點(序號)入隊列*/
While(!EMPTY(Q)) /*隊非空時執行*/
{i＝DEQUEUE(Q); /*隊頭元素序號出隊列*/
for(j＝0;j<n;j++)
if((g.arcs[i][j]＝＝1)＆＆(! visited[j]))
{printf("％c＼n" , g.vexs[j]); /*訪問vi+l的未曾訪問的鄰接點vj+l */
visited[j]＝TRUE;
ENQUEUE(Q,j); /*訪問過的頂點入隊*/
}
}
} /* BFS */
BFSL(k) /*從vk+l出發寬度優先搜索圖g1，g1用鄰接表表示*/
int k
{ int i;
edgenode * p;
SETNULL(Q);
printf("％c＼n" , g1[k].vertex);
visited[k]＝TRUE;
ENQUEUE(Q,k);
while(! EMPTY(Q));
{ i＝DEQUEUE(Q);
p＝g1[i].1ink /*取vi+l的邊表頭指針*/
while(p !＝NULL) /*依次搜索vi+l的鄰接點*/
{ if( ! visited[p - >adjvex]) /*訪問vi+l的未訪問的鄰接點*/
{ printf{"％c＼n" , g1[p - >adjvex].vertex};
visited[p - >adjvex]＝TRUE;
ENQUEUE(Q,p - >adjvex); /*訪問過的頂點入隊*/
}
p＝p - >next; /*找vi+l的下一個鄰接點*/
}
}
} /*BFSL*/

P148 在對演算法Prim求精之前，先確定有關的存儲結構如下：
typdef struct
{Int fromvex，endvex; /*邊的起點和終點*/
float length; /*邊的權值*/
} edge;

float dist[n][n]; /*連通網路的帶權鄰接矩陣*/
edgeT[n-1]; /*生成樹*/

P149 抽象語句(1)可求精為：
for(j=1;j<n;j++) /*對n-1個藍點構造候選紫邊集*/
{T[j-1].fromvex＝1}; /*紫邊的起點為紅點*/
T[j-1].endvex＝j+1; /*紫邊的終點為藍點*/
T[j-1].1ength＝dist[0][j]; /*紫邊長度*/
}

P149 抽象語句(3)所求的第k條最短紫邊可求精為：
min＝max; /*znax大於任何邊上的權值*/
for (j＝k;j<n-1;j++) /*掃描當前候選紫邊集T[k]到T[n-2]，找最短紫邊*/
if(T[j].1ength<min)
{min＝T[j].1ength;m＝j; /*記錄當前最短紫邊的位置*/
}

P149 抽象語句(4)的求精：
e＝T[m];T[m]＝T[k];T[k]＝e， /* T[k]和T[m]交換*/
v＝T[kl.Endvex]; /* v是剛被塗紅色的頂點*/

P149 抽象語句(5)可求精為：
for(j＝k+1;j<n-1;j++) /*調整候選紫邊集T[k+1]到T[n-2]*/
{d＝dist[v-1][T[j].endvex-1]; /*新紫邊的長度*/
if(d<T[j].1ength) /*新紫邊的長度小於原最短紫邊*/
{T[j].1ength＝d;
T[j].fromvex＝v; /*新紫邊取代原最短紫邊*/
}
}

P150 完整的演算法：
PRIM() /*從第一個頂點出發構造連通網路dist的最小生成樹，結果放在T中*/
{int j , k , m , v , min , max＝l0000;
float d;
edge e;
for(j=1;j<n;j++) /*構造初始候選紫邊集*/
{T[j-1].formvex＝1; /*頂點1是第一個加入樹中的紅點*/
T[j-1].endvex＝j+1;
T[j-1].length＝dist[o][j];
}
for(k＝0;k<n-1;k++) /*求第k條邊*/
{min＝max;
for(j＝k;j<n-1;j++) /*在候選紫邊集中找最短紫邊*/
if(T[j].1ength<min)
{min＝T[j].1ength;
m＝j;
} /*T[m]是當前最短紫邊*/
}
e＝T[m];T[m]＝T[k];T[k]＝e; /*T[k]和T[m]交換後，T[k]是第k條紅色樹邊*/
v＝T[k].endvex ; /* v是新紅點*/
for(j＝k+1;j<n-1;j++) /*調整候選紫邊集*/
{d＝dist[v-1][T[j].endvex-1];
if(d<T[j].1ength);
{T[j].1ength＝d;
T[j].fromvex＝v;
}
}
} /* PRIM */

P151 Kruskl演算法的粗略描述：
T＝(V,φ);
While(T中所含邊數<n-1)
{從E中選取當前最短邊(u,v);
從E中刪去邊(u,v);
if((u,v)並入T之後不產生迴路，將邊(u,v)並入T中;
}

P153 迪傑斯特拉演算法實現。演算法描述如下：
#define max 32767 /*max代表一個很大的數*/
void dijkstra (float cost[][n],int v)
/*求源點v到其餘頂點的最短路徑及其長度*/
{ v1=v-1;
for (i=0;i<n;i++)
{ dist[i]=cost[v1][i]; /*初始化dist*/
if (dist[i]<max)
pre[i]=v;
else pre[i]=0;
}
pre[v1]=0;
for (i=0;i<n;i++)
s[i]=0; /*s數組初始化為空*/
s[v1]=1; /*將源點v歸入s集合*/
for (i=0;i<n;i++)
{ min=max;
for (j=0;j<n;j++)
if (!s[j] && (dist[j]<min))
{ min=dist[j];
k=j;
} /*選擇dist值最小的頂點k+1*/
s[k]=1; /*將頂點k+1歸入s集合中*/
for (j=0;j<n;j++)
if (!s[j]&&(dist[j]>dist[k]+cost[k][j]))
{ dist[j]=dist[k]+cost[k][j]; /*修改 V-S集合中各頂點的dist值*/
pre[j]=k+1; /*k+1頂點是j+1頂點的前驅*/
}
} /*所有頂點均已加入到S集合中*/
for (j=0;j<n;j++) /*列印結果*/
{ printf("%f\n%d",dist[j],j+1;);
p=pre[j];
while (p!=0)
{ printf("%d",p);
p=pre[p-1];
}
}
}

P155 弗洛伊德演算法可以描述為：
A(0)[i][j]=cost[i][j]; //cost為圖的鄰接矩陣
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n

P155 弗洛伊德演算法實現。演算法描述如下：
int path[n][n]; /*路徑矩陣*/
void floyd (float A[][n],cost[][n])
{ for (i=0;i<n;i++) /*設置A和path的初值*/
for (j=0;j<n;j++)
{ if (cost[i][j]<max)
path[i][j]=j;
else { path[i][j]=0;
A[i][j]=cost[i][j];
}
}
for (k=0;k<n;k++)
/*做n次迭代，每次均試圖將頂點k擴充到當前求得的從i到j的最短路徑上*/
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (A[i][j]>(A[i][k]+A[k]

⑩ 用哈希表實現C語言關鍵字的演算法

#include <iostream.h>
#include<fstream.h>
#include <string>
#include <iomanip.h>
using namespace std;

const int TOTAL=32;
const int MAXLEN=10;
const int HASHLEN=41;
int cont=0;
class HashTable
{
public:
char keyword[MAXLEN];
int count;
int num;
};
HashTable HS[HASHLEN];

char KeyWords[TOTAL][MAXLEN]= {
"char", "double", "enum", "float", "int", "long", "short", "signed",
"struct", "union", "unsigned", "void", "break", "case", "continue",
"default", "do", "else", "for", "goto", "if", "return", "switch", "while",
"auto", "extern", "register", "static", "const", "sizeof", "typedef", "volatile"
};

template<class T>
class HASH
{
public:
void Show(int key);
int CreatHX(char *keyword);
int GetFreePos(int key);
void ResetHX();
int GetKey(char *keyword);
int isKeyWords(char *word);
int Read(char *filename);
int isLetter(char ch);
int FindHX(char *keyword);
private:
int key;
char *keyword;
char *word;
char ch;

};
template<class T>
void HASH<T>::Show(int key)
{
if(key<0||key>=HASHLEN)
{
cout<<"關鍵字不存在!"<<endl;
return;
}
if(strlen(HS[key].keyword)==0)
{
cout<<"哈希表位置："<<key<<" 記錄是空的"<<endl;
return ;
}
cout<<"哈希表位置: "<<key<<" 關鍵字: "
<<HS[key].keyword<<" 出現次數 "<<HS[key].count<<endl;
cont++;
}

template<class T>
int HASH<T>::CreatHX(char *keyword)
{
int key;
if(!isKeyWords(keyword)) return -1;
key=GetKey(keyword);

if(strlen(HS[key].keyword)>0)
{
if(strcmp(HS[key].keyword,keyword)==0)
{
HS[key].count++;
return 1;
}
key=FindHX(keyword);
if(key<0)
{
key=GetFreePos(GetKey(keyword));
if(key<0) return -1;
strcpy(HS[key].keyword,keyword);
}

if(key<0) return -1;
HS[key].count++;
}
else
{
strcpy(HS[key].keyword,keyword);
HS[key].count++;
}
return 1;
}
template<class T>
int HASH<T>::GetFreePos(int key)
{
int find,tem=0;
if(key<0||key>=HASHLEN) return -1;
for(find=key+1;find<HASHLEN;find++)
{
tem++;
if(strlen(HS[find].keyword)==0){
HS[find].num=tem;
return find; }
}

for(find=0;find<key;find++)
{
tem++;
if(strlen(HS[find].keyword)==0){
HS[find].num=tem;
return find; }
}
return -1;
}

template<class T>
void HASH<T>::ResetHX()
{
int i;
for(i=0;i<HASHLEN;i++)
{
strcpy(HS[i].keyword,"");
HS[i].count=0;
HS[i].num=0;
}
}

template<class T>
int HASH<T>::GetKey(char *keyword)
{
return ( keyword[0]*100+keyword[strlen(keyword)-1] ) % 41;
}

template<class T>
int HASH<T>::isKeyWords(char *word)
{
int i;
for(i=0;i<TOTAL;i++)
if(strcmp(word,KeyWords[i])==0) return 1;
return 0;
}

template<class T>
int HASH<T>::isLetter(char ch)
{
if( (ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z') ) return 1;
else return 0;

}

template<class T>
int HASH<T>::FindHX(char *keyword)
{
int key,find,tem=0;
if(!isKeyWords(keyword)) return -1;
key=GetKey(keyword);
if(strcmp(HS[key].keyword,keyword)==0) return key;
for(find=key+1;find<HASHLEN;find++)
{
tem++;
if(strcmp(HS[find].keyword,keyword)==0){
HS[find].num=tem;
return find; }
}

for(find=0;find<key;find++)
{
tem++;
if(strcmp(HS[find].keyword,keyword)==0){
HS[find].num=tem;
return find; }
}
return -1;
}

template<class T>
int HASH<T>::Read(char *filename)
{
char word[MAXLEN],ch;
int i;
FILE *read;
fstream myfile;
myfile.open("filename");
if(!myfile)
{
cout<<"文件不存在,請確認好再輸入!"<<endl;
return -1;
}
ResetHX();
while(!feof(read))
{
i=0;
ch=fgetc(read);
while(isLetter(ch)==0 && feof(read)==0 )
ch=fgetc(read);
while(isLetter(ch)==1 && feof(read)==0 )
{
if(i==MAXLEN)
{
while(isLetter(ch)==1&& feof(read)==0)
{
ch=fgetc(read);
}
i=0;
break;
}

else
{
word[i++]=ch;
ch=fgetc(read);
}
}
word[i]='\0';
if(isKeyWords(word))
{
CreatHX(word);
}
}
fclose(read);
cout<<"讀取成功，文件中關鍵字已經存入hash表，請繼續操作"<<endl;
return 1;
}

void main()
{
HASH<char> hash;
char filename[128],word[MAXLEN];
int i=0,count=0;
int key;
char j,y;
cout<<"請輸入要讀取的文件名:";
cin>>filename;
cout<<endl;
hash.Read(filename);
for(i=0;i<HASHLEN;i++)
{
hash.Show(i);
getchar();
}
cout<<"關鍵字總數為："<<cont<<endl;
cout<<"請輸入你想要查找的關鍵字： ";
cin>>word;
cout<<endl;
hash.Show(hash.FindHX(word));
cout<<" C語言中的關鍵字和其在哈希表的位置:"<<endl;
for(i=0;i<TOTAL;i++)
{
cout<<setiosflags(ios::left)<<"["<<setw(2)<<hash.GetKey(KeyWords[i])<<"]"
<<setiosflags(ios::left)<<setw(11)<<KeyWords[i];
if((i+1)%4==0) cout<<endl;
}
cout<<"是否顯示沖突關鍵字列表？y(是) 其它（否）:";
cin>>j;
if(j=='y')
{
cout<<"沖突關鍵字列表"<<endl;
for(i=0;i<HASHLEN;i++)
{
if(strlen(HS[i].keyword)>0)
{
key=hash.GetKey(HS[i].keyword);
if(key!=i)
{
count++;
cout<<setiosflags(ios::left)<<setw(14)<<
"\t[關鍵 字]:"<<HS[i].keyword<<setiosflags(ios::left)<<
setw(20)<<"\t[哈希表當前位置]: "<<i<<setiosflags(ios::left)<<
setw(20)<<"\t[沖突次數]: "<<HS[i].num<<endl;
}
}
}
if(count==0)
cout<<"沒有沖突"<<endl;
else
cout<<"\t沖突關鍵字共:"<<count<<"個"<<endl;
}
else
cout<<"不顯示沖突關鍵字列表，但已存在！"<<endl;
return;
}