数据结构(四) 散列表(Hash表)和字符串

散列表(Hash表)

实现一个基于链表法解决冲突问题的散列表

typedef struct node  //记录对应的节点 
{
   
	keytype key;
	...
	struct noode *next; 
}Renode;

Renode *LinkHsearch(Renode *HT[m], keytype k)  //链地址法解决冲突时的查找算法 
{
   
	Renode *p;
	int d;
	d = H(k);  //求Hash地址并赋值给d 
	p = HT[d];  //取链表头节点指针 
	while(p && (p->key != k))
		p = p->next;  //冲突时取下一同一词节点 
	return (p);  //查找成功时p->key == k，否则p=^ 
}

void LinkHinsert(Renode *HT[m], Renode *S)  //将指针S所指记录插入表HT的算法 
{
   
	int d;
	Renode *p;
	p = LinkHsearch(HT, S->key);  //查找S节点 
	if(p) error();  //记录已存在时的处理 
	else
	{
   
		d = H(S->key);
		S->next = HT[d];
		HT[d] = S;
	}
}

实现一个 LRU 缓存淘汰算法

class LRUCache{
   
private:
	//LRU数据结构
	struct Node{
   
		int key;
		int value;
		Node(int k,int v):key(k),value(v){
   }
	};
public:
	LRUCache(int c):capacity(c) {
   }
	
	int get(int key){
   
		if (cacheMap.find(key) == cacheMap.end())
			return -1; //这里产生缺页中断，根据页表将页面调入内存，然后set(key, value)
		//将key移到第一个，并更新cacheMap 
		cacheList.splice(cacheList.begin(),cacheList,cacheMap[key]);
		cacheMap[key] = cacheList.begin();
		return cacheMap[key]->value;
	}
	void set(int key, int value){
   
		if (cacheMap.find(key) == cacheMap.end())
		{
   
			//淘汰最后一个，然后将其加到第一个位置
			if (cacheList.size() == capacity)
			{
   
				cacheMap.erase(cacheList.back().key);
				cacheList.pop_back();
			}
			cacheList.push_front(Node(key,value));
			cacheMap[key] = cacheList.begin();
		} 
		else
		{
   
			//更新节点的值，并将其加到第一个位置
			cacheMap[key]->value = value;
			cacheList.splice(cacheList.begin(),cacheList,cacheMap[key]);
			cacheMap[key] = cacheList.begin();
		}
	}
private:
	int capacity;
	list<Node> cacheList;
	unordered_map<int, list<Node>::iterator> cacheMap;
};

字符串

实现一个字符集，只包含 a～z 这 26 个英文字母的 Trie 树

public class Trie {
   

    private Node root;

    private int size;

    private static class Node {
   
        public boolean isWord;
        public Map<Character, Node> next;

        public Node() {
   
            next = new TreeMap<>();
        }

        public Node(boolean isWord) {
   
            this();
            this.isWord = isWord;
        }

    }

    public Trie() {
   
        root = new Node();
    }

    public int size() {
   
        return size;
    }

    public boolean isEmpty() {
   
        return size == 0;
    }

    /** * 插入操作 * * @param word 单词 */
    public void add(String word) {
   
        Node current = root;
        char[] cs = word.toCharArray();
        for (char c : cs) {
   
            Node next = current.next.get(c);
            if (next == null) {
   
                current.next.put(c, new Node());
            }
            current = current.next.get(c);
        }
        //如果当前的node已经是一个word，则不需要添加
        if (!current.isWord) {
   
            size++;
            current.isWord = true;
        }
    }


    /** * 是否包含某个单词 * * @param word 单词 * @return 存在返回true，反之false */
    public boolean contains(String word) {
   
        Node current = root;
        for (int i = 0; i < word.length(); i++) {
   
            char c = word.charAt(i);
            Node node = current.next.get(c);
            if (node == null) {
   
                return false;
            }
            current = node;
        }
        //如果只存在 panda这个词，查询 pan，虽然有这3个字母，但是并不存在该单词
        return current.isWord;
    }


    /** * Trie是否包含某个前缀 * * @param prefix 前缀 * @return */
    public boolean containsPrefix(String prefix) {
   
        Node current = root;
        for (int i = 0; i < prefix.length(); i++) {
   
            char c = prefix.charAt(i);
            Node node = current.next.get(c);
            if (node == null) {
   
                return false;
            }
            current = node;
        }
        return true;
    }


    /* * 1，如果单词是另一个单词的前缀，只需要把该word的最后一个节点的isWord的改成false * 2，如果单词的所有字母的都没有多个分支，删除整个单词 * 3，如果单词的除了最后一个字母，其他的字母有多个分支， */

    /** * 删除操作 * * @param word * @return */
    public boolean remove(String word) {
   
        Node multiChildNode = null;
        int multiChildNodeIndex = -1;
        Node current = root;
        for (int i = 0; i < word.length(); i++) {
   
            Node child = current.next.get(word.charAt(i));
            //如果Trie中没有这个单词
            if (child == null) {
   
                return false;
            }
            //当前节点的子节点大于1个
            if (child.next.size() > 1) {
   
                multiChildNodeIndex = i;
                multiChildNode = child;
            }
            current = child;
        }
        //如果单词后面还有子节点
        if (current.next.size() > 0) {
   
            if (current.isWord) {
   
                current.isWord = false;
                size--;
                return true;
            }
            //不存在该单词，该单词只是前缀
            return false;
        }
        //如果单词的所有字母的都没有多个分支，删除整个单词
        if (multiChildNodeIndex == -1) {
   
            root.next.remove(word.charAt(0));
            size--;
            return true;
        }
        //如果单词的除了最后一个字母，其他的字母有分支
        if (multiChildNodeIndex != word.length() - 1) {
   
            multiChildNode.next.remove(word.charAt(multiChildNodeIndex + 1));
            size--;
            return true;
        }
        return false;
    }
}

实现朴素的字符串匹配算法

#ifndef STRING_H_
#define STRING_H_

/*朴素算法查找字符串，时间复杂度是O(nm)，不需要预处理*/
int naive_search(const char * txt, const char * pat, int offset[])
{
   
    int i, j, n, m, c = 0;
    n = strlen(txt);
    m = strlen(pat);
    for (i = 0; i <= n - m; i++) {
   
        for (j = 0; j < m; j++)
            if (pat[j] != txt[i + j])
                break;
        if (j == m)
            offset[c++] = i;
    }
    return c;
}
#endif