- ////////////////////////////带附加头结点的单链表的类定义///////////////////////////////////////
- template <class T> //定义在头文件"LinkedList.h"中
- struct LinkNode //链表结点类的定义
- {
- T data; //数据域
- LinkNode<T> *link; //链指针域
- LinkNode(LinkNode<T> *ptr = NULL)
- { link = ptr; } //仅初始化指针成员的构造函数
- LinkNode(const T& item, LinkNode<T> *ptr = NULL)
- { data = item; link = ptr; } //初始化数据与指针成员的构造函数
- };
- template <class T>
- class List:public LinearList<T> //单链表类定义,不用继承也可以实现
- {
- public:
- List(){first = new LinkNode<T>;} //构造函数
- List(const T& x){first = new LinkNode<T>(x);} //构造函数
- List(List<T>& L); //复制构造函数
- ~List(){makeEmpty();} //析构函数
- void makeEmpty(); //将链表置为空表
- int Length()const; //计算链表的长度
- LinkNode<T> *getHead()const{return first;} //返回附加头结点地址
- LinkNode<T> *Search(T x); //搜索含数据x的元素
- LinkNode<T> *Locate(int i); //搜索第i个元素的地址
- bool getData(int i, T& x); //取出第i个元素的值
- void setData(int i, T& x); //用x修改第i个元素的值
- bool Insert(int i, T& x); //在第i个元素后插入x
- bool Remove(int i, T& x); //删除第i个元素,x返回该元素的值
- bool IsEmpty()const //判表空否?空则返回false
- { return first -> link == NULL? true; false; }
- bool IsFull()const{return false;} //判表满否?不满则返回false
- void Sort(); //排序
- void input(); //输入
- void output(); //输出
- List<T>& operator = (List<T>& L); //重载函数:赋值
- protected:
- LinkNode<T> *first; //链表的头指针
- };
- ///////////////////////////////List类的成员函数的实现//////////////////////////////////////////
- template <class T>
- List<T>::List(List<T>& L)
- {
- //复制构造函数
- T value;
- LinkNode<T> *srcptr = L.getHead(); //被复制表的附加头结点地址
- LinkNode<T> *destptr = first = new LinkNode<T>;
- while(srcptr ->link != NULL) //逐个结点复制
- {
- value = srcptr ->link ->data;
- destptr ->link = new LinkNode<T>(value);
- destptr = destptr ->link;
- srcptr = srcptr ->link;
- }
- destptr ->link = NULL;
- };
- template <class T>
- void List<T>::makeEmpty()
- {
- //将链表置为空表
- LinkNode<T> *q;
- while(first->link!=NULL) //当链不空时,删去链中所有结点
- {
- q = first->link;
- first->link = q->link; //保存被删结点,从链上摘下该结点
- delete q; //删除(仅保留一个表头结点)
- }
- };
- template <class T>
- int List<T>::Length()const
- {
- //计算带附加头结点的单链表的长度
- LinkNode<T> *p = first->link;
- int count = 0;
- while(p != NULL) //循链扫描,寻找链尾
- {
- p = p->link;
- count++;
- }
- return count;
- };
- template <class T>
- LinkNode<T> *List<T>::Search(T x)
- {
- //在表中搜索含数据x的结点,搜索成功时函数返回该结点地址;否则返回NULL值。
- LinkNode<T> *current = first->link;
- while(current != NULL)
- {
- if(current->data == x) break; //循链找含x结点
- else current = current->link;
- }
- return current;
- };
- template <class T>
- LinkNode<T> *List<T>::Locate(int i)
- {
- //定位函数。返回表中第i个元素的地址。若i<0或i超出表中结点个数,则返回NULL。
- if(i<0) return NULL; //i不合理
- LinkNode<T> *current = first; int k = 0;
- while(current!=NULL && k<i) //循链找第i个结点
- {
- current = current->link;
- k++;
- }
- return current; //返回第i个结点地址,若返回NULL,表示i值太大
- };
- template <class T>
- bool List<T>::getData(int i, T& x)
- {
- //取出链中第i个元素的值
- if(i<=0) return NULL; //i值太小
- LinkNode<T> *current = Locate(i);
- if(current == NULL) return false; //i值太大
- else {x = current->data; return true;}
- };
- template<class T>
- void List<T>::setData(int i, T& x)
- {
- //给链表中第i个元素赋值x.
- if(i<=0) return; //i值太小
- LinkNode<T> *current = Locate(i);
- if(current == NULL) return; //i值太大
- else current->data = x;
- };
- template <class T>
- bool List<T>::Insert(int i, T& x)
- {
- //将新元素x插入在链表中第i个结点之后。
- LinkNode<T> *current = Locate(i);
- if(current == NULL) return false; //插入不成功
- LinkNode<T> *newNode = new LinkNode<T>(x);
- if(newNode == NULL)
- {
- cerr << "存储分配错误!" << endl;
- exit(1);
- }
- newNode->link = current->link; //链接在current之后
- current->link = newNode;
- return true; //插入成功
- };
- template <class T>
- bool List<T>::Remove(int i, T& x)
- {
- //将链表中的第i个元素删去,通过引用型参数x返回该元素的值
- LinkNode<T> *current = Locate(i-1);
- if(current == NULL || current->link == NULL)
- return false; //删除不成功
- LinkNode<T> *del = current->link; //重新拉链,将被删结点从链中摘下
- current->liink = del->link;
- x = del->data; delete del; //取出被删结点中的数据值
- return true;
- };
- template <class T>
- void List<T>::output()
- {
- //单链表的输出函数:将单链表中所有数据按逻辑顺序输出到屏幕上
- LinkNode<T> *current = first->link;
- while(current!=NULL)
- {
- cout << current->data << endl;
- current = current->link;
- }
- };
- template <class T>
- List<T>& List<T>::operator = (List<T>& L)
- {
- //重装函数:赋值操作,形式如A=B,其中A是调用此操作的List对象,B是与参数表中的引用型参数L结合的实参
- T value;
- LinkNode<T> *srcptr = L.getHead(); //被复制表的附加头结点地址
- LinkNode<T> *destptr = first = new LinkNode<T>;
- while(srcptr->link != NULL) //逐个结点复制
- {
- value = srcptr->link->data;
- destptr->link = new LinkNode<T>(value);
- destptr = destptr->link;
- srcptr = srcptr->link;
- }
- destptr->link = NULL;
- return *this; //返回操作对象地址
- };
- //该片段来自于http://www.codesnippet.cn/detail/100420149296.html
来源: http://www.codesnippet.cn/detail/100420149296.html