数据结构者

数据（data）：可被计算机接受处理的符号总称

数据元素（data element）：数据的基本单位，常作为一个整体进行考虑和处理

一个数据元素可以由若干个数据项（data item）组成

 

数据对象（data object）：性质相同的数据元素集合

 

数据结构（data structure）：相互之间存在特定关系的数据元素集合

 

Data_Structure ＝ ｛D，R｝

Data object（D） + Specific existing relationships（R）

 

逻辑结构：描述数据元素间逻辑关系

物理结构/存储结构：数据结构在计算机中的表示

 

按某种物理结构存储数据时，要能恢复其逻辑结构

 

数据类型（data type）：值集合和值集合上操作的总称

 

原子类型（atom type）

结构类型（structure type）

作用：实现信息隐藏

 

抽象数据类型（abstract data type）：（数据类型是抽象数据类型的物理实现）数据类型的延伸（值集合和值集合上的操作/数学模型和模型上的操作），是一个三元组，（D，R，P）

P -＞ 对数据的操作/处理

抽象在何处：不关注其物理实现，抓住本质，忽略细节

例如：语文成绩，不关注是浮点还是整型

 

集合结构（sets）：none specific relationship

线性结构（linear）

树形结构（tree structure）

可将树组织成堆（heap）

图结构（graph）

网（net）：带权图

 

 

线性表（linear list）：逻辑结构

顺序表和链表是常用的实现线性表的数据结构

堆栈与队列（stack queue）：有特定特征的线性表，两种数据结构

字符串（String）：特殊的线性结构，以字符为元素

不讲也不考

 

树（tree）：逻辑上表示结点层次关系的非线性结构

 

graph/net：一个结点集合和一个边集合

 

 

 

算法（algorithm）：为解决问题的一系列操作

特征：

finity（有限）

certainty（确定/无二义）

feasibility（可行）

input（输入）

output（输出）

 

设计要求：

正确correctness（对几组数据/对苛刻数据/对所有合法数据）

可读性（readability）

健壮性（robustness）（处理异常情况）

efficiency and low storage（高效低耗）

 

算法分析：

事后统计法（empirical comparison）：

缺陷（disadvantage）：

必须先运行程序/依赖于计算机软硬件环境等因素（vary with the environment）

 

事前估计法（asymptotic algorithm analysis）：

因素（factors）：

a.算法策略（strategy of algorithm）

b. 问题的规模（scale of problem itself）

c. 编程语言

d.  编译程序产生的机器码质量（quality of machine code after compilation）

e. 机器指令执行速度(speed of machine instruction)

 

语句频度总数-＞时间复杂度

辅助空间-＞空间复杂度

 

算法上界（upper bound/worst）和下界（lower bound/best）

average case

O表示上界

 

 

 

数据结构是算法处理的对象，也是设计算法的基础

 

 

 

顺序表（sequential list）

线性表的一种实现，存储在连续空间，亦称向量

计算地址：略

 优缺点

 

链表（linked list）：

第二种链表结构：Head node用来记录元信息

H-＞head-＞next才表示第一个有效元素

 

 

静态链表（static linked list）：

 

 

 静态链表即不想在插入/删除时，大规模移动元素

又不想像普通链表一样存储密度较低，所以使用int cursor（冰云：其实感觉和普通链表比没什么绝对优势）

 

 

内存管理：

用链式结构管理

 

例题：

 

 

环形链表：

下图第一个：head执行第一个有效结点

下图第二个：head指向头结点

 

 

 

双链表：

 

 

 

栈（stack）（限定性线性表）

将入栈/进栈，出栈/退栈操作仅允许在栈顶

又称：LIFO表（Last In First Out）

 

顺序栈：用地址连续的存储单元依次存储元素

 

多栈共享技术

一个程序同时使用多个栈时，可能出现有的栈溢出，有的栈空闲的情况，分配不均，且无法动态调整

故产生多栈共享技术

 

双端栈：两个栈的共享技术

两个栈的栈底分置一维数组两端，栈顶动态变化

 

链栈：以链表作为存储结构

不用预估栈的最大容量，系统空间足够，则链栈不会溢出

 

采用多个链表实现多个链栈

将多个链栈的栈顶指针放在一维数组中统一管理

冰云：hashmap

 

队列

防止队列假满：

1：循环队列

2：队列动态扩展