线性表--链表（C++）

Node.h

#ifndef NODE_H
#define NODE_H

class Node
{
public:
    int data;//数据域
    Node* next;//指针域 指向下一个节点
    void printNode();
};

#endif //NODE_F

Node.cpp

#include "Node.h"
#include <iostream>
using namespace std;

void Node::printNode()
{
    cout << data << endl;
}

LinkList.h

#ifndef LINKLIST_H
#define LINKLIST_H

#include "Node.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 //LINKLIST_H

LinkList.cpp

#include "LinkList.h"

List::List()
{
    m_pList = new Node;//new运算符在堆中申请内存
    m_pList->data = 0;
    m_pList->next = NULL;
    m_iLength = 0;
}

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

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

bool List::ListEmpty()
{
    if (m_iLength == 0)
        return true;
    else
        return false;
}
int List::ListLength()
{
    return m_iLength;
}

bool List::ListInsertHead(Node *pNode)
{
    Node *temp=m_pList->next; //保留头节点
    Node *newNode = new Node; //为传入数据的存储开辟空间
    if (newNode == NULL)
        return false;
    newNode->data = pNode->data;//赋值
    m_pList->next = newNode;
    newNode->next = temp;
    m_iLength ++;
    return true;
}

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;
    newNode->data = pNode->data;
    newNode->next = NULL;
    currentNode->next = newNode; //newNode更新为整个链表的尾节点
    m_iLength ++;
    return true;
}

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;
    newNode->data = pNode->data;
    newNode->next = currentNode->next;
    currentNode->next = newNode; // 插入;
}

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;
}

bool List::GetElem(int i, Node *pNode)
{
    if (i<0 || i >= m_iLength)
        return false;
    //找到第i个节点
    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;
}

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;//没找到与pNode相同的数据域
}

bool List::PriorElem(Node *pCurrentNode, Node *pPreNode)
{
    Node *currentNode = m_pList;
    Node *tempNode = NULL;
    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;
}

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;
        }
    }
}

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

test.cpp

#include "LinkList.h"
#include <stdlib.h>

int main()
{
    Node node1;  //调用默认的构造函数
    node1.data = 3;
    Node node2;  
    node2.data = 4;
    Node node3; 
    node3.data = 5;
    Node node4;  
    node4.data = 6;
    Node node5;
    node5.data = 7;
    Node temp;

    List *pList = new List();

    /*pList->ListInsertHead(&node1);  //测试头插
    pList->ListInsertHead(&node2);
    pList->ListInsertHead(&node3);
    pList->ListInsertHead(&node4);*/  

    pList->ListInsertTail(&node1);    //测试尾插
    pList->ListInsertTail(&node2);
    pList->ListInsertTail(&node3);
    pList->ListInsertTail(&node4);

    //pList->ListInsert(0, &node5);      //测试任意位置插入
    //pList->ListDelete(0, &temp);   //测试删除函数 删除的值放在temp中
    //pList->GetElem(1, &temp); //测试获取元素
    //pList->PriorElem(&node4, &temp);  //测试取元素前驱
    pList->NextElem(&node1, &temp);//测试取元素的后继

    pList->ListTraverse();

    //cout <<"temp="<< temp.data << endl;  //测试删除函数 删除的值是放在temp中的
    //cout << "temp=" << temp.data << endl;  //测试获取元素 获取的元素是放在temp中
    //cout << "temp=" << temp.data << endl; //测试取元素前驱 获取的前驱是放在temp中的
    cout << "temp=" << temp.data << endl; //测试取元素后继 获取的后继是放在temp中的
    
    delete pList;
    pList = NULL;

    system("pause");
}

运行结果： LinkList.png