c語言實現哈希
A. C語言怎麼實現有重復元素的全排列
整體思路就是利用回溯的思想，也可認為是深度優先搜索
從字元串第一位idx=0開始，每次遞歸都從s[idx]之後選擇一個字元與s[idx]交換
因為可能有重復字元，可使用哈希數組標記當前循環每個字元是否被選擇
因為字元范圍不超過ASCII碼，所以使用128空間的數組足夠用來標記了
選擇好當前字元s[i]並與s[idx]交換之後，遞歸調用繼續排列下一位s[idx+1]
注意這里要進行回溯，即不選s[i]而選擇之後的某個字元交換到s[idx]
所以要將之前的s[i]與s[idx]交換過來，恢復原狀，才能循環判斷下一個選擇
具體代碼截圖如下：
結果正確，望採納~
附源碼：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000000 // 排列總數可能很多
int num = 0; // 記錄排列總數
char *res[MAXN] = {NULL}; // 指針數組保存排列結果
void swap(char *x, char *y) { // 交換兩個字元變數的內容
char ch = *x;
*x = *y;
*y = ch;
}
void perm(char *s, int n, int idx) { // 回溯產生字元串全排列
if (idx == n) { // 已排列到字元串結尾
res[num] = (char *)malloc(sizeof(char) * (n + 1));
//printf("%s ", s); // 輸出當前排列
strcpy(res[num], s); // 保存當前排列
num++; // 排列總數加1
return;
}
int i, hash[128] = {0}; // 哈希數組，標記每個字元是否被選擇
for (i = idx; i < n; i++) {
if (hash[s[i]] == 1)
continue; // 跳過已被標記過的重復字元
hash[s[i]] = 1; // 選過的話在數組中標記為1
swap(&s[idx], &s[i]); // 選擇s[i]交換到s[idx]
perm(s, n, idx + 1); // 遞歸，繼續s[idx+1]的選擇
swap(&s[idx], &s[i]); // 回溯，當前不選擇s[i]，而選擇其他字元
}
}
int main() {
int n, i;
scanf("%d", &n);
char *s = (char *)malloc(sizeof(char) * (n + 1));
scanf("%s", s);
perm(s, n, 0);
printf("一共有%d種排列: ", num); // 輸出排列總數
for (i = 0; i < num; i++) { // 輸出所有排列
printf("%s ", res[i]);
free(res[i]); // 釋放內存空間
}
free(s);
return 0;
}
B. 這段C語言代碼如何轉換成Python語言（關於哈希表）
將以上 C 語言代碼轉換為 Python 語言可能需要對哈希表和其他數據結構進行重新實現。但是可以提供一個類似的實現方式
def search_hash(hash_table, name):
collisions = 0 # to keep track of number of collisions
index = hash_function(name)
while hash_table[index] is not None and hash_table[index]['name'] != name:
collisions += 1
index = collision_resolution(index)
if hash_table[index] is not None:
print("Search successful! Number of collisions:", collisions)
print("Name: ", hash_table[index]['name'])
print("ID: ", hash_table[index]['id'])
print("Phone: ", hash_table[index]['phone'])
else:
print("Search unsuccessful.")
這個例子使用了字典來存儲聯系人的信息，其中 'name'，'id' 和 'phone' 是字典的鍵。hash_function() 和 collision_resolution() 函數可以用 Python 中的內置函數來實現，或者自己實現。
注意，這只是一種類似的實現方式，並不能完全替代原來的代碼，還需要根據實際需求進行修改。
另外,在 Python 中可以使用字典或字典組成的列表來存肆指儲哈希表,可以使用字典中的 get() 方法或者列表中的 in 關鍵字來查找一個元素是否在字典或列表中，如果要實現類似 C 語言中的沖突解決方式明察，可以在字典中使用鏈表或線性探測法來實現激雹茄。
這里只是給出了一種可能的實現方式，具體實現還需要根據具體需求進行調整。
C. C語言版數據結構哈希演算法題：設m=16,HASH函數為H（key）=key mod 13,現採用再哈希法Hi=RHi(key）處理沖突
應該是這個意思：
第一次沖突就是散列的位置+1，這次發生沖突了就繼續第二次
第二次用的是平方取中，55^2= 3025，當然第二次沖突的RH2就是02了，答案(2)
D. 哈希造表: 為某個集體"人名"設計一個哈希表,平均查找長度不超過2,假設30個待填入的人名為拼音形式.
這個是我們的作業 ^^根據自己的需要改一下就行了
#include <stdio.h>
#include<malloc.h>
#include<string.h>
//#include
#define HASH_LEN 50 //哈希表的長度
#define M 47
#define NAME_NO 30 //人名的個數
typedef struct NAME
{
char *py; //名字的拼音
int k; //拼音所對應的整數
}NAME;
NAME NameList[HASH_LEN];
typedef struct hterm //哈希表
{
char *py; //名字的拼音
int k; //拼音所對應的整數
int si; //查找長度
}HASH;
HASH HashList[HASH_LEN];
/*-----------------------姓名（結構體數組）初始化---------------------------------*/
void InitNameList()
{
NameList[0].py="chenghongxiu";
NameList[1].py="yuanhao";
NameList[2].py="yangyang";
NameList[3].py="zhanghen";
NameList[4].py="chenghongxiu";
NameList[5].py="xiaokai";
NameList[6].py="liupeng";
NameList[7].py="shenyonghai";
NameList[8].py="chengquan";
NameList[9].py="luqing";
NameList[10].py="gongyunxiang";
NameList[11].py="sunzhenxing";
NameList[12].py="sunrongfei";
NameList[13].py="sunminglong";
NameList[14].py="zhanghao";
NameList[15].py="tianmiao";
NameList[16].py="yaojianzhong";
NameList[17].py="yaojianqing";
NameList[18].py="yaojianhua";
NameList[19].py="yaohaifeng";
NameList[20].py="chengyanhao";
NameList[21].py="yaoqiufeng";
NameList[22].py="qianpengcheng";
NameList[23].py="yaohaifeng";
NameList[24].py="bianyan";
NameList[25].py="linglei";
NameList[26].py="fuzhonghui";
NameList[27].py="huanhaiyan";
NameList[28].py="liudianqin";
NameList[29].py="wangbinnian";
char *f;
int r,s0;
for (int i=0;i<NAME_NO;i++)// 求出各個姓名的拼音所對應的整數
{
s0=0;
f=NameList[i].py;
for (r=0;*(f+r) != '\0';r++) //方法：將字元串的各個字元所對應的ASCII碼相加，所得的整數做為哈希表的關鍵字
s0=*(f+r)+s0;
NameList[i].k=s0;
}
}
/*-----------------------建立哈希表---------------------------------*/
void CreateHashList()
{
for (int i=0; i<HASH_LEN;i++)//哈希表的初始化
{
HashList[i].py="";
HashList[i].k=0;
HashList[i].si=0;
}
for (i=0; i<NAME_NO;)
{
int sum=0;
int adr=(NameList[i].k) % M; //哈希函數
int d=adr;
if(HashList[adr].si==0) //如果不沖突
{
HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;
}
else //沖突
{
do
{
d=(d+((NameList[i].k))%10+1)%M; //偽散列
sum=sum+1; //查找次數加1
}while (HashList[d].k!=0);
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}i++;
}
}
/*-------------------------------------查找------------------------------------*/
void FindList()
{
printf("\n\n請輸入姓名的拼音: "); //輸入姓名
char name[20]={0};
scanf("%s",name);
int s0=0;
for (int r=0;r<20;r++) //求出姓名的拼音所對應的整數(關鍵字)
s0+=name[r];
int sum=1;
int adr=s0 % M; //使用哈希函數
int d=adr;
if(HashList[adr].k==s0) //分3種情況進行判斷
printf("\n姓名:%s 關鍵字:%d 查找長度為: 1",HashList[d].py,s0);
else if (HashList[adr].k==0)
printf("無該記錄!");
else
{
int g=0;
do
{
d=(d+s0%10+1)%M; //偽散列
sum=sum+1;
if (HashList[d].k==0)
{
printf("無記錄! ");
g=1;
}
if (HashList[d].k==s0)
{
printf("\n姓名:%s 關鍵字:%d 查找長度為:%d",HashList[d].py,s0,sum);
g=1;
}
}while(g==0);
}
}
/*--------------------------------顯示哈希表----------------------------*/
void Display()
{
printf("\n\n地址\t關鍵字\t\t搜索長度\tH(key)\t\t拼音 \n"); //顯示的格式
for(int i=0; i<15; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意鍵繼續顯示...\n"); //由於數據比較多，所以分屏顯示（以便在Win9x／DOS下能看到所有的數據）
// getch();
for( i=15; i<30; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意鍵繼續顯示...\n");
// getch();
for( i=30; i<40; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
//printf("按任意鍵繼續顯示...\n");
//getch();
for( i=40; i<50; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
float average=0;
for (i=0;i<HASH_LEN;i++)
average+=HashList[i].si;
average/=NAME_NO;
printf("\n\n平均查找長度：ASL(%d)=%f \n\n",NAME_NO,average);
}
/*--------------------------------主函數----------------------------*/
void main()
{
/* ::SetConsoleTitle("哈希表操作"); //Windows API函數,設置控制台窗口的標題
HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //獲得標准輸出設備的句柄
::SetConsoleTextAttribute(hCon, 10|0); //設置文本顏色
*/
printf("\n------------------------哈希表的建立和查找----------------------");
InitNameList();
CreateHashList ();
while(1)
{
printf("\n\n");
printf(" 1. 顯示哈希表\n");
printf(" 2. 查找\n");
printf(" 3. 退出\n");
err:
char ch1;
scanf("%c",&ch1);
if (ch1=='1')
Display();
else if (ch1=='2')
FindList();
else if (ch1=='3')
return;
else
{
printf("\n請輸入正確的選擇!");
goto err;
}
}
}