1.1数据结构的基本概念

1.1.1基本概念和术语1.数据数据是信息的载体此处是指计算机程序加工的原料2.数据元素数据元素是数据的基本单位如学生的信息记录每一条都是一个数据元素其中姓名、年龄、ID等每个字段都是一个数据项3.数据对象具有相同性质的数据元素的集合是数据的一个子集,比如一个包含几百名学生的数据的文件4.数据类型数据类型是一个值的集合和定义在此集合上的一组操作的总称。1、原子类型。值不可再分如整数int、浮点数float、布尔型bool、字符型char、指针类型等2、结构类型。值可再分割为若干成分的数据类型如数组、结构体struct、共同体union、字符串、对象3、抽象数据类型ADT,一个数学模型及定义在数学模型上的一系列操作。ADT数据结构 操作只关心功能(封装数据与操作)不关心底层怎么实现。如栈stack、队列Queue、链表LinkedList、树Tree、图Graph、字典/映射Map抽象数据类型逻辑结构存储结构数据的运算数据对象数据关系基本操作集5.数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合简单的来说就是把零散的数据按照一定规则摆在一起如栈stack、队列Queue、链表LinkedList、树Tree、图Graph、字典/映射Map这些看存储时是数据结构看操作时是抽象数据类型。表格名称作为数据结构看存储作为抽象数据类型看操作数组连续内存存放同类型数据一般不算标准 ADT仅基础存储结构链表节点 指针串联空间不连续ADT定义增、删、查节点的操作栈可用数组 / 链表实现存储ADT规则先进后出仅支持入栈、出栈、判空队列可用数组 / 链表实现存储ADT规则先进先出仅支持入队、出队、判空树分层分支式存储ADT定义遍历、增删节点、查找等操作图顶点 边构成网状存储ADT定义遍历、查路径、增删顶点 / 边等操作哈希表哈希数组 映射存储ADT定义键值对增、删、查1.1.2 数据结构三要素1.数据的逻辑结构逻辑结构是数据元素之间的逻辑关系不关心数据如何存储只关心元素之间怎么相连。逻辑结构独立于存储结构从实际问题的角度出发如集合元素之间没有关系只是凑成一组、线性结构元素一对一排成一条线、树形结构元素一对多、图形结构元素多对多2.数据的存储结构存储结构是数据结构在计算机中的表示物理结构在存储时不止存储数据的值也存储数据元素之间的关系1、顺序存储。相邻元素存储在物理位置上也相邻的位置2、链式存储。借助元素存储地址的指针来表示元素之间的逻辑关系。3、索引存储。在存储元素同时建索引表。索引表的每项称索引项。4、散列存储。根据元素关键字如学号2006110或者姓名张三直接计算出该元素的存储地址也叫哈希(Hash)存储。