[C语言][数据结构][链表] 单链表的从零实现!

目录

零.必备知识

1.一级指针 && 二级指针

2. 节点的成员列表

    a.数据

    b.指向下一个节点的指针.

3. 动态内存空间的开辟 (malloc-calloc-realloc)

一.单链表的实现与销毁 

注:具体解释都在代码的注释中!(在代码中具体分析)

        1.1 节点的定义

        1.2 单链表的尾插

        1.3 单链表的头插

        1.4 单链表的尾删

        1.5 单链表的头删 

        1.6 单链表的查找

        1.7 在指定位置之前插入数据

        1.8 在指定位置之后插入数据

        1.9 删除指定位置的数据

        1.10 删除指定位置之后的数据

        1.11 销毁单链表 

二. 单链表源码

SingleList.h

#define  _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 节点的定义
typedef int SLTDateType;
typedef struct SingleListNode
{
	SLTDateType date;
	struct SingleListNode* next;
}SLTNode;

// 单链表的展示
void SLTPrint(SLTNode* phead);
// 单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
// 单链表的尾删
void SLTPopBack(SLTNode** pphead);
// 单链表的头删
void SLTPopFront(SLTNode** pphead);
// 单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x);
// 在指定位置之前插入数据
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 删除指定位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除指定位置之后的数据
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);
// 销毁单链表
void SLTDestroy(SLTNode** pphead);

SingleList.c 

#define  _CRT_SECURE_NO_WARNINGS
#include "SingleList.h"
// 单链表的展示
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead; //current 当前的,现在的  currect 正确的
	while (pcur != NULL) {
		printf("%d->", pcur->date);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
// 节点的创造
SLTNode* SLTCreat(SLTDateType x)
{
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newNode == NULL) {
		printf("创建失败!\n");
		exit(1);
	}
	newNode->date = x;
	newNode->next = NULL;
	return newNode;
}
// 单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	// 创建节点
	SLTNode* newNode = SLTCreat(x);
	// 没有节点
	if ((*pphead) == NULL) {
		(*pphead) = newNode;
	}
	else { // 有一个或多个节点
		SLTNode* pcur = (*pphead);
		while (pcur->next != NULL) {
			pcur = pcur->next;
		}
		pcur->next = newNode;
	}
}
// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* pcur = (*pphead);
	// 创建节点
	SLTNode* newNode = SLTCreat(x);
	// 没有节点
	if ((*pphead) == NULL) {
		(*pphead) = newNode;
	}
	else { // 有一个或者多个节点
		newNode->next = (*pphead);
		(*pphead) = newNode;
	}
}
// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && (*pphead));
	SLTNode* pcur = (*pphead);
	SLTNode* prev = (*pphead);
	// 只有一个节点
	if (pcur->next == NULL) {
		free(*pphead);
		(*pphead) = NULL;
		pcur = NULL;
		prev = NULL;
	}
	else { // 有多个节点
		while (pcur->next != NULL) {
			prev = pcur;
			pcur = pcur->next;
		}
		free(pcur);
		pcur = NULL;
		prev->next = NULL;
	}
}
// 单链表的头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && (*pphead));
	SLTNode* pcur = (*pphead);
	// 只有一个节点
	if (pcur->next == NULL) {
		free(*pphead);
		(*pphead) = NULL;
		pcur = NULL;
	}
	else { //有多个节点
		(*pphead) = (*pphead)->next;
		free(pcur);
		pcur = NULL;
	}
}
// 单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* pcur = phead;
	while (pcur != NULL) {
		if (pcur->date == x) {
			printf("找到了!\n");
			return pcur;
		}
		pcur = pcur->next;
	}
	printf("找不到!\n");
	return NULL;
}
// 在指定位置之前插入数据
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	SLTNode* pcur = (*pphead);
	// 创建节点
	SLTNode* newNode = SLTCreat(x);
	// 头插
	if (pos == (*pphead) || (*pphead) == NULL) {
		SLTPushFront(pphead, x);
	}
	else { //正常插入
		while (pcur->next != NULL) {
			if (pcur->next == pos) {
				newNode->next = pcur->next;
				pcur->next = newNode;
				break;
			}
			pcur = pcur->next;
		}
	}
}
// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	// 创建节点
	SLTNode* newNode = SLTCreat(x);
	if ((*pphead) == NULL || pos == (*pphead)) {
		// 尾插
		SLTPushBack(pphead, x);
	}
	else { //正常插入
		SLTNode* pcur = (*pphead);
		while (pcur->next != NULL) {
			if (pcur == pos) {
				newNode->next = pcur->next;
				pcur->next = newNode;
				break;
			}
			pcur = pcur->next;
		}
	}
}
// 删除指定位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && (*pphead));
	// 处理特殊情况(头删)
	if ((*pphead) == pos) {
		SLTPopFront(pphead);
	}
	else {
		SLTNode* prev = (*pphead);
		SLTNode* pcur = (*pphead);
		while (pcur != NULL) {
			if (pcur == pos) {
				prev->next = pcur->next;
				free(pcur);
				pcur = NULL;
				prev = NULL;
				break;
			}
			prev = pcur;
			pcur = pcur->next;
		}
	}
}
// 删除指定位置之后的数据
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && (*pphead));
	SLTNode* pcur = (*pphead);
	while (pcur->next != NULL) {
		if (pcur == pos) {
			SLTNode* tmp = pcur->next;
			pcur->next = pcur->next->next;
			free(tmp);
			tmp = NULL;
			break;
		}
		pcur = pcur->next;
	}
}
// 销毁单链表
void SLTDestroy(SLTNode** pphead)
{
	assert(pphead && (*pphead));
	SLTNode* pcur = (*pphead);
	SLTNode* prev = (*pphead);
	while (pcur != NULL) {
		prev = pcur;
		pcur = pcur->next;
		free(prev);
	}
	prev = NULL;
	(*pphead) = NULL;
}