本文将用C++语言来实现数据结构中的无头单链表,带头循环链表,以及带头循环双向链表等链表结构(带头单链表与后两种链表的结构相似,实现起来比后两种更简单,读者阅读完本文即可自行实现)
一、无头单链表的实现
无头单链表在头插时需要改变头指针的位置,具体代码实现如下:
//无头单链表
#include <iostream>
#include <assert.h>
using namespace std;
template <class T>
//先定义链表中的节点
struct SListNode
{
T data;
SListNode* next;
SListNode(T x)
{
this->data = x;
this->next = nullptr;
}
};
template <class T>
class SList
{
private:
//链表初始化后链表中就有一个节点
SListNode<T>* head;
public:
SList(T x)
{
this->head = new SListNode<T>(x);
}
~SList()
{
SListNode<T>* cur = head;
while (cur)
{
SListNode<T>* next = cur->next;
delete cur;
cur = next;
}
}
// 动态申请一个节点
SListNode<T>* BuySListNode(T x);
// 单链表打印
void SListPrint();
// 单链表尾插
void SListPushBack(T x);
// 单链表的头插
void SListPushFront(T x);
// 单链表的尾删
void SListPopBack();
// 单链表头删
void SListPopFront();
// 单链表查找
SListNode<T>* SListFind(T x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode<T>* pos, T x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode<T>* pos);
};
template <class T>
SListNode<T>* SList<T>:: BuySListNode(T x)
{
SListNode<T>* tmp = new SListNode<T>(x);
tmp->next = nullptr;
return tmp;
}
template <class T>
void SList<T>::SListPrint()
{
SListNode<T>* cur =head;
while (cur)
{
cout << cur->data << "->";
cur = cur->next;
}
cout << "NULL" << endl;
}
template <class T>
void SList<T>::SListPushBack(T x)
{
SListNode<T>* cur = head;
while (cur->next)
{
cur = cur->next;
}
SListNode<T>* newnode = BuySListNode(x);
cur->next = newnode;//连接
}
template <class T>
void SList<T>::SListPushFront(T x)
{
SListNode<T>* newnode = BuySListNode(x);
newnode->next = head;
head = newnode;
}
template <class T>
void SList<T>::SListPopBack()
{
assert(head);//头结点为空就不能继续删除了
SListNode<T>* tail = head;
//链表中只有一个节点就只能删除头结点
if (tail->next == nullptr)
{
delete head;
}
else
{
while (tail->next->next != NULL)
{
tail = tail->next;
}
delete tail->next;
tail->next = nullptr;
}
}
template <class T>
void SList<T>::SListPopFront()
{
assert(head);
SListNode<T>* cur = head->next;
delete head;
head = cur;
}
template <class T>
SListNode<T>* SList<T>::SListFind(T x)
{
assert(head);
SListNode<T>* cur = head;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return nullptr;
}
template <class T>
void SList<T>::SListInsertAfter(SListNode<T>* pos, T x)
{
assert(pos);
SListNode<T>* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
template <class T>
void SList<T>::SListEraseAfter(SListNode<T>* pos)
{
assert(pos->next && pos);
SListNode<T>* cur = pos->next;
pos->next = pos->next->next;
delete cur;
}
int main()
{
SList<int> cur(1);
cur.SListPushBack(2);
cur.SListPushBack(3);
cur.SListPushBack(4);
cur.SListPushBack(5);
cur.SListPushBack(6);
cur.SListPrint();
cur.SListPopFront();
cur.SListPrint();
cur.SListPopBack();
cur.SListPrint();
SListNode<int>* p1 = cur.SListFind(2);
cur.SListInsertAfter(p1, 20);
cur.SListPrint();
cur.SListEraseAfter(p1);
cur.SListPrint();
return 0;
}
二、带头循环链表的实现
带头意味着链表中会一直存在着一个头结点,无论链表的插入还是删除都是对头结点后面的节点进行的操作。头插的节点也是直接连接在头结点的下一个结点,不会改变头结点。循环意味着尾节点的next指针指向头节点,就像是形成了一个环一样。
具体实现代码如下:文章来源:https://www.uudwc.com/A/4rnnM/
#include <iostream>
#include <assert.h>
using namespace std;
template <class T>
struct Node
{
T data;
struct Node* next;
Node()
{
this->data = 0;
this->next = nullptr;
}
Node(T data)
{
this->data = data;
this->next = nullptr;
}
};
template <class T>
class SList
{
private:
Node<T>* head;
Node<T>* tail;
public:
SList()
{
this->head = new Node<T>();
this->tail = head;
}
~SList()
{
Node<T>* p = head;
Node<T>* q = head;
while (p != tail)
{
q = p->next;
delete p;
p = q;
}
delete tail;
}
// 动态申请一个节点
Node<T>* BuySListNode(T x);
// 单链表打印
void SListPrint();
// 单链表尾插
void SListPushBack(T x);
// 单链表的头插
void SListPushFront(T x);
// 单链表的尾删
void SListPopBack();
// 单链表头删
void SListPopFront();
// 单链表查找
Node<T>* SListFind( T x);
// 单链表在pos位置之后插入x
void SListInsertAfter(Node<T>* pos, T x);
// 单链表删除pos位置之后的值
void SListEraseAfter(Node<T>* pos);
};
template <class T>
Node<T>* SList<T>::BuySListNode(T x)
{
Node<T>* tmp = new Node<T>;
tmp->data = x;
tmp->next = nullptr;
return tmp;
}
template <class T>
void SList<T>::SListPrint()
{
assert(head->next);//保证头节点后还有结点才打印,不然报错
Node<T>* cur = head->next;
while (cur != head)
{
cout << cur->data << "->";
cur = cur->next;
}
cout << "NULL" << endl;
}
template <class T>
void SList<T>::SListPushBack(T x)
{
Node<T>* newnode = BuySListNode(x);
tail->next = newnode;
tail = newnode;
tail->next = head;//尾节点的next指向头节点
}
template <class T>
void SList<T>::SListPushFront(T x)
{
Node<T>* newnode = BuySListNode(x);
if (head == tail)
{
head->next = newnode;
tail = newnode;
tail->next = head;
}
else
{
newnode->next = head->next;
head->next = newnode;
}
}
template <class T>
void SList<T>::SListPopBack()
{
assert(head->next);
Node<T>* cur = head;
while (cur->next != tail)
{
cur = cur->next;
}
delete tail;
tail = cur;
tail->next = head;
}
template <class T>
void SList<T>::SListPopFront()
{
assert(head->next);
Node<T>* cur = head->next;
if (head->next == tail)
{
delete tail;
tail = head;
}
else
{
head->next = cur->next;
delete cur;
}
}
template <class T>
Node<T>* SList<T>::SListFind(T x)
{
assert(head->next);
Node<T>* cur = head->next;
while (cur != head)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return nullptr;
}
template <class T>
void SList<T>::SListInsertAfter(Node<T>* pos, T x)
{
assert(pos);
if (pos->next == head)
{
SListPushBack(x);
}
else if(pos == head)
{
SListPushFront(x);
}
else
{
Node<T>* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
}
template <class T>
void SList<T>::SListEraseAfter(Node<T>* pos)
{
assert(pos);
//尾节点后的头节点不能删
if (pos->next == head)
{
exit(-1);
}
else if (pos == head)
{
SListPopFront();
}
else
{
Node<T>* cur = pos->next;
pos->next = pos->next->next;
delete cur;
}
}
int main()
{
SList<int> SL1;
SL1.SListPushBack(1);
SL1.SListPushBack(2);
SL1.SListPushBack(3);
SL1.SListPushBack(4);
SL1.SListPushBack(5);
SL1.SListPrint();
SL1.SListPushFront(10);
SL1.SListPrint();
SL1.SListPopFront();
SL1.SListPrint();
SL1.SListPopBack();
SL1.SListPrint();
Node<int>* cur = SL1.SListFind(2);
SL1.SListInsertAfter(cur, 20);
SL1.SListPrint();
SL1.SListEraseAfter(cur);
SL1.SListPrint();
return 0;
}
三、带头双向循环链表的实现
具体实现思路与带头循环链表大同小异,只是在节点中需要增加一个指向前一个节点的指针。
具体实现代码如下:
#include <iostream>
#include <assert.h>
using namespace std;
template <class T>
struct Node
{
T data;
struct Node* prev;//指向前一个节点的指针
struct Node* next;
Node()
{
this->data = 0;
this->prev = nullptr;
this->next = nullptr;
}
Node(T data)
{
this->data = data;
this->prev = nullptr;
this->next = nullptr;
}
};
template <class T>
class SList
{
private:
Node<T>* head;//头节点
Node<T>* tail;//尾节点
public:
SList()
{
this->head = new Node<T>();
head->next = nullptr;
head->prev = nullptr;
this->tail = head;
}
~SList()
{
Node<T>* p = head;
Node<T>* q = head;
while (p != tail)
{
q = p->next;
delete p;
p = q;
}
delete tail;
}
Node<T>* getHead()
{
return this->head;
}
// 动态申请一个节点
Node<T>* BuySListNode(T x);
// 单链表打印
void SListPrint();
// 单链表尾插
void SListPushBack(T x);
// 单链表的头插
void SListPushFront(T x);
// 单链表的尾删
void SListPopBack();
// 单链表头删
void SListPopFront();
// 单链表查找
Node<T>* SListFind(T x);
// 单链表在pos位置之后插入x
void SListInsertAfter(Node<T>* pos, T x);
// 单链表删除pos位置之后的值
void SListEraseAfter(Node<T>* pos);
};
template <class T>
Node<T>* SList<T>::BuySListNode(T x)
{
Node<T>* tmp = new Node<T>;
tmp->data = x;
tmp->prev = nullptr;
tmp->next = nullptr;
return tmp;
}
template <class T>
void SList<T>::SListPrint()
{
assert(head->next);
Node<T>* cur = head->next;
while (cur != head)
{
cout << cur->data << "<->";
cur = cur->next;
}
cout << endl;
}
template <class T>
void SList<T>::SListPushBack(T x)
{
Node<T>* newnode = BuySListNode(x);
tail->next = newnode;
newnode->prev = tail;
tail = newnode;
tail->next = head;
head->prev = tail;
}
template <class T>
void SList<T>::SListPushFront(T x)
{
Node<T>* newnode = BuySListNode(x);
if (head == tail)//头节点后没有节点
{
head->next = newnode;
newnode->prev = head;
tail = newnode;
tail->next = head;
head->prev = tail;
}
else
{
newnode->next = head->next;
newnode->prev = head;
head->next = newnode;
}
}
template <class T>
void SList<T>::SListPopBack()
{
assert(head->next);
Node<T>* cur = tail->prev;
head->prev = tail->prev;
delete tail;
tail = cur;
tail->next = head;
}
template <class T>
void SList<T>::SListPopFront()
{
assert(head->next);//只剩头节点不删
Node<T>* cur = head->next;
if (head->next == tail)//头节点后只有一个节点
{
delete tail;
tail = head;
head->next = head;
head->prev = head;
}
else
{
head->next = cur->next;
cur->next->prev = head;
delete cur;
}
}
template <class T>
Node<T>* SList<T>::SListFind(T x)
{
assert(head->next);
Node<T>* cur = head->next;
while (cur != head)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return nullptr;
}
template <class T>
void SList<T>::SListInsertAfter(Node<T>* pos, T x)
{
assert(pos);
if (pos->next == head)
{
SListPushBack(x);
}
else if (pos == head)
{
SListPushFront(x);
}
else
{
Node<T>* newnode = BuySListNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next = newnode;
}
}
template <class T>
void SList<T>::SListEraseAfter(Node<T>* pos)
{
assert(pos);
if (pos->next == head)//尾节点后的头节点不删
{
exit(-1);
}
else if (pos == head)
{
SListPopFront();
}
else
{
Node<T>* cur = pos->next;
pos->next = pos->next->next;
pos->next->prev = pos;
delete cur;
}
}
int main()
{
//SListNode<int>* head = new SListNode<int>;
SList<int> SL1;
SL1.SListPushBack(1);
SL1.SListPushBack(2);
SL1.SListPushBack(3);
SL1.SListPushBack(4);
SL1.SListPushBack(5);
SL1.SListPrint();
SL1.SListPushFront(10);
SL1.SListPrint();
SL1.SListPopFront();
SL1.SListPrint();
SL1.SListPopBack();
SL1.SListPrint();
Node<int>* cur = SL1.SListFind(2);
SL1.SListInsertAfter(cur, 20);
SL1.SListPrint();
SL1.SListEraseAfter(cur);
SL1.SListPrint();
return 0;
}
文章来源地址https://www.uudwc.com/A/4rnnM/