数据结构学习笔记5——双向链表(链表源码+测试源码)

曾经终败给现在 2022-09-07 15:53 223阅读 0赞

# 1.DoubleLinkList.h  #

#ifndef DOUBLELINKLIST_H
    #define DOUBLELINKLIST_H
    
    #include <iostream>
    using namespace std;
    
    typedef struct LNode
    {
    public:
        int m_iValue;
        LNode* m_pNext;
        LNode* m_pPre;
    
        LNode()
        {
            m_iValue = 0;
            m_pNext = nullptr;
            m_pPre = nullptr;
        }
    
    }LNode;
    
    class DoubleLinkList
    {
    public:
        DoubleLinkList()
        {
            Init();
        }
    
        ~DoubleLinkList()
        {
            LNode *pNode = m_pHeadNode->m_pNext;
            while (pNode)
            {
                m_pHeadNode->m_pNext = pNode->m_pNext;
                delete pNode;
                pNode = m_pHeadNode->m_pNext;
            }
    
            delete m_pHeadNode;
            m_pHeadNode->m_pNext = nullptr;
        }
    
        bool Init()
        {
            m_pHeadNode = new LNode;
            m_pTailNode = new LNode;
            if (!m_pHeadNode || !m_pTailNode)
            {
                return false;
            }
    
            m_pHeadNode->m_pNext = m_pTailNode;
            m_pTailNode->m_pPre = m_pHeadNode;
            return true;
        }
    
        //添加元素(后插法)
        bool Append(int iValue)
        {
            if (!m_pHeadNode || !m_pTailNode)
            {
                return false;
            }
    
            LNode *pNewNode = new LNode;
            pNewNode->m_iValue = iValue;
            pNewNode->m_pNext = m_pTailNode;
            pNewNode->m_pPre = m_pTailNode->m_pPre;
            m_pTailNode->m_pPre->m_pNext = pNewNode;
            m_pTailNode->m_pPre = pNewNode;
            return true;
        }
    
        //添加元素(前插法)
        bool PrePend(int iValue)
        {
            if (!m_pHeadNode || !m_pTailNode)
            {
                return false;
            }
    
            LNode *pNewNode = new LNode;
            pNewNode->m_iValue = iValue;
            
            pNewNode->m_pPre = m_pHeadNode;
            pNewNode->m_pNext = m_pHeadNode->m_pNext;
            m_pHeadNode->m_pNext->m_pPre = pNewNode;
            m_pHeadNode->m_pNext = pNewNode;
    
            return true;
        }
    
    
        //获取元素
        LNode* GetAt(int iIndex)
        {
            if (!m_pHeadNode || !m_pTailNode)
            {
                return nullptr;
            }
    
            int iCnt = 1;
            LNode *pNode = m_pHeadNode->m_pNext;
            while (pNode && (iCnt <= iIndex) && (pNode != m_pTailNode))
            {
                if (iIndex == iCnt)
                {
                    return pNode;
                }
    
                pNode = pNode->m_pNext;
                iCnt++;
            }
    
            return nullptr;
        }
    
        //查找元素
        LNode *Find(int iValue)
        {
            if (!m_pHeadNode || !m_pTailNode)
            {
                return nullptr;
            }
    
            LNode *pNode = m_pHeadNode->m_pNext;
            while (pNode && (pNode != m_pTailNode))
            {
                if (iValue == pNode->m_iValue)
                {
                    return pNode;
                }
    
                pNode = pNode->m_pNext;
            }
    
            return nullptr;
        }
    
        //删除元素
        bool Delete(int iIndex)
        {
            if (!m_pHeadNode || !m_pTailNode)
            {
                return nullptr;
            }
    
            int iCurIndex = 1;
            LNode *pNode = m_pHeadNode->m_pNext;
            while (pNode && (iCurIndex <= iIndex) && (pNode != m_pTailNode))
            {
                if (iIndex == iCurIndex)
                {
                    pNode->m_pPre->m_pNext = pNode->m_pNext;
                    pNode->m_pNext->m_pPre = pNode->m_pPre;                
                    delete pNode;
                    pNode = nullptr;
                    return true;
                }
    
                pNode = pNode->m_pNext;
                iCurIndex++;
            }
    
            return false;
        }
    
        //顺序打印链表中的所有元素
        void ShowAllElement()
        {
            LNode *pNode = m_pHeadNode->m_pNext;
            cout << "\n如下是链表中的所有元素:\n" << "  前一个节点  " << "  当前节点  " 
                << "  当前节点的值  " << "下一个节点\n";
            while (pNode && (pNode != m_pTailNode))
            {
                cout<< pNode->m_pPre <<"      " << pNode << "      " << pNode->m_iValue 
                    << "           " << pNode->m_pNext << endl;
                pNode = pNode->m_pNext;
            }
    
            cout << "\n";
        }
    
        //逆序打印链表中的所有元素
        void ShowAllReverse()
        {
            LNode *pNode = m_pTailNode->m_pPre;
            cout << "\n如下是链表中的所有元素:\n" << "  前一个节点  " << "  当前节点  "
                << "  当前节点的值  " << "下一个节点\n";
            while (pNode && (pNode != m_pHeadNode))
            {
                cout << pNode->m_pPre << "      " << pNode << "      " << pNode->m_iValue
                    << "           " << pNode->m_pNext << endl;
                pNode = pNode->m_pPre;
            }
    
            cout << "\n";
        }
    
        //打印某一个元素的信息
        void ShowElement(LNode *pNode)
        {
            if (pNode)
            {
                cout << "\n元素信息如下:\n" << "  前一个节点  " << "  当前节点  " << "  当前节点的值  " 
                    << "下一个节点\n";
                cout << pNode->m_pPre << "      " << pNode << "      " << pNode->m_iValue 
                    << "           " << pNode->m_pNext << endl;
                cout << "\n";
            }
        }
    
    private:
        LNode *m_pHeadNode;//头节点
        LNode *m_pTailNode;//尾节点
    };
    
    
    
    
    #endif

# 2.main.cpp #

#include "stdafx.h"
    
    #include "DoubleLinkList.h"
    
    int main()
    { 
        DoubleLinkList list;
        while (true)
        {
            cout << "\n请输入操作类型:\n\n1.添加元素-前插\n\n2.添加元素-后插\n\n3.获取指定位置的元素\n\n4.查找指定值的元素\n\n"
                "5.删除指定位置的元素\n\n6.顺序打印所有元素信息\n\n7.逆序打印所有元素信息\n\n";
            int i = 0;
            cin >> i;
            switch (i)
            {
                case 1://添加元素-前插
                {
                    cout << "\n请输入要插入的数值:\n";
                    int m;
                    cin >> m;
                    list.PrePend(m);
                }break;
                case 2://添加元素-后插
                {
                    cout << "\n请输入要插入的数值:\n";
                    int m;
                    cin >> m;
                    list.Append(m);
                }break;
                case 3://获取指定位置的值
                {
                    cout << "\n请输入下标:\n";
                    int m;
                    cin >> m;
                    LNode* pNode = list.GetAt(m);
                    if (pNode)
                    {
                        cout << "获取成功！\n";
                        list.ShowElement(pNode);
                    }
                    else
                    {
                        cout << "获取失败！\n";
                    }
                }break;
                case 4://查找指定值的元素
                {
                    cout << "\n请输入要查找的数值:\n";
                    int m;
                    cin >> m;
                    LNode* pNode = list.Find(m);
                    if (pNode)
                    {
                        cout << "查找成功！\n";
                        list.ShowElement(pNode);
                    } 
                    else
                    {
                        cout << "查找失败！\n";
                    }            
                }break;
                case 5://删除指定位置的元素
                {
                    cout << "\n请输入下标:\n";
                    int m;
                    cin >> m;
                    list.Delete(m);
                }break;
                case 6://顺序打印所有元素
                {
                    list.ShowAllElement();
                }break;
                case 7://逆序打印所有元素
                {
                    list.ShowAllReverse();
                }break;
                default:
                {
                    cout << "\n输入值不符合要求!\n";
                }
                break;
            }
        }
        
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70]: /images/20220829/d0f434c0cd4c434e9092326b6b1589d2.png