• 首页

  • 文章归档

  • 友链

  • 关于页面
D u e l s , I S h e e p !
D u e l s , I S h e e p !

ISheep

Code for fun, Make world better

11月
14
大学课程

数据结构笔记

发表于 2019-11-14 • 字数统计 1030 • 被 122 人看爆

Github仓库:My_Ds_Demo

数据的逻辑结构

  • 逻辑结构(logical structure)是指在数据中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型。

    1. 集合结构:集合的数据元素没有其他关系,仅仅是因为他们挤在一个被称作“集合”的盒子里。

    2. 线性结构:线性的数据元素结构关系是一对一的,并且是一种先后的次序,就像a-b-c-d-e-f- g·····被一根线穿连起来。

    3. 树形结构:树形的数据元素结构关系是一对多的,这就像公司的部门级别,董事长-CEO\CTO-技术部\人事部\市场部.....。

    4. 图结构:图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图,一个城市有很多线路连接不同城市。

数据的存储(物理)结构

  • 存储结构(storage structure)也称为物理结构(physical structure),指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构一般可以反映数据元素之间的逻辑关系。分为顺序存储结构和链式存储结构。

    1. 顺序存储结构:是把数据元素存放在一组存储地址连续的存储单元里,其数据元素间的逻辑关系和物理关系是一致的。

    2. 链式存储结果:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的,数据元素的存储关系并不能反映其逻辑关系,因此需要借助指针来表示数据元素之间的逻辑关系。

小结:数据的逻辑结构和物理结构是密切相关的,在学习数据的过程中会发现,任何一个算法的设计取决于选定的数据逻辑结构,而算法的实现依赖于所采用的存储结构。

算法

有穷性、可行性、确定性、输入、输出

时间复杂度

  • 语句频度:该条语句可能重复执行的次数
  • T(n):所有语句的频度之和,其中n为问题的规模
  • 时间复杂度:T(n)=O(f(n)),其中O表示T(n)与f(n)在n->正无穷时为同阶无穷大

规则:

  • 加法规则
  • 乘法规则

常见时间复杂度
$O(1)$<$O(log_2⁡n)$<$O(n)$<$O(nlog_2n)$<$O(n2)$<$O(n3)$<$O(2n)$<$O(n!)$<$O(nn)$

分享到:
数据库理论笔记
  • 文章目录
  • 站点概览
ISheep

🐏 ISheep

放羊么?

Github Twitter Email Telegram RSS
看爆 Top5
  • 2020年终总结 538次看爆
  • 【转载】 2010年的房地产调控,我们收获了什么?写在房价暴涨前 423次看爆
  • 正则表达式入门 415次看爆
  • 搬家 408次看爆
  • 二〇二一 · 迷茫 、恐慌 368次看爆

站点已萌萌哒运行 00 天 00 小时 00 分 00 秒(●'◡'●)ノ♥

Copyright © 2022 ISheep 浙ICP备19046944号

由 Halo 强力驱动 · Theme by Sagiri · 站点地图