数据结构--单链表single linked list数据结构C++实现

Michael阿明

发布于 2021-02-20 10:23:42

48900

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

2018年2月开始学习的 C++ Primer，到今天2019年3月已经整整一年了，非常感谢在一起交流的小伙伴，是你们的无私帮助和分享使得我能跨越很多技术的坑，感谢你们！期待我们2019年一起拿下《数据结构与算法》以及Python入门。

我的github代码链接https://github.com/hitskyer/course/tree/master/dataAlgorithm/chenmingming/linkedList

单链表反转参考他人博客https://blog.csdn.net/feliciafay/article/details/6841115

single_linkedlist.h

#ifndef LINKEDLIST_SINGLE_LINKEDLIST_H
#define LINKEDLIST_SINGLE_LINKEDLIST_H

#include<iostream>
using namespace std;

template<class ElemType>
struct LinkNode      //节点类
{
    ElemType _data;    //节点的数据
    LinkNode *_next;    //指向该节点的下一个节点的指针
    LinkNode(): _next(NULL)
    {
        cout << "please enter data: ";
        cin >> _data;
    }
    LinkNode(const ElemType &d, LinkNode* p = NULL) : _data(d), _next(p) {}
    ~LinkNode(){}
};
template <class ElemType> class Single_linkedlist
{
    LinkNode<ElemType> *p_head = NULL;   //首尾指针
    LinkNode<ElemType> *p_tail = NULL;
    int listlength = 0; //链表长度
public:
    Single_linkedlist(int len = 0); //构造函数(顺序插入)
    Single_linkedlist(char reverse, int len = 0); //构造函数(逆序插入)
    ~Single_linkedlist()    //析构函数
    {
        deleteAll();  //释放new出来的节点
    }

    void deleteAll();   //删除所有节点
    void *get_p_head() const //返回头节点的位置，即头指针
    {
        return p_head;
    }

    void *get_p_tail() const //返回为节点的位置，即尾指针
    {
        return p_tail;
    }

    int getLength() const //返回链表长度
    {
        return listlength;
    }

    bool isEmpty() const    //判断链表是否为空
    {
        return listlength == 0;
    }

    ElemType getCurData(LinkNode<ElemType> *p) const  //返回当前节点的数据内容
    {
        return p->_data;
    }

    void addHead(const ElemType &data);    //在链表头部添加元素
    void addTail(const ElemType &data);     //在链表尾部添加元素
    LinkNode<ElemType>* find(int m) const; //按下标查找
    LinkNode<ElemType>* find(ElemType &data) const; //按元素值查找
    bool insertAtElemFront(const LinkNode<ElemType> &data, int i);    //在i号元素前插入新节点
    bool insertAtElemBack(const LinkNode<ElemType> &data, int i);    //在i号元素后插入新节点
    bool deleteElem(int i); //删除i号元素节点
    bool modifyElem(int i, const ElemType &data);   //修改i号元素的值
    LinkNode<ElemType>* reverse();  //链表反转(就地反转法)
    void printList() const; //打印链表数据

};

#include "single_linkedlist.cpp"    //模板实现文件，包含编译模型
#endif //LINKEDLIST_SINGLE_LINKEDLIST_H

single_linkedlist.cpp

/*
 * 内存泄漏总结：
 * 局部定义的指针，指向new出来的节点（堆空间），指针就可以返回
 * （如果指针没有指向堆空间，函数退出后，栈内的内容销毁，返回的指针也就是无效的）
 * 链表析构的时候delete 这些new出来的节点的地址（堆指针）
 */
template <class ElemType> 
Single_linkedlist<ElemType>::Single_linkedlist(int len)
{
    LinkNode<ElemType> *curNode;
    for(int i = 0; i != len; ++i) {
        curNode = new LinkNode<ElemType>;
        if(i == 0) {
            p_head = curNode;
            p_tail = curNode;
        } else {
            p_tail->_next = curNode;
            p_tail = curNode;
        }
        ++listlength;
    }
}
template <class ElemType> 
Single_linkedlist<ElemType>::Single_linkedlist(char reverse, int len)
{
    if(reverse == 'r' | reverse == 'R') {
        LinkNode<ElemType> *curNode, *prevNode;
        for(int i = 0; i != len; ++i) {
            curNode = new LinkNode<ElemType>;
            if(i == 0) {
                p_head = curNode;
                p_tail = curNode;
                prevNode = curNode;
            } else {
                curNode->_next = prevNode;
                p_head = curNode;
                prevNode = curNode;
            }
            ++listlength;
        }
    } else {
        cout << "you should enter 'r' or 'R' to the second Parameter！" << endl;
    }
}

template <class ElemType> 
void Single_linkedlist<ElemType>:: deleteAll()
{
    LinkNode<ElemType> *del_tempNode, *tempNode;
    del_tempNode = this -> p_head;
    while(del_tempNode != NULL) {
        tempNode = del_tempNode -> _next;
        delete del_tempNode;
        del_tempNode = tempNode;
        listlength--;
    }
    p_head = NULL;
    p_tail = NULL;
}

template <class ElemType> 
LinkNode<ElemType>* Single_linkedlist<ElemType>::find(int m) const
{
    if(m < 0 | m >= listlength)
    {
        cout << "位置不正确（位置序号从0开始）！" << endl;
        return NULL;
    }
    else
    {
        LinkNode<ElemType> *tempNode = p_head;
        for (int i = 0; i < m; ++i, tempNode = tempNode->_next)
        {   //空函数体
        }
        return tempNode;
    }
}
template <class ElemType> 
LinkNode<ElemType>* Single_linkedlist<ElemType>::find(ElemType &data) const
{
    LinkNode<ElemType> *tempNode = p_head;
    for (; (tempNode != NULL) && (tempNode->_data != data); tempNode = tempNode->_next)
     {   //空函数体
    }
    if(tempNode != NULL) {
        cout << "找到了指定元素！地址是：" << tempNode << endl;
        return tempNode;
    } else {
        cout << data << " is not exist!" << endl;
        return NULL;
    }
}
template <class ElemType> 
void Single_linkedlist<ElemType>::addHead(const ElemType &data)
{
    LinkNode<ElemType> *node = new LinkNode<ElemType>(data);
    if(p_head == NULL) {
        p_head = node;
        p_tail = node;
    } else {
        node->_next = p_head;
        p_head = node;
    }
    ++listlength;
    cout << "新的链表是：\n";
    this->printList();
    cout << "链表的长度是：" << listlength << endl;
}
template <class ElemType> 
void Single_linkedlist<ElemType>::addTail(const ElemType &data)
{
    LinkNode<ElemType> *node = new LinkNode<ElemType>(data);
    if(p_tail == NULL) {
        p_head = node;
        p_tail = node;
    } else {
        p_tail->_next = node;
        p_tail = node;
    }
    ++listlength;
    cout << "新的链表是：\n";
    this->printList();
    cout << "链表的长度是：" << listlength << endl;
}
template <class ElemType> 
bool Single_linkedlist<ElemType>::insertAtElemFront(const LinkNode<ElemType> &data, int i)
{
    LinkNode<ElemType> *node = new LinkNode<ElemType>(data);
    LinkNode<ElemType> *tempNode = p_head;
    if(i < 0 | i >= listlength)
    {
        cout << "位置不正确（位置序号从0开始）！" << endl;
        return false;
    }
    else
    {
        if(this->find(i) == NULL)
        {
            p_head = node;
            p_tail = node;
        }
        else
        {
            while(tempNode->_next != this->find(i))
            {
                tempNode = tempNode->_next;
            }
            node->_next = this->find(i);
            tempNode->_next = node;
        }
        ++listlength;
        return true;
    }
}
template <class ElemType> 
bool Single_linkedlist<ElemType>::insertAtElemBack(const LinkNode<ElemType> &data, int i)
{
    LinkNode<ElemType> *node = new LinkNode<ElemType>(data);
    LinkNode<ElemType> *tempNode = p_head;
    if(i < 0 | i >= listlength)
    {
        cout << "位置不正确（位置序号从0开始）！" << endl;
        return false;
    }
    else
    {
        if(this->find(i) == NULL)
        {
            p_head = node;
            p_tail = node;
        }
        else
        {
            tempNode = this->find(i);
            node->_next = tempNode->_next;
            tempNode->_next = node;
        }
        ++listlength;
        return true;
    }
}
template <class ElemType> 
bool Single_linkedlist<ElemType>::deleteElem(int i)
{
    LinkNode<ElemType> *tempNode = p_head, *deleteNode;
    deleteNode = this->find(i);
    if(i < 0 | i >= listlength)
    {
        cout << "位置不正确（位置序号从0开始）！" << endl;
        return false;
    }
    else
    {
        if(deleteNode == NULL)
        {
            return false;
        }
        else
        {
            while (tempNode->_next != deleteNode)
            {
                tempNode = tempNode->_next;
            }
            tempNode->_next = deleteNode->_next;
            if (deleteNode == p_tail)
                p_tail = tempNode;
            delete deleteNode;
            --listlength;
            return true;
        }
    }
}
template <class ElemType> 
bool Single_linkedlist<ElemType>::modifyElem(int i, const ElemType &data)
{
    LinkNode<ElemType> *tempNode = p_head, *modifyNode;
    modifyNode = this->find(i);
    if(i < 0 | i >= listlength)
    {
        cout << "位置不正确（位置序号从0开始）！" << endl;
        return false;
    }
    else
    {
        if(modifyNode == NULL)
        {
            return false;
        }
        else
        {
            modifyNode->_data = data;
            return true;
        }
    }
}
template <class ElemType> 
LinkNode<ElemType>* Single_linkedlist<ElemType>::reverse()
{
    if(p_head == NULL || p_head->_next == NULL)
        return NULL;
    else    //就地反转法
    {
        LinkNode<ElemType> *prevNode, *nextNode, *tempNode;
        prevNode = p_head;
        nextNode = prevNode->_next;
        prevNode->_next = NULL;
        p_tail = prevNode;
        while(nextNode != NULL)
        {
            tempNode = nextNode->_next;
            nextNode->_next = prevNode;
            prevNode = nextNode;
            nextNode = tempNode;
        }
        p_head = prevNode;
        return p_head;
    }
}
template <class ElemType> 
void Single_linkedlist<ElemType>::printList() const
{
    int m = 0;
    LinkNode<ElemType>* tempNode = p_head;
    for(; tempNode != NULL; tempNode = tempNode->_next)
    {
        cout << "N.O[" << m++ << "] element "  << tempNode->_data << endl;
    }
    cout << "--------------------------------------" << endl;
}

main_single_linkedlist.cpp

#include "single_linkedlist.h"
#include <iostream>
#include <string>

int main()
{
    Single_linkedlist<int> intList1(2);
    intList1.printList();
    cout << "链表的长度是：" << intList1.getLength() << endl;
    intList1.deleteAll();
    cout << "链表的长度是：" << intList1.getLength() << endl;
    Single_linkedlist<string> strList1('r',3);
    strList1.printList();
    cout << "链表是空的吗？(0:不是；1:是)" << strList1.isEmpty() << endl;
    cout << "链表的第2号元素list[2]是：" << (strList1.find(2))->_data << endl;
    string str("abc");
    cout << "链表的包含字符串\"abc\"的元素的地址：" << endl;
    strList1.find(str);
    strList1.addHead(str);
    strList1.addTail(str);
    strList1.insertAtElemFront(str,2);
    strList1.printList();
    strList1.insertAtElemBack(str,3);
    strList1.printList();
    strList1.deleteElem(strList1.getLength()-1);
    strList1.printList();
    strList1.modifyElem(strList1.getLength()-1,string("end"));
    strList1.printList();
    strList1.reverse();
    strList1.printList();
    return 0;
}