首页 > 代码库 > 4.2.2 算法之美--单链表实现
4.2.2 算法之美--单链表实现
按照书上的要求实现了一下单链表；单链表的实现可能以前看过几次了；现在想想最主要的几个操作算法应该能够写了吧；遇到的问题：
1. 链表节点写成private;所已给出了访问的接口；
2.模板类的.h和.cpp实现写在同一个文件；
3.感觉以后的数据结构实现还是用纯c的实现好一些；然后书主要是思路
节点类：
#ifndef SINGLELIST_LISTNODE_H_#define SINGLELIST_LISTNODE_H_template <class T>class ListNode{public: //定义为private时，所以在会用到访问 T data; ListNode<T> * pNext;public: ListNode() : pNext(nullptr){} ListNode(T value_) :data(value_), pNext(nullptr){} ~ListNode(){} void SetpNext(ListNode<T>* next_); void SetData(T value_); ListNode<T>* GetpNext(); T& GetData();};template <class T>void ListNode<T>::SetpNext(ListNode<T>* next_){ pNext = next_;}template<class T>void ListNode<T>::SetData(T value_){ data = value_;}template<class T>ListNode<T>* ListNode<T>::GetpNext(){ return pNext;}template<class T>T& ListNode<T>::GetData(){ return data;}#endif
链表类：
#ifndef SINGLELIST_SINGLELIST_H_#define SINGLELIST_SINGLELIST_H_#include "ListNode.h"template<class T>class SingleList{private: ListNode<T>* head; ListNode<T>* tail;public: SingleList(); ~SingleList(); bool AddTail(T value_); bool RemoveTail(); bool InsertAt(int index_, T value_); bool RemoveAt(int index_); T& GetAt(int index_); bool IsEmpty(); int GetCount(); void RemoveAll(); ListNode<T>* GetHead(); ListNode<T>* GetTail(); ListNode<T>* GetNodeAt(int index_); ListNode<T>* GetCur(); ListNode<T>* TowardCur();};template<class T>bool SingleList<T>::AddTail(T value_){ ListNode<T>* pointer = new ListNode<T>(value_); tail->SetpNext(pointer); tail = tail->pNext; tail->pNext = nullptr; if (tail != nullptr) { return true; } else { return false; }}template<class T>//在索引值指向的节点前插入新节点bool SingleList<T>::InsertAt(int index_, T value_){ if (index_ > this->GetCount() || index_ < 0) { cerr << "A wrong position!\n"; return false; } ListNode<T>* current = head; while (index_) { current = current->pNext; index_--; } ListNode<T>* add = new ListNode<T>(value_); add->pNext = current->pNext; current->pNext = add; if (current != nullptr) { return true; } else { return false; }}template<class T>bool SingleList<T>::RemoveTail(){ return RemoveAt(this->GetCount() - 1);}template<class T>bool SingleList<T>::RemoveAt(int index_){ if (index_ > this->GetCount() || index_ < 0) { cerr << "A wrong position!\n"; return false; } ListNode<T>* current = head; while (index_ - 1) { current = current->pNext; index_--; } ListNode<T>* deletePoint = current->pNext; if (current->pNext->pNext == nullptr) { current->pNext = nullptr; } else current->pNext = current->pNext->pNext; delete deletePoint; return true;}template<class T>SingleList<T>::SingleList(){ head = new ListNode<T>(); tail = head; tail->pNext = NULL;}template<class T>SingleList<T>::~SingleList(){ RemoveAll(); delete head;}template<class T>T& SingleList<T>::GetAt(int index_){ if (index_ > GetCount() || index_ < 0) { cerr << "A wrong position!\n"; } ListNode<T>* cur; cur = head->pNext; while (index_) { cur = cur->pNext; index_--; } return cur->GetData();}template<class T>bool SingleList<T>::IsEmpty(){ return head->pNext == NULL;}template<class T>int SingleList<T>::GetCount(){ int count = 0; ListNode<T>* cur = head->pNext; while (cur != nullptr) { cur = cur->pNext; count++; } return count;}template<class T>void SingleList<T>::RemoveAll(){ ListNode<T>* cur; while (head->pNext != nullptr) { cur = head->pNext; head->pNext = cur->pNext; delete cur; } tail = head;}template<class T>ListNode<T> * SingleList<T>::GetNodeAt(int index_){ if (index_ > this->GetCount() - 1 || index_ < 0) { cerr << "A wrong position!\n"; } ListNode<T>* handle = head->pNext; while (index_) { handle = handle->pNext; index_--; } return handle;}template <class T>ListNode<T>* SingleList<T>::GetHead(){//返回头指针 return head;}template <class T>ListNode<T>* SingleList<T>::GetTail(){//返回尾指针 return tail;}template <class T>ListNode<T>* SingleList<T>::GetCur(){ return cur;}template <class T>ListNode<T>* SingleList<T>::TowardCur(){ cur = cur->GetLink(); return cur}#endif
测试函数：
#include <iostream> #include "SingleList.h" using namespace std;int main(){ SingleList<int> list; for (int i = 0; i < 9; i++) list.AddTail(i); cout << list.GetCount() << endl; cout << list.GetAt(3) << endl; list.RemoveAt(3); cout << list.GetCount() << endl; cout << list.GetAt(3) << endl; list.RemoveAll(); cout << list.GetCount() << endl; system("PAUSE"); return 0;}
结果：
后续用纯c实现链表的基本操作：创建，增，删，改，查。
4.2.2 算法之美--单链表实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。