基础数据结构-绪论(一)

基础数据结构-绪论(一)> 指数阶空间复杂度算法空间复杂度是通过计算算法所需的存储空间实现,算法空间复杂度的计算公式:S),其中,n为问题的规模,f换成高斯算法,

欢迎大家来到IT世界,在知识的湖畔探索吧!

数据结构-绪论(一)

  1. 存储
  2. 数据结构
  3. 算法
  4. 概述

数据结构-线性表(二)

  1. 数组
    1. 删除
    2. 插入
    3. 交换
    4. 移动
  2. 链表
    1. 单/双,循环,静态链表
    2. 单链表逆序
    3. 单链表的,从尾部输出(单次遍历)
    4. 求单链表的中间节点(不知道链表的长度)
    5. 单链表求得倒数第K个元素
    6. 单链表插入排序
    7. 两个顺序单链表的,合并(顺序)
    8. 两个单链表的,公共点
    9. 判读单链表是否带环
    10. 求环的长度
    11. 得到环的切入节点
    12. 求带环链表的长度
    13. 求出环中的任意,节点的最长距离节点
    14. 求带环链表的相交点
    1. 递归
    2. 共享栈
    3. 斐波那契数列
    4. 用两个栈,实现一个队列
    5. 求最新栈元素,要求时间复杂度是O(1)
    6. 一个数组实现两个栈,本质上就是顺序存储的共享栈
    7. 如何实现逆序栈
    8. 如何实现栈的排序
    9. 内存栈的构成,栈区和堆区的说明
  3. 队列
    1. 循环队列
    2. 优先队列
    3. 两个队列实现,栈
    4. 猫狗队列

数据结构-串(三)

  1. KMP模式匹配算法
  2. BM算法
  3. Sunday算法
  4. 最长公共子串

数据结构-树(四)

  1. 搜索二叉树
  2. 红黑树
  3. B+树
  4. B-树
  5. 默克尔树
  6. 赫夫曼树

数据结构-图(五)

  1. 广度优先遍历
  2. 深度优先遍历
  3. 最小生成树-Prim(普利姆算法)
  4. 最小生成树-Kruskal(克鲁斯卡尔)
  5. 最短路径-Dijkstra(迪杰特斯拉)
  6. 最短路径-Floyd(弗洛伊德算法)
  7. A*路径搜索算法
  8. 关键路径算法

基础数据结构,总共分为5篇文章,依次来介绍说明,今天介绍第一篇绪论

数据结构-绪论

  • 存储
  • 数据结构
  • 算法
  • 程序 = 数据结构 + 算法;

    一切程序的来源都是数据之间的关系存储。

    1、数据是什么呢?

    数据,通俗的讲就是整型123,字符串ABC等数值类型,以及声音,图片,视频等等,最终以二级制数据存储到磁盘中;数据是计算机操作的对象,所有可输入的处理符号,且可被计算机识别的对象都成为数据

    数据元素:是一个数据的集合,也成为”记录”

    数据项:一个数据元素由若干个数据项组成

    数据对象:性质相同的数据元素的集合

    数据关系:相互之间存在的一种或是多种关系的数据元素集合

    2、数据之间的关系有哪些?

    基础数据结构-绪论(一)

    无关系

    基础数据结构-绪论(一)

    一对一关系

    基础数据结构-绪论(一)

    一对多关系

    基础数据结构-绪论(一)

    多对多关系

    3、算法及与数据结构之间的关系?

    算法是解决问题求解步骤的描述,一条条的序列指令的步骤集合;

    就像,如何炒一盘菜?

    那么算法就可以理解为“菜谱”,那么数据结构就可以理解为“食材”,有了食材,有了菜谱,才能做出一份“程序”

    接下来分别描述一下,数据结构和算法

    数据结构

    数据结构,也就是数据之间的关系,分为结构:逻辑结构和物理结构(也就是如何存储的)

    • 逻辑结构
    1. 集合结构 == 无关系
      1. 定义:数据元素之间没有关系,只是存储在一个集合
      2. 特点:数据元素是平等的
    2. 线性结构 == 一对一的关系
      1. 定义:数据元素之间是一对一线性关系
      2. 特点:每个数据元素都有前驱或是后驱
    3. 树形结构 == 一对多的关系
      1. 定义:数据元素之间是一对多的层次关系
      2. 特点:数据元素都有一个前驱或多个后驱
    4. 图形结构 == 多对多的关系
      1. 定义:数据元素之间是多对多的关系
      2. 特点:数据元素之间相互之间
    • 存储结构

    又叫做物理结构,是指数据元素的逻辑结构在计算机中的存储形式。

    1. 顺序存储结构
      1. 定义:是把数据元素存放在连续的存储单元里
      2. 例如:创建一个长度为10的整型数组,计算机就在内存中,按照一个整型(4个Btye)所占位置的大小乘以9,开辟一段连续的空间,然后第一个数据元素放在第一个位置,第二个数据放在第二个位置,依次存放
      3. 特点:开辟的空间是连续的,索引查询比较快,会浪费多余的空间,需要预制数据元素的大小,空间扩展比较麻烦,插入/删除数据元素,则需要大量元素跟着移动
    2. 链式存储结构
      1. 定义:是把数据元素发在任意的存储单元里,每个数据元素中含有其对应逻辑关系的存储地址,也就是链式存储结构在分配空间的时候不是连续的,当然了也可以是连续的
      2. 例如:现在医院排队系统,每个人过去先领取一个号,等着叫好,叫到的时候去看病,在等待的时候,可以爱去哪儿去哪儿;“号”就是一个指针存放数据元素的地址,通过“号”找到关联数据元素的位置
      3. 特点:插入/删除数据元素比较灵活,查询效率较低,数据元素复杂的关系用链式存储可以更好的表示

    算法

    算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条特定指令都表示一个或多个操作

    • 特性
    1. 正确的输入和输出
    2. 有穷性
    3. 确定性
    4. 可行性
    • 设计要求
    1. 正确性
    2. 可读性
    3. 健壮性
    4. 时间复杂度低和空间复杂度低
    • 时间复杂度

    定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随着n的变化情况并确定T(n)的数量级,算法的时间复杂度,就是算法的时间量度T(n)=O(f(n))

    常数阶 > 对数阶 > 线性阶 > nLogn阶 > 平方阶 > 立方阶 > 2^n > N! > 指数阶

    • 空间复杂度

    算法空间复杂度是通过计算算法所需的存储空间实现,算法空间复杂度的计算公式:S(n) = O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占用的存储空间的函数

    例如:求证1+2+3+4+…+100?

    基本的算法,遍历1到100个数,进行相加,时间复杂度O(n)

    换成高斯算法,时间复杂度O(1)

    1 + 2 + 3 + … + 98 + 99 + 100 = a;

    100 + 99 + 98 + … + 3 + 2 + 1 = a;

    上面两个表达式相加求证:2a =(100 + 1)* 100

    a =(100 + 1)* 100 / 2

    那么求,∑i = 1+2+3+…+n,得出∑i =(n + 1)* n/ 2

    就好像上面说的算法,就像炒菜的菜谱(算法),在一定的食材(数据)中,如何做出一份又快又好吃的饭菜;

    数据结构和算法

    线性表

    免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/30105.html

    (0)

    相关推荐

    发表回复

    您的邮箱地址不会被公开。 必填项已用 * 标注

    联系我们YX

    mu99908888

    在线咨询: 微信交谈

    邮件:itzsgw@126.com

    工作时间:时刻准备着!

    关注微信