Loading... 今天把单向链表写了一下。(超了预计时间一个小时才写完QAQ) 在这里记录一下吧。 后面加了几个函数，为了加强对指针的理解。代码我还在测试，所以可能会有BUG。欢迎指正。 ##代码实现 ```cpp #pragma once #include <iostream> using namespace std; struct Node //链表的节点 { int value; Node* next; Node(int n = 0) :value(n), next(nullptr) { } }; class List { private: int SIZE; Node* head; public: /*构造、析构*/ List(); //构建一个单链表; ~List(); //销毁一个单链表; /*链表信息*/ int size() { return SIZE; } bool empty() { return SIZE == 0 ? true : false; } Node* begin() { return head->next; } /*查找*/ Node* find(int data); //查找节点 /*插入*/ void push_back(int data); //在尾部插入指定的元素 Node* insert(int i, int data); //在指定位置插入指定元素 Node* insert(Node* node, int data); void push_front(int data); //在头部插入指定元素 /*删除*/ void pop_back(); //在尾部删除元素 void clear(); //删除所有数据 Node* erase(int data); //删除指定的数据 Node* erase(Node* node); Node* remove(int ith); void pop_front(); //在头部删除节点 /*其他*/ void traval(); //遍历线性表 void reverse(); //反转链表 bool IsCircle(); //检测链表中是否含有环 void merge(List a); //合并两个有序链表 Node* middle(); //寻找链表中间节点 }; /***************************************************************** Function:List Description：构造函数，主要是初始化size、实例化头指针head。 *****************************************************************/ inline List::List() { SIZE = 0; head = new Node(); } /***************************************************************** Function:List Description：析构函数，主要是释放链表的空间。 *****************************************************************/ inline List::~List() { Node* tmp = head->next; while (SIZE > 0) tmp = erase(tmp); delete head; } /***************************************************************** Function:find Description：遍历查找值为data的节点。 *****************************************************************/ inline Node* List::find(int data) { Node* tmp = head->next; while (tmp != nullptr) { if (tmp->value == data) return tmp; tmp = tmp->next; } return nullptr; } /***************************************************************** Function:push_back Description：在链表最后面插入一个节点。 *****************************************************************/ inline void List::push_back(int data) { Node* tmp = head; while (tmp->next != nullptr) tmp = tmp->next; Node* add = new Node(data); tmp->next = add; SIZE++; return; } /***************************************************************** Function:insert Description：在第i个节点后插入值data。 *****************************************************************/ inline Node* List::insert(int i, int data) { if (i > SIZE || i < 0) return nullptr; Node* tmp = head; for (int j = 0; j < i; j++) tmp = tmp->next; Node* add = new Node(data); add->next = tmp->next; tmp->next = add; SIZE++; return add; } /***************************************************************** Function:insert Description：在node节点后插入值data。 *****************************************************************/ inline Node* List::insert(Node* node, int data) { if (node == nullptr) return nullptr; Node* add = new Node(data); add->next = node->next; node->next = add; SIZE++; return add; } /***************************************************************** Function:push_front Description：在最开始的节点前插入一个节点。 *****************************************************************/ inline void List::push_front(int data) { insert(head, data); return; } /***************************************************************** Function:pop_back Description：删除最后一个节点。 *****************************************************************/ inline void List::pop_back() { if (SIZE == 0) return; Node* tmp = head->next; while (tmp->next != nullptr) tmp = tmp->next; erase(tmp); return; } /***************************************************************** Function:clear Description：清空链表。 *****************************************************************/ inline void List::clear() { Node* tmp = head->next; while (SIZE > 0) tmp = erase(tmp); return; } /***************************************************************** Function:erase Description：删除指定的数据。 *****************************************************************/ inline Node* List::erase(int data) { return erase(find(data)); } /***************************************************************** Function:erase Description：删除node节点的数据。 *****************************************************************/ inline Node* List::erase(Node* node) { if (node == nullptr) return nullptr; Node* prev = head; while (prev != nullptr && prev->next != node) prev = prev->next; prev->next = node->next; delete node; SIZE--; return prev->next == nullptr ? prev : prev->next; } /***************************************************************** Function:remove Description：删除第ith个数据。 *****************************************************************/ inline Node* List::remove(int ith) { if (ith > SIZE || ith <= 0) return nullptr; Node* tmp = head; for (int i = 0; i < ith; i++) tmp = tmp->next; return erase(tmp); } /***************************************************************** Function:pop_front Description：删除第一个节点。 *****************************************************************/ inline void List::pop_front() { erase(head->next); return; } /***************************************************************** Function:traval Description：遍历链表。 *****************************************************************/ inline void List::traval() { if (SIZE == 0) return; Node* tmp = head->next; while (tmp != nullptr) { std::cout << tmp->value << " "; tmp = tmp->next; } return; } /***************************************************************** Function:reverse Description：反转链表 *****************************************************************/ void List::reverse() { if (SIZE <= 1) return; //定义三个指针来遍历修改 Node* prev = nullptr; Node* cur = head->next; Node* nex = cur->next; while (nex != nullptr) { cur->next = prev; prev = cur; cur = nex; nex = nex->next; } cur->next = prev; head->next = cur; return; } /***************************************************************** Function: IsCircle Description：利用快慢指针判断链表中是否有环。若两个指针在链表中 相遇了，就说明链表中含有环。 *****************************************************************/ inline bool List::IsCircle() { Node* fast = head->next; Node* slow = head->next; while (fast != slow) //快慢指针相遇说明没有终点 { if (fast->next == nullptr || fast->next->next == nullptr) return false; //有终点一定没有环 fast = fast->next->next; slow = slow->next; } return true; } /***************************************************************** Function: merge Description：合并两个有序链表 *****************************************************************/ inline void List::merge(List a) { List tmp = *this; Node* p1 = tmp.head->next; Node* p2 = a.head->next; clear(); //清空，方便赋值 while (p1 != nullptr && p2 != nullptr) { if (p1->value < p2->value) push_back(p1->value); else push_back(p2->value); p1 = p1->next; p2 = p2->next; } while (p1 != nullptr) { push_back(p1->value); p1 = p1->next; } while (p2 != nullptr) { push_back(p2->value); p2 = p2->next; } tmp.~List(); return; } /***************************************************************** Function: middle Description：利用快慢指针寻找中间节点 *****************************************************************/ inline Node * List::middle() { Node* fast = head->next; Node* slow = head->next; while (fast != nullptr) { //快指针到重点了，慢指针指向的就是中点 fast = fast->next->next; slow = slow->next; } return slow; } ``` 最后修改：2019 年 05 月 12 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏