数据结构02-线性表.ppt

数 据 结 构 Data Structures,安海忠 博士,中国地质大学（北京）人文经管学院 院长 教授 博士生导师 国土资源部资源环境承载力评价重点实验室 主任,电话：01082323793（办）电邮：,教学内容,第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第六章 树和二叉树 第七章 图 第九章 查找 第十章 内部排序,第二章 线性表,2.1 线性表的定义 2.2 用数组实现线性表（顺序表） 2.3 用指针实现线性表（链表） 2.4 循环链表 2.5 用双链表示线性表（双向链表） 2.6 线性表的应用：一元多项式的表示及相加,第二章 线性表,学习重点,线性结构的特点 熟练掌握两种存储结构的描述方法。链表是本章的重点和难点 熟练掌握顺序表的定义与实现，包括查找、插入、删除算法的实现 熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构,2.1 线性表的定义,线性表L是n(n=0)个相同类型数据元素a1, ，an-1 , an构成的有限序列。 表示成:L= (a1, ，an-1 , an ) 形式化定义： Linearlist = (D, R),其中：,D0为某个数据对象的集合 n为线性表长度,2.1 线性表的定义,（a1, a2, ai-1，ai, ai1 ，, an）,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,线性终点,2.1 线性表的定义,表长-线性表中元素的个数(n),n=0为空表 直接前驱-线性表中ai-1是ai的直接前驱元素，a1无直接前驱 直接后继-线性表中ai+1是ai的直接后继元素，an无直接后继 在线性表中加上一些运算，才可以构成一个抽象数学模型List,2.1 线性表的定义,例 分析26 个英文字母组成的英文表,（ A, B, C, D, , Z）,例 分析学生情况登记表,数据元素都是记录; 元素间关系是线性,数据元素都是字母; 元素间关系是线性,同一线性表中的元素必定具有相同特性,2.1 线性表的定义,2.1 线性表的定义,2.2 用数组实现线性表（顺序表）,线性表的顺序表示又称为顺序存储结构或顺序映像 逻辑上相邻，物理上也相邻 用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）,线性表 (a1,a1,a2,.an)顺序存储结构的一般形式 序号 存储状态 存储地址 1 b 2 b+p i b+(i-1)*p n b+(n-1)*p 自由区 maxleng b+(maxleng-1)*p 其中: b-表的首地址/基地址/元素a1的地址。 p-1个数据元素所占存储单元的数目。 maxleng-最大长度,为某个常数。,2.2 用数组实现线性表（顺序表）,线性表顺序结构在C语言中的定义 其中：SqList-结构类型名 La-结构类型变量名 La.length-表长 La.elem0-a1 La.elemLa.length-1-an,#define maxleng 100 struct SqList ElemType elemmaxleng;/下标:0,1,.,maxleng-1 int length; /表长 ; SqList La;,2.2 用数组实现线性表（顺序表）,顺序存储结构的寻址公式 i= 1 2 i n 地址= b b+p b+(i-1)p b+(n-1)p 假设: 线性表的首地址为b,每个数据元素占p个存储 单元,则表中任意元素ai(1in)的存储地址是: LOC(i)=LOC(1)+(i-1)*p =b+(i-1)*p (1in) 例: 假设 b=1024, p=4,i=35 LOC(i)=b+(i-1)*p =1024+(35-1)*4 =1024+34*4 =1160,2.2 用数组实现线性表（顺序表）,在表中插入元素x插入算法,2.2 用数组实现线性表（顺序表）,插入算法,2.2 用数组实现线性表（顺序表）,插入算法,2.2 用数组实现线性表（顺序表）,插入算法,2.2 用数组实现线性表（顺序表）,插入算法,2.2 用数组实现线性表（顺序表）,在表中删除元素删除算法,2.2 用数组实现线性表（顺序表）,删除算法,2.2 用数组实现线性表（顺序表）,删除算法,2.2 用数组实现线性表（顺序表）,删除算法,2.2 用数组实现线性表（顺序表）,删除算法,2.2 用数组实现线性表（顺序表）,顺序存储结构的评价 优点： (1)是一种随机存取结构，存取任何元素的时间是一个常数，速度快； (2)结构简单，逻辑上相邻的元素在物理上也是相邻的； (3)不使用指针，节省存储空间。 缺点： (1)插入和删除元素要移动大量元素，消耗大量时间； (2)需要一个连续的存储空间； (3)插入元素可能发生“溢出”； (4)自由区中的存储空间不能被其它数据共享,2.3 用指针实现线性表（链表）,顺序表：随机存取 链表：逻辑相邻，物理不一定相邻 特点 每个元素(表项)由结点(Node)构成。 线性结构 结点可以不连续存储 表可扩充 适用于存储空间需求不定、插入或删除频繁的情形,data next,a0,a1,a2,a3,a4,first,2.3 用指针实现线性表（链表）,free,(a) 可利用存储空间,a0,a2,a1,a3,free,first,(b) 经过一段运行后的单链表结构,单链表的存储映像,2.3 用指针实现线性表（链表）,2.3.1 线性链表,用一组任意的存储单元存储线性表的数据元素，可以是零散分布在内存中的任意位置上的。链表中结点的逻辑次序和物理次序不一定相同。 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的地址（或位置）信息，这个信息称为指针(pointer)或链(link) 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置,线性链表,31,ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG,H,例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,31,H,头指针,线性链表,结点：数据元素的存储映像。由数据域和指针域两部分组成 链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。 单链表、双链表、循环链表： 结点只有一个指针域的链表，称为单链表或线性链表； 有两个指针域的链表，称为双链表； 首尾相接的链表称为循环链表。,2.3 用指针实现线性表（链表）,线性链表,2.3 用指针实现线性表（链表）,头指针、头结点和首元结点 头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 单链表可由一个头指针唯一确定。 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息; 首元结点是指链表中存储线性表第一个数据元素a1的结点,线性链表,上例链表的逻辑结构示意图有以下两种形式：,ZHAO,QIAN,LI,SUN,ZHOU,WU,ZHENG,/,WANG,H,ZHAO,QIAN,LI,SUN,ZHOU,WU,ZHENG,/,WANG,H,区别： 无头结点 有头结点,线性链表,2.3 用指针实现线性表（链表）,查找链表中某个元素,2.3 用指针实现线性表（链表）,在链表中插入元素,2.3 用指针实现线性表（链表）,在第一个结点前插入 newnode-next = first ; first = newnode;,在链表中插入元素,2.3 用指针实现线性表（链表）,在链表中间插入 Newnode-next=current-next current-next = newnode；,在链表中插入元素,2.3 用指针实现线性表（链表）,在链表中插入元素,2.3 用指针实现线性表（链表）,在链表末尾插入 current-next = newnode； Newnode-next=null,在链表中删除k处的元素x,2.3 用指针实现线性表（链表）,在链表中删除k处的元素x,2.3 用指针实现线性表（链表）,单链表的特点,2.3 用指针实现线性表（链表）,单循环链表,2.4 循环链表(Circular List),循环链表：首尾相接的链表 单循环链表：在单链表中，将终点的指针域NULL改为指向第一个结点，也可以设置一个头结点,单循环链表的各种算法与单链表基本一样，只是循环条件不同,双向链表,2.5 用双链表示线性表（双向链表）,双向循环链表,2.5 用双链表示线性表（双向链表）,双向链表运算：删除,2.5 用双链表示线性表（双向链表）,双向链表运算：插入,2.5 用双链表示线性表（双向链表）,一元多项式,2.6 线性表的应用：一元多项式的表示与相加,一元多项式,2.6 线性表的应用：一元多项式的表示与相加,一元多项式,2.6 线性表的应用：一元多项式的表示与相加,一元多项式,2.6 线性表的应用：一元多项式的表示与相加,本章小结,理解线性表的概念：同一类型的元素组成的有限系列 熟悉定义在线性表上的基本运算：查找、插入、删除 掌握实现线性表的一般步骤 掌握用数组实现线性表的步骤和方法 掌握用指针实现线性表的步骤和方法 掌握单循环链表的实现方法 掌握双向链表的实现方法,作业1,小娜和小丽喜欢游戏，准备开始一个新游戏。在一条直线上放置了n个巧克力棒，小娜从左到右吃，小丽从右到左吃。两个人同时开始吃，且吃的速度是一样的。当玩家吃饭一根巧克力棒后，立即吃下一