单链表的C++实现（采用模板类）

链表结构定义

定义单链表的结构可以有4方式。如代码所示。

本文采用的是第4种结构类型

/*************************************************************************

1、复合类：在Node类中定义友元的方式，使List类可以访问结点的私有成员

*************************************************************************/

classLinkNode

{

friendclassLinkList;

private:

intdata;

LinkNode*next;

};

classLinkList

{

public:

//单链表具体操作

private:

LinkNode*head;

};

/*************************************************************************

2、嵌套类：在List内部定义Node类，但是Node的数据成员放在public部分，使List

和Node均可以直接访问Node的成员

*************************************************************************/

classLinkList

{

public:

//单链表具体操作

private:

classLinkNode

{

public:

intdata;

LinkNode*next;

};

LinkNode*head;

};

/*************************************************************************

3、继承：在Node类中把成员定义为protected，然后让List继承Node类，这样就可以

访问Node类的成员了。

*************************************************************************/

classLinkNode

{

protected:

intdata;

LinkNode*next;

};

classLinkList:publicLinkNode

{

public:

//单链表具体操作

private:

LinkNode*head;

};

/*************************************************************************

4、直接用struct定义Node类，因为struct的成员默认为公有数据成员，所以可直接

访问（struct也可以指定保护类型）。

*************************************************************************/

structLinkNode

{

intdata;

LinkNode*next;

};

classLinkList

{

public:

//单链表具体操作

private:

LinkNode*head;

};

单链表的模板类定义

使用模板类需要注意的一点是template<class T>必须定义在同一个文件，否则编译器会无法识别。

如果在.h中声明类函数，但是在.cpp中定义函数具体实现， 会出错。所以，推荐的方式是直接在.h中定义。

/*单链表的结点定义*/

template<classT>

structLinkNode

{

Tdata;

LinkNode<T>*next;

LinkNode(LinkNode<T>*ptr=NULL){next=ptr;}

LinkNode(constT&item,LinkNode<T>*ptr=NULL)

//函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面

{

next=ptr;

data=item;

}

};

/*带头结点的单链表定义*/

template<classT>

classLinkList

{

public:

//无参数的构造函数

LinkList(){head=newLinkNode<T>;}

//带参数的构造函数

LinkList(constT&item){head=newLinkNode<T>(item);}

//拷贝构造函数

LinkList(LinkList<T>&List);

//析构函数

~LinkList(){Clear();}

//重载函数:赋值

LinkList<T>&operator=(LinkList<T>&List);

//链表清空

voidClear();

//获取链表长度

intLength()const;

//获取链表头结点

LinkNode<T>*GetHead()const;

//设置链表头结点

voidSetHead(LinkNode<T>*p);

//查找数据的位置，返回第一个找到的满足该数值的结点指针

LinkNode<T>*Find(T&item);

//定位指定的位置，返回该位置上的结点指针

LinkNode<T>*Locate(intpos);

//在指定位置pos插入值为item的结点，失败返回false

boolInsert(T&item,intpos);

//删除指定位置pos上的结点，item就是该结点的值，失败返回false

boolRemove(intpos,T&item);

//获取指定位置pos的结点的值，失败返回false

boolGetData(intpos,T&item);

//设置指定位置pos的结点的值，失败返回false

boolSetData(intpos,T&item);

//判断链表是否为空

boolIsEmpty()const;

//打印链表

voidPrint()const;

//链表排序

voidSort();

//链表逆置

voidReverse();

private:

LinkNode<T>*head;

};

定位位置

/* 返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL */
template<class T>
LinkNode<T>* LinkList<T>::Locate(int pos)
{
    int i = 0;
    LinkNode<T> *p = head;
    if (pos < 0)
        return NULL;
    while (NULL != p && i < pos)
    {
        p = p->next;
        i++;
    }
    
    return p;
}

插入结点

单链表插入结点的处理如图

图：单链表插入操作

要在p结点后插入一个新结点node，（1）要让node的next指针指向p的next结点；（2）再让p的next指向node结点（即断开图中的黑色实线，改成红色虚线指向node）

接下来：node->next = p->next;p->next = node;

template<class T>
bool LinkList<T>::Insert(T &item, int pos)
{
    LinkNode<T> *p = Locate(pos);
    if (NULL == p)
        return false;
    LinkNode<T> *node = new LinkNode<T>(item);
    if (NULL == node)
    {
        cerr << "分配内存失败!" << endl;
        exit(1);
    }
    node->next = p->next;
    p->next = node;
    return true;
}

删除结点

删除结点的处理如图：

图：单链表删除

删除pos位置的结点，如果这个位置不存在结点，则返回false；

如果找到对应结点，则通过实参item输出要删除的结点的数值， 然后删除结点并返回true。

template<class T>
bool LinkList<T>::Remove(int pos, T &item)
{
    LinkNode<T> *p = Locate(pos);
    if (NULL == p || NULL == p->next)
        return false;
    LinkNode<T> *del = p->next;
    p->next = del->next;
    item = del->data;
    delete del;
    return true;
}

清空链表

遍历整个链表，每次head结点的next指针指向的结点，直到next指针为空。

最后保留head结点。

template<class T>
void LinkList<T>::Clear()
{
    LinkNode<T> *p = NULL;
    //遍历链表，每次都删除头结点的next结点，最后保留头结点
    while (NULL != head->next)
    {
        p = head->next;
        head->next = p->next;   //每次都删除头结点的next结点
        delete p;
    }
}

求链表长度和打印链表

着两个功能的实现非常相近，都是遍历链表结点用模板实现链表，不赘述。

template<class T>
void LinkList<T>::Print() const
{
    int count = 0;
    LinkNode<T> *p = head;
    while (NULL != p->next)
    {
        p = p->next;
        std::cout << p->data << " ";
        if (++count % 10 == 0)  //每隔十个元素，换行打印
            cout << std::endl;
    }
}
template<class T>
int LinkList<T>::Length() const
{
    int count = 0;
    LinkNode<T> *p = head->next;
    while (NULL != p)
    {
        p = p->next;
        ++count;
    }
    return count;
} 

单链表倒置

单链表的倒置处理如图：

图：单链表倒置

# 2: [head]->[next]->node->node->...->node->[prev]->[tail]。# 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail]。curr=curr->next)。

（2）让链表的第一个结点的next指针指向空

initlist 初始化循环链表,开辟一个空间作为头结点,并让l l- next先让它指向自己,令链表循环起来. listinsert 向循环链表里面插入数据 包括编号和密码 , displist 以定义的头结点为第一个数,输出循环链表.josephus 主要用于解决约瑟夫环问题,首先调用initlist 建立循环链表,再调用listinsert 插入数据,再调用displist 把储存的数据输出来.定义两个指针s和q,再定义count作为计数器,此时需要任意输入一个正整数x作为初始报数上限值,当计数器count x时就把该指针所指向的数据输出并把该数据赋给x,作为新的报数上限值.然后删除该结点,s和q的主要作用是在把输出数据之后的结点删除.如此循环,直到还剩最后一个结点,同时定义a[i],b[i]用来储存编号和密码。循环双链表的构造源自双链表，即将终端结点的nnext指针指向链表中第一个结点，将链表中第一个结点的prior指针指向终端结点。循环单链表终端结点的next结点指针指向表头结点。

（4）让prev、curr结点都继续向后移位。即：prev = curr; curr = next;

（2）、输出单循环链表模块：先判断表是否为空，若不空则输出结点信息用模板实现链表，同时指针向后移，指向下一结点，继续输出直到指针再次指向头结点为止，输出完毕。while循环语句里的for循环实现报数功能，设指针pprv和指针pcur，移动结点到ikey,再删除第ikey个结点并把该结点的key值赋给ikey，再从该结点的下一个结点开始移动，重复上述过程，直到结点全部出列。循环双链表的构造源自双链表，即将终端结点的nnext指针指向链表中第一个结点，将链表中第一个结点的prior指针指向终端结点。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-112102-1.html