数据结构-算法
算法定义
算法（Algorithm）是解决特定问题的步骤的描述。在计算机中算法是一个有穷规则（或语句、指令）的有序集合。
它确定了解决某一问题的一个运算序列。对于问题的初始输入，通过算法有限步的运行，产生一个或多个输出。
算法与程序
算法是解决问题的思想方法
程序是计算机语言的具体实现
算法与数据结构
算法设计：取决于选定的逻辑结构
算法实现：依赖于采用的存储结构
瑞士科学家沃思(N.Wirth)的著名公式：
数据结构 ＋ 算法 ＝ 程序
算法特性
- 有穷性
- 确定性
- 可行性
- 输入
- 输出
算法分析
解决一个问题可以有多种不同的算法，在算法正确的前提下，评价算法好坏的方法：
- 正确性
- 可读性
- 健壮性
- 时间效率高
- 存储量低
- 消耗时间的多少
- 消耗存储空间的多少
- 容易理解、容易编程和调试、容易维护
算法效率的度量——算法时间复杂度
算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量
问题的规模：输入数据量的大小，用n来表示
算发的时间复杂度：算法消耗时间，它是问题规模的函数T(n)
算法时间复杂度——事后统计法
通过编写测试程序和设计测试数据，测试程序的运行时间，从而确定算法效率的高低。
缺陷：
- 依赖于特定的计算机硬件和软件
- 需要花大量尽力设计测试程序和测试数据
算法时间复杂度——时间估计方法
根据统计学的方法，对算法效率进行估算
程序在计算机运行所消耗时间取决于：
- 算法设计
- 算法的输入规模
- 编译器对代码的优化
- 计算机执行指令的速度
引用了"0"，"0"表示一个数量级的概念。根据算法中语句的最大次数（频度）来估算一个算法执行时间的数量级。
时间复杂度：
算法中基本操作重复执行的次数是问题规模n的某个函数f(n),T(n)=0 (f(n))，他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。
语句频度：是该语句重复执行的次数。
算法效率的度量——计算大０
方法：
- 根据语句频度，写出表达式
- 常数部分变为１
- 只保留最高阶项目，其余项的舍去
- 如果最高阶项有乘数且不为１，表达式除以最高阶相乘的数
算法空间复杂度
算法的空间复杂度就是计算算法所需要的存储空间的大小
S(n) = 0(f(n))
线性表
线性表定义：线性表就是零个或多个相同数据元素的有限序列。
线性表的统计方法：L=(a0,......,an-1)
L为表名，ai(0<=i<=n-1)为数据元素，n为表长。
线性表L可用二元组形式描述：
L=(D,R)
线性表的特征：
- 对非空表，a0是表头，无前驱；
- an-1是表尾，无后继；
- 其它的每个元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)。
线性表基本运算
- 建立一个空表：CreateList(L)
- 置空表：ClearList(L)
- 判断表是否为空：EmptyList(L)，若表为空，返回值为True(或１），否则返回False(或０)
- 求表长：Length(L)
- 取表中某个元素：GetList(L, i)，即ai。要求0<=i<=length(L)-1
- 定位运算：Locate(L, x)，i表示有相等的，-i表示不属于L。
- 插入：Insert(L,x,i)。将元素x插入到表中第i个元素ai之前，且表长＋１．
- 删除：Delete(L,i)。删除表中第i个元素ai,且表长减一。
线性表的顺序存储结构
线性表作为一种基本的数据结构类型，在计算机存储器中的映像（或表示）一般有两种形式，一种是顺序映像，一种是链式映象。
顺序存储的特点
- 逻辑上相邻的元素ai,ai+1，其存储位置也是相邻的
- 对数据元素ai的存取为随机存取或按地址存取
- 存储密度高。存储密度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;
网友评论