这篇文章主要介绍了C语言如何实现无头单向链表,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
由于创建一个新节点是频繁的操作,所以封装为一个接口最佳。
链表节点的属性有:(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。
尾插的难点在于存在特殊情况。
当对非空链表和空链表进行尾插时,所需代码不同。
对非空链表尾插时,算法是:找到此链表的尾部,即遍历此链表,直至自定义的结构体指针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; } }
此接口也有特殊情况处理。
当链表有一个以上的节点时,算法:遍历链表到尾部,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; }
void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
int SListSize(SLTNode* phead) { //计数器 int count = 0; SLTNode* cur = phead; while (cur) { count++; cur = cur->next; } return count; }
bool SListEmpty(SLTNode* phead) { return phead == NULL; }
SLTNode* SListFind(SLTNode* phead, SLTDataType data) { //通过数据查找节点-遍历节点,判断值是否相等 SLTNode* cur = phead; while (cur) { if (cur->data == data) return cur; cur = cur->next; } return NULL; }
void SListPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
void SListPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = NULL; *pphead = next; }
void SListInsert(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySListNode(x); SLTNode* next = pos->next; pos->next = newnode; newnode->next = next; }
void SListErase(SLTNode* pos) { assert(pos); assert(pos->next); SLTNode* next = pos->next; pos->next = next->next; free(next); next = NULL; }
void SListDestroy(SLTNode** pphead) { assert(pphead); SLTNode* cur, * nextnode; cur = *pphead; nextnode = NULL; while (cur) { nextnode = cur->next; free(cur); cur = nextnode; } *pphead = NULL; }
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h>
typedef int SLTDataType;//重定义可便于修改值的数据类型 1 typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;//重定义可减少代码冗余
感谢你能够认真阅读完这篇文章,希望小编分享的“C语言如何实现无头单向链表”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。