#ifndef __CHAIN_H__ #define __CHAIN_H__ #include <iostream> using namespace std; //VS平台下自己定义了nullptr = null = 0 //但是在gcc下没有定义 #ifndef nullptr #define nullptr 0 #endif /* 链表的节点元素类 */ template <class T> class ChainNode { public: T data; //数据域 ChainNode<T> *link; //指向下一个节点 }; /* 链表类 */ template <class T> class Chain { public: Chain() //构造函数 { first = nullptr; //头指针清空 } ~Chain(); //析构函数 bool isEmpty() const //判断链表是否为空 { return first == nullptr; } int Length() const; //获取链表长度 bool Find(int k,T& x) const; //获取第k个元素 int Search(const T& x) const; //在链表中查找元素x Chain<T>& Delete(int k,T& x); //从链表中删除一个元素 Chain<T>& Insert(int k,const T& x); //向链表中插入一个元素 void Output(ostream& out) const; //按照链表中遍历方向输出链表元素 private: ChainNode<T> *first; //指向第一个结点的指针 }; template<class T> Chain<T>::~Chain() //析构函数中将申请的堆空间都释放掉 { ChainNode<T> *next; while (first) { next = first->link; delete first; first = next; } } /*获取链表的长度*/ template<class T> int Chain<T>::Length() const { ChainNode<T> *current = first; int len = 0; while (current) { ++len; current = current->link; //指针向后移动 } return len; } /*返回第k个元素*/ template<class T> bool Chain<T>::Find(int k,T& x) const { ChainNode<T> *current = first; while(k--) { if (current->link) return false; current = current->link; } x = current; return true; } /* 在链表中搜索元素x */ template<class T> int Chain<T>::Search(const T& x) const { ChainNode<T> *current = first; int index = 0; while (current && current->data == x) { current = current->link; ++index; } if (!current) return -1; return index; } /* 从当前链表中删除一个元素 */ template<class T> Chain<T>& Chain<T>::Delete(int k,T& x) { if(k < 1 || k > Length()) //删除元素的位置不符合要求,则抛出异常 throw "不在范围内"; ChainNode<T> *p = first; if(k == 1) //如果要删除第一个元素 { first = first->link; delete p; return *this; } k -= 2; while(k--) //将p移动到要删除元素的上一个位置 { p = p->link; } ChainNode<T> *tmp = p->link; //要删除的元素 if(!tmp->link) //如果删除的是最后一个元素 { p->link = nullptr; delete tmp; } else { p->link = tmp->link; delete tmp; } return *this; } /* 在第k个元素之后插入节点,和这个过程要分为两种情况: 1、插入点在链表的头部,也就是k=0的位置; 2、插入点在链表的中间。 */ template<class T> Chain<T>& Chain<T>::Insert(int k,const T& x) { ChainNode<T> *p = new ChainNode<T>; //新节点 p->data = x; //数据域 p->link = nullptr; //指针域 //检查k是否在范围内 if(k < 0 || k > Length()) //插入的位置不满足要求,则抛出异常 throw "不在范围内"; if(0 == k) //插入位置在0处,则插入到第一个节点的后面 { if(!first) //如果原链表为空 { first = p; return *this; } p->link = first->link; //改变指针指向 first->link = p; return *this; } else { ChainNode<T> *index = first; k = k-1; while(k--) //index移动到要插入的前一个位置 { /*if(!index->link) throw "不在范围内";*/ index = index->link; //index向后移动 } p->link = index->link; //修改指针指向 index->link = p; return *this; } } /*依次输出链表中的元素*/ template<class T> void Chain<T>::Output(ostream& out) const { ChainNode<T> *p = first; out << "Chain List: " << endl; while (p) //遍历当前链表依次输出元素值 { out << p->data << " "; p = p->link; } out << endl; } template <class T> ostream& operator<<(ostream& out,const Chain<T>& x) { x.Output(out); return out; } #endif // !__CHAIN_H__原文链接:https://www.f2er.com/datastructure/382538.html