完了写了主函数又执行不了help - 数据结构与算法

/* *哈希表开放定址法 */ #include<stdio.h> #include<stdlib.h> #define MinTableSize 10 typedef int ElemType; enum KindOfEntry{Legitimate,Empty,Deleted}; typedef struct HashEntry { ElemType element; enum KindOfEntry info; }Cell; /* Cell *TheCells will be an array of */ /* HashEntry cells, allocated later */ typedef struct HashTbl { int TableSize; Cell *TheCells; }*HashTable; typedef int Index; typedef Index Position; /* Return next prime; assume N >= 10 */ int NextPrime(int N) { int i; if(N%2==0) N++; for(;;N+=2) { for(i=3;i*i<=N;i+=2) if(N%i==0) return 0; return N; } } /*Hash function for ints*/ Index Hash(ElemType Key,int TableSize) { return Key%TableSize; } HashTable InitializeTable(int TableSize) { HashTable H; int i; if(TableSize<MinTableSize) { printf("Table size too small"); return NULL; } /*Allocate table*/ H=(HashTable)malloc(sizeof(struct HashTbl)); if(NULL==H) printf("Out of space!!!\n"); H->TableSize=NextPrime(TableSize); /*Allocate array of cells*/ H->TheCells=(Cell *)malloc(sizeof(Cell)*H->TableSize); if(NULL==H->TheCells) { printf("Out of space!!!\n"); free(H); } for(i=0;i<H->TableSize;i++) { H->TheCells[i].info=Empty; H->TheCells[i].element=0; } return H; } Position Find(ElemType Key,HashTable H) { Position CurrentPos; int CollisionNum; CollisionNum=0; CurrentPos=Hash(Key,H->TableSize); while( H->TheCells[ CurrentPos ].info != Empty && H->TheCells[ CurrentPos ].element != Key )/* Probably need strcmp!! */ { CurrentPos+=2*++CollisionNum-1; if(CurrentPos>=H->TableSize) CurrentPos-=H->TableSize; } return CurrentPos; } void Insert(ElemType Key,HashTable H) { Position Pos; Pos=Find(Key,H); if(H->TheCells[Pos].info!=Legitimate) { H->TheCells[Pos].info=Legitimate;/*Ok to insert here*/ H->TheCells[Pos].element=Key;/*Probably need strcpy*/ } } HashTable ReHash(HashTable H) { int i,OldSize; Cell *OldCells; OldCells=H->TheCells; OldSize=H->TableSize; /*Get a new empty table*/ H=InitializeTable(2*OldSize); /*Scan through old table reinserting into new*/ for(i=0;i<OldSize;i++) if(OldCells[i].info==Legitimate) Insert(OldCells[i].element,H); free(OldCells); return H; } void traverseHash(HashTable H,int len) { int i; printf("哈希地址0~%d\n",len-1); for(i=0;i<len;i++) { if(H->TheCells[i].info=Legitimate)//有数据 printf("address=%d value=%d\n",i,H->TheCells[i].element); } } void DestroyTable(HashTable H) { free(H->TheCells); free(H); } int main() { HashTable H; int array[]={19,14,23,01,68,20,84,27,55,11,10,79}; int len=sizeof(array)/sizeof(array[0]); int i; // ElemType k; H=InitializeTable(len); for(i=0;i<len;i++) { Insert(array[i],H); } traverseHash(H,len); printf("\n\n"); return 0; }

/* *哈希表开放定址法 */ #include<stdio.h> #include<stdlib.h> #define MinTableSize 10 typedef int ElemType; enum KindOfEntry{Legitimate,Empty,Deleted}; typedef struct HashEntry { ElemType element; enum KindOfEntry info; }Cell; /* Cell *TheCells will be an array of */ /* HashEntry cells, allocated later */ typedef struct HashTbl { int TableSize; Cell *TheCells; }*HashTable; typedef int Index; typedef Index Position; /* Return next prime; assume N >= 10 */ int NextPrime(int N) { int i; if(N%2==0) N++; for(;;N+=2) { for(i=3;i*i<=N;i+=2) if(N%i==0) return 0; return N; } } /*Hash function for ints*/ Index Hash(ElemType Key,int TableSize) { return Key%TableSize; } HashTable InitializeTable(int TableSize) { HashTable H; int i; if(TableSize<MinTableSize) { printf("Table size too small"); exit(-1); } /*Allocate table*/ H=(HashTable)malloc(sizeof(struct HashTbl)); if(NULL==H) { printf("Out of space!!!\n"); exit(-1); } H->TableSize=NextPrime(TableSize); /*Allocate array of cells*/ H->TheCells=(Cell *)malloc(sizeof(Cell)*H->TableSize); if(NULL==H->TheCells) { printf("Out of space!!!\n"); free(H); } for(i=0;i<H->TableSize;i++) { H->TheCells[i].info=Empty; //H->TheCells[i].element=0; } return H; } Position Find(ElemType Key,HashTable H) { Position CurrentPos; int CollisionNum; CollisionNum=0; CurrentPos=Hash(Key,H->TableSize); while( H->TheCells[ CurrentPos ].info != Empty && H->TheCells[ CurrentPos ].element != Key )/* Probably need strcmp!! */ { CurrentPos+=2*++CollisionNum-1; if(CurrentPos>=H->TableSize) CurrentPos-=H->TableSize; } return CurrentPos; } void Insert(ElemType Key,HashTable H) { Position Pos; Pos=Find(Key,H); if(H->TheCells[Pos].info!=Legitimate) { H->TheCells[Pos].info=Legitimate;/*Ok to insert here*/ H->TheCells[Pos].element=Key;/*Probably need strcpy*/ } } HashTable ReHash(HashTable H) { int i,OldSize; Cell *OldCells; OldCells=H->TheCells; OldSize=H->TableSize; /*Get a new empty table*/ H=InitializeTable(2*OldSize); /*Scan through old table reinserting into new*/ for(i=0;i<OldSize;i++) if(OldCells[i].info==Legitimate) Insert(OldCells[i].element,H); free(OldCells); return H; } void traverseHash(HashTable H,int len) { int i; printf("哈希地址0~%d\n",len); for(i=0;i<len;i++) { if(H->TheCells[i].info!=Empty)//有数据 printf("address=%d value=%d\n",i,H->TheCells[i].element); } } void DestroyTable(HashTable H) { free(H->TheCells); free(H); } int main() { HashTable H; int array[]={19,14,23,01,68,20,84,27,55,11,10,79}; int len=sizeof(array)/sizeof(array[0]); int i; ElemType k; Position p; H=InitializeTable(len-1);//插入前len-1个记录 for(i=0;i<len-1;i++) { Insert(array[i],H); } traverseHash(H,len-1); printf("\n\n"); printf("please input the value which need find:"); scanf("%d",&k); p=Find(k,H); if(p>=0) printf("address=%d value=%d\n",p,H->TheCells[p].element); else printf("cannot find the value!"); printf("\n\n"); H=ReHash(H); traverseHash(H,2*len); printf("\n\n"); printf("please input the value which need find:"); scanf("%d",&k); p=Find(k,H); if(p>=0) printf("address=%d value=%d\n",p,H->TheCells[p].element); else printf("cannot find the value!"); printf("\n\n"); printf("free the table\n"); DestroyTable(H); printf("it's done!!!"); printf("\n\n"); return 0; }

第 6 楼

得分:0

我这个是依照严蔚敏数据结构算法写的代码，上次回答你B树的时候也是，里面有个&符号是引用变量的意思（属于c++范围），用这个比较方便~以下代码在VC++6.0通过运行。

程序代码：

#include<string.h> //字符串函数头文件
#include<ctype.h> //字符函数头文件
#include<malloc.h> //malloc()等
#include<stdio.h> //标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> //atoi()，exit()
#include<math.h> //数学函数头文件，包括floor()，ceil()，abs()等

//函数结果状态代码。
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; //Status是函数的类型，其值是函数结果状态代码，如OK等

#define NULL_KEY 0 // 0为无记录标志
#define N 15 // 数组可容纳的数据元素个数
int m; // 哈希表表长，全局变量
typedef int KeyType; // 定义关键字域为整型
struct ElemType // 数据元素类型
{ 
    KeyType key;
    int order;
};

// 对两个数值型关键字的比较约定为如下的宏定义。
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

//开放定址哈希表的存储结构。
int hashsize[]={11,19,29,37}; // 哈希表容量递增表，一个合适的素数序列
struct HashTable
{ 
    ElemType *elem; // 数据元素存储基址，动态分配数组
    int count; // 当前数据元素个数
    int sizeindex; // hashsize[sizeindex]为当前容量
};

#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

//哈希函数的基本操作
void InitHashTable(HashTable &H)
{    // 操作结果：构造一个空的哈希表
    int i;
    H.count=0; // 当前元素个数为0
    H.sizeindex=0; // 初始存储容量最小，为hashsize[0]
    m=hashsize[0]; // 哈希表表长，全局变量
    H.elem=(ElemType*)malloc(m*sizeof(ElemType));
    if(!H.elem)
        exit(OVERFLOW); // 存储分配失败
    for(i=0;i<m;i++)
        H.elem[i].key=NULL_KEY; // 未填记录的标志
}

void DestroyHashTable(HashTable &H)
{    // 初始条件：哈希表H存在。操作结果：销毁哈希表H
    free(H.elem); // 释放H.elem的存储空间
    H.elem=NULL;
    H.count=0;
    H.sizeindex=0;
}

unsigned Hash(KeyType K)
{    // 一个简单的哈希函数(m为表长，全局变量)
    return K%m;
}

int d(int i) // 增量序列函数，在以下3行中根据需要选取1行，其余2行作为注释
{ 
    return i; // 线性探测再散列
    //return ((i+1)/2)*((i+1)/2)*(int)pow(-1,i-1); // 二次探测再散列
    //return rand(); // 伪随机探测再散列
}

void collision(KeyType K,int &p,int i)
{ 
    p=(Hash(K)+d(i))%m; // 开放定址法处理冲突
}

Status SearchHash(HashTable H,KeyType K,int &p,int &c)
{    // 在开放定址哈希表H中查找关键字为K的元素，若查找成功，以p指示待查数据
    // 元素在表中位置，并返回SUCCESS；否则，以p指示插入位置，并返回UNSUCCESS
    // c用以计冲突次数，其初值置零，供建表插入时参考。
    p=Hash(K); // 求得哈希地址
    while(H.elem[p].key!=NULL_KEY&&!EQ(K,H.elem[p].key))
    {    // 该位置中填有记录．并且与待查找的关键字不相等
        c++; // 计冲突次数+1
        if(c<m) // 在H中有可能找到插入地址，修改
            collision(K,p,c); // 求得下一探查地址p
        else // 在H中不可能找到插入地址
            break; // 退出while循环
    }
    if EQ(K,H.elem[p].key) // 查找成功
        return SUCCESS; // p返回待查数据元素位置
    else // 查找不成功
        return UNSUCCESS; // H.elem[p].key==NULL_KEY，p返回的是插入位置
}

void RecreateHashTable(HashTable&); // 对函数RecreateHashTable()的声明
Status InsertHash(HashTable &H,ElemType e)
{    // 查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK；
    // 若冲突次数过大，则重建哈希表
    int p,c=0; // 冲突次数，初始为0
    if(SearchHash(H,e.key,p,c)) // 查找成功
        return DUPLICATE; // H中已有与e有相同关键字的元素，不再插入
    else if(c<hashsize[H.sizeindex]/2) // 未找到，冲突次数也c未达到上限，(c的阀值可调)
    { 
        H.elem[p]=e; // 在H中插入数据元素e
        ++H.count; // H的数据元素个数+1
        return OK; // 插入成功
    }
    else // 未找到，但冲突次数c已达到上限
    { 
        RecreateHashTable(H); // 重建哈希表
        return UNSUCCESS; // 插入不成功，需重新插入
    }
}

void RecreateHashTable(HashTable &H)
{    // 重建哈希表H
    int i,count=H.count; // H中原有数据个数
    ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));
    // 动态生成存放哈希表H原有数据的空间
    p=elem; // p指向elem
    for(i=0;i<m;i++) // 将H原有的第1个数据到最后1个数据，保存到elem中
        if((H.elem+i)->key!=NULL_KEY) // H在该单元有数据
            *p++=*(H.elem+i); // 将数据依次存入elem
    H.count=0; // H的当前数据元素个数为0
    H.sizeindex++; // 增大存储容量为下一个序列数
    m=hashsize[H.sizeindex]; // 新的存储容量
    H.elem=(ElemType*)realloc(H.elem,m*sizeof(ElemType));
    // 以新的存储容量重新生成空哈希表H
    for(i=0;i<m;i++)
        H.elem[i].key=NULL_KEY; // 未填记录的标志(初始化)
    for(p=elem;p<elem+count;p++) // 将原有的数据按照新的表长插入到重建的哈希表中
        InsertHash(H,*p);
    free(elem); // 释放elem的存储空间
}

void TraverseHash(HashTable H,void(*Visit)(int,ElemType))
{    // 按哈希地址的顺序遍历哈希表H
    int i;
    printf("哈希地址0～%d\n",m-1);
    for(i=0;i<m;i++) // 对于整个哈希表H
        if(H.elem[i].key!=NULL_KEY) // H在第i个单元有数据
            Visit(i,H.elem[i]); // 访问第i个数据
}


void Visit(int p,ElemType r)
{ 
    printf("address=%d (%d,%d)\n",p,r.key,r.order);
}

void main()
{
    ElemType r[N]; // 记录数组
    HashTable h;
    int i,n,p=0;
    Status j;
    KeyType k;
    printf("输入10个记录(最后一个为待插入的记录)：\n");
    do // 输入10个记录
    { 
        scanf("%d%d",&r[p].key,&r[p].order); // 输入数据
        p++;
    }while(p<10&&p<N); // p<10且记录数组未满
    InitHashTable(h); // 构造一个空的哈希表h
    for(i=0;i<p-1;i++)
    { 
        j=InsertHash(h,r[i]); // 在h中插入前p-1个记录(最后1个记录不插入)
        if(j==DUPLICATE)
            printf("表中已有关键字为%d的记录，无法再插入记录(%d,%d)\n",
        r[i].key,r[i].key,r[i].order);
    }
    printf("按哈希地址的顺序遍历哈希表：\n");
    TraverseHash(h,Visit); // 按哈希地址的顺序遍历哈希表h
    printf("请输入待查找记录的关键字：");
    scanf("%d",&k); // 输入待查找记录的关键字
    j=SearchHash(h,k,p,n); // 查找时n值无用
    if(j==SUCCESS) // 查找成功
        Visit(p,h.elem[p]); // 输出该纪录
    else // 查找失败
        printf("未找到\n"); // 输出未找到信息
    j=InsertHash(h,r[i]); // 插入最后1个记录(需重建哈希表)
    if(j==ERROR) // 重建哈希表
        j=InsertHash(h,r[i]); // 重建哈希表后重新插入
    printf("按哈希地址的顺序遍历重建后的哈希表：\n");
    TraverseHash(h,Visit); // 按哈希地址的顺序遍历哈希表h
    printf("请输入待查找记录的关键字：");
    scanf("%d",&k); // 输入待查找记录的关键字
    j=SearchHash(h,k,p,n); // 查找时n值无用
    if(j==SUCCESS) // 查找成功
        Visit(p,h.elem[p]); // 输出该纪录
    else // 查找失败
        printf("未找到\n"); // 输出未找到信息
    DestroyHashTable(h); // 销毁哈希表h
}

图片附件: 游客没有浏览图片的权限，请登录或注册

A real warrior never quits.