王道数据结构个人向笔记-第二章(线性表)

文章目录

  • 2.1 线性表的定义和基本操作
  • 2.2 顺序表
    • 2.2.1 顺序表的定义
    • 2.2.2 顺序表的插入、删除(实现是基于静态分配)
    • 2.2.3 顺序表的查找
  • 2.3 链表
    • 2.3.1 单链表的定义
    • 2.3.2 单链表的插入删除
    • 2.3.3 单链表的查找
    • 2.3.4 单链表的建立
    • 2.3.4 双链表
    • 2.3.5 循环链表
    • 2.3.6 静态链表
    • 2.3.7 顺序表和链表的对比

2.1 线性表的定义和基本操作

线性表:是具有相同数据类型 n ( n > = 0 ) n(n>=0) n(n>=0)个元素的有限序列,其中n为表长,当 n = 0 n=0 n=0时线性表是一个空表。若用L命名线性表,则其一般表示为
L = ( a 1 , a 2 , . . . , a i , a i + 1 , . . . , a n ) L=(a_1,a_2,...,a_i,a_{i+1},...,a_n) L=(a1,a2,...,ai,ai+1,...,an)
image

  • 相同的数据类型意味着每个元素所占的空间一样大
  • a i a_i ai是表头元素: a n a_n an是表尾元素
  • 除第一个元素外,每个元素有且仅有一个直接前驱;除最后一个元素外,每个元素有且仅有一个直接后继
    线性表的基本操作
    InitList(&L):初始化表。构造一个空的线性表L,分配内存空间。
    DestroyList(&L):销毁线性表,并释放线性表L所占用的内存空间
    ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e
    ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值
    LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值得元素。
    GetElem(L,i):按位查找操作。获取表L中第i个位置得元素得值。
    其他常用操作:
    Lengt h(L):求表长。返回线性表L得长度,即L中数据元素的个数。
    PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
    Empty(L):判空操作。若L为空表,则返回true,否则返回false.
    image

2.2 顺序表

2.2.1 顺序表的定义

顺序表:用顺序存储的方式实现线性表。所谓顺序存储,把逻辑上相邻的元素存储在物理上也相邻的存储单元中,元素之间的关系由存储单元的临界关系来体现。

顺序表的实现-静态分配

#define MaxSize 10  //定义最大长度
typedef struct {ElemType data[MaxSize]; //用静态的数组存放数据元素int length; //顺序表的当前长度
}SqList;

实现

#include <bits/stdc++.h>using namespace std;
#define MaxSize 10
typedef struct {int data[MaxSize];  //用静态的数组存放数据元素int length; //顺序表的当前长度
}SqList;void InitList(SqList &L){for(int i=0; i<MaxSize; i++){L.data[i]=0;    //将所有数据元素设置为默认初始值}L.length=0; //顺序表初始长度为0
}int main() {SqList L;    //生命一个顺序表InitList(L);return 0;
}

image
顺序表的实现-动态分配

#define InitSize 10
typedef struct {ElemType *data;  //指示动态分配数组的指针int MaxSize; //顺序表的最大容量int length;  //顺序表的当前长度
}SeqList;   //顺序表的类型定义(动态分配方式)

c语言中提供了malloc和free函数动态申请和释放内存空间

#include <bits/stdc++.h>using namespace std;
#define InitSize 10
typedef struct {int *data;  //指示动态分配数组的指针int MaxSize; //顺序表的最大容量int length;  //顺序表的当前长度
}SeqList;   //顺序表的类型定义(动态分配方式)void InitList(SeqList &L){L.data=(int*)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;
}//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){int *p=L.data;L.data=(int *) malloc((L.MaxSize+len)*sizeof(int));for(int i=0; i<L.length; ++i){L.data[i]=p[i]; //将数据复制到新区域}L.MaxSize=L.MaxSize+len;    //顺序表最大长度增加lenfree(p);
}int main() {SeqList L;  //声明一个顺序表InitList(L);    //初始化顺序表cout<<L.MaxSize<<'\n';IncreaseSize(L,5);cout<<L.MaxSize<<'\n';return 0;
}

image

顺序表的特点

  • 随机访:即可以在 O ( 1 ) O(1) O(1)时间内找到第i个元素
  • 存储密度高,每个节点只存储数据元素
  • 拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
  • 插入、删除操作不方便,需要移动大量元素

image

2.2.2 顺序表的插入、删除(实现是基于静态分配)

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

#include <bits/stdc++.h>using namespace std;
#define MaxSize 10
typedef struct {int data[MaxSize];  //用静态的数组存放数据元素int length;  //顺序表的当前长度
}SqList;   //顺序表的类型定义(动态分配方式)void InitList(SqList &L){for(int i=0; i<MaxSize; i++){L.data[i]=0;    //将所有数据元素设置为默认初始值}L.length=0; //顺序表初始长度为0
}void ListInsert(SqList &L, int i, int e){for(int j=L.length;j>=i;j--)    L.data[j]=L.data[j-1];L.data[i-1]=e;  //在位序i处放入eL.length++; //插入元素后长度增加1
}void Print(SqList L){for(int i=0; i<L.length; ++i) cout<<L.data[i]<<' ';cout<<'\n';}int main() {SqList L;   //生命顺序表InitList(L);ListInsert(L,1,1);ListInsert(L,2,2);Print(L);ListInsert(L,3,3);Print(L);return 0;
}

image

更健壮的代码
考虑了插入位置是否合法,空间容量是否合法

bool ListInsert(SqList &L, int i, int e){if(i<1||i>L.length+1||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;  //在位序i处放入eL.length++; //插入元素后长度增加1return true;
}

插入操作的时间复杂度
关注最深层for循环语句执行的次数与问题规模n的关系
image
顺序表的删除

bool ListDelete(SqList &L, int i, int &e){if(i<1||i>L.length) return false;   //判断i的位置是否合法e=L.data[i-1];  //回带删除元素的值for(int j=i; j<L.length; j++)   L.data[j-1]=L.data[j];  //将第i个位置后的元素前移L.length--; //线性表当前长度加1return true;
}

egg

#include <bits/stdc++.h>using namespace std;
#define MaxSize 10
typedef struct {int data[MaxSize];  //用静态的数组存放数据元素int length;  //顺序表的当前长度
}SqList;   //顺序表的类型定义(动态分配方式)void InitList(SqList &L){for(int i=0; i<MaxSize; i++){L.data[i]=0;    //将所有数据元素设置为默认初始值}L.length=0; //顺序表初始长度为0
}bool ListInsert(SqList &L, int i, int e){if(i<1||i>L.length+1||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;  //在位序i处放入eL.length++; //插入元素后长度增加1return true;
}bool ListDelete(SqList &L, int i, int &e){if(i<1||i>L.length) return false;   //判断i的位置是否合法e=L.data[i-1];  //回带删除元素的值for(int j=i; j<L.length; j++)   L.data[j-1]=L.data[j];  //将第i个位置后的元素前移L.length--; //线性表当前长度加1return true;
}void Print(SqList L){for(int i=0; i<L.length; ++i) cout<<L.data[i]<<' ';cout<<'\n';}int main() {SqList L;   //生命顺序表InitList(L);ListInsert(L,1,1);ListInsert(L,2,2);ListInsert(L,3,3);Print(L);int e=0;ListDelete(L,3,e);cout<<"Delete element's value is "<<e<<'\n';Print(L);return 0;
}

image

删除操作的时间复杂度
image

image

2.2.3 顺序表的查找

查找有两种一种是按位茶盅,一种是按值查找
按位查找

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

image
按值查找

//按值查找,在顺序表L找查找第一个元素值等于e的元素,并返回其位序
int LocateElem(SqList L, int e){for(int i=0; i<L.length; ++i){if(L.data[i]==e)    return i+1; //数组下标为i的元素值等于e,返回其位序i+}return 0;   //查找失败返回0
}

image

image

2.3 链表

关于链表的实现可以看这篇博客(侧重于实现)链表的实现

2.3.1 单链表的定义

image

typedef struct LNode{   //定义单链表的节点类型ElemType data;  //每个节点存放一个数据元素struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;

image

不带头节点的单链表的初始化

bool InitList(LinkList &L){L=NULL; //空表,暂时还没有任何节点return true;
}void test(){LinkList L; //声明一个指向单链表的指针InitList(L);
}

带头结点的单链表


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=NULL;   //头节点之后暂时还有没节点return true;
}bool Empty(LinkList L){if(L->next==NULL)   return true;else    return false;
}void test(){LinkList L; //声明一个指向单链表的指针InitList(L);
}

image

2.3.2 单链表的插入删除

带头结点的插入

//在第i各位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, int e){if(i<1) return false;LNode *p;   //指针p指向当前扫描到的节点int j=0;p=L;    //L指向头节点,头节点是第0各节点(不存数据)while(p!=NULL&&j<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;
}

不带头结点需要对第一个位置进行特殊处理

指定节点的后插操作

//后插操作,在p节点之后插入元素e
bool InsertNextNode(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;
}

指定节点的前插操作(头天换日O(1))

//前插操作:在p节点之前插入元素e
bool InsertPriorNode(LNode *p, int e){if(p==NULL) return false;LNode *s = (LNode *) malloc(sizeof(LNode));if(s==NULL) return false;   //内存分配失败s->next=p->next;p->next=s;  //新节点s连到p之后s->data=p->data;    //将p中元素复制到s中p->data=e;  //p中元素覆盖为ereturn true;
}

按位序删除

bool ListDelete(LinkList &L, int i, int e){if(i<1) return false;LNode *p;   //指针p指向当前扫描到的节点int j=0;    //当前o指向的是第几个节点p=L;    //L指向头节点,头节点是第0个节点while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}if(p==NULL) return false;   //i值不合法if(p->next==NULL)  return false; //第i-1个节点之后已经无其他节点LNode *q=p->next;   //q指向被删除节点e=q->data;  //用e返回元素的值p->next=q->next;    //将*q节点从链中断开free(q);    //释放节点的存储空间return true;
}

删除指定节点

//删除指定节点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;
}

上面代码是有bug的,当是最后一个结点的是偶p->next->data这个会出错,因为p->next=NULL

2.3.3 单链表的查找

按位序查找

//按位查找,返回第i个元素(带头结点)
LNode *GetElem(LinkList L, int i){if(i<0) return NULL;LNode *p;   //当指针p指向当前扫描到的结点int j=0;    //当前p指向的是第几个结点p=L;while(p!=NULL&&j<i){//循环找到第i个结点p=p->next;j++;}return p;
}

按值查找

//按值查找,找到数据域==e的结点
LNode * LocateElem(LinkList L, int e){LNode *p=L->next;while(p!=NULL&&p->data!=e)  p=p->next;return p;   //找到后返回该结点指针,否则返回NULL;
}

2.3.4 单链表的建立

image
尾插法可以设置一个变量length记录当前链表的长度,然后调用之前的按位序插入函数这样的话时间复杂度是 O ( n 2 ) O(n^2) O(n2)的,因为每次我们都需要从头开始遍历这是没有必要的,我们可以用一个指针去指向最后一个结点

LinkList List_Tailnsert(LinkList &L){int x;L=(LinkList) malloc(sizeof(LNode)); //建立头节点LNode *s,*r=L;  //r为表尾指针scanf("%d",&x); //输入结点的值while(x!=9999){//输入9999表示结束s=(LNode *) malloc(sizeof(LNode));s->data=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;   //尾结点指针置空return L;
}

头插法

//头插法
LinkList List_HeadInsert(LinkList &L){//逆向建立单链表LNode  *s;int x;L=(LinkList) malloc(sizeof (LNode));    //创建头节点L->next=NULL;   //初始化空链表scanf("%d",&x);while(x!=9999){//输入9999表示结束s=(LNode *) malloc(sizeof(LNode));s->data=x;s->next=L->next;L->next=s;  //将新节点插入到表中,L为头指针scanf("%d",&x);}return L;
}

头插法可以实现链表的逆置

2.3.4 双链表

双链表的定义

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;  //头节点的prior永远指向NULLL->next=NULL;   //头节点之后暂时还没有结点return true;
}

双链表的插入

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){if(p==NULL||s==NULL)    return false;   //非法参数s->next=p->next;//如果p有后继结点if(p->next!=NULL)   p->next->prior=s;s->prior=p;p->next=s;return true;
}

双链表的删除

bool DeleteNextDNode(DNode *p){if(p==NULL) return false;DNode *q=p->next;   //找到p的后继节点qif(q==NULL) return false;   //p没有结点p->next=q->next;if(q->next!=NULL)   q->next->prior=p;free(q);return true;
}

image

2.3.5 循环链表

image
循环单链表
初始化循环单链表

//初始化一个循环单链表
bool InitList(LinkList &L){L=(LNode *) malloc(sizeof (LNode));if(L==NULL) return false;L->next=L;  //头节点next指向头结点return true;
}

判空

//判断循环单链表是否为空
bool Empty_(LinkList L){if(L->next==L)  return true;else    return false;
}

循环单链表可以从任意结点出发找到任何单链表中的结点
image
循环双链表
image
循环双链表的初始化


//初始化空的循环双链表
bool InitDLinkList_(DLinklist &L){L=(DNode*) malloc(sizeof (DNode));if(L==NULL) return false;L->prior=L; //头节点的prior指向头节点L->next=L;  //头节点的next指向头节点return true;
}

判空的和循环单链表一样

//判断结点p是否为循环双链表的表尾结点
bool isTaol(DLinklist L, DNode *p){if(p->next==L)  return true;else    return false;
}

双链表的插入

//在p结点之后插入s结点
bool InsertDNode_(DNode *p, DNode *s){s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;
}

image

2.3.6 静态链表

参考现实博客

2.3.7 顺序表和链表的对比

image

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

React18+TS+NestJS+GraphQL 全栈开发在线教育平台

高质量平台级应用流行全栈技术实用职场技巧通用面试策略React18TSNestJSGraphQL 全栈开发在线教育平台&#xff08;完结&#xff09; 黑石老师&#xff0c;大厂技术专家&#xff0c;深耕前后端十多年。发现很多的前端同学都面临如下的职业困扰&#xff1a;没有能拿的出手的面试…

机器人系统ros2-开发实践07-将机器人的状态广播到 tf2(Python)

上个教程将静态坐标系广播到 tf2&#xff0c;基于这个基础原理这个教程将演示机器人的点位状态发布到tf2 1. 写入广播节点 我们首先创建源文件。转到learning_tf2_py我们在上一教程中创建的包。在src/learning_tf2_py/learning_tf2_py目录中输入以下命令来下载示例广播示例代码…

EXCEL数据快速上传至SAP透明表

文章目录 前言一、案例介绍/笔者需求二、备份数据三、数据处理转化 a.EXCEL转为TXT注意事项 b.EXCEL转为TXT 四、ABAP结合内表更新数据至透明表 a.代码实现 b.断点TXT上传至内表 c.查看上传结果 五、总结 前言 这篇文章…

OpenSPG docker 安装教程

文章目录 前言自述 一、OpenSPG1.介绍 二、安装步骤1.安装服务端2.客户端部署 前言 自述 我最近是想结合chatglm3-6b和知识图谱做一个垂直领域的技术规范的问答系统&#xff0c;过程中也遇到了很多困难&#xff0c;在模型微调上&#xff0c;在数据集收集整理上&#xff0c;在知…

【Qt 学习笔记】Qt常用控件 | 输入类控件 | Dial的使用及说明

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt常用控件 | 输入类控件 | Dial的使用及说明 文章编号&#xff1a;Qt…

【intro】GraphSAGE

论文 https://arxiv.org/pdf/1706.02216 abstract 大图中节点的低维embedding已经被证明在各种预测任务中非常有用&#xff0c;然而&#xff0c;大多数现有的方法要求在embedding训练期间图中的所有节点都存在;这些先前的方法属于直推式&#xff08;transductive&#xff09…

女性名字有孤寡数,易离婚

丁老师&#xff1a;您好&#xff01;我孩子&#xff08;女孩&#xff09;准备取名&#xff1a;周小程&#xff0c;宝宝出生于阳历2016年8月13号16时30分左右&#xff0c;准备给孩子取个名字&#xff0c;在网上查询了哈&#xff0c;这个名字的分数还蛮高的&#xff0c;99分&…

Mitmproxy 抓包工具安装使用

简介 Mitmproxy是一个使用python编写的中间人代理工具&#xff0c;跟Fiddle、Charles等等的抓包工具是差不多的&#xff0c;同样可以用于拦截、修改、保存http/https请求。比起Fiddle、Charles&#xff0c;mitmproxy有一个最大的特点是支持python自定义脚本。 安装 Win 官网…

【重塑世界的火种】制造业:从匠人之心到智能未来之旅

在人类文明的宏伟乐章中&#xff0c;有一段旋律始终激昂&#xff0c;它既古老又现代&#xff0c;既是力量的象征&#xff0c;也是智慧的结晶——这就是制造业&#xff0c;一个将梦想变为现实&#xff0c;将创意铸就为生活的神奇领域。今天&#xff0c;让我们一起走进这个塑造世…

【ITK配准】第七期 尺度(Metric)- 均方Metric

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ:870202403 公众号:VTK忠粉 前言 本文分享ITK中的均方Metric,即itk::MeanSquaresImageToImageMetricv4,希望对各位小伙伴有所帮助! 感谢各位小伙伴的点赞+关注,小易会继续努力分享,一起进步! 你的点赞就是我的动力…

携手并进:OpenCSG与博云科技共同探索DevOps的AI化之路

01 DevOps AI化迫在眉睫 数字化转型的浪潮席卷全球&#xff0c;企业对于提升研发效能和软件交付质量的需求日益迫切。在这一背景下&#xff0c;AIGC的发展为DevOps带来了革命性的变化。近日&#xff0c;OpenCSG与云计算解决方案服务商博云宣布建立战略合作伙伴关系&#xff0c…

FebHost:为什么注册法国.FR域名?

注册 .FR 域名&#xff0c;意味着您的网站将主要面向法国市场。法国不仅是欧盟内购买力第二强的经济体&#xff0c;也是全球第七大经济体。值得注意的是&#xff0c;法语是29个国家的官方语言&#xff0c;使用人数约达2.7亿。一旦您拥有了 .FR 域名&#xff0c;就能向这个具有强…

C++算法题 - 二叉树层次遍历

目录 199. 二叉树的右视图637. 二叉树的层平均值102. 二叉树的层序遍历103. 二叉树的锯齿形层序遍历 199. 二叉树的右视图 LeetCode_link 给定一个二叉树的 根节点 root&#xff0c;想象自己站在它的右侧&#xff0c;按照从顶部到底部的顺序&#xff0c;返回从右侧所能看到的节…

Web前端三大主流框架是什么?

Web前端开发领域的三大主流框架分别是Angular、React和Vue.js。它们在Web开发领域中占据着重要的地位&#xff0c;各自拥有独特的特点和优势。 Angular Angular是一个由Google开发的前端框架&#xff0c;最初版本称为AngularJS&#xff0c;后来升级为Angular。它是一个完整的…

全面升级企业网络安全 迈入SASE新时代

随着数字化业务、云计算、物联网和人工智能等技术的飞速发展&#xff0c;企业的业务部署环境日渐多样化&#xff0c;企业数据的存储由传统的数据中心向云端和SaaS迁移。远程移动设备办公模式的普及&#xff0c;企业多分支机构的加速设立&#xff0c;也使得企业业务系统的用户范…

Redis如何保证数据一致性?

Redis如何保证数据一致性&#xff1f; Redis通常作为持久层数据库&#xff08;例如MySQL&#xff09;的缓存层&#xff0c;如果缓存或者数据库数据发生改变&#xff0c;如何保证双方的数据是一致的&#xff1f; 这其实是要分情况讨论滴&#xff0c;对数据一致性不同的要求有不…

Transformer详解:从放弃到入门(完结)

前几篇文章中&#xff0c;我们已经拆开并讲解了Transformer中的各个组件。现在我们尝试使用这些方法实现Transformer的编码器。   如图所示&#xff0c;编码器(Encoder)由N个编码器块(Encoder Block)堆叠而成&#xff0c;我们依次实现。 class EncoderBlock(nn.Module):def …

【求助】鸿蒙DevEco Studio 4.1 Release-模拟器启动方式错误

软件版本&#xff1a;DevEco Studio 4.1 Release 报错提示&#xff1a; 没有权限查看处理指导 Size on Disk 显示1.0MB 尝试方案&#xff08;统统无效&#xff09;&#xff1a; 1、“windows虚拟机监控程序平台”、"虚拟机平台"已开启 启用CPU虚拟化 2、CPU虚…

微服务项目实战-黑马头条(十三):持续集成

文章目录 项目部署_持续集成1 今日内容介绍1.1 什么是持续集成1.2 持续集成的好处1.3 今日内容 2 软件开发模式2.1 软件开发生命周期2.2 软件开发瀑布模型2.3 软件的敏捷开发 3 Jenkins安装配置3.1 Jenkins介绍3.2 Jenkins环境搭建3.2.1 Jenkins安装配置3.2.2 Jenkins插件安装3…

pymysql用法整理--python实现mysql数据库操作

前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 本文着重整理pymsql的常用方法 不专门讲解MySQL数据库的相关知识 常用基本语法汇总 import pymysql#连接数据库 connpymysql.connect(host127.0.0.1,port3306,userroot,password123456,charsetutf8,db"expe…