无头单向非循环链表（C语言实现）

有礼貌的灰绅士

发布于 2023-03-28 15:23:55

3720

发布于 2023-03-28 15:23:55

文章被收录于专栏：C++与Linux的学习之路

单链表

设计思路

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

实现增删查改的准备工作

分两个源文件，一个头文件：

linked.h linked.c test.c

结点类型的定义

//linked.h
typedef int type;//重新定义数据类型的名字，这样方便更换链表里面的数据类型
typedef struct Chain_table//链表类型
{
	type data;//数据域
	struct Chain_table* next;//指针域
}ct;

定义一个头节点

//test.c
	ct* head = NULL;//头结点指针

默认指向为空，如果没有数据就为空 开辟结点空间

//linked.c
ct* crunode(type x)//动态创建一个结点
{
	ct* cur = (ct*)malloc(sizeof(ct));
	if (cur == NULL)
	{
		perror("malloc fail");
		exit(-1);//程序结束
	}
	cur->data = x;
	cur->next = NULL;
	return cur;//返回开辟结点的地址
}

打印链表函数 这里不能断言是否为空指针，因为没有数据的时候头节点的指向的地方就是空指针，所以空指针我们也要打印（因为更形象，实际上并不需要打印NULL）

//linked.c
void SListPrint(ct* phead)//打印链表
{
	ct* cur = phead;//让cur也指向头指针的位置
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");//打印末尾的NULL
}

头插尾插

下面这些函数都是在linked.c文件中尾插

void SListPushBack(ct** phead, type x)//尾插
{
	assert(phead);//这里断言是因为phead指向的是头节点，所以不可能为空
	ct* newnode = crunode(x);
	if (*phead == NULL)//头节点指针为空
	{
		*phead = newnode;//让头节点指向新创建的结点
	}
	else//头节点指针不为空
	{
		ct* cur = *phead;
		while (cur->next)//找到最后一个结点
		{
			cur = cur->next;
		}
		cur->next = newnode;//让最后一个结点的next区域里面存储新创建结点的地址
	}
}

这里要注意，用二级指针把头节点的地址传过去，不然就导致了形参与实参开辟的是两个独立空间从而头节点不会因为调动函数而移动。

这样就能通过phead控制head了。头插

void SListPushFront(ct** phead, type x)//头插
{
	assert(phead);
	ct* newnode = crunode(x);
	newnode->next = *phead;
	*phead = newnode;
}

头插不需要分情况，因为就算链表里面为空，头插是将头节点指向的位置储存到新创建结点的next中。

头删尾删

尾删

void SListPopBack(ct** phead)//尾删
{
	assert(phead);
	assert(*phead);//判断是否为空链表
	ct* cur = *phead;
	if (cur->next == NULL)//判断链表中的结点是否只剩下一个结点
	{
		free(cur);
		cur = NULL;
		*phead = NULL;
	}
	else
	{
		while (cur->next->next)//判断是否走到了末尾
		{
			cur = cur->next;
		}
		free(cur->next);//cur->next->next为空就说明cur->next指向的是最后一个结点，释放掉
		cur->next = NULL;//将末尾节点的next置为空指针
	}
}

头删

void SListPopFront(ct** phead)//头删
{
	assert(phead);
	assert(*phead);//检查链表里面是否为空
	ct* cur = *phead;
	*phead = cur->next;
	free(cur);//释放头节点的空间
	cur = NULL;
}

查找与销毁

销毁

void SListDestory(ct** phead)//销毁链表
{
	assert(phead);
	ct* cur = *phead;
	while (cur)
	{
		ct* tai = cur->next;//保留cur的下一个结点
		free(cur);
		cur = tai;
	}
	*phead = NULL;//最后让头结点指针变成空指针
}

查找设计查找的时候返回值如果不等于空指针，就是存在

ct* SListFind(ct* phead, type x)//搜索
{
	ct* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;//找到返回对应的地址
		}
		cur = cur->next;
	}
	return NULL;//找不到就返回空指针
}

在pos之后插入数据为x的结点与删除pos后面的结点

这个配合我们的查找进行运作返回的pos后面一位的地址就是我们要插入和删除的地方插入

void SListInsertAfter(ct* pos, type x)//在pos之后插入数据为x的结点
{
	assert(pos);
	ct* newnode = crunode(x);
	newnode->next= pos->next;
	pos->next = newnode;
}

删除

void SListEraseAfter(ct* pos)//删除pos后面的结点
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;//如果pos后面的结点是空直接返回就好了
	}
	else 
	{
		ct* cur = pos->next;
		pos->next = cur->next;
		free(cur);
		cur = NULL;
	}
}

至于在pos前面插入和删除就不写了，只要加一个指针找到pos前面的结点就好了。

完整代码

linked.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int type;//重新定义数据类型的名字，这样方便更换链表里面的数据类型
typedef struct Chain_table//链表类型
{
	type data;//数据域
	struct Chain_table* next;//指针域
}ct;

//函数声明
ct* crunode(type x);//头节点的开辟
void SListPrint(ct* phead);//打印链表

void SListPushBack(ct** phead, type x);//尾插
void SListPushFront(ct** phead, type x);//头插
void SListPopBack(ct** phead);//尾删
void SListPopFront(ct** phead);//头删

void SListDestory(ct** phead);//销毁链表
ct* SListFind(ct* phead, type x);//查找

void SListInsertAfter(ct* pos, type x);//在pos之后插入数据为x的结点
void SListEraseAfter(ct* pos);//删除pos后面的结点

linked.c

#include "linked.h"
ct* crunode(type x)//动态创建一个结点
{
	ct* cur = (ct*)malloc(sizeof(ct));
	if (cur == NULL)
	{
		perror("malloc fail");
		exit(-1);//程序结束
	}
	cur->data = x;
	cur->next = NULL;
	return cur;//返回开辟结点的地址
}
void SListPrint(ct* phead)//打印链表
{
	ct* cur = phead;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");//打印末尾的NULL
}
void SListPushBack(ct** phead, type x)//尾插
{
	assert(phead);
	ct* newnode = crunode(x);
	if (*phead == NULL)//头节点指针为空
	{
		*phead = newnode;
	}
	else//头节点指针不为空
	{
		ct* cur = *phead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}
void SListPushFront(ct** phead, type x)//头插
{
	assert(phead);
	ct* newnode = crunode(x);
	newnode->next = *phead;
	*phead = newnode;
}
void SListPopBack(ct** phead)//尾删
{
	assert(phead);
	assert(*phead);
	ct* cur = *phead;
	if (cur->next == NULL)
	{
		free(cur);
		cur = NULL;
		*phead = NULL;
	}
	else
	{
		while (cur->next->next)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
}
void SListPopFront(ct** phead)//头删
{
	assert(phead);
	assert(*phead);//检查链表里面是否为空
	ct* cur = *phead;
	*phead = cur->next;
	free(cur);//释放头节点的空间
	cur = NULL;
}
void SListDestory(ct** phead)//销毁链表
{
	assert(phead);
	ct* cur = *phead;
	while (cur)
	{
		ct* tai = cur->next;
		free(cur);
		cur = tai;
	}
	*phead = NULL;
}
ct* SListFind(ct* phead, type x)//搜索
{
	ct* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SListInsertAfter(ct* pos, type x)//在pos之后插入数据为x的结点
{
	assert(pos);
	ct* newnode = crunode(x);
	newnode->next= pos->next;
	pos->next = newnode;
}
void SListEraseAfter(ct* pos)//删除pos后面的结点
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else 
	{
		ct* cur = pos->next;
		pos->next = cur->next;
		free(cur);
		cur = NULL;
	}
}

test.c

#include "linked.h"
void test()
{
	ct* head = NULL;//头节点指针
	SListPushBack(&head, 1);//尾插
	SListPushBack(&head, 2);
	SListPushFront(&head, 3);//头插
	SListPushFront(&head, 4);
	SListPopFront(&head);//头删
	SListPopBack(&head);//尾删
	ct* pos = SListFind(head, 1);//查找
	if (pos)
	{
		printf("YES\n"); 
		SListInsertAfter(pos, 9);
		SListPrint(head);//打印链表
		SListEraseAfter(pos);
	}
	else
	{
		printf("NO\n");
	}
	SListPrint(head);
	SListDestory(&head);//销毁链表
	SListPrint(head);

}
int main()
{
	test();
	return 0;
}

代码运行结果