欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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;
}