🍔链表许多结构
单链表，单循环链表，双链表，双循环链表，带头节点的单链表，不带头节点的双向链表......
1.线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）
2.一个结点包括两个域：其中存储数据元素的叫数据域，存储直接后继存储位置的域叫指针域
3.用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，指针为数据元素之间的逻辑关系映像，所以逻辑上相邻的两个数据元素其存储的物理位置不要求相邻
?
🍔搞清楚带头节点和不带头节点的链表的区别
大家可以参照这个文章
🍔以下是不带头节点的单链表的基本操作
🍟定义单链表
typedef struct Dlist{
int data;//以整形为例子
struct Dlist *next;//指针域
}Dlist;🍟初始化
void InitDlist(Dlist *head){
assert(head);
head = NULL;
}🍟动态申请结点
//动态申请结点
Dlist *BuyNode(int x){
Dlist* s = (Dlist *)malloc(sizeof(Dlist));
assert(s != NULL);
s->data = x;
s->next = NULL;
return s;
}🍟打印
//打印
void DlistPrint(Dlist *head){
assert(head);
Dlist *p = head;
while (p != NULL){
printf("%d->", p->data);
p = p->next;
}
}
?
🍟尾插
//尾插
void PushbackDlist(Dlist **head,int x){
//assert(head);
Dlist *s = BuyNode(x);
assert(s != NULL);//判断结点是否申请成功
Dlist *p = *head;
//如果此时链表是空的，s就是链表的第一个结点
if (p==NULL){
*head = s;
}
//链表不为空，需要遍历整个单链表去找到最后一个结点，把结点s插在后面
else{
while (p->next != NULL){
p = p->next;
}
p->next = s;
}
}🍟头插
//头插
void PushFrontDlist(Dlist **head, int x){
assert(*head);//避免空指针
Dlist *s = BuyNode(x);
assert(s != NULL);//判断结点是否申请成功
Dlist *p = *head;
//如果此时链表是空的，需要改变头指针
if (*head == NULL){
(*head) = s;
}
else{
s->next = p;
(*head) = s;
}
}
?
🍟尾删
//单链表尾删
void PopBackDlist(Dlist **head){
assert(*head);
Dlist *prev = *head;
Dlist *p = *head;
Dlist *tail = p->next;
if (*head == NULL){
printf("空表");
}//只有一个结点时，删除后要改变头指针，指向NULL
else{
if (p->next == NULL){
free(*head);//free掉唯一一个结点
*head = NULL;
}
else{//需要找到最后一个元素的前一个结点，才可以删除
while (tail->next != NULL){
prev = tail;
}
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;//最后一个结点的前一个结点指向空
}
}🍟头删
//头删
void PopTopDlist(Dlist **head){
assert(*head);
if (*head == NULL){
return;
}
else{
Dlist *cur= (*head)->next;//定义一个变量指向首结点的
free(*head);
*head = cur;//改变首结点的位置
}
}🍟按位置后插入
//按指定位置后插入
void InsertAfterDlist(Dlist *pos, int x){
assert(pos);
Dlist *s = BuyNode(x);
assert(s);
s->next = pos->next;
pos->next = s;//pos指向新节点
}🍟按位置前插入
//按指定位置前插入
void InsertBeforeDlist(Dlist *pos, int x){
assert(pos);
Dlist *s = BuyNode(x);
assert(s);
//在pos位置后面尾插，然后交换新节点和pos的data值
s->next = pos->next;
pos->next = s;
int temp = pos->data;
pos->data =s->data;
s->data = temp;
}🍟按位置删除后一个结点
//按指定位置后删
void EraseAfterDlist(Dlist *pos)
{
assert(pos);
//如果要删除的位置后面是空的，则代表没有东西删除
if (pos->next == NULL){
return;
}
//代表删除这个结点以后，pos也指向空了
if (pos->next->next == NULL){
pos->next = NULL;
return;
}
Dlist *p = pos->next;
pos->next = p->next;
free(p);
p = NULL;
}🍟按位置删除前一个结点
//按指定位置头删
void EraseBeforeDlist(Dlist **head, Dlist* pos){
assert(pos);
assert(*head);
if (*head == pos){
return;
}
if ((*head)->next == pos){
*head = pos;
return;
}
Dlist *prev = *head;
Dlist *cur = prev->next;
while (prev->next->next != pos){
prev = prev->next;
}
prev->next = pos;
free(cur);
pos = NULL;
}