1.2什么是数据结构 (data structure) 数据的逻辑结构 数据的存储结构 数据的运算 北京大学信息学院 版权所有,转载或翻印必究 Page 16
北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 1.2 什么是数据结构 (data structure) ◼ 数据的逻辑结构 ◼ 数据的存储结构 ◼ 数据的运算
1.2.1数据的逻辑结构 n反映了我们对数据含义的解释 数据的逻辑结构可以用一组数据(表示为结点集合 K),以及这些数据之间的一组二元关系(关系集合R) 来表示:(K,R) K是由有限个结点组成的集合,每一个结点都代表一个数据 或一组有明确结构的数据 而关系集R是定义在集合K上的一组关系,其中每个关系 relation)r(r∈R)都是K×K上的二元关系,用它描述结 点数据之间的逻辑关系 北京大学信息学院 版权所有,转载或翻印必究 Page 17
北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 1.2.1 数据的逻辑结构 ◼ 反映了我们对数据含义的解释 ◼ 数据的逻辑结构可以用一组数据（表示为结点集合 K），以及这些数据之间的一组二元关系（关系集合R） 来表示：( K ，R ) ◼ K是由有限个结点组成的集合，每一个结点都代表一个数据 或一组有明确结构的数据 ◼ 而关系集R是定义在集合K上的一组关系，其中每个关系 (relation) r（r∈R）都是K×K上的二元关系，用它描述结 点数据之间的逻辑关系
数据的逻辑结构(示例) 家族人员 把每个成员个体的属性描述作为数据结点,而全部人员组成 结点集K 家族的各类亲属关系就是一组关系R,其中如母系血缘关系r、 远亲关系r*、和非血缘的亲情关系r等等,每一个关系要给 出具体人员的关系元组 ■例如:母子关系(王爱莲,张选) 兄弟关系(张选,张立) 妯娌关系(王爱莲,李美英) 北京大学信息学院 版权所有,转载或翻印必究 Page 18
北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 数据的逻辑结构（示例） ◼ 家族人员 ◼ 把每个成员个体的属性描述作为数据结点，而全部人员组成 结点集K ◼ 家族的各类亲属关系就是一组关系R, 其中如母系血缘关系r、 远亲关系r*、和非血缘的亲情关系r’等等，每一个关系要给 出具体人员的关系元组 ◼ 例如：母子关系（王爱莲，张选） 兄弟关系（张选，张立） 妯娌关系 （王爱莲，李美英）
结点的类型 基本数据类型 整数类型( integer):该类型规定了所能表示的整数范围, 在计算机中一般使用1个字节到4个字节来存储整数 实数类型(rea):计算机的浮点数据类型所能表示的数值范 围和精度是有限的。机器一般使用4个字节到8个字节来存 储浮点数 n布尔类型( boolean):取值为真(true)和假( false),在 C++语言中一般使用整数0表示 false,用非0表示真 北京大学信息学院 版权所有,转载或翻印必究 Page 19
北京大学信息学院 ©版权所有，转载或翻印必究 Page 19 结点的类型 ◼ 基本数据类型 ◼ 整数类型(integer)：该类型规定了所能表示的整数范围， 在计算机中一般使用1个字节到4个字节来存储整数 ◼ 实数类型(real)：计算机的浮点数据类型所能表示的数值范 围和精度是有限的。 机器一般使用4个字节到8个字节来存 储浮点数 ◼ 布尔类型(boolean)：取值为真(true)和假(false)，在 C++语言中一般使用整数0表示false，用非0表示真
结点的类型 基本数据类型 n字符类型(char):用单个字节(8bit,最高位bit 为0)表示ASCT字符集中的字符 n汉字符号需要使用2个字节(每个字节的最高位bit为1) 的编码,单个字节对于汉字是没有独立含义的。 北京大学信息学院 版权所有,转载或翻印必究 Page 20
北京大学信息学院 ©版权所有，转载或翻印必究 Page 20 结点的类型 ◼ 基本数据类型 ◼ 字符类型(char)：用单个字节（8bit，最高位bit 为0）表示ASCII字符集中的字符。 ◼ 汉字符号需要使用2个字节（每个字节的最高位bit为1） 的编码，单个字节对于汉字是没有独立含义的