数据结构学习笔记4——单链表(链表实现源码+功能测试源码)

た入场券 2022-09-07 14:33 166阅读 0赞

# 1.数据存储结构 #

typedef struct LNode
    {
    public:
        int m_iValue;
        LNode* m_pNext;
    
        LNode()
        {
            m_iValue = 0;
            m_pNext = NULL;
        }    
    
    }LNode,*LinkList;

# 2.封装数据的基本操作 #

class MyList
    {
    public:
        MyList()
        {
            Init();
        }
    
        bool Init()
        {
            m_pHeadNode = new LNode;
            if (!m_pHeadNode)
            {
                return false;
            }
    
            m_pHeadNode->m_pNext = NULL;
            return true;
        }
    
        //添加元素(后插法)
        bool Append(int iValue)
        {
            if (!m_pHeadNode)
            {
                return false;
            }
    
            LNode **pNodeAddr = &m_pHeadNode->m_pNext;
            while (*pNodeAddr)
            {
                pNodeAddr = &((*pNodeAddr)->m_pNext);
            }
    
            LNode *pNewNode = new LNode;
            pNewNode->m_iValue = iValue;
            pNewNode->m_pNext = NULL;
            *pNodeAddr = pNewNode;
            return true;
        }
    
        //添加元素(前插法)
        bool PrePend(int iValue)
        {
            if (!m_pHeadNode)
            {
                return false;
            }
    
            LNode *pNewNode = new LNode;
            pNewNode->m_iValue = iValue;
            if (m_pHeadNode->m_pNext)
            {
                pNewNode->m_pNext = m_pHeadNode->m_pNext;
            }
            else
            {
                pNewNode->m_pNext = NULL;
            }
    
            m_pHeadNode->m_pNext = pNewNode;
            return true;
        }
    
    
        //获取元素
        LNode* GetAt(int iIndex)
        {
            if (!m_pHeadNode)
            {
                return NULL;
            }
    
            int iCnt = 1;
            LNode *pNode = m_pHeadNode->m_pNext;
            while (pNode && (iCnt <= iIndex))
            {
                if (iIndex == iCnt)
                {
                    return pNode;
                }
    
                pNode = pNode->m_pNext;
                iCnt++;
            }
    
            return NULL;
        }
    
        //查找元素
        LNode *Find(int iValue)
        {
            if (!m_pHeadNode)
            {
                return NULL;
            }
    
            LNode *pNode = m_pHeadNode->m_pNext;
            while (pNode)
            {
                if (iValue == pNode->m_iValue)
                {
                    return pNode;
                }
    
                pNode = pNode->m_pNext;
            }
    
            return NULL;
        }
    
        //删除元素
        bool Delete(int iIndex)
        {
            if (!m_pHeadNode)
            {
                return NULL;
            }
    
            int iCurIndex = 1;
            LNode *pNode = m_pHeadNode->m_pNext;
            LNode *pPreNode = m_pHeadNode;
            while (pNode && (iCurIndex <= iIndex))
            {
                if (iIndex == iCurIndex)
                {
                    pPreNode->m_pNext = pNode->m_pNext;
                    delete pNode;
                    pNode = NULL;
                    return true;
                }
    
                pPreNode = pNode;
                pNode = pNode->m_pNext;
                iCurIndex++;
            }
    
            return false;
        }
    
        void ShowAllElement()
        {
            LNode *pNode = m_pHeadNode->m_pNext;
            cout<< "\n如下是链表中的所有元素:\n" << "当前节点" << "  当前节点的值  " << "下一个节点\n";
            while (pNode)
            {
                cout << pNode << "      " << pNode->m_iValue << "           " << pNode->m_pNext << endl;
                pNode = pNode->m_pNext;
            }
    
            cout << "\n";
        }
    
        void ShowElement(LNode *pNode)
        {        
            if (pNode)
            {
                cout << "\n元素信息如下:\n" << "当前节点" << "  当前节点的值  " << "下一个节点\n";
                cout << pNode << "      " << pNode->m_iValue << "           " << pNode->m_pNext << endl;
                cout << "\n";
            }        
        }
    
    private:
        LinkList m_pHeadNode;
    };

# 3.测试代码 #

#include "stdafx.h"
    #include <iostream>
    using namespace std;
    
    int main()
    { 
        MyList list;
        while (true)
        {
            cout << "\n请输入操作类型:\n\n1.添加元素-前插\n\n2.添加元素-后插\n\n3.获取指定位置的元素\n\n4.查找指定值的元素\n\n"
                "5.删除指定位置的元素\n\n6.显示所有元素\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;
            default:
            {
                cout << "\n输入值不符合要求!\n";
            }
            break;
            }
        }
        
        return 0;
    }

# 4.测试方法 #

把以上所有代码放入main.cpp即可，然后编译运行。程序提供6种操作，输入编号（1-6）执行对应操作。

![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 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70]: /images/20220829/581337a5a3d84fc58a13737f29121620.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 1]: /images/20220829/ae8551efbc084c8ca5bd583108ac5653.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 2]: /images/20220829/58a6c7b48f2c40fab3ba28f67d2b1f68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 3]: /images/20220829/eb82d101ded34c66ad49c35a2aed6297.png