北京大学：《数据结构与算法》课程教学资源（实验班讲义）课程简介、概论

什么是数据结构 为什么要学习数据结构 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 北真大学张帖精写 聊张帖写 权新有,究 6

6 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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

结点的类型 结点的类型 基本数据类型 复合数据类型 指针类型( pointer):指向某一内存单元的地址 32bit机器,4个字节表示一个指针 基本数据类型/复合类型 64bit的机器,8指针 指针操作 数组intA[100] 分配地址 賦值(另一个指针的地址值,NUL空值) 比较两个指针地址 结构 typedef struct{}B 指针增减一个数量 class cifi 举位▲张倍墙写 北大单张铭写 叔新有,命邮 结点和结构 结构的分类 数据结构的设计一层一层地进行 ■对(KR)的分类,用R的性 先明确数据结点,及其主要关系r 质来刻划 ■对于复杂情况,再分析下一层次 线性结构( linear 的逻辑结构 structure) 自顶向下的分析设计方法 m树型结构( tree structure) a图结构( graph structure 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 线性结构 线性结构 应用最广泛,关系r是一种线性关系 ■图示法(注意与链表的图示区别开 大小关系 来) 关系r有向,全序性和单索性等约束条件 全序性:全部结点两两皆可以比较前后(关系r) 单索性:每一个结点y都存在唯一的直接后继结点z [[。区。区 北真大学张铭编写 聊张帖写 权新有,究

7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 结点的类型 „ 基本数据类型 „ 指针类型(pointer)：指向某一内存单元的地址 „ 32 bit机器，4个字节表示一个指针 „ 64bit的机器， 8指针 „ 指针操作 „ 分配地址 „ 赋值（另一个指针的地址值，NULL空值） „ 比较两个指针地址 „ 指针增减一个整数量 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 结点的类型 „ 复合数据类型 „ 基本数据类型/复合类型 „ 数组 int A[100]; „ 结构 typedef struct {} B; class C { }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 39 结点和结构 „ 数据结构的设计一层一层地进行 „ 先明确数据结点，及其主要关系r „ 对于复杂情况，再分析下一层次 的逻辑结构 „ 自顶向下的分析设计方法 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 结构的分类 „ 对（K,R）的分类，用R的性 质来刻划 „线性结构（linear structure） „树型结构（tree structure） „图结构（graph structure） 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 41 线性结构 „ 应用最广泛，关系r 是一种线性关系 „ ‘前后关系’ „ ‘大小关系’ „ 关系r有向，全序性和单索性等约束条件 „ 全序性：全部结点两两皆可以比较前后（关系r） „ 单索性：每一个结点y都存在唯一的直接后继结点z „ y -> z „ x -> … -> z „ 则x -> … y-> z „ x = y ？ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42 线性结构 „ 图示法（注意与链表的图示区别开 来） k0 Kn-2 k1 Kn-1 k…