首页 > 其他分享 >单链表

单链表

时间：2024-08-31 11:52:59浏览次数：15  
标签：pphead ps 单链 SLTNode cur void next

目录

1. 链表的概念及结构

2. 单链表的实现

3. 链表的分类                                              

1. 链表的概念及结构

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

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在，并且车厢是独立存在的，且每节车厢都有车门，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下通过每节车厢里都放一把下一节车厢的钥匙，从而实现从车头走到车尾

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”

节点的组成主要有两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）

图中指针变量 plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希
望plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFA0

结合前面学到的结构体知识，我们可以给出每个节点对应的结构体代码：
假设当前保存的节点为整型：
 

struct SListNode
{
    int data; //节点数据
    struct SListNode* next; //指针变量用保存下一个节点的地址
};

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数
据，也需要保存下一个节点的地址（当下一个节点为空时保存的地址为空）
当我们想要从第一个节点走到最后一个节点时，只需要在前一个节点拿上下一个节点的地址（下一个节点的钥匙）就可以

实现节点从头到尾的打印：

注意：

  1. 链式机构在逻辑上是连续的，在物理结构上不一定连续
  2. 节点一般是从堆上申请的
  3. 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

2. 单链表的实现
//list.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType val;
	struct SListNode* next;
}SLTNode;


void SLTPrint(SLTNode* phead);
SLTNode* buyNode(SLTDataType x);
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);
//list.c
#include"list.h"
#include<stdlib.h>
void SLTPrint(SLTNode* phead)
{
	while (phead)
	{
		printf("%d->", phead->val);
		phead = phead->next;
	}
	printf("NULL\n");
}
SLTNode* buyNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	node->next = NULL;
	node->val = x;
	return node;
}
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* node = buyNode(x);
	if (*pphead == NULL)
	{
		*pphead = node;
		return;
	}
	SLTNode* cur = (*pphead);
	while (cur->next)
	{
		cur = cur->next;
	}
	cur->next = node;
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* node = buyNode(x);
	if (pphead == NULL)
	{
		*pphead = node;
		return;
	}
	node->next = (*pphead);
	(*pphead) = node;
}
void SLTPopBack(SLTNode** pphead)
{
	SLTNode* cur = (*pphead);
	if (cur->next == NULL)
	{
		free(cur);
		cur = NULL;
		return;
	}
	SLTNode* prev = NULL;
	while (cur->next)
	{
		prev = cur;
		cur = cur->next;
	}
	free(cur);
	prev->next = NULL;
}
void SLTPopFront(SLTNode** pphead)
{
	SLTNode* cur = (*pphead);
	if (cur->next == NULL)
	{
		free(cur);
		cur = NULL;
	}
	SLTNode* prev = cur;
	cur = cur->next;
	free(prev);
	prev = NULL;
}

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	while (phead)
	{
		if (phead->val == x)
		{
			return phead;
		}
		phead = phead->next;
	}
	return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	SLTNode* cur = (*pphead);
	SLTNode* node = buyNode(x);
	if (cur == pos)
	{
		SLTPushFront(pphead, x);
		return;
	}
	while (cur->next == pos)
	{
		cur = cur->next;
	}
	node->next = cur->next;
	cur->next = node;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	SLTNode* cur = (*pphead);
	if (cur == pos)
	{
		SLTPopFront(pphead);
		return;
	}
	while (cur->next == pos)
	{
		cur = cur->next;
	}
	SLTNode* next = cur->next;
	cur->next = next->next;
	free(next);
	next = NULL;
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	SLTNode* node = buyNode(x);
	SLTNode* next = pos->next;
	pos->next = node;
	node->next = next;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	SLTNode* next = pos->next;
	while (next)
	{
		SLTNode* nnext = next->next;
		free(next);
		next = nnext;
	}
	pos->next = NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
	SLTNode* cur = (*pphead);
	while (cur)
	{
		SLTNode* next = cur;
		free(cur);
		cur = next;
	}
	pphead = NULL;
}
//test.c
#include"list.h"

int main()
{
	//SLTNode s;
	SLTNode* ps =0;

	SLTPushBack(&ps, 1);
	SLTPushBack(&ps, 2);
	SLTPushBack(&ps, 3);

	//SLTPrint(ps);
	//printf("-----------------\n");
	//SLTPushFront(& ps, 4);
	//SLTPrint(ps);
	//printf("-----------------\n");

	//SLTPopBack(&ps);
	//SLTPrint(ps);
	//printf("-----------------\n");

	//SLTPopFront(&ps);
	//SLTPrint(ps);
	//printf("-----------------\n");

	SLTNode* find =  SLTFind(ps, 1);
	SLTInsert(&ps, find,6);
	SLTPrint(ps);
	printf("-----------------\n");
	
	find = SLTFind(ps, 1);
	SLTErase(&ps, find);
	SLTPrint(ps);
	printf("-----------------\n");

	find = SLTFind(ps, 1);
	SLTInsertAfter(find, 7);
	SLTPrint(ps);
	printf("-----------------\n");

	find = SLTFind(ps, 1);
	SLTEraseAfter(find);
	SLTPrint(ps);
	printf("-----------------\n");

	SListDesTroy(&ps);
	return 0;
}

测试结果： 

3. 链表的分类                                              

8种（2 x 2 x 2）链表结构

最常用还是两种结构：单链表和双向带头循环链表

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表

谢谢观看

标签：pphead,ps,单链,SLTNode,cur,void,next
From： https://blog.csdn.net/Limerence_Aries/article/details/141750325

相关文章

  • 数据结构-单链表-详解-1
    数据结构-单链表-详解-11.前言2.结点3.打印3.1关于断言3.2下一结点的找法物理结构逻辑结构1.前言在数据结构-顺序表-详解中，我详细介绍了顺序表的实现，而顺序表也有一些缺点：中间，头部插入时，需整体挪动数据，效率低下。空间不够时扩容，有一定的消耗，也可能有一定空间浪费......
  • 链表-单链表的基本操作及C语言代码实现
    1.遍历单链表（打印，修改）便利的概念想必大家都不会陌生，即就是从链表的头开始，逐步向后进行每一个元素的访问，这就是遍历，对于遍历操作，我们可以衍生出很多常用的数据操作，比如说查询元素，修改元素，获取元素个数，打印整个链表数据等等。进行遍历的思路极其简单，只需要建立一个指向链表L的......
  • 【链栈的实现】--------本质为不带头结点的 头插法建立起来的单链表
    1.链栈的基本属性与特征：链栈是运算受限的单链表，只能在链表头部进行操作2.链栈的相关基础操作汇总初始化操作：操作结果:构造一个空栈S。InitStack(LinkStack*s)判定S是否为空栈：初始条件:栈S已存在操作结果:若栈S为空栈，则返回TRUE，否则FALSE.StackEmpty(LinkStack......
  • 【408DS算法题】022基础-递增输出单链表中的结点值
    Index题目分析实现总结以上内容稍后补全，以下内容来自https://blog.csdn.net/weixin_60702024/article/details/141336041题目分析实现总结分析题目给定单链表的头结点，按照递增的顺序，输出单链表结点的值。分析实现具体实现如下：总结注意delete执行后，只会将......
  • 单链表入门
    1.概念与结构概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。2.结点与顺序表不同的是，链表⾥的每一个都是独⽴申请下来的空间，我们称之为“结点/结点”结点的组成主要有两个部分：当前结点要保存的数据......
  • 单链表C语言版
        一、单链表的定义单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。 程序如下：#include<stdio.h>#include<stdlib.h>//定义链表节点结构体typedefstructNode{intdata;//数据域structNode*nex......
  • 单链表
    //单链表#include<iostream>usingnamespacestd;constintN=1010;inthead,e[N],ne[N],idx;//初始化voidinit(){ head=-1; idx=0;}//插入voidadd_to_head(intx){ e[idx]=x; ne[idx]=head; head=idx; idx++;}//将x插到下标为k的点的后面voidadd(......
  • 【数据结构】详细剖析链表，带你实现单链表，双向链表，附链表编程练习题
    目录一.链表1.链表的概念及结构2.单链表的实现2.1单链表节点结构2.2动态申请一个节点2.3单链表打印2.4单链表尾插2.5单链表头插2.6单链表尾删2.7单链表头删2.8单链表查找 2.9单链表在pos后一位插入x2.10单链表删除pos后一位的值2.11单链表销毁 ......
  • 【408DS算法题】016基础-倒序输出单链表的结点值
    Index题目分析实现总结题目给定单链表的头结点，倒序输出单链表的结点值。分析实现要倒序输出链表结点值，首先可以想到的是先将链表的结点值存储到数组中，然后利用数组随机访问的特性进行倒序输出。如果考虑其它思路的话，还可以使用栈来代替数组——将链表元素依次......
  • 数据结构+单链表应用
    一、问题描述编写程序实现两个有序表的交和差，令L1=(x1,x2,x3,...,xn)，L2=(y1,y2,y3,...,yn)，它们是两个线性表，采用带头结点的单链表存储，请先实现单链表存储两个链表，再完成如下功能：（1）sort：将单链表的所有结点按照数据域进行递增排序，构造成有序单链表；（2）interSect：求两个......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99