数据结构复习

数据结构在学什么？

如何利用程序代码把现实世界的问题信息化，

什么是数据？

数据是信息的载体，描述客观事物属性的数、字符及所有能输到计算程序识别和处理的符号的集合。

什么是数据对象

具有相同性质对象的数据元素集合，是数据一个子集。

什么是数据结构

相互之间存在一种或者多种特定关系的数据元素集合

数据结构三要素

逻辑结构：集合、线性、树形、图状
数据运算：针对某种逻辑结构，结合实际需求，定义基本运算
物理结构：如何用计算机实现这种数据结构
数据的存储结构：（如何用计算机表示数据逻辑关系）
顺序：逻辑物理都连续
链式：逻辑连续，物理可以不相邻
索引：建立索引表（关键字+地址）可以离散
散列： hash 存储
数据存储结构影响存储空间分配，数据运算速度

数据类型

值的集合和定义在此集合上一组操作
原子类型：（bool，int）
结构类型（struct）值可以再分解若干成分

抽象数据类型

抽象数据组织与之相关的操作

什么是算法

程序 =数据结构 + 算法
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或者多个操作
算法特性：
有穷性：一个算法执行有穷步后结束，每一步在有穷时间完成，（程序可以无穷）
确定性：算法中每条指令有确切的含义，对于相同的输入只能得出相同的输出
可行性：算法中描述操作可以通过已经实现基本运算执行有限次数来实现
输入：一个算法中有零个或者多个输入，这些输入取自某个特定对象的集合
输出：一个算法有一个或者多个输出。输出与输入有着某种特定的关系

好的算法具备特质：

       正确性、可读性、健壮性、 高效率和低存储需求

时间复杂度与空间复杂度

评估时间开销

事前预估算法时间开销与问题求解
O(n)

空间复杂度

程序代码存放内存与问题规模大小无关

问题内存与n大小无关，原地工作
空间：与 n正比 0（n）
递归调用空间复杂度计算，每次调用都会重新申请新的空间

第二章线性表

def：

具有相同类型（n >=0) 个有限序列，n=0时线性表为空表，一般为L=(a1,a2…,an)

几个概念：

ai是线性表中“第i个”元素线性表的位序
a1是表头元素，an是表尾元素
除了第一个元素每个元素有一个直接前驱，除了最后一个元素每个元素都有一个直接后继
线性表 -Linear List
InitList（&L）初始化分配内存
Destory（&L）销毁释放内存
ListInser（&L，i，e）在第i个位置上插入e

TIPS
C语言函数定义： <返回类型> 函数名（
《类型》参数1 。。。）