c++ - 遍历链表以查找字符串

Question

我需要遍历链表 vector 并检查是否存在具有字符串的节点。显然，这只会检查开头以查看它是否存在。我想知道如何遍历整个链表。

vector <Dlist *> table; //Dlist is the linked list

int DL_Hash::Present(string &s) {

    int index = djb_hash(s) % table.size();
    for(int i = 0; i < table[index]->Size(); i++) {
        if(table[index]->Begin()->s == s) {
            return 1;
        }
    }
    return 0;
}

Answer 1

你根本没有使用变量 i，你确实不能做像 table[index][i] 这样的事情，因为你不能索引链表。您只能获取列表中的第一个元素，紧随其后。

首先你得到指向开始的指针(迭代器会更合适)。然后根据您的情况检查每个项目，直到您位于列表的末尾。

int DL_Hash::Present(string &s) {

    int index = djb_hash(s) % table.size();
    auto tmp = table[index]->Begin();
    while (tmp != nullptr) { // check if you are at end of linked list
        if (tmp->s == s)
            return 1;
        tmp = tmp.Next(); // asuming you have function to get next element in linked list.
    }
    return 0;
}

如果 Dlist 有迭代器:

int DL_Hash::Present(string &s) {

    int index = djb_hash(s) % table.size();
    auto tmp = table[index]->begin();
    while (tmp != table[index].end()) { // check if you are at end of linked list
        if (tmp->s == s)
            return 1;
        tmp++;
    }
    return 0;
}

或者更好的是，使用 range for

int DL_Hash::Present(string &s) {

    int index = djb_hash(s) % table.size();
    for (auto &tmp : table[index]) {
        if (tmp->s == s)
            return 1;
        }
    return 0;
}