单链表的学习
链表是一种很重要的数据结构,它由两部分组成,第一个部分是我们要储存的数据,第二个部分是指向下一个储存单元的指针。链表在使用中有顺序表无法比拟的灵活性,免去了储存空间不够,又有可能浪费的尴尬。
单链表有一个头指针pHead,当我们没有数据要储存的时候它指向NULL,当我们有数据的时候它指向第一块储存单元。储存单元里面有两个部分,前面的部分是我们要储存的数据data,后面的部分是指向下一个储存单元的指针pNext,当后面没有储存单元的时候就指向NULL。那么我们储存的数据在内存中并不是连续储存的,而是在内存中跳跃式储存的。要使用的时候再直接申请一块空间。
下面是链表的定义
typedef struct ListNode
{
DataType data;
struct ListNode *pNext;
}SListNode, *PSListNode;
可以看到单链表的两个成员。为了使用方便我们直接typedef重命名。
单链表有几种基本操作,比如插入数据,删除数据,那我下面实现了一下。
首先,我写了一个申请新单元的函数
PSListNode ByeNode(DataType data)
{
PSListNode pNewNode = (PSListNode)malloc(sizeof(SListNode));
if (NULL != pNewNode)
{
pNewNode->data = data;
pNewNode->pNext = NULL;
}
return pNewNode;
}
它可以为我们直接在内存中申请一块新的空间并且返回它的地址。
第一个实现就是我们从尾部插入数据
void PushBack(PSListNode* pHead, DataType data)
{
PSListNode pNode = NULL;
PSListNode pNewNode = NULL;
assert(pHead);
if (NULL == *pHead)
{
*pHead = ByeNode(data);
}
else
{
pNode = *pHead;
while (NULL != pNode->pNext)
{
pNode = pNode->pNext;
}
pNewNode = ByeNode(data);
pNode->pNext = pNewNode;
}
}
这里我们传的参数是二级指针,因为我们是要改变它指针的指向。假如我们直接传递一级指针,那么我们并不能改变它的指向,相当于我们函数中操作了半天,其实都是在操作一个临时的指针变量,只不过他跟我们的头指针的指向是一样的,最后什么也没有返回,头指针什么变化都没有。
接下来就是我们从尾部删除数据的实现
void PopBack(PSListNode* pHead)
{
/*PSListNode pPerNode = NULL;
PSListNode pCurNode = NULL;
assert(pHead);
if (NULL == *pHead)
{
return;
}
else
{
pCurNode = *pHead;
pPerNode = pCurNode;
while (NULL != pCurNode->pNext)
{
pPerNode = pCurNode;
pCurNode = pCurNode->pNext;
}
if (pCurNode==pPerNode)
{
*pHead = NULL;
free(pCurNode);
pCurNode = NULL;
pPerNode = NULL;
}
else
{
pPerNode->pNext = NULL;
free(pCurNode);
pCurNode = NULL;
}
}*/
PSListNode pPerNOde = *pHead;
PSListNode pCurNode = *pHead;
assert(pHead);
if (NULL == *pHead)
{
return;
}
else
{
if (NULL == pCurNode->pNext)
{
return;
}
else
{
while (NULL!=pCurNode->pNext)
{
pPerNOde = pCurNode;
pCurNode = pCurNode->pNext;
}
pPerNOde->pNext = NULL;
free(pCurNode);
pCurNode = NULL;
}
}
}
注释中的代码是我刚开始的时候写的,我发现他的逻辑不是很清晰,在第二个部分中我把链表中只有一个节点的情况单列了出来,逻辑比之前清晰了很多。
那我们也可以在链表的头部插入数据
void PushFront(PSListNode* pHead, DataType data)
{
PSListNode NewNode = NULL;
assert(pHead);
if (NULL == *pHead)
{
*pHead = ByeNode(data);
}
else
{
NewNode = ByeNode(data);
if (NULL == NewNode)
{
return;
}
else
{
NewNode->pNext = (*pHead);
*pHead = NewNode;
}
}
}
思路有了之前的两个函数做铺垫想起来并不难。申请一块新的空间之后,让它的pNext指向我们之前的第一块空间。然后改变我们的头指针的指向,让它指向我们的新空间。这里注意我们申请空间是有可能失败的,所以要判断一下。
当然还有从头部删除
void PopFront(PSListNode* pHead)
{
assert(pHead);
if (NULL == *pHead)
{
return;
}
else
{
PSListNode pCurNode = *pHead;
pCurNode = pCurNode->pNext;
free(*pHead);
*pHead = pCurNode;
pCurNode = NULL;
}
}
千万不要忘记free空间之后要给指针赋空,否则会形成野指针。
还有就是寻找我们链表中的元素
PSListNode Find(PSListNode pHead, DataType data)
{
if (NULL == pHead)
{
return NULL;
}
else
{
PSListNode pNode = pHead;
/*while (data != pNode->data)
{
if (NULL == pNode->pNext)
{
return NULL;
}
pNode = pNode->pNext;
}
return pNode;*/
while (NULL != pNode)
{
if (data == pNode->data)
return pNode;
pNode = pNode->pNext;
}
return NULL;
}
}
注释掉的代码是我第一次写的,后来我发现它的逻辑有点问题,我可以更简单的实现它的功能。
最后返回我要找的数据的位置,假如没有找到那么就返回空。
打印我链表中的元素
void PrintList(PSListNode pHead)
{
PSListNode pNode = pHead;
while (NULL!=pNode)
{
printf("%d ", pNode->data);
pNode = pNode->pNext;
}
printf("\n");
}
删除我的任意位置的节点
void Erase(PSListNode* pHead, PSListNode pos)
{
PSListNode pCurNode = pos;
PSListNode pPerNode = NULL;
assert(pHead);
if (NULL == *pHead)
{
return;
}
else
{
pPerNode = *pHead;
while (pPerNode->pNext != pCurNode)
{
pPerNode = pPerNode->pNext;
}
pPerNode->pNext = pCurNode->pNext;
free(pCurNode);
pCurNode = NULL;
}
}
在我的链表的任意位置插入一个节点
void Insert(PSListNode* pHead, PSListNode pos, DataType data)
{
PSListNode ptmpNode = *pHead;
PSListNode pNode = *pHead;
assert(pHead);
if (NULL == *pHead)
{
*pHead = ByeNode(data);
}
else
{
while (pos != pNode)
{
if (NULL == pNode)
{
return;
}
pNode = pNode->pNext;
}
ptmpNode = pNode->pNext;
pNode->pNext = ByeNode(data);
pNode = pNode->pNext;
pNode->pNext = ptmpNode;
}
}
转载于:https://blog.51cto.com/lzd1995/1751909
上一篇: Java1.8-Arrays源码解析
下一篇: LeetCode初级之链表