文档介绍：全国计算机二级基础知识
算法与数据结构
算法四个基本特征
可行性
确定性(明确的定义)
有穷性(有限的时间)
拥有足够的情报
时空复杂度
时间复杂度:需要计算工作量。
空间复杂度:执行过程中需要存储空间。
数据结构的基本概念:数据元素之间关系的元素集合,提高数据处理的效率。
数据结构的三方面:{线性结构{线性表,栈,队列},非线性结构{树,图}}
数据的存储结构:{顺序存储,连式存储}:检索,排序,插入,删除,修改。
数据逻辑结构:反映元素之间逻辑关系的数据及结构。
B=(D,R)B:数据结构D:数据元素集合R:数据之间前后件关系。
图形表示
数据元素:用中间标有元素值方框表示称为节点。
逻辑关系:用有向线段从前件指向后件,没有前件的是根节点,没有后件的是终端节点(叶子节点)
B=(D,R) D={di|1<=i<=7}={d1,d2,d3,d4,d5,d6,d7} R=[(d1,d3)(d1,d7)(d2,d4)(d3,d6)(d4,d5)]
数据流图中带有箭头的线段表示的是数据流
数据存储结构逻辑存储结构与数据存储结构不一定相同。一种数据结构可以表示多种存储结构。不同的存储结构,处理效率不同。
数据的存储结构有顺序,链接,索引等。
线性结构(线性表)节点个数n称为线性表长度。N=0表示空表。
常见线性表:栈,队列,循环队列。
空的数据结构可能属于线性结构,也可能属于非线性结构。
顺序存储结构的特点:
线性表中所有元素所占存储空间是连续的,各数据元素在存储空间中按逻辑顺序依次存放。
ADR(a1)=ADR(a1)+(i-1)k,ADR(a1)为第一个元素地址,k代表每个元素所占的字节数。
数据的逻辑结构是指反映数据元素之间的逻辑关系的数据结构。
数据的逻辑结构有两个要素:,记作D 2 .各元素的前后件关系记作R
数据结构B=(D,R)
线性表的基本概念:线性表是由一组数据构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。
在复杂的线性表中,由若干数据元素组成的数据元素称为记录,由多个记录构成的线性表称为文件。
非空线性表的结构特性:
·有且只有一根节点a1,它无前件
·有且只有一终结点an,它无后件
·除根节点和终端节点外,其他所有节点有且只有一个前件,有一个后前。
顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连续的
节点个数n称为线性表的长度。当N=0时,称为空表。
顺序表的插入运算:
当存储空间已满时为“上溢”错误,不能插入,算法结束。
当i>n时,认为在最后一个元素之后插入;当i<n时,在第一个元素前插入。
然后从最后一个元素开始,直到第一个元素,其中每一个元素均往后移动一个位置。
也有且只
,并且将线性表的长度增加1。
删除的过程:
·首先处理两种异常情况:
当线性表为空(即n=0)时为“上溢”错误,算法结束;
当i<1或i>n时
·然后从第i+1个元素开始,直到最后一个元素,其中每个元素依次向前移动一个位置。
循环队列初始状态改变,先将rear+改变后的数值再减去改变后front的值
线性表顺序存储的缺点:插入删除效率低,不易扩张,多个线性表共享空间时,不易分配空间。
线性链表基本概念
数据结构中的每个数据结构节点对应于一个存储单元,这种存储单元称为存储节点,简称节点。
链式存储方式中,节点的两个组成部分:
·存放数据元素值的部分,称为数据域;
·存放指针的部分,称为指针域。用于指向该节点的前一个或后一个节点。
链式存储方式既可以用于线性结构,也可以用于非线性结构。
线性表的链式存储方式称为线性链表。HEAD称为头指针,HEAD=NULL(或0)称为空表。
双向链表中,Llink为左指针(指向前一个),Rlink为右指针(指向后一个)。
带链的表带链的队列
线性链表的基本运算
·在线性链表中查找指定元素;
·线性链表对的插入(先断开,插入,再连接);
·线性链表的删除。
循环链表:最后一个节点的指针域指向头节点,整个链表形成一个环。
在长度为n的有序线性链表中使用二分法查找,最坏的情况下,需要比较log2n次.
支持子程序调用的数据结构是( 栈)。
树
一种简单的非线性结构元素之间具有明显的层次特性
·每个节点只有一个前节点,称为父节点;
·没有前件的节点只有一个,为根节点,简称根;
·每一个节点可以有多个后节点,称为该节点的子节点
·没有后件的节点为叶子节点;
·一个节点拥有的后间个数,称为该节点的度
·所有节点中最大的度,称为数的度;
·树的最大层