概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
值得注意的是：
1.链表的在逻辑是连续的，物理上不一定是连续的；
2.现实中节点是从堆上申请的。
链表的单个结点的定义
就像这个图一样，一个空间用了存放数据（数据域），另一个空间用了存放下一个节点的地址（指针域）。
template <class datetype>
struct LinkNode
{
//数据域
DateType data;
//指针域
LinkNode<datetype>* next;
//注意两个事项：1.如果程序员提供了有参构造，那么编译器就不会提供默认的构造函数，但是会提供默认的拷贝构造
//2.注意事项2：如果程序员提供了拷贝构造，那么编译器不会提供默认的构造函数和拷贝构造
LinkNode(LinkNode<datetype> *ptr = NULL):next(ptr) { }
//struct的构造函数，默认参数构造, //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
LinkNode(const DateType& item, LinkNode<datetype>* ptr = NULL)
{
next = ptr;
data = item;
}
};
</datetype></datetype></datetype></class>
链表的小框架
template <class datetype>
class LinkList
{
public:
private:
//头节点
LinkNode<datetype>* head;
};
</datetype></class>
链表的接口
LinkList(); //构造函数,初始化为空链表
LinkList(const DateType &item);//有参构造，初始化头节点
LinkList(const LinkList<datetype>& list);//拷贝构造,拷贝单链表
CreateLink(int n);//创建单链表
~LinkList();//析构函数,单链表的删除
void PushBack(const DateType& data);//尾插
void PopBack();//尾删
void PushFront(const DateType &data)；//头插
void PopFront();//头删
int Length()const;//求单链表的长度
bool GetElem(int pos, DateType& data);//获得pos位置的元素
LinkNode<datetype>* Locate(int pos);//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回null bool insert(int pos, const datetype &data); 在序号pos位置插入元素值为data的结点 delete(int datetype& data); 删除pos位置的结点，并且返回结点 linknode<datetype>* Locate(int pos);//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回null void clear(); 清空链表 printlist()const; 输出单链表所有结点的元素值 exchangedata(int pos1, int pos2); 进行两结点元素值的交换 < code></0或pos超出链表最大个数返回null></0或pos超出链表最大个数返回null></datetype></datetype>
构造和析构
1.无参构造函数：没什么好说的，用new从堆分配一个结点的空间给我们都头结点指针，注意检查堆是否满是一个很好的习惯
2.含参构造函数：初始化头节点指向第一个结点
3.析构函数（单链表的删除）：单链表的删除很简单用两个指针，从头结点开始，一前一后依次释放申请的内存即可
4.拷贝构造：操作都很简单，依次分配内存拷贝链接即可，类似于链表的构建。区别在于拷贝构造还没有LinkList对象，需要创建，而赋值已经有了LinkList对象，需要将其链表删除再重新构造
//构造函数,初始化为空链表
LinkList()
{
head = new LinkNode<datetype>;
if (head == NULL)
{
cout << "内存分配失败" << endl;
exit(-1);
}
}
//有参构造，初始化头节点
LinkList(const DateType &item)
{
//LinkNode会调用构造函数，初始化结点内的内容
head = new LinkNode<datetype>();
LinkNode<datetype> *p = new LinkNode<datetype>(item);
head->next = p;
if (head == NULL)
{
cout << "内存分配失败" << endl;
exit(-1);
}
}
//拷贝构造,拷贝单链表
LinkList(const LinkList<datetype>& list)
{
LinkNode<datetype>* p = list.head->next;
if (p == NULL)
{
cout << "内存分配失败" << endl;
exit(-1);
}
head = new LinkNode<datetype>;
LinkNode<datetype>* h = head;
while (p != NULL)
{
LinkNode<datetype>* t = new LinkNode<datetype>;
h->next = t;
t->data = p->data;
p = p->next;
h = h->next;
}
}
//析构函数,单链表的删除
~LinkList()
{
//申请一个指针指向头节点
LinkNode<datetype>* cur = head;
LinkNode<datetype>* next;
while (cur)
{
next = cur->next;
delete cur;
cur = next;
}
}
</datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype>
首先，我们先来实现一个尾插的接口，尾插就是在链表的尾部插入一个节点。
在进行尾插的时候我们要考虑的几点：
为了更好的理解尾插，我们先看一个动图展示：
void PushBack(const DateType& data)
{
LinkNode<datetype>* p = new LinkNode<datetype>(data);
if (head->next == NULL)
{
head->next = p;
}
else
{
LinkNode<datetype>* cur = head;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = p;
}
}
</datetype></datetype></datetype>
创建单链表
首先定义一个指向Head的指针q；
然后不断重复以下三个步骤完成单链表的构造：
①用new申请一个LinkNode的空间返回指针p，并输入数据元素；
②q->next=p，将q指针对应结点的后继修改为p；
③q=q->next,将指针指向其直接后继，这样一个结点就被链接进了链表之中
//创建单链表
void CreateLink(int n)
{
LinkNode<datetype>* q = head;
DateType* nodetemp = new DateType[n];
for (size_t i = 0; i < n; i++)
{
cout << "Enter the element: " << endl;
cin >> nodetemp[i];
}
//尾插法
for (size_t i = 0; i < n; i++)
{
LinkNode<datetype>* p = new LinkNode<datetype>;
p->data = nodetemp[i];
p->next = q->next;
q->next = p;
q = q->next;
}
delete[] nodetemp;
}
</datetype></datetype></datetype>
尾删无非就是在链表的尾部删除一个节点，听起来很简单，但是有很多细节是我们要注意的，我们要分三种情况来进行讨论：
先看动图演示：
//尾删
void PopBack()
{
//分三种情况
//1.没有结点
if (head->next == NULL)
{
return;
}
//2.只有一个结点
else if (head->next->next == NULL) {
delete head->next;
head->next= NULL;
}
//3.两个以及两个以上的结点
else
{
LinkNode<datetype>* prev = NULL;
LinkNode<datetype>* cur = head;
while (cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
delete cur;
cur = NULL;
prev->next = NULL;
}
}
</datetype></datetype>
先看动图演示：
//头插
void PushFront(const DateType &data)
{
LinkNode<datetype>* p = new LinkNode<datetype>(data);
p->next = head->next;
head->next = p;
}
</datetype></datetype>
头删就要分情况讨论：
先看动图演示：
//头删
void PopFront()
{
//分两种情况
if (head->next == NULL)
{
return;
}
else
{
LinkNode<datetype>* p = head->next;
head->next = p->next;
delete p;
p = NULL;
}
}
</datetype>
定位位置
封装一个函数，返回第pos位置的地址，在下面用得到
//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回null linknode<datetype>* Locate(int pos)
{
int i = 0;
LinkNode<datetype>* p = head;
if (pos < 0)
return NULL;
while (NULL != p && i < pos)
{
p = p->next;
i++;
}
return p;
}
</datetype></0或pos超出链表最大个数返回null>
单链表任意位置插入
//在序号index位置插入元素值为data的结点
bool Insert(int pos, const DateType &data)
{
LinkNode<datetype>* p = Locate(pos);
if (p == NULL)
{
return false;
}
LinkNode<datetype>* node = new LinkNode<datetype>(data);
if (NULL == node)
{
cerr << "分配内存失败!" << endl;
exit(-1);
}
node->next = p->next;
p->next = node;
return true;
}
</datetype></datetype></datetype>
单链表的任意位置删除
先看动图演示：
//删除pos位置的结点，并且返回结点
bool Delete(int pos, DateType& data)
{
LinkNode<datetype>* p = Locate(pos-1);
if (NULL == p || NULL == p->next)
return false;
LinkNode<datetype>* del = p->next;
p->next = del->next;
data = del->data;
delete del;
return true;
}
</datetype></datetype>
打印链表
//输出单链表所有结点的元素值
void PrintList()const
{
int count = 0;
LinkNode<datetype>* p = head->next;
while (p)
{
cout << p->data<<" "; p="p-">next;
//打印十个元素换行
if (++count % 10 == 0)
{
cout << endl;
}
}
}
</"></datetype>
清空链表
//清空链表
void Clear()
{
//所有结点的next清空，最后头节点head清空
LinkNode<datetype>* p = NULL;
while (head->next != NULL)
{
p = head->next;
head->next = p->next;
delete p;
}
}
</datetype>
单链表的长度
//求单链表的长度
int Length()const
{
int count = 0;
LinkNode<datetype>* p = head;
while (p->next != NULL)
{
p = p->next;
++count;
}
return count;
}
</datetype>
两结点元素值的互换
//进行两结点元素值的交换
void Exchangedata(int pos1, int pos2)
{
LinkNode<datetype>* p1 = Locate(pos1);
LinkNode<datetype>* p2 = Locate(pos2);
DateType tmp = p1->data;
p1->data = p2->data;
p2->data = tmp;
}
</datetype></datetype>
#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<string>//C++中的字符串
using namespace std; //标准命名空间
template <class datetype>
struct LinkNode
{
//数据域
DateType data;
//指针域
LinkNode<datetype>* next;
//注意两个事项：1.如果程序员提供了有参构造，那么编译器就不会提供默认的构造函数，但是会提供默认的拷贝构造
//2.注意事项2：如果程序员提供了拷贝构造，那么编译器不会提供默认的构造函数和拷贝构造
LinkNode(LinkNode<datetype> *ptr = NULL):next(ptr) { }
//struct的构造函数，默认参数构造, //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
LinkNode(const DateType& item, LinkNode<datetype>* ptr = NULL)
{
next = ptr;
data = item;
}
};
template <class datetype>
class LinkList
{
public:
//构造函数,初始化为空链表
LinkList()
{
head = new LinkNode<datetype>;
if (head == NULL)
{
cout << "内存分配失败" << endl;
exit(-1);
}
}
//有参构造，初始化头节点
LinkList(const DateType &item)
{
//LinkNode会调用构造函数，初始化结点内的内容
head = new LinkNode<datetype>();
LinkNode<datetype> *p = new LinkNode<datetype>(item);
head->next = p;
if (head == NULL)
{
cout << "内存分配失败" << endl;
exit(-1);
}
}
//拷贝构造,拷贝单链表
LinkList(const LinkList<datetype>& list)
{
LinkNode<datetype>* p = list.head->next;
if (p == NULL)
{
cout << "内存分配失败" << endl;
exit(-1);
}
head = new LinkNode<datetype>;
LinkNode<datetype>* h = head;
while (p != NULL)
{
LinkNode<datetype>* t = new LinkNode<datetype>;
h->next = t;
t->data = p->data;
p = p->next;
h = h->next;
}
}
//创建单链表
void CreateLink(int n)
{
LinkNode<datetype>* q = head;
int* nodetemp = new int[n];
for (size_t i = 0; i < n; i++)
{
cout << "Enter the element: " << endl;
cin >> nodetemp[i];
}
//尾插法
for (size_t i = 0; i < n; i++)
{
LinkNode<datetype>* p = new LinkNode<datetype>;
p->data = nodetemp[i];
p->next = q->next;
q->next = p;
q = q->next;
}
delete[] nodetemp;
}
//析构函数,单链表的删除
~LinkList()
{
//申请一个指针指向头节点
LinkNode<datetype>* cur = head;
LinkNode<datetype>* next;
while (cur)
{
next = cur->next;
delete cur;
cur = next;
}
}
//尾插
void PushBack(const DateType& data)
{
LinkNode<datetype>* p = new LinkNode<datetype>(data);
if (head->next == NULL)
{
head->next = p;
}
else
{
LinkNode<datetype>* cur = head;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = p;
}
}
//尾删
void PopBack()
{
//分三种情况
//1.没有结点
if (head->next == NULL)
{
return;
}
//2.只有一个结点
else if (head->next->next == NULL) {
delete head->next;
head->next= NULL;
}
//3.两个以及两个以上的结点
else
{
LinkNode<datetype>* prev = NULL;
LinkNode<datetype>* cur = head;
while (cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
delete cur;
cur = NULL;
prev->next = NULL;
}
}
//头插
void PushFront(const DateType &data)
{
LinkNode<datetype>* p = new LinkNode<datetype>(data);
p->next = head->next;
head->next = p;
}
//头删
void PopFront()
{
//分两种情况
if (head->next == NULL)
{
return;
}
else
{
LinkNode<datetype>* p = head->next;
head->next = p->next;
delete p;
p = NULL;
}
}
//求单链表的长度
int Length()const
{
int count = 0;
LinkNode<datetype>* p = head;
while (p->next != NULL)
{
p = p->next;
++count;
}
return count;
}
//得到序号为index的结点元素值
bool GetElem(int pos, DateType& data)
{
LinkNode<datetype>* p = Locate(pos);
if (p == NULL)
{
return false;
}
data = p->data;
return true;
}
//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回null linknode<datetype>* Locate(int pos)
{
int i = 0;
LinkNode<datetype>* p = head;
if (pos < 0)
return NULL;
while (NULL != p && i < pos)
{
p = p->next;
i++;
}
return p;
}
//在序号index位置插入元素值为data的结点
bool Insert(int pos, const DateType &data)
{
LinkNode<datetype>* p = Locate(pos);
if (p == NULL)
{
return false;
}
LinkNode<datetype>* node = new LinkNode<datetype>(data);
if (NULL == node)
{
cerr << "分配内存失败!" << endl;
exit(-1);
}
node->next = p->next;
p->next = node;
return true;
}
//删除pos位置的结点，并且返回结点
bool Delete(int pos, DateType& data)
{
LinkNode<datetype>* p = Locate(pos-1);
if (NULL == p || NULL == p->next)
return false;
LinkNode<datetype>* del = p->next;
p->next = del->next;
data = del->data;
delete del;
return true;
}
//清空链表
void Clear()
{
//所有结点的next清空，最后头节点head清空
LinkNode<datetype>* p = NULL;
while (head->next != NULL)
{
p = head->next;
head->next = p->next;
delete p;
}
}
//输出单链表所有结点的元素值
void PrintList()const
{
int count = 0;
LinkNode<datetype>* p = head->next;
while (p)
{
cout << p->data<<" "; p="p-">next;
//打印十个元素换行
if (++count % 10 == 0)
{
cout << endl;
}
}
}
//进行两结点元素值的交换
void Exchangedata(int pos1, int pos2)
{
LinkNode<datetype>* p1 = Locate(pos1);
LinkNode<datetype>* p2 = Locate(pos2);
DateType tmp = p1->data;
p1->data = p2->data;
p2->data = tmp;
}
private:
//头节点
LinkNode<datetype>* head;
};
/*
LinkList(); //构造函数,初始化为空链表
LinkList(const DateType &item);//有参构造，初始化头节点, 有问题
LinkList(const LinkList<datetype>& list);//拷贝构造,拷贝单链表
CreateLink(int n);//创建单链表
~LinkList();//析构函数,单链表的删除
void PushBack(const DateType& data);//尾插
void PopBack();//尾删
void PushFront(const DateType &data)；//头插
void PopFront();//头删
int Length()const;//求单链表的长度
bool GetElem(int pos, DateType& data);//获得pos位置的元素
LinkNode<datetype>* Locate(int pos);//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回null bool insert(int pos, const datetype &data); 在序号pos位置插入元素值为data的结点 delete(int datetype& data); 删除pos位置的结点，并且返回结点 void clear(); 清空链表 printlist()const; 输出单链表所有结点的元素值 exchangedata(int pos1, int pos2); 进行两结点元素值的交换 * main() { linklist<int> list;
list.CreateLink(5);
list.PrintList();
cout << "-------------------" << endl;
list.PushBack(299);
list.PrintList();
cout << "-------------------" << endl;
list.PopBack();
list.PrintList();
cout << "-------------------" << endl;
list.PushFront(19);
list.PrintList();
cout << "-------------------" << endl;
list.PopFront();
cout << list.Length() << endl;
list.PrintList();
cout << "-------------------" << endl;
int b = 0;
list.GetElem(2,b);
cout << b << endl;
list.PrintList();
cout << "-------------------" << endl;
list.Insert(2, 99);
list.PrintList();
cout << "-------------------" << endl;
list.Exchangedata(1, 2);
list.PrintList();
cout << "-------------------" << endl;
list.Clear();
list.PrintList();
cout << "-------------------" << endl;
LinkList<int> list2(list);
list2.PrintList();
LinkList<int> list(90);
list.PrintList();
system("pause");
return EXIT_SUCCESS;
}
</int></int></0或pos超出链表最大个数返回null></datetype></datetype></datetype></datetype></datetype></"></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></0或pos超出链表最大个数返回null></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></datetype></class></datetype></datetype></datetype></class></string></iostream>
Original: https://www.cnblogs.com/yzsn12138/p/16924424.html
Author: 一只少年AAA
Title: 数据结构初阶–单链表（讲解+类模板实现）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/797908/
转载文章受原作者版权保护。转载请注明原作者出处！