数据结构--单链表single linked list（无表头哨兵）重写
针对上次写的单链表中不足的地方进行修改：
1.构造函数需要让用户输入（bad）
2.函数功能不单一，既操作链表，还打印输出（bad）
代码链接（包含无头\有头单链表、循环单链表、双链表、循环双链表）
接口 singleList.h
//
// Created by mingm on 2019/3/18.
//
#ifndef _SINGLELIST_H
#define _SINGLELIST_H
struct SNode //结点的基本数据类型
{
int data;
SNode* pNext;
};
typedef unsigned int UINT;
typedef SNode* ListNode;
class SingleList
{
public:
SingleList(void);
~SingleList(void);
bool IsEmpty() const;//判断链表是否为空
UINT GetLength() const;//获取当前链表的长度
ListNode GetHeadNode() const;//获取链表的头结点
ListNode GetTailNode() const;//获取链表的尾结点
ListNode GetMidNode();//获得链表的中间结点
void AddHead(const int &data);//在链表的头部插入新的结点
void AddTail(const int &data);//在链表的尾部插入新的结点
bool posInList(ListNode pos);//检查节点指针是否在链表中
ListNode InsertAt(ListNode pos, const int &data);//在指定结点前插入数据，并返回新结点的地址
ListNode ModifyAt(ListNode pos, const int &data);//修改指定结点的数据，并返回当前节点的地址
ListNode RemoveAt(ListNode pos);//删除指定结点，并返回被删除结点的下一结点的地址
ListNode RemoveAtBack(UINT nCountBack);//删除倒数第n个节点，并返回被删除结点的下一结点的地址
ListNode Find(const int &data);//在当前链表中找到和要查找数据相等的第一个结点的地址
void Erase();//删除链表的所有结点
void PrintList() const;//打印链表所有结点的数据
void Reverse();//反转链表
private:
ListNode m_pHead; //头结点
UINT m_nListLen; //链表数据长度
};
#endif类实现文件 singleList.cpp
//单向链表（不带头）
// Created by mingm on 2019/3/18.
//
#include "singleList.h"
#include <iostream>
SingleList::SingleList():m_pHead(NULL),m_nListLen(0){}
SingleList::~SingleList()
{
Erase();
}
void SingleList::Erase()
{
if(m_pHead != NULL)
{
ListNode temp = m_pHead, del;
while(temp != NULL)
{
del = temp;
temp = temp->pNext;
delete del;
}
m_pHead = NULL;
m_nListLen = 0;
}
}
bool SingleList::IsEmpty() const
{
return m_pHead == NULL;
}
UINT SingleList::GetLength() const
{
return m_nListLen;
}
ListNode SingleList::GetHeadNode() const
{
return m_pHead;
}
ListNode SingleList::GetTailNode() const
{
if(!m_pHead)
return NULL;
ListNode temp = m_pHead;
while(temp->pNext != NULL)
{
temp = temp->pNext;
}
return temp;
}
ListNode SingleList::GetMidNode() //快慢指针法
{
ListNode fast = m_pHead, slow = m_pHead;
while(fast)
{
if(fast->pNext != NULL)
{
fast = fast->pNext->pNext;
}
else
{
break;
}
slow = slow->pNext;
}
//简洁写法
// while(fast && fast->pNext)
// {
// fast = fast->pNext->pNext;
// slow = slow->pNext;
// }
return slow;
}
void SingleList::AddHead(const int &data)
{
ListNode newNode = new SNode;
newNode->data = data;
newNode->pNext = NULL;
if(m_pHead == NULL)
{
m_pHead = newNode;
}
else
{
newNode->pNext = m_pHead;
m_pHead = newNode;
}
m_nListLen++;
}
void SingleList::AddTail(const int &data)
{
ListNode newNode = new SNode;
newNode->data = data;
newNode->pNext = NULL;
if(m_pHead == NULL)
{
m_pHead = newNode;
}
else
{
GetTailNode()->pNext = newNode;
}
m_nListLen++;
}
bool SingleList::posInList(ListNode pos)
{
if(m_pHead == NULL)
return false;
else
{
ListNode temp = m_pHead;
while(temp && temp != pos)
{
temp = temp->pNext;
}
if(temp == NULL) //指针地址不在链表内
return false;
else
return true;
}
}
ListNode SingleList::InsertAt(ListNode pos, const int &data)
{
if(pos == NULL)
return NULL;
else if(pos == m_pHead)
{
AddHead(data);
return m_pHead;
}
else
{
ListNode temp = m_pHead;
ListNode preNode = NULL;
while(temp && temp != pos)
{
preNode = temp;
temp = temp->pNext;
}
if(temp == NULL) //指针地址不在链表内
return NULL;
else
{
ListNode newNode = new SNode;
newNode->data = data;
newNode->pNext = NULL;
newNode->pNext = pos;
preNode->pNext = newNode;
m_nListLen++;
return newNode;
}
}
}
ListNode SingleList::ModifyAt(ListNode pos, const int &data)
{
if(!posInList(pos))
return NULL;
else
{
pos->data = data;
return pos;
}
}
ListNode SingleList::RemoveAt(ListNode pos)
{
if(!posInList(pos))
return NULL;
else
{
ListNode temp = m_pHead;
if(pos == m_pHead)
{
temp = pos->pNext;
delete pos;
m_nListLen--;
m_pHead = temp;
return temp;
}
else
{
while(temp->pNext != pos)
{
temp = temp->pNext;
}
temp->pNext = pos->pNext;
delete pos;
m_nListLen--;
return temp->pNext;
}
}
}
ListNode SingleList::RemoveAtBack(UINT nCountBack)
//先让快指针先走n-1步，然后快慢指针一起动，快指针到达尾部，慢指针指向倒数第n个
{
if(nCountBack == 0 || nCountBack > m_nListLen)
return NULL;
else
{
ListNode fast = m_pHead;
ListNode slow = m_pHead;
for(int i = 0; i < nCountBack-1 && fast; ++i)
{
fast = fast->pNext;
}
while(fast->pNext)
{
fast = fast->pNext;
slow = slow->pNext;
}
fast = RemoveAt(slow);
return fast;
}
}
ListNode SingleList::Find(const int &data)
{
ListNode temp = m_pHead;
while(temp && temp->data != data)
{
temp = temp->pNext;
}
return temp;
}
void SingleList::PrintList() const
{
std::cout << "----- print start ----" << std::endl;
ListNode temp = m_pHead;
for(int i = 0; i < m_nListLen && temp; ++i)
{
std::cout << "No. " << i+1 << " node is " << temp->data << std::endl;
temp = temp->pNext;
}
std::cout << "----- print end ----" << std::endl;
}
void SingleList::Reverse() //就地反转法
{
if(m_pHead && m_pHead->pNext)
{
ListNode preNode, curNode, tempNode;
preNode = curNode = tempNode = m_pHead;
curNode = preNode->pNext;
preNode->pNext = NULL;
while(curNode->pNext)
{
tempNode = curNode;
curNode = curNode->pNext;
tempNode->pNext = preNode;
preNode = tempNode;
}
curNode->pNext = preNode;
m_pHead = curNode;
}
}测试主程序 test_singleList.cpp
测试程序包含长度从0开始的 list，以便检查边界情况下程序是否正常运行。
//
// Created by mingm on 2019/3/20.
//
#include "singleList.cpp"
#include <iostream>
using namespace std;
int main()
{
for(int k = 0; k < 5; ++k)
{
cout << "------------ test start ----------------" << endl;
SingleList intList;
if(intList.IsEmpty())
cout << "empty list!" << endl;
cout << intList.GetLength() << " node(s) !" << endl;
cout << "---------------" << endl;
cout << "add 0 to " << k-1 << " into list: " << endl;
for(int j = 0; j < k; ++j)
{
intList.AddTail(j);
}
cout << intList.GetLength() << " node(s) !" << endl;
intList.PrintList();
cout << "------------- reverse list" << endl;
intList.Reverse();
intList.PrintList();
if(intList.GetHeadNode())
{
cout << "head node: " << intList.GetHeadNode()->data << endl;
cout << "tail node: " << intList.GetTailNode()->data << endl;
cout << "middle node: " << intList.GetMidNode()->data << endl;
}
cout << "--------------- addTail " << k << endl;
intList.AddTail(k);
intList.PrintList();
if(intList.posInList(intList.GetMidNode()))
cout << "midNode in List !" << endl;
cout << "100 insert at midNode ";
if(intList.GetMidNode())
cout << intList.GetMidNode()->data ;
cout << " front " << endl;
intList.InsertAt(intList.GetMidNode(),100);
intList.PrintList();
cout << "modify head to 99 " << endl;
intList.ModifyAt(intList.GetHeadNode(),99);
intList.PrintList();
cout << "del Tail" << endl;
intList.RemoveAt(intList.GetTailNode());
intList.PrintList();
cout << "del the " << intList.GetLength()-1 << "th node count from end !" << endl;
intList.RemoveAtBack(intList.GetLength()-1);
intList.PrintList();
cout << "address of first " << k-3 << " is ";
if(intList.Find(k-3))
cout << intList.Find(k-3) << endl;
else
cout << "not exits !" << endl;
}
return 0;
}Valgrind检查内存是否泄漏（部分结果展示如下）