数据结构-单向链表 C和C++的实现

首页 > 代码库 > 数据结构-单向链表 C和C++的实现

数据结构-单向链表 C和C++的实现

2024-10-26 03:59:02 206人阅读

数据结构，一堆数据的存放方式。

今天我们学习数据结构中的链表：

数组，大家相当熟悉的存放数据方式，而链表是数组的一种特殊方式，它每个节点包括两个部分：

数据域：存放数据，此部分与数组相同
指针域：存放了下一个节点的地址

链表比数组多了指针域，因为链表需要通过上一个节点的指针域去找下一个数据，比如有一个链表ABCD四个节点，我们要访问D里边的数据。操作如下：

先通过A节点的指针域找到B节点
再通过B节点的指针域找到C节点
再通过C节点的指针域找到D节点
获取D节点数据域的数据

对比数组直接通过下标访问，链表的访问方式相当麻烦，既然这么麻烦，为什么还有链表这种数据结构呢？因为链表插入删除节点方式十分便捷，在数据量大的时候，删除数组的数据需要把删除数据后面的数据都前移一位，而链表只需要改变前一个元素的指针域，插入和删除操作速度快。

这么厉害的东西，还是看程序比较直接

单向链表

C

（此处插入代码）

C++

在C++中，使用模板的方法实现

本程序包括3个文件组成，他们分别是：

技术分享

定义节点类：Node.h

这个类定义了每个节点的两个区域：m_tpData数据域和 m_tpNext指针域：

#include <iostream>

using namespace std;

template <typename T>
class Node
{
public:
    Node();
    Node(T data);
    ~Node();
    void setData(T data);
    T getData();
    void setNext(Node<T> *next);
    Node* getNext();
    void printData();
private:
    T *m_tpData;
    Node<T> *m_tpNext;
};


template <typename T>
Node<T>::Node()
{
    m_tpData = new T;
    m_tpNext=NULL;
}

template <typename T>
Node<T>::Node(T data)
{
    m_tpData = new T(data);
    m_tpNext=NULL;
}

template <typename T>
Node<T>::~Node()
{
    delete m_tpData;
    m_tpData=NULL;
}

template <typename T>
void Node<T>::setData(T data)
{
    *m_tpData =http://www.mamicode.com/ data;
}

template <typename T>
T Node<T>::getData()
{
    return *m_tpData;
}

template <typename T>
void Node<T>::setNext(Node<T> *next)
{
    m_tpNext = next;
}

template <typename T>
Node<T>* Node<T>::getNext()
{
    return m_tpNext;
}

template <typename T>
void Node<T>::printData()
{
    cout<<*m_tpData<<endl;
}

链表类 LinkList.h

#include <iostream>
#include "Node.h"

using namespace std;

template <typename T>
class LinkList
{
public:
    LinkList();
    ~LinkList();
    bool isListEmpty();
    bool clearList();
    int getListLength();
    int getElemIndex(T &elem);
    bool getListElem(int index,T* elem);
    //bool getListPrevious(int index,T* elem); 
    //bool getListNext(int index,T* elem);
    bool ListInsert(int index,T &elem);
    bool ListDelete(int index,T *elem);
    void ListPrint(void);
private:
    Node<T> *m_pList;
    int m_iLength;
};

template <typename T>
LinkList<T>::LinkList()
{
    m_pList = new Node<T>;
    m_pList->setData(NULL);
    m_pList->setNext(NULL);
    m_iLength=0;
}

template <typename T>
LinkList<T>::~LinkList()
{
    Node<T> *nextNode = m_pList;
    while(nextNode->getNext()!=NULL)    //delete Node while pointerNext == NULL
    {        
        nextNode=m_pList->getNext();
        delete m_pList;
        m_pList = nextNode;
    }
    delete m_pList;//delete last Node
    m_pList = NULL;
}

template <typename T>
bool LinkList<T>::isListEmpty()
{
    if(m_iLength==0)
        return true;
    return false;
}


template <typename T>
bool LinkList<T>::clearList()
{
    if(isListEmpty())
    {
        cout<<"List empty clear fail"<<endl;
        return false;
    }

    //delete All node except first node
    Node<T> *nowNode = m_pList->getNext();
    Node<T> *nextNode = m_pList->getNext();
    while(nextNode->getNext()!=NULL)    
    {        
        nextNode=nowNode->getNext();
        delete nowNode;
        nowNode = nextNode;
    }
    delete nowNode;//delete last Node

    m_iLength = 0;
    m_pList->setNext(NULL);
    return true;
}

template <typename T>
int LinkList<T>::getListLength()
{
    return m_iLength;
}
template <typename T>
int LinkList<T>::getElemIndex(T &elem)
{
    Node<T> *tempNode = m_pList;
    for(int i=0;i<m_iLength;i++)
    {
        tempNode = tempNode->getNext();
        if(elem == tempNode->getData())
        {
            return i;
        }
    }
    return -1;
}
template <typename T>
bool LinkList<T>::getListElem(int index,T* elem)
{
    if(index<0 || index>= m_iLength)
    {
        return false;
    }

    Node<T> *tempNode = m_pList;
    for(int i=0;i<=index;i++)
    {
        tempNode=tempNode->getNext();
    }

    *elem = tempNode->getData();
    return true;
}



template <typename T>
bool LinkList<T>::ListInsert(int index,T &elem)
{
    //index out of range
    if(index<0 || index>m_iLength)
    {
        return false;
    }

    //
    Node<T> *tempPreNode = m_pList; 
    for(int i=0;i<index;i++)
    {
        tempPreNode = tempPreNode->getNext();
    }

    Node<T> *newnode = new Node<T>;    //create a new node
    if(newnode == NULL)
    {
        cout<<"new node create fail"<<endl;
        return false;
    }
    Node<T> *tempNode= tempPreNode->getNext();//save pre node pointer
    tempPreNode->setNext(newnode); //set pre node pointer to new node address
    newnode->setNext(tempNode);//set new node pointer to pre node pointer
    newnode->setData(elem);    //set new node new data
    m_iLength++;
    return true;
}

template <typename T>
bool LinkList<T>::ListDelete(int index,T *elem)
{
    //index out of range
    if(index<0 || index>=m_iLength)
    {
        return false;
    }

    //
    Node<T> *tempPreNode = m_pList; //pre node
    for(int i=0;i<index;i++)//find pre node
    {
        tempPreNode = tempPreNode->getNext();
    }

    Node<T> * tempNode = tempPreNode->getNext();//save delete point pointer 
    tempPreNode->setNext(tempNode->getNext());//set pre node  point to next node
    *elem = tempNode->getData();
    delete tempNode;

    m_iLength--;
    return true;        
}

template <typename T>
void LinkList<T>::ListPrint(void)
{
    if(isListEmpty())
    {
        cout<<"List empty"<<endl;
        return;
    }
    Node<T> *tempNode=m_pList->getNext();
    while(tempNode->getNext() != NULL)
    {        
        tempNode->printData();
        tempNode = tempNode->getNext();
    }
    tempNode->printData();
    cout<<"end"<<endl;
}

单项链表模板定义完了，我们在main.cpp中使用int类型实例化它、并测试它的功能

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

int main(void)
{
    /*insert data check*/
    int data[10]={0,1,2,3,4,5,6,7,8,9};
    LinkList<int> *linklist = new LinkList<int>;
    for(int i=0;i<5;i++)
    {
        linklist->ListInsert(i,data[i]);
    }
    linklist->ListPrint();

    /*getElemIndex check*/
    cout<<"getElemIndex:"<<linklist->getElemIndex(data[4])<<endl;

    /*getListElem check*/
    int getdata;
    linklist->getListElem(2,&getdata);
    cout<<"getListElem:"<<getdata<<endl;


    /*delete data check*/
    int deletedata;
    linklist->ListDelete (0,&deletedata);
    cout<<"delete data:"<<deletedata<<endl;
    linklist->ListPrint();

    /*clearList check*/
    linklist->clearList();
    linklist->ListPrint();

    delete linklist;
    linklist = NULL;
    system("pause");
    return 0;
}

运行结果如下：

技术分享

数据结构-单向链表 C和C++的实现

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 数据结构-单向链表 C和C++的实现

数据结构-单向链表 C和C++的实现

C

C++

看完仍有疑问？有类似问题直接问程序猿