使用哈希表和鏈接列表的C++訪問衝突

所以我一直試圖創建一個處理1000個鏈表的類，並且最初聲明瞭指向它們的指針。使用哈希表和鏈接列表的C++訪問衝突

這是我的問題直接處理代碼：在while循環

struct node 
{ 
    char name[40]; 
    char numb[12]; 
    node * next; 
}; 
class hashTable 
{ 
public: 
    //Creates a table of 1000 pointers to linked-list nodes 
    node * table[1000]; 

//Functions 
void addNode(char name[40], char numb[12]) 
{ 
    node * temp;  //Initializes temp node as pointer 
    temp = new node; //Points temp node to a new node 

    int hash = h(g(name)); //The hash of the key (name) used to check nodes 
    temp = table[hash];  //sets the temporary node to the first node of the list 

    while (temp->next != 0) 
    { 
//...

右邊是我得到的錯誤「訪問衝突讀取位置0xcccccd00」我不知道爲什麼它可以」訪問表成員，除非可能是因爲這些值沒有被初始化或任何東西？

來源

2013-03-20 DatapawWolf

也許正是因爲這些值尚未初始化或什麼？ – Thomas 2013-03-20 18:52:20

或散列> 1000？ – Smash 2013-03-20 18:54:36

我會說這是從未初始化的內存偏移。由於0xcccccccc表示在VC調試模式下未初始化。 http://stackoverflow.com/questions/127386/in-visual-studio-c-what-are-the-memory-allocation-representations – drescherjm 2013-03-20 18:57:07

你可能不會做兩件事。首先確保你的哈希表正確初始化爲包含所有NULL指針。其次，要確保從哈希表中檢索到的任何指針是有效之前來提領它：

對於第一個問題：

hashTable::hashTable() : table() 
{ 
}

而且，你要確保這個東西清理正確

hashTable::~hashTable() 
{ 
    for (size_t i=0;i<sizeof(table)/sizeof(table[0]); ++i) 
    { 
     node *temp = table[i]; 
     while (temp) 
     { 
      node *victim = temp; 
      temp = temp->next; 
      delete victim; 
     } 
    } 
}

對於第二個問題：

void addNode(const char *name, const char *numb) 
{ 
    int hash = h(g(name)); //The hash of the key (name) used to check nodes 
    node *temp = table[hash]; //sets the temporary node to the first node of the list 

    if (temp) 
    { 
     // preexisting entry. walk that list looking for matching key. 
     node **pp = &temp->next; 
     while (temp) 
     { 
      if (0 == strcmp(temp->name, name)) 
       break; 
      pp = &temp->next; 
      temp = temp->next; 
     } 

     // link to last node if not found in list 
     if (!temp) 
      *pp = new node(name, numb); 
    } 
    else 
    { // no prior entry. create a new one and store it at table[hash]. 
     table[hash] = new node(name, numb); 
    } 
}

注：以上代碼假設節點類作爲

struct node 
{ 
    char name[40]; 
    char numb[12]; 
    node * next; 

    node(const char* name_, const char *numb_) 
     : next() 
    { 
     strncpy(name, name_, sizeof(name)/sizeof(name[0])-1); 
     name[ sizeof(name)/sizeof(name[0])-1 ] = 0; 
     strncpy(numb, numb_, sizeof(numb)/sizeof(numb[0])-1); 
     numb[ sizeof(numb)/sizeof(numb[0])-1 ] = 0; 
    } 
};

親自落實，我會使用std::string

來源

2013-03-20 19:06:41 WhozCraig

這似乎比我的猜測更可能。結果temp =新節點;在這種情況下沒有意義。 – drescherjm 2013-03-20 19:08:14

非常感謝您的詳細解答。現在開始有意義了。 :) – DatapawWolf 2013-03-20 19:48:13

艾姆，最後一件事。使用代碼將指針初始化爲NULL，當我多次使用同一個確切條目時，此「if（temp）」現在永遠不會爲false。 – DatapawWolf 2013-03-20 20:26:58

如果散列值大於（或等於）1000，則temp將指向無效區域。

由於您正在覆蓋temp變量，所以您正在泄漏由new node分配的內存。

來源

2013-03-20 18:56:13 Akobold

使用哈希表和鏈接列表的C++訪問衝突

回答

相關問題