一、基础

1.信息的表示是计算机科学的基础。

2.数据是信息载体，是描述事物的数、字符以及可输入计算机并被程序识别处理的符号的集合。

3.数据的基本单位是数据元素。（最小标识单位数据项组成了数据元素）

数据结构：某一数据元素的集合及该集合中所有数据元素间关系。Data_Structure={D,R}

D:数据元素集 R：D中所有数据元素之间关系的有限集。

线性结构:

①线性结构list：仅一个元素无前驱（表头），一个元素无后继（表尾），其余元素均有一个前驱与一个后继。

非线性结构：

②树结构tree：有且仅有一个元素（root）无前驱，可有多个后继，其余元素要有且仅有一个前驱

③图结构graph：可能有0-多个前驱或后继。（可出现孤立的点）

数据据结构涵盖：①元素间的逻辑关系即数据逻辑结构。

②元素及其关系在计算机存储中的表示即数据的存储表示，

③数据的运算即对元素的操作。

数据逻辑结构：①从逻辑上描述数据与存储无关②与元素本身形式内容无关③与元素相对存储位置无关④具体问题抽象出的数据模型

数据的存储表示：逻辑结构用语言实现。

适用内存：顺序/链式

适用外存：索引（树）、散列

数据处理前后应维持结构（逻辑关系）

二叉树可分左右满足二分查找。

1.在数据结构中，与所使用的计算机无关的是数据的（ 逻辑）结构。

2.数据的逻辑结构可以分为（线性与非线性 )两类。

3.

4.逻辑结构相同的数据，可采用多种不同的存储方法

二、抽象数据类型

数据类型：一个类型及定义在此类型上的操作

抽象：实现细节与详细的规范说明完全分开

ADT与数据结构的关系：①二者都表示数据类型②ADT是数据类型的逻辑表现③数据结构是ADT物理形式

三、算法分析

1.概述

数据规模不大时：运行时间函数的每个项数都有很重要的作用。

数据规模不断增大时：运行时间函数的增长速度只和高次项有关、具有同样高次项的运行时间函数增长速度一致、运行函数的差异性起决定作用的是增长率（高次项的增长速度）

基本考虑：处理一定规模（输入量的数目）的输入时该算法所需要执行的基本操作（完成该操作所需的时间与操作数的具体取值无关）数。

输入规模n对运行时间不产生影响。这称为常数运行时间。

2.数据分布的特点对很多检索算法都会有很大影响。在实时系统中我们比较关注最差情况的算法分析，在其他情况下，通常考虑平均情况，只要我们知道计算平均情况所需要的输入数据的分布即可。否则就只能求助于最差情况。

大O表示法：确定一个函数的上界，也就是确定函数可能运行的多糟。

使用O:f的增长率小于或等于某个函数的增长率。

使用Ω：f的增长率大于或等于某个函数的增长率。

使用θ：f的增长率等于某个函数的增长率。（上下界相同）两个Θ相同的函数有交换性。

大O 运算的简化法则。

3.并非所有的嵌套for循环都为Θ（n方）

for（k=1;k<=n;k*=2)

for(j=1;j<=k;j++)

为Θ（nlogn） k部分为级数

4.顺序检索与二分法检索比较：顺序检索法的平均和最差情况代价Θ（n）原大于二分法的代价Θ（logn），但是二分法要求元素必须按照从高到低顺序保存，这个排序的要求可能会对时间代价产生损害，插入新元素时会增加时间代价，需要权衡。

5.多参数问题：不同参数的取值可能会对结果造成影响，不能轻易舍去。

Θ（P+ClogC)若p小一些而c大一些，clogc则不能忽略。

6.空间代价

数据结构的主要目的是使用恰当的方法存储数据，所有这类并非真正数据结构的附加信息如指针等被称为结构性开销（应尽量小）

练习：

a：是正确的，满足法则。

b：是错误的，T1（N)为N的立方+N的平方，T2（N）为N的立方+N，显然T1-T2=O（N)而不等于原先的O（F（N））。

c：是错误的，T1=T2=N的平方，显然T1/T2=O（1）.

d: 是错误的，O的使用方法为f的增长率小于某个函数的增长率，T1和T2同小于等于某个函数，但是T1却可能大于T2，所以错误。

a：t=5x0.5ms=2.5ms

b：t=0.5x5xlog5ms=2.5log5ms

c：t=5x5x0.5ms=12.5ms

d：t=5x5x5x0.5ms=67.5ms

此算法仅调用了一重for循环，故时间复杂度为O（n）

要使算法的时间复杂度为O（logn），要使用分治的思想并递归调用函数。

先编写一个swap函数用于交换某两项。