[数据结构] C ++基于无序链表实现符号表查找

符号表的主要目的是将键与值相关联. 用例可以将一个键值对插入到符号表中无序链表的快速查找，并希望通过键直接从符号表中的所有键值对中找到对应的值.

要实现符号表，我们必须首先定义其后面的数据结构，并指定创建和操纵该数据结构以实现诸如插入和搜索之类的操作所需的算法.

符号表中使用的数据结构的一个简单选项是链接列表，其中每个节点都存储一个键值对. 搜索的实现是遍历链表，将要搜索的键与每个节点中的键进行比较，如果匹配成功，则返回相应的值，否则返回null. 插入的实现还可以遍历链表，将要找到的密钥与每个节点中的密钥进行比较，如果匹配成功，则用第二个参数指定的值更新与该密钥关联的值，否则使用点的键值对将创建一个新节点，并将其插入到链表的开头.

此方法也称为顺序搜索: 在搜索中，逐一遍历符号表中的所有键，然后对它们进行比较以找到与搜索到的键匹配的键.

using namespace std;
template<class T, class K> class SequenyialSearch
{
public:
    SequenyialSearch(){}
    void put(T key, K value){
        //查找给定的键，找到则更新其值，否则在表中新建节点
        for(Node *x = m_pFirst; x != nullptr; x = x->m_pNext){
            if(key == x->m_key){
                x->m_value = value;
                return;
            }
        }
        m_pFirst = new Node(key, value, m_pFirst);
        if(m_pLast){
            m_pLast->m_pPre = m_pFirst;
        }
        m_pLast = m_pFirst;
        N++;
    }
    K get(T key){
        //查找给定的键返回相关联的值
        for(Node *x = m_pFirst; x != nullptr; x = x->m_pNext){
            if(key == x->m_key){
                return x->m_value;
            }
        }
        return K();
    }
    //从表中删去键key及对应的值
    void deleteKey(T key){
        for(Node *x = m_pFirst; x != nullptr; x = x->m_pNext){
            if(key == x->m_key){
                Node *pre = x->m_pPre;
                if(pre){
                    pre->m_pNext = x->m_pNext;
                }
                if(m_pFirst == x){
                    m_pFirst = x->m_pNext;
                    m_pLast = m_pFirst;
                }
                x->m_pNext = nullptr;
                delete x;
                x = nullptr;
                N--;
                return;
            }
        }
    }
    int size() {return N;}
    bool isEmpty() {return size() == 0;}
private:
    //要实现随便删除链表的某个结点，故使用双向链表
    struct Node{
        Node(T key, K value, Node *next):
            m_key(key), m_value(value), m_pNext(next)
        {
        }
        T m_key;
        K m_value;
        Node *m_pNext = nullptr;
        Node *m_pPre = nullptr;
    };
    Node *m_pFirst = nullptr;
    Node *m_pLast = nullptr;
    int N = 0;
};

要插入put（）的位置无序链表的快速查找，要找到get（）的位置，而deleteKey（）要删除的元素. 如果仅实现put和get，则只能使用一个单链表. 要实现deleteKey，需要使用一个双向链表，即遍历整个链表，根据密钥找到对应的节点，使该节点的上一个节点指向该节点的下一个节点，然后释放节点的资源. 但是，当删除第一个节点时，链表的头节点所指向的前一个节点和所指向的下一个节点都被设置为空，并且当前节点资源可以被释放并设置为空.

    SequenyialSearch<string, int> search;
    search.put("1", 1);
    search.put("3", 3);
    search.put("5", 5);
    cout << "value:" << search.get("5") << endl;
    search.deleteKey("1");
    cout << "value:" << endl
         << search.get("5") << endl
         << search.get("1") << endl
         << search.get("3") << endl;

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-248780-1.html