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*p