Shulou(Shulou.com)06/03 Report--

这篇文章主要介绍了C语言如何实现无头单向链表，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

一、易错的接口实现

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 = 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而出现内存错误。

当链表没有节点时，是不可以调用尾删的，直接用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 == 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 引用的库函数

#include#include#include#include3.2 结构体声明

typedef int SLTDataType;//重定义可便于修改值的数据类型1typedef struct SListNode{ SLTDataType data; struct SListNode* next;}SLTNode;//重定义可减少代码冗余感谢你能够认真阅读完这篇文章，希望小编分享的"C语言如何实现无头单向链表"这篇文章对大家有帮助，同时也希望大家多多支持，关注行业资讯频道，更多相关知识等着你来学习!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.