搜索
编程论坛 → 开发语言 → 『 数据结构与算法 』 → 完了 写了主函数 又执行不了help
标题：完了 写了主函数 又执行不了help
只看楼主
世界模型
Rank: 4
等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12
结帖率：97.44%
楼主
 已结贴√  问题点数：20 回复次数：6 
完了 写了主函数 又执行不了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;
}
2011-08-17 22:13
世界模型
Rank: 4
等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12
第 2 楼
 得分:0 
分析了下  问题在插入的部分
可是 调了好久 应该没错 大家帮忙看下啊
2011-08-17 22:33
QQ346957135
Rank: 7Rank: 7Rank: 7
等　级：黑侠
帖　子：148
专家分：658
注　册：2011-8-9
第 3 楼
 得分:20 
我还以为你做出来了呢。晚上帮你看看~

A real warrior never quits.
2011-08-18 08:59
世界模型
Rank: 4
等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12
第 4 楼
 得分:0 
谢谢啦
没有哦  哈希表 部分学的不好
2011-08-18 10:23
世界模型
Rank: 4
等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12
第 5 楼
 得分: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;
}
重建之后 元素79 依然插不进去
2011-08-18 13:08
QQ346957135
Rank: 7Rank: 7Rank: 7
等　级：黑侠
帖　子：148
专家分：658
注　册：2011-8-9
第 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.
2011-08-18 19:35
世界模型
Rank: 4
等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12
第 7 楼
 得分:0 
严版的我写过  
上面的我是在数据结构算法与分析里看到的 感觉那个更简练写 所以还是想 把那个搞懂
2011-08-18 21:10



参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-347808-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有，并保留所有权利。
Powered by Discuz, Processed in 2.188454 second(s), 9 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved