数据结构之单向链表

淡淡的烟草味﹌ 2022-05-27 07:18 250阅读 0赞

LinkedList.h：

#ifndef LINKEDLISH_H
    #define LINKEDLISH_H
    
    #include "Node.h"
    
    class LinkedList { 
    public:
        LinkedList();
        ~LinkedList();
        bool insert(Node *ele, int locate);
        bool insertHead(Node *ele);
        bool insertTail(Node *ele);
        bool del(int locate, Node *e);
        bool isEmpty();
        int  length();
        void clear();
        bool preElem(Node *current, Node *preElem);
        bool nextElem(Node *current, Node *nextElem);
        bool get(int locate, Node *e);
        int  locate(Node *e);
        void printAll();
    
    private:
        int m_iLength;
        Node *m_pList;
    };
    
    #endif

LinkedList.cpp：

#include "LinkedList.h"
    #include <iostream>
    
    using namespace std;
    
    LinkedList::LinkedList() {
        m_pList = new Node();
        m_pList->data = 0;
        m_pList->next = NULL;
        m_iLength = 0;
    };
    LinkedList::~LinkedList() {
        clear();
        delete m_pList;
        m_pList = NULL;
    };
    bool LinkedList::insert(Node *ele, int locate) {
    
        if (locate < 0 || locate > m_iLength) return false;
    
        Node *current = m_pList;
        for (int i = 0; i < locate; i++)
        {
            current = current->next;
        }
        Node * newNode = new Node();
        if (newNode == NULL) return false;
    
        newNode->data = ele->data;
        newNode->next = current->next;
        current->next = newNode;
        m_iLength++;
        return true;
    
    };
    
    bool LinkedList::insertHead(Node *ele) {
        Node * temp = m_pList->next;
        Node * newNode = new Node();
        if (newNode == NULL) return false;
        newNode->data = ele->data;
        newNode->next = temp;
        m_pList->next = newNode;
        m_iLength++;
        return true;
    };
    
    bool LinkedList::insertTail(Node *ele) {
    
        Node * currentNode = m_pList;
        while (NULL != currentNode->next) {
            currentNode = currentNode->next;
        }
        Node * newNode = new Node();
        if (newNode == NULL) return false;
    
        newNode->data = ele->data;
        newNode->next = NULL;
        currentNode->next = newNode;
        m_iLength++;
        return true;
    };
    
    bool LinkedList::del(int locate, Node *e) {
    
        if (locate < 0 || locate >= m_iLength) return false;
    
        if (isEmpty()) return false;
    
        Node *current = m_pList;
        Node *currentBefore = NULL;
        for (int i = 0; i <= locate; i++)
        {
            currentBefore = current;
            current = current->next;
        }
        currentBefore->next = current->next;
        e->data = current->data;
        delete current;
        current = NULL;
        m_iLength--;
        return true;
    };
    
    bool LinkedList::isEmpty() {
        return m_iLength == 0;
    };
    
    int  LinkedList::length() {
        return m_iLength;
    };
    
    void LinkedList::clear() {
        Node *current = m_pList->next;
        while (NULL != current) {
            Node * tmp = current->next;
            delete current;
            current = tmp;
        }
        m_pList->next = NULL;
        m_iLength = 0;
    };
    
    bool LinkedList::preElem(Node *current, Node *preElem) {
        Node *currentNode = m_pList;
        Node *tmp = NULL;
        while (NULL != currentNode->next) {
            tmp = currentNode;
            currentNode = currentNode->next;
            if (currentNode->data == current->data) {
                preElem->data = tmp->data;
                return true;
            }
        }
        return false;
    };
    
    bool LinkedList::nextElem(Node *current, Node *nextElem) {
        Node *currentNode = m_pList;
    
        while (NULL != currentNode->next) {
    
            currentNode = currentNode->next;
            if (currentNode->data == current->data) {
                if (currentNode->next == NULL) return false;
    
                nextElem->data = currentNode->next->data;
                return true;
            }
        }
        return false;
    };
    
    bool LinkedList::get(int locate, Node *e) {
    
        if (locate < 0 || locate >= m_iLength) return false;
    
        Node *current = m_pList;
        for (int i = 0; i <= locate; i++)
        {
            current = current->next;
        }
        e->data = current->data;
    
        return true;
    
    };
    
    int LinkedList::locate(Node *e) {
    
        Node *current = m_pList;
        int i = 0;
        while (NULL != current->next) {
            current = current->next;
            if (current->data == e->data) {
                return i;
            }
            i++;
        }
        return -1;
    };
    
    void LinkedList::printAll() {
    
        Node *current = m_pList;
    
        while (current->next != NULL) {
            current = current->next;
            current->printNode();
        }
    };

Node.h：

#ifndef NODE_H
    #define NODE_H
    
    class Node { 
    public:
        int data;
        Node * next;
        void printNode();
    };
    
    #endif

Node.cpp：

#include "Node.h"
    #include <iostream>
    
    using namespace std;
    
    void Node::printNode() {
        cout << data << endl;
    }

测试：

#include <iostream>
    #include <stdlib.h>
    #include "LinkedList.h"
    
    using namespace std;
    
    
    int main(void) {
    
        Node node1;
        node1.data = 1;
        Node node2;
        node2.data = 2;
        Node node3;
        node3.data = 3;
        Node node4;
        node4.data = 4;
    
        LinkedList * plist = new LinkedList();
    
        plist->insertHead(&node1);
        plist->insertHead(&node2);
        plist->insertTail(&node3);
        plist->insertTail(&node4);
    
        plist->printAll();
        cout << "=======" << endl;
        Node tmp;
        plist->del(2,&tmp);
    
        plist->printAll();
        cout << "=======" << endl;
    
        cout << "长度：" << plist->length() << endl;
        plist->get(1, &tmp);
        cout << "第1个元素为：";
        tmp.printNode();
    
        Node find;
        find.data = 2;
        cout << "元素为2的位置是：" << plist->locate(&find) << endl;
    
        Node pre;
        find.data = 1;
        plist->preElem(&find, &pre);
        cout << "1的上一个是" << pre.data << endl;
    
        Node next;
        plist->nextElem(&find, &next);
        cout << "1的下一个是" << next.data << endl;
    
    
        delete plist;
        plist = NULL;
    
        system("pause");
        return 0;
    
    }