定义
单链表是一种线性数据结构，用一组地址任意存储单元来存储数据，存储单元分散在内存任意地址上，存储单元之间用指针连接。
单链表一般有两种：
- 带头结点的，头结点不存放数据，只是为了操作方便。
- 不带头结点的。
链表只要得到头指针就可以操作每一个结点。
示例
定义
//数据结点
template <typename T>struct linkeNode
{
T data;
linkeNode * next{nullptr};
};
template <typename T> class singlyLinkedList
{
public:
singlyLinkedList()
{
}
~singlyLinkedList()
{
freeAllNode();
}
void append(const T &data);//在末尾插入
void freeOneNode(linkeNode<T> *node);//清空一个结点
void freeAllNode();//清空所有结点
void traverseSequenceList();//遍历
void insert(const unsigned int index, const T &data);//在index处插入一个结点
void removeOne(const unsigned int index);//移除index处的结点
private:
linkeNode<T> * header{nullptr};//首结点指针
};
清除一个结点
//清除一个结点
template <typename T> void singlyLinkedList<T>::freeOneNode(linkeNode<T> * node)
{
node->next = nullptr;
free(node);
}
清除所有结点
//清除所有结点
template <typename T> void singlyLinkedList<T>::freeAllNode()
{
if(header)
{
linkeNode<T> * thisNode = header;
while (thisNode)
{
linkeNode<T> * p = thisNode->next;
freeOneNode(thisNode);
thisNode = p;
}
header = nullptr;
}
}
在末尾插入?
//在末尾插入
template <typename T> void singlyLinkedList<T>::append(const T & data)
{
if(!header)
{
header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
header->data = data;
header->next = nullptr;
return;
}
linkeNode<T> * thisNode = header;
while (thisNode)
{
if(thisNode->next)
{
thisNode = thisNode->next;
}
else
{
linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
node->data = data;
node->next = nullptr;
thisNode->next = node;
break;
}
}
}
遍历?
//遍历
template <typename T> void singlyLinkedList<T>::traverseSequenceList()
{
if(header)
{
linkeNode<T> * thisNode = header;
int index = {0};
while (thisNode)
{
qDebug()<<"index = "<<index<< thisNode->data;
if(!thisNode->next)
{
break;
}
thisNode = thisNode->next;
++index;
}
}
}
在index处插入?
//在index处插入
template <typename T> void singlyLinkedList<T>::insert(const unsigned int index, const T &data)
{
if(!header)
{
header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
header->data = data;
header->next = nullptr;
return;
}
linkeNode<T> * thisNode = header;
int currentIndex = {1};
while (thisNode)
{
if(currentIndex == index)
{
linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
node->data = data;
linkeNode<T> * newNodeNext = thisNode->next;
thisNode->next = node;
node->next = newNodeNext;
break;
}
thisNode = thisNode->next;
++currentIndex;
}
}
删除index处的数据?
//删除index处的数据
template <typename T> void singlyLinkedList<T>::removeOne(const unsigned int index)
{
if(!header)
{
return;
}
if(index == 0)
{
linkeNode<T> * headerNextNode = header->next;
freeOneNode(header);
header = headerNextNode;
return;
}
linkeNode<T> * thisNode = header;
linkeNode<T> * lastNode = nullptr;
int currentIndex = {0};
while (thisNode)
{
if(currentIndex == index)
{
linkeNode<T> * willRemoveNode = thisNode;
lastNode->next = thisNode->next;
freeOneNode(willRemoveNode);
break;
}
lastNode = thisNode;
thisNode = thisNode->next;
++currentIndex;
}
}
汇总
#include <QDebug>
//数据结点
template <typename T>struct linkeNode
{
T data;
linkeNode * next{nullptr};
};
template <typename T> class singlyLinkedList
{
public:
singlyLinkedList()
{
}
~singlyLinkedList()
{
freeAllNode();
}
void append(const T &data);//在末尾插入
void freeOneNode(linkeNode<T> *node);//清空一个结点
void freeAllNode();//清空所有结点
void traverseSequenceList();//遍历
void insert(const unsigned int index, const T &data);//在index处插入一个结点
void removeOne(const unsigned int index);//移除index处的结点
private:
linkeNode<T> * header{nullptr};//首结点指针
};
//清除一个结点
template <typename T> void singlyLinkedList<T>::freeOneNode(linkeNode<T> * node)
{
node->next = nullptr;
free(node);
}
//清除所有结点
template <typename T> void singlyLinkedList<T>::freeAllNode()
{
if(header)
{
linkeNode<T> * thisNode = header;
while (thisNode)
{
linkeNode<T> * p = thisNode->next;
freeOneNode(thisNode);
thisNode = p;
}
header = nullptr;
}
}
//在末尾插入
template <typename T> void singlyLinkedList<T>::append(const T & data)
{
if(!header)
{
header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
header->data = data;
header->next = nullptr;
return;
}
linkeNode<T> * thisNode = header;
while (thisNode)
{
if(thisNode->next)
{
thisNode = thisNode->next;
}
else
{
linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
node->data = data;
node->next = nullptr;
thisNode->next = node;
break;
}
}
}
//遍历
template <typename T> void singlyLinkedList<T>::traverseSequenceList()
{
if(header)
{
linkeNode<T> * thisNode = header;
int index = {0};
while (thisNode)
{
qDebug()<<"index = "<<index<< thisNode->data;
if(!thisNode->next)
{
break;
}
thisNode = thisNode->next;
++index;
}
}
}
//在index处插入
template <typename T> void singlyLinkedList<T>::insert(const unsigned int index, const T &data)
{
if(!header)
{
header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
header->data = data;
header->next = nullptr;
return;
}
linkeNode<T> * thisNode = header;
int currentIndex = {1};
while (thisNode)
{
if(currentIndex == index)
{
linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
node->data = data;
linkeNode<T> * newNodeNext = thisNode->next;
thisNode->next = node;
node->next = newNodeNext;
break;
}
thisNode = thisNode->next;
++currentIndex;
}
}
//删除index处的数据
template <typename T> void singlyLinkedList<T>::removeOne(const unsigned int index)
{
if(!header)
{
return;
}
if(index == 0)
{
linkeNode<T> * headerNextNode = header->next;
freeOneNode(header);
header = headerNextNode;
return;
}
linkeNode<T> * thisNode = header;
linkeNode<T> * lastNode = nullptr;
int currentIndex = {0};
while (thisNode)
{
if(currentIndex == index)
{
linkeNode<T> * willRemoveNode = thisNode;
lastNode->next = thisNode->next;
freeOneNode(willRemoveNode);
break;
}
lastNode = thisNode;
thisNode = thisNode->next;
++currentIndex;
}
}
|