数据结构---线性表

1，顺序表实现---动态分配

#include<stdlib.h>
#define InitSize 10
typedef struct {
	int *data;//静态分配
	int length;
	int MaxSize;
}SqList;
void InitList(SqList& L)
{
	L.data = (int*)malloc(InitSize * sizeof(int));//分配空间
	L.length = 0;
	L.MaxSize = InitSize;//初始空间为10

}
void ListInsert(SqList& L, int x, int a)
{
	L.data[x] = a;
}
void Increaselength(SqList& L, int len)
{
	int *p = L.data;
	L.data = (int*)malloc((InitSize + len) * sizeof(int));//重新开辟空间
	for (int i = 0; i < L.MaxSize;i++)
	{
		L.data[i] = p[i];
	}
	L.MaxSize = InitSize + len;
	free(p);


}
int main()
{
	SqList q;
	InitList(q);
	ListInsert(q, 2, 4);
	Increaselength(q, 5);
	ListInsert(q, 12, 2);
	printf("data[2]=%d,data[12]=%d", q.data[2],  q.data[12]);
	system("pause");
	return 0;
}

 第i个元素中的i表示的是位序

2， 静态分配的插入元素操作：

typedef struct {
	int data[MaxSize];
	int length;

}SqList;
void InitList(SqList& L)
{
	L.length = 0;
	for (int i = 0; i <MaxSize-1; i++)
	{
		L.data[i] = i;//赋予原始数据，注意不要插满
		L.length++;
	}

}
bool ListInsert(SqList &L,int i,int e)//在第i个位置插入e
{
	if (i<1 || i>L.length + 1)
		return false;
	if (L.length >= MaxSize)//存储空间已满
	{
		return false;
	}
	for(int j=L.length;j>=i;j--)
	{
		L.data[j] = L.data[j - 1];
		 }
	L.data[i - 1] = e;
	L.length++;
	return true;

}
int main()
{
	SqList L;
	InitList(L);
	if (ListInsert(L, 8, 1))
	{
		printf("data[7]=%d ", L.data[7]);//验证插入
	}
	system("pause");
	return 0;

}

3，静态分配的删除元素操作：

typedef struct {
	int data[MaxSize];
	int length;

}SqList;
void InitList(SqList& L)
{
	L.length = 0;
	for (int i = 0; i < MaxSize - 1; i++)
	{
		L.data[i] = i;//赋予原始数据，注意不要插满
		L.length++;
	}

}
bool ListDelete(SqList &L,int i,int &e)//在第i个位置插入e
{
	if (i<1 || i>L.length)
		return false;
	e=L.data[i - 1];//赋值
	for(int j=i;j<L.length;j++)
	{
		L.data[j-1] = L.data[j];
		 }

	L.length--;
	return true;

}

int main()
{
	SqList L;
	InitList(L);
	int e = -1;
	if (ListDelete(L, 8, e))//位置8的元素是7
	{
		printf("删除的元素是%d data[7]=%d", e,L.data[7]);//验证删除，删除后data[7]=8
	}
	system("pause");
	return 0;

}

顺序表的查找：

按位查找,动态分配和普通数组访问方式相同,时间复杂度为O（1）

GetElem(SqList L,int i)
{
return L.data[i-1];
}

按值查找，动态分配方式：

int LocatElem(SqList L, int e)
{
for(int i=0;i<L.length;i++)
{
if(L.data[i]==e)
return i+1;
}
return 0;}

不带头结点的单链表的初始化：

与顺序表不同，单链表是用指针来定义

 

typedef struct LNode {
	int data;
	struct LNode* next;//每个元素包括数据和指向下一个节点的指针

}LNode,*LinkList;//LNode*等价于LinkList
bool InitList(LinkList &L)//声明是一个单链表
{
	L = NULL;
	return true;

    }
bool IsEmpty(LinkList &L)//声明是一个单链表
{
	return (L == NULL);

}
int main()
{
	LinkList L;//声明一个指向单链表的指针
	InitList(L);
	if(IsEmpty(L))
		printf("初始化成功");
	system("pause");
	return 0;

}

带头结点的单链表的初始化： 

typedef struct LNode {
	int data;
	struct LNode* next;//每个元素包括数据和指向下一个节点的指针

}LNode,*LinkList;//LNode*等价于LinkList
bool InitList(LinkList &L)//声明是一个单链表
{
	L = (LNode*)malloc(sizeof(LNode));//头指针指向下一个节点：即为头节点
	if (L == NULL)
		return false;//没有内存，分配失败
	L->next = NULL;//头节点暂时没有节点
	return true;

 }
bool IsEmpty(LinkList &L)//声明是一个单链表
{
	return (L == NULL);

}
int main()
{
	LinkList L;
	InitList(L);
	if(IsEmpty(L)==false)
		printf("初始化成功");
	system("pause");
	return 0;

}

带头结点，按位序插入：

typedef struct LNode {
	int data;
	struct LNode* next;//每个元素包括数据和指向下一个节点的指针

}LNode,*LinkList;//LNode*等价于LinkList
//带头结点按位序插入
bool ListInsert(LinkList& L,int i,int e)//在第i个位置插入e
{
	if (i < 1)
		return false;
	int j = 0;
	LNode *p;
	p= L;//是从第0个节点开始遍历，所以p应该与头节点相同
	while (p != NULL && j < i - 1)//找到第i-1的节点
	{
		p = p->next;
		j++;
	}
	if (p == NULL)//超出链表长度
	{
		return false;
	}
	LNode *s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;

}
bool InitList(LinkList &L)//声明是一个单链表
{
	L = (LNode*)malloc(sizeof(LNode));//头指针指向下一个节点：即为头节点
	if (L == NULL)
		return false;//没有内存，分配失败
	L->next = NULL;//头节点暂时没有节点
	return true;

 }
bool IsEmpty(LinkList &L)//声明是一个单链表
{
	return (L == NULL);

}
int main()
{
	LinkList L;
	InitList(L);
	if(IsEmpty(L)==false)
		printf("初始化成功");
	if(ListInsert(L, 1, 1))
		printf("插入成功");
	system("pause");
	return 0;

}

 不带头节点按位序插入：

bool ListInsert(LinkList& L,int i,int e)//在第i个位置插入e
{
	if (i < 1)
		return false;
	if (i == 1)//此处插入第一个节点和其他节点不同，直接与L交互
	{
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;//指向L指向的节点
		L = s;//需要更改头结点的指向，比较麻烦
		return true;
	}
	int j = 1;//没有第0个节点
	LNode *p;
	p= L;//是从第0个节点开始遍历，所以p应该与头节点相同
	while (p != NULL && j < i - 1)//找到第i-1的节点
	{
		p = p->next;
		j++;
	}
	if (p == NULL)//超出链表长度
	{
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;

}

指定节点的后插操作：

//在指定节点后插入一个元素
bool InsertNextLNode(LNode *p,int e)//传入节点即可，不需要传入表
{
	if (p == NULL)
		return false;//节点选择错误
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL)//内存分配不够
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

 

前插操作：

在p节点之前插入s节点

思路：无法找到前驱节点，因此可以插在p节点之后，然后将两个节点中的数据调换

bool InsertPriorNode(LNode* p, LNode* s)
{
	if (p == NULL || s == NULL)
		return false;
	s->next = p->next;
	p->next = s;
	int temp = s->data;
	s->data = p->data;
	p->data = temp;
	return true;
}

 带头结点按位序删除第i个节点：

思路：先找到第i-1节点，然后将前一个结点的next指针指向后一个结点的next指针

bool ListDelete(LinkList L, int i, int& e)
{
	if (i < 1)
		return false;
	LNode* p = L;//当前指向结点
	int j = 0;
	while (p != NULL&&j<i-1) {//找到i-1结点
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	if (p->next== NULL)//需要删除的结点也为空
		return false;
	LNode* q = p->next;//应当被删除的结点
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

指定节点的删除p：

将p的后一个结点复制到p,然后将p的后一个结点释放掉

bool DeleteNode(LNode* p)
{
	if (p == NULL)
		return false;
	LNode* q = p->next;
	p->data = p->next->data;
	p->next = q->next;
	free(q);
	return true;
}

注意：如果p是最后一个结点，只能从表头依次寻找p的前驱

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/529547.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

企业如何管理员工技能，提升人员管理质效？

企业如何管理员工技能，提升人员管理质效？

最近总有客户来抱怨&#xff0c;传统集团由于企业规模庞大、员工分散及线下管理模式局限&#xff0c;导致HR部门工作效率不高&#xff0c;无法及时解决一线员工的岗位排班、员工技能水平变更等问题。 正好&#xff0c;最近我们有类似成功案例和大家分享一下。 我们特意邀请到…
阅读更多...
猫头虎分享已解决Error: 解决“IndexError: list index out of range“

猫头虎分享已解决Error: 解决“IndexError: list index out of range“

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 文章目录 猫头虎分享已解决Error: 解决"IndexError: list index out of range" &#x1f431;&#x1f989;&#x1f6e0;️摘要正文内容一、错误现场勘察 &#x1f575…
阅读更多...
关于Linux内核code段被改写的原因分析

关于Linux内核code段被改写的原因分析

本文基于Linux-4.19.125&#xff0c; ARM V7&#xff0c;dual core。 1 code 段 Linux的code段&#xff08;或者说text段&#xff09;自_stext开始&#xff0c;到_etext结束&#xff0c;这段内容一般情况下是只读的&#xff0c;在理论上来说&#xff0c;这段数据在设备上应该…
阅读更多...
如何在淘~宝接单和解决别人问题-java开发

如何在淘~宝接单和解决别人问题-java开发

如下这是一个连接&#xff1a;https://s.tb.cn/c.0vDtL3https://s.tb.cn/c.0vDtL3 解决各种问题。可付费咨询
阅读更多...
初识C++ · 类和对象(上)

初识C++ · 类和对象(上)

目录 1.面向过程和面向对象初步认识 2.类的引入 3.类的定义 4.类的访问限定符及封装 4.1 访问限定符 4.2 封装 5.类的作用域 6.类的实例化 7.类的对象大小的计算 8.类成员函数的this指针 1.面向过程和面向对象初步认识 C语言是一门面向过程的语言&#xff0c;注重的…
阅读更多...
FPGA(Verilog)实现按键消抖

FPGA(Verilog)实现按键消抖

实现按键消抖功能&#xff1a; 1.滤除按键按下时的噪声和松开时的噪声信号。 2.获取已消抖的按键按下的标志信号。 3.实现已消抖的按键的连续功能。 Verilog实现 模块端口 key_filter(input wire clk ,input wire rst_n ,input wire key_in , //按下按键时为0output …
阅读更多...
《QT实用小工具·二十二》多种样式导航按钮控件

《QT实用小工具·二十二》多种样式导航按钮控件

1、概述 源码放在文章末尾 该项目实现了多种样式的导航按钮控件 可设置文字的左侧、右侧、顶部、底部间隔。 可设置文字对齐方式。 可设置显示倒三角、倒三角边长、倒三角位置、倒三角颜色。 可设置显示图标、图标间隔、图标尺寸、正常状态图标、悬停状态图标、选中状态图标…
阅读更多...
纯C语言手搓GPT-2，前OpenAI、特斯拉高管新项目火了

纯C语言手搓GPT-2，前OpenAI、特斯拉高管新项目火了

ChatGPT狂飙160天&#xff0c;世界已经不是之前的样子。 新建了免费的人工智能中文站https://ai.weoknow.com 新建了收费的人工智能中文站https://ai.hzytsoft.cn/ 更多资源欢迎关注 「Real men program in C.」 众所周知&#xff0c;大语言模型还在快速发展&#xff0c;应该有…
阅读更多...
自动驾驶基础技术-无迹卡尔曼滤波UKF

自动驾驶基础技术-无迹卡尔曼滤波UKF

自动驾驶基础技术-无迹卡尔曼滤波UKF Unscented Kalman Filter是解决非线性卡尔曼滤波的另一种思路&#xff0c;它利用Unscented Transform来解决概率分布非线性变换的问题。UnScented Kalman Filter不需要像Extended Kalman Filter一样计算Jacobin矩阵&#xff0c;在计算量大…
阅读更多...
Vue - 你知道Vue2中对象动态新增属性，视图无法更新的原因吗

Vue - 你知道Vue2中对象动态新增属性，视图无法更新的原因吗

难度级别：中高级及以上 提问概率：55% 这道题面试官会这样描述，比如有这样一个场景，一个对象里有name属性，可以正常显示在页面中。但后续动态添加了一个age属性，通过调试打印发现对象里的age属性已经添加了上了，但试图中却没有展示出来，…
阅读更多...
程序语言基础

程序语言基础

根据希赛相关视频课程汇总整理而成&#xff0c;个人笔记&#xff0c;仅供参考。考点偏向于通用程序语言的基础概念。 程序语言基础概念 程序设计语言&#xff1a; ①低级语言 机器语言汇编语言 汇编语言&#xff1a;指令语句/伪指令语句/宏指令语句 ②高级语言 Fotrane语言&…
阅读更多...
计算系数（acwing，数论）

计算系数（acwing，数论）

题目描述&#xff1a; 给定一个多项式 (axby)^k&#xff0c;请求出多项式展开后 x^n*y^m 项的系数。 输入格式&#xff1a; 共一行&#xff0c;包含 5 个整数&#xff0c;分别为 a&#xff0c;b&#xff0c;k&#xff0c;n&#xff0c;m&#xff0c;每两个整数之间用一个空格…
阅读更多...
2024马来西亚电商选品博览会

2024马来西亚电商选品博览会

2024马来西亚电商选品博览会 展会概况 展会名称&#xff1a;2024马来西亚电商选品博览会 主办单位&#xff1a;广东进出口商会 时间:2024.11.29-12.1 地点&#xff1a;马来西亚国际贸易展览中心(MITEC) 展览面积&#xff1a;10000平方米 展会简介 2024马来西亚跨境电商选…
阅读更多...
vue2 父子组件通讯

vue2 父子组件通讯

父传子 父组件&#xff1a;app.vue <template><div>app 父组件<!-- 2.动态绑定定义的数据 --><LiCount :title"mytitle"></LiCount></div> </template><script> import LiCount from "./components/LiCount.…
阅读更多...
自定义的@TableField，解决插入或更新失效

自定义的@TableField，解决插入或更新失效

自定义的TableField&#xff0c;解决插入或更新失效 01 使用场景 需要使用到mybatisplus的自动填充时 02 配置类和扫描包 在启动类处配置扫描包&#xff0c;每次启动扫描配置类 配置类 package com.ruoyi.framework.hander;import com.baomidou.mybatisplus.core.handlers.…
阅读更多...
c# wpf LiveCharts 饼图 简单试验

c# wpf LiveCharts 饼图 简单试验

1.概要 c# wpf LiveCharts 饼图 简单试验 2.代码 <Window x:Class"WpfApp3.Window5"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schem…
阅读更多...
YOLOv9改进策略 ：小目标 | 新颖的多尺度前馈网络(MSFN) | 2024年4月最新成果

YOLOv9改进策略 ：小目标 | 新颖的多尺度前馈网络(MSFN) | 2024年4月最新成果

💡💡💡本文独家改进：多尺度前馈网络(MSFN)，通过提取不同尺度的特征来增强特征提取能力，2024年最新的改进思路 💡💡💡创新点：多尺度前馈网络创新十足，抢先使用 💡💡💡如何跟YOLOv8结合：1）放在backbone后增强对全局和局部特征的提取能力；2）放在detect…
阅读更多...
在Spring中使用Redis

在Spring中使用Redis

端口怎么设置&#xff0c;看我前一篇文章 前面使用jedis&#xff0c;通过Jedis对象中各种方法来操作redis的。 此处Spring中则是通过StringRedisTemplate来操作redis。 最原始提供的类是RedisTemplate StringRedisTemplate是RedisTemplate的子类&#xff0c;专门处理文本数据的…
阅读更多...
网格矢量如何计算莫兰指数

网格矢量如何计算莫兰指数

网格矢量如何计算莫兰指数 引言 遇到一个问题&#xff0c;计算矢量网格的莫兰指数。 概念解释 莫兰指数 莫兰指数&#xff08;Moran’s Index&#xff09;是一种空间自相关指标&#xff0c;用于衡量空间数据的相似性和聚集程度。它可以用来描述一个区域与其邻近区域之间的属…
阅读更多...
LeetCode 使数组连续的最少操作数

LeetCode 使数组连续的最少操作数

地址&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 难度&#xff1a;困难 题目描述&#xff1a;给你一个整数数组 nums 。每一次操作中&#xff0c;你可以将 nums 中 任意 一个元素替换成 **任意 **整数。 如果 nums 满足以下条件&#xff0c;那么它是 连续的 &#x…
阅读更多...
最新文章

Copyright @ 2022~2023