Category - 数据结构

Untitled
2024-03-26 17:25:28    21    0    0

线性表的抽象数据类型

  1. ADT 线性表List（）
  2. DATA
  3.     （对于线性表的文字描述、线性表的数据对象集合为{a1,b1,c1,..}每个元素类型均为xxx...）
  4. Operation
  5.     InitList(*L):初始化操作，建立一个空的线性表L
  6.     ListEmpty(L):判断线性表是否为空表、若线性表为空、返回true、反之返回false
  7.     ClearList(*L):将线性表清空
  8.     getElem(L,i,*e)：将线性表L中的第i个位置元素值返回给e
  9.     LocateElem(L,e):在线性表中查找与给定值e相等的元素、如果查找成功、返回该元素在表中序号表示成功、否则，返回0表示失败（这里注意数据结构中讨论的数组是从1开始的、所以失败返回0）
  10.     ListInsert(*L,i,e):在线性表L中第i个位置插入新元素e
  11.     ListDelete(*L,i,*e):删除线性表L中第i个位置元素，并用e返回其值
  12.     ListLenght(L):返回线性表L
  13. endADT

对于不同的应用、线性表基本操作是不同的、
具体问题具体解决

时间复杂度
2024-03-26 17:25:28    29    0    0

我们假设计算机运行一行基础代码需要执行一次运算。

  1. int aFunc(void) {
  2.     printf("Hello, World!\n");      
  3.     return 0;       
  4. }

那么上面这个方法需要执行 2 次运算

  1. int aFunc(int n) {
  2.     for(int i = 0; i<n; i++) {         
  3.         printf("ßßHello, World!\n");      
  4.     }
  5.     return 0;     
  6. }

这个方法需要 (n + 1 + n + 1) = 2n + 2 次运算。

我们把 算法需要执行的运算次数 用 输入大小n 的函数 表示，即 T(n) 。
此时为了 估算算法需要的运行时间 和 简化算法分析，我们引入时间复杂度的概念。

定义： 存在常数 c，使得当 N >= c 时 T(N) <= f(N)，表示为 T(n) = O(f(n)) 。
如图：
title

当 N >= 2 的时候，f(n) = n^2 总是大于 T(n) = n + 2 的，于是我们说 f(n) 的增长速度是大于或者等于 T(n) 的，也说 f(n) 是 T(n) 的上界，可以表示为 T(n) = O(f(n))。

因为f(n) 的增长速度是大于或者等于 T(n) 的，即T(n) = O(f(n))，所以我们可以用 f(n) 的增长速度来度量 T(n) 的增长速度，所以我们说这个算法的时间复杂度是 O(f(n))。

算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。

显然如果 T(n) = n^2，那么 T(n) = O(n^2)，T(n) = O(n^3)，T(n) = O(n^4) 都是成立的，但是因为第一个 f(n) 的增长速度与 T(n) 是最接近的，所以第一个是最好的选择，所以我们说这个算法的复杂度是 O(n^2) 。

那么当我们拿到算法的执行次数函数 T(n) 之后怎么得到算法的时间复杂度呢？

我们知道常数项对函数的增长速度影响并不大，所以当 T(

数据结构和算法笔记 - 45 二叉树II
2024-03-26 17:25:28    22    0    0

在二叉树的第i层上至多有2^（i-1）个节点

二叉树的性质2：深度为k的二叉树至多有2^k-1个节点

二叉树性质3：对于任何二叉树T、如果其终端结点数为n0，度为2的节点数为n2，则n0=n2+1

数据结构和算法笔记 - 44 二叉树I
2024-03-26 17:25:28    17    0    0

二叉树 (Binary Tree) 是n(n >= 0)个节点的有限集合
该集合或者为空集（空二叉树），或者由一个根节点和两颗互不交叉的、分别称为根节点的额左子树和右子树的二叉树组成

这个定义显然是递归形式的、

每个节点 最多可以有2个子树

左子树和右子树是有顺序的、次序不能颠倒

即使树种只有一颗子树、也要区分是左子树和右子数

下面这两个是完全不同的二叉树
A A
/ \
B B

二叉树五种基本形态
·空二叉树
·只有一个根节点
·根节点只有左子树
·根节点只有右子树
·根节点既有左子树又有右子树

特殊二叉树：
-斜树
-满二叉树 所有分支结点都存在左子树和右子树
满二叉树的特点有：
而且满二叉树的叶子只能出现在最下层
非叶子节点的【度】一定是2
在同样深度的二叉树中、满二叉树的节点个数一定最多、同时叶子也是最多的

对一棵树具有n个节点的二叉树按层序编号，如果编号为i（1<=i<=n）的节点与同样深度的满二叉树相同、则这颗二叉树称为完全二叉树

  1. 完全二叉树的特典：
  2.     -叶子节点只能出现在最下两层
  3.     -最下层的叶子一定几种在左部连续位置
  4.     -倒数第二层、若有叶子节点、一定在右部连续位置
  5.     -如果节点的度为1，则该节点只有左孩子
  6.     -同样节点数的二叉树、完全二叉树的深度最小
  8. 注意：满二叉树一定是完全二叉树、但完全二叉树不一定是man
数据结构和算法笔记 - 10 线性表V
2024-03-26 17:25:28    21    0    0

头指针
-是指链表指向第一个节点的指针、
-头指针具有标识作用、所以常用头指针冠以链表的名字（指针变量的名字）
-无论链表是否为空、头指针均不为空
-头指针是链表的必要元素

头节点
-头结点是为了操作的统一和方便而设立的，
放在第一个元素的节点之前、其数据域一般无意义（但也可以用来存放链表的长度）
-有了头结点、对在第一元素节点前插入节点和删除第一节点起操作与其他节点的操作就同意了
-头节点不一定是链表的必须要素

  1. 单链表图
  3.     头指针
  4.     ——————> [头节点|  ]——————> [a1|  ]
  7. 空链表图例
  9.     头指针
  10.     ——————> [头节点|  ]——————> null

单链表的读取
对于单链表实现获取第i个数据的算法思路：（GetElem）
- 声明一个节点p指向链表第一个节点，初始化j从1开始；

数据结构和算法笔记 - 9 线性表IV
2024-03-26 17:25:28    35    0    0

在线性表
插入和删除操作

因为顺序存储的线性表中间插入和删除操作都要位移

所以

最好的情况、
插入和删除 操作的是最后的一个元素
时间复杂度是O(1)

最差的情况

就是第一个元素操作、 时间复杂度是O(n)

平均值O((n-1)/2)

根据简化规则
就为O(n)

结论 线性表的顺序存储结构、
读写 任何位置都是 O(1)
插入删除时 时间复杂度都是O(n)

优缺点：
优点：
存储中无虚位、无需为了表示元素之间的逻辑关系而增加额外的存储空间。可以快速的存取表中数据

缺点：
插入和删除操作需要移动大量元素
当线性表长度变化较大时、难以确定存储空间容量。 容易造成存储空间的碎片

链式存储的线性表

用一组任意的存储单元存储线性表的数据元素、这组存储单元可以存在内存中未被占用的任意位置
需要存储一个它的后继元素地址（指针）

我们把存储数据元素信息的域称之为数据域、把存储直接为后继位置的域称之为指针域。指针域中存储的信息成为指针域或者链。
这两部分信息组成的数据元素成为存储映像，称为节点（Node）

——————————————————————————————————————————————
单链表

如果每个节点中只包含一个指针域、所以交作单链表

我们把链表中的第一个节点的存储位置叫做头指针、
最后一个节点指针为空（null）

数据结构和算法笔记 - 8 线性表III
2024-03-26 17:25:28    23    0    0

线性表的顺序存储结构

指的是一段连续的存储单元依次存储线性表的数据元素

顺序存储结构封装需要三个属性
存储空间的起始位置、数组data、他的存储位置就是线性表存储空间的存储位置

线性表的最大存储容量：数组的长度MaxSize

线性表的当前长度：length

地址计算方法

定义 LOC(xxx)就是获取存储位置的函数、c是一个存储单元宽度

  1. LOC(ai+1) = LOC(ai) + c

所以对于第i个数据元素ai的存储位置可以由ai推算得出

  1. LOC(ai)=LOC(ai)+(i-1)*c

他存储的时间复杂度为O(1)，一般来说O(1)的就是随机存储结构

实现GetElem的具体操作

数据结构和算法笔记 - 5 时间复杂度和空间复杂度III
2024-03-26 17:25:28    32    0    0

函数调用的时间复杂度分析
常用的时间复杂度 所耗时间从小到大对比

  1. O(0)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

——————————————————————————————————————
概念

平均运行时间、
最坏运行时间

——————————————————————————————————————————
算法的空间复杂度

也就是存储空间和运算复杂程度的取舍

S(n) = O(f(n))

数据结构和算法笔记 - 6 线性表I
2024-03-26 17:25:28    26    0    0

线性表(List):有0个或者读个数据元素组成的有限数列
· 他是一个数列、有先来后到
· 任何一个元素 只有一个前驱和后继。
· 有限的

  1. 线性表元素个数n(n>=0)
  2. 当n=0 就是空表

数据类型
原子类型：不可以再分解的基本类型、
结构类型：由若干个类型组合而成

抽象数据类型（ADT）
抽象数据类型的定义仅取决于他的一组逻辑特性，与其在计算机内部如何表示和实现无关。

  1. 比如在3d游戏中 把  x、y、z整合在一起抽象成一个point类型
  3. 数据结构描述抽象数据类型的
  4. ADT：抽象数据类型
  5. Data
  6.     数据元素之间逻辑关系的定义
  7. Operation
  8.     操作
  9. endDAT
数据结构和算法笔记 - 4 时间复杂度和空间复杂度II
2024-03-26 17:25:28    18    0    0

在算法分析时、
语句总执行次数T(n)是关于问题规模n的函数、
进而分析T(n)随着n的变化情况并确定T(n)的数量级

算法的时间复杂度、也就是算法的时间量度
记做 T(n)=O(f(n))

他表示随着规模n的增大、算法执行时间的增长率和f（n）的增长率想用、曾作算法的渐进时间复杂度。其中f(n)是问题规模n的某个函数。

用大写O()来体现算法时间复杂度的记法、可叫做大O记法

一般情况下 随着输入规模n增加
T(n)增长最慢的算法 最为优先

——————————
推导大O阶方法

  • 用常数1取代运行时间中的又有加法常数
  • 在修改后的运行次数函数中、只保留最高项
  • 如果最高阶创业板在且不是1、则去除与这个项相乘的常数
  • 得到最后的结果就是大O阶、也就是时间复杂度

线性阶

一般含有非嵌套循环涉及线性阶、线性阶就是随着问题规模n的扩大而扩大
O（n）

平方阶

含有嵌套循环的程序
比如 n次循环嵌套一个循环n次的循环 时间复杂度为O(n^2)

循环的时间复杂度 = 循环体的复杂度乘以该循环的运行次数

对数阶

int i=1,n=100;
while(i < n)
{
i = i * 2;
}

其实i就是2的指数、多少次方的结果能够不比n小
就循环完毕

求多少次方 就是对数

所以循环次数 为 log(2)n

所以时间复杂度为O(logn)

1/2
Proudly powered by Leanote