赞
踩
上面文章用C语言实现了顺序表的增删查改,本片文章继续用C语言来实现另一种线性存储结构——单链表。我们知道,顺序表中的数据元素在内存中是连续存储的,而单链表的数据元素在内存中是随机存储的。它由节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。
例如:使用单链表存储 {1,2,3,4,5},数据在内存中的存储状态的逻辑图如下所示:
总结:单链表的数据元素在内存中随机存储,数据元素之间的逻辑关系是通过指针来表示的。
链表的结点分为两部分:数据域和指针域。
数据域:链表要存储的数据所在的区域。
指针域:指向下一个节点的指针所在的区域。
链表节点的定义:
typedef int SLTDatatype;
typedef struct SListNode
{
SLTDatatype data;//数据域
struct SListNode* next;//指针域, 指向下一个节点
}SLTNode;
创建一个新链表,通常包括一个指向链表头节点的指针,初始时指向NULL。
例如:一个存储 {1,2,3,4,5} 的链表结构下如图所示:
该链表是由头指针 plist 来维护的,通过头指针 plist 就能找到该链表。由于链表刚创建的时候,链表中没有节点,因此链表创建时,plist 为空。
创建头指针的代码如下:
SLTNode* plist = NULL;//创建头指针
向链表插入数据时,根据插入位置的不同可以分为以下三种情况:
头插数据步骤:
代码如下:
//创建新节点
SLTNode* BuyNode(SLTDatatype x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("BuyNode->malloc");
return;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
代码如下:
void SLTPushFront(SLTNode** pphead, SLTDatatype x)
{
assert(pphead);//检查参数的有效性
//创建节点
SLTNode* newnode = BuyNode(x);
newnode->next = (*pphead);
*pphead = newnode;
}
尾插数据分为以下两种情况:
代码如下:
void SLTPushBack(SLTNode** pphead, SLTDatatype x) { assert(pphead);//检查参数有效性 SLTNode* newnode = BuyNode(x); //链表为空的情况 if (*pphead == NULL) { *pphead = newnode; } else { //链表不为空的情况 SLTNode* cur = *pphead; //遍历链表,找最后一个节点 while (cur->next) { cur = cur->next; } cur->next = newnode; } }
步骤如下:
代码如下:
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDatatype x) { assert(pphead);//检查参数的有效性 assert(pos);//检查插入位置的有效性 SLTNode* newnode = BuyNode(x); //头插 if (*pphead == pos) { newnode->next = *pphead; *pphead = newnode; } else { //中间位置插入数据 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } newnode->next = pos; prev->next = newnode; } }
头删的步骤如下:
代码如下:
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);//检查参数有效性
assert(*pphead);//检查链表是否为空
SLTNode* phead = *pphead;
*pphead = phead->next;
free(phead);
}
尾删的步骤如下:
代码如下:
void SLTPopBack(SLTNode** pphead) { assert(pphead);//检查参数有效性 assert(*pphead);//检查链表是否为空 //只有一个元素时,相当于头删 if ((*pphead)->next == NULL) { SLTNode* phead = *pphead; *pphead = phead->next; free(phead); } else { SLTNode* prev = *pphead; while (prev->next->next != NULL) { prev = prev->next; } SLTNode* ptail = prev->next; prev->next = NULL; free(ptail); } }
代码如下:
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead);//检查参数有效性 assert(*pphead);//检查链表是否为空 //头删 if (*pphead == pos) { SLTNode* phead = *pphead;//保存头节点的指针 *pphead = phead->next; free(phead); //SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
在链表中查找指定数据的方法是:从表头开始依次遍历链表的节点,如果被查找数据与当前遍历节点的数据相同就是查找成功,如果遍历完链表都没找到,则查找失败。
代码如下:
SLTNode* SLTFind(SLTNode* phead, SLTDatatype x)
{
SLTNode* cur = phead;
//遍历链表的每一个节点
while (cur)
{
//与每个节点的数据进行比较
if (cur->data == x)
{
return cur;
}
}
return NULL;
}
依次释放链表的每个节点。
代码如下:
void SLTDestroy(SLTNode** pphead) { assert(pphead); //检查参数的有效性 SLTNode* cur = *pphead; SLTNode* next = NULL; if (cur) { next = cur->next; } while (cur) { free(cur); cur = next; if (cur) { next = cur->next; } } *pphead = NULL; }
至此,本片文章就结束了,若本篇内容对您有所帮助,请三连点赞,关注,收藏支持下。
创作不易,白嫖不好,各位的支持和认可,就是我创作的最大动力,我们下篇文章见!
如果本篇博客有任何错误,请批评指教,不胜感激 !!!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。