数据结构+算法=程序设计

什么是数据结构

数据（data）：符号集合，处理对象。

数据元素（data element），由数据项（data item）组成。

关键字（key）识别元素，主关键字（primary key）唯一识别元素。

数据结构（data structure）指数据元素之间存在的关系。

包含以下三方面： 数据的逻辑结构数据的存储结构数据操作

数据的逻辑结构

线性结构：数据元素只有一个前驱数据元素和一个后继数据元素。

树结构：每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。

图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素。

数据的存储结构

顺序存储结构

链式存储结构

数据操作

1.初始化。

2.判断是否空状态。

3.存取，指获得、设置指定元素值。

4.统计数据元素个数。

5.遍历（traverse），指按照某种次序访问一个数据结构中的所有元素，并且每个数据元素只被访问一次。遍历一种数据结构，将得到一个所有数据元素的线性序列。

6.插入（insert）、删除（remove）指定元素。

7.查找（search），指在数据结构中寻找满足给定条件的数据元素。

8.排序（sort），指对数据元素按照指定关键字值的大小递增（或递减）次序重新排列。

数据类型与抽象数据类型

数据类型（data type）是指一个类型和定义在这个类型上的操作集合。

抽象数据类型（Abstract Data Type，ADT）是指一个逻辑概念上的类型和这个类型上的操作集合。

即，一种数据结构的抽象数据类型包括：

数据的逻辑结构
数据操作

#复数抽象类型

ADT Complex

{

double real, imag; //实部和虚部

Complex(double real, double imag)

Complex add(Complex c) //加法

Complex sub(Complex c) //减法

}

#集合的表示与实现

ADT Set<T> //集合抽象数据类型

{

数据：集合中的数据元素，数据元素的数据类型为T

操作：

boolean isEmpty(); //判断集合是否为空

int size (); //返回元素个数

T search(T key) //返回查找到的关键字为key元素

boolean contains(T key) //判断是否包含关键字为key元素

boolean add(T x) //增加元素x

T remove(T key) //删除关键字为key元素

void clear() //删除所有元素

String toString() //返回所有元素的描述字符串

#集合的抽象数据类型

ADT Set<T> {

boolean equals(Object obj) //比较this与obj是否相等

Object[] toArray() //返回包含所有元素的数组

//以下方法描述集合运算，参数是另一个集合

boolean containsAll(Set<?> set) //判断是否子集

boolean addAll(Set<? extends T> set) //集合并运算

boolean removeAll(Set<?> set) //集合差

boolean retainAll(Set<?> set) //仅保留那些也包含在set的元素，集合差

}

实现不同特性的集合

①线性表表示可重复的无序集合，元素间具有前驱、后继次序关系；不同元素的关键字可重复，采用序号能够识别关键字重复的数据元素。

②排序线性表表示可重复的排序集合，元素按关键字大小次序排序。

③散列表表示不可重复的无序集合，元素关键字不重复，元素间没有次序，不排序。

④二叉排序树表示不可重复的排序集合，元素关键字不重复，元素按关键字升/降序排序。

用java语言的接口描述抽象数据类型

Java语言的接口（interface）是一组抽象方法、常量和内嵌类型的集合。

1.声明接口

public interface Set<T> //集合接口，T是泛型参数

2.声明实现接口的类

public abstract class AbstractSet<T> implements Set<T> //抽象集合类，没有实现所有抽象方法 public class HashSet<T> implements Set<T> //散列表类

3.接口是引用类型

Set<T> set = new HashSet<T>(); //接口对象引用实例

set.add(x) //运行时多态性，执行HashSet<T>类实现的add(x)方法

算法

一个算法（Algorithm）是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。

定义

有穷性
确定性
输入
输出
可行性

算法设计目标

正确性
可读性
健壮性
高时间效率
高空间效率

算法描述

//在当前数据结构中，顺序查找与key相等的元素（数据类型为T）；key提供查找条件的关键字

元素 search(T key) {

for (elem : 数据结构中的每个元素) //遍历

if (key与elem元素相等) //由T类型约定两个元素相等的比较规则

查找成功，返回元素或元素位置;

查找不成功，返回查找不成功标记;

}

算法与数据结构

算法分析

1.度量算法的时间效率

算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率。

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

1.一条简单语句的时间复杂度是O(1)。

int count=0;

2.一个循环的时间复杂度是O(n)。

int n=8, count=0;

for (int i=1; i<=n; i++)

count++; //循环体执行n次

3.以下循环语句的时间复杂度是O(log_2 n)。

for (int i=1; i<=n; i*=2) //i按2的幂（1,2,4,8）递增

count++; //循环体执行1+log2 n 次

4.以下二重循环的时间复杂度为O(n^2)。

for (int i=1; i<=n; i++)

for (int j=1; j<=n; j++)

5.以下二重循环的时间复杂度是O(n×log_2 n)

for (int i=1; i<=n; i*=2) //循环log2n次

for (int j=1; j<=n; j++) //循环n次

6.以下二重循环的时间复杂度是O(n)。

for (int i=1; i<=n; i*=2) //循环log2n次

for (int j=1; j<=i; j++) //循环i次

//循环次数