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