第二章线性表、栈和队列 张铭 http://db.pku.edu.cn/mzhang/ds 北京大学信息科学与技术学院 数据结构与算法”教学小组 版权所有,转载或翻印必究
第二章 线性表、栈和队列 张铭 http://db.pku.edu.cn/mzhang/DS/ 北京大学信息科学与技术学院 “数据结构与算法 ”教学小组 ©版权所有，转载或翻印必究
资源提示 作业提交ftp更改 实验班作业提交 ftp:/dshonoradsoZhonor@fusiongrids.cn 实习课作业提交 tp:/dsproi:dso7proi@fusion,grids.cn 讲义和作业发布不变 实验班讲义和作业发布(包括实习作业) http://db.pku.edu.cn/mzhang/ds/honor/ 实习课讲义和作业发布 http:/db.pkuedu.cn/mzhang/ds/shixil back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 2
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 back next 资源提示 作业提交ftp更改 实验班作业提交 ftp://ds_honor:ds07honor@fusion.grids.cn 实习课作业提交 ftp://ds_proj:ds07proj@fusion.grids.cn 讲义和作业发布不变 实验班讲义和作业发布（包括实习作业） http://db.pku.edu.cn/mzhang/ds/honor/ 实习课讲义和作业发布 http://db.pku.edu.cn/mzhang/DS/shixi/
大纲 21线性表( linear list 令22顺序表一向量( Sequential list vector) 令23链表( Linked list) 令24线性表实现方法的比较 令25栈( Stack) 令26队列( Queue) back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 3
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 back next 大纲 2.1 线性表(linear list) 2.2 顺序表—向量(Sequential list— vector ) 2.3 链表(Linked list) 2.4 线性表实现方法的比较 2.5 栈(Stack) 2.6 队列(Queue)
线性结构分类 线性结构 直接访问型 顺序访问型 目录索引型 向量 记录 字典 散列表 顺序文件 广义表 栈 队列
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 back next 线性结构分类 线性结构 直接访问型 顺序访问型 目录索引型 向 量 记 录 字 典 散列表 栈 队 列 顺序文件 广义表
21线性表( linear list 逻辑定义:由结点集N,以及定义在结点集N 上的线性关系r所组成的线性结构 n结点:线性表的元素 唯一的起点:没有前驱,有一个唯一的后继 n唯一的终点:有一个唯一的前驱而没有后继 n内部结点:有唯一的前驱,唯一的后继 结点个数:线性表的长度 线性表的关系r,简称前驱关系 back 反对称性、传递性 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 5
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 back next 2.1 线性表(linear list) 逻辑定义：由结点集N，以及定义在结点集 ，以及定义在结点集N 上的线性关系r所组成的线性结构 所组成的线性结构 结点：线性表的元素 结点：线性表的元素 唯一的起点：没有前驱，有一个唯一的后继 唯一的起点：没有前驱，有一个唯一的后继 唯一的终点：有一个唯一的前驱而没有后继 唯一的终点：有一个唯一的前驱而没有后继 内部结点：有唯一的前驱，唯一的后继 内部结点：有唯一的前驱，唯一的后继 结点个数：线性表的长度 结点个数：线性表的长度 线性表的关系r，简称前驱关系 ，简称前驱关系 反对称性、传递性 反对称性、传递性