数据结构笔记1:绪论
Table of Contents
数据结构基本概念:
数据:
- 数据对象:数据的子集-具有相同性质(所有员工)
- 数据元素:数据的基本单位-每一个对象的信息(每个员工)
- 数据项:构成数据元素(员工姓名、年龄)
数据类型(集合+操作):
- 原子类型:值的集合+操作(int)
- 结构类型(list)
- 抽象数据类型ADT:数据对象+数据关系+操作(模型)
数据结构
相互存在关系的数据元素的集合
结构=关系
数据结构3要素:
逻辑结构、物理结构、数据运算
逻辑结构:
线性结构、集合、树形结构、图状结构(多对多)
存储结构=物理结构(计算机内-包括数据,及其关系):
顺序存储、链式存储、索引存储、散列存储
顺序存储:逻辑相连,物理也相连。(特点:可随机存储,想拿哪个拿哪个)
链式存储:存放下一个元素的地址(顺序存储,无法随机存储)
索引存储:索引表存放关键字,及其对应地址(索引表消耗内存)
散列存储=哈希存储:通过关键字函数计算得地址
数据运算:
定义(逻辑)+实现(存储)
算法
基本概念
求解问题指令的有限序列
算法五特性:有穷、可行(可以实现为代码)、确定性(无二义性)、输入、输出
算法(指导)与程序(实施)区别:
有穷性:算法有穷,程序无穷
正确性:算法正确,程序可错
描述方法:算法伪代码框图和代码,程序-代码
效率度量
正确性,可读性、健壮性(输入非法时反应)、效率与存储量(时间、空间)
空间复杂度
时间复杂度
语句频度:重复次数
T(n):所有语句频度和,n为问题规模
时间复杂度:T(n)=O(f(n))当n->无穷时f的同阶无穷大
最坏、最好、平均
求解规则
加法规则:相加时取阶大的
乘法规则:先求数量级乘积,再求同阶无穷大
基本运算频度:最深层循环
主要取最大的两个时间复杂度
空间复杂度
S(n)=O(g(n))
除了常数、变量、输入数据外的存储空间
题目
数据结构
- 抽象数据类型ADT可定义完整数据结构,抽象数据类型=数据对象(数据)+关系(结构)+操作(可读可写)
- 线性结构特点:有首有尾,除了收尾其他有唯一前驱后继
- 4.顺序表、哈希表、单链表既描述了逻辑又描述了存储、运算,循环队列属于顺序表。有序表、线性表、栈是纯粹的逻辑结构
6.存储数据时要存储数据对象、关系,不需要存储操作,存储数据结构才需要
7.链式存储结点内部的存储单元地址必须连续
9.顺序表、链表都是线性表。顺序存储方式插入删除时间复杂度O(n),链式存储O(1)
算法
- 定义和特点区分
- 问题规模:n,执行时间与时间复杂度n^2成正比
- 算时间复杂度:(1)找最深层循环(2)求执行次数最大阶
第t次循环i的值:2^t<=n,t<=log2 n
- 第k轮:x=2^(k+1)<=n/2, 2^(k+2)=n, k=log2 n-2
- 递归
- 链表升序变降序,用头插法。升序变升序用尾插法
链表插入时最重要的是先把新元素的next存入指针,再修改原表中的指针,防止断链
O(max(m,n))=O(m+n)
7.
10.排序目标是升序,最坏情况为倒序。每次检查都换位。第一轮结束后,相当于把第一个数挪到最后,其他序列不变。执行次数为:n+(n-1)+…+1
11.也是等差数列
12.算法原地工作:O(1)需要常数个辅助空间,不是不需要。
算法在时间上优于另一个算法,特例不构成反例。
时间复杂度:最坏情况
13.求时间复杂度T(n)的通项,代入2^k得到递推公式