首页 > 其他分享 >单链表定义和操作

单链表定义和操作

时间：2024-09-19 20:01:45浏览次数：8  
标签：单链 return 定义 int next 操作 NULL data LNode

首先是单链表的定义，使用结构体定义两个部分，分别是数据域和指针域。

点击查看代码 
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;

这里可以使用typedef关键字将后续的定义简化。
具体例子如下：

  • 如果这样定义struct LNode{}的话。在定义LNode类型变量的时候我们需要这样写，struct LNode L;
  • 如果是使用typedef可以将struct省略掉。直接这样写：LNode L;

对链表的初始化(带头节点、不带头节点)

点击查看代码 
// 无头节点初始化链表 
bool InitListNoHead(LinkList &L){ 
	return (L == NULL);
}

// 有头节点的初始化链表 
bool InitListWithHead(LinkList &L){
	L = (LNode *) malloc(sizeof(LNode));
	if(L == NULL) return 0;
	L->next = NULL;
	return 1;
}

单链表的插入（指定位置插入、节点前后插入）

点击查看代码 
// 在链表中指定位置插入值 
bool InsertElemPos(LinkList &L, int pos, int e){
	if(pos < 1) return 0;
	LNode *p = L;
	int j = 0;
	while(p != NULL && j < pos - 1){
		p = p->next;
		j ++;
	}
	if(p == NULL) return 0;
	LNode *t = (LNode*)malloc(sizeof(LNode));
	t->data = e;
	t->next = p->next;
	p->next = t;
	return 1;
}

// 链表中指定节点后面插入（后插） 
bool InsertNextNode(LNode *p, ElemType e){
	if(p == NULL) return 0;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL) return 0;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return 1;
}

// 链表中指定节点前面插入（前插）
// 注意前插操作要确定是不是第一个节点，是的话要特殊处理
bool InsertPriorNode(LNode *p, ElemType e){
//	cout << (p->data) << endl;
//	p = p->next;
	if(p == NULL) return 0;
	LNode *s = (LNode*)malloc(sizeof(LNode));
	if(s == NULL) return 0;
	s->next = p->next;
	s->data = p->data;
	p->data = e;
	p->next = s;
	return 1;
}

链表的删除操作

点击查看代码 
// 删除第pos个节点并传回 
bool DeleteNodePos(LinkList L, int pos, ElemType &e){
	if(pos < 1) return 0;
	LNode *p = L;
	int j = 0;
	while(p != NULL && j < pos - 1){
		p = p->next;
		j ++;
	}
	if(p == NULL || p->next == NULL) return 0;
	e = p->next->data;
	p->next = p->next->next;
	return 1;
}

// 删除指定节点 
// 如果要删除的是最后一个会出现无值可删的bug
bool DeleteNodeVal(LNode *p){
	if(p == NULL) return 0;
	p->data = p->next->data;
	p->next = p->next->next;
	return 1; 
}

获取链表元素以及获取长度

点击查看代码 
// 链表中获取第i个节点 
LNode *GetElem(LinkList L, int i){
	if(i < 0) return NULL;
	LNode *p;
	int j = 0;
	p = L;
	while(p != NULL && j < i){
		p = p->next;
		j ++;
	}
	return p;
}

// 链表中获取值为e的节点 
LNode *LocateElem(LinkList L, ElemType e){
	LNode *p = L;
	while(p != NULL && p->data != e){
		p = p->next;
	}
	return p;
}

// 获取链表长度 
int GetLength(LinkList L){
	LNode *p = L;
	int len = 0;
	while(p->next != NULL){
		p = p->next;
		len ++;
	}
	return len;
}

链表头插、尾插实现初始化

点击查看代码 
// 尾插节点 
LinkList List_TailInsert(LinkList &L, int n){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s, *p = L;
	for(int i = 1;i <= n;i ++){
		cin >> x;
		s = (LNode *)malloc(sizeof(LNode)); 
		s->data = x;
		p->next = s;
		p = s;
	}
	p->next = NULL;
	return L;
}

// 头插节点 (逆置链表操作)
LinkList List_HeadInsert(LinkList &L, int n){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL; // 没这句话就是无头节点的链表 
	LNode *s, *p = L;
	for(int i = 1;i <= n;i ++){
		cin >> x;
		s = (LNode *)malloc(sizeof(LNode)); 
		s->data = x;
		s->next = p->next;
		p->next = s; 
	}
	return L;
}

output链表
void ListPrint(LNode *L){
 LNode *p = L;
 p = p->next;
 while(p != NULL){
  cout << p->data << ' ';
  p = p->next;
 cout << endl;
}

完整代码：

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef int ElemType;
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;

// 无头节点初始化链表 
bool InitListNoHead(LinkList &L){ 
	return (L == NULL);
}

// 有头节点的初始化链表 
bool InitListWithHead(LinkList &L){
	L = (LNode *) malloc(sizeof(LNode));
	if(L == NULL) return 0;
	L->next = NULL;
	return 1;
}

// 在链表中指定位置插入值 
bool InsertElemPos(LinkList &L, int pos, int e){
	if(pos < 1) return 0;
	LNode *p = L;
	int j = 0;
	while(p != NULL && j < pos - 1){
		p = p->next;
		j ++;
	}
	if(p == NULL) return 0;
	LNode *t = (LNode*)malloc(sizeof(LNode));
	t->data = e;
	t->next = p->next;
	p->next = t;
	return 1;
}

// 链表中指定节点后面插入（后插） 
bool InsertNextNode(LNode *p, ElemType e){
	if(p == NULL) return 0;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL) return 0;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return 1;
}

// 链表中指定节点前面插入（前插） 
bool InsertPriorNode(LNode *p, ElemType e){
//	cout << (p->data) << endl;
	p = p->next;
	if(p == NULL) return 0;
	LNode *s = (LNode*)malloc(sizeof(LNode));
	if(s == NULL) return 0;
	s->next = p->next;
	s->data = p->data;
	p->data = e;
	p->next = s;
	return 1;
}

// 删除第pos个节点并传回 
bool DeleteNodePos(LinkList L, int pos, ElemType &e){
	if(pos < 1) return 0;
	LNode *p = L;
	int j = 0;
	while(p != NULL && j < pos - 1){
		p = p->next;
		j ++;
	}
	if(p == NULL || p->next == NULL) return 0;
	e = p->next->data;
	p->next = p->next->next;
	return 1;
}

// 删除指定节点 
bool DeleteNodeVal(LNode *p){
	if(p == NULL) return 0;
	p->data = p->next->data;
	p->next = p->next->next;
	return 1; 
}

// 链表中获取第i个节点 
LNode *GetElem(LinkList L, int i){
	if(i < 0) return NULL;
	LNode *p;
	int j = 0;
	p = L;
	while(p != NULL && j < i){
		p = p->next;
		j ++;
	}
	return p;
}

// 链表中获取值为e的节点 
LNode *LocateElem(LinkList L, ElemType e){
	LNode *p = L;
	while(p != NULL && p->data != e){
		p = p->next;
	}
	return p;
}

// 获取链表长度 
int GetLength(LinkList L){
	LNode *p = L;
	int len = 0;
	while(p->next != NULL){
		p = p->next;
		len ++;
	}
	return len;
}

// 尾插节点 
LinkList List_TailInsert(LinkList &L, int n){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s, *p = L;
	for(int i = 1;i <= n;i ++){
		cin >> x;
		s = (LNode *)malloc(sizeof(LNode)); 
		s->data = x;
		p->next = s;
		p = s;
	}
	p->next = NULL;
	return L;
}

// 头插节点 (逆置链表操作)
LinkList List_HeadInsert(LinkList &L, int n){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL; // 没这句话就是无头节点的链表 
	LNode *s, *p = L;
	for(int i = 1;i <= n;i ++){
		cin >> x;
		s = (LNode *)malloc(sizeof(LNode)); 
		s->data = x;
		s->next = p->next;
		p->next = s; 
	}
	return L;
}

// 打印链表 
void ListPrint(LNode *L){
	LNode *p = L;
	p = p->next;
	while(p != NULL){
		cout << p->data << ' ';
		p = p->next;
	}
	cout << endl;
}
int main(){
	LinkList L;
	ElemType val;
	int n; cin >> n;
	List_HeadInsert(L, n);
	ListPrint(L);
	cout << "获取链表长度：\n"; 
	int len = GetLength(L);
	cout << "len:" << len << endl;
	cout << "插入指定位置：\n"; 
	InsertElemPos(L, 3, 3);
	ListPrint(L);
	cout << "插入指定节点的后面：\n"; 
	InsertNextNode(L, 3); 
	ListPrint(L);
	cout << "插入指定节点的前面：\n"; 
	InsertPriorNode(L, 100); 
	ListPrint(L);
	cout << "获取第i个节点：\n"; 
	LNode *T = GetElem(L, 2);
	cout << (T->data) << endl;
	cout << "获取值为e的节点：\n"; 
	T = LocateElem(L, 2);
	cout << (T->data) << endl;	
	cout << "删除第3个节点：\n"; 
	DeleteNodePos(L, 3, val);
	cout << val << endl;
	ListPrint(L);
		
	return 0;
}

标签：单链,return,定义,int,next,操作,NULL,data,LNode
From： https://www.cnblogs.com/asherof/p/18421243

相关文章

  • Oracle 中，根据状态字段进行自定义排序例（待验证、待维修、重新维修）
    按照指定的顺序（待验证、待维修、重新维修、待派单、待接单、驳回、已完成）进行排序，可以修改ORDERBY子句中的CASE语句。以下是修改后的查询：SELECT a.nid,  CASEa.REPAIR_PROGRESS    WHEN1THEN'待验证'    WHEN2THEN'待维修'    WHEN3TH......
  • flowable 流程动态设置监听器（非xml中定义）及发起时从驳回节点开始审批实现
    一、flowable使用代码动态修改监听器1、配置类@ConfigurationpublicclassFlowableGlobListenerConfig{@Lazy@AutowiredprivateTaskStartListenertaskStartListener;@Lazy@AutowiredprivateTaskCompleteListenertaskCompletedListener;......
  • 2024Mysql And Redis基础与进阶操作系列（6）作者——LJS[含MySQL 多表之一对一/多；多对多；
    MySQL多表操作1多表关系简介1.1一对一关系比如1.2一对多/多对一关系比如：实现规则：1.3多对多关系举例：规则：2.多表联合查询简介多表查询有以下分类知识补充——笛卡尔积（了解即可）交叉连接查询[产生笛卡尔积]内连接查询(使用的关键字innerjoin--inner可以省......
  • 《现代操作系统》第10章——实例研究1：UNIX、Linux和Android
    《现代操作系统》第10章——实例研究1：UNIX、Linux和Android10.1UNIX与Linux的历史第一次使UNIX的两种流派一致的严肃尝试来源于IEEE（它是一个得到高度尊重的中立组织）标准委员会的赞助。有上百名来自业界、学界以及政府的人员参加了此项工作。他们共同决定将这个项目......
  • GBase 8s 自定义split_part函数
    gbase数据该函数的功能：以第二个参数separator_in分隔第一个参数str_in，返回第三个参数field_in指定字段。dropfunctionifexistssplit_part2;createfunctionsplit_part2(str_inlvarchar(2048),separator_inchar(1),field_inint)returningvarchar(255);def......
  • 2024Mysql And Redis基础与进阶操作系列（5）作者——LJS[含MySQL DQL基本查询:select；简单
    目录1MySQL数据库基本操作-DQL-基本查询1.2SQL概述1.3SQL类2.SQL语言的规则与规范2.1基本规则2.2SQL大小写规范推荐采用统一的书写规范：2.3注释2.4命名规则(了解即可)举例：两句是一样的，不区分大小写创建表格order使用``飘号，因为order和系统关键字或系统函数名......
  • DAY9：条件，逻辑操作符
    *条件操作符形式：exp1?exp2:exp3如果exp1为真，计算exp2，如果为假，计算exp3这种操作符在一定情况下可以简化代码，节省时间，如当我们进行两数之间的比较时： *逻辑操作符 &&，意为并且，&&左右两边都为真则为真，有一个为假，也为假！，意为取反，真的变为假，假的变为真当输入3和4时，3>4为......
  • 从方法、操作流程等方面对Windows和Linux的命令进行对比
    Windows和Linux是两个常见的操作系统，它们都有自己的命令行接口。尽管两者的目的都是相同的——执行特定的任务，但它们的命令之间存在一些差异。下面将从方法、操作流程等方面对Windows和Linux的命令进行对比。一、文件和目录操作：列出目录中的文件：–Windows命令：dir–Linux命......
  • 2024Mysql And Redis基础与进阶操作系列（4）作者——LJS[含MySQL FOREIGN KEY、CHECK 、D
    接上集1.FOREIGNKEY约束1.1作用限定某个表的某个字段的引用完整性。例如：员工表的员工所在部门的选择，必须在部门表能找到对应的部分。1.2关键字FOREIGNKEY1.3主表和从表/父表和子表主表（父表）：被引用的表，被参考的表从表（子表）：引用别人的表，参考别人的表例如：员工表的员工所在部门这......
  • 2024 Python3.10 系统入门+进阶（十五）：文件及目录操作
    目录一、文件IO操作1.1创建或打开文件1.2读取文件1.2.1按行读取1.2.2多行读取1.2.3完整读取1.3写入文件1.3.1写入字符串1.3.2写入序列1.4上下文管理1.4.1with语句的使用1.4.2上下文管理器(拓展----可以学了面向对象之后再回来看)1.5文件的遍历二、os.pat......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99