C/C++链表的常用操作实现

C/C++链表的常用操作实现

  链表的存储结构为一个节点连着下一个节点(node)，节点包括两个域，数据域和指针域。

struct Node
{int m_nElement;				// 数据域Node* m_pNext;				// 指针域Node(int nElement = 0, Node* pNext = nullptr):m_nElement(nElement), m_pNext(pNext){// ...}
};

链表操作

• 1.初始化链表
• 2.判断链表是否为空
• 3.按序号查找
• 4.查找元素与e相等的节点
• 5.定位操作，确定节点在单链表中的序号
• 6.在第 index 个位置插入元素
• 7.删除第 index 个节点
• 8.求链表长度
• 9.清空链表

链表实现代码

// 链表节点
struct Node
{int m_nElement;Node* m_pNext;Node(int nElement = 0, Node* pNext = nullptr):m_nElement(nElement), m_pNext(pNext){// ...}
};// 链表类
class LinkedList
{
public:LinkedList();~LinkedList();public:void Initialize();                              // 初始化链表bool IsEmpty() const;                           // 判断链表是否为空Node* GetNodeByIndex(int nIndex);               // 按序号查找Node* GetNodeByElement(int nElement);           // 查找元素与e相等的节点int GetIndexByElement(int nElement);            // 定位操作，确定节点在单链表中的序号bool Insert(int nIndex, int nElement);          // 在第 index 个位置插入元素bool Delete(int nIndex, int& nElement);         // 删除第 index 个节点int Length();                                   // 求链表长度void Release();                                 // 清空链表void Print();                                   // 打印链表 (在Qt环境下使用 qDebug() 实现)private:Node* m_pHead;
};// 链表类成员函数实现
LinkedList::LinkedList() : m_pHead(nullptr)
{// ...
}LinkedList::~LinkedList()
{Release();
}void LinkedList::Initialize()
{if (nullptr == m_pHead)m_pHead = new Node();
}bool LinkedList::IsEmpty() const
{if (nullptr == m_pHead)return true;return (nullptr == m_pHead->m_pNext);
}Node* LinkedList::GetNodeByIndex(int nIndex)
{Node* pCurNode = m_pHead;for (int i = 0; i > nIndex; ++i){if (nullptr == pCurNode)return nullptr;pCurNode = pCurNode->m_pNext;}return pCurNode;
}Node* LinkedList::GetNodeByElement(int nElement)
{if (nullptr == m_pHead)return nullptr;Node* pCurNode = m_pHead;while (nullptr != pCurNode->m_pNext){pCurNode = pCurNode->m_pNext;if (nElement == pCurNode->m_nElement)return pCurNode;}return nullptr;
}int LinkedList::GetIndexByElement(int nElement)
{if (nullptr == m_pHead)return -1;Node* pCurNode = m_pHead;int nIndex = -1;while (nullptr != pCurNode->m_pNext){pCurNode = pCurNode->m_pNext;++nIndex;if (nElement == pCurNode->m_nElement)return nIndex;}return -1;
}bool LinkedList::Insert(int nIndex, int nElement)
{if (nullptr == m_pHead)Initialize();if (nIndex > Length())return false;Node* pPreNode = nullptr;Node* pCurNode = m_pHead;for (int i = 0; i <= nIndex; ++i){pPreNode = pCurNode;pCurNode = pCurNode->m_pNext;}pPreNode->m_pNext = new Node(nElement, pCurNode);return true;
}bool LinkedList::Delete(int nIndex, int &nElement)
{if (nullptr == m_pHead)return false;if (nIndex >= Length())return false;Node* pPreNode = nullptr;Node* pCurNode = m_pHead;for (int i = 0; i <= nIndex; ++i){pPreNode = pCurNode;pCurNode = pCurNode->m_pNext;}nElement = pCurNode->m_nElement;pPreNode->m_pNext = pCurNode->m_pNext;delete  pCurNode;return true;
}int LinkedList::Length()
{if (nullptr == m_pHead)return 0;Node* pCurNode = m_pHead;int nLength = 0;while (nullptr != pCurNode->m_pNext){pCurNode = pCurNode->m_pNext;++nLength;}return nLength;
}void LinkedList::Release()
{Node* pCurNode = m_pHead;while (pCurNode){Node* pNode = pCurNode;pCurNode = pCurNode->m_pNext;delete pNode;}m_pHead = nullptr;
}void LinkedList::Print()
{if (nullptr == m_pHead){qDebug() << "Empty Linked List!";return;}Node* pCurNode = m_pHead->m_pNext;QString strInfo("[");while (nullptr != pCurNode){strInfo.append(QString::number(pCurNode->m_nElement) + ((nullptr != pCurNode->m_pNext) ? QString(", ") : QString("]")));pCurNode = pCurNode->m_pNext;}qDebug() << strInfo;
}