Loading... 今天的作业中有链表相关的题目，所以就顺手写了一个双向链表。在这里记录一下我写的链表吧。 (没什么好说的直接上代码吧) ##代码实现 ```cpp #include <iostream> struct Node { int value; Node* previous; Node* next; Node() :value(0), previous(nullptr), next(nullptr) { } }; class MyList { private: size_t SIZE; Node* head; Node* tail; public: /*构造、析构*/ MyList(); ~MyList(); /*插入、删除*/ void insert(Node* node, int data);//在结点node后插入数据data void insert_prev(Node* node, int data);//在结点node前插入数据data void push_back(int data);//在最后加入节点 Node* erase(Node* node);//删除node结点 void pop_back();//删除最后一个节点 /*查找*/ Node* find(int data);//查找链表中数据为data的结点 Node* search(int ith);//查找链表中第ith个结点 /*链表信息*/ int size() { return SIZE; } bool empty() { return SIZE == 0; } Node* begin() { return head; } Node* end() { return tail; } /*其他*/ void display(); void clear(); }; /***************************************************************** Function:MyList Description：构造函数，主要是初始化size、实例化头结点、初始化 头指针head和尾指针tail。 *****************************************************************/ inline MyList::MyList() { SIZE = 0; head = new Node(); tail = head; } /***************************************************************** Function:~MyList Description：析构函数，主要是释放链表的空间。 *****************************************************************/ inline MyList::~MyList() { while (SIZE > 0) erase(tail); delete head; } /***************************************************************** Function:insert Description：在node节点后插入值data。 *****************************************************************/ inline void MyList::insert(Node* node, int data) { if (node == nullptr) return; Node* tmp = new Node(); tmp->value = data; if (node->next != nullptr) {//如果node不为末节点就修改node后一个节点 tmp->next = node->next; node->next->previous = tmp; } //处理node和tmp的关系 node->next = tmp; tmp->previous = node; //如果node是末节点，则将tail修改为tmp if (node == tail) tail = tmp; SIZE++; return; } /***************************************************************** Function:insert_prev Description：在node节点前插入值data。 *****************************************************************/ inline void MyList::insert_prev(Node* node, int data) { if (node == nullptr || node == head) return; Node* tmp = new Node(); tmp->value = data; if (node->previous != nullptr) {//如果node不为头节点就修改node前一个节点 tmp->previous = node->previous; node->previous->next = tmp; } //处理node和tmp的关系 node->previous = tmp; tmp->next = node; SIZE++; return; } /***************************************************************** Function:push_back Description：在链表最后面插入一个节点。 *****************************************************************/ inline void MyList::push_back(int data) { insert(tail, data); return; } /***************************************************************** Function:erase Description：从链表中删除node节点，返回下一节点的指针。 *****************************************************************/ inline Node* MyList::erase(Node* node) { if (node == nullptr) return tail; Node* tmp = node->next; //分三种情况，node为head，node为tail，以及node在中间 if (node == tail) { node->previous->next = nullptr; tail = node->previous; } else { node->previous->next = node->next; node->next->previous = node->previous; } //调整完node前后节点的关系即可删除node节点 delete node; SIZE--; return tmp; } /***************************************************************** Function:puop_back Description：删除链表最后一个节点。 *****************************************************************/ inline void MyList::pop_back() { if (SIZE == 0) return; erase(tail); return; } /***************************************************************** Function:find Description：遍历查找值为data的节点。 *****************************************************************/ inline Node* MyList::find(int data) { Node* tmp = head->next; while (tmp != nullptr) { if (tmp->value == data) return tmp; tmp = tmp->next; } return nullptr; } /***************************************************************** Function:search Description：遍历查找第ith个节点。 *****************************************************************/ inline Node* MyList::search(int ith) { if (ith > SIZE || ith < 1) return nullptr; Node* tmp = head; for (int i = 0; i < ith; i++) tmp = tmp->next; return tmp; } /***************************************************************** Function:display Description：遍历输出链表。 *****************************************************************/ inline void MyList::display() { Node* tmp = head->next; while (tmp != nullptr) { std::cout << tmp->value << " "; tmp = tmp->next; } return; } /***************************************************************** Function:clear Description：清空链表。 *****************************************************************/ inline void MyList::clear() { while (SIZE > 0) erase(tail); return; } ``` 我简单地测试了一下似乎没什么问题。单向链表后面再补吧。 ##随便写写 在写双向链表的时候我遇到了一个error LNK2005，我把所有的函数都加上 inline 修饰词后就没事了。猜测可能是我写在两个cpp文件导致的。具体原因找到在写下来吧。(之前写模板类好像没出过这个问题) 这个错误似乎是重复定义了一些变量。我把函数声明和定义放在 .h 文件里面就不会了。 最后修改：2019 年 05 月 12 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏