① 誰能幫忙寫一個c語言的哈希排序小女感激不盡~~
1.選擇合適的哈希函數H(key)=key%p(p為小於或等於哈希表長的最大質數)；
2.計算各個關鍵字的直接哈希函數值；
3.根據處理沖突的方法建立哈希表，並輸出；
4.在哈希表中進行查找，輸出查找的結果，以及所需和記錄關鍵字比較的次數，並計算和輸出在等概率情況下查找成功的平均查找長度。
#include<stdlib.h>
#include<stdio.h>
#define NULL 0
typedef int KeyType;
typedef struct
{
KeyType key;
} ElemType;
int haxi(KeyType key,int m) /*根據哈希表長m，構造除留余數法的哈希函數haxi*/
{
int i,p,flag;
for(p=m;p>=2;p--) /*p為不超過m的最大素數*/
{
for(i=2,flag=1;i<=p/2&&flag;i++)
if(p%i==0)
flag=0;
if(flag==1)
break;
}
return key%p; /*哈希函數*/
}
void inputdata(ElemType **ST,int n) /*從鍵盤輸入n個數據，存入數據表ST(採用動態分配的數組空間)*/
{
KeyType key;
int i;
(*ST)=(ElemType*)malloc(n*sizeof(ElemType));
printf("\nPlease input %d data:",n);
for(i=1;i<=n;i++)
scanf("%d",&((*ST)[i].key));
}
void createhaxi(ElemType **HASH,ElemType *ST,int n,int m) /*由數據表ST構造哈希表HASH，n、m分別為數據集合ST和哈希表的長度*/
{
int i,j;
(*HASH)=(ElemType *)malloc(m*sizeof(ElemType));
for(i=0;i<m;i++)
(*HASH)[i].key=NULL; /*初始化哈希為空表(以0表示空)*/
for(i=0;i<n;i++)
{
j=haxi(ST[i].key,m); /*獲得直接哈希地址*/
while((*HASH)[j].key!=NULL)
j=(j+1)%m; /*用線性探測再散列技術確定存放位置*/
(*HASH)[j].key=ST[i].key; /*將元素存入哈希表的相應位置*/
}
}
int search(ElemType *HASH,KeyType key,int m,int *time) /*在表長為m的哈希表中查找關鍵字等於key的元素，並用time記錄比較次數，若查找成功，函數返回值為其在哈希表中的位置，否則返回-1*/
{
int i;
*time=1;
i=haxi(key,m);
while(HASH[i].key!=0&&HASH[i].key!=key)
{
i++;
++*time;
}
if(HASH[i].key==0)
return -1;
else
return i;
}
main()
{
ElemType *ST,*HASH;
KeyType key;
int i,n,m,stime,time;
char ch;
printf("\nPlease input n&&m(n<=m)"); /*輸入關鍵字集合元素個數和哈希表長*/
scanf("%d%d",&n,&m);
inputdata(&ST,n); /*輸入n個數據*/
createhaxi(&HASH,ST,n,m); /*創建哈希表*/
printf("\nThe haxi Table is\n"); /*輸出已建立的哈希表*/
for(i=0;i<m;i++)
printf("%5d",i);
printf("\n");
for(i=0;i<m;i++)
printf("%5d",HASH[i].key);
do /*哈希表的查找，可進行多次查找*/
{
printf("\nInput the key you want to search:");
scanf("%d",&key);
i=search(HASH,key,m,&time);
if(i!=-1) /*查找成功*/
{
printf("\nSuccess,the position is %d",i);
printf("\nThe time of compare is %d",time);
}
else /*查找失敗*/
{
printf("\nUnsuccess");
printf("\nThe time of compare is %d",time);
}
printf("\nContiue(y/n):\n"); /*是否繼續查找yes or no*/
ch=getch();
}
while(ch=='y'||ch=='Y'); /*計算表在等概率情況下的平均查找長度，並輸出*/
for(stime=0,i=0;i<n;i++)
{
search(HASH,ST[i].key,m,&time);
stime+=time;
}
printf("\nThe Average Search Length is %5.2f",(float)stime/n);
ch=getch();
}
② 哈希表的設計(數據結構C語言版）
解決沖突方法無非兩種嘛，而且這個不難的，幫你寫不是害你嘛，這個不學好以後的課程容易出現問題的！
③ 構造哈希表存儲電話號碼，用再哈希法處理沖突要c語言程序代碼
給你個hash表的介面和實現
你根據需求該下吧
#ifndef _Hash_H_
#define _Hash_H_
/*
* 查找演算法時間是 O(1)
* 優點:查找迅速
* 缺點:比較佔用內存
*/
/*
*
* hash原子結構體
*
*
*/
typedef struct hash_table_pair_s{
/*hash表長*/
int length;
/*hash key*/
char *key;
/*儲存的值,可以是地址*/
int value;
struct hash_table_pair_s *next;
}hash_table;
/*
* function: hash_insert
* --------------------------------------
* 往hash表中增加一個元素
* Usage:
*
* #include "corelib/hash.h"
* void run(hash_table*hash){
* int i, status, value;
* status = hash_get(hash,"hawk", &value);
* if(status!=-1){
* printf("find,%d",value);
* }else{
* printf("not find");
* }
* }
* void main(){
* hash_table* hash= hash_create(10);//創建一個表長是10的hash表
* hash_insert(hash,"robin", 0);
* hash_insert(hash,"sparrow", 1);
* hash_insert(hash,"hawk", 2);
* hash_insert(hash,"jack", 3);
* hash_insert(hash,"seagull", 4);
* run(hash);
* }
*
*/
void hash_insert(hash_table *hash,const char *key, int value);
/*
* function: hash_get
* --------------------------------------
* 根據key值在hash表中獲取一個元素對象
*
*
*/
int hash_get(hash_table *hash,const char* key, int *value);
/*
* function: hash_create
* 創建一個hash表
*
*/
hash_table* hash_create(int size);
#include "corelib/hash.c"
#endif
//-----------------------------------------------------------------------------------------------
#include <default.c>
#include <stdio.h>
/*
*一個key字元串佔用的位元組數
*/
#define KEY_SIZE 64
/*
*
*hash函數
*
*/
int ELFhash(const char *key){
unsigned long h = 0;
unsigned long g;
while( *key )
{
h =( h<< 4) + *key++;
g = h & 0xf0000000L;
if( g ) h ^= g >> 24;
h &= ~g;
}
return h;
}
void hash_insert(hash_table *hash,const char *key, int value){
char keystr[KEY_SIZE];
memset(keystr,0,KEY_SIZE);
memcpy(keystr,key,strlen(key));
int pos;
hash_table *new_pair;
char *new_str;
pos = ELFhash(key) % hash[0].length;
if (hash[pos].key != NULL) {
/*發生沖突*/
char log[512];
memset(log,0,512);
int j=0;
j+=sprintf(log+j,"沖突: %s and %s\n", keystr, hash[pos].key);
new_pair = (hash_table *)malloc(sizeof(hash_table));
new_str = (char *)malloc(sizeof(char) * (strlen(keystr) + 1));
strcpy(new_str, keystr);
new_pair->key = new_str;
new_pair->value = value;
new_pair->next = hash[pos].next;
hash[pos].next = new_pair;
// printf("%s",log);
}else{
int len = sizeof(char) * (strlen(keystr) + 1);
new_str = (char *)malloc(len);
memset(new_str,0,len);
strcpy(new_str, keystr);
hash[pos].key = new_str;
hash[pos].value = value;
hash[pos].next = NULL;
}
}
int hash_get(hash_table *hash,const char* key, int *value){
int pos;
hash_table *p;
char keystr[KEY_SIZE];
memset(keystr,0,KEY_SIZE);
memcpy(keystr,key,strlen(key));
pos = ELFhash(key) % hash[0].length;
for (p = &(hash[pos]); p != NULL; p = p->next) {
if (!strcmp(p->key, keystr)) {
*value = p->value;
return 0;
}
}
return -1;
}
hash_table* hash_create(int size){
int i;
hash_table *hash = (hash_table *)malloc(size * sizeof(hash_table));
hash[0].length = size;
for (i = 0; i < size; i++) {
hash[i].key = NULL;
hash[i].next = NULL;
hash[i].value = 0;
}
return hash;
}
#undef KEY_SIZE
④ 可以不學數據結構直接學哈希表嗎C語言實現
可以的，哈希表那部分和圖，樹聯系不是很大。直接看是完全可以的，而且哈希這部分也比較容易些。
⑤ 編寫一個C語言程序，求出1至1000之間滿足「用3除餘2；用5除餘3；用7除餘2」的數，並把滿足條件的數顯示...
#include "stdio.h"
int main()
{
int i,j=0;
for(i=1;i<=1000;i++)
{
if(i%3==2&&i%5==3&&i%7==2)
{
printf("%d ",i);
j++;
if (j%5==0)
{printf(" ");}
}
}
return 0;
}
C語言是一種結構化的語言，提供的控制語句具有結構化特徵，如for語句、if⋯else語句和switch語句等。可以用於實現函數的邏輯控制，方便麵向過程的程序設計。
(5)c語言用除余留數法構建哈希表擴展閱讀：
C語言是面向過程的編程語言，用戶只需要關注所被解決問題的本身，而不需要花費過多的精力去了解相關硬體，且針對不同的硬體環境。
在用C語言實現相同功能時的代碼基本一致，不需或僅需進行少量改動便可完成移植，這就意味著，對於一台計算機編寫的C程序可以在另一台計算機上輕松地運行，從而極大的減少了程序移植的工作強度。
⑥ 利用C語言如何提取Excel中的數據並利用其中的數據生成哈希表
應該有專門的工具軟體吧，類似與fuzzytech，visual state之類的
⑦ 希望大家幫幫我啊！！！C語言 哈希表生成及哈希查找演算法 輸入：待哈希數據序列 功能要求：輸出哈希方法和
你看看這個哈希演算法吧、、貌似。，，也差不多咯
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
typedef int KeyType;
typedef struct /*元素類型定義*/
{
KeyType key; /*關鍵字*/
int hi; /*沖突次數*/
}DataType;
typedef struct /*哈希表類型定義*/
{
DataType *data;
int tableSize; /*哈希表的長度*/
int curSize; /*表中關鍵字個數*/
}HashTable;
void CreateHashTable(HashTable *H,int m,int p,int hash[],int n);
int SearchHash(HashTable H,KeyType k);
void DisplayHash(HashTable H,int m);
void HashASL(HashTable H,int m);
void CreateHashTable(HashTable *H,int m,int p,int hash[],int n)
/*構造一個空的哈希表，並處理沖突*/
{
int i,sum,addr,di,k=1;
(*H).data=(DataType*)malloc(m*sizeof(DataType));/*為哈希表分配存儲空間*/
if(!(*H).data)
exit(-1);
for(i=0;i<m;i++) /*初始化哈希表*/
{
(*H).data[i].key=-1;
(*H).data[i].hi=0;
}
for(i=0;i<n;i++) /*求哈希函數地址並處理沖突*/
{
sum=0; /*沖突的次數*/
addr=hash[i]%p; /*利用除留余數法求哈希函數地址*/
di=addr;
if((*H).data[addr].key==-1) /*如果不沖突則將元素存儲在表中*/
{
(*H).data[addr].key=hash[i];
(*H).data[addr].hi=1;
}
else /*用線性探測再散列法處理沖突*/
{
do
{
di=(di+k)%m;
sum+=1;
} while((*H).data[di].key!=-1);
(*H).data[di].key=hash[i];
(*H).data[di].hi=sum+1;
}
}
(*H).curSize=n; /*哈希表中關鍵字個數為n*/
(*H).tableSize=m; /*哈希表的長度*/
}
int SearchHash(HashTable H,KeyType k)
/*在哈希表H中查找關鍵字k的元素*/
{
int d,d1,m;
m=H.tableSize;
d=d1=k%m; /*求k的哈希地址*/
while(H.data[d].key!=-1)
{
if(H.data[d].key==k)/*如果是要查找的關鍵字k，則返回k的位置*/
return d;
else /*繼續往後查找*/
d=(d+1)%m;
if(d==d1) /*如果查找了哈希表中的所有位置，沒有找到返回0*/
return 0;
}
return 0; /*該位置不存在關鍵字k*/
}
void DisplayHash(HashTable H,int m)
/*輸出哈希表*/
{
int i;
printf("哈希表地址：");
for(i=0;i<m;i++)
printf("%-5d",i);
printf("\n");
printf("關鍵字key: ");
for(i=0;i<m;i++)
printf("%-5d",H.data[i].key);
printf("\n");
printf("沖突次數： ");
for(i=0;i<m;i++)
printf("%-5d",H.data[i].hi);
printf("\n");
}
void HashASL(HashTable H,int m)
/*求哈希表的平均查找長度*/
{
float average=0;
int i;
for(i=0;i<m;i++)
average=average+H.data[i].hi;
average=average/H.curSize;
printf("平均查找長度ASL=%.2f",average);
printf("\n");
}
void main()
{
int hash[]={23,35,12,56,123,39,342,90};
int m=11,p=11,n=8,pos;
KeyType k;
HashTable H;
CreateHashTable(&H,m,p,hash,n);
DisplayHash(H,m);
k=123;
pos=SearchHash(H,k);
printf("關鍵字%d在哈希表中的位置為：%d\n",k,pos);
HashASL(H,m);
}
⑧ 如何用C語言中實現哈希表
C++有 map,set
還有其他的，看STL相關的吧
數組還慢....
⑨ C語言哈希表
/#include "iostream.h"
#include <iostream>
#include "string.h"
#include "fstream"
#define NULL 0
unsigned int key;
unsigned int key2;
int *p;
struct node //建節點
{
char name[8],address[20];
char num[11];
node * next;
};
typedef node* pnode;
typedef node* mingzi;
node **phone;
node **nam;
node *a;
using namespace std; //使用名稱空間
void hash(char num[11]) //哈希函數
{
int i = 3;
key=(int)num[2];
while(num[i]!=NULL)
{
key+=(int)num[i];
i++;
}
key=key%20;
}
void hash2(char name[8]) //哈希函數
{
int i = 1;
key2=(int)name[0];
while(name[i]!=NULL)
{
key2+=(int)name[i];
i++;
}
key2=key2%20;
}
node* input() //輸入節點
{
node *temp;
temp = new node;
temp->next=NULL;
cout<<"輸入姓名："<<endl;
cin>>temp->name;
cout<<"輸入地址："<<endl;
cin>>temp->address;
cout<<"輸入電話："<<endl;
cin>>temp->num;
return temp;
}
int apend() //添加節點
{
node *newphone;
node *newname;
newphone=input();
newname=newphone;
newphone->next=NULL;
newname->next=NULL;
hash(newphone->num);
hash2(newname->name);
newphone->next = phone[key]->next;
phone[key]->next=newphone;
newname->next = nam[key2]->next;
nam[key2]->next=newname;
return 0;
}
void create() //新建節點
{
int i;
phone=new pnode[20];
for(i=0;i<20;i++)
{
phone[i]=new node;
phone[i]->next=NULL;
}
}
void create2() //新建節點
{
int i;
nam=new mingzi[20];
for(i=0;i<20;i++)
{
nam[i]=new node;
nam[i]->next=NULL;
}
}
void list() //顯示列表
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=phone[i]->next;
while(p)
{
cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;
p=p->next;
}
}
}
void list2() //顯示列表
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=nam[i]->next;
while(p)
{
cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;
p=p->next;
}
}
}
void find(char num[11]) //查找用戶信息
{
hash(num);
node *q=phone[key]->next;
while(q!= NULL)
{
if(strcmp(num,q->num)==0)
break;
q=q->next;
}
if(q)
cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl;
else cout<<"無此記錄"<<endl;
}
void find2(char name[8]) //查找用戶信息
{
hash2(name);
node *q=nam[key2]->next;
while(q!= NULL)
{
if(strcmp(name,q->name)==0)
break;
q=q->next;
}
if(q)
cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl;
else cout<<"無此記錄"<<endl;
}
void save() //保存用戶信息
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=phone[i]->next;
while(p)
{
fstream iiout("out.txt", ios::out);
iiout<<p->name<<"_"<<p->address<<"_"<<p->num<<endl;
p=p->next;
}
}
}
void menu() //菜單
{
cout<<"0.添加記錄"<<endl;
cout<<"3.查找記錄"<<endl;
cout<<"2.姓名散列"<<endl;
cout<<"4.號碼散列"<<endl;
cout<<"5.清空記錄"<<endl;
cout<<"6.保存記錄"<<endl;
cout<<"7.退出系統"<<endl;
}
int main()
{
char num[11];
char name[8];
create();
create2() ;
int sel;
while(1)
{
menu();
cin>>sel;
if(sel==3)
{ cout<<"9號碼查詢，8姓名查詢"<<endl;
int b;
cin>>b;
if(b==9)
{ cout<<"請輸入電話號碼:"<<endl;
cin >>num;
cout<<"輸出查找的信息:"<<endl;
find(num);
}
else
{ cout<<"請輸入姓名:"<<endl;
cin >>name;
cout<<"輸出查找的信息:"<<endl;
find2(name);}
}
if(sel==2)
{ cout<<"姓名散列結果:"<<endl;
list2();
}
if(sel==0)
{ cout<<"請輸入要添加的內容:"<<endl;
apend();
}
if(sel==4)
{ cout<<"號碼散列結果:"<<endl;
list();
}
if(sel==5)
{ cout<<"列表已清空:"<<endl;
create();
create2();
}
if(sel==6)
{ cout<<"通信錄已保存:"<<endl;
save();
}
if(sel==7) return 0;
}
return 0;
}
⑩ 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 的約數越多，發生這種余數分布不均勻的情況就越頻繁，沖突的幾率越高。而素數的約數是最少的，因此我們選用大素數。記住"素數是我們的得力助手"。
另一方面，一味的追求低沖突率也不好。理論上，是可以設計出一個幾乎完美，幾乎沒有沖突的函數的。然而，這樣做顯然不值得，因為這樣的函數設計很浪費時間而且編碼一定很復雜，與其花費這么大的精力去設計函數，還不如用一個雖然沖突多一些但是編碼簡單的函數。因此，函數還需要易於編碼，即易於實現。
綜上所述，設計一個好的哈希函數是很關鍵的。而"好"的標准，就是較低的沖突率和易於實現。