devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

c++相关的数据结构

作者：weixin_40725706 | 2024-06-21 01:29:17

赞

踩

c++相关的数据结构

单链表，模板加智能指针 

  1. #include <iostream>
  2. #include <memory>
  3.  
  4. // 定义链表节点结构
  5. template <typename T>
  6. struct Node {
  7.     T data;
  8.     std::shared_ptr<Node<T>> next;
  9.  
  10.     Node(const T& value) : data(value), next(nullptr) {}
  11. };
  12.  
  13. // 定义链表类
  14. template <typename T>
  15. class LinkedList {
  16. private:
  17.     std::shared_ptr<Node<T>> head;
  18.  
  19. public:
  20.     LinkedList() : head(nullptr) {}
  21.  
  22.     // 在链表末尾插入节点
  23.     void insert(const T& value) {
  24.         std::shared_ptr<Node<T>> newNode = std::make_shared<Node<T>>(value);
  25.  
  26.         if (head == nullptr) {
  27.             head = newNode;
  28.         } else {
  29.             std::shared_ptr<Node<T>> temp = head;
  30.             while (temp->next != nullptr) {
  31.                 temp = temp->next;
  32.             }
  33.             temp->next = newNode;
  34.         }
  35.     }
  36.  
  37.     // 打印链表元素
  38.     void print() {
  39.         std::shared_ptr<Node<T>> temp = head;
  40.         while (temp != nullptr) {
  41.             std::cout << temp->data << " ";
  42.             temp = temp->next;
  43.         }
  44.         std::cout << std::endl;
  45.     }
  46. };
  47.  
  48. int main() {
  49.     LinkedList<int> list;
  50.  
  51.     list.insert(1);
  52.     list.insert(2);
  53.     list.insert(3);
  54.     list.insert(4);
  55.  
  56.     list.print(); // 输出: 1 2 3 4
  57.  
  58.     return 0;
  59. }

单链表加完美转发进阶版

  1. #include <iostream>
  2. #include <memory>
  3. #include <utility>
  4.  
  5. template <typename T>
  6. class LinkedList {
  7. private:
  8.     struct Node {
  9.         T data;
  10.         std::shared_ptr<Node> next;
  11.         Node(const T& value) : data(value), next(nullptr) {}
  12.     };
  13.  
  14.     std::shared_ptr<Node> head;
  15.  
  16. public:
  17.     LinkedList() : head(nullptr) {}
  18.     //头插法
  19.     template <typename U>
  20.     void insert(U&& data) {
  21.         std::shared_ptr<Node> newNode = std::make_shared<Node>(std::forward<U>(data));
  22.         newNode->next = head;
  23.         head = newNode;
  24.     }
  25.  
  26.     void print() const {
  27.         std::shared_ptr<Node> current = head;
  28.         while (current != nullptr) {
  29.             std::cout << current->data << " ";
  30.             current = current->next;
  31.         }
  32.         std::cout << std::endl;
  33.     }
  34. };
  35.  
  36. int main() {
  37.     LinkedList<int> list;
  38.  
  39.     list.insert(3);
  40.     list.insert(5);
  41.     list.insert(7);
  42.  
  43.     list.print();  // 输出链表内容: 7 5 3
  44.  
  45.     return 0;
  46. }

双链表  

  1. #include <iostream>
  2. #include <memory>
  3.  
  4. // 定义链表节点结构
  5. template <typename T>
  6. struct Node {
  7.     T data;
  8.     std::shared_ptr<Node<T>> prev;
  9.     std::shared_ptr<Node<T>> next;
  10.  
  11.     Node(const T& value) : data(value), prev(nullptr), next(nullptr) {}
  12. };
  13.  
  14. // 定义链表类
  15. template <typename T>
  16. class DoublyLinkedList {
  17. private:
  18.     std::shared_ptr<Node<T>> head;
  19.     std::shared_ptr<Node<T>> tail;
  20.  
  21. public:
  22.     DoublyLinkedList() : head(nullptr), tail(nullptr) {}
  23.  
  24.     // 在链表末尾插入节点
  25.     void insert(const T& value) {
  26.         std::shared_ptr<Node<T>> newNode = std::make_shared<Node<T>>(value);
  27.  
  28.         if (head == nullptr) {
  29.             head = newNode;
  30.             tail = newNode;
  31.         }
  32.         else {
  33.             tail->next = newNode;
  34.             newNode->prev = tail;
  35.             tail = newNode;
  36.         }
  37.     }
  38.  
  39.     // 打印链表元素
  40.     void print() {
  41.         std::shared_ptr<Node<T>> temp = head;
  42.         while (temp != nullptr) {
  43.             std::cout << temp->data << " ";
  44.             temp = temp->next;
  45.         }
  46.         std::cout << std::endl;
  47.     }
  48. };
  49.  
  50. int main() {
  51.     DoublyLinkedList<int> list;
  52.  
  53.     list.insert(1);
  54.     list.insert(2);
  55.     list.insert(3);
  56.     list.insert(4);
  57.  
  58.     list.print(); // 输出: 1 2 3 4
  59.  
  60.     return 0;
  61. }

双链表进阶版

  1. //双链表
  2. template<typename T>
  3. class DoubleLinkList {
  4.  
  5. private:
  6. 	struct Node {
  7. 		std::shared_ptr<Node> next;
  8. 		std::shared_ptr<Node> prev;
  9. 		T data;
  10. 		Node(const T& value): data(value),next(nullptr),prev(nullptr){}
  11. 	};
  12.  
  13. 	std::shared_ptr<Node> head;
  14. 	std::shared_ptr<Node> tail;
  15. public:
  16. 	DoubleLinkList():head(nullptr),tail(nullptr){}
  17. 	template<typename U>
  18. 	void insert(U&& value) {
  19. 		std::shared_ptr<Node> NewNode = std::make_shared<Node>(std::forward<U>(value));
  20. 		if (head == nullptr) {
  21. 			head = NewNode;
  22. 			tail = NewNode;
  23. 		}
  24. 		else {
  25. 			//尾插法和头指针无关
  26. 			tail->next= NewNode;
  27. 			NewNode->prev = tail;
  28. 			tail = NewNode;
  29. 		}
  30. 	}
  31. 	void print() {
  32. 		std::shared_ptr<Node> tmp = head;
  33. 		while (tmp != nullptr) {
  34. 			std::cout << tmp->data << std::endl;
  35. 			tmp = tmp->next;
  36. 		}
  37. 	}
  38. };

栈

  1. #include <iostream>
  2. #include <memory>
  3.  
  4. // 定义栈节点结构
  5. template <typename T>
  6. struct Node {
  7.     T data;
  8.     std::shared_ptr<Node<T>> next;
  9.  
  10.     Node(const T& value) : data(value), next(nullptr) {}
  11. };
  12.  
  13. // 定义栈类
  14. template <typename T>
  15. class Stack {
  16. private:
  17.     std::shared_ptr<Node<T>> top;
  18.  
  19. public:
  20.     Stack() : top(nullptr) {}
  21.  
  22.     // 入栈操作
  23.     void push(const T& value) {
  24.         std::shared_ptr<Node<T>> newNode = std::make_shared<Node<T>>(value);
  25.         newNode->next = top;
  26.         top = newNode;
  27.     }
  28.  
  29.     // 出栈操作
  30.     void pop() {
  31.         if (top != nullptr) {
  32.             std::shared_ptr<Node<T>> temp = top;
  33.             top = top->next;
  34.             temp.reset();
  35.         }
  36.     }
  37.  
  38.     // 获取栈顶元素
  39.     T& peek() {
  40.         if (top != nullptr) {
  41.             return top->data;
  42.         }
  43.         throw std::runtime_error("Stack is empty.");
  44.     }
  45.  
  46.     // 判断栈是否为空
  47.     bool isEmpty() {
  48.         return top == nullptr;
  49.     }
  50. };
  51.  
  52. int main() {
  53.     Stack<int> stack;
  54.  
  55.     stack.push(1);
  56.     stack.push(2);
  57.     stack.push(3);
  58.  
  59.     std::cout << "Top element: " << stack.peek() << std::endl; // 输出: Top element: 3
  60.  
  61.     stack.pop();
  62.  
  63.     std::cout << "Top element: " << stack.peek() << std::endl; // 输出: Top element: 2
  64.  
  65.     return 0;
  66. }

升级栈 

  1. #include <iostream>
  2. #include <memory>
  3. #include <utility>
  4.  
  5. //栈
  6. template<typename T>
  7. class Stack {
  8.  
  9. private:
  10. 	struct Node {
  11. 		std::shared_ptr<Node> next;
  12. 		T data;
  13. 		Node(const T& value):data(value),next(nullptr) {}
  14. 	};
  15.  
  16. 	std::shared_ptr<Node> top;
  17. public:
  18. 	Stack():top(nullptr) {}
  19. 	//入栈
  20. 	template<typename U>
  21. 	void push(U&& value) {
  22. 		std::shared_ptr<Node> NewNode = std::make_shared<Node>(std::forward<U>(value));
  23. 		if (top == nullptr) {
  24. 			top = NewNode;
  25. 		}
  26. 		else {
  27. 			NewNode->next = top;
  28. 			top = NewNode;
  29. 		}
  30. 	}
  31. 	//出栈
  32. 	void Pop() {
  33. 		if (top != nullptr) {
  34. 			std::shared_ptr<Node> tmp = top;
  35. 			top = top->next;
  36. 			tmp.reset();//很像指针的delete
  37. 		}else {
  38. 			throw std::exception("栈为空1");
  39. 		}
  40. 	}
  41. 	//获取栈顶元素
  42. 	T& Peek() const{
  43. 		if (top != nullptr) {
  44. 			return top->data;
  45. 		}
  46. 		else {
  47. 			throw std::exception("栈为空2");
  48. 		}
  49. 	}
  50. 	//判断栈是否为空
  51. 	bool IsEmpty() {
  52. 		if (top == nullptr) {
  53. 			return false;
  54. 		}
  55. 		else
  56. 			return true;
  57. 	}
  58.  
  59.  
  60.  
  61. };
  62.  
  63. int main() {
  64. 	Stack<int> stack;
  65. 	try {
  66. 		stack.push(1);
  67. 		/*stack.push(2);
  68. 		stack.push(3);*/
  69.  
  70. 		std::cout << "Top element: " << stack.Peek() << std::endl; // 输出: Top element: 3
  71. 		stack.Pop();
  72. 		stack.Pop();
  73. 		std::cout << "Top element: " << stack.Peek() << std::endl; // 输出: Top element: 2
  74. 	}
  75. 	catch (const std::exception& e) {
  76. 		std::cout << "捕获到异常: " << e.what() << std::endl;
  77. 	}
  78. 	
  79. 	return 0;
  80. }

 

 队列

  1. #include <iostream>
  2. #include <memory>
  3.  
  4. // 定义队列节点结构
  5. template <typename T>
  6. struct Node {
  7.     T data;
  8.     std::shared_ptr<Node<T>> next;
  9.  
  10.     Node(const T& value) : data(value), next(nullptr) {}
  11. };
  12.  
  13. // 定义队列类
  14. template <typename T>
  15. class Queue {
  16. private:
  17.     std::shared_ptr<Node<T>> front;
  18.     std::shared_ptr<Node<T>> rear;
  19.  
  20. public:
  21.     Queue() : front(nullptr), rear(nullptr) {}
  22.  
  23.     // 入队操作
  24.     void enqueue(const T& value) {
  25.         std::shared_ptr<Node<T>> newNode = std::make_shared<Node<T>>(value);
  26.         if (rear == nullptr) {
  27.             front = newNode;
  28.             rear = newNode;
  29.         } else {
  30.             rear->next = newNode;
  31.             rear = newNode;
  32.         }
  33.     }
  34.  
  35.     // 出队操作
  36.     void dequeue() {
  37.         if (front != nullptr) {
  38.             std::shared_ptr<Node<T>> temp = front;
  39.             front = front->next;
  40.             temp.reset();
  41.             if (front == nullptr) {
  42.                 rear = nullptr;
  43.             }
  44.         }
  45.     }
  46.  
  47.     // 获取队头元素
  48.     T& peek() {
  49.         if (front != nullptr) {
  50.             return front->data;
  51.         }
  52.         throw std::runtime_error("Queue is empty.");
  53.     }
  54.  
  55.     // 判断队列是否为空
  56.     bool isEmpty() {
  57.         return front == nullptr;
  58.     }
  59. };
  60.  
  61. int main() {
  62.     Queue<int> queue;
  63.  
  64.     queue.enqueue(1);
  65.     queue.enqueue(2);
  66.     queue.enqueue(3);
  67.  
  68.     std::cout << "Front element: " << queue.peek() << std::endl; // 输出: Front element: 1
  69.  
  70.     queue.dequeue();
  71.  
  72.     std::cout << "Front element: " << queue.peek() << std::endl; // 输出: Front element: 2
  73.  
  74.     return 0;
  75. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/741514
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号