首页 > 其他分享 >数据结构——单链表

数据结构——单链表

时间：2024-07-04 12:27:32浏览次数：17  
标签：Node 单链 return int next 数据结构 NULL plist

1、结构体

typedef struct Node
{
	int data;//数据域
	struct Node* next;//后继指针
}Node,*List;

 注意：单链表最后一个节点的next域未NULL

2、头插（重点）

//头插,考试重点
bool  Insert_head(List  plist, int val)
{

	assert(plist != NULL);
	if (plist == NULL)
		return false;
	//动态申请节点
	Node* p = (Node*)malloc(sizeof(Node));
	assert(plist != NULL);
	//将数据放入新节点
	p->data = val;
	//插入新节点
	p->next = plist->next;//先连接后面的节点
	plist->next = p;
}

3、尾插

//尾插
bool  Insert_tail(List plist, int val)//时间复杂度：O(n)
{
	assert(plist != NULL);
	if (plist == NULL)
		return false;
	//动态申请节点
	Node* p = (Node*)malloc(sizeof(Node));
	assert(plist != NULL);
	//将数据放入新节点
	p->data = val;
	//找尾巴
	Node* q;
	for (q = plist; q->next != NULL; q = q->next)
	{
		;
	}
	//插入新节点
	p->next = q->next;
	q->next = p;
}

 4、在指定位置插入数据

//插入数据,在plist链表的pos位置插入val;
bool   Insert(List plist, int pos, int val)
{
	if (pos < 1 || pos >= Getlength(plist))
	{
		return false;
	}
	Node* p = plist;
	int j = 0;
	//获得前结点
	while (p != NULL && j < pos - 1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)
	{
		return false;
	}
	//插入新结点
	Node* q = (Node*)malloc(sizeof(Node));
	q->data = val;
	q->next = p->next;
	p->next = q;
	return true;
}

5、删除指定位置的数据

//删除pos位置的值
bool   DelPos(List plist, int pos)
{
	assert(plist != NULL);
	if (plist == NULL)
		return NULL;
	if (pos < 1 || pos >= Getlength(plist))
	{
		return false;
	}
	Node* p = plist;
	int j = 0;
	//获得前结点
	while (p != NULL && j < pos - 1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)
	{
		return false;
	}
	Node* q = p->next;
	p->next = p->next->next;
	free(q);
	return true;
}

6、删除指定数据（重点）

//删除第一个val的值,考试重点
bool  DelVal(List plist, int val)
{
	//获得前驱
	Node* p = plist;
	Node* q = NULL;
	while (p->next != NULL)
	{
		if (p->next->data == val)
		{
			q = p->next;//保存被删结点的地址
			p->next = p->next->next;
			break;
		}
		p = p->next;
	}
	//释放
	if (q != NULL)
		free(q);
	return 0;
}

完成代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include <string.h>
#include<ctype.h>
#include<assert.h>
#include<stdlib.h>
typedef struct Node
{
	int data;//数据域
	struct Node* next;//后继指针
}Node,*List;

//初始化
void   InitList(List  plist)
{
	//头结点的数据域不使用
	assert(plist != 0);//参数判断
	if (plist == NULL)
		return;
	plist->next = NULL;
}

//头插,考试重点
bool  Insert_head(List  plist, int val)
{

	assert(plist != NULL);
	if (plist == NULL)
		return false;
	//动态申请节点
	Node* p = (Node*)malloc(sizeof(Node));
	assert(plist != NULL);
	//将数据放入新节点
	p->data = val;
	//插入新节点
	p->next = plist->next;//先连接后面的节点
	plist->next = p;
}

//尾插
bool  Insert_tail(List plist, int val)//O(n)
{
	assert(plist != NULL);
	if (plist == NULL)
		return false;
	//动态申请节点
	Node* p = (Node*)malloc(sizeof(Node));
	assert(plist != NULL);
	//将数据放入新节点
	p->data = val;
	//找尾巴
	Node* q;
	for (q = plist; q->next != NULL; q = q->next)
	{
		;
	}
	//插入新节点
	p->next = q->next;
	q->next = p;
}

//获取数据节点的个数
int  Getlength(List plist)
{
	int count = 0;
	assert(plist != NULL);
	if (plist == NULL)
		return -1;
	for (Node* p = plist->next; p != NULL; p = p->next)
		count++;
	return count;
}

//插入数据,在plist链表的pos位置插入val;
bool   Insert(List plist, int pos, int val)
{
	if (pos < 1 || pos >= Getlength(plist))
	{
		return false;
	}
	Node* p = plist;
	int j = 0;
	//获得前结点
	while (p != NULL && j < pos - 1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)
	{
		return false;
	}
	//插入新结点
	Node* q = (Node*)malloc(sizeof(Node));
	q->data = val;
	q->next = p->next;
	p->next = q;
	return val;
}

//判空
bool   IsEmpyt(List plist)
{
	assert(plist != NULL);
	if (plist == NULL)
		return false;
	return plist->next == NULL;
}


//在plist中查找第一个key值,找到返回节点地址,没有找到返回NULL
Node* Search(List   plist, int key)
{
	assert(plist != NULL);
	if (plist == NULL)
		return NULL;
	for (Node* p = plist->next; p->next != NULL; p = p->next)
	{
		if (p->data == key)
			return p;
	}
	return NULL;
}


//删除pos位置的值
bool   DelPos(List plist, int pos)
{
	assert(plist != NULL);
	if (plist == NULL)
		return NULL;
	if (pos < 1 || pos >= Getlength(plist))
	{
		return false;
	}
	Node* p = plist;
	int j = 0;
	//获得前结点
	while (p != NULL && j < pos - 1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)
	{
		return false;
	}
	Node* q = p->next;
	p->next = p->next->next;
	free(q);
	return true;
}

//删除第一个val的值,考试重点
bool  DelVal(List plist, int val)
{
	//获得前驱
	Node* p = plist;
	Node* q = NULL;
	while (p->next != NULL)
	{
		if (p->next->data == val)
		{
			q = p->next;//保存被删结点的地址
			p->next = p->next->next;
			break;
		}
		p = p->next;
	}
	//释放
	if (q != NULL)
		free(q);
	return 0;
}

//返回key的前驱地址,如果不存在返回NULL
Node* GetPrio(List  plist, int key)
{
	assert(plist != NULL);
	if (plist == NULL)
		return NULL;
	for (Node* p = plist->next; p->next != NULL; p = p->next)
	{
		if (p->next->data == key)
			return p;
	}
	return NULL;
}


//返回key的后继地址,如果不存在返回NULL
Node* GetNext(List  plist, int key)
{
	Node* p = Search(plist, key);
	return p->next;
}

//输出
void  Show(List  plist)
{
	assert(plist != NULL);
	if (plist == NULL)
		return;
	for (Node* p = plist->next; p != NULL; p = p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");
}

//销毁整个内存
void   Destroy(List  plist)
{
	Node* p;
	while (plist->next != NULL)
	{
		p = plist->next;
		plist->next = plist->next->next;
		free(p);
	}
}

//清空数据
void  Clear(List plist)
{
	Destroy(plist);
}

int main()
{
	Node head;
	InitList(&head);
	for (int i = 0; i < 20; i++)
	{
		//Insert_head(&head, i);
		Insert_tail(&head, i);
	}
	int len = Getlength(&head);
	printf("len=%d\n", len);
	Show(&head);
	Node* p = Search(&head, 10);
	if (p != NULL)
		printf("%d\n", p->data);
	else
		printf("没有找到\n");
	DelVal(&head, 12);
	Show(&head);
	Insert(&head, 2, 100);
	Show(&head);
	DelPos(&head, 6);
	Show(&head);
	Node* s = GetNext(&head, 16);
	if (s != NULL)
		printf("%d\n", s->data);
	else
		printf("没有找到\n");
	Node* w = GetPrio(&head, 100);
	if (w != NULL)
		printf("%d\n", w->data);
	else
		printf("没有找到\n");
	Destroy(&head);
	Show(&head);
	return 0;
}

总结

头插，头删 时间复杂度是O(1)

尾插，尾删 时间复杂度是O(n)

P初始化成什么?
如果我们要修改表的结构(或者说依赖于前驱,比如插入,删除):遍历:
for(Node *p=plist;p->next!=NULL;p=p->next)

如果我们不修改表的结构(或者说不依赖于前驱,比如求长度,打印,查找) :遍历:
for(Node*p=plist->next;p!= NULL;p=p->next) 

标签：Node,单链,return,int,next,数据结构,NULL,plist
From： https://blog.csdn.net/quite123_/article/details/140175784

相关文章

  • [JLU] 数据结构与算法上机题解思路分享-
    前言首先，请务必自己尽全力尝试实现题目，直接看成品代码，思维就被拘束了，也很容易被查重。这里只是思路解析的博客，代码仓库在JLU_Data_Structures_Record希望你能在这里找到你想要的:)第三次上机A手撕BST分数50作者朱允刚单位吉林大学对一棵初始为空的二叉查找树（Binary......
  • [JLU] 数据结构与算法上机题解思路分享-课程设计第一次与第二次上机
    前言首先，请务必自己尽全力尝试实现题目，直接看成品代码，思维就被拘束了，也很容易被查重。这里只是思路解析的博客，代码仓库在JLU_Data_Structures_Record希望你能在这里找到你想要的:)第一次上机A网络布线分数50作者朱允刚单位吉林大学2024年亚洲杯足球赛刚刚落下帷幕，......
  • [学习笔记] 动态开点权值线段树合并 - 数据结构
    权值线段树例题【模板】普通平衡树#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+1;intn,val[N],opt[N],num[N],cnt,len,san[N],m[N],rnk[N];unordered_map<int,int>dfn;structWeightedSegmentTree{ #definels(id<<1) #define......
  • 高效存储的秘诀：bitmap 数据结构在标签中的应用
    在当今大数据和信息爆炸的时代，如何有效地管理和查询海量的数据成为了企业和开发者面临的重大挑战。其中，标签系统作为数据管理中的一种重要手段，被广泛应用于用户画像、商品分类、内容推荐等多个场景。然而，随着标签数量的急剧增加，传统的数据存储和查询方式已难以满足高效率、低延迟......
  • 数据结构小学期第三天
    今天试着完成第二阶段的目标，实现九宫格拼图游戏，但是看着教程只有4*4的我也只能先按照这个做了APP.class1importcom.itheima.ui.GameJFrame;2importcom.itheima.ui.LoginJFrame;3importcom.itheima.ui.RegisterJFrame;45publicclassApp{6publicstat......
  • 【数据结构】堆栈
    目录一、堆栈的基本概念1.1堆栈定义1.2堆栈操作1.3堆栈应用二、顺序栈2.1定义2.2操作2.3C语言实现三、共享栈3.1定义3.2操作3.3C语言实现四、链式栈4.1定义4.2操作4.3C语言实现五、总结        堆栈（Stack）重要的数据结构，它们在计算机科......
  • 数据结构第3节： 抽象数据类型
    第3节：基础概念-抽象数据类型（ADT）抽象数据类型（ADT）是一种逻辑上的数学模型，以及定义在此数学模型上的一组操作。ADT通常隐藏了底层实现的细节，只暴露出一个可以被外界访问和操作的接口。在Java中，ADT可以通过接口（interface）来定义，并通过类（class）来实现。2.3.1抽象数据类型的定......
  • 【408考点之数据结构】B树和B+树
    B树和B+树在大规模数据存储和检索中，B树和B+树是两种广泛使用的数据结构。它们被设计用来高效地管理数据，使得插入、删除和查找操作都能在对数时间内完成。以下是对这两种数据结构的详细介绍。1.B树（B-Tree）定义：B树是一种自平衡的多路查找树，通常用于数据库和文件系统中。B树......
  • [JLU] 数据结构与算法上机题解思路分享-第三次上机
    前言首先，请务必自己尽全力尝试实现题目，直接看成品代码，思维就被拘束了，也很容易被查重。这里只是思路解析的博客，代码仓库在JLU_Data_Structures_Record希望你能在这里找到你想要的:)正文A图的创建分数10作者朱允刚单位吉林大学请编写程序创建一个有向图。有向图中包含......
  • C语言编程-基于单链表实现贪吃蛇游戏
    基于单链表实现贪吃蛇游戏1.定义结构体参数蛇行走的方向蛇行走的状态蛇身节点类维护蛇的结构体型2.游戏运行前预备工作定位光标位置游戏欢迎界面绘制游戏地图（边界）初始化游戏中的蛇身创建食物3.游戏运行下一个位置是食物，就吃掉食物，释放该节点下一个位置不是......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99