|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
关于链表的功能实现的其中一个头文件
- #ifndef INC_9_7LINKEDLIST_LINKEDLIST_H
- #define INC_9_7LINKEDLIST_LINKEDLIST_H
- #include <iostream>
- #include <cassert>
- #include <cstdlib>
- #include "Node.h"
- using namespace std;
- template <class T>
- class LinkedList {
- private:
- //数据成员:
- Node<T>* front, * rear; //表头和表尾
- Node<T>* prevPtr, * currPtr; //记录当前遍历位置的指针,由插入和删除操作更新
- int size; //表中的元素个数
- int position; //当前元素在表中的位置序号。由函数reset使用
- //函数成员
- //生成新结点,数据域为item,指针域为ptrNext
- Node<T>* newNode(const T& item, Node<T>* ptrNext = NULL);
- //释放结点
- void freeNode(Node<T>* p);
- //将链表L复制到当前表(假设当前表尾空)
- //被复制构造函数和“operator=”调用
- void copy(const LinkedList<T>& L);
- public:
- LinkedList(); //构造函数
- LinkedList(const LinkedList<T>& L); //复制构造函数
- ~LinkedList(); //析构函数
- LinkedList<T>& operator=(const LinkedList<T>& L); //重载运算符
- int getSize() const; //返回链表中元素个数
- bool isEmpty() const; //链表是否为空
- void reset(int pos = 0); //初始化游标位置
- void next(); //使游标移动到下一个结点
- bool endOfList() const; //游标是否到了表尾
- int currentPosition() const; //返回游标当前位置
- void insertFront(const T& item); //在表头插入结点
- void insertRear(const T& item); //在表尾添加结点
- void insertAt(const T& item); //在当前结点之前插入结点
- void insertAfter(const T& item); //在当前结点之后插入结点
- T deleteFront(); //删除头结点
- void deleteCurrent(void); //删除当前结点
- T& data(); //返回对当前结点成员数据的引用
- const T& data() const; //返回对当前结点成员数据的常引用
- //清空链表:释放所有结点的内存空间。被析构函数和“operator="调用
- void clear(void);
- };
- template <class T> Node<T>* LinkedList<T>::newNode(const T& item, Node<T>* ptrNext)
- {
- Node<T>* p;
- p = newNode<T>(item, ptrNext);
- if (p == NULL)
- {
- cout << "Memory allocation failure!" << endl;
- exit(1);
- }
- return p;
- }
- /*释放节点*/
- template <class T> void LinkedList<T>::freeNode(Node<T>* p)
- {
- delete p;
- }
- /*复制链表*/
- template <class T> void LinkedList<T>::copy(const LinkedList<T>& L)
- {
- nextNode<T>* p = L.front; //p用来遍历L
- int pos;
- while (p != NULL) //将L中的每一个元素插入到当前连接表最后
- {
- InsertRear(p->data);
- p = p->NextNode();
- }
- if (position == -1) //如果链表为空,则返回
- return;
- //在新链表中重新设置prevPtr和currptr
- prevPtr = NULL;
- currPtr = front;
- for (pos = 0; pos != position; pos++)
- {
- prevPtr = currPtr;
- currPtr = currPtr->NextNode();
- }
- }
- /*构造函数,构造新链表,size为0,positon为-1*/
- template <class T> LinkedList<T>::LinkedList() :front(NULL), rear(NULL), prevPtr(NULL), currPtr(NULL), size(0), position(-1) {}
- /*拷贝构造函数*/
- template <class T>LinkedList<T>::LinkedList(const LinkedList<T>& L)
- {
- front = rear = NULL;
- prevPtr = currPtr = NULL;
- size = 0;
- position = -1;
- Copy(L);
- }
- /*析构函数*/
- template <class T> LinkedList<T>::~LinkedList()
- {
- clear();
- }
- /*重载赋值运算符*/
- template <class T> LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& L)
- {
- if (this == &L) //不能将链表赋值给它自身
- return *this;
- clear();
- copy(L);
- return *this;
- }
- /*获取链表的大小*/
- template <class T> int LinkedList<T>::getSize()const
- {
- return size;
- }
- /*判断链表是否为空*/
- template <class T> bool LinkedList<T>::isEmpty()const
- {
- return size == 0;
- }
- /*将链表当前位置设置为pos*/
- template <class T> void LinkedList<T>::reset(int pos)
- {
- int startPos;
- if (front == NULL) //如果链表为空
- return;
- if (pos<0 || pos>size - 1) //如果指定位置不合法,返回
- {
- cerr << "ReSet:Invalid list position: " << pos << endl;
- return;
- }
- //设置与链表有关的成员
- if (pos == 0) //如果pos为0,将指针重新设置到表头
- {
- prevPtr = NULL;
- currPtr = front;
- position = 0;
- }
- else //否则重新设置currPtr,prevPtr,position
- {
- currPtr = front->NextNode();
- prevPtr = front;
- startPos = 1;
- for (position = startPos; position != pos; position++)
- {
- prevPtr = currPtr;
- currPtr = currPtr->NextNode();
- }
- }
- }
- /*将prevPtr和currPtr先前移动一个结点*/
- template <class T> void LinkedList<T>::next()
- {
- if (currPtr != NULL)
- {
- prevPtr = currPtr;
- currPtr = currPtr->NextNode();
- position++;
- }
- }
- /*判断是否已到达链表尾*/
- template <class T> bool LinkedList<T>::endOfList()const
- {
- return currPtr == NULL;
- }
- /*返回当前节点的位置*/
- template <class T> int LinkedList<T>::currentPosition()const
- {
- return position;
- }
- /*将item插入在表头*/
- template <class T> void LinkedList<T>::insertFront(const T& item)
- {
- if (front != NULL) //如果链表不为空,则调用ReSet()
- reset();
- InsertAt(item); //在表头插入
- }
- /*在表尾插入结点*/
- template <class T> void LinkedList<T>::insertRear(const T& item)
- {
- Node<T>* nNode;
- prevPtr = rear;
- nNode = newNode(item); //创建新节点
- if (rear == NULL) //如果表为空,则插入在表头
- front = rear = nNode;
- else
- {
- rear->insertAfter(nNode);
- rear = nNode;
- }
- currPtr = rear;
- position = size;
- size++;
- }
- /*将item插入在当前位置之前*/
- template <class T> void LinkedList<T>::insertAt(const T& item)
- {
- cNode<T>* nNode;
- if (prevPtr == NULL) //插入在链表头,包括将结点插入到空表中
- {
- nNode = newNode(item, front);
- front = nNode;
- }
- else //插入到链表之中,将结点置于prevPtr之后
- {
- nNode = newNode(item);
- prevPtr->insertAfter(nNode);
- }
- if (prevPtr == rear)//正在向空表中插入,或者是插入到非空表的表尾
- {
- rear = nNode; //更新rear
- position = size; //更新position
- }
- currPtr = nNode; //更新currPtr
- size++; //更新szie
- }
- /*将item插入到当前位置之后*/
- template <class T>void LinkedList<T>::insertAfter(const T& item)
- {
- cNode<T>* p;
- p = newNode(item);
- if (front == NULL) //向空链表中插入
- {
- front = currPtr = rear = p;
- position = 0;
- }
- else //插入到
- {
- if (currPtr == NULL)
- currPtr = prevPtr;
- currPtr->InsertAfter(p);
- if (currPtr == rear)
- {
- rear = p;
- position = size;
- }
- else
- position++;
- prevPtr = currPtr;
- currPtr = p;
- }
- size++; //更新链表长度
- }
- /*删除表头结点*/
- template <class T> T LinkedList<T>::deleteFront()
- {
- T item;
- reset();
- if (front == NULL)
- {
- cerr << "Invalid deletion!" << endl;
- exit(1);
- }
- item = currPtr->data;
- deleteCurrent();
- return item;
- }
- /*删除链表当前位置的结点*/
- template <class T> void LinkedList<T>::deleteCurrent()
- {
- cNode<T>* p;
- if (currPtr == NULL)//如果链表为空或者到达表尾
- {
- cerr << "Invalid deletion!" << endl;
- exit(1);
- }
- if (prevPtr == NULL) //删除操作发生在表头或者表中
- {
- p = front; //保存头结点地址
- front = front->NextNode(); //将其从链表分离
- }
- else //分离prevPtr之后的一个内部结点,保存其地址
- {
- p = prevPtr->deleteAfter();
- }
- if (p == rear) //如果尾节点被删除
- {
- rear = prevPtr; //新的表尾是prevPtr
- position--; //position回退一步
- }
- currPtr = p->NextNode(); //使currPtr越过被删除的结点
- freeNode(p); //释放节点,并使链表长度减-
- size--;
- }
- //返回一个当前节点的数值引用
- template <class T>T& LinkedList<T>::data()
- {
- if (size == 0 || currPtr == NULL) //如果链表为空,或者到达链表尾
- {
- cerr << "Data:invalid reference!" << endl;
- exit(1);
- }
- return currPtr->data;
- }
- /*清空链表*/
- template <class T> void LinkedList<T>::clear()
- {
- cNode<T>* currPosition, * nextPosition;
- currPosition = front;
- while (currPosition != NULL)
- {
- nextPosition = currPosition->NextNode(); //取得下一个结点的地址
- FreeNode(currPosition);//删除当前节点
- currPosition = nextPosition; //当前指针移到下一个结点
- }
- front = rear = NULL;
- prevPtr = currPtr = NULL;
- size = 0;
- position = -1;
- }
- #endif
复制代码 |
|