数据结构---线性表

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， 静态分配的插入与删除操作：

2.1插入操作：

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;}

2.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 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;}

3，顺序表的查找：

3.1按位查找

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

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

3.2按值查找

动态分配方式：

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

4,链表初始化

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

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

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;}

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

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;}

5，链表插入操作：

5.1,带头结点，按位序插入：

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;}

 5.2,不带头节点按位序插入：

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;}

5.3,指定节点的后插操作：

//在指定节点后插入一个元素
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;
}

 

5.4前插操作：

在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;
}

 6，链表删除操作：

6.1,带头结点按位序删除第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;
}

6.2,指定节点的删除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的前驱

7,单链表的查找（带头结点）

7.1按位查找

LNode *GetElem2(LinkList L, int i)
{if (i < 0)//第位序0返回的是头节点return NULL;LNode* p;p = L;int j = 0;//带头结点下标从0开始while (p != NULL && j < i){p = p->next;j++;}return p;
}

回顾：

 

7.2按值查找

LNode* GetElem3(LinkList L, int e)
{LNode* p=L->next;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;
}

 8，单链表的建立：

8.1尾插法建立单链表

LinkList List_TailInsert(LinkList& L)
{int a = 0;L = (LinkList)malloc(sizeof(LNode));//建立头结点scanf("%d", &a);LNode* r,*s = L;//r是尾结点while (a != 9999)//结束标志{s = (LNode*)malloc(sizeof(LNode));//放入新节点s->data = a;r->next = s;//建立链表连接r = s;//新的尾结点scanf("%d", &a);//循环输入数字}r->next = NULL;return L;}

8.2头插法建立单链表

LinkList List_HeadInsert(LinkList& L)
{int a = 0;LNode* s;L = (LinkList)malloc(sizeof(LNode));//建立头结点L->next = NULL;//初始化单链表，以防有脏数据scanf("%d", &a);while (a != 9999)//结束标志{s = (LNode*)malloc(sizeof(LNode));//放入新节点s->data = a;s->next= L->next;//建立链表连接L->next = s;//新的尾结点scanf("%d", &a);//循环输入数字}return L;}

 尾插法元素排列为顺序，头插法元素排列为逆序，头插法可以用于链表的逆置

9，双链表（带头结点）：

9.1定义：

typedef struct DNode {int data;struct DNode *prior,* next;
}DNode,*DLinkList;
bool InitDLinkList(DLinkList &L)
{L = (DNode*)malloc(sizeof(DNode));//分配头结点if (L == NULL)return false;L->prior = NULL;//头结点的前驱节点都为NULL；L->next = NULL;return true;
}
int main()
{DLinkList L;InitDLinkList(L);}

9.2插入操作（在p结点后插入s结点）

bool InsertNextDNode(DNode* p, DNode* s)
{if (p == NULL && s == NULL)return false;s->next = p->next;if (p->next != NULL)//p有后继节点p->next->prior = s;//则后继节点的前继指针指向ss->prior = p;p->next = s;return true;
}

9.3删除操作（删除p结点的后继节点）：

bool DeleteNextDNode(DNode* p)
{if (p == NULL)return false;DNode* q = p->next;if (q == NULL)return false;//没有后继节点p->next = q->next;if (q->next != NULL)//后继结点不为最后一个结点q->next->prior = p;//则后继节点的前继指针为sfree(q);return true;
}

9.4销毁双链表：

void DestoryList(DLinkList &L)//L代表的是链表的头指针
{while (L->next != NULL){DeleteNextDNode(L);//从表头开始删除}free(L);//释放头结点L = NULL;//头指针指向NULL
}

9.5遍历：

向后遍历：

while(p!=NULL)
{
p=p->next;
}

向前遍历(跳过头结点）：

while(p->prior!=NULL)
{
p=p->prior;}

 

10，循环链表：

10.1循环单链表

定义：

typedef struct LNode {int data;struct LNode* next;
}LNode,*LinkList;//初始化相同
bool InitList(LinkList& L)
{L = (LNode*)malloc(sizeof(LNode));//定义头结点if (L == NULL)//空间分配失败return false;L->next = L;//头指针只向自己return true;
}
bool IsEmpty(LinkList L)
{if (L->next == L)return true;elsereturn false;
}
bool IsTail(LinkList L,LNode *p)//判断p结点是否为尾结点
{if (p->next == L)return true;elsereturn false;
}

从一个结点出发，不同于单链表只能找到后续的各个节点，循环单链表可以找到其他任何一个结点 

10.2循环双链表：

初始化：

判断是否为空是否是表尾结点与循环单链表相同，初始化与双链表不同的是：

L->prior=L;
L->next=L;

插入后继结点：

bool InsertNextDNode(DNode* p, DNode* s)
{s->next = p->next;p->next->prior = s;//双链表需要判断是否是最后一个结点，循环双链表不需要s->prior = p;p->next = s;return true;
}

删除后继结点：

void DeleteNextDNode(DNode* p)
{p->next = q->next;q->next->prior = p;//双链表需要判断是否是最后一个结点，循环双链表不需要free(q);}

11,静态链表：用数组的方式实现链表

初始化：

#define MaxSize 10
typedef struct{
int data;
int next;
}SLinkList[MaxSize];
int main(){
SLinkList a;}

12，顺序表与链表的比较 

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

React 集成三方登录按钮样式的插件库

React 集成三方登录按钮样式的插件库

按钮不提供任何社交逻辑。 效果如下&#xff1a; 原地址&#xff1a;https://www.npmjs.com/package/react-social-login-buttons 时小记&#xff0c;终有成。
阅读更多...
沐风老师3DMAX物品摆放插件ObjectPlacer安装和使用方法详解

沐风老师3DMAX物品摆放插件ObjectPlacer安装和使用方法详解

3DMAX物品摆放插件ObjectPlacer安装和使用教程 3DMAX物品摆放插件ObjectPlacer&#xff0c;一键在曲面上摆放对象&#xff0c;如摆放家具物品、种植花草树木、布设电线杆交通标志等。它的功能是将对象与几何体对象&#xff08;网格、多边形、面片或NURBS&#xff09;的面法线对…
阅读更多...
提高大型语言模型 (LLM) 性能的四种数据清理技术

提高大型语言模型 (LLM) 性能的四种数据清理技术

原文地址&#xff1a;four-data-cleaning-techniques-to-improve-large-language-model-llm-performance 2024 年 4 月 2 日 检索增强生成&#xff08;RAG&#xff09;过程因其增强对大语言模型&#xff08;LLM&#xff09;的理解、为它们提供上下文并帮助防止幻觉的潜力而受…
阅读更多...
部署Kafka集群图文详细步骤

部署Kafka集群图文详细步骤

1 集群规划 共三台虚拟机同处overlay网段&#xff0c;每台虚拟机部署一套kafka和zookeeper&#xff0c;kafka_manager安装其中一台虚拟机上即可。 HostnameIP addrPortListenerzk1docker-swarm分配2183:2181zk2docker-swarm分配2184:2181zk3docker-swarm分配2185:2181k1docke…
阅读更多...
Navicat连接SQL server出现：[IM002] [Microsoft][ODBC 驱动程序管理器] 未发现数据源名称并且未指定默认驱动程序(0)

Navicat连接SQL server出现：[IM002] [Microsoft][ODBC 驱动程序管理器] 未发现数据源名称并且未指定默认驱动程序(0)

问题 解决方法 一 找到Navicat的安装路径&#xff0c;然后找到sqlncli_x64.msi文件并安装&#xff0c;安装成功后重启Navicat重新进行连接&#xff0c;看是否成功。 解决方法 二 如果方法一没有找到找到sqlncli_x64.msi 还是Navicat的安装路径&#xff0c;然后找到msodbcsql_64…
阅读更多...
Linux磁盘扩容并设置挂载点

Linux磁盘扩容并设置挂载点

背景 使用pve创建了一个虚拟机&#xff0c;各种环境配置都安装好了之后发现分配的磁盘空间太小了&#xff0c;默认的就30多个G&#xff0c;这还没咋玩呢就满了&#xff0c;像扩容却找遍了这个pve都没找到扩容按钮&#xff0c;并且我这个磁盘不是lvm结构的&#xff0c;所以好像…
阅读更多...
Zookeeper集群+消息队列Kafka

Zookeeper集群+消息队列Kafka

一. Zookeeper 集群的相关知识 1. zookeeper的概念 ZooKeeper 是一个分布式的&#xff0c;开放源码的分布式应用程序协调服务&#xff0c;是Google的Chubby一个开源的实现&#xff0c;是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件&#xff0c;提供的…
阅读更多...
zookeeper分布式应用程序协调服务+消息中间件kafka分布式数据处理平台

zookeeper分布式应用程序协调服务+消息中间件kafka分布式数据处理平台

一、zookeeper基本介绍 1.1 zookeeper的概念 Zookeeper是一个开源的分布式的&#xff0c;为分布式框架提供协调服务的Apache项目。 是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件&#xff0c;提供的功能包括&#xff1a;配置维护、域名服务、…
阅读更多...
【Excel】使用VBA宏简单自定义Excel软件界面

【Excel】使用VBA宏简单自定义Excel软件界面

改行做经济师学习Excel&#xff0c;偶有心得&#xff0c;摘录于此&#xff0c;备忘。 言简意赅&#xff0c;仅供自用。 1 实现效果 在Excel的左上角可添加按钮&#xff0c;该按钮的功能可由我们自己通过编写代码定义&#xff0c;能实现特定功能&#xff0c;并且在所有打开的…
阅读更多...
Electron 桌面端应用的使用 ---前端开发

Electron 桌面端应用的使用 ---前端开发

Electron是什么&#xff1f; Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 嵌入 Chromium 和 Node.js 到 二进制的 Electron 允许您保持一个 JavaScript 代码代码库并创建 在Windows上运行的跨平台应用 macOS和Linux——不需要本地开发 经验。 入门…
阅读更多...
LLM大语言模型助力DataEase小助手，新增气泡地图，DataEase开源数据可视化分析平台v2.5.0发布

LLM大语言模型助力DataEase小助手，新增气泡地图，DataEase开源数据可视化分析平台v2.5.0发布

2024年4月8日&#xff0c;DataEase开源数据可视化分析平台正式发布v2.5.0版本。 这一版本的功能升级包括&#xff1a;新增DataEase小助手支持&#xff0c;通过结合智能算法和LLM&#xff08;即Large Language Model&#xff0c;大语言模型&#xff09;能力&#xff0c;DataEas…
阅读更多...
浮点数在内存中的存储

浮点数在内存中的存储

索引 1. 浮点数在内存中的存储2. 浮点数存的过程3. 浮点数取的过程4. 题目解析 正文开始 1. 浮点数在内存中的存储 常见的浮点数: 3.14159 , 1E10等, 浮点数家族包括 : float , double , long double类型. 浮点数的表示范围在 float.h中定义. (1E10为科学计数法表示1.0 * 2的…
阅读更多...
从零开始编写一个cmake构建脚本

从零开始编写一个cmake构建脚本

简介 本文档介绍cmake构建脚本编写&#xff0c;包含的一些主要元素和命名规范。 cmake构建脚本编写步骤 cmake构建工具版本要明确 # 命令名字要小写&#xff0c;这条语句要求构建工具至少需要版本为3.12或以上 cmake_minimum_required (VERSION 3.12)工程名及库的版本号明确…
阅读更多...
SQLite从出生到现在（发布历史记录）（二十二）

SQLite从出生到现在（发布历史记录）（二十二）

返回&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;从 SQLite 3.5.9 迁移到 3.6.0&#xff08;二十一&#xff09; 下一篇:PSQLite的RAGMA 声明 引言&#xff1a; SQLite拥有别人无法比拟的装机量&#xff0c;究竟什么成就了SQLite呢&#xff0c;本文将SQLite的历…
阅读更多...
探索进程控制第一弹（进程终止、进程等待）

探索进程控制第一弹（进程终止、进程等待）

文章目录 进程创建初识fork函数fork函数返回值fork常规用法fork调用失败的原因 写时拷贝进程终止进程终止是在做什么&#xff1f;进程终止的情况代码跑完&#xff0c;结果正确/不正确代码异常终止 如何终止 进程等待概述进程等待方法wait方法waitpid 进程创建 初识fork函数 在…
阅读更多...
代码随想录算法训练营第51天|309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

代码随想录算法训练营第51天|309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

309.最佳买卖股票时机含冷冻期 题目链接&#xff1a;最佳买卖股票时机含冷冻期 题目描述&#xff1a;给定一个整数数组prices&#xff0c;其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下&#xff0c;你可以尽可能地完成更多的交…
阅读更多...
【CLR】《Cyclical Learning Rates for Training Neural Networks》

【CLR】《Cyclical Learning Rates for Training Neural Networks》

WACV-2017 IEEE Winter Conference on Applications of Computer Vision 文章目录 1 Background and Motivation2 Related Work3 Advantages / Contributions4 Method5 Experiments5.1 Datasets and Metrics5.2 CIFAR-10 and CIFAR-1005.3 ImageNet 6 Conclusion&#xff08;o…
阅读更多...
内网渗透-cobaltstrike之cs上线获取shell

内网渗透-cobaltstrike之cs上线获取shell

cobaltstrike之cs上线获取shell 文章目录 cobaltstrike之cs上线获取shell前言一、什么是cobaltstrike二、cs上线获取shell 1.环境搭建 CS安装windows连接 2. cs上线获取shell 总结 前言 一、什么是cobaltstrike CobaltStrike是一款渗透测试神器&#xff0c;被业界人称为CS神器…
阅读更多...
在线视频下载工具lux（原annie）安装及使用教程

在线视频下载工具lux（原annie）安装及使用教程

安装教程 下载ffmpeg&#xff0c;参考这篇文章&#xff1a;Python——Windows下载ffmpeg由于博主的系统为windows&#xff0c;所以选择不安装lux&#xff0c;直接下载.exe文件&#xff0c;进入lux的github网站后&#xff0c;选择右侧的Releases&#xff0c;下载下图的windows …
阅读更多...
五、LoadBalancer负载均衡服务调用

五、LoadBalancer负载均衡服务调用

一、Ribbon目前也进入维护模式 1、是什么 Spring Cloud Ribbon是基于Netflix Ribbon实现的一套客户端负载均衡的工具。 简单的说&#xff0c;Ribbon是Netflix发布的开源项目&#xff0c;主要功能是提供客户端的软件负载均衡算法和服务调用。Ribbon客户端组件提供一系列完善的…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023