1.2基本概念和术语 数据结构在计算机中的表示称为数据的物理结构,又称为 存储结构。 数据结构在计算机中有两种不同的表示方法: 顺序表示和非顺序表示 ●由此得出两种不同的存储结构:顺序存储结构和链式存储 结构 ●顺序存储结构:用数据元素在存储器中的相对位置来表示 数据元素之间的逻辑关系。 ●链式存储结构:在每一个数据元素中增加一个存放地址的 指针,用此指针来表示数据元素之间的逻辑关系。 北京邮电大学自动化学院
北京邮电大学自动化学院 26 ⚫ 数据结构在计算机中的表示称为数据的物理结构，又称为 存储结构。 ⚫ 数据结构在计算机中有两种不同的表示方法： ⚫ 顺序表示和非顺序表示 ⚫ 由此得出两种不同的存储结构：顺序存储结构和链式存储 结构 ⚫ 顺序存储结构:用数据元素在存储器中的相对位置来表示 数据元素之间的逻辑关系。 ⚫ 链式存储结构：在每一个数据元素中增加一个存放地址的 指针，用此指针来表示数据元素之间的逻辑关系。 1.2 基本概念和术语
存储地址存储内容 元素1 元素2 Lo+m 顺序存储 元素i Lo+(i-1) m 元素n Lo+(n-1)*m Loc(元素i)=L0+(i1)*m 北京邮电大学自动化学院 27
北京邮电大学自动化学院 27 元素n …….. 元素i …….. 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储
h 1345 链式存储 元素11400 元素21536 元素31346 元素4 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 1400 元素2 1536 1536 元素3 1346 北京邮电大学自动化学院
北京邮电大学自动化学院 28 元素1 1400 元素2 1536 元素3 1346 元素4 ∧ 1345 h 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. ……. 1400 元素2 1536 ……. …….. ……. 1536 元素3 1346 链式存储 h
1.2基本概念和术语 数据结构的三个方面: 线性表 线性结构栈 队 数据的逻辑结构 非线性结构 树形结构 图形结构 数据的存储结构顺序存储 链式存储 数据的运算:检索、排序、插入、删除、修改等 北京邮电大学自动化学院
北京邮电大学自动化学院 29 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个方面： 1.2 基本概念和术语
1.2基本概念和术语 ●数据类型:数据类型是一个值的集合和定义在这个值集范围 上的一组操作的总称。例如,C语言中的整型变量,其值集 为某个区间上的整数,定义在其上的操作为:加、减、乘、 除和取模等算术运算 按“值”的不同特性,高级程序语言中的数据类型可分为: 一类是非结构的原子类型。原子类型的值是不可分解的。 如:C语言中的基本类型(整型、实型、字符型和枚举类 型)、指针类型和空类型。 ●另一类是结构类型。结构类型的值是由若干成分按某种结构 组成的。例如数组的值由若干分量组成。每个分量可以是整 数,也可以是数组等。 北京邮电大学自动化学院
北京邮电大学自动化学院 30 ⚫ 数据类型：数据类型是一个值的集合和定义在这个值集范围 上的一组操作的总称。例如，C语言中的整型变量，其值集 为某个区间上的整数，定义在其上的操作为：加、减、乘、 除和取模等算术运算。 ⚫ 按“值”的不同特性，高级程序语言中的数据类型可分为： ⚫ 一类是非结构的原子类型。原子类型的值是不可分解的。 如：C语言中的基本类型（整型、实型、字符型和枚举类 型）、指针类型和空类型。 ⚫ 另一类是结构类型。结构类型的值是由若干成分按某种结构 组成的。例如数组的值由若干分量组成。每个分量可以是整 数，也可以是数组等。 1.2 基本概念和术语