链表的概念与结点类模板
顺序访问的线性群体——链表类
-
链表是一种动态数据结构，可以用来表示顺序访问的线性群体。
-
链表是由系列 结点 组成的，结点可以在运行时动态生成。
-
每一个结点包括 数据域 和指向链表中下一个结点的 指针 （即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。
例9-5 结点类模板
Node<T> 相当于int等数据类型
//Node.h
#ifndef NODE_H
#define NODE_H
//类模板的定义
template <class T>
class Node {
private: Node<T> *next; //指向后继结点的指针
public: T data; //数据域 Node (const T &data, Node<T> *next = 0); //构造函数 void insertAfter(Node<T> *p); //在本结点之后插入一个同类结点p Node<T> *deleteAfter(); //删除本结点的后继结点，并返回其地址 Node<T> *nextNode(); //获取后继结点的地址 const Node<T> *nextNode() const; //获取后继结点的地址
};
//类的实现部分
//构造函数，初始化数据和指针成员
template <class T>
Node<T>::Node(const T& data, Node<T> *next = 0 ) : data(data), next(next) { }
//返回后继结点的指针
template <class T>
Node<T> *Node<T>::nextNode() { return next;
}
//返回后继结点的指针
template <class T>
const Node<T> *Node<T>::nextNode() const { return next;
}
//在当前结点之后插入一个结点p
template <class T>
void Node<T>::insertAfter(Node<T> *p) { p->next = next; //p结点指针域指向当前结点的后继结点 next = p; //当前结点的指针域指向p
}
//删除当前结点的后继结点，并返回其地址
template <class T> Node<T> *Node<T>::deleteAfter() { Node<T> *tempPtr = next;//将欲删除的结点地址存储到tempPtr中 if (next == 0) //如果当前结点没有后继结点，则返回空指针 return 0; next = tempPtr->next;//使当前结点的指针域指向tempPtr的后继结点 return tempPtr; //返回被删除的结点的地址
}
#endif //NODE_H 链表的基本操作
-
生成链表
-
插入结点
-
查找结点
-
删除结点
-
遍历链表
-
清空链表
例9-6 链表类模板
//LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "Node.h"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);//释放结点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(); //删除当前结点T& data(); //返回对当前结点成员数据的引用const T& data() const; //返回对当前结点成员数据的常引用//清空链表：释放所有结点的内存空间。被析构函数、operator= 调用void clear();
};template <class T> //生成新结点
Node<T> *LinkedList<T>::newNode(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;
}template <class T>
void LinkedList<T>::copy(const LinkedList<T>& L) //链表复制函数
{Node<T> *p = L.front; //P用来遍历L int pos;while (p != NULL) //将L中的每一个元素插入到当前链表最后{insertRear(p->data);p = p->nextNode();}if (position == -1) //如果链表空,返回return;//在新链表中重新设置prevPtr和currPtrprevPtr = NULL;currPtr = front;for (pos = 0; pos != position; pos++){prevPtr = currPtr;currPtr = currPtr->nextNode();}
}template <class T> //构造一个新链表，将有关指针设置为空，size为0，position为-1
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;
}template <class T>
void LinkedList<T>::reset(int pos) //将链表当前位置设置为pos
{int startPos;if (front == NULL) // 如果链表为空，返回return;if (pos < 0 || pos > size - 1) // 如果指定位置不合法，中止程序{std::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();}}
}template <class T>
void LinkedList<T>::next() //将prevPtr和currPtr向前移动一个结点
{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;
}template <class T>
void LinkedList<T>::insertFront(const T& item) // 将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++;
}template <class T>
void LinkedList<T>::insertAt(const T& item) // 将item插入在链表当前位置
{Node<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; //更新currPtrsize++; //使size增值
}template <class T>
void LinkedList<T>::insertAfter(const T& item) // 将item 插入到链表当前位置之后
{Node<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;}elseposition++;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() // 删除链表当前位置的结点
{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();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() //清空链表
{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;
}
#endif //LINKEDLIST_H例 9-7 链表类应用举例
从键盘输入10个整数，用这些整数值作为结点数据，生成一个链表，按顺序输出链表中 结点的数值。然后从键盘输入一个待查找整数，在链表中查找该整数，若找到则删除该整 数所在的结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在程序结束 之前清空链表。
//9_7.cpp
#include <iostream>
#include "LinkedList.h"
using namespace std;
int main() {LinkedList<int> list;for (int i = 0; i < 10; i++) {int item;cin >> item;list.insertFront(item);}cout << "List: ";list.reset();while (!list.endOfList()) {cout << list.data() << " ";list.next();}cout << endl;int key;cout << "Please enter some integer needed to be deleted: ";cin >> key;list.reset();while (!list.endOfList()) {if (list.data() == key)list.deleteCurrent();list.next();}cout << "List: ";list.reset();while (!list.endOfList()) {cout << list.data() << " ";list.next();}cout << endl;return 0;
} 运行结果：
10 9 8 7 6 5 4 3 2 1
List: 1 2 3 4 5 6 7 8 9 10 
