链表可以说是一种最为基础的数据结构了,而单向链表更是基础中的基础。链表是由一组元素以特定的顺序组合或链接在一起的,不同元素之间在逻辑上相邻,但是在物理上并不一定相邻。在维护一组数据集合时,就可以使用链表,这一点和数组
1.链表概况
1.1 链表的概念及结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
1.2 链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构
单向或者双向
带头或者不带头
循环或者非循环
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构
- 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了
2. 单向链表的实现
单向链表结构
2.1 SList.h(头文件的汇总,函数的声明)
#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
int data;//数据
struct SListNode* next;//下一个节点的地址
}SListNode;
void SListPrint(SListNode* phead);//打印
SListNode* BuySListNode(SLTDataType x);//搞出一个新节点
void SListPushBack(SListNode** pphead, SLTDataType x);//尾插
void SListPushFront(SListNode** pphead, SLTDataType x);//头插
void SListPopBack(SListNode** pphead);//尾删
void SListPopFront(SListNode** pphead);//头删
SListNode* SListFind(SListNode* phead, SLTDataType x);//查找
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDataType x);//在pos位置之后插入
void SListErase(SListNode** pphead, SListNode* pos);//删除pos位置
void SListEraseAfter(SListNode* pos);//删除pos之后位置
void SListDestroy(SListNode** pphead);//销毁
2.2 SList.c(函数的具体实现逻辑)
2.2.1 打印链表
//打印
void SListPrint(SListNode* phead)
{
//assert(phead);//没必要断言,空链表也能打印
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//test.c
void TestSList1()
{
SListNode* slist;//结构体指针,用于存节点的地址
SListNode* n1 = (SListNode *)malloc(sizeof(SListNode));
SListNode* n2 = (SListNode*)malloc(sizeof(SListNode));
SListNode* n3 = (SListNode*)malloc(sizeof(SListNode));
n1->data = 1;
n2->data = 2;
n3->data = 3;
n1->next = n2;
n2->next = n3;
n3->next = NULL;
slist = n1;
SListPrint(slist);
}
2.2.2 搞出一个新节点(为其他函数服务)
//搞出一个新节点
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
return newnode;
}
2.2.3 链表尾插
//尾插
void SListPushBack(SListNode** pphead,SLTDataType x)//会改变实参slist,要传二级指针
{
assert(pphead);//就算链表是空,它的二级指针也不为空
SListNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//遍历找尾
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void TestSList2()
{
SListNode* slist = NULL;
for (int i = 0; i < 6; i++)
{
SListPushBack(&slist,i);
}
SListPrint(slist);
}
2.2.4 链表头插
//头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);//就算链表是空,它的二级指针也不为空
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void TestSList2()
{
SListNode* slist = NULL;
for (int i = 0; i < 6; i++)
{
SListPushFront(&slist,i);
}
SListPrint(slist);
}
2.2.5 链表尾删
方法1(用两个指针,分别找最后一个和倒数第二个):
方法2(直接找倒数第二个):
//尾删
void SListPopBack(SListNode** pphead)//如果只有一个节点但还要尾删,就会改变实参slist,建议传二级指针
{
assert(pphead);//就算链表是空,它的二级指针也不为空
//三种情况:
//1.空
//2.一个节点
//3.多个节点
if (*pphead == NULL)
{
return;
}
else if ((*pphead)->next == NULL)//优先级,记得加括号
{
free(*pphead);
*pphead = NULL;
}
//第一种写法(用两个指针,分别找最后一个和倒数第二个)
else
{
SListNode* prev = NULL;//找倒数第二个元素,用于将它指向NULL
SListNode* tail = *pphead;//找尾
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;//习惯性free掉就将其置空
prev->next = NULL;
}
//方法二(直接找倒数第二个)
//else
//{
//SListNode* tail = *pphead;//找尾
//while (tail->next->next != NULL)
//{
// tail = tail->next;
/
沃梦达教程
本文标题为:C语言数据结构超详细讲解单向链表
猜你喜欢
- C++ 数据结构超详细讲解顺序表 2023-03-25
- C语言qsort()函数的使用方法详解 2023-04-26
- 详解C语言中sizeof如何在自定义函数中正常工作 2023-04-09
- Easyx实现扫雷游戏 2023-02-06
- ubuntu下C/C++获取剩余内存 2023-09-18
- C语言详解float类型在内存中的存储方式 2023-03-27
- C语言手把手带你掌握带头双向循环链表 2023-04-03
- 我应该为我的项目使用相对包含路径,还是将包含目录放在包含路径上? 2022-10-30
- c++ const 成员函数,返回一个 const 指针.但是返回的指针是什么类型的 const? 2022-10-11
- Qt计时器使用方法详解 2023-05-30