什么是数据结构 为什么要学习数据结构 data structure) 计算机软件与理论学科的专业基础课程 ■后续专业课程学习的必要知识与技能准备 ■数据逻辑结构 编译技术要使用栈、散列表及语法树 数据的存储结构 逻辑/数据存储 操作系统中用队列、存储管理表及目录树 数据库系统运用线性表、多链表、及索引树 k结构 数据的运算 运算 ■增强求解复杂问题的能力 举位▲张倍墙写 北大单张铭写 叔新有,命邮 数据的逻辑结构 常见的逻辑关系 二元组:(K,R) 线性结构 K是由有限个结点组成的集合 ■树形结构 ■R是定义在集合K上的一组关系,其中 图结构 每个关系( relation)r(r∈R)都是 ■文件结构 K×K上的二元关系 数据结构中,只讨论R={ 图二树二二叉树线性表 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 结点的类型 结点的类型 基本数据类型 ■基本数据类型 整数类型( integer) 字符类型(char):用单个字节(8bt,最高位 bt为0)表示ASCI字符集中的字符。 实数类型(rea) 汉字符号需要使用2个字节〔每个字节的最高位 ■布尔类型( boolean) 在C++语言中一般使用整数0表示 Unicode, GB, Big5, HZ false,用非0衰示true 北真大学张帖精写 聊张帖写 权新有,究 66 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 为什么要学习数据结构 „ 计算机软件与理论学科的专业基础课程 „ 后续专业课程学习的必要知识与技能准备 „ 编译技术要使用栈、散列表及语法树 „ 操作系统中用队列、存储管理表及目录树 „ 数据库系统运用线性表、多链表、及索引树 „ …… „ 增强求解复杂问题的能力 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 什么是数据结构 (data structure) „ 数据逻辑结构 „ 数据的存储结构 „ 数据的运算 数据 存储 结构 逻辑 运算 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 数据的逻辑结构 „ 二元组：( K ，R ) „ K是由有限个结点组成的集合 „ R是定义在集合K上的一组关系，其中 每个关系(relation) r（r∈R）都是 K×K上的二元关系 „ 数据结构中，只讨论R={r} 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 常见的逻辑关系 „ 线性结构 „ 树形结构 „ 图结构 „ 文件结构 图⊇树⊇二叉树⊇线性表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 结点的类型 „ 基本数据类型 „ 整数类型(integer) „ 实数类型(real) „ 布尔类型(boolean) „ 在C++语言中一般使用整数0表示 false，用非0表示true 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 结点的类型 „ 基本数据类型 „ 字符类型(char)：用单个字节（8bit，最高位 bit为0）表示ASCII字符集中的字符。 „ 汉字符号需要使用2个字节（每个字节的最高位 bit为1）的编码 „ Unicode，GB，Big5，HZ