乐趣区

C实现简单的单链表

使用 C ++ 实现简单 (阉割版) 的单链表:
实现的功能有:插入节点、删除节点、查找、显示列表。

#ifndef FORWARDLIST_H_
#define FORWARDLIST_H_

#include <iostream>
using std::cout;
using std::endl;

template<class T>
struct ListNode
{
    T m_data;
    ListNode<T>* m_pNext;
};

template<class T>
class ForwardList
{
public:
    ForwardList(const ListNode<T>* node);
    ~ForwardList();
    // 在 pos 位置节点后边插入节点 node
    void Insert(ListNode<T>* pos, const ListNode<T>* node); 
    // 删除位于 pos 位置的节点
    ListNode<T> Delete(ListNode<T>* pos); 
    // 删除所有值为 value 的节点
    void Delete(const T& value); 
    // 按值查找
    ListNode<T>* Find(const ListNode<T>* node); 
    // 按位置查找
    ListNode<T>* Find(int idx); 
    // 显示整个列表
    void PrintList();

    int size()
    {return count;}

    // 返回头节点
    ListNode<T>* Head() 
    {return m_pHead;}
private:
    ListNode<T>* m_pHead;
    int count;
};

template<class T>
ForwardList<T>::ForwardList(const ListNode<T>* node)
{
    m_pHead = new ListNode<T>;
    m_pHead->m_data = node->m_data;
    m_pHead->m_pNext = nullptr;
    count = 1;
}

template<class T>
ForwardList<T>::~ForwardList()
{
    ListNode<T>* pos;    
    while (m_pHead != nullptr)
    {
        pos = m_pHead;
        m_pHead = m_pHead->m_pNext;
        delete pos;
    }
}

template<class T>
void ForwardList<T>::Insert(ListNode<T>* pos, const ListNode<T>* node) 
{
    ListNode<T>* temp = new ListNode<T>;
    temp->m_data = node->m_data;
    temp->m_pNext = pos->m_pNext;
    pos->m_pNext = temp;
    count++;
}

template<class T>
ListNode<T> ForwardList<T>::Delete(ListNode<T>* pos)  
{
    ListNode<T> ret;
    ListNode<T>* temp;
    temp = m_pHead;
    if (temp == pos)
    {
        m_pHead = m_pHead->m_pNext;
        ret.m_data = temp->m_data;
        ret.m_pNext = nullptr;
        delete temp;
        count--;
        return ret;
    }
    while (temp->m_pNext != pos)
    {temp = temp->m_pNext;}    
    ret.m_data = temp->m_pNext->m_data;
    ret.m_pNext = temp->m_pNext->m_pNext;
    delete temp->m_pNext;
    temp->m_pNext = ret.m_pNext;
    ret.m_pNext = nullptr;
    count--;
    return ret;
}

template<class T>
void ForwardList<T>::Delete(const T& value)  
{
    ListNode<T>* temp;
    ListNode<T> ret;
    temp = m_pHead;
    while (m_pHead != nullptr && m_pHead->m_data == value)
    {    
        m_pHead = m_pHead->m_pNext;
        delete temp;
        count--;
        temp = m_pHead;
    }
    while (temp != nullptr)
    {if (temp->m_pNext != nullptr && temp->m_pNext->m_data == value)
        {
            ret.m_pNext = temp->m_pNext;
            temp->m_pNext = temp->m_pNext->m_pNext;
            delete ret.m_pNext;
            count--;
        }
        else
        {temp = temp->m_pNext;}
    }
}

template<class T>
ListNode<T>* ForwardList<T>::Find(const ListNode<T>* node)
{
    ListNode<T>* pos = m_pHead;
    while (pos != nullptr && pos->m_data != node->m_data)
    {pos = pos->m_pNext;}
    return pos;

}

template<class T>
ListNode<T>* ForwardList<T>::Find(int idx) 
{if (idx >= count || idx < 0)
    {
        cout << "索引溢出!\n";
        return nullptr;
    }
    ListNode<T>* pos = m_pHead;
    int i = 0;
    while (i < idx)
    {
        pos = pos->m_pNext;
        i++;
    }
    return pos;
}

template<class T>
void ForwardList<T>::PrintList()
{
    ListNode<T>* pos = m_pHead;
    while (pos != nullptr)
    {
        cout << pos->m_data << endl;
        pos = pos->m_pNext;
    }
}
#endif

测试代码:

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

using namespace std;

int main()
{ListNode<string> head{ "0000", nullptr};
    ListNode<string> n1{"0001", nullptr};
    ListNode<string> n2{"0002", nullptr};
    ListNode<string> n3{"0003", nullptr};
    ListNode<string> n4{"0004", nullptr};
    ListNode<string> n5{"0005", nullptr};

    ForwardList<string> mfl(&head);

    mfl.PrintList();
    cout << endl;

    mfl.Insert(mfl.Head(), &n1);
    mfl.Insert(mfl.Head(), &n2);
    mfl.Insert(mfl.Head(), &n3);
    mfl.Insert(mfl.Head(), &n4);
    mfl.PrintList();
    cout << endl;

    cout << mfl.Find(2)->m_data << endl << endl;

    mfl.Insert(mfl.Find(&n2), &n5);
    mfl.PrintList();
    cout << endl;

    mfl.Delete("0000");
    mfl.Delete("0001");
    mfl.Delete(mfl.Find(&n5));
    mfl.PrintList();
    cout << endl;

    system("pause");
    return 0;
}

~~

退出移动版