#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){ //在本结点之后出入一个同类结点P
p->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,指针域为 ptrNext
Node<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 初始化游标的位置
@param pos 从零计起的位置编号
@note pos 无限制
当 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 在当前结点之前插入结点
@param item 新结点的数据域
@note 只考虑当前位置的结点存在的情况
*/
void InsertBefore(const T &item){
if (currPtr != NULL) {
Node<T> *newNode = GetNode(item, currPtr);
if (prevPtr != NULL)
prevPtr->InsertAfter(newNode);
else
front = prevPtr = newNode;
size++;
Reset(++position);
}
}
/**
@brief 在当前结点之后插入结点
@param item 新结点的数据域
@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;
}
分享到:
相关推荐
链表类 c++ 实现的 链表类 c++ 实现的 链表类 c++ 实现的
一种支持类模版和函数模版的C++双向链表,实现了各种排序算法(排序原则可定制),包含学生信息的使用示例(VC 6.0、VS2008).
C++链表类 模板类 #include #include #include "LinkedList.h" using namespace std; template Node<T> *LinkedList<T>::GetNode(const T& item, Node* ptrNext) //生成新结点 { Node<T> *p; p = new Node...
一个抽象链表类的C++模板实现,主要适合初学者入门数据结构基础。
1. 请创建一个数据类型为T的链表类模板List,实现以下成员函数: 1) 默认构造函数List(),将该链表初始化为一个空链表(10分) 2) 拷贝构造函数List(const List<T>& list),根据一个给定的链表构造当前链表(10...
C++实现链表模板(链表项的数据元素可以为任意类型):链表项的插入、删除、链表的打印、两个链表的连接 开发环境为VS2010
C++实现的模板链表类,没有用到STL的list,是用指针实现的。
使用C++做的双链表模板类 具有头插法,尾插法,左向插入,右向插入,删除结点,获取结点值,设置结点值,复制构造函数,还重载了输出操作符、赋值操作符、相等操作符和不等操作符,还具有倒置链表的功能。还有结点类...
用模板类实现了一个简单的双向链表domo。
此代码是我收集的用C++实现双向链表模板类。
此代码是我收集的用C++实现单向链表模板类。
体验用面向对象的方法操作数组和动态链表 了解C++标准类和标准模板库
c++,类、模板、链表的简单使用,包括入链表、出链表等等
C++的模版类,实现了链表的基本功能,添删改查。
C++手动实现带头结点的单链表类,测试环境为Visual Studio 2010
C++链表类模版 //构造函数 //创建n个元素的列表 //拷贝构造 //释放链表 //析构函数(虚) //输出链表 //用t替换掉当前结点内容 //重载赋值运算符= //获取当前链表的长度或结点数 // 当前结点位置:第 n (从 0 起)...
c++模板实现双向链表操作如逆序建立双向链表,插入结点等。
单向链表操作类模板实现代码,代码内包含结点类、链表操作类的实现以及主测试函数等;其中链表操作包含结点插入、删除、获取等;
基本功能完备 代码结构清晰易懂 适合初学者
利用标准C++的语言,实现封装链表模板类,即List模板类