国家级精品课程—《数据结构与算法》 第2章线性表 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.ipk.pku.edu.cn/pkuipk/courselsig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:赵海燕 版权所有,转载或翻印必究
国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：赵海燕 ©版权所有，转载或翻印必究 第2章 线性表
主要内容 21线性表的概念 22顺序表 23链表 24线性表实现方法的比较 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 2.1 线性表的概念 ◼ 2.2 顺序表 ◼ 2.3 链表 ◼ 2.4 线性表实现方法的比较
问题求解 线性结构 顺序表 链表 线性表实现方法的比较 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。3
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 3 问题求解 ◼ 线性结构 ◼ 顺序表 ◼ 链表 ◼ 线性表实现方法的比较
线性结构 元素间满足线性关系 口“一对一”的关系 a按此关系结构中的所有元素排成一个线性序列 元组B=K,R), K={ao,a1,…,an-1},R={r}: 口结点集K中有一个唯一的开始结点,它没有前驱,但有一个 唯一的后继; 口对于有限集K,它存在一个唯一的终止结点,该结点有一个 唯一的前驱而没有后继 口其它的结点皆称为内部结点,每二个内部结点都有且仅有 个唯一的前驱,也有一个唯一的后继 yn-1 <a;a1>a是a的前驱,a+是a的后继 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。4
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 4 线性结构 ◼ 元素间满足线性关系 ❑ “一对一”的关系 ❑ 按此关系结构中的所有元素排成一个线性序列 ◼ 二元组B = (K, R) , K = {a0 , a1 , …, an-1 }, R = {r} ： ❑ 结点集K中有一个唯一的开始结点，它没有前驱，但有一个 唯一的后继； ❑ 对于有限集K , 它存在一个唯一的终止结点，该结点有一个 唯一的前驱而没有后继； ❑ 其它的结点皆称为内部结点，每一个内部结点都有且仅有一 个唯一的前驱，也有一个唯一的后继； a0 , a1 , …, an-1 < ai , ai+1> ai是ai+1的前驱， ai+1是ai的后继
线性结构 特点: 均匀性:虽然不同线性表的数据元素可以是各种 各样的,但对于同一线性表的各数据元素必定具 有相同的数据类型和长度 口有序性:各数据元素在线性表中都有自己的位置, 且数据元素之间的相对位置是线性的 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。5
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5 线性结构 ◼ 特点： ❑ 均匀性：虽然不同线性表的数据元素可以是各种 各样的，但对于同一线性表的各数据元素必定具 有相同的数据类型和长度 ❑ 有序性：各数据元素在线性表中都有自己的位置， 且数据元素之间的相对位置是线性的