c++ 用类模版实现链表(c++语言程序设计第四版示例代码)

C++  /  houtizong 发布于 3年前   302

#include<iostream>#include<cassert>using namespace std;template<class T>class Node{private:Node<T> * next;public:T data;                                                                     //数据域Node(const T & data, Node<T> * next = 0):data(data),next(next){}            //构造函数void InsertAfter(Node<T> *p){                                              //在本结点之后出入一个同类结点Pp->next = next;        //P结点指针域指向当前结点的后继结点next = p;              //当前结点的指针域指向P}                                       Node<T> *DeleteAfter(){                                                     //删除本结点的后继结点，并返回其地址Node<T>* tempp = next; //将欲删除的结点地址储存到tempp中if (next == 0)         //如果当前结点没有后继结点，则反回空指针return 0;next = tempp->next;    //使当前结点的指针域指向tempp的后继结点return tempp;          //返回被删除的结点的地址}Node<T> *NextNode(){ return next; }                                         //获取后继结点的地址const Node<T>* NextNode()const{ return next; }                              //获取后继结点的地址~Node(){}};template <class T>class LinkedList {private:// 数据成员：Node<T> *front, *rear;      // 表头和表尾指针Node<T> *prevPtr, *currPtr; // 记录表当前遍历位置的指针，由插入和删除操作更新int size;                   // 表中的元素个数int position;               // 当前元素在表中的位置序号。由函数 Reset 使用// 函数成员：// 生成新结点，数据域为 item，指针域为 ptrNextNode<T>* NewNode(const T &item, Node<T> *ptrNext = NULL){Node<T> *newNode;newNode = new Node<T>(item, ptrNext);if (newNode == NULL) {cerr << "Memory allocation failure!" << endl;exit(1);}return newNode;}// 释放结点void FreeNode(Node<T> *p){delete p;}// 将链表 L 拷贝到当前表（假设当前表为空）。// 被复制构造函数和“operator =”调用void Copy(const LinkedList<T> &L){if (L.size == 0)return;front = rear = NewNode(L.front->Data);for (Node<T> *srcNode = L.front->NextNode();srcNode != NULL;srcNode = srcNode->NextNode()){Node<T> *newNode = NewNode(srcNode->Data);rear->InsertAfter(newNode);rear = newNode;}size = L.size;Reset(position = L.CurrentPosition());}public://默认构造函数-空LinkedList(void): front(NULL), rear(NULL), prevPtr(NULL), currPtr(NULL), size(0), position(0){}LinkedList(const LinkedList<T> &L) : front(NULL), rear(NULL), prevPtr(NULL), currPtr(NULL), size(0), position(0){Copy(L);}//复制构造函数~LinkedList(void){//析构函数Clear();}LinkedList<T>& operator =(const LinkedList<T> &L){ // 重载赋值运算符Clear();Copy(L);return *this;}int GetSize(void) const{            // 返回链表中元素个数return size;}bool IsEmpty(void) const{           // 链表是否为空return (size == 0);}/**@brief初始化游标的位置@parampos从零计起的位置编号@notepos 无限制当 pos 在 0 和 size 之间时，prevPtr 和 currPtr 正常指示;当 pos 为 0 时，prevPtr = NULL, currPtr = front;当 pos 为 size 时，prevPtr = rear, currPtr = NULL;当 pos 取其他值时，prevPtr = currPtr = NULL。*/void Reset(int pos = 0){            // 初始化游标的位置if (0 <= pos && pos <= size) {position = 0;prevPtr = NULL;currPtr = front;// 游标回到头结点，再逐步前移while (pos--)Next();}else {position = pos;prevPtr = NULL;currPtr = NULL;}}void Next(void){                    // 使游标移动到下一个结点position++;prevPtr = currPtr;if (currPtr != NULL)currPtr = currPtr->NextNode();}/**@brief游标是否到了链尾@return游标是否到了链尾游标“到了链尾”意即游标“超出了链表”，当游标所示的当前结点不存在时即判断到了链尾。*/bool EndOfList(void) const{     return (currPtr == NULL);}/**@brief返回游标当前的位置@return从零计起的位置编号@note游标可以在链表之外*/int CurrentPosition(void) const{   return position;}void InsertFront(const T &item){    // 在表头插入结点front = NewNode(item, front);if (IsEmpty())rear = front;size++;Reset(++position);}void InsertRear(const T &item){     // 在表尾插入结点Node<T> *newNode = NewNode(item);if (IsEmpty()) {front = rear = newNode;}else {rear->InsertAfter(newNode);rear = newNode;}size++;Reset(position);}/**@brief在当前结点之前插入结点@paramitem新结点的数据域@note只考虑当前位置的结点存在的情况*/void InsertBefore(const T &item){  if (currPtr != NULL) {Node<T> *newNode = GetNode(item, currPtr);if (prevPtr != NULL)prevPtr->InsertAfter(newNode);elsefront = prevPtr = newNode;size++;Reset(++position);}}/**@brief在当前结点之后插入结点@paramitem新结点的数据域@note只考虑当前位置的结点存在的情况*/void InsertAfter(const T &item){    if (currPtr != NULL) {Node<T> *newNode = NewNode(item, currPtr->NextNode());currPtr->InsertAfter(newNode);if (rear == currPtr)rear = newNode;size++;}}T DeleteFront(void){                // 删除头结点if (IsEmpty()) {cerr << "List is empty, delete error." << endl;exit(1);}Node<T> *delNode = front;front = front->NextNode();if (--size == 0)rear = NULL;Reset(--position);T item = delNode->data;FreeNode(delNode);return item;}void DeleteCurrent(void){           // 删除当前结点if (currPtr != NULL) {if (front == currPtr)front = currPtr->NextNode();if (rear == currPtr)rear = prevPtr;if (prevPtr != NULL)prevPtr->DeleteAfter();FreeNode(currPtr);size--;Reset(position);}}T& Data(void){                      // 返回对当前结点成员数据的引用if (currPtr == NULL) {cerr << "Current node is invalid." << endl;exit(1);}return currPtr->data;}const T& Data(void) const{          // 返回对当前结点成员数据的常引用if (currPtr == NULL) {cerr << "Current node is invalid." << endl;exit(1);}return currPtr->data;}// 清空链表：释放所有结点的内存空间。被析构函数和“operator =”调用void Clear(void){while (!IsEmpty())DeleteFront();}};int main(){LinkedList<int> linklist;for (int i = 0; i < 10; i++){int x;cin >> x;linklist.InsertFront(x);}linklist.Reset(0);while (!linklist.EndOfList()){cout << linklist.Data() << endl;linklist.Next();}cout << endl;return 0;}