数据结构（未完待续）

栈

#ifndef ARRAY_STACK_H #define ARRAY_STACK_H #include <iostream> //#include "ArrayStack.h" using namespace std; template<class T> class ArrayStack { public: ArrayStack(unsigned int length); ~ArrayStack(); void push(T t); T peek(); T pop(); int size(); int is_Empty(); private: T* arr; unsigned int count; }; // 创建栈 template<class T> ArrayStack<T>::ArrayStack(unsigned int length):count(0) { arr = new T[count]; if (!arr){ cout << "arr malloc error" << endl; } } // 销毁栈 template<class T> ArrayStack<T>::~ArrayStack() { if (arr) { delete[] arr; arr = nullptr; } } // 进栈 template<class T> void ArrayStack<T>::push(T t) { arr[count] = t; count++; } // 返回栈顶元素 template<class T> T ArrayStack<T>::peek() { return arr[count - 1]; } // 出栈 template<class T> T ArrayStack<T>::pop() { int ret = arr[count - 1]; count--; return ret; } // 返回栈的大小 template<class T> int ArrayStack<T>::size() { return count; } // 判断栈是否为空 template<class T> int ArrayStack<T>::is_Empty() { return size() == 0; } #endif

队列

#ifndef ARRAY_QUEUE_H #define ARRAY_QUEUE_H #include <iostream> using namespace std; template<class T> class ArrayQueue { public: ArrayQueue(unsigned int length); ~ArrayQueue(); void add(T t); T front(); T pop(); int size(); int isEmpty(); private: T* arr; int count; }; // 创建队列 template<class T> ArrayQueue<T>::ArrayQueue(unsigned int length) :count(0) { arr = new T[length]; if (!arr) { cout << "arr malloc error!" << endl; } } // 销毁队列 template<class T> ArrayQueue<T>::~ArrayQueue() { if (arr) { delete[] arr; arr = nullptr; } } // 入队 template<class T> void ArrayQueue<T>::add(T t) { arr[count] = t; count++; } // 返回队首元素 template<class T> T ArrayQueue<T>::front() { return arr[0]; } // 返回并删除队尾的元素 template<class T> T ArrayQueue<T>::pop() { count--; return arr[count]; } // 返回队列的大小 template<class T> int ArrayQueue<T>::size() { return count; } // 返回队列是否为空 template<class T> int ArrayQueue<T>::isEmpty() { return 0 == count; } #endif

双向链表

/************************************************************************/ /* author@huluwa date@2017-11-13 */ /************************************************************************/ #ifndef DOUBLE_LINK_H #define DOUBLE_LINK_H #include <iostream> using namespace std; template<class T> struct DNode { public: DNode(){} DNode(T t, DNode* prev, DNode* next) { this->value = t; this->prev = prev; this->next = next; } public: T value; DNode* prev; DNode* next; }; template<class T> class DoubleLink { public: DoubleLink(); ~DoubleLink(); int size(); int is_empty(); T get(int index); T get_first(); T get_last(); int insert(int index, T t); int insert_first(T t); int insert_last(T t); int del(int index); int delete_first(); int delete_last(); private: int count; // 链表长度 DNode<T>* phead; DNode<T>* get_node(int index); }; template<class T> DoubleLink<T>::DoubleLink() :count(0) { // 创建表头，表头不存储数据 phead = new DNode<T>(); phead->prev = phead->next = phead; } template<class T> DoubleLink<T>::~DoubleLink() { // 删除所有节点 DNode<T>* ptmp; DNode<T>* pnode = phead->next; while (pnode != phead) { ptmp = pnode; pnode = pnode->next; delete ptmp; } // 删除表头 delete phead; phead = nullptr; } // 返回节点数目 template<class T> int DoubleLink<T>::size(){ return count; } // 返回链表是否为空 template<class T> int DoubleLink<T>::is_empty(){ return count == 0; } // 获取地index位置的节点 template<class T> DNode<T>* DoubleLink<T>::get_node(int index) { // 判断参数有效性 if (index < 0 || index > count) { cout << "get node failed! the index in out of bound!" << endl; return nullptr; } // 正向查找 if (index <= count / 2) { int i = 0; DNode<T>* pindex = phead->next; while (i < index) { pindex = pindex->next; i++; } return pindex; } else { // 反向查找 int i = count; DNode<T>* pindex = phead->prev; while (i > index) { pindex = pindex->prev; i--; } return pindex; } } // 获取第index位置节点的值 template<class T> T DoubleLink<T>::get(int index) { return get_node(index)->value; } // 获取第一个节点的值 template<class T> T DoubleLink<T>::get_first() { return get_node(0)->value; } // 获取最后一个节点的值 template<class T> T DoubleLink<T>::get_last() { return get_node(count-1)->value; } // 将节点插入到第index位置之前 template<class T> int DoubleLink<T>::insert(int index, T t) { // 判断参数有效性 if (index < 0 || index > count) { cout << "get node failed! the index in out of bound!" << endl; return -1; } DNode<T>* pindex = get_node(index); DNode<T>* pnode = new DNode<T>(t, pindex->prev, pindex); pindex->prev->next = pnode; pindex->prev = pnode; count++; return 0; } // 将节点插入到第一个节点处 template<class T> int DoubleLink<T>::insert_first(T t) { /*DNode<T>* pnode = new DNode<T>(t, phead, phead->next); phead->next->prev = pnode; phead->next = pnode; count++;*/ insert(0, t); return 0; } // 将节点追加到链表的末尾 template<class T> int DoubleLink<T>::insert_last(T t) { /*DNode<T>* pnode = new DNode<T>(t, phead->prev, phead); phead->prev->next = pnode; phead->prev = pnode; count++;*/ insert(count - 1, t); return 0; } // 删除index位置的节点 template<class T> int DoubleLink<T>::del(int index) { DNode<T>* pindex = get_node(index); pindex->next->prev = pindex->prev; pindex->prev->next = pindex->next; delete pindex; count--; return 0; } // 删除第一个节点 template<class T> int DoubleLink<T>::delete_first(){ return del(0); } // 删除最后一个节点 template<class T> int DoubleLink<T>::delete_last(){ return del(count - 1); } #endif