C语言实现单链表的代码教程
程序员文章站
2022-04-17 08:57:28
LinkList.h //这里面主要放函数声明,头文件等
#ifndef __LINKLIST_H__
#define __LINKLIST_H__
#include...
LinkList.h //这里面主要放函数声明,头文件等
#ifndef __LINKLIST_H__ #define __LINKLIST_H__ #include #include #include typedef int DataType; typedef struct Node { DataType data; struct Node* next; }Node; void InitLinkList(Node**pphead);//初始化链表 Node* BuyNode(DataType x);//创建一个结点 void PrintList(Node *phead);//打印链表 不改变结点指针指向,因此传一级指针即可 void PushBack(Node**pphead, DataType x);//尾插一个结点 void PopBack(Node**phead);//尾删一个结点 void PushFront(Node**pphead, DataType x);//头插一个结点 void PopFront(Node**phead);//头删一个结点 Node*Find(Node*pphead, DataType x);//找一个结点 不改变结点指针指向,因此传一级指针即可 void Erase(Node**pphead, Node*pos);//删除指定位置结点 void Insert(Node**pphead, Node*pos, DataType x);//在指定位置前插入一个节点 #endif
LinkList.c //这里面主要放各个函数的实现
#include"LinkList.h" void InitLinkList(Node ** pphead) { assert(pphead); *pphead = NULL; } Node* BuyNode(DataType x) { //开辟空间 Node *node=(Node*)malloc(sizeof(Node)); //赋值 node->next = NULL; node->data = x; return node; } void PrintList(Node *phead) { //1.空 if (phead == NULL) { printf("NULL\n"); return; } //2.非空 while (phead) { printf("%d->", phead->data); phead = phead->next; } printf("NULL\n"); } void PushBack(Node**pphead, DataType x) { assert(pphead);//检查参数 Node*tail = *pphead; //1.空 if (*pphead == NULL) { *pphead =BuyNode(x); } //2.非空 else { //找尾 while (tail->next) { tail = tail->next; } //插入 tail->next = BuyNode(x); } } void PopBack(Node**pphead) { //检查参数 assert(pphead); //1.空 if (*pphead == NULL) { return; } //2.有一个结点 else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } //3.两个及其两个以上结点 else { //找尾的前一个结点 Node *prev = NULL;//用于找最后一个结点的前一个结点 不能直接释放尾,否则指向尾结点的指针野指针,因此要找到指向尾的指针,置成空 Node *tmp = *pphead;//找最后一个结点 while (tmp->next) { prev = tmp; tmp = tmp->next; } prev->next = NULL; free(tmp);//切记一定要释放,因为它是malloc出来的,也就是动态开辟出来的 。否则内存泄漏 tmp = NULL; } } void PushFront(Node**pphead, DataType x) { assert(pphead);//检查参数 //1.链表为空 if (*pphead==NULL) { *pphead = BuyNode(x); } //2.链表非空 else { Node *tmp = BuyNode(x); tmp->next = *pphead; *pphead = tmp; } } void PopFront(Node**pphead) { assert(pphead);//检查参数 //1.空 if (*pphead == NULL) { return; } //2.一个结点 else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } //3.两个及两个以上结点 else { Node *next = (*pphead)->next;//第二个结点 free(*pphead); *pphead = next; } } Node*Find(Node*phead, DataType x) { assert(phead);//检查参数 Node*cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL;//没找到 } void Insert(Node**pphead, Node*pos, DataType x) { assert(pphead);//检查参数 //1.pos为头结点 if (pos == *pphead) { PushFront(pphead, x); } //2.非头结点 else { Node*prev = *pphead;//找pos前一个结点 Node*tmp = BuyNode(x); while (prev->next !=pos) { prev = prev->next; } prev->next = tmp; tmp->next = pos; } } void Erase(Node**pphead, Node*pos) { assert(pphead);//检查参数 //1.pos为头节点 if (*pphead == pos) { PopFront(pphead); } //2.pos为尾结点 else if (pos->next == NULL) { PopBack(pphead); } //3.非头尾结点 else { Node *prev = *pphead; Node* next = pos->next; if (prev->next != pos) { prev = prev->next; } prev->next = next; free(pos); pos = NULL; } }
test.c //测试
#include"LinkList.h" void test1() { //测试PopBack,PushBack Node *list = NULL; PrintList(list); PushBack(&list, 4); PushBack(&list, 3); PushBack(&list, 2); PushBack(&list, 1); PopBack(&list); PopBack(&list); PrintList(list); PopBack(&list); PopBack(&list); PrintList(list); } void test2() { //测试PopFront,PushFront Node *list = NULL; PushFront(&list, 1); PushFront(&list, 2); PushFront(&list, 3); PushFront(&list, 4); PrintList(list); PopFront(&list); PrintList(list); PopFront(&list); PopFront(&list); PopFront(&list); PrintList(list); } void test3() { //测试Find Insert Erase Node *list = NULL; PushFront(&list, 1); PushFront(&list, 2); PushFront(&list, 3); PushFront(&list, 4); PrintList(list); Node* pos = Find(list, 4); Insert(&list, pos, 20); PrintList(list); Insert(&list, pos->next, 30); PrintList(list); Erase(&list, pos); PrintList(list); } int main() { //test1(); //test2(); test3(); system("pause"); return 0; }