单向链表

实现一个基本具有增删查改功能的单向链表

基本思想：结构体内含有一个节点数据变量和指向下一节点的指针变量，最后一个节点内的指针变量为空，如下图所示，基本操作都是基于节点地址的操作

注：在链表的功能实现中，增加节点是动态开辟了一块空间，因此在删除节点时一定要释放节点所在空间，以免造成内存泄漏；在每个功能实现之前先考虑清楚实现此功能会遇到的各种情况；在函数传参时一定要清楚所传参数为值传递还是地址传递，形式参数的改变不会使实参跟着改变。

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);//在pos位置前面插入 void Erase(ListNode** pplist, ListNode* pos);//删除位置为pos的节点 void PrintList(ListNode* plist);//打印列表

list.c

#include "List.h" 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() { //test1(); //test2(); test3(); return 0; }

测试结果

test1

test2

test3

若有错误之处，恳请留言指正