使用链表实现符号表

链表可实现灵活快速地插入、删除任意位置元素
但查找特定元素需遍历链表

1. 结构介绍

每个节点node是一个class，存放键、值和next指针，next指针指向下一个node地址

template <class T1, class T2>
class Node
{
public:
    Node<T1, T2>* next;
    T1 key;
    T2 value;
};

2. 基本操作

2.1 添加元素

1. 添加新节点后，新节点的next指针指向head的next指针指向的地址（注意顺序：更新head节点前，先把需要用上的值给用了，避免更新后值被覆盖）
2. 更新head节点：头节点head的next指针指向新节点的地址

链表需要维护两个地址：当前节点所在地址、next指针指向的地址

//添加元素，默认为有序表
//判断表中是否已经存在相应key值
//true：更新key对应的value
//false：插入(key, value)对
template <class Key, class Value>
inline void ST<Key, Value> :: put(Key key, Value value, bool isSort)
{
    Node<Key, Value>* node = get(key);
    if (node != NULL)  node->value=value;
    else if(node == NULL)
    {
        node = new Node<Key, Value>;
        node->key = key;
        node->value = value;
        //插入位置决定表是否有序
        if (isSort == false)
        {
            //无序表直接从头插入
            node->Next = head->Next;
            head->Next = node;
        }
        else if (isSort == true)
        {
            //有序表找到比自己大的节点
            //插到该节点前面
            Node<Key, Value>* pCurr = head->Next;
            Node<Key, Value>* pPrev = head;
            while(pCurr != NULL)
            {
                if (pCurr->key > key) break;
                pCurr = pCurr->Next;
                pPrev = pPrev->Next;
            }
            pPrev->Next = node;
            node->Next = pCurr;
        }
        length ++;
    }
}

2.2 删除元素

将给定key的value值置为NULL

2.3 判断元素是否在表内

遍历表即可，链表的遍历关键在于next指针值的更新

template <class T1, class T2>
bool ST<T1, T2> :: contain(T1 key)
{
    Node<T1, T2>* currNode = head->next; //节点都是以地址存放的
    while (currNode != NULL)
    {
        if (currNode->key == key)   return true;
        currNode = currNode->next;    
    }
    return false;
}

2.4 输出

//输出表
template <class Key, class Value>
inline void ST<Key, Value> ::print()
{
    Node<Key, Value>* pCurr = head->Next;
    while (pCurr != NULL)
    {
        cout<<"key is "<<pCurr->key<<" "<<"value is "<<pCurr->value<<endl;
        pCurr = pCurr->Next;
    }
}

3. 示例代码

/*
copyright: Zheng Yeping
time: 2021-7-11
*/
#pragma once
#include <iostream>
using namespace std;

//定义链表节点
template <class Key, class Value>
class Node
{
public:
    Node<Key, Value>* Next;
    Key key;
    Value value;
};

template <class Key, class Value>
class ST
{
public:
    ST();
    ~ST();
    void put(Key, Value, bool isSort=true);
    Node<Key,Value>* get(Key);
    void remove(Key);
    void print();
    bool isEmpty();
    bool isContain(Key);
private:
    Node<Key, Value>* head;
    int length;
};

//相关函数功能实现
template <class Key, class Value> 
ST<Key,Value> :: ST()
{
    this->head = new Node<Key, Value>;
    head->Next = NULL;
    length = 0;
}

template <class Key, class Value> 
ST<Key,Value> :: ~ST()
{
    Node<Key, Value>* pCurr = head->Next;
    while (pCurr != NULL)
    {
        head->Next = pCurr->Next;
        delete pCurr->Next;
        pCurr = head->Next;
    }
    delete head;
}

//添加元素，默认为有序表
//判断表中是否已经存在相应key值
//true：更新key对应的value
//false：插入(key, value)对
template <class Key, class Value>
inline void ST<Key, Value> :: put(Key key, Value value, bool isSort)
{
    Node<Key, Value>* node = get(key);
    if (node != NULL)  node->value=value;
    else if(node == NULL)
    {
        node = new Node<Key, Value>;
        node->key = key;
        node->value = value;
        //插入位置决定表是否有序
        if (isSort == false)
        {
            //无序表直接从头插入
            node->Next = head->Next;
            head->Next = node;
        }
        else if (isSort == true)
        {
            //有序表找到比自己大的节点
            //插到该节点前面
            Node<Key, Value>* pCurr = head->Next;
            Node<Key, Value>* pPrev = head;
            while(pCurr != NULL)
            {
                if (pCurr->key > key) break;
                pCurr = pCurr->Next;
                pPrev = pPrev->Next;
            }
            pPrev->Next = node;
            node->Next = pCurr;
        }
        length ++;
    }
}

//删除
template <class Key, class Value>
inline void ST<Key, Value> :: remove(Key key)
{
    put(key, NULL);
}

//空则返回true
template <class Key, class Value>
inline bool ST<Key, Value> :: isEmpty()
{
    return (length == 0);
}

//不包含key值，返回false
template <class Key, class Value>
inline bool ST<Key, Value> :: isContain(Key key)
{
    return (get(key) != NULL);
}

//输入key，返回对应节点
//如果key不存在，返回NULL
template <class Key, class Value>
inline Node<Key, Value>* ST<Key, Value> :: get(Key key)
{
    Node<Key, Value>* pCurr = head->Next;
    while (pCurr != NULL)
    {
        if (pCurr->key == key)  return pCurr;
        else pCurr = pCurr->Next;
    }
    return NULL;
}

//输出表
template <class Key, class Value>
inline void ST<Key, Value> ::print()
{
    Node<Key, Value>* pCurr = head->Next;
    while (pCurr != NULL)
    {
        cout<<"key is "<<pCurr->key<<" "<<"value is "<<pCurr->value<<endl;
        pCurr = pCurr->Next;
    }
}