数据结构初 - 链表
人类接受信息较少或较多时，眨眼次数会增加。。。
目录
数据结构简介
链表常见分类
单链表
特点：
组成：
简单实现（单向带头不循环链表）
链表结点定义
开辟新结点
初始化头结点（哨兵位）
尾插
头插
头删
尾删
修改
打印
销毁
小知识
数据结构简介
概念：数据结构意为计算机储存、管理数据的方式。
分类：分为线性和非线性。
线性包括：数组、单链表、双链表、队列、栈。
非线性包括：树、堆、图、哈希表。
链表常见分类
顺序表、单链表、双链表，其中单链表与双链表又可以细分为八种链表。
它们是：单向不带头循环链表、单向带头循环链表、单向不带头不循环链表、单向带头不循环链表、双向不带头循环链表、双向带头循环链表、双向不带头不循环链表、双向带头不循环链表 QWQ
其中带头不带头指的是链表前有无一个占位置的结点，这个结点也叫哨兵位。
单链表
单链表是一种数据结构类型，是由一个个的节点和“链条”构成，在语法结构上就像一条锁链，而又是单向的，所以叫单链表。
特点：
物理结构不一定是线性的，但逻辑结构一定是线性的。
组成：
由一个一个结点组成，每个普通结点包含（要储存的数据+指向下一个普通结点的地址的指针），尾部结点存空指针。
简单实现（单向带头不循环链表）
链表结点定义
typedef int datatype;
typedef struct slnode
{
datatype _data;
struct slnode* _next;
}sl
开辟新结点
sl* createnode(datatype data = 0)
{
sl* newnode = new sl;
assert(newnode);
newnode->_data = data;
newnode->_next = nullptr;
return newnode;
}
初始化头结点（哨兵位）
sl* Init()
{
sl* newnode = new sl;
assert(newnode);
newnode->_next = nullptr;
return newnode;
}
尾插
void push_back(sl*head,datatype data = 0)
{
assert(head);
sl* tmp = head;
while (tmp->_next)
{
tmp = tmp->_next;
}
tmp->_next = createnode(data);
}
头插
void push_front(sl* head, datatype data = 0)
{
assert(head);
sl* tmp = createnode(data);
tmp->_next = head->_next;
head->_next = tmp;
}
头删
void delete_front(sl* head)
{
assert(head&&head->_next);
sl* tmp = head->_next;
head->_next = tmp->_next;
delete tmp;
}
尾删
void delete_back(sl* head)
{
assert(head && head->_next);
sl* tmp = head;
while (tmp->_next->_next)
{
tmp = tmp->_next;
}
sl* ttmp = tmp->_next;
tmp->_next = nullptr;
delete ttmp;
}
查找
sl* search(sl* head, datatype data = 0)
{
assert(head);
sl* tmp = head->_next;
while (tmp)
{
if (tmp->_data == data)
return tmp;
tmp = tmp->_next;
}
return nullptr;
}
修改
void change(sl* pos, datatype data = 0)
{
assert(pos);
pos->_data = data;
}
打印
void print(sl* head)
{
assert(head);
sl* tmp = head->_next;
while (tmp)
{
cout << tmp->_data<<' ';
tmp = tmp->_next;
}
}
销毁
void SLdestory(Sl** pphead)
{
assert(pphead && *pphead);
Sl* slist = *pphead;
while (slist)
{
Sl* next = slist->slist;
free(slist);
slist = next;
}
*pphead = NULL;
}
小知识
1.流插入和流提取运算符不能做成员函数，不过也不一定要做友元函数。因为可以用成员函数返回私有成员。
2.发现错误时，先确认是不是这一行的问题，编译器不一定是对的，调试时找到错误大概位置就打断点，然后继续调试，可以先跳过函数看预期结果，不然调试代码太长，VS里面要用那个console字体，那个字体的中英符号区别特别明显。
