同上一篇文章,我们一样是把以前使用C语言实现的单向链表用模版实现了一次,进一步让我们对模版和C++的封装特性有了了解。对于链表的操作我们不过多介绍了,如果有还不清楚操作的,请看以前介绍链表的文章。
#pragma once // 链表储存数据的结构体 template<typename T> struct LinkListNode { T data; LinkListNode* next; }; template<typename T> class LinkList { public: LinkList(); ~LinkList(); void clear(); // 清空 T get(int pos); // 获取某位置的元素 int insert(int pos, T& data); // 插入一个元素 T remove(int pos); // 删除一个元素 int length(); // 获取链表长度 private: LinkListNode < T >* m_header; // 链表头节点 int m_length; // 链表长度 }; template<typename T> int LinkList<T>::length() { return m_length; } template<typename T> T LinkList<T>::remove(int pos) { // 备份头节点指针 LinkListNode < T >* pCur = m_header; // 循环找到pos位置的前一个节点 for (int i = 0; i < pos; i++) { if (pCur->next != nullptr) pCur = pCur->next; } // 定义一个指针记录pos位置的节点 LinkListNode < T >* pDel = pCur->next; // 备份节点的数据 T tData = pDel->data; // 改变指针指向,让链表跳过pos位置的节点重新连接 pCur->next = pDel->next; // 删除节点并长度-- delete pDel; m_length--; // 返回被删除的数据 return tData; } template<typename T> int LinkList<T>::insert(int pos, T& data) { // 记录头节点位置 LinkListNode < T >* pCur = m_header; // 生成新节点 LinkListNode < T >* node = new LinkListNode < T > ; // 给新节点数据域赋值 node->data = data; // 循环找到 pos 位置的前一个节点的位置 for (int i = 0; i < pos; i++) { if (pCur->next != nullptr) pCur = pCur->next; } // 把新节点插入到 pos 的前一个位置并对长度++ node->next = pCur->next; pCur->next = node; m_length++; return 0; } template<typename T> T LinkList<T>::get(int pos) { // 记录头节点位置 LinkListNode < T >* pCur = m_header; // 循环找到 pos 位置的节点 for (int i = 0; i <= pos; i++) { // 如果后面没有节点了,就指向最后一个节点 if (pCur->next != nullptr) pCur = pCur->next; } // 返回节点数据 return pCur->data; } template<typename T> void LinkList<T>::clear() { while (length()) { remove(0); } } template<typename T> LinkList<T>::~LinkList() { clear(); // 释放头节点 delete m_header; } template<typename T> LinkList<T>::LinkList() { // 初始化头节点和长度 m_header = new LinkListNode < T > ; m_header->next = nullptr; m_length = 0; }
测试代码
#include <iostream> #include "seqlist.hpp" #include "LinkList.hpp" using namespace std; void LinkListTest() { //创建链表 LinkList<int> list; int array[5] = { 0 }; //初始化 for (int i = 0; i < sizeof(array) / sizeof(int); ++i) { array[i] = i; //插入数据 list.insert(array[i], i); } //遍历链表 for (int i = 0; i < list.length(); ++i) { cout << "list emement " << i << " value = " << list.get(i) << endl; } //删除所有节点 while (list.length() > 0) { cout << "Delete element " << list.remove(0) << endl; } } int main(int argc, char* argv[]) { LinkListTest(); return 0; }