投稿
  1. 首页
  2. C

深入浅出数据结构C++优雅实现（带注释 精简无废话）

code • 2022-4-9 • C • 阅读 64

深入浅出数据结构C++优雅实现（带注释 精简无废话）,第1张

ElegantDataStructure
  • Github地址传送门
  • 链表
    • 单链表链式存储
    • 循环链表
    • 双向链表链式存储
  • 堆
  • 队列链式存储
  • 栈链式存储
  • 二叉树
    • 普通二叉树
    • 二叉搜索树
  • 哈希表
    • 线性探测实现
    • 拉链法实现

Github地址传送门

不定时更新，C++实现一些常见较为简单的数据结构。



https://github.com/ZYunfeii/ElegantDataStructure

链表 单链表链式存储 
#include 

using namespace std;

struct Node {
	int val;
	Node* next;
};

// 创建list
Node* create_list() {
	Node* head = new Node;
	head->next = nullptr;
	return head;
}

// 头插法
void insert(Node* t, Node* head) {
	t->next = head->next;
	head->next = t;
}

void print_list(Node* head) {
	Node* tmp = head->next;
	while (tmp) {
		cout << tmp->val << " ";
		tmp = tmp->next;
	}
	cout << "print complete!"<<endl;
}

// 删除：默认list中val不同，删除对应val的节点
void delete_node(int val, Node* head) {
	Node* pre = head;
	Node* cur = head->next;
	while (cur) {
		if (cur->val == val) {
			pre->next = cur->next;
			delete cur;
			return;
		}
		cur = cur->next;
		pre = pre->next;
	}
}

// 删除整个list
void delete_list(Node* head) {
	Node* cur = head->next;
	Node* tmp;
	while (cur) {
		tmp = cur->next;
		delete cur;
		cur = tmp;
	}
	head->next = nullptr; // key!
}

int main()
{
	Node* mylist = create_list();
	for (int i = 0; i < 4; ++i) {
		Node* tmp = new Node;
		tmp->val = i;
		insert(tmp, mylist);
	}
	print_list(mylist);

	delete_node(2, mylist);
	print_list(mylist);

	delete_list(mylist);
	print_list(mylist);

	return 0;
}
循环链表 
#include 
using namespace std;

template<class T>
struct Node {
	T data;
	Node<T> *next;
	Node(T src) :data(src), next(nullptr) {}
	Node() :next(nullptr) {}
};

template<class T>
class CircularLinkedList {
private:
	Node<T> *head_;
	size_t counter_;
public:
	explicit CircularLinkedList() {
		head_ = new Node<T>;
		head_->next = head_;
		counter_ = 0;
	}

	void PushFront(T data) {
		Node<T> *node = new Node<T>(data);
		node->next = head_->next;
		head_->next = node;
		counter_++;
	}

	void PushBack(T data) {
		Node<T> *node = new Node<T>(data);
		node->next = head_;   // 循环链表最后一个节点指向头
		Node<T>* tmp = head_;
		for (int i = 0; i < counter_; ++i) {
			tmp = tmp->next; // 找到最后一个节点
		}
		tmp->next = node;
		counter_++;
	}

	void PopFront() {
		if (counter_ == 0) return;
		Node<T> *tmp = head_->next;
		head_->next = head_->next->next;
		counter_--;
		delete tmp;
	}

	void PopBack() {
		if (counter_ == 0) return;
		Node<T> *tmp = head_;
		for (int i = 0; i < counter_ - 1; ++i) {
			tmp = tmp->next; // 找到最后一个节点前一个节点
		}
		Node<T> *delete_node = tmp->next;
		tmp->next = tmp->next->next;
		counter_--;
		delete delete_node;
	}

	void PrintList() { // 仅支持data为可打印类型
		if (counter_ == 0) return;
		Node<T> *tmp = head_;
		for (int i = 0; i < counter_; ++i) {
			tmp = tmp->next;
			cout << tmp->data << endl;
		}
	}

	bool IsEmpty() {
		return counter_ == 0;
	}

	size_t Size() {
		return counter_;
	}

	void Clear() {
		if (counter_ == 0) return;
		Node<T> *cur = head_->next;
		Node<T> *next = nullptr;
		while (cur != head_) {
			next = cur->next;
			delete cur;
			cur = next;
		}
		head_->next = head_;
		counter_ = 0;
	}
};

int main(){
	CircularLinkedList<int> my_cir_link_list;
	my_cir_link_list.PushBack(2);
	my_cir_link_list.PushFront(3);
	my_cir_link_list.PushBack(4);
	my_cir_link_list.PrintList();
	my_cir_link_list.PopBack();
	my_cir_link_list.PrintList();

	return 0;
}
双向链表链式存储 
#include 

using namespace std;

// 双端链表 

class Node {
public:
	int val;
	Node * prev;
	Node  * next;
public:
	Node(int val):val(val){}
};

class DoubleLinkedList {
public:
	Node * head;
	Node * tail;

public:
	DoubleLinkedList() {
		this->head = new Node(0);
		this->tail = new Node(0);

		head->next = tail;
		tail->prev = head;
		head->prev = nullptr;
		tail->next = nullptr;
	}

	void addFirst(Node* newNode) {
		newNode->next = head->next;
		newNode->prev = head;
		head->next->prev = newNode;
		head->next = newNode;
	}

	void addLast(Node* newNode) {
		newNode->next = tail;
		newNode->prev = tail->prev;
		tail->prev->next = newNode;
		tail->prev = newNode;
	}

	void deleteNode(Node * n) {
		n->next->prev = n->prev;
		n->prev->next = n->next;
	}

	void deleteLast() {
		if (head->next == tail) return;
		deleteNode(tail->prev);
	}

	void deleteFirst() {
		if (head->next == tail) return;
		deleteNode(head->next);
	}

	void print_list() {
		Node* tmp = head->next;
		while (tmp->next) {
			cout << tmp->val << " ";
			tmp = tmp->next;
		}
		cout << endl;
	}
};

int main() {
	DoubleLinkedList* dlist = new DoubleLinkedList;
	for (int i = 0; i < 5; ++i) {
		Node* tmp = new Node(i);
		dlist->addFirst(tmp); // 这里别写成addFirst(&Node(i)) !!
	}
	dlist->print_list();

	dlist->deleteLast();
	dlist->print_list();

	dlist->addLast(new Node(6));
	dlist->print_list();

	return 0;
}
堆
  1. 最大堆
  2. 最小堆
#include 
#include 
#include 
using namespace std;
 
// 堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
// 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
// 构建堆复杂度O(n) 重建堆复杂度O(nlogn)

// 最大堆
template<class T>
class MaxHeap {
private: 
	vector<T> data;
	int pos;       // 记录堆的终止索引 当没有erase元素时 pos == data.size() - 1
public:
	MaxHeap(vector<T> src):data(src), pos(src.size() - 1) {
		for (int i = data.size() / 2; i >= 0; --i) {
			heapAdjust(i, data.size() - 1);
		}
	}
	void heapAdjust(int s, int m) {
		if (s == 0 && m == 0) return;               // 有些书用1作为root，如果用0的话要考虑这种情况，否则在for中会一直循环退不出来
		int temp, j;
		temp = data[s];
		for (j = s; j <= m; j *= 2) {                // 对于完全二叉树，一个节点i的左节点和右节点为2i和2i+1
			if (j < m && data[j] < data[j + 1]) ++j; // 找到左右孩子中值大的索引 j < m是保证j+1有定义
			if (temp > data[j]) break;               // 由于子树已经是大顶堆了，如果temp还大于左右孩子的最大值，那么不用进行之后的遍历了
			data[s] = data[j];
			s = j;                                   // 准备遍历大的节点的孩子节点
		}
		data[s] = temp;                              // 最后将一开始的节点插入到“合适”的位置
	}
	T getMaxEle() {
		if (!data.empty()) return data[0];
	}
	T eraseTopAdjust() {                              // 返回根节点后删除并重新调整堆
		assert(!data.empty());
		T top = data[0];
		swap(data[0], data[pos]);
		pos--;
		heapAdjust(0, pos);
		return top;
	}
	void addEle(T val) {                        // 加入节点到堆 加在树的末尾
		if (pos < data.size() - 1) {
			data[pos + 1] = val;
			pos++;
		}
		else {
			data.push_back(val);
			pos = data.size() - 1;
		}
		for (int i = pos / 2; i >= 0; --i) {  // 重新调整堆
			heapAdjust(i, pos);
		}
	}
};

// 最小堆
template<class T>
class MinHeap {
private:
	vector<T> data;
	int pos;       // 记录堆的终止索引 当没有erase元素时 pos == data.size() - 1

public:
	MinHeap(vector<T> src):data(src), pos(src.size() - 1) {
		for (int i = data.size() / 2; i >= 0; --i) {
			heapAdjust(i, data.size() - 1);
		}
	}
	void heapAdjust(int s, int m) {
		if (s == 0 && m == 0) return;
		int temp, j;
		temp = data[s];
		for (j = s; j <= m; j *= 2) {                // 对于完全二叉树，一个节点i的左节点和右节点为2i和2i+1
			if (j < m && data[j] > data[j + 1]) ++j; // 找到左右孩子中值小的索引 j < m是保证j+1有定义
			if (temp < data[j]) break;               // 由于子树已经是小顶堆了，如果temp还小于左右孩子的最大值，那么不用进行之后的遍历了
			data[s] = data[j];
			s = j;                                   // 准备遍历小的节点的孩子节点
		}
		data[s] = temp;                              // 最后将一开始的节点插入到“合适”的位置
	}
	T getMinEle() {
		if (!data.empty()) return data[0];
	}
	T eraseTopAdjust() {
		assert(!data.empty());
		T top = data[0];
		swap(data[0], data[pos]);
		pos--;
		heapAdjust(0, pos);
		return top;
	}
	void addEle(T val) {
		if (pos < data.size() - 1) {
			data[pos + 1] = val;
			pos++;
		}
		else {
			data.push_back(val);
			pos = data.size() - 1;
		}
		for (int i = pos / 2; i >= 0; --i) {
			heapAdjust(i, pos);
		}
	}
};

int main() {
	MaxHeap<int> myMaxHeap({ 3,2,5,1,7 });
	cout << myMaxHeap.eraseTopAdjust() << endl;
	cout << myMaxHeap.eraseTopAdjust() << endl;
	cout << myMaxHeap.eraseTopAdjust() << endl;
	myMaxHeap.addEle(9);
	cout << myMaxHeap.eraseTopAdjust() << endl;
	cout << myMaxHeap.eraseTopAdjust() << endl;
	cout << myMaxHeap.eraseTopAdjust() << endl;
	myMaxHeap.addEle(10);
	cout << myMaxHeap.eraseTopAdjust() << endl;

	//MinHeap myMinHeap({ 3,2,5,1,7 });
	//cout << myMinHeap.getMinEle() << endl;
	return 0;
}
队列链式存储 
#include 
using namespace std;

template<class T>
class Node {
public:
	T data;
	Node* next;
	Node(T data) :data(data) {}
	Node() {};
};

template<class T>
class queue {
public:
	Node<T>* head;
	Node<T>* tail;
	queue() {
		head = new Node<T>;
		head->next = nullptr;
		tail = head;
	}
	// 尾插法
	void push(Node<T>* n) {
		tail->next = n;
		tail = n;
	}

	Node<T>* front() {
		return head->next;
	}

	Node<T>* back() {
		return tail;
	}

	// 两种实现都可以
	void pop() {
		if (!head->next) return;
		Node<T>* tmp = head;
		head = head->next;
		delete tmp;

		//if (!head->next) return;
		//Node* tmp = head->next;
		//head->next = head->next->next;
		//delete tmp;
	}

	bool empty() {
		return !head->next;
	}
};

int main() {
	queue<int>* q = new queue<int>;
	for (int i = 0; i < 5; ++i) {
		q->push(new Node<int>(i));
	}

	while (!q->empty()) {
		Node<int>* node = q->front();
		cout << node->data << " ";
		q->pop();
	}

	return 0;
}
栈链式存储 
#include 

using namespace std;

// 栈链式存储

template<class T>
class Node {
public:
	T data;
	Node* next;
	Node(T data) :data(data) {}
};

template<class T>
class Stack {
public:
	Stack(T data) {
		head = new Node<T>(data);
		head->next = nullptr;
	}

	void push(Node<T>* n) {
		n->next = head->next;
		head->next = n;
	}

	Node<T>* top() {
		return head->next;
	}

	void pop() {
		Node<T>* tmp = head->next;
		if (!head->next) return;
		head->next = head->next->next;
		delete tmp;
	}

	bool empty() {
		return !head->next;
	}

	Node<T>* head;
};

int main() {
	Stack<int> stk(0);
	for (int i = 0; i < 5; ++i) {
		stk.push(new Node<int>(i));
	}

	while (!stk.empty()) {
		Node<int>* tmp = stk.top();
		cout << tmp->data << endl;
		stk.pop();
	}

	return 0;
}
二叉树 普通二叉树 
#include 
#include 
#include 
using namespace std;

typedef struct node
{
	struct node *lchild;
	struct node *rchild;
	char data;
}BiTreeNode, *BiTree;

class Tree {
private:
	BiTree tree;
public:
	void create() {
		BiTree T = new BiTreeNode;
		this->tree = createBiTree(T);
	}
	BiTree createBiTree(BiTree& T) { // 注意使用的是指针的引用 如果只是传入指针会被拷贝
		char c;
		cin >> c;
		if ('#' == c)
			T = NULL;
		else
		{
			cout << "创建一个节点!" << endl;
			T = new BiTreeNode;
			T->data = c;
			createBiTree(T->lchild);
			createBiTree(T->rchild);
		}
		return T;
	}
	void preOrderTraverse() {  // 先序遍历
		recurDfsPre(tree);
	}
	void recurDfsPre(BiTree& tree) {
		if (tree == nullptr) return;
		cout << tree->data << endl;
		recurDfsPre(tree->lchild);
		recurDfsPre(tree->rchild);
	}

	void inOrderTraverse() {    // 中序遍历
		recurDfsIn(tree);
	}
	void recurDfsIn(BiTree& tree) {
		if (tree == nullptr) return;
		recurDfsIn(tree->lchild);
		cout << tree->data << endl;
		recurDfsIn(tree->rchild);
	}

	void postOrderTraverse() {   // 后序遍历
		recurDfsPost(tree);
	}
	void recurDfsPost(BiTree& tree) {
		if (tree == nullptr) return;
		recurDfsPost(tree->lchild);
		recurDfsPost(tree->rchild);
		cout << tree->data << endl;
	}

	void levelTraverse() { // 层序遍历
		queue<BiTree> q;
		q.push(tree);
		while (!q.empty()) {
			for (int i = 0; i < q.size(); ++i) {
				BiTree tmp = q.front();
				q.pop();
				cout << tmp->data << endl;
				if(tmp->lchild) q.push(tmp->lchild);
				if(tmp->rchild) q.push(tmp->rchild);
			}
		}
	}
};

int main() {
	Tree t;
	t.create();
	t.preOrderTraverse();
	t.levelTraverse();
	return 0;
}
二叉搜索树 
#include 
#include 
#include 
using namespace std;

// 二叉搜索树实现
typedef struct node
{
	struct node *lchild;
	struct node *rchild;
	int data;
	node(int src) :data(src) {
		lchild = nullptr;
		rchild = nullptr;
	}
}BiTreeNode, *BiTree;

class BST {
private:
	BiTree tree;
public:

	BST() {
		tree = nullptr;
	}

	// BST 插入 *** 作
	void insert(BiTreeNode node) {
		insertRecur(node, tree);
	}

	void insertRecur(BiTreeNode node, BiTree& root) {
		if (root == nullptr){
			root = new BiTreeNode(node.data); // 不能用root = &node, node传进来是个临时变量 
			return;
		}

		if (node.data < root->data) {
			insertRecur(node, root->lchild);
		}
		else {
			insertRecur(node, root->rchild);
		}

	}

	// 删除 *** 作详见《大话数据结构》p352
	void erase(int key) {
		if (deleteBST(tree, key)) {
			cout << "删除成功!" << endl;
		}
		else {
			cout << "删除失败!" << endl;
		}
	}

	bool deleteBST(BiTree& root, int key) {
		// 先序DFS找到要删除的节点
		if (root == nullptr) return false;
		else {
			if (key == root->data) return deleteNode(root); 
			else if (key < root->data) return deleteBST(root->lchild, key);
			else return deleteBST(root->rchild, key);
		}
	}

	bool deleteNode(BiTree& root) {
		BiTree tmp;
		if (root->rchild == nullptr) { // 没有右子树的情况直接把左子树接上来
			tmp = root;
			root = root->lchild;
			delete tmp;
		}
		else if (root->lchild == nullptr) { // 没有左子树的情况直接把右子树接上来
			tmp = root;
			root = root->rchild;
			delete tmp;
		}
		else {                         // 既有左子树又有右子树
			BiTree q = root;
			BiTree s = root->lchild;
			// 找左子树的最右节点s，因为这个节点一定是左子树中最大的节点同时一定比右子树的所有节点值小，用它来代替待删除节点
			// q是s的前驱节点
			while (s->rchild) { 
				q = s;
				s = s->rchild;
			}
			root->data = s->data;
			if (q != root) {
				q->rchild = s->lchild;
			}
			else {
				q->lchild = s->lchild;  // q == root的情况是待删除节点的左孩子节点没有右子树，此时直接把左孩子节点的左子树接上来
			}
			delete s;
		}
		return true;
	}

	// BST查找 *** 作O(logn)
	BiTree search(int key) {
		BiTree res = searchDfs(tree, key);
		if (res == nullptr) {
			cout << "没有对应节点!" << endl;
			return nullptr;
		}
		else return res;
	}

	BiTree searchDfs(BiTree& root, int key) {
		if (root == nullptr) return nullptr;
		if (key < root->data) return searchDfs(root->lchild, key);
		else if(key > root->data) return searchDfs(root->rchild, key);
		else return root;
	}
	
	void preOrderTraverse() {  // 先序遍历
		recurDfsPre(tree);
	}
	void recurDfsPre(BiTree& tree) {
		if (tree == nullptr) return;
		cout << tree->data << endl;
		recurDfsPre(tree->lchild);
		recurDfsPre(tree->rchild);
	}

	void inOrderTraverse() {    // 中序遍历
		recurDfsIn(tree);
	}
	void recurDfsIn(BiTree& tree) {
		if (tree == nullptr) return;
		recurDfsIn(tree->lchild);
		cout << tree->data << endl;
		recurDfsIn(tree->rchild);
	}

	void postOrderTraverse() {   // 后序遍历
		recurDfsPost(tree);
	}
	void recurDfsPost(BiTree& tree) {
		if (tree == nullptr) return;
		recurDfsPost(tree->lchild);
		recurDfsPost(tree->rchild);
		cout << tree->data << endl;
	}

	void levelTraverse() { // 层序遍历
		queue<BiTree> q;
		q.push(tree);
		while (!q.empty()) {
			for (int i = 0; i < q.size(); ++i) {
				BiTree tmp = q.front();
				q.pop();
				cout << tmp->data << endl;
				if (tmp->lchild) q.push(tmp->lchild);
				if (tmp->rchild) q.push(tmp->rchild);
			}
		}
	}
};

int main() {
	BST t;
	t.insert(BiTreeNode(3));
	t.insert(BiTreeNode(2));
	t.insert(BiTreeNode(5));
	t.insert(BiTreeNode(1));
	t.erase(3);
	t.levelTraverse();
	cout << t.search(5)->data << endl;
	return 0;
}
哈希表 线性探测实现 
#include 
using namespace std;

class HashTable {
private:
	static const int HASHSIZE = 12;
	static const int NULLKEY = -32768;
	int* elem;
public:
	HashTable() {
		elem = new int[HASHSIZE];
		for (int i = 0; i < HASHSIZE; ++i) {
			elem[i] = NULLKEY;
		}
	}
	int hash(int key) {
		return key % HASHSIZE;
	}
	void insertHash(int key) {
		int addr = hash(key);
		while (elem[addr] != NULLKEY) {
			addr = (addr + 1) % HASHSIZE;    // 开放定址法线性探测
		}
		elem[addr] = key;
	}
	int searchHash(int key) {
		int addr = hash(key);
		while (elem[addr] != key) {    // hash冲突了
			addr = (addr + 1) % HASHSIZE;
			if (elem[addr] == NULLKEY || addr == hash(key)) { // 如果循环一圈或者下一个探测为null则搜索失败（在插入的时候不可能留有null）
				return NULLKEY;
			}
		}
		return elem[addr];
	}
};

int main() {
	HashTable tab;
	tab.insertHash(14);
	tab.insertHash(3);
	tab.insertHash(2);
	cout << tab.searchHash(2) << endl;
	return 0;
}
拉链法实现 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int hashsize = 12;

//定⼀个节点的结构体
template <class T, class U>
struct HashNode
{
	T _key;
	U _value;
};

//使⽤拉链法实现哈希表类
template <typename T, typename U>
class HashTable
{
public:
	HashTable() : vec(hashsize) {}//类中的容器需要通过构造函数来指定⼤⼩
	~HashTable() {}
	bool insert_data(const T &key, const U &value);
	int hash(const T &key);
	bool hash_find(const T &key);
private:
	vector<list<HashNode<T, U>>> vec;//将节点存储到容器中
};

//哈希函数（除留取余）
template <typename T, typename U>
int HashTable<T, U>::hash(const T &key)
{
	return key % 13;
}

//哈希查找
template <typename T, typename U>
bool HashTable<T, U>::hash_find(const T &key)
{
	int index = hash(key);//计算哈希值
	for (auto it = vec[index].begin(); it != vec[index].end(); ++it)
	{
		if (key == it->_key)//如果找到则打印其关联值
		{
			cout << it->_value << endl;//输出数据前应该确认是否包含相应类型
			return true;
		}
	}
	return false;
}

//插⼊数据
template <typename T, typename U>
bool HashTable<T, U>::insert_data(const T &key, const U &value)
{
	//初始化数据
	HashNode<T, U> node;
	node._key = key;
	node._value = value;
	for (int i = 0; i < hashsize; ++i)
	{
		if (i == hash(key))//如果溢出则把相应的键值添加进链表
		{
			vec[i].push_back(node);
			return true;
		}
	}
}

int main(int argc, char const *argv[])
{
	HashTable<int, int> ht;
	static default_random_engine e;
	static uniform_int_distribution<unsigned> u(0, 100);
	long long int a = 10000000;
	for (long long int i = 0; i < a; ++i)
		ht.insert_data(i, u(e));
	clock_t start_time = clock();
	ht.hash_find(114);
	clock_t end_time = clock();
	cout << "Running time is: " << static_cast<double>(end_time - start_time) /
		CLOCKS_PER_SEC * 1000 <<
		"ms" << endl;//输出运⾏时间。


	system("pause");
	return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/568484.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-09
下一篇 2022-04-09

发表评论

登录后才能评论

评论列表（0条）

保存