南通昨晚最新疫情爆发_网页设计多少钱一个页面_手机百度下载app_品牌推广策略怎么写

🔥 博客主页: 偷心编程
🎥 系列专栏: 《Java学习》 《C语言学习》 《数据结构C语言版》
❤️ 感谢大家点赞👍收藏⭐评论✍️

1. 链表的概念

  链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链
接次序实现的 。

  链表也是线性表的一种，特点是：物理上不连续，逻辑上连续。

2. 链表的分类

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

---

当然了我们最常用的还是下面两种结构：

3. 实现无头单向非循环链表（单链表）

3.1 单链表的声明

typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SListNode;

3.2 单链表的打印

//打印这个链表
void SListPrint(SListNode* phead) {if (!phead) {printf("NULL!链表为空!!!");return;}while (phead) {printf("%d ", phead->data);phead = phead->next;}
}

3.3 尾插

1. 处理一般的单链表（链表不为空）

//尾插
void SListPushBack(SListNode* phead, SLTDataType x) {//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));newnode->data = x;newnode->next = NULL;//尾插，链表必须找尾SListNode* ptail = phead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;return;
}

2. 考虑链表为空的情况

错误示范

//尾插
void SListPushBack(SListNode* phead, SLTDataType x) {//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);
}newnode->data = x;newnode->next = NULL;//处理空链表的情况if (!phead) {phead = newnode; //我们要改变第一个节点（指向NULL）里面的内容，但是这是传值调用，无法再main里面改变，因此要传递地址，所以最终是二级指针return ;}//尾插，链表必须找尾SListNode* ptail = phead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;return;
}

正确示范

//尾插
void SListPushBack(SListNode** pphead, SLTDataType x) {assert(pphead);//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);
}newnode->data = x;newnode->next = NULL;//处理空链表的情况if (!*pphead) {*pphead = newnode;return ;}//尾插，链表必须找尾SListNode* ptail = *pphead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;return;
}//创建了节点(动态开辟了空间)就要给里面的元素初始化
/*SListNode* head = (SListNode*)malloc(sizeof(SListNode));
head->data = 2;
head->next = NULL;*/
//要么就不开辟空间
SListNode* head = NULL;

3.4 头插

1. 可以跟尾插一样，分类讨论

//头插
void SListPushFront(SListNode** pphead, SLTDataType x) {assert(pphead);//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;//处理空链表的情况if (!*pphead) {*pphead = newnode;return;}//处理一般情况newnode->next = *pphead;*pphead = newnode;
}

2. 也可以合并

//头插
void SListPushFront(SListNode** pphead, SLTDataType x) {assert(pphead);//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;newnode->next = *pphead;*pphead = newnode;
}

3.5 尾删

//尾删
void SListPopBack(SListNode** pphead) {assert(pphead);//处理链表为空的情况if (!*pphead) {printf("链表为空，无法删除！");return;}//处理只有一个节点的情况if (!((*pphead)->next)) {free(*pphead);*pphead = NULL;return;}//处理一般情况//找倒数第二个节点和最后一个节点SListNode* prev = *pphead;SListNode* ptail = *pphead;while (ptail->next) {prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;return;
}

3.6 头删

1. 分类讨论

//头删
void SListPopFront(SListNode** pphead) {assert(pphead);//处理链表为空的情况if (!*pphead) {printf("链表为空，无法删除！");return;}//处理只有一个节点的情况if (!((*pphead)->next)) {free(*pphead);*pphead = NULL;return;}//处理一般情况SListNode* ptem = *pphead;*pphead = (*pphead)->next;free(ptem);ptem = NULL;
}

2. 合并

//头删
void SListPopFront(SListNode** pphead) {assert(pphead);//处理链表为空的情况if (!*pphead) {printf("链表为空，无法删除！");return;}SListNode* ptem = *pphead;*pphead = (*pphead)->next;free(ptem);ptem = NULL;
}

3.7 查找

//查找
SListNode* SListFind(SListNode* phead, SLTDataType x) {while (phead) {if (phead->data == x) {return phead;}phead = phead->next;}printf("没有找到！");return NULL;
}

3.8 在指定位置之前插入数据

1. 给的pos是int

//在指定位置之前插入数据（默认链表不为空）
void SListInsert(SListNode** pphead, int pos, SLTDataType x) {assert(pphead && (*pphead));//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;//处理在第一个节点的情况（说明是头插）,关键在于没有第pos-1个节点，所以要分类讨论if (pos==1) {SListPushFront(pphead, x);return;}//处理一般情况//找到第pos-1个节点SListNode* prev = *pphead;int i;for (i = 0;i<pos-2; i++) {prev = prev->next;}newnode->next = prev->next;prev->next = newnode;
}

2. 给的pos是一个指针

//在指定位置之前插入数据(默认链表不为空)
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x) {assert(pphead && (*pphead));//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;//处理在第一个节点的情况（说明是头插）,关键在于没有第pos-1个节点，所以要分类讨论if (pos==*pphead) {SListPushFront(pphead, x);return;}//处理一般情况//找到第pos-1个节点SListNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}newnode->next = prev->next;prev->next = newnode;
}

3.9 在指定位置之后插入数据

1. 给的pos是int

//在指定位置之后插入数据(默认链表不为空)
void SListInsertAfter(SListNode** pphead, int pos, SLTDataType x) {assert(pphead && (*pphead));//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;//适用所有情况//找到第pos个节点SListNode* prev = *pphead;int i;for (i = 0; i < pos - 1; i++) {prev = prev->next;}newnode->next = prev->next;prev->next = newnode;
}

2. 给的pos是一个指针

//在指定位置之后插入数据(默认链表不为空)
void SListInsertAfter( SListNode* pos, SLTDataType x) {//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;//适用所有情况//找到第pos个节点newnode->next = pos->next;pos->next = newnode;
}

3.10 删除指定节点

//删除pos节点(默认链表不为空)
void SListErase(SListNode** pphead, SListNode* pos) {//pos为第一个节点的情况if (pos == *pphead) {*pphead = pos->next;free(pos);pos = NULL;return;}//处理一般情况//找到第pos-1个节点SListNode* pcur = *pphead;while (pcur->next != pos) {pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;
}//删除pos之后的节点
void SListEraseAfter(SListNode* pos) {SListNode* ptem = pos->next;pos = ptem->next;free(ptem);ptem = NULL;
}

3.11 销毁链表

//销毁链表
void SListDesTroy(SListNode** pphead) {//处理一般情况SListNode* pnext = (*pphead);while (pnext) {pnext = (*pphead)->next;free(*pphead);*pphead = pnext;}
}

4. 一些细节

4.1 指针与二级指针

  若是涉及到我们需要改变头节点，也就是要改变head指针的内容的时候，我们就要传入二级指针（涉及到“头”的改变就要传二级指针）

4.2 创建一个获取节点的函数

//获取一个新的节点
SListNode* getNode(SLTDataType x) {SListNode* node = (SListNode*)malloc(sizeof(SListNode));if (!node) {perror("malloc:");exit(1);}node->data = x;node->next = NULL;return node;
}

4.3 单链表中可能需要分情况的点

1. 链表为空链表或者非空链表
2. 单链表只能由前一个节点得到下一个节点，因此在增 、删的时候prev节点很重要。由于这个特性，我们常常要就处理第一个节点的时候进行讨论（没有prev节点，这时候直接改变头结点）

4.4改变结构的处理顺序

  我们在处理问题的时候，无论是单链表还是双向链表，我们总是先改变外部结构（新创建的节点里面的数据），然后再改变我们原本的内部结构（改变链表内部节点的next指向或者数据等等）