数据结构之线性表课件.ppt

数据结构 第二章 线性表 第二章 线性表 知 识 点 线性数据结构的基本特征和基本运算 线性表的存储结构 双向链表 循环链表 难 点 循环链表 利用本章的基本知识设计有效的算法解决与线性相关的应用问题 要 求 熟练掌握以下内容： 线性表的基本运算 线性表的特征、基本运算并能设计简单算法 了解以下内容： 线性表运算时间复杂性分析 第二章目录 2.1 线性表的逻辑结构 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 循环链表 2.5 双向链表 小 结 习题与练习 2 线性表（Linear List） 线性表是由有限数目的相同类型元素组成的序列。 表中的数据元素, 除了第一个和最后一个以外，都有一个且只有一个前驱元素，同时也都有一个且只有一个后继元素； 第一个元素只有一个后继元素而无前驱元素；最后一个元素只有一个前驱元素而无后继元素。 线性表的元素个数n称为这个表的长度，当n=0时，这个表叫做空表。 线性表在计算机内存中采用各元素顺序存储的方式，这种存储结构叫做向量。 每个线性表元素叫做这个向量的一个分量。 如果已知线性表第一个元素的地址和每个元素占用的存储单元数，由任一元素的序号就可以计算出该元素在内存中的地址。 在编程时以一维数组表示线性表最简单，用的也最普遍。 2.1线性表的逻辑结构 线性表的定义 例：Ａ＝｛Monday,Tuesday，Wednesday， Thursday，Friday，Saturday， Sunday｝ 又 Score={sdudent1，50，student2，60， student3，70} [注意]线性表和集合的区别。 线性表元素之间是有序的，而集合元素 之间是无序的。 2.1线性表的逻辑结构 线性表的定义 线性表是由n个结点a1，a2，…..,an 组成的有限序列，当n=0时，线性表为空，即为空表。 若n0, 则a1是第1个结点，an是最后一个结点。 其形式化的定义为： S=（D，R） 其中：D是由n个元素组成的集合， R是定义在集合D上的一种关系。 2.1线性表的逻辑结构 线性表的逻辑结构 线性表的元素类型是多样的，但同一线性表中的元素必须是同一类型，且相邻元素之间存在一种序偶关系。 2.1线性表的逻辑结构 线性表的基本运算： 1. 求线性表的长度n； 2. 在第i个数据元素前面插入一个新的数据元素； 3. 删除第i个数据元素； 4. 存取或更新线性表第i个元素； 5. 将两个或两个以上的线性表合并成一个线性表； 6. 将一个线性表拆成多个线性表； 7. 将线性表中各数据元素按某个域值（如关键字） 递增或递减的顺序重新排列； 8. 在线性表中查找满足某种条件的数据元素； 2.2 线性表的顺序存储 线性表的顺序存储结构(顺序表） 例：一顺序表 A=（3，6，8，9，2） 顺序存放在一维数组中 顺序存储的特点： 逻辑顺序与物理顺序一致， 元素之间的关系由物理位置的相邻关系体现 2.2 线性表的顺序存储 地址计算 设顺序表的每个元素占c个存储单元，并且元素所占的第一个单元的存储地址作为顺序表的存储位置，则顺序表中第I个元素的存储位置 Loc（ai）满足 Loc（ai）=Loc（ai-1）+ c Loc（ai）=Loc（a1）+（i-1）* c 2.2 线性表的顺序存储 结点描述 #define Maxlen 顺序表的最大长度 typedef struct seqenlist {elementtype elements [maxlen]; int lenth; } list; 顺序存储下线性表的运算 1. 数据