实现一个基本具有增删查改功能的单向链表
基本思想:结构体内含有一个节点数据变量和指向下一节点的指针变量,最后一个节点内的指针变量为空,如下图所示,基本操作都是基于节点地址的操作
注:在链表的功能实现中,增加节点是动态开辟了一块空间,因此在删除节点时一定要释放节点所在空间,以免造成内存泄漏;在每个功能实现之前先考虑清楚实现此功能会遇到的各种情况;在函数传参时一定要清楚所传参数为值传递还是地址传递,形式参数的改变不会使实参跟着改变。
List.h
#pragma once
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
typedef int Datatype;
typedef struct ListNode
{
Datatype data;
struct ListNode* next;
}ListNode;
ListNode* BuyNode(Datatype d);
void Pushback(ListNode** pplist, Datatype d);
void Popback(ListNode** pplist);
void Pushfront(ListNode** pplist, Datatype d);
void Popfront(ListNode** pplist);
ListNode* Find(ListNode* plist, Datatype d);
void Insert(ListNode** pplist, ListNode* pos, Datatype d);
void Erase(ListNode** pplist, ListNode* pos);
void PrintList(ListNode* plist);
list.c
ListNode* BuyNode(Datatype d)//创建一个新的节点
{
ListNode* node=(ListNode
*)malloc(sizeof(ListNode));
node->data = d;
node->
next = NULL;
return node;
}
void Pushback(ListNode
** pplist, Datatype d)//尾插
{
//1.空
//
2.只有一个节点
//
3.多个节点
if(
*pplist==NULL)
{
*pplist=BuyNode(d);
}
else if((
*pplist)->
next==NULL)
{
(
*pplist)->
next=BuyNode(d);
}
else
{
ListNode* src=
*pplist;
while (src->
next != NULL)
{
src = src->
next;
}
src->
next = BuyNode(d);
}
}
void Popback(ListNode
** pplist)//尾删
{
//1.空
//
2.只有一个节点
//
3.多个节点
if(
*pplist==NULL)
{
return ;
}
else if ((
*pplist)->
next==NULL)
{
free(
*pplist);
*pplist=NULL;
}
else
{
ListNode* cur=
*pplist;
ListNode*
pos=cur;
while (cur->
next)
{
pos=cur;
//pos和cur指向同一个节点
cur=cur->
next;
//pos指向cur前一个节点
}
free(cur);
cur=NULL;
pos->
next=NULL;
}
}
void Pushfront(ListNode
** pplist, Datatype d)
{
if(
*pplist==NULL)
{
*pplist=BuyNode(d);
}
else
{
ListNode* tmp=BuyNode(d);
tmp->
next=
*pplist;
*pplist=tmp;
}
}
void Popfront(ListNode
** pplist)
{
if (
*pplist==NULL)
{
return ;
}
else
{
ListNode* tmp=(
*pplist)->
next;
free(
*pplist);
*pplist=NULL;
*pplist=tmp;
}
}
ListNode* Find(ListNode* plist, Datatype d)
{
//1.空
//
2.非空
ListNode*
pos=plist;
if(plist==NULL)
{
return NULL;
}
while (
pos)
{
if (
pos->data==d)
{
return pos;
}
pos=
pos->
next;
}
return NULL;
}
void PrintList(ListNode* plist)
{
ListNode*
pos=plist;
while(
pos)
{
printf(
"%d->",
pos->data);
pos=
pos->
next;
}
printf(
"NULL\n");
}
void Insert(ListNode
** pplist, ListNode*
pos, Datatype d)
{
//1.空
//
2.只有一个节点
//
3.要插入的位置恰好是头节点
//
4.有多个节点
assert(
pos);
if((
*pplist==NULL)||((
*pplist)->
next==NULL)||(
*pplist==
pos))
{
Pushfront(pplist, d);
}
else
{
ListNode* tmp=NULL;
ListNode* cur=
*pplist;
while (cur->
next!=
pos)
{
cur=cur->
next;
}
tmp=BuyNode(d);
cur->
next = tmp;
tmp->
next =
pos;
}
}
void Erase(ListNode
** pplist, ListNode*
pos)
{
assert(
pos);
//1.只有一个节点或空或恰好删第一个节点用头删
//
2.多个节点
if((
*pplist==NULL)||((
*pplist)->
next==NULL)||(
*pplist==
pos))
{
Popfront(pplist);
}
else
{
ListNode* tmp=
*pplist;
while (tmp->
next!=
pos)
{
tmp=tmp->
next;
}
tmp->
next=
pos->
next;
free(
pos);
pos=NULL;
}
}
test.c
#include"List.h"
void test1()
{
ListNode
*list=NULL;
Pushback(
&list,
1);
Pushback(
&list,
2);
Pushback(
&list,
3);
Pushback(
&list,
4);
PrintList(
list);
Popback(
&list);
Popback(
&list);
Popback(
&list);
Popback(
&list);
PrintList(
list);
}
void test2()
{
ListNode
* ret
=NULL;
ListNode
* list=NULL;
Pushfront(
&list,
4);
Pushfront(
&list,
3);
Pushfront(
&list,
2);
Pushfront(
&list,
1);
PrintList(
list);
ret
=Find(
list,
0);
printf(
"%p\n", ret);
Popfront(
&list);
Popfront(
&list);
Popfront(
&list);
Popfront(
&list);
PrintList(
list);
}
void test3()
{
ListNode
* list = NULL;
ListNode
* pos
= NULL;
Pushback(
&list,
1);
Pushback(
&list,
3);
pos
=Find(
list,
3);
Insert(
&list, pos,
2);
Pushback(
&list,
4);
pos
=Find(
list,
1);
Insert(
&list, pos,
0);
PrintList(
list);
pos
=Find(
list,
3);
Erase(
&list, pos);
pos
=Find(
list,
0);
Erase(
&list, pos);
PrintList(
list);
}
int main()
{
test3();
return 0;
}
测试结果
test1
test2
test3
若有错误之处,恳请留言指正