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

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

2024-10-24 18:26:02   210人阅读

2015年学习计划安排：

http://www.cnblogs.com/cyrus-ho/p/4182275.html

 

尝试用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 = http://www.mamicode.com/0;    this->next = NULL;    this->front = NULL;}Node::Node(int data){    this->data =http://www.mamicode.com/ data;    this->next = NULL;    this->front = NULL;}Node::Node(int data, Node* nextPtr, Node* frontPtr){    this->data =http://www.mamicode.com/ 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;}

 

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


联系
我们