数据结构与算法学习第1季02 链表的基本功能 C++实现

浏览数：21 / 时间：2015年06月08日

2015年学习计划安排：

尝试用C++实现了双向链表类LinkList，基本功能是在位置i插入结点和删除位置i的结点。

首先是结点类，每个结点有数据data，指向前一个结点的指针front和指向后一个结点的指针next

class Node
{
public:
    int data;
    Node* next;
    Node* front;
public:
    Node();
    Node(int data);
    Node(int data, Node* nextPtr, Node* frontPtr);
};

结点类的实现：

#include "stdafx.h"
#include "Node.h"

Node::Node()
{
    this->data = 0;
    this->next = NULL;
    this->front = NULL;
}

Node::Node(int data)
{
    this->data = data;
    this->next = NULL;
    this->front = NULL;
}

Node::Node(int data, Node* nextPtr, Node* frontPtr)
{
    this->data = data;
    this->next = nextPtr;
    this->front = frontPtr;
}

双向链表类的实现

#include "Node.h"

class LinkList
{
public:
    int length;
    Node headNode;
    Node rearNode;

public:
    LinkList();
    bool IsLinkListEmpty();
    void Display(int mode);
    void InsertNode(int i, int data);
    void DeleteNode(int i);
};

初始化空链表，注意headNode和rearNode会分别调用Node类的无参的构造方法。

LinkList::LinkList()
{
    this->length = 0;
    this->headNode.next = &(this->rearNode);
    this->rearNode.front = &(this->headNode);
}

如果想显示调用Node类的有参的构造方法，需要用初始化列表的方式来给headNode和rearNode初始化。

LinkList::LinkList():headNode(10),rearNode(10)
{
    this->length = 0;
    this->headNode.next = &(this->rearNode);
    this->rearNode.front = &(this->headNode);
}

当然头结点和尾结点的数据是没有意义的，实际上我们只需要用到头结点的next和尾结点的front，不过为了统一操作，将单纯一个指针扩为一个结点。

双向链表中结点的数量为length，不包括头尾结点。

判断链表是否为空。

bool LinkList::IsLinkListEmpty()
{
    if(this->length==0)
    {
        return true;
    }
    return false;
}

在控制台输出链表，可以选择反向输出。

void LinkList::Display(int mode)
{
    if (mode == 0)
    {
        Node* ptr = this->headNode.next;
        for (int i = 0; i < this->length; i++)
        {
            std::cout<<ptr->data<<std::endl;
            ptr = ptr->next;
        }
    } 
    else
    {
        Node* ptr = this->rearNode.front;
        for (int i = 0; i < this->length; i++)
        {
            std::cout<<ptr->data<<std::endl;
            ptr = ptr->front;
        }
    }
    return;
}

规律是，ptr一开始是头结点的指针域，那么，执行i次

ptr = ptr->next;

ptr指向的结点在链表中的位置就是i（注意i从0开始计算，一次都不执行自然就是指向结点0---当然也可能是指向尾结点，如果链表为空）

在位置i插入结点，即插入的结点在链表的位置为i。

void LinkList::InsertNode(int i, int data)
{
    if ( (i > this->length) || (i < 0) )
    {
        std::cout<<"Error!!!!!!!!!"<<std::endl;
    } 
    else
    {
        Node* temp = new Node(data);
        Node* ptr = this->headNode.next;
        for (int k = 0; k < i; k++)
        {
            ptr = ptr->next;
        }

        temp->next = ptr;
        temp->front = ptr->front;
        
        ptr->front = temp;
        temp->front->next = temp;

        this->length++;
    }
    return;
}

首先判断位置i是否合法。对于一个长度为length的链表，各结点（不含头尾结点）的位置是0，1，...，length-1，合法的插入位置是0，1，...，length。

接下来是找到链表中的某next指针，其指向的结点是原链表中的结点i。即 ptr: Node i-1 -> Node i，当i=0时，Node i-1是头结点。当i=length时，Node i是尾结点。

Node* ptr = this->headNode.next;
for (int k = 0; k < i; k++)
{
      ptr = ptr->next;
}

上述代码实现了这个功能。特别地，当i=0时，循环体一次都没有执行，ptr: Head Node -> Node 0，当i=length时，循环体执行了length+1次，ptr: Node i -> Rear Node。

然后，生成一个新的结点，其（指向它的）指针为temp：

 Node* temp = new Node(data);

这个结点是要插入的结点，所以其位置应该为i，因此它的next应该指向原来链表中的结点i，而原来链表中的结点i的地址，正是ptr：

temp->next = ptr;

而这个新结点的front应该指向原来链表中的结点i-1，而原来链表中的结点i-1的地址，是ptr->front。（ptr现在指向的是原链表的结点i，原链表的结点i的front则指向原链表的结点i-1）：

temp->front = ptr->front;

然后，原链表的结点i的front，应该指向这个新结点，这个新结点的地址是temp。（ptr现在指向的是原链表的结点i，这个结点的front应该由指向原链表的结点i-1变为指向新结点）：

ptr->front = temp;

接下来，原链表的结点i-1的next，也应该指向这个新结点。（temp的front现在就是指向了原链表的结点i-1，将这个结点的next由指向原链表的结点i改为指向新结点）：

temp->front->next = temp;

最后，length+1。

在完成这个函数的过程中我曾犯了3个错误：

1.一开始我没有track指针域，而是不停地copy结点本身，获得原来的结点i-1和结点i的copy，然后在上边做指针变换，所以实际上我create了3个结点（新结点temp，结点i-1的copy和结点i的copy），然后把这3个结点连在一起，这对原链表一点儿影响都没有，因为我处理的是结点i-1和结点i的COPY！

2.track指针域，在做指针断开/交换操作的最后一步（接下来，原链表的结点i-1的next，也应该指向这个新结点）时，写了

ptr = temp;

的确，原链表的结点i-1的next，和ptr的值是一样的（都是指向原链表的结点i），但是上面的代码是改了ptr，而不是改了原链表的结点i-1的next！

3.在生成新结点的时候，一开始我用了以下方式：

Node temp(data);

函数内执行结果并没有错（当然Node*的地方要变为Node），但是函数返回后在主程序中没有得到正确的结果。我推测应该是函数局部变量的函数结束时会被自动销毁，所以在主程序中获得的链表，在读到新结点的时候就会得到垃圾值。

在插入结点的经验上，实现删除结点的操作就轻松很多了：

void LinkList::DeleteNode(int i)
{
    if ( (i > this->length - 1) || (i < 0) )
    {
        std::cout<<"Error!!!!!!!!!"<<std::endl;
    } 
    else
    {
        Node* ptr = this->headNode.next;
        for (int k = 0; k < i; k++)
        {
            ptr = ptr->next;
        }
        Node* temp = ptr;
        ptr->next->front = ptr->front;
        ptr->front->next = ptr->next;
        this->length--;
        delete temp;
        temp = NULL;
    }
    return;
}