线性表之单链表C++实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

源码：https://github.com/cjy513203427/C_Program_Base/tree/master/54.%E9%93%BE%E8%A1%A8

需要实现的方法

#pragma once
#include"Node.h"
#ifndef LIST_H
#define LIST_H
#include<iostream>
using namespace std;
class List
{
public:
    List();//构造函数
    ~List();//析构函数
    void ClearList();//清空链表
    bool ListEmpty();//链表判空
    int ListLength();//链表长度
    bool GetElem(int i, Node *pNode);//获取指定索引的元素
    int LocateElem(Node *pNode);//获取指定元素的索引
    bool PriorElem(Node *pCurrentNode, Node *pPreNode);//获取前驱结点
    bool NextElem(Node *pCurrentNode, Node *pNextNode);//获取后继结点
    void ListTraverse();//遍历
    bool ListInsert(int i,Node *pNode);//插入元素
    bool ListDelete(int i, Node *pNode);//删除元素
    bool ListInsertHead(Node *pNode);//插入在头结点后面
    bool ListInsertTail(Node *pNode);//插入到链表最后
private:
    Node * m_pList;
    int m_iLength;
};

#endif // !LIST_H

1.构造函数

堆中为头结点m_pList申请内存

m_pList数据域置为0

指向地址为空，事实上这里声明了一个头结点，头结点没有后继结点并且数据域为空

长度置为0

List::List()
{
    m_pList = new Node;
    m_pList->data = 0;
    m_pList->next = NULL;
    m_iLength = 0;
}

2.析构函数

调用清空链表方法

删除头结点并置空

List::~List()
{
    ClearList();
    delete m_pList;
    m_pList = NULL;
}

3.清空链表

声明一个Node*类型的指针指向m_pList的下一个结点，特别指明：m_pList是头结点，m_pList->next是头结点的指针域

判断currentNode是否为空，即判断m_pList的指针域是否为空，为空说明currentNode是尾结点，尾结点没有后继结点

currentNode不为空时，声明一个Node*类型的指针temp指向currentNode的下一个结点，也可以理解为temp接收currentNode的指针域值

删除当前的currentNode,再把temp保存的currentNode的指针域赋值回去

依次类推...

循环结束，再把尾结点指针域置空

清空链表和析构函数的区别：清空链表是将头结点之后的结点全部清空，析构函数是把头结点和之后的结点全部清空

void List::ClearList()
{
    Node *currentNode = m_pList->next;
    while (currentNode != NULL)
    {
        Node *temp = currentNode->next;
        delete currentNode;
        currentNode = temp;
    }
    m_pList->next = NULL;
}

4.链表判空与获取长度

没什么好说的

bool List::ListEmpty()
{
    return 0 == m_iLength ? true : false;
}

int List::ListLength()
{
    return m_iLength;
}

5.在头结点后面插入元素

pNode指针作为参数传入

temp保存头结点的指针域，指向第一个结点

在堆中申请一个newNode指针的内存

没申请到内存返回错误

申请到内存，参数的数据域赋值给新结点数据域

头结点指向新结点

新结点指向原来头结点的下一个结点，这样链表就连接起来了

bool List::ListInsertHead(Node *pNode)
{
    Node *temp = m_pList->next;
    Node *newNode = new Node;
    if (newNode == NULL) //判断申请的结点内存是否为空
    {
        return false;
    }
    else
    {
        newNode->data = pNode->data;
        m_pList->next = newNode;
        newNode->next = temp; 
        m_iLength++;
        return true;
    }
}

6.在尾结点后面插入元素

pNode指针作为参数传入

currentNode接收头结点

判断currentNode是否是尾结点，因为尾结点后继结点为空

循环到最后一个结点，此时currentNode->next=NULL

在堆中申请一个newNode的内存

没申请到内存返回错误

申请到内存

pNode的数据域赋值给newNode的数据域

新结点指针域置空

currentNode指向新结点

新结点指向空，这样链表就连接起来了，新结点成为了新的尾结点

链表长度++

返回正确

bool List::ListInsertTail(Node *pNode)
{
    Node *currentNode = m_pList;
    while (currentNode->next != NULL)
    {
        currentNode = currentNode->next;
    }
    Node *newNode = new Node;
    if (newNode == NULL)
    {
        return false;
    }
    else
    {
        newNode->data = pNode->data;
        newNode->next = NULL;
        currentNode->next = newNode;
        m_iLength++;
        return true;
    }
}

7.插入元素

判断参数i的合法性

i不能小于0，i不能大于链表长度,i等于链表长度代表可以尾元素后插入

currentNode保存头结点

声明newNode

pNode数据域赋值给newNode数据域

新结点指向原来结点的下一个结点

原来的结点指向新结点

bool List::ListInsert(int i, Node *pNode)
{
    if (i<0 || i>m_iLength)
    {
        return false;
    }
    Node *currentNode = m_pList;
    for (int k = 0; k < i; k++)
    {
        currentNode = currentNode->next;
    }
    Node *newNode = new Node;
    if (newNode == NULL) //判断申请的结点内存是否为空
    {
        return false;
    }
    else
    {
        newNode->data = pNode->data;
        newNode->next = currentNode->next;
        currentNode->next = newNode;
        return true;
    }
}

8.删除元素

判断i是否合法，索引最大是m_iLength-1，和循环条件k<i对应

currentNode保存头指针

currentNodeBefore置空

currentNodeBefore指向currentNode的下一个结点的指针域，这样currentNode就可以被删除释放了

pNode数据域接收当前结点的数据域

删除当前结点并置空

bool List::ListDelete(int i, Node *pNode)
{
    if (i<0 || i>=m_iLength)
    {
        return false;
    }
    Node *currentNode = m_pList;
    Node *currentNodeBefore = NULL;
    for (int k = 0; k <= i; k++)
    {
        currentNodeBefore = currentNode;
        currentNode = currentNode->next;
    }
    currentNodeBefore->next = currentNode->next;
    pNode->data = currentNode->data;
    delete currentNode;
    currentNode = NULL;
    m_iLength--;
    return true;
}

9.获取指定索引的元素

逻辑同删除元素

bool List::GetElem(int i, Node *pNode)
{
    if (i<0 || i >= m_iLength)
    {
        return false;
    }
    Node *currentNode = m_pList;
    Node *currentNodeBefore = NULL;
    for (int k = 0; k <= i; k++)
    {
        currentNodeBefore = currentNode;
        currentNode = currentNode->next;
    }
    pNode->data = currentNode->data;
    return true;
}

10.获取指定元素的索引

currenNode保存头指针

只要currentNode的指针域/指向不为空，继续下去

如果参数的数据域等于currentNode的数据域，返回count，count就是索引

int List::LocateElem(Node *pNode)
{
    Node *currentNode = m_pList;
    int count = 0;
    while (currentNode->next != NULL)
    {
        currentNode = currentNode->next;
        if (currentNode->data == pNode->data)
        {
            return count;
        }
        count++;
    }
    return -1;
}

11.获取前驱结点

currentNode保存头结点

中间变量tempNode置空

currentNode指针域不为空开始循环

tempNode保存当前结点

currentNode像后移一位

如果pCurrentNode的数据域等于当前结点的数据域

如果tempNode等于头结点，返回错误

将tempNode的数据域赋值给pPreNode的数据域，此时tempNode是保存的currentNode,currentNode是下一个的结点

所以currentNode->data==pCurrentNode->data是currentNode下一个结点的数据域和pCurrentNode比较

bool List::PriorElem(Node *pCurrentNode, Node *pPreNode)
{
    Node *currentNode = m_pList;
    Node *tempNode = NULL;
    int count = 0;
    while (currentNode->next != NULL)
    {
        tempNode = currentNode;
        currentNode = currentNode->next;
        if (currentNode->data == pCurrentNode->data)
        {
            if (tempNode == m_pList) 
            {
                return false;
            }
            pPreNode->data = tempNode->data;
            return true;
        }
    }
    return false;
}

12.获取后继结点

currentNode保存头指针

currentNode指针域不为空执行循环

currentNode一直向后移动

如果pCurrentNode的数据域等于currentNode的数据域

如果是尾结点，返回错误

再将当前结点指向的下一个结点的数据域赋值给pNextNode的数据域

bool List::NextElem(Node *pCurrentNode, Node *pNextNode)
{
    Node *currentNode = m_pList;
    while (currentNode->next != NULL)
    {
        currentNode = currentNode->next;
        if (currentNode->data == pCurrentNode->data)
        {
            if (currentNode->next == NULL)
            {
                return false;
            }
            pNextNode->data = currentNode->next->data;
            return true;
        }
    }
}

13.遍历

currentNode保存头指针

currentNode只要不是尾结点一直遍历下去

currentNode后移，调用printNode()方法

void List::ListTraverse()
{
    Node *currentNode = m_pList;
    while (currentNode->next != NULL)
    {
        currentNode = currentNode->next;
        currentNode->printNode();
    }
}