中山大学黎培兴C++语言程序设计ppt

#include <iostream.h> #include <stdlib.h> #include "9_6.h" template <class T> Node<T> *LinkedList<T>::GetNode(const T& item, Node<T>* ptrNext) { Node<T> *p; p = new Node<T>(item,ptrNext); if (p == NULL) { cout << "Memory allocation failure!\n"; exit(1); } return p; } template <class T> void LinkedList<T>::FreeNode(Node<T> *p) { delete p; } //将L复制到当前链表 template <class T> void LinkedList<T>::CopyList(const LinkedList<T>& L) { //P用来遍历L Node<T> *p = L.front; int pos; //将L中的每一个元素插入到当前链表最后 while (p != NULL) { 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,position为-1 template <class T> LinkedList<T>::LinkedList(void): 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; CopyList(L); } template <class T> void LinkedList<T>::ClearList(void) { Node<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; } template <class T> LinkedList<T>::~LinkedList(void) { ClearList(); } template <class T> LinkedList<T>& LinkedList<T>::operator= (const LinkedList<T>& L) { if (this == &L) // 不能将链表赋值给它自身 return *this; ClearList(); CopyList(L); return *this; } template <class T> int LinkedList<T>::ListSize(void) const { return size; } template <class T> int LinkedList<T>::ListEmpty(void) const { return size == 0; } //将prevPtr和currPtr向前移动一个结点 template <class T> void LinkedList<T>::Next(void) { // if traversal has reached the end of the list or // the list is empty, just return if (currPtr != NULL) { // advance the two pointers one node forward prevPtr = currPtr; currPtr = currPtr->NextNode(); position++; } } // 如果已经遍历完链表则返回True template <class T> int LinkedList<T>::EndOfList(void) const { return currPtr == NULL; } // 返回当前结点的位置 template <class T> int LinkedList<T>::CurrentPosition(void) const { return position; } //将链表当前位置设置为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) { // 将指针重新设置到表头 prevPtr = NULL; currPtr = front; position = 0; } else // 重新设置 currPtr, prevPtr, 和 position { currPtr = front->NextNode(); prevPtr = front; startPos = 1; //移动指针直到 position == pos for(position=startPos; position != pos; position++) { // 向前移动遍历指针 prevPtr = currPtr; currPtr = currPtr->NextNode(); } } } //返回一个当前结点数值的引用 template <class T> T& LinkedList<T>::Data(void) { // 如果链表为空或已经完成遍历则出错 if (size == 0 || currPtr == NULL) { cerr << "Data: invalid reference!" << endl; exit(1); } return currPtr->data; } // 将item插入在表头 template <class T> void LinkedList<T>::InsertFront(const T& item) { // 如果链表不空则调用Reset if (front != NULL) Reset(); InsertAt(item); // 在表头插入 } // 在表尾插入 template <class T> void LinkedList<T>::InsertRear(const T& item) { Node<T> *newNode; prevPtr = rear; newNode = GetNode(item); // 创建新结点 if (rear == NULL) // 如果表空则插入在表头 front = rear = newNode; else { rear->InsertAfter(newNode); rear = newNode; } currPtr = rear; position = size; size++; } // 将item插入在链表当前位置 template <class T> void LinkedList<T>::InsertAt(const T& item) { Node<T> *newNode; // 两种情况: 插入在链表头或链表之中 if (prevPtr == NULL) { // 插入在链表头，包括将结点插入到空表中 newNode = GetNode(item,front); front = newNode; } else { // 插入到链表之中. 将结点置于prevPtr之后 newNode = GetNode(item); prevPtr->InsertAfter(newNode); } // 如果prevPtr == rear, 说明正在向空表中插入， // 或者是插入到非空表的表尾；更新rear 和 position if (prevPtr == rear) { rear = newNode; position = size; } //更新currPtr并且使size增值 currPtr = newNode; size++; } // 将item 插入到链表当前位置之后 template <class T> void LinkedList<T>::InsertAfter(const T& item) { Node<T> *p; p = GetNode(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(void) { T item; Reset(); if (front == NULL) { cerr << "Invalid deletion!" << endl; exit(1); } item = currPtr->data; DeleteAt(); return item; } // 删除链表当前位置的结点 template <class T> void LinkedList<T>::DeleteAt(void) { Node<T> *p; // 如果表空或达到表尾则出错 if (currPtr == NULL) { cerr << "Invalid deletion!" << endl; exit(1); } // 删除将发生在表头或链表之中 if (prevPtr == NULL) { // 保存头结点地址并将其从链表中分离。 p = front; front = front->NextNode(); } else // 分离prevPtr之后的一个内部结点. 保存其地址 p = prevPtr->DeleteAfter(); // 如果表尾结点被删除, 则新的表尾是prevPtr 并且position自减； // 否则position不变 if (p == rear) { rear = prevPtr; position--; } // 使currPtr越过被删除的结点 currPtr = p->NextNode(); // 释放结点，并使链表长度自减 FreeNode(p); size--; }