结点的类型 结点的类型 基本数据类型 复合数据类型 指针类型( 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…