[IT认证]二级公共基础知识1.ppt

数据结构可描述为 Group=（D，R） 例1：一年四季的数据结构可表示成 B=（D，R） D={春，夏，秋，冬} R={（春，夏），（夏，秋），（秋，冬）} 例2：家庭成员数据结构可表示成 B=（D，R） D={父亲，儿子，女儿} R={（父亲，儿子），（父亲，女儿）} 数据结构也可用图形表示 一年四季的数据结构可表示成 家庭成员数据结构可表示成 4、线性表（Linear List） * 有关树的几个概念 根结点、叶子结点、结点的孩子与父结点、结点的度、树的度、结点的层次、树的深度、子树、森林等。 * 学 生 成 绩 表 (按成绩排列) 86 胡孝臣 9861103 95 刘忠赏 9861107 100 张卓 9861109 成 绩 姓 名 学 号 线性表——结点间是以线性关系联结： 线性表：具有线性结构的有限序列。 数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。 线性表的定义: 线性表是n个元素的有限序列，它们之间的关系可以排成 一个线性序列：a1，a2，…… ，ai，…… ，an 其中n称作表的长度，当n=0时，称作空表。 线性表的特点： 1、线性表中所有元素的性质相同。 2、除第一个和最后一个数据元素之外，其它数据元素有且 仅有一个前驱和一个后继。第一个数据元素无前驱，最 后一个数据元素无后继。 3、数据元素在表中的位置只取决于它自身的序号。 在线性表上常用的运算有： 初始化、求长度、取元素、修改、前插、删除、检索、排序 * 线性表的 顺序存储结构 及其 插入 与 删除 操作 特点： 1、线性表中数据元素类型一致，只有数据域，存储空间 利用率高。 2、所有元素所占的存储空间是连续的。 3、各数据元素在存储空间中是按逻辑顺序依次存放的 （a）做插入、删除时需移动大量元素。 （b）空间估计不明时，按最大空间分配。 算 法 与 数 据 结 构 顺序存储 存储地址 存储内容 元素n …….. 元素i …….. 元素2 元素1 Lo Lo + m Lo+(i-1)×m Lo+（n-1)×m Loc(元素i)=Lo+（i-1)×m 每个元素所占用 的存储单元个数 线性表的 顺序存储结构： 首地址 起始地址 基地址 …….. 元素ai+1 …….. 元素a2 元素a1 0 1 i 线性表的顺序存储结构——可用C语言中的一维数组来描述. 第i个元素的ai存储地址： Loc(ai)=Loc(a1)+(i-1)* m V[０] V[１] V[i] V[m-1] int V[M]; 其中：V是数组的名字，M是数组大小， 假设数组中的元素是整型类型 算 法 与 数 据 结 构 插入运算 ….. a2 a1 an ….. ai+1 ai 0 1 i-1 i n-1 ai-1 ….. a2 a1 alength … ai+1 ai x ai-1 ….. a2 a1 X ai ai+1 ….. alength 插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若 假定在n+1个位置上插入元素的可能性均等，则平均移动元素 的个数为： * 在进行删除操作时，若假定删除每个元素的可能性均等， 则平均移动元素的个数为： 分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平 均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。 删除算法的分析 * 线性表的例题讲解 顺序存储方法是把逻辑上相邻的结点存储在物理位置 【1】 的存储单元中。 【答案】相邻 长度为n的顺序存储线性表中，当在任何位置上插入一个元 素概率都相等时，插入一个元素所需移动元素的平均个数 为【2】 。 【答案】 n/2 线性表L=(a1,a2,a3,…ai，…an)，下列说法正确的是（D） A) 每个元素都有一个直接前件和直接后件 B) 线性表中至少要有一个元素 C) 表中诸元素的排列顺序必须是由小到大或由大到小 D) 除第一个元素和最后一个元素外，其余每个元素都有一 个且只有一个直接前件和直接后件 √ * 数据结构中，与所使用的计算机无关的是数据的( C ) A) 存储结构 B) 物理结构 C) 逻辑结构 D) 物理和存储结构 下列叙述中，错误的是（ B ） A) 数据的存储结构与数据处理的效率密切相关 B) 数据的存储结