首页 > 其他分享 >数据结构（链表）

数据结构（链表）

时间：2024-10-09 23:19:45浏览次数：9  
标签：pphead NULL STLNode SLTN pos next 链表 数据结构

我可以接受失败，但绝对不能接受未奋斗过的自己。     

链表

链表的概念

1. 链表是⼀种物理存储结构上非连续、非顺序的存储结构。

2. 链表是顺序表的一种，所以它一定在逻辑结构上是线性的。

3. 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

4. 链表实际上由一个个节点组成。

结点的概念

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

2. 链表中每个结点都是独立申请的，即需要插⼊数据时才去申请⼀块结点的空间。

3. 我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。 

4. 两个节点之间的地址不一定是连续的。 

单链表

定义单链表

typedef int LTDataType
typedef struct SListNode
{
 LTDataType data; //节点数据
 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
}SLTN;
//SListNode==Single List Node 单链表节点

创建新的节点 

SLTN* Add_STLNode(SLTDataType x)
{
	SLTN* node=(SLTN*)malloc(sizeof(SLTN));
	node->data = x;
	node->next = NULL;
	return node;
}

打印单链表

void Print_SLTNode(SLTN* phead)//不需要对原来的链表进行修改，所以只要传值。
{
    assert(phead);
	SLTN* purc = phead;
	while (purc != NULL)
	{
		printf("%d\n", purc->data);
		purc = purc->next;
	}
	printf("NULL\n");
}

尾插单链表

void Back_Push_STLNode(SLTN** pphead, SLTDataType x)//要对原来的链表进行操作，所以传地址。
{
	SLTN* newnode = Add_STLNode(x);
	SLTN* purc = *pphead;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (purc->next != NULL)
		{
			purc = purc->next;
		}
		purc->next = newnode;
	}
}

头插单链表 

void Front_Push_STLNode(SLTN** pphead, SLTDataType x)
{
	SLTN* newnode = Add_STLNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

指定插入单链表 

void Insert_STLNode(SLTN** pphead, SLTN* pos, SLTDataType x)
{
	assert(*pphead);
	assert(pos);
	SLTN* newnode=Add_STLNode(x);
	SLTN* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
}

尾删单链表 

void Back_Pop_STLNode(SLTN** pphead)
{
	assert(*pphead);
	SLTN* ptail = *pphead;
	SLTN* prev = NULL;
	if (ptail->next == NULL)
	{
		free(ptail);
		ptail = NULL;
	}
	else
	{
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}

 头删单链表

void Front_Pop_STLNode(SLTN** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTN* second = (*pphead)->next;
		free(*pphead);
		*pphead = second;
	}
}

指定删除单链表

void Delete_STLNode(SLTN** pphead, SLTN* pos)
{
	assert(*pphead);
	assert(pos);
	SLTN* prev = *pphead;
    if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
    else
    {
	    while (prev->next != pos)
	    {
		    prev = prev->next;
	    }
	    prev->next = pos->next;
	    free(pos);
	    pos = NULL;
    }
}

 销毁单链表

void Destroy_STLNode(SLTN** pphead)
{
	assert(*pphead);
	SLTN* pcur = *pphead;
	while (pcur)
	{
		if (pcur!=NULL)
		{
			SLTN* next = pcur;
			free(pcur);
			pcur = next->next;
		}
	}
	*pphead = NULL;
}

代码

<test.h>文件

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SLTNode* next;
}SLTN;
void PrintSLTNode(SLTN* phead);
void Back_Push_STLNode(SLTN** pphead, SLTDataType x);
SLTN* Add_STLNode(SLTDataType x);
void Front_Push_STLNode(SLTN** pphead, SLTDataType x);
void Back_Pop_STLNode(SLTN** pphead);
void Front_Pop_STLNode(SLTN** pphead);
SLTN* Search_STLNode(SLTN* phead, SLTDataType x);
void Insert_STLNode(SLTN** pphead, SLTN* pos, SLTDataType x);
void STLNode_Insert(SLTN** pphead, SLTN* pos, SLTDataType x);
void Delete_STLNode(SLTN** pphead, SLTN* pos);
void Destroy_STLNode(SLTN** pphead);

<test.c>文件

#include "test.h"
void Print_SLTNode(SLTN* phead)
{
	SLTN* purc = phead;
	while (purc)
	{
		printf("%d\n", purc->data);
		purc = purc->next;
	}
	printf("NULL");
}
SLTN* Add_STLNode(SLTDataType x)
{
	SLTN* node=(SLTN*)malloc(sizeof(SLTN));
	node->data = x;
	node->next = NULL;
	return node;
}
void Back_Push_STLNode(SLTN** pphead, SLTDataType x)
{
	SLTN* newnode = Add_STLNode(x);
	SLTN* purc = *pphead;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (purc->next != NULL)
		{
			purc = purc->next;
		}
		purc->next = newnode;
	}
}
void Front_Push_STLNode(SLTN** pphead, SLTDataType x)
{
	SLTN* newnode = Add_STLNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void Back_Pop_STLNode(SLTN** pphead)
{
	assert(*pphead);
	SLTN* ptail = *pphead;
	SLTN* prev = NULL;
	if (ptail->next == NULL)
	{
		free(ptail);
		ptail = NULL;
	}
	else
	{
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}
void Front_Pop_STLNode(SLTN** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTN* second = (*pphead)->next;
		free(*pphead);
		*pphead = second;
	}
}
SLTN* Search_STLNode(SLTN* phead, SLTDataType x)
{
	assert(phead);
	SLTN* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			printf("找到了。\n");
			return pcur;
		}
		else
		{
			pcur = pcur->next;
		}
	}
	printf("没找到。\n");
}
void Insert_STLNode(SLTN** pphead, SLTN* pos, SLTDataType x)
{
	assert(*pphead);
	assert(pos);
	SLTN* newnode=Add_STLNode(x);
	SLTN* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
}
void STLNode_Insert( SLTN* pos, SLTDataType x)
{
	assert(pos);
	SLTN* newnode = Add_STLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void Delete_STLNode(SLTN** pphead, SLTN* pos)
{
	assert(*pphead);
	assert(pos);
	SLTN* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}
void Destroy_STLNode(SLTN** pphead)
{
	assert(*pphead);
	SLTN* pcur = *pphead;
	while (pcur)
	{
		if (pcur!=NULL)
		{
			SLTN* next = pcur;
			free(pcur);
			pcur = next->next;
		}
	}
	*pphead = NULL;
}
int main()
{
	SLTN* plist = NULL;
	Back_Push_STLNode(&plist,2);
	Back_Push_STLNode(&plist,3);
	Back_Push_STLNode(&plist,4);
	Front_Push_STLNode(&plist, 1);
	//Back_Pop_STLNode(&plist);
	//Front_Pop_STLNode(&plist);
	SLTN* pos1=Search_STLNode(plist,3);
	Insert_STLNode(&plist, pos1, 9);
	STLNode_Insert(pos1, 8);
	Delete_STLNode(&plist, pos1);
	//Destroy_STLNode(&plist);
	Print_SLTNode(plist);
	return 0;
}

致谢

  感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！

标签：pphead,NULL,STLNode,SLTN,pos,next,链表,数据结构
From： https://blog.csdn.net/hsy1603914691/article/details/142524838

相关文章

  • c++单链表（带头结点）
    #include<iostream>usingnamespacestd;//定义typedefstruct_LinkNode{  intdata;//结点的数据域  struct_LinkNode*next;//结点的指针域}LinkNode,Linklist;//初始化boolInitList(Linklist*&L){  L=newLinkNode;  if(!L)returnfalse; ......
  • 链表Set_LinkList（建立）
    用单链保存集合元素，元素由键盘输入。输入以-1结束，将所建链表打印输出。链表结构如下图所示：提示：1.链表中数据元素为整型，typedef int ElemType;2.用结构体自定义链表结构Set_LinkList ；3.初始化链表函数init()，该函数可创建空链表L，返回L的头指针地址；4.链表插入结点函数......
  • JS刷力扣-链表【持续跟新】
    力扣的链表归类2.两数相加【链表+递归】前置知识：1.链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。2.链表的入口节点称为链表的头结点也就是head。leet......
  • 【数据结构与算法】排序算法
    3.7排序算法概述比较排序算法算法最好最坏平均空间稳定思想注意事项冒泡O(n)O(n2n^2......
  • 2024年软件设计师中级（软考中级）详细笔记【3】数据结构(下)（分值5分）
    上午题第3章数据结构下部目录前言第3章数据结构【下】(5分)3.5查找3.5.1查找的基本概念【考点】3.5.2静态查找表的查找方法3.5.3动态查找表3.5.4哈希表3.5.4.1哈希表的定义3.5.4.2哈希函数的构造方法3.5.4.3处理冲突的方法3.6排序3.6.1排序的基本概念3.6.2......
  • 23_合并K个升序链表
    23_合并K个升序链表【问题描述】给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。【算法设计思想】使用优先队列（最小堆）设计思想：初始化优先队列：创建一个最小堆（优先队列），将每个链表的第一个节点加入堆中。这里堆中存储的是节......
  • 代码随想录算法训练营第四天|24. 两两交换链表中的节点、19.删除链表的倒数第N个节点
    24.两两交换链表中的节点力扣题目链接(opensnewwindow)给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。输入：head=[1,2,3,4]输出：[2,1,4,3]示例2：输入：head=[]输出：[]示例3：输入：head=[1]......
  • 代码随想录算法训练营第三天|链表理论基础、203.移除链表元素、707.设计链表、206.反
    链表理论基础链表的类型单链表每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链表的入口节点称为链表的头结点也就是head。双链表单链表中的指针域只能指向节点的下一个节点。双链表：每一个节点有......
  • 【数据结构与算法】线性表
    文章目录一.什么是线性表？二.线性表如何存储？三.线性表的类型我们知道从应用中抽象出共性的逻辑结构和基本操作就是抽象数据类型，然后实现其存储结构和基本操作。下面我们依然按这个思路来认识线性表一.什么是线性表？定义线性表（LinearList）是由n(n>=0)个具有相同特性......
  • 7-1单链表的基本操作
    题目：7-1单链表基本操作分数20作者朱允刚单位吉林大学请编写程序实现单链表插入、删除结点等基本算法。给定一个单链表和一系列插入、删除结点的操作序列，输出实施上述操作后的链表。单链表数据域值为整数。输入格式:输入第1行为1个正整数n，表示当前单链表长度；第2行为n个......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99