目录
概念
链表是一种物理存储结构上非连续、非顺序的存储结构,但链表在逻辑上是连续的,顺序的,而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
结构组成
链表有多个节点组成,节点就是包含元素存储单元和指针的结构体。
准备工作
我们要实现类似于顺序表的操作,同样也要先进行符号的定义:
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
使用typedef把任意类型命名为SLTDataType,然后就是定义节点,包含存储的变量和用于连接下一个节点的指针,为了方便,所以用typede将结构体命名为SLNode;
函数接口
1.尾插
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//链表为空,新节点作为phead
if (*pphead == NULL) {
*pphead = newnode;
return;
}
//链表不为空,找尾节点
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//ptail就是尾节点
ptail->next = newnode;
}
首先分析下形参,pphead使用的是二级指针,因为初始化后pphead是空的,所以我们需要改变头结点的指向,所以就需要传递地址,如果使用一级指针,函数结束后,pphead仍然会指向空,操作无效,x是插入数据的值;
插入我们需要使用临时的指针向后连接各个节点,这里我们创造了个ptail指针;在插入前如果头结点为空,说明链表中没有节点,我们需要创造一个节点,为了方便使用利用函数进行包装;
//创造节点
SLTNode* SLTBuyNode(SLTDataType x) {
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
返回值是一个节点的地址;如果链表插入时不为空,先使用ptail遍历到最后一个节点,用ptail指针进行连接;
2.尾插
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//newnode *pphead
newnode->next = *pphead;
*pphead = newnode;
}
头插:直接创造一个节点next指向头结点,这是需要将头节点指向新的头结点;
3.头删
//头删
void SLTPopFront(SLTNode** pphead) {
assert(pphead);
//链表不能为空
assert(*pphead);
//让第二个节点成为新的头
//把旧的头结点释放掉
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
需要用一个临时指针指向第二个节点,然后释放头结点,*pphead再为空,然后*pphead指向新的头结点;
4.尾删
//尾删
void SLTPopBack(SLTNode** pphead) {
assert(pphead);
//链表不能为空
assert(*pphead);
//链表不为空
//链表只有一个节点,有多个节点
if ((*pphead)->next == NULL) {
free(*pphead);
*pphead = NULL;
return;
}
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
//销毁尾结点
free(ptail);
ptail = NULL;
}
如果没有节点是无法进行删除节点的,所以用assert进行检查,如果之有一个节点,就直接释放掉,如果节点数至少两个,就需要两个临时指针进行遍历到最后一个节点和倒数第二个节点,prev是倒数第二个节点,ptail是尾部节点,所以释放掉ptail节点,然后prev节点的next指向空;
5.查找
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {
assert(pphead);
//遍历链表
SLTNode* pcur = *pphead;
while (pcur) //等价于pcur != NULL
{
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}
查找的时间复杂度是O(N),需要进行遍历,遍历到直接返回节点即可,否则返回空;
6.指定位置之前插入
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead);
assert(pos);
//要加上链表不能为空
assert(*pphead);
SLTNode* newnode = SLTBuyNode(x);
//pos刚好是头结点
if (pos == *pphead) {
//头插
SLTPushFront(pphead, x);
return;
}
//pos不是头结点的情况
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev -> newnode -> pos
prev->next = newnode;
newnode->next = pos;
}
指定的节点是pos,如果pos是头结点,直接头插即可,如果不是头结点就需要遍历到pos的前一个节点,prev指向newnode,newnode指向pos;
7.指定位置之后插入
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//pos newnode pos->next
newnode->next = pos->next;
pos->next = newnode;
}
这个比较简单,先将newnode指向pos的next;然后pos在指向newnode;
8.删除pos节点
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead);
assert(*pphead);
assert(pos);
//pos刚好是头结点,没有前驱节点,执行头删
if (*pphead == pos) {
//头删
SLTPopFront(pphead);
return;
}
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
如果pos是头结点,直接头删;否则,需要遍历到pos前的一个节点,让prev指向pos的后一个节点;
9.删除pos之后的节点
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
assert(pos);
//pos->next不能为空
assert(pos->next);
//pos pos->next pos->next->next
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
直接让pos的next指向pos的next的next即可;
10.打印链表
//打印
void SLTPrint(SLTNode* phead) {
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
打印链表是利用临时指针变量的遍历;
11.销毁链表
//销毁链表
void SListDesTroy(SLTNode** pphead) {
assert(pphead);
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
储存下一个节点,利用遍历释放掉下一个节点,知道链表为空;