数据结构-算法

算法定义

算法（Algorithm）是解决特定问题的步骤的描述。在计算机中算法是一个有穷规则（或语句、指令）的有序集合。

它确定了解决某一问题的一个运算序列。对于问题的初始输入，通过算法有限步的运行，产生一个或多个输出。

算法与程序

算法是解决问题的思想方法

程序是计算机语言的具体实现

算法与数据结构

算法设计：取决于选定的逻辑结构

算法实现：依赖于采用的存储结构

瑞士科学家沃思(N.Wirth)的著名公式：

数据结构　＋　算法　＝　程序

算法特性

1. 有穷性
2. 确定性
3. 可行性
4. 输入
5. 输出

算法分析

解决一个问题可以有多种不同的算法，在算法正确的前提下，评价算法好坏的方法：

• 正确性
• 可读性
• 健壮性
• 时间效率高
• 存储量低
• 消耗时间的多少
• 消耗存储空间的多少
• 容易理解、容易编程和调试、容易维护

算法效率的度量——算法时间复杂度

算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量

问题的规模：输入数据量的大小，用n来表示

算发的时间复杂度：算法消耗时间，它是问题规模的函数T(n)

算法时间复杂度——事后统计法

通过编写测试程序和设计测试数据，测试程序的运行时间，从而确定算法效率的高低。

缺陷：

1. 依赖于特定的计算机硬件和软件
2. 需要花大量尽力设计测试程序和测试数据

算法时间复杂度——时间估计方法

根据统计学的方法，对算法效率进行估算

程序在计算机运行所消耗时间取决于：

• 算法设计
• 算法的输入规模
• 编译器对代码的优化
• 计算机执行指令的速度

引用了"0"，"0"表示一个数量级的概念。根据算法中语句的最大次数（频度）来估算一个算法执行时间的数量级。

时间复杂度：

​ 算法中基本操作重复执行的次数是问题规模n的某个函数f(n),T(n)=0 (f(n))，他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。

语句频度：是该语句重复执行的次数。

算法效率的度量——计算大０

方法：

1. 根据语句频度，写出表达式
2. 常数部分变为１
3. 只保留最高阶项目，其余项的舍去
4. 如果最高阶项有乘数且不为１，表达式除以最高阶相乘的数

算法空间复杂度

算法的空间复杂度就是计算算法所需要的存储空间的大小

S(n) = 0(f(n))

线性表

线性表定义：线性表就是零个或多个相同数据元素的有限序列。

线性表的统计方法：L=(a0,......,an-1)

L为表名，ai(0<=i<=n-1)为数据元素，n为表长。

线性表L可用二元组形式描述：

L=(D,R)

线性表的特征：

1. 对非空表，a0是表头，无前驱；
2. an-1是表尾，无后继；
3. 其它的每个元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)。

线性表基本运算

1. 建立一个空表：CreateList(L)
2. 置空表：ClearList(L)
3. 判断表是否为空：EmptyList(L)，若表为空，返回值为True(或１），否则返回False(或０)
4. 求表长：Length(L)
5. 取表中某个元素：GetList(L, i)，即ai。要求0<=i<=length(L)-1
6. 定位运算：Locate(L, x)，i表示有相等的，-i表示不属于L。
7. 插入：Insert(L,x,i)。将元素x插入到表中第i个元素ai之前，且表长＋１．
8. 删除：Delete(L,i)。删除表中第i个元素ai,且表长减一。

线性表的顺序存储结构

线性表作为一种基本的数据结构类型，在计算机存储器中的映像（或表示）一般有两种形式，一种是顺序映像，一种是链式映象。

顺序存储的特点

1. 逻辑上相邻的元素ai,ai+1，其存储位置也是相邻的
2. 对数据元素ai的存取为随机存取或按地址存取
3. 存储密度高。存储密度D=(数据结构中元素所占存储空间) / (整个数据结构所占空间）

不足：对表的插入和删除等运算的时间复杂度较差

线性表的链式存储结构

单链表结构

将线性表L=(a0.....an-1)中各元素分布在存储器的不同存储块，称为结点，通过地址或指针建立它们之间的联系，所得到的存储结构为链表结构。结点的data域存放数据元素ai，而next域是一个指针，指向ai的直接后继ai+1所在的节点。

typedef struct node_t
{
    data_t data;
    struct node_t *next;
}linknode_t,*linklist_t;