数据结构(1):线性表

1 线性表的顺序实现

创建的新项目是cpp类型哦!

1.1 初始化

1.1.1  静态分配

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>
#define MaxSize 10 //定义顺序表的长度
typedef struct {int data[MaxSize];//用静态的数组存放元素!int length;
}SqList;
//相当于python中的类,这个类有一个属性是 长度//基本操作--初始化一个顺序表
void InitList(SqList& L) {for (int i = 0; i < MaxSize; i++) {L.data[i] = 0;}//初始化每一个值为0L.length = 0;
}//主函数
int main() {SqList L;//创建一个顺序表InitList(L);//初始化一个顺序表!!!return 0;
}

脏数据!

1.1.2 动态分配

1.2 基本操作【基于静态分配】

1.2.1 插入

1.2.2 删除操作

1.2.3 查找

【1】按位查找

静态分配:

动态分配:

注意指针!!!

【2】按值查找

数据是结构类型的时候比较不能用==

c语言程序设计!

2 线性表的链式表示-单链表

2.1 单链表的定义

用代码实现,带头结点/不带头结点,一般使用带头结点

代码实现:

【1】长一点的写法

【2】

2.2 初始化

2.2.1 不带头结点

2.2.2 带头结点

头结点不存储数据,

不带头结点那么这个头指针指向的就是实际用于存放数据的结点

而带头结点 这个头指针指向的是头结点 这个结点不存放数据,这个头结点之后的下一个结点才会用于存放数据!!!

2.3 按位序插入

2.3.1 带头结点

当i=1时

2.3.2 不带头指针

要对第一个结点做单独的处理!

2.4 给定结点在结点之后插入

时间复杂度o(1)

2.5 给定结点之前插入【前插】

2.5.1 方法一:传入头指针

o(n)

利用头阶段找到给定节点的前区结点!

2.5.2 方法二:偷天换日

时间复杂度0(1)

2.6 按位序删除

平均:o(n)

2.7 删除给定结点

偷天换日

如果p是最后一个结点的话:【只能采用方法一来弄!】

2.8 查找

2.8.1 按位查找

平均时间复杂度:o(n) 顺序表的按位置查找

可以封装起来,在插入和删除里进行调用!!

2.8.2 按值查找

o(n)

2.9 表的长度

2.10 建立单链表

2.10.1 尾插法建立

这样的问题是每次都要遍历到找到最后一个元素,那么时间复杂度就是0+1+2+3+.....+(n-1)这样的话时间复杂度就是o(n^2)

太高了,引入尾指针!

9999就是一个特殊的出口

时间复杂度就是o(n)

2.10.2 头插法

写代码的时候 去掉的那句写上就是好习惯!!!

头插法最后得到的是逆序的链表!

3 顺序表的链式表示-双链表

3.1 初始化

3.2 插入--后插

更严谨一点:

修改指针的顺序一定要先后面再前面

3.3 删除

3.4 销毁

3.5 遍历

注意指针修改的顺序!!!

注意边界的情况!!!

4 循环单链表

4.1 初始化

在删除的时候找不到前驱结点

找到最后一个结点

L指针放在表尾的时候就会 自己指向的是尾结点,下一个是头结点,当应用场景是要频繁的使用头结点和尾结点的时候,就把指针放在最后!

5 循环双链表

插入:

删除:

循环双链表不用考虑最后一盒结点

6 静态链表

初始化:

用数组存放,书本上的写法后面:

基本操作:

初始化:

查找某个位序的节点时间复杂度o(n)

插入:

空闲标记成-2

尽管是一整片连续的区域,但是各个在逻辑上相邻的元素在物理上也可以不相邻!

先后关系是通过游标实现的!

文件分配表FAT就是静态链表!

7 链表和顺序表比较

奶茶店排队取号

查询操作比较多,课堂点名

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

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

相关文章

目标检测 | R-CNN、Fast R-CNN与Faster R-CNN理论讲解

☀️教程&#xff1a;霹雳吧啦Wz ☀️链接&#xff1a;https://www.bilibili.com/video/BV1af4y1m7iL?p1&vd_sourcec7e390079ff3e10b79e23fb333bea49d 一、R-CNN R-CNN&#xff08;Region with CNN feature&#xff09;是由Ross Girshick在2014年提出的&#xff0c;在PAS…

基于文本来推荐相似酒店

基于文本来推荐相似酒店 查看数据集基本信息 import pandas as pd import numpy as np from nltk.corpus import stopwords from sklearn.metrics.pairwise import linear_kernel from sklearn.feature_extraction.text import CountVectorizer from sklearn.feature_extrac…

蓝桥杯-AB路线(详细原创)

问题描述&#xff1a; 有一个由 N M 个方格组成的迷宫&#xff0c;每个方格写有一个字母 A 或者 B。小蓝站在迷宫左上角的方格&#xff0c;目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。 由于特殊的原因&#xff0c;小蓝的路线必须先走 K 个 A 格子、再…

java高级——Collection集合之List探索(包含ArrayList、LinkedList、Vector底层实现及区别,非常详细哦)

java高级——Collection集合之List探索 前情提要文章介绍提前了解的知识点1. 数组2. 单向链表3. 双向链表4. 为什么单向链表使用的较多5. 线程安全和线程不安全的概念 ArrayList介绍1. 继承结构解析1.1 三个标志性接口1.2 AbstractList和AbstractCollection 2. ArrayList底层代…

刷爆leetcode第六期

题目一 用队列实现栈 请你仅使用两个队列实现一个后入先出&#xff08;LIFO&#xff09;的栈&#xff0c;并支持普通栈的全部四种操作&#xff08;push、top、pop 和 empty&#xff09;。 实现 MyStack 类&#xff1a; void push(int x) 将元素 x 压入栈顶。 int pop() 移除…

MVC架构中的servlet层重定向404小坑

servlet层中的UserLoginServlet.java package com.mhys.servlet; /*** ClassName: ${NAME}* Description:** Author 数开_11* Create 2024-05-29 20:32* Version 1.0*/import com.mhys.pojo.User; import com.mhys.service.UserService; import com.mhys.service.impl.UserSer…

Paddle使用问题No module named ‘paddle.fluid’

这是Paddle版本的问题&#xff0c;从飞桨框架 2.5 版本开始&#xff0c;已经废弃了 paddle.fluid 。 ​解决方案&#xff1a;修改paddle版本 pip install paddlepaddle2.4.0

2.1色彩空间

色彩发送器 色彩认知 光源是出生点&#xff0c;光源发射出光线&#xff0c;光线通过直射反射折射等路径最终进入人眼。 但人眼接收到光线后&#xff0c;人眼的细胞产生了一系列化学反应。 由此把产生的信号传入大脑&#xff0c;最终大脑对颜色产生了认知感知。 光的要素 光…

汽车IVI中控开发入门及进阶(二十一):DAB和FM 收音机

前言: 在过去的十年里,数字收音机对车载娱乐产生了重大影响。现在,几乎每辆新车都标配了这项技术,这也是我们60%以上的人收听收音机的方式。甚至有传言称,在不久的将来,将永久关闭调频发射机,使许多车载收音机过时。但一些相对年轻的汽车在工厂里仍然没有安装DAB,而且…

UG NX二次开发(C#)-UFun函数-利用UFPart.Export导出模型中的对象并创建一个新的part

文章目录 1、前言2、UF_PART_export函数定义3、UF_PART_export_with_options函数定义4、代码1、前言 在UG NX 10.0二次开发中,需要用到将装配体中通过几何建模创建的对象独立创建一个part文件,所以查找了下UFun函数,即是UF_PART_export 和UF_PART_export_with_options两个函…

J.搬砖【蓝桥杯】/01背包+贪心

搬砖 01背包贪心 思路&#xff1a;要让重量更小的在更前面&#xff0c;价值更大的在更后面&#xff0c;vi−wj>vj−wi viwi>vjwj 第 i 个箱子放在第 j 个箱子下面就显然更优。所以进行排序再用01背包即可。 #include<iostream> #include<algorithm> #defi…

洗地机哪个牌子最好用?十大名牌洗地机排行榜

作为一种新兴的智能家居产品&#xff0c;洗地机的市场规模已经突破了百亿大关。如此庞大的市场自然吸引了大量资本的涌入&#xff0c;许多品牌纷纷推出自己的洗地机产品&#xff0c;试图在这个竞争激烈的市场中占据一席之地。然而&#xff0c;面对如此多的品牌和型号&#xff0…

检索字符串

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 在Python中&#xff0c;字符串对象提供了很多应用于字符串查找的方法&#xff0c;这里主要介绍以下几种方法。 &#xff08;1&#xff09;count()方…

JRT性能演示

演示视频 君生我未生&#xff0c;我生君已老&#xff0c;这里是java信创频道JRT&#xff0c;真信创-不糊弄。 基础架构决定上层建筑&#xff0c;和给有些品种的植物种植一样&#xff0c;品种不对&#xff0c;施肥浇水再多&#xff0c;也是不可能长成参天大树的。JRT吸收了各方…

FFMPEG+ANativeWinodow渲染播放视频

前言 学习音视频开发&#xff0c;入门基本都得学FFMPEG&#xff0c;按照目前互联网上流传的学习路线&#xff0c;FFMPEGANativeWinodow渲染播放视频属于是第一关卡的Boss&#xff0c;简单但是关键。这几天写了个简单的demo&#xff0c;可以比较稳定进行渲染播放&#xff0c;便…

vue3 使用vant

使用前提&#xff1a; vite创建的vue3项目 vanthttps://vant-ui.github.io/vant/#/zh-CN/home npm i vant 引入样式&#xff1a; main.js import vant/lib/index.css vant封装 import { showLoadingToast,closeToast,showDialog,showConfirmDialog } from vant;export func…

分布式版本控制工具 git

git 是什么 分布式版本控制工具。github 是代码托管平台。 git 有什么用 保存文件的所有修改记录。使用版本号&#xff08;sha1 哈希值&#xff09; 进行区分。随时可浏览历史版本记录。可还原到历史指定版本。对比不同版本的文件差异。 为什么要使用 git 多人协作开发一个大…

【Linux学习】进程

下面是有关进程的相关介绍&#xff0c;希望对你有所帮助&#xff01; 小海编程心语录-CSDN博客 目录 1. 进程的概念 1.1 进程与程序 1.2 进程号 2. 进程的状态 2.1 fork创建子进程 2.2 父子进程间的文件共享 3. 进程的诞生与终止 3.1 进程的诞生 3.2 进程的终止 1. 进…

K8S认证|CKA题库+答案| 15. 备份还原Etcd

目录 15、 备份还原Etcd CKA v1.29.0模拟系统 下载试用 题目&#xff1a; 开始操作: 1&#xff09;、切换集群 2&#xff09;、登录master并提权 3&#xff09;、备份Etcd现有数据 4&#xff09;、验证备份数据快照 5&#xff09;、查看节点和Pod状态 6&#xff0…

【数据结构:排序算法】堆排序(图文详解)

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;数据结构课程学习 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 &#x1f369;1.大堆和小堆 &#x1f369;2.向上调整算法建堆和向下调整算法建堆&#xff1a;…