文档介绍：数据结构与算法

算法:解决方案的准确而完整的描述
算法的特征: 可行性确定性有穷性算法有零个或多个输入算法有一个或多个输出
算法的基本要素:运算操作控制结构(包括:顺序、选择、循环结构)
算法设计的基本方法:列举法归纳法递推递归减半递推技术回溯法
算法复杂度:时间复杂度空间复杂度
时间复杂度:处理问题的规模执行指令的次数(相对时间、相对问题规模)
计算时间复杂度: 例一 for(i=1;i<=n;i++) for(j=1;j<=m;j++) k=i+j; f(n)=n*n=n² (平方阶) 例二 for(k=1;k<=n+5;k++); s=s+k; O(f(n))=O(n+5)=n (线性阶)
例三 a=2;b=3;t=a+b; O(f(n))=O(3)=常数(常数阶)
时间复杂度的表现形式
常数阶线性阶平方阶立方阶平方根阶对数阶
分析算法的手段:平均性态最坏情况复杂性
数据结构的研究对象:内存
数据结构的主要目的:提高数据处理的效率
程序=算法+数据结构(数据结构决定算法)
数据结构是二元组
数据结构:数据的集合(D)、关系的集合(R) DS=(D,R)
数据结构包括:线性结构树图
线性结构
线性结构: 唯一的数据,没有前驱唯一的数据,没有后继除了第一个元素外,其余的都没有唯一的前驱;除了最后一个元素外,其余的都有唯一的后继
线性表的顺序存储结构: 方法: 顺序结构(随机结构) 非顺序结构
非线性结构
非线性结构:不是有唯一的后继,而是有多个后继。
“树”属于非线性结构
物理上的相邻表示逻辑上的相邻
顺序结构对应的相关操作:插入、删除
B
C
D
F
G
 
 
插入“E”:从G开始移动
删除“D”把“F”向前移
栈
栈”:先进后出或后进先出
栈的基本运算:入栈退栈读栈顶元素
“队列”:先进先出或后进后出
入队队尾(rear)
出队对头(front)
循环队列:maxsize+(front-rear)%maxsize
一个循环队列有15个元素,队头所在的位置6,队尾为8,求循环队列有多少元素?
解:15+(6-8)%15=13 %:取余
线性列表:非顺序结构称为链式结构
前一个链表记住后一个元素位置
单向链表双向连链表循环链表