漫画算法笔记

链表实现

#include <iostream> #include <stdlib.h> using namespace std; //C/C++代码实现 template<typename T> struct Node { T _data; Node<T> *_next; Node(T data) :_data(data) {}; }; template<typename T> class MyList { public: ~MyList() { Node<T> *temp = _head; for ( int i =0; i < _size; ++i ) { Node<T> *delNode = temp; temp = temp->_next; delete delNode; } } void toString() { Node<T> *temp = _head; for ( int i = 0; i < _size; ++i) { cout << temp->_data << " "; temp = temp->_next; } cout << endl; } /* 链表插入元素 @param data 插入元素 @param index 插入位置 */ void insert(const T &data, const int &index) { if ( index < 0 || index > _size ) { throw out_of_range("超出链表节点范围"); } Node<T> *insertNode = new Node<T>(data); if ( _size == 0 ) { //空链表 _head = insertNode; _last = insertNode; } else if ( index == 0 ) { //插入头部 insertNode->_next = _head; _head = insertNode; } else if ( index == _size ) { //插入尾部 _last->_next = insertNode; _last = insertNode; } else { //插入中间 Node<T> *preNode = get(index - 1); insertNode->_next = preNode->_next; preNode->_next = insertNode; } ++_size; } /* 链表删除元素(被删除节点内存不释放) @param index 删除的位置 */ Node<T> *remove(const int &index) { if (index < 0 || index > _size) { throw out_of_range("超出链表节点范围"); } Node<T> *removeNode; if ( index == 0 ) { //删除头结点 removeNode = _head; _head = _head->_next; } else if (index == _size - 1) { //删除尾节点 removeNode = _last; Node<T> *preNode = get(index - 1); _last = preNode; _last->_next = nullptr; } else { //删除中间节点 Node<T> *preNode = get(index - 1); removeNode = preNode->_next; preNode->_next = preNode->_next->_next; } --_size; return removeNode; } /* 链表查找元素 */ Node<T>* get(int index) { if (index < 0 || index > _size) { throw out_of_range("超出链表节点范围"); } Node<T>* temp = _head; for (int i =0; i < index; ++i) { temp = temp->_next; } return temp; } private: Node<T> *_head; Node<T> *_last; int _size = 0; }; int main(int argc, char** argv) { MyList<int> list; list.insert(3, 0); list.insert(7, 1); list.insert(9, 2); list.insert(5, 3); list.insert(6, 1); list.toString(); //3 6 7 9 5 list.remove(1); list.toString(); //3 7 9 5 system("pause"); return 0; }