文档介绍：概念总结
第一章概论
,涉及数据的逻辑结构、存储结构和运算
,反映了事物的组成结构及事物之间的逻辑关系
可以用一组数据(结点集合K)以及这些数据之间的一组二元关系(关系集合R)来表示:(K, R)
结点集K是由有限个结点组成的集合,每一个结点代表一个数据或一组有明确结构的数据
关系集R是定义在集合K上的一组关系,其中每个关系r(r∈R)都是K×K上的二元关系
整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型(char)、指针类型(pointer)
复合类型是由基本数据类型组合而成的数据类型;复合数据类型本身,又可参与定义结构更为复杂的结点类型
:线性结构(一对一)、树型结构(一对多)、图结构(多对多)
:顺序、链接、索引、散列
:通用性、有效性、确定性、有穷性
:目的是从解决同一个问题的不同算法中选择比较适合的一种,或者对原始算法进行改造、加工、使其优化
:上限,表明最坏情况
:下限,表明最好情况
:当上限和下限相同时,表明平均情况
第二章线性表
“第一元素”
“最后元素”
,均有唯一的后继
,均有唯一的前驱
:均匀性、有序性
:元素的类型相同;元素顺序地存储在连续存储空间中,每一个元素唯一的索引值;使用常数作为向量长度
b. 线性表中任意元素的存储位置:Loc(ki) = Loc(k0) + i * L(设每个元素需占用L个存储单元)
c. 线性表的优缺点:
优点:逻辑结构与存储结构一致;属于随机存取方式,即查找每个元素所花时间基本一样
缺点:空间难以扩充
:ASL=【Ο(1)】
:插入前检查是否满了,插入时插入处后的表需要复制【Ο(n)】
:删除前检查是否是空的,删除时直接覆盖就行了【Ο(n)】
:逻辑顺序与物理顺序有可能不一致;属于顺序存取的存储结构,即存取每个数据元素所花费的时间不相等
:head和tail指向单链表的头结点
(q->next=p->next; p->next=q;)【Ο(n)】
(q=p->next; p->next = q->next; delete q;)【Ο(n)】
:next仅指向后继,不能有效找到前驱
,弥补单链表的不足
:head和tail指向单链表的头结点
:(q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;)
:(p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;)
没用使用指针,不用花费附加开销;线性表元素的读访问非常简洁便利
无需事先了解线性表的长度;允许线性表的长度有很大变化;能够适应经常插入删除内部元素的情况
经常插入删除时,不宜使用顺序表;线性表的最大长度也是一个重要因素
当不经常插入删除时,不应选择链表;当指针的存储开销与整个结点内容所占空间相比其比例较大时,应该慎重选择
第三章栈与队列
;其特点后进先出;插入:入栈(压栈);删除:出栈(退栈);插入、删除一端被称为栈顶(浮动),另一端称为栈底(固定);实现分为顺序栈和链式栈两种
:
1)数制转换
while (N) {
N%8入栈;
N=N/8;
}
while (栈非空){
出栈;
输出;}
2)括号匹配检验
不匹配情况:各类括号数量不同;嵌套关系不正确
算法:
逐一处理表达式中的每个字符ch:
ch=非括号:不做任何处理
ch=左括号:入栈
ch=右括号:if (栈空)