C++骨干数据结构:链表(list)

基本数据结构:链表(list)

笔者:C小加 更新时间:2012-7-31

  说到链表之前,先说一样生线性表。线性表是无比基本、最简便易行、也是无限常用之一律种植数据结构。线性表中数据元素中的关联是一定之关联,即除去第一单及最后一个数额元素之外,其它数据元素还是首尾相接的。线性表来一定量栽存储方,一栽是顺序存储结构,另一样种植是链式存储结构。

  顺序存储结构即是片只相邻之要素在内存中也是相邻的。这种囤方的助益是询问的时间复杂度为O(1),通过首地址与偏移量就足以直接访问到某某元素,关于寻找的适配算法很多,最抢得达到O(logn)。缺点是插和去的光阴复杂度最可怜能及O(n),如果你当首先个职务插入一个素,你得拿数组的诸一个要素于后动一各,如果你当率先独岗位去一个素,你要拿数组的各个一个因素向前移动一号。还有一个欠缺,就是当你切莫确定因素的数据时,你从头的数组必须确保能放下元素最充分数目,遗憾之是使实在数目比最要命数据少多时时,你从头之数组没有使用的内存就不得不浪费掉了。

  我们常常因此底数组就是同等栽典型的顺序存储结构,如图1。

C++ 1

链式存储结构即是有限个相邻之素以内存中或未是附近的,每一个要素都生一个因针域,指针域一般是储存方到下一个素的指针。这种囤方的优点是插和去的年华复杂度为O(1),不见面浪费最多内存,添加元素的时段才见面申请内存,删除元素会释放内存,。缺点是看的时复杂度最深为O(n),关于寻找的算法很少,一般只能遍历,这样时间复杂度也是线性(O(n))的了,频繁之报名及刑满释放内存为会见吃时间。

顺序表的表征是自由读取,也便是看一个素的时光复杂度是O(1),链式表的特点是插和去的流年复杂度为O(1)。要基于实际情况去挑选适合自己之蕴藏结构。

链表就是链式存储的线性表。根据指针域的不同,链表分为单为链表、双向链表、循环链表等等。

相同、 单向链表(slist)

链表中最为简单易行的一律种是一味为链表,每个元素包含两只地方,值域和指针域,我们管这样的素称之为节点。每个节点的指针域内发出一个指针,指向下一个节点,而结尾一个节点则对一个空值。如图2虽是一个单为链表。

C++ 2

一个止为链表的节点被分为两个组成部分。第一单部分保存还是显示关于节点的音,第二只有存储下一个节点的地点。单为链表只可通往一个趋势遍历。

自身形容了一个简单易行的C++版单向链表类模板,就因此当下段代码讲解一下一个现实的只是为链表该怎么写(代码仅供上),当然首先你如果持有C++基础知识和概括的沙盘元编程。
完全代码

先是我们若描绘一个节点类,链表中的诸一个节点就是一个节点类的对象。如图3。

C++ 3

代码如下:

template<class T>
class slistNode
{
    public:
    slistNode(){next=NULL;}//初始化
    T data;//值
    slistNode* next;//指向下一个节点的指针
};

 

老二步,写单链表类的宣示,包括属性和法。

代码如下:

template<class T>
class myslist
{
    private:
    unsigned int listlength;
    slistNode<T>* node;//临时节点
    slistNode<T>* lastnode;//头结点
    slistNode<T>* headnode;//尾节点
    public:
        myslist();//初始化
        unsigned int length();//链表元素的个数
        void add(T x);//表尾添加元素
        void traversal();//遍历整个链表并打印
        bool isEmpty();//判断链表是否为空
        slistNode<T>* find(T x);//查找第一个值为x的节点,返回节点的地址,找不到返回NULL
        void Delete(T x);//删除第一个值为x的节点
        void insert(T x,slistNode<T>* p);//在p节点后插入值为x的节点
        void insertHead(T x);//在链表的头部插入节点
};

 

 

老三步,写构造函数,初始化链表类的属性。

代码如下:

template<class T>
myslist<T>::myslist()
{
    node=NULL;
    lastnode=NULL;
    headnode=NULL;
    listlength=0;
}

 

第四步,实现add()方法。

代码如下:

template<class T>
void  myslist<T>::add(T x)
{
    node=new slistNode<T>();//申请一个新的节点
    node->data=x;//新节点赋值为x
    if(lastnode==NULL)//如果没有尾节点则链表为空,node既为头结点,又是尾节点
    {
        headnode=node;
        lastnode=node;
    }
    else//如果链表非空
    {
        lastnode->next=node;//node既为尾节点的下一个节点
        lastnode=node;//node变成了尾节点,把尾节点赋值为node
    }
    ++listlength;//元素个数+1
}

 

第五步,实现traversal()函数,遍历并出口节点信息。

代码如下:

template<class T>
void  myslist<T>::traversal()
{
    node=headnode;//用临时节点指向头结点
    while(node!=NULL)//遍历链表并输出
    {
        cout<<node->data<<ends;
        node=node->next;
    }
    cout<<endl;
}

 

第六步,实现isEmpty()函数,判断链表是否为空,返回真为空,假则无拖欠。

代码如下:

template<class T>
bool  myslist<T>::isEmpty()
{
    return listlength==0;
}

 

第七步,实现find()函数。

代码如下:

template<class T>
slistNode<T>* myslist<T>::find(T x)
{
    node=headnode;//用临时节点指向头结点
    while(node!=NULL&&node->data!=x)//遍历链表,遇到值相同的节点跳出
    {
        node=node->next;
    }
    return node;//返回找到的节点的地址,如果没有找到则返回NULL
}

 

第八步,实现delete()函数,删除第一个值为x的节点,如图4。

C++ 4

代码如下:

template<class T>
void  myslist<T>::Delete(T x)
{
    slistNode<T>* temp=headnode;//申请一个临时节点指向头节点
    if(temp==NULL) return;//如果头节点为空,则该链表无元素,直接返回
    if(temp->data==x)//如果头节点的值为要删除的值,则删除投节点
    {
        headnode=temp->next;//把头节点指向头节点的下一个节点
        if(temp->next==NULL) lastnode=NULL;//如果链表中只有一个节点,删除之后就没有节点了,把尾节点置为空
        delete(temp);//删除头节点
        return;
    }
    while(temp->next!=NULL&&temp->next->data!=x)//遍历链表找到第一个值与x相等的节点,temp表示这个节点的上一个节点
    {
        temp=temp->next;
    }
    if(temp->next==NULL) return;//如果没有找到则返回
    if(temp->next==lastnode)//如果找到的时候尾节点
    {
        lastnode=temp;//把尾节点指向他的上一个节点
        delete(temp->next);//删除尾节点
        temp->next=NULL;
    }
    else//如果不是尾节点,如图4
    {
        node=temp->next;//用临时节点node指向要删除的节点
        temp->next=node->next;//要删除的节点的上一个节点指向要删除节点的下一个节点
        delete(node);//删除节点
        node=NULL;
    }
}

 

第九步,实现insert()和insertHead()函数,在p节点后插入值为x的节点。如图5。

C++ 5

 

代码如下:

template<class T>
void  myslist<T>::insert(T x,slistNode<T>* p)
{
    if(p==NULL) return;
    node=new slistNode<T>();//申请一个新的空间
    node->data=x;//如图5
    node->next=p->next;
    p->next=node;
    if(node->next==NULL)//如果node为尾节点
    lastnode=node;
}
template<class T>
void  myslist<T>::insertHead(T x)
{
    node=new slistNode<T>();
    node->data=x;
    node->next=headnode;
    headnode=node;
}

 

 

说到底,我们得一个简单易行的单独为链表。此才为链表代码还有为数不少亟需到之地方,以后会改代码并无定时更新。

仲、 双向链表

双向链表的指针域有三三两两单指针,每个数据结点分别针对直接后继和一直前驱。单为链表只能于表头开始往后遍历,而双向链表不但可以往于后遍历,也得以自晚迈入遍历。除了双向遍历的长,双向链表的删减的时间复杂度会跌为O(1),因为直接通过目的指针就得找到前驱节点,单为链表得打表头开始遍历寻找前驱节点。缺点是每个节点多了一个指针的空中开发。如图6就是一个双向链表。

C++ 6

老三、 循环链表

循环链表就是受链表的末梢一个节点指向第一独节点,这样就算形成了一个圆环,可以循环遍历。单为循环链表可以一边循环遍历,双向循环链表的头节点的指针也只要指向最后一个节点,这样的可以双向循环遍历。如图7就是一个双向循环链表。

C++ 7

 

季、 链表相关题材

1、如何判定一个单链表有环

  2、如何判定一个缠C++之入口点在乌

  3、如何理解环之长

  4、如何晓得少独单链表(无环)是否相交

  5、如果个别单单链表(无环)相交,如何理解她相交的第一独节点是什么

  6、如何晓得少个单链表(有环)是否相交

  7、如果少独单链表(有环)相交,如何知道它们相交的第一单节点是什么

       答案