数据结构
Table of Contents
List
Singly-Linked List (forward_list)
struct node {
int val;
struct node* next;
};
void echo(struct node* p) {
while (p) {
printf("->node(%d)", p->val);
p = p->next;
}
printf("\n");
}
struct node * reverse(struct node *head) {
if (head == 0) return head;
struct node* pre = head;
struct node* p = pre->next;
struct node* nxt;
while (p) {
nxt = p->next;
p->next = pre;
pre = p;
p = nxt;
}
head->next = 0;
return pre;
}
void insert(struct node** pp, struct node* p) {
if (NULL == pp || NULL == p) return;
p->next = *pp;
*pp = p;
}
void delete(struct node **pp) {
if (pp == 0) return;
*pp = (*pp)->next;
}
int main() {
struct node nodes[10];
struct node* p = NULL;
for (int i = 0; i < 10; ++i) {
nodes[i].val = i+1;
nodes[i].next = NULL;
insert(&p, &nodes[i]);
}
echo(p);
p = reverse(p);
echo(p);
delete(&(nodes[4].next));
delete(&(nodes[6].next));
delete(&(nodes[8].next));
echo(reverse(p));
return 0;
}
Doubly-Linked List (list)
Queue
template<typename T>
class Q {
public:
void enq(T v) { m_in_stack.push(v); }
T deq() {
if (m_out_stack.empty())
while (!m_in_stack.empty()) {
m_out_stack.push(m_in_stack.top());
m_in_stack.pop();
}
T v = m_out_stack.top();
m_out_stack.pop();
return v;
}
bool empty() const { return m_in_stack.empty() && m_out_stack.empty(); }
private:
std::stack<T> m_in_stack; // in stack
std::stack<T> m_out_stack; // out stack
};
TRIE
namespace Trie {
class Node {
public:
static Node* createNode() {
// zero-initialized, cause no user-provided default constructor
static Node SharedMemory[MAX_CNT];
static size_t allocp; // static is initialized to zero
if (allocp >= MAX_CNT) throw new std::bad_alloc;
Node *p = &SharedMemory[allocp++];
p->count = 1;
return p;
}
public:
size_t count; // number of occurence of this char
Node* next[MAX_CHAR];
};
class Trie {
public:
Trie() : root(nullptr) {}
void insert(const std::string& s) {
Node *p = root;
if (nullptr == p) p = root = Node::createNode();
for (const auto& c : s) {
int index = c - 'a';
if (nullptr != p->next[index]) ++p->next[index]->count;
else p->next[index] = Node::createNode();
p = p->next[index];
}
}
size_t search(const std::string& s) const {
Node *p = root;
if (nullptr == p) return 0;
for (const auto& c : s) {
int index = c - 'a';
if (nullptr == p->next[index]) return 0;
p = p->next[index];
}
return p->count;
}
private:
Node *root;
};
}
int main(int argc, char *argv[]) {
Trie::Trie t;
t.insert("hello");
t.insert("world");
std::cout << "search(\"h\")" << t.search("h") << std::endl
<< "search(\"hell\")" << t.search("hell") << std::endl
<< "search(\"w\")" << t.search("w") << std::endl;
return 0;
}
LRU
template<typename Key, typename Value>
class LRUCache {
typedef pair<Key, Value> T;
size_t m_capacity;
Value m_sentinel;
list<T> m_cache;
unordered_map<Key, typename list<T>::iterator> m_hash;
public:
LRUCache(size_t capacity, Value sentinel) : m_capacity(capacity), m_sentinel(sentinel) {
m_hash.reserve(capacity);
}
bool exists(Key key) const {
return m_hash.find(key) != m_hash.end();
}
Value get(Key key) {
auto it = m_hash.find(key);
if (it == m_hash.end()) return m_sentinel;
m_cache.splice(m_cache.begin(), m_cache, it->second);
return it->second->second;
}
void set(Key key, Value value) {
const auto it = m_hash.find(key);
if (it != m_hash.end()) {
m_cache.splice(m_cache.begin(), m_cache, it->second);
it->second->second = value;
return;
}
if (m_cache.size() == m_capacity) {
m_hash.erase(m_cache.back().first);
m_cache.pop_back();
}
m_cache.emplace_front(key, value);
m_hash[key] = m_cache.begin();
}
};