单向不带头链表

  • 开发
  • 37

单向不带头链表

一、单项不带头链表结构

 1.什么是链表？
  我的理解是链表是一种逻辑上是线性结构，在真正的内存空间中是非线性，一般而言，不连续的结构，它是通过在堆区一块一块申请空间，用指针把各块空间连起来的结构，也就保存各块空间的地址来连接！！！
  下面给出链表的结构！

typedef int SLTDataType;
typedef struct SListNode
{
   
	//存储数据
	SLTDataType val;
	//存储下一块空间的地址
	struct SListNode* next;
}SListNode;

  简单认识链表的物理结构！
1
一个区域存下一个区域的地址，一个区域存数据，这样就用地址把申请的空间链接起来了!

下面实现一下接口：
//申请节点
SListNode* BuySListNode(SLTDataType x);
//打印链表
void SListPrint(SListNode* phead);
//释放节点
void SListDestory(SListNode** pphead);
//尾插
void SListPushBack(SListNode** pphead,SLTDataType x);
//头插
void SListPushFront(SListNode** pphead,SLTDataType x);
//尾删
void SListPopBack(SListNode** pphead);
//头删
void SListPopFront(SListNode** pphead);
//查找节点
SListNode* FindSList(SListNode* phead,SLTDataType x);
//删除指定位置pos
void SListErase(SListNode** pphead,SListNode* pos)
//在pos节点之后插入
void SListInsertAfter(SListNode* pos,SLTDataType x)
//删除pos后面的一个节点
void SListEraseAfrer(SListNode* pos);

下面实现一下这个接口
//先大概写一下测试文件

//Test.c -- 测试文件
#include "SList.h"


void SListTest()
{
   
	SListNode* phead = NULL;
	SListPushBack(&phead, 1);
	SListPushBack(&phead, 2);
	SListPushBack(&phead, 3);
	SListPushBack(&phead, 4);
	SListPrint(phead);
	//SListPushFront(&phead, 4);
	//SListPushFront(&phead, 3);
	//SListPushFront(&phead, 2);
	//SListPushFront(&phead, 1);
	//SListPrint(phead);
	//SListPopBack(&phead);
	//SListPopBack(&phead);
	//SListPopBack(&phead);
	//SListPopBack(&phead);
	//SListPrint(phead);
	//SListPopFront(&phead);
	//SListPopFront(&phead);
	//SListPopFront(&phead);
	//SListPopFront(&phead);
	//SListPrint(phead);
	SListNode* find = SListFind(phead,1);
	//SListErase(&phead, find);
	//SListPrint(phead);
	SListInsertAfter(find,11);
	SListPrint(phead);
	//SListEraseAfter(find);
	//SListPrint(phead);
}
int main()
{
   
	SListTest();
	return 0;
}

//尾插怎么写?
//1.考虑没有节点的情况。
//2.考虑有节点的情况。直接插在尾巴后面

void  SListPushBack(SListNode** pphead, SLTDataType  x)
{
   
	//二级指针不能传null
	assert(pphead);
	//申请节点
	SListNode* newnode = BuySListNode(x);
	//1.一个节点问题
	if (*pphead == NULL)
	{
   
		*pphead = newnode;
	}
	//2.其它
	else {
   
		SListNode* cur = *pphead;
		while (cur->next)
		{
   
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

//头插怎么写？
//头插有点特殊，不用考虑任何情况，可以直接头插
//因为刚开始SListNode* plist = NULL;刚开始给的是NULL，NULL也是一个地址，所以，申请一个新的节点，可以直接存NULL。
//代码如下

void SListPushFront(SListNode** pphead, SLTDataType  x)
{
   
	//二级指针不能传null
	assert(pphead);
	//申请节点
	SListNode* newnode = BuySListNode(x);
	newnode->next = (*pphead);
	*pphead = newnode;
}

//尾删怎么写？
//要考虑清楚一件事，要正常尾删，必须要能找到前一个节点。因此，考虑只有一个节点和其它节点两种情况！

void  SListPopBack(SListNode** pphead)
{
   
	assert(pphead);
	//链表不能为NULL
	assert(*pphead);
	//1.1个节点
	if ((*pphead)->next == NULL)
	{
   
		free(*pphead);
		*pphead = NULL;
	}
	else{
   
		//2.至少2个节点问题
		SListNode* cur = *pphead;
		SListNode* prev = NULL;
		while (cur->next)
		{
   
			prev = cur;
			cur = cur->next;
		}
		//删除节点
		prev->next = NULL;
		free(cur);
		cur = NULL;
	}
}

//头删怎么写？
//要考虑头删怎么写，要删除头，把下一个节点存起来，当做newHead,即使下一个节点是NULL,也可以存起来，所以只有一种情况！

void  SListPopFront(SListNode** pphead)
{
   
	assert(pphead);
	//检测是否有节点
	assert(*pphead);
	SListNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

//在pos节点之后插入，怎么写？
//可以把pos后面的先存起来，然后在pos之后插入
//或先把节点插在pos之后节点的前面，在把pos里面存新节点

void SListEraseAfter(SListNode* pos)
{
   
	assert(pos);
	//assert(pos->next);
	if (pos->next == NULL)
	{
   
		printf("pos之后的节点为null\n");
		return;
	}
	SListNode* next = pos->next;
	SListNode* nnext = pos->next ->next;
	pos->next = nnext;
	free(next);
	next = NULL;
}

//怎样删除pos之后节点？
//1.检测pos之后是不是NULL节点
//2.保存pos后面的后面节点（NULL没有影响),删除pos之后的节点，在链接保存的节点

void SListEraseAfter(SListNode* pos)
{
   
	assert(pos);
	//assert(pos->next);
	if (pos->next == NULL)
	{
   
		printf("pos之后的节点为null\n");
		return;
	}
	SListNode* next = pos->next;
	SListNode* nnext = pos->next ->next;
	pos->next = nnext;
	free(next);
	next = NULL;
}

//怎样删除pos节点？
//要删除pos节点，就要找前面和后面（后面的为NULL也可以），但是前面不能没有节点
//因此，考虑pos前面没有节点和有节点
//pos前面没有节点，pos是头，直接头删
//pos前面有节点，正常删除

//删除指定位置
void SListErase(SListNode** pphead,SListNode* pos)
{
   
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//考虑pos前面没有节点
	if (*pphead == pos)
	{
   
		SListPopFront(pphead);
	}
	//其它
	else {
   
		SListNode* prev = *pphead;
		while (prev->next!=pos)
		{
   
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//打印存储的数据
//直接遍历即可

void SListPrint(SListNode* phead)
{
   
	SListNode* cur = phead;
	while (cur)
	{
   
		printf("->%d", cur->val);
		cur = cur->next;
	}
	printf("->NULL\n");
}
//把堆区申请的空间还给操作系统 
void SListDestory(SListNode** pphead)
{
   
	SListNode* cur = *pphead;
	while (cur)
	{
   
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

完整代码

//SList.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>


typedef int SLTDataType;
typedef struct SListNode
{
   
	SLTDataType val;
	struct SListNode* next;
}SListNode;

SListNode* BuySListNode(SLTDataType x);
void SListPrint(SListNode* phead);
void  SListPushBack(SListNode** pphead, SLTDataType  x);
void SListPushFront(SListNode** pphead, SLTDataType  x);
void  SListPopBack(SListNode** pphead);
void  SListPopFront(SListNode** pphead);
SListNode* SListFind(SListNode* phead);
//删除指定指点位置
void SListErase(SListNode** pphead,SListNode* pos);
void SListInsertAfter(SListNode* pos, SLTDataType x);
void SListEraseAfter(SListNode* pos);
void SListDestory(SListNode** pphead);


//sList.c
#include "SList.h"

SListNode* BuySListNode(SLTDataType x)
{
   
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
   
		perror("BuySListNode malloc fail!");
		return 1;
	}
	//申请成功
	newnode->next = NULL;
	newnode->val = x;
	return newnode;
}

void SListPrint(SListNode* phead)
{
   
	SListNode* cur = phead;
	while (cur)
	{
   
		printf("->%d", cur->val);
		cur = cur->next;
	}
	printf("->NULL\n");
}
void  SListPushBack(SListNode** pphead, SLTDataType  x)
{
   
	//二级指针不能传null
	assert(pphead);
	//申请节点
	SListNode* newnode = BuySListNode(x);
	//1.一个节点问题
	if (*pphead == NULL)
	{
   
		*pphead = newnode;
	}
	//2.其它
	else {
   
		SListNode* cur = *pphead;
		while (cur->next)
		{
   
			cur = cur->next;
		}
		cur->next = newnode;
	}
}


void SListPushFront(SListNode** pphead, SLTDataType  x)
{
   
	//二级指针不能传null
	assert(pphead);
	//申请节点
	SListNode* newnode = BuySListNode(x);
	newnode->next = (*pphead);
	*pphead = newnode;
}


void  SListPopBack(SListNode** pphead)
{
   
	assert(pphead);
	//链表不能为NULL
	assert(*pphead);
	//1.1个节点
	if ((*pphead)->next == NULL)
	{
   
		free(*pphead);
		*pphead = NULL;
	}
	else{
   
		//2.至少2个节点问题
		SListNode* cur = *pphead;
		SListNode* prev = NULL;
		while (cur->next)
		{
   
			prev = cur;
			cur = cur->next;
		}
		//删除节点
		prev->next = NULL;
		free(cur);
		cur = NULL;
	}
}


void  SListPopFront(SListNode** pphead)
{
   
	assert(pphead);
	//检测是否有节点
	assert(*pphead);
	SListNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

SListNode* SListFind(SListNode* phead,SLTDataType x)
{
   
	//不能为NULL
	assert(phead);
	SListNode* cur = phead;
	while (cur)
	{
   
		if (cur->val == x)
		{
   
			return cur;
		}
		cur = cur->next;
	}
	//找不到，为NULL
	return NULL;
}

void SListInsertAfter(SListNode* pos, SLTDataType x)
{
   
	assert(pos);
	//申请节点
	SListNode* newnode = BuySListNode(x);
	SListNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}

void SListEraseAfter(SListNode* pos)
{
   
	assert(pos);
	//assert(pos->next);
	if (pos->next == NULL)
	{
   
		printf("pos之后的节点为null\n");
		return;
	}
	SListNode* next = pos->next;
	SListNode* nnext = pos->next ->next;
	pos->next = nnext;
	free(next);
	next = NULL;
}

//删除指定位置
void SListErase(SListNode** pphead,SListNode* pos)
{
   
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//考虑pos前面没有节点
	if (*pphead == pos)
	{
   
		SListPopFront(pphead);
	}
	//其它
	else {
   
		SListNode* prev = *pphead;
		while (prev->next!=pos)
		{
   
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

void SListDestory(SListNode** pphead)
{
   
	SListNode* cur = *pphead;
	while (cur)
	{
   
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

//测试代码
#include "SList.h"


void SListTest()
{
   
	SListNode* phead = NULL;
	SListPushBack(&phead, 1);
	SListPushBack(&phead, 2);
	SListPushBack(&phead, 3);
	SListPushBack(&phead, 4);
	SListPrint(phead);
	//SListPushFront(&phead, 4);
	//SListPushFront(&phead, 3);
	//SListPushFront(&phead, 2);
	//SListPushFront(&phead, 1);
	//SListPrint(phead);
	//SListPopBack(&phead);
	//SListPopBack(&phead);
	//SListPopBack(&phead);
	//SListPopBack(&phead);
	//SListPrint(phead);
	//SListPopFront(&phead);
	//SListPopFront(&phead);
	//SListPopFront(&phead);
	//SListPopFront(&phead);
	//SListPrint(phead);
	SListNode* find = SListFind(phead,1);
	//SListErase(&phead, find);
	//SListPrint(phead);
	SListInsertAfter(find,11);
	SListPrint(phead);
	//SListEraseAfter(find);
	//SListPrint(phead);
	SListDestory(&phead);
}
int main()
{
   
	SListTest();
	return 0;
}

完结！！！

阅读全部

相关推荐

  7. 数据结构基础（不带头节点的单向非循环链表）

    2024-02-21 11:20:03       59 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-02-21 11:20:03       98 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-02-21 11:20:03       106 阅读

  9. 在Django里面运行非项目文件

    2024-02-21 11:20:03       87 阅读

  19. Python语言-面向对象

    2024-02-21 11:20:03       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-02-21 11:20:03       91 阅读

热门阅读

  5. bash shell实现简易进度条

    2024-02-21 11:20:03       56 阅读

  11. MySQL 的存储引擎（基本介绍）

    2024-02-21 11:20:03       57 阅读

  13. 数据权限设计思考

    2024-02-21 11:20:03       52 阅读

  26. .net 微服务 服务保护 自动重试 Polly

    2024-02-21 11:20:03       52 阅读

  27. C++ 中的单例模式singleton

    2024-02-21 11:20:03       47 阅读

  28. 设计模式----单例模式

    2024-02-21 11:20:03       45 阅读

  29. 指定截至频率的低通滤波器设计

    2024-02-21 11:20:03       49 阅读