考虑和处理。 数据对象:是性质相同的数据元素的集合,是数据的一个子集。 数据的逻辑结构是对数据元素之间的逻辑关系的描述, 它可以用一个数据元素的集合和定义 在此集合中的若干关系来表示。数据的逻辑结构有两个要素:一是数据元素的集合,通常记 为 D;二是 D 上的关系,它反映了数据元素之间的前后件关系,通常记为 R。一个数据结 构可以表示成 B=(D,R) 其中 B 表示数据结构。为了反映 D 中各数据元素之间的前后件关系,一般用二元组来表示。 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结 构) 。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同, 因此, 为了表示存放在 计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系) ,在数据的存储结构中, 不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构,
常用的存储结构有顺序、链接、索 引等存储结构。而采用不同的存储结构,其数据处理的效率是不同的。因此,在进行数据处 理时,选择合适的存储结构是很重要的。 考点 4 线性结构与非线性结构 考试链接: 考点 4 在笔试考试中,虽然说不是考试经常考查的内容,但读者还是对此考点有所了解,在 笔试考试
中出现的几率为 30%,主要是以填空题出现的形式出现,分值为 2 分,此考点为 识记内容。 根据数据结构中各数据元素之间前后件关系的复杂程度, 一般将数据结构分为两大类型: 线 性结构与非线性结构。如果一个非空的数据结构满足下列两个条件: (1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 则称该数据结构为线性结构。 线性结构又称线性表。 在一个线性结构中插入或删除任何一个
结点后还应是线性结构。如果一个数据结构不是线性结构,则称之为非线性结构。
疑难解答:空的数据结构是线性结构还是非线性结构? 一个空的数据结构究竟是属于线性结构还是属于非线性结构, 这要根据具体情况来确定。 如 果对该数据结构的算法是按线性结构的规则来处理的, 则属于线性结构; 否则属于非线性结 构。 1.3 栈及线性链表 考点 5 栈及其基本运算 考试链接: 考点 5 在笔试考试中,是一个必考的内容,在笔试考试中出现的几率为 100%,主要是以选 择的形式出现,分值为 2 分,此考点为重点掌握内容,读者应该掌握栈的运算 。 1.栈的基本概念 栈是限定只在一端进行插入与删除的线性表,通常称插入、删除的这一端为栈顶,另一端为 栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素,从而也是最先被删除的 元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。栈是按照"先进 后出"或"后进先出"的原则组织数据的。 2.栈的顺序存储及其运算 用一维数组 S(1∶m)作为栈的顺序存储空间,其中 m 为最大容量。 在栈的顺序存储空间 S(1∶m)中,S(bottom)为栈底元素,S(top)为栈顶元素。top=0 表示栈空;top=m 表示栈满。 栈的基本运算有三种:入栈、退栈与读栈顶元素。 (1)入栈运算:入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即 top 加 1) ,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一 个位置时,说明栈空间已满,不可能再进行入栈操作。这种情况称为栈"上溢"错误。 (2)退栈运算:退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素(栈顶指 针指向的元素)赋给一个指定的变量,然后将栈顶指针减一(即 top 减 1) 。当栈顶指针为 0 时,说明栈空,不可进行退栈操作。这种情况称为栈的"下溢"错误。 (3)读栈顶元素:读栈顶元素是指将栈顶