数据结构|最好懂的C语言实现无头单向链表-新手向 c语言|数据结构|链表

- 一、易错的接口实现
- - 1.1 新节点开辟函数
  - 1.2 尾插
  - 1.3 尾删
- 二、常见简单接口
- - 2.1 打印链表
  - 2.2 节点计数器
  - 2.3 判断是否为空链表
  - 2.4 通过值查找节点
  - 2.5 头插
  - 2.6 头删
  - 2.7 在任意节点后插入节点
  - 2.8 在任意节点后删除节点
  - 2.9 销毁链表
- 三、头文件相关内容
- - 3.1 引用的库函数
  - 3.2 结构体声明

一、易错的接口实现 1.1 新节点开辟函数
由于创建一个新节点是频繁的操作，所以封装为一个接口最佳。
链表节点的属性有：（1）数值。（2）指向下一个节点的地址。（3）自身地址。

static SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //开辟失败 if (newnode == NULL) {printf("malloc fail\n"); exit(-1); } //初始化 newnode->data = https://www.it610.com/article/x; newnode->next = NULL; return newnode; }

数值和next地址都由此函数初始化，自身地址则由函数的返回值返回。
要注意使用malloc函数时，可能存在开辟空间失败的情况，这时会返回NULL。
1.2 尾插
尾插的难点在于存在特殊情况。
当对非空链表和空链表进行尾插时，所需代码不同。
对非空链表尾插时，算法是：找到此链表的尾部，即遍历此链表，直至自定义的结构体指针tail的下一个节点为NULL，结束遍历。在tail的后面插入一个新节点。
对空链表尾插时，算法是：直接把新节点作为链表的头节点。

void SListPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); //找尾 SLTNode* tail = *pphead; if (tail == NULL) {tail = BuySListNode(x); *pphead = tail; } else {while (tail->next != NULL) {tail = tail->next; } SLTNode* newnode = BuySListNode(x); tail->next = newnode; } }

1.3 尾删
此接口也有特殊情况处理。
当链表有一个以上的节点时，算法：遍历链表到尾部，free掉tail所在内存，改变tail之前一个节点的next，为NULL。
需要一个结构体指针变量prev来记录tail的前一个节点。
当链表只有一个节点时，算法：tail一开始就在尾部，直接free掉tail，再把prev指针（初值为NULL）赋值给头节点*pphead。
如果不单独考虑这种情况的话，会因为NULL->next而出现内存错误。
【数据结构|最好懂的C语言实现无头单向链表-新手向】当链表没有节点时，是不可以调用尾删的，直接用assert函数报错。

void SListPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead); //没有节点断言报错 SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->next != NULL) {prev = tail; tail = tail->next; } free(tail); tail = NULL; if (prev != NULL) prev->next = NULL; else *pphead = prev; }

二、常见简单接口 2.1 打印链表

void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) {printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }

2.2 节点计数器

int SListSize(SLTNode* phead) { //计数器 int count = 0; SLTNode* cur = phead; while (cur) {count++; cur = cur->next; } return count; }

2.3 判断是否为空链表

bool SListEmpty(SLTNode* phead) { return phead == NULL; }

2.4 通过值查找节点

SLTNode* SListFind(SLTNode* phead, SLTDataType data) { //通过数据查找节点-遍历节点，判断值是否相等 SLTNode* cur = phead; while (cur) {if (cur->data =https://www.it610.com/article/= data) return cur; cur = cur->next; } return NULL; }

2.5 头插

void SListPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }

2.6 头删

void SListPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = NULL; *pphead = next; }

2.7 在任意节点后插入节点

void SListInsert(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySListNode(x); SLTNode* next = pos->next; pos->next = newnode; newnode->next = next; }

2.8 在任意节点后删除节点

void SListErase(SLTNode* pos) { assert(pos); assert(pos->next); SLTNode* next = pos->next; pos->next = next->next; free(next); next = NULL; }

2.9 销毁链表

void SListDestroy(SLTNode** pphead) { assert(pphead); SLTNode* cur, * nextnode; cur = *pphead; nextnode = NULL; while (cur) {nextnode = cur->next; free(cur); cur = nextnode; } *pphead = NULL; }

三、头文件相关内容 3.1 引用的库函数