哈系表的有关问题

2013-06-25

哈系表的问题#includeiostream#includemath.husing namespace stdtypedef struct Node{int Key// 关

哈系表的问题


#include<iostream>
#include<math.h>
using namespace std;

typedef struct Node
{
int Key;                        // 关键字
    struct Node* pNext;
}NODE,*PNODE;

struct HeadNode
{
PNODE pNext;
};

class HashTable
{
public:
HashTable(); 
~HashTable();
void Traverse();
bool Insert(int Key);
bool Delete(int Key);
int H(int Key);
protected:
HeadNode* ht;                   // 此为首个散列地址，每个散列地址将建立一个单链表                                 
};

int HashTable::H(int Key)
{
return Key%10;                   // 除留余法的除数设为10，可以作为是头结点指针索引的数量
}

HashTable::HashTable()
{
ht=new HeadNode[10];
for(int i=0;i<10;i++)
{
ht[i].pNext=NULL; 
}
}

HashTable::~HashTable()
{
NODE *w,*q;
for(int i=0;i<10;i++)
{
w=ht[i].pNext;
while(w)
{
q=w;
delete w;
w=q->pNext;
}
}
delete []ht;               // 释放指针索引结点
}

void HashTable::Traverse()
{
int i;
PNODE temp;
for(i=0;i<10;i++)
{
cout<<i<<":";
temp=ht[i].pNext;
while(temp)
{
cout<<temp->Key<<" ";
temp=temp->pNext;
}
cout<<endl;
}
}

bool HashTable::Insert(int Key)
{
int pos;
pos=H(Key);
PNODE pNew=new NODE;
pNew->Key=Key;
pNew->pNext=ht[pos].pNext; 
ht[pos].pNext=pNew;
return true;
}

bool HashTable::Delete(int Key)
{
int pos,flag=0;
pos=H(Key);
PNODE p=new NODE;
p->pNext=ht[pos].pNext;
PNODE q=NULL;
while(p->pNext->pNext!=NULL)
{
if(p->pNext->Key==Key)
{
q=p->pNext;
p->pNext=q->pNext;
delete q;
flag=1;
}
else
p=p->pNext;
}
if(flag)
return true;
else
return false;
}



class Interface
{
protected:
HashTable A;
public:
void Run();
void Input();
void Insert();
void Delete();
void Output();
};



void Interface::Run()
{
int choice;
cout<<"0.退出"<<endl;
cout<<"1.录入"<<endl;
cout<<"2.插入"<<endl;
cout<<"3.删除"<<endl;
cout<<"4.输出"<<endl;
do
{
cin>>choice;
switch(choice)
{
case 0:exit(-1);
case 1:
Input();
break;
case 2:
Insert();
break;
case 3:
Delete();
break;
case 4:
Output();
break;
}
}while(choice);
}

void Interface::Input()
{
int Key; 
 
cout<<"输入关键字"<<endl;
cin>>Key;
A.Insert(Key);
}

void Interface::Insert()
{
int Key;
cout<<"输入关键字"<<endl;
cin>>Key;
A.Insert(Key);
}

void Interface::Delete()
{
int Key;
cout<<"键入所删除关键字"<<endl;
cin>>Key;
A.Delete(Key);
/*if(HashTable::A.Delete(Key))
cout<<"删除成功"<<endl;
else
cout<<"无所删除关键字"endl;
*/
}

void Interface::Output()
{
A.Traverse();
}

int main()
{
//HashTable A(10);
Interface in;
in.Run();
return 0;
}

上面bool HashTable::Delete(int Key)这个函数里删除某个元素老是出错。。大神看看吧
[解决办法]
试改如下：

bool HashTable::Delete(int Key)
{
int pos,flag=0;
pos=H(Key);
PNODE p,h;//PNODE p=new NODE;
h=p=ht[pos].pNext;//p->pNext=ht[pos].pNext;
PNODE q=NULL;
while(p!=NULL)//while(p->pNext->pNext!=NULL)
{
if(p->Key==Key)//if(p->pNext->Key==Key)
{
      if (p==ht[pos].pNext)//added
      {
        ht[pos].pNext=p->pNext;//added
      }
      else//added
      {
        h->pNext=p->pNext;//added
      }
q=p;
p=q->pNext;
delete q;
flag=1;
}
else
    {
      h=p;//added
      p=p->pNext;
    }
}
if(flag)
return true;
else
return false;
}

[解决办法]


bool HashTable::Delete(int Key)
{
    int pos,flag=0;
    pos=H(Key);
    PNODE p=new NODE;//临时对象还要动态分配？而且没有释放……
   
    p->pNext=ht[pos].pNext;
    PNODE q=NULL;
    while(p->pNext->pNext!=NULL)//该链表的最后一个节点就不删除吗？
    {
        if(p->pNext->Key==Key)//最后一个节点明显也有数据
        {
            q=p->pNext;
            p->pNext=q->pNext;
            delete q;
            flag=1;
        }
        else
            p=p->pNext;
    }
    if(flag)
        return true; 
 
    else
        return false;
}

[解决办法]


bool HashTable::Delete(int Key)
{
    int pos = H(Key);//hash_key
    bool deleted = false;//是否有删除动作
    PNODE p=&(ht[pos]);//p指向链表头节点，p->next为当前数据节点
    PNODE q=NULL;//临时变量，用于删除。
    while(p->pNext!=NULL)//遍历所有节点
    {
        if(p->pNext->Key==Key)//当前节点需要删除
        {
            q=p->pNext;
            p->pNext=q->pNext;
            delete q;
            deleted = true;
        }
        else
        {
            p=p->pNext;
        }
    }
    
    return deleted;
}

热点排行

C++

哈系表的有关问题