数据结构——单链表1

1. 单链表

1.1 概念与结构

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

1.1.1 结点

• 与顺序表不同的是，链表里的每节都是独立申请下来的空间，我们称之为“节点/结点”
• 节点的组成部分主要有两个部分组成：当前节点要保存的数据（数据域）和保存下一个节点的地址（指针域）
• 链表中每个节点都是独立申请的，（需要插入数据时才去申请一块节点的空间），需要指针变量来保存下一个节点的位置才可以从当前的节点找到下一个节点。

1.1.2 链表的性质

• 链表结构在逻辑上时连续的，在物理结构上不一定是连续的
• 节点一般是从堆上申请的
• 从堆上申请来的空间，是按照一定的策略来分配的，每次申请的空间可能是连续的，也可能是不连续的

每个节点对应的结构体代码：

typedef int SLTDataType;
//定义链表节点的结构
typedef struct SListNode
{
	SLTDataType  data;       //节点数据
	struct SListNode* next;  //下一个节点的地址
}SLTNode;

1.1.3 链表的打印

//单链表的打印
void SLTPrint(SLTNode* phead) {
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d -> ",pcur->data);
		pcur = pcur->next;

	}
	printf("NULL\n");
}

1.2 实现单链表

SList.h

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

//定义单链表就是定义节点，因为单链表是由节点组成的，所以定义单链表就是定义节点
typedef int SLTDataType;
//定义链表节点的结构
typedef struct SListNode
{
	SLTDataType  data;
	struct SListNode* next;
}SLTNode;

//单链表的打印
void SLTPrint(SLTNode* phead);

//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//单链表的尾删
void SLTPopBack(SLTNode** pphead);

SList.c

#include"SList.h"

//单链表的打印
void SLTPrint(SLTNode* phead) {
	SLTNode* pcur = phead;
	while (pcur != NULL)
	{
		printf("%d -> ",pcur->data);
		pcur = pcur->next;

	}
	printf("NULL\n");
}


//新节点的申请
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//申请新节点这里传的应该是节点类型而不是数据类型
	//单链表：每次插入一个节点时，需要分配一个节点（结构体）的内存，因此使用 `sizeof(节点类型)`。
	//顺序表：在扩容时，需要为多个数据元素分配一块连续的内存（即数组），因此使用 `元素个数 * sizeof(数据类型)`。
	if (node == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	node->data= x;
	node->next = NULL;
	return node;
}

//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	//单链表为空
	assert(pphead);
	//SLTNode* Tail = *pphead; 不能在这里定义Tail 因为这里的Tail为空，后面循环中的Tail->next 就会报错，不会进入循环当中
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else {
		//单链表不为空，找尾节点，插入新节点
		SLTNode* Tail = *pphead;
		while (Tail->next != NULL)
		{
			Tail = Tail->next;
		}
		//跳出循环，插入新节点
		Tail->next = newnode;
		//newnode->next = NULL; 不需要写是因为，newnode在初始化的时候就已经置为NULL了
	}
}

//单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) 
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//单链表尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//只有一个节点的情况
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	SLTNode* Tail = *pphead;
	SLTNode* prev = NULL;
	while (Tail->next)
	{
		prev = Tail;
		Tail = Tail->next;
	}
	//跳出循环
	prev->next = NULL;
	free(Tail);
	Tail = NULL;
}

后续还有其它的单链表的实现哦~~~