数据结构（一）——绪论

一、数据结构的研究内容

1.数据的各种逻辑结构和物理结构，以及他们之间的相应关系

2.存储结构的方法，对每种结构定义相适应的各种运算

3.设计出相应的算法

4.分析算法的效率

二、数据结构的基本概念

1.数据（data）：能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图像等，都称为数据

2.数据元素(data element) :数据的基本单位 ，在计算机程序中通常作为一个整体进行考虑和处理。

3.一个数据元素包含若干个 数据项 (data item)。

4.数据元素、 数据项和数据的逻辑结构在计算机中的表示又称为结点、数据域和存储(物理)结构。

例如：

这两张表就是 数据

单独的一张表称为 数据对象 ，即人员表是一个数据对象，课程表也是一个数据对象

每张表中的每一行就称为 数据元素

姓名，性别，身高，课程代号，课程名就称为 数据项

5.数据结构：是 相互之间存在一种或者多种特定关系的数据元素的集合

数据结构包括 逻辑结构 和 存储结构 两个层次

逻辑结构 分为四种类型： 集合结构，线性结构，树形结构，图形结构

(1)集合结构：数据元素同属一个集合，单个数据元素之间没有任何关系

例:

(2)线性结构：类似于线性关系，线性结构中的数据元素是一对一的关系

例：

（3）树形结构：树形结构中的数据元素之间存在一对多的关系（各元素级元素关系所组成图形类似于树状图）

例：

（4）图形结构：数据元素之间是多对多的关系

例：

物理结构 又叫存储结构，分为两种： 顺序存储结构，链式存储结构

（1） 顺序存储结构 ：是把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的。数组就是一种顺序存储结构。

例：

（2） 链式存储结构 ：是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。

例:

6.数据类型:一个值的集合及定义在这个值集上的一组操作的总称。

一般包括整型、实型、字符型等原子类型外，还有数组、结构体和指针等结构类型。

7.抽象数据类型(Abstract DataType,ADT)：类似C语言中的结构体以及C++语言中的类。通俗的讲，抽象数据类型，泛指除基本数据类型以外的数据类型，

三、算法和算法分析

算法 (algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作;此外，一个算法还具有下列5个重要特性:

（1）. 有穷性 :一个算法必须总是(对合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成

（2）. 确定性 :算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。

（3）. 可行性 :一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

（4）. 输入 :一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。

（5）. 输出 :一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。

算法+数据结构=程序

时间复杂度

时间复杂度指算法中各语句执行时间的总和

T(n) = O(f(n))

例:

计算时间复杂度：

在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数，这样可以简化算法分析，也体现出增长率的含义

因此，

（1）最好时间复杂度:算法在最好情况下的时间复杂度。

（2）最坏时间复杂度:算法在最坏情况下的时间复杂度。

（3）平均时间复杂度:算法在所有可能的情况下，按照输入实例以等概率出现时，算法计量的加权平均值。

对算法时间复杂度的度量，通常只讨论算法在最坏情况下的时间复杂度即分析在最坏情况下，算法执行时间的上界。

3.示例

（1）常量阶实例：

f(n) = 1 + 1 = 2

T(n) = O(1)

T(n) = O(1) （i<10000，最后是常数）

只要最后算出是一个常数，其时间复杂度都是O(1)

（2）线性阶示例：

f(n) = (n+1)+n+n = 3n+1

T(n) = O(n)

(3)平方阶示例

T(n) = O(n^2)

（4）立方阶示例

以上计算方式：

（5）对数阶示例：

4.时间复杂度汇总

5.例题

循环结束条件是i<n，故求i的值