C语言实现单链表_c语言单链表实现

一、什么是链表

        链表是用来作为一种数据结构来存储数据的，它可以做到需要存储一个数据时便会向内存空间申请一块地址，并不会产生空间上的浪费。本篇博客将介绍单链表的功能以及实现。

二、代码的实现

        单链表在具体更改其存储的数据时，需要用到二级指针。因为我们在最开始定义单链表时创建的结构体指针指向NULL，而它的类型是结构体指针，我们如果想要改变实参就需要穿这个结构体指针的地址，再进行解应用来完成单链表的功能。而在打印、查询等不需要更改单链表内容的功能中，我们只用一级指针便可以完成相应的功能。

        具体实现方法在注释中，供借鉴。我们需要三个文件。

        SList.h用来存放一些函数以及其他所需变量的声明。

        SList.c用来实现函数的定义。

        list_test.c用来进行测试。

//SList.h文件
 
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//一些需要的库函数
typedef int SLType;//便于更改，重定义单链表存储的数据类型
typedef struct SList
{
	struct SList * next;
	SLType data;
}SL;
//定义结构体，由于单链表是一个结点找到下一个结点，
//所以应当采用结构体指针来存储下一个结点的地址
 
void SLPush(SL** pphead,SLType x);//尾插
 
void SLPrint(SL* phead);//打印
 
void SLPop(SL** pphead);//尾删
 
void SLPushFront(SL** pphead, SLType x);//头插
 
void SLPopFront(SL** pphead);//头删
 
int SLFind(SL* phead,SLType x);//查找
 
void SLInsert(SL** pphead, int pos, SLType x);//在指定位置插入一个元素
 
void SLPopPos(SL** pphead, int pos);//删除指定位置元素

SList.c文件
 
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void SLPush(SL** pphead, SLType x)//尾插功能的实现，传入的是头指针的地址
{
	SL* newNode = (SL*)malloc(4 + sizeof(SLType));
	newNode->next = NULL;
	newNode->data = x;//创建最后一个尾结点
	if (*pphead == NULL)//单链表为空的情况下
	{
		*pphead = newNode;
	}//则直接解应用把我们的头指针指向创建的结点
	else//如果链表不为空的情况下
	{
		SL* ptail = *pphead;//创建一个尾指针来寻找最后一个结点
		while (ptail->next != NULL)
		{
			ptail = ptail->next;
		}//找到最后一个结点
		ptail->next = newNode;//把最后一个结点的next指向新创建的结点
	}
}
 
void SLPrint(SL* phead)//单链表的打印
{
	if (phead == NULL)//链表为空的情况下
	{
		printf("NULL");//直接打印NULL
	}
	else
	{
		while (phead->next != NULL)
		{
			printf("%d", phead->data);
			printf("->");
			phead = phead->next;
		}//打印到最后一个结点的前一个结点
		printf("%d", phead->data);//打印最后一个结点
		printf("\n");
 
	}
}
 
void SLPop(SL** pphead)//尾删操作
{
	if (*pphead == NULL)//在链表为空的情况下，直接采用暴力方式退出
	{
		assert(*pphead);
		exit(-1);
	}
	else if ((*pphead)->next == NULL)//链表只有一个元素的情况下
	{
		free(*pphead);//释放掉唯一一个结点的空间
		*pphead = NULL;//把头指针重新指向NULL
	}
	else//链表由两个及两个元素的情况下
	{
		
		SL* ptail = *pphead;//定义ptail指针来找到尾结点
		SL* prev = ptail;//定义一个prev指针来找到最后一个结点的前一个结点
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}//完成上述操作
		free(ptail);//释放掉最后一个结点的空间
		prev->next = NULL;//将尾结点的上一个结点的next指向NULL
 
	}
}
void SLPushFront(SL** pphead, SLType x)//头插
{
	
	SL* newNode = (SL*)malloc(4 + sizeof(SLType));
	newNode->next = NULL;
	newNode->data = x;//创建新结点
	if (*pphead == NULL)//链表中没有元素
	{
		*pphead = newNode;//把头指针直接指向新节点
	}
	else//链表中有至少一个元素
	{
		SL* temP = *pphead;//将最初头指针指向的结点的地址存放在一个临时变量中
		newNode->next = temP;//新节点的next指向原来的第一个结点
		*pphead = newNode;//把头指针指向新节点
	}
}
void SLPopFront(SL** pphead)//头删
{
	if (*pphead == NULL)//如果链表中没有元素直接警告
	{
		assert(*pphead!=NULL);
		exit(-1);
	}
	else//链表中有至少一个元素
	{
		SL* temP = (*pphead)->next;
		free(*pphead);
		*pphead = temP;
	}
}
 
int SLFind(SL* phead,SLType x)//查找，如果查找到元素则返回位置，没找到则返回0
{
	int count = 1;//记录元素在第几个结点
	assert(phead != NULL);//判断链表是否为空
	while (phead->next != NULL)
	{
		if (phead->data == x)
		{
			return count;
		}
		count++;
		phead = phead->next;
	}//判断到尾结点的前一个结点
	if (phead->data == x)//判断尾结点
		return count;
	printf("没找到\n");
	return 0;
}
 
 
void SLInsert(SL** pphead, int pos, SLType x)//在指定位置插入元素
{
	
	SL* des = *pphead;//用来找到目标位置的后一个位置
	SL* prev = *pphead;//用来找到目标位置
	SL* newNode = (SL*)malloc(4 + sizeof(SLType));
	newNode->data = x;
	newNode->next = (*pphead);//创建新结点
	if (pos == 1)
	{
		*pphead = newNode;//如果pos为1，则按头插处理
 
	}
	else//其他情况下，由于暴力退出，不可以在最后插入元素
	{
		for (int i = 1; i < pos; i++)//循环找到需要插入元素的位置
		{
			prev = des;
			des = des->next;
			assert(des!=NULL);//判断pos是否合法
		}
		newNode->next = des;//把新节点的next指向pos的下一个结点的地址
		prev->next = newNode;//前一个结点的next指向新的结点
	}
 
 
}
void SLPopPos(SL** pphead, int pos)//删除指定位置元素
{
	
	assert(*pphead != NULL);//判断链表是否为空
 
	SL* pdes = *pphead;//找到指定位置
	SL* prev = NULL;//找到指定位置的前一个位置
	for (int i = 1; i < pos; i++)
	{
		prev = pdes;
 
		pdes = pdes->next;
		assert(pdes != NULL);//判断pos是否
 
	}//完成上述操作
	if (pos == 1)//如果pos为1按头删处理
	{
		SL* tem = (*pphead)->next;
		free(*pphead);
		*pphead = tem;
	}
	else//其他情况下
	{
		SL* tem = pdes->next;
		free(pdes);//释放被删除的空间
		prev->next = tem;
	}
}

list_test.c文件下
 
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
int main()
{
	return 0;
}

读者可自己进行测试，在x86的环境下。