数据结构——单链表（上）

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

结构分为物理结构和逻辑结构逻辑结构就像下图一样在下面的代码实现中我们会想象指针plist会不断的移动而图片中的箭头其实也是一种逻辑结构是为了我们方便理解而形象地画出来的。与逻辑结构相反在物理结构中是不存在下图中的箭头的指针也不会移动只是其中的内容在不断的改变而链表也只是一个个的内存块

3.2链表的分类

上图的结构只是链表的一种结构实际中链表的结构非常多样以下情况组合起来就有八种链表结构

①单向或者双向

②带头或者不带头

③ 循环或者非循环

虽然有这么多的链表结构但是我们实际中最常用的还是这两种结构无头单向非循环链表和带头双向循环链表

1、无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了

3.3链表的实现【无头单向非循环】

3.3.1模块化

为了后续代码的不断优化和调试方便我们这次依旧采取模块化的方式来实现无头单向非循环链表。整个工程共分为三个部分SList.c[具体功能的实现]、SList.h[函数、变量的声明]、text.c[测试部分]

3.3.2 变量的定义

在这一部分我们先是定义了一个结构体变量作为我们链表的每一个单元。那么链表的内容大致可以分为两部分一部分是根据实际需求所要存储的信息另一部分则是指向下一个结点【内存单元】的指针变量。为了提高链表的灵活性我们还对存储信息的类型进行了重定义方便后期的修改。具体代码如下

typedef int SLTDataType;	//存储信息为整型
typedef struct SListNode
{
	SLTDataType data;		//存储信息
	struct SListNode* next;//指向下一个结点的结构体指针
}SListNode;

3.3.3动态申请一个结点

无论是对链表内容的头插、尾插、以及指定位置的插入都需要对结点的申请因此我们提取了一个函数专门用来动态申请一个结点避免代码在多个函数中的重复。在看过往期关于动态内存管理函数的博文的小伙伴们们应该是轻车熟路了首先就是像内存申请一个结构体大小的内存注意在申请后一定要对内存函数返回的参数进行判断若是为空则说明结点的内存空间开辟失败最后就是对所开辟空间的内容修改了主要是依据个人需求来编写具体代码实现如下

//结点的动态申请
SListNode* BuySLTNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));	//申请一个结构体大小的内存空间
	if (newnode == NULL)	//对返回的指针进行检查
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;	//结点信息的编写
	newnode->next = NULL;
	return newnode;
}

3.3.4单链表的尾插

在申请完结点之后就是将结点插入链表了插入的方式有很多我们先是编写尾插的代码。在逻辑上我们应该是先要找到链表的最后一个结点并将其中的指针修改为所插入结构体的指针这样便能通过这个指针找到新插入的指针。大致就是找尾和插入这两部分要注意的是如果链表的内容为空时就无需经过找尾这个过程直接插入便可以了。具体代码如下

//尾插的实现
void SLTPushBack(SListNode** pphead, SLTDataType x)
{
	SListNode *newnode = BuySLTNode(x);
	if (*pphead ==NULL)
	{
		*pphead= newnode;
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next=newnode;
	}

}

3.3.5单链表的头插

相比于单链表的尾插头插要相对简单一点。只需将链表的首个指针修改成所要插入的结构体的指针并将其指向原首个结点。

//头插的实现
void SLTPushFront(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySLTNode(x);    
	newnode->next = *pphead;    //新结点指向原首个结点
	*pphead = newnode;          //将新结点的指针作为链表的首指针

}

3.3.6单链表的尾删

在讲解玩单链表的结点插入之后就是结点的删除了依旧先来编写尾删的代码。下面讲讲大致的实现思路首先在进行尾删的处理时先要判断链表是否为空如果为空的话尾删就没有任何意义了。然后在链表不为空的情况下再进行尾删的处理。这一部分有几种思路无论是哪种思路共有的部分就是将最后一个结点的空间释放主要区别在于寻找这个结点的过程不同。下面只讲解其中一种思路就是找到倒数第二个结点将其指向最后一个结点的指针置空并释放其所指向的空间也就是最后一个结点的空间。

//尾删
void SLTPopBack(SListNode** pphead)
{
	assert(*pphead);
	SListNode* cur = *pphead;
	while ((cur->next)->next)    //寻找倒数第二个结点
	{
		cur = cur->next;
	}
	free(cur->next);    //释放最后一个结点的空间
	cur->next = NULL;   //指向最后一个结点的指针置空
}

3.3.7 单链表头删

单链表的尾删与其实与头插的思路类似只是将第二个结点作为第一个结点而将第一个结点的空间释放也无需尾删复杂传来的参数就能直接找到第一个结点。不过要注意的一点依旧是链表的内容是否为空。具体代码实现如下

//头插的实现
void SLTPopFront(SListNode** pphead)
{
	assert(*pphead);
	SListNode* tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
	tmp = NULL;
}

整体的代码如下

//SList.c

#include "SList.h"
void SLTPrint(SListNode* phead)
{
	SListNode *cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
SListNode* BuySLTNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));	//申请一个结构体大小的内存空间
	if (newnode == NULL)	//对返回的指针进行检查
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;	//结点信息的编写
	newnode->next = NULL;
	return newnode;
}
void SLTPushBack(SListNode** pphead, SLTDataType x)
{
	SListNode *newnode = BuySLTNode(x);
	if (*pphead ==NULL)
	{
		*pphead= newnode;
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next=newnode;
	}

}

void SLTPushFront(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;

}

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

void SLTPopFront(SListNode** pphead)
{
	assert(*pphead);
	SListNode* tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
	tmp = NULL;
}

//SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef int SLTDataType;	//存储信息为整型
typedef struct SListNode
{
	SLTDataType data;		//存储信息
	struct SListNode* next;//指向下一个结点的结构体指针
}SListNode;

void SLTPrint(SListNode* phead);
SListNode* BuySLTNode(SLTDataType x);
void SLTPushBack(SListNode** pphead, SLTDataType x);
void SLTPushFront(SListNode** pphead, SLTDataType x);
void SLTPopBack(SListNode** pphead);
void SLTPopFront(SListNode** pphead);

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

//以下均为笔者测试时所用代码
void SLTText1()
{
	SListNode *plist=NULL;
	SLTPushBack(&plist,1);
	SLTPrint(plist);
	SLTPushBack(&plist, 2);
	SLTPrint(plist);
	SLTPushBack(&plist, 3);
	SLTPrint(plist);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
}
void SLTText2()
{
	SListNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPrint(plist);
	SLTPushFront(&plist, 2);
	SLTPrint(plist);	
	SLTPushFront(&plist, 3);
	SLTPrint(plist);	
	SLTPushFront(&plist, 4);
	SLTPrint(plist);
}

void SLTText3()
{
	SListNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPrint(plist);
	SLTPushBack(&plist, 2);
	SLTPrint(plist);
	SLTPushBack(&plist, 3);
	SLTPrint(plist);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
}
void SLTText4()
{
	SListNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPrint(plist);
	SLTPushFront(&plist, 2);
	SLTPrint(plist);
	SLTPushFront(&plist, 3);
	SLTPrint(plist);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
}


int main()
{
	SLTText1();    //读者可自行选择测试的函数
	return 0;
}