数据结构幻灯片第2章线性表a

1,上堂课要点回顾,数据结构课程涉及数学、计算机硬件和计算机软件 数据结构定义指互相有关联的数据元素的集合，用D_S=( D, S ) 表示。 数据结构内容数据的逻辑结构、存储结构和运算 算法效率指标时间效率和空间效率,2,数据结构课程的内容,逻辑结构唯一 存储结构不唯一 运算的实现依赖于存储结构,3,近3周 上课 内容,第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表,线性结构,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。,可表示为：（a1 , a2 , , an）,线性结构的定义：,（逻辑、存储和运算）,4,第二章 线性表 学习指南,【学习目标】 1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 4. 结合线性表类型的定义增强对抽象数据类型的理解。,5,【重点和难点】 链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。 【知识点】 线性表、顺序表、链表 【学习指南】 本章建议完成的算法设计题为：2.11，2.21，2.19，2.22，2.24，2.27，2.28，2.38,第二章 线性表 学习指南(续),6,线性结构的特点：, 只有一个首结点和尾结点； 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构表达式：（a1 , a2 , , an）,线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是-,线性表,简言之，线性结构反映结点间的逻辑关系是 一对一 的,见第2章,7,第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加,8,线性表：由一组数据组成，线性表或者是一个空表，或者可以写成（a1,a2,ai,an）,其中ai是取自某个集合S的元素。当1in时，数据元素ai-1称为数据元素ai的直接前驱，而称ai+1为ai的直接后继。线性表中数据元素的个数称为该线性表的长度。,2.1 线性表的类型定义,9,（a1, a2, ai-1，ai, ai1 ，, an）,1. 线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,线性终点,10,形式化定义： Linearlist = (D, R),其中：,D0为某个数据对象的集合 N为线性表长度,11,线性表的主要操作,初始化 求长度 取元素 定位 插入 删除,12,对线性表可进行如下基本运算： InitList(&L)：构造一个空的线性表L。 ListLength(&L)：返回L数据元素的个数。 GetElem(L,i,&e)：用e返回L中第i个数据元素的值。 ListInsert(&L,i,e)：在L中第i个位置前插入新的数据元素e，L的长度加1。 ListDelete(&L,i,&e)：删去L中第i个元素，用e返回其值，L的长度减1。 PriorElem(L,cur_e,&pre_e)：用pre_e返回数据元素cur_e的前驱，如果存在的话。 NextElem(L,cur_e,&next_e)：用next_e返回数据元素cur_e的后继，如果存在的话。 LocateElem(L,e,compare()：返回L中第一个与e满足关系compare()的数据元素的位序。0表示这种元素不存在。,13,例1 分析26 个英文字母组成的英文表,（ A, B, C, D, , Z）,例2 分析学生情况登记表,数据元素都是记录; 元素间关系是线性,数据元素都是字母; 元素间关系是线性,同一线性表中的元素必定具有相同特性,14,例3、学生健康情况登记表如下：,15,例4、一副扑克的点数 （2，3，4，J，Q，K，A）,16,从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1； 其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。,17,线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。 抽象数据类型的定义为：P19,18,算法2.1 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。 void union(List if(!LocateElem(La，e，equal) ListInsert(La，+La-len，e) / for ,19,算法2.2 p21 例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 此问题的算法如下：,20,void MergeList(list la，list lb，list / while,21,while(I=la-len) getelem(la，I+，ai);listinsert(lc，+k，ai); /while 处理la表 while(j=lb-len) getelem(lb，j+，bj);listinsert(lc，+k，bi); / while 处理lb表 / MergeList,22,练：判断下列叙述的正误：,1. 数据的逻辑结构是指数据元素之间的逻辑关系，是用户按使用需要建立的。 2. 线性表的逻辑结构定义是唯一的，不依赖于计算机。 3. 数据结构是指相互之间存在一种或多种关系的数据元素的全体。 4. 线性结构反映结点间的逻辑关系是一对一的。 一维向量是线性表，但二维或N维数组不是。 “同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。,23,2.2 线性表的顺序表示和实现,2.2.1 顺序表的表示 2.2.2 顺序表的实现 2.2.3 顺序表的运算效率分析,本节小结,作 业,24,2.2.1 顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素，可通过数组Vn来实现。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,简言之，逻辑上相邻，物理上也相邻,25,线性表顺序存储特点：,1. 逻辑上相邻的数据元素，其物理上也相邻； 2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是（参见存储结构示意图）： 设首元素a1的存放地址为LOC(a1)（称为首地址）， 设每个元素占用存储空间（地址长度）为L字节， 则表中任一数据元素的存放地址为： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai)+L,注意：C语言中的数组的下标从0开始， 即：Vn的有效范围是V0Vn-1,26,线性表的顺序存储结构示意图,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,27,一个一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是,113,例1,因此：LOC( M3 ) = 98 + 5 ×(3-0) =113,解：地址计算通式为：,LOC(ai) = LOC(a1) + L *（i-1）,28,用数组V来存放26个英文字母组成的线性表（a，b，c，z），写出在顺序结构上生成和显示该表的C语言程序。,void build() /*字母线性表的生成，即建表操作*/ int i; V0='a' for(i=1;i=n-1;i+) Vi=Vi-1+1; ,核心语句： 法1 Vi= Vi-1+1; 法2 Vi=a+i; 法3 Vi=97+i;,例2,29,void main(void) /*主函数，字母线性表的生成和输出*/ n=26; /* n是表长，是数据元素的个数，而不是V的 实际下标*/ build(); display(); ,void display() /*字母线性表的显示，即读表操作*/ int i; for(i=0;i=n-1;i+) printf(“%c“,Vi); printf(“n“); ,执行结果： a b c d e f g h i j k l m n o p q r s t u v w x y z,30,2.2.2 顺序表的实现（或操作）,回忆：数据结构基本运算操作有： 修改、插入、删除、查找、排序,1) 修改 通过数组的下标便可访问某个特定元素并修改之。,核心语句: Vi=x;,显然，顺序表修改操作的时间效率是T(n)=O(1),31,2)插入 在线性表的第i个位置前插入一个元素,实现步骤： 将第n至第i 位的元素向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。 注意：事先应判断: 插入位置i 是否合法?表是否已满? 应当有1in+1 或 i=1,n+1,for (j=n;j=i;j-) aj+1=aj; ai=x; n+;,/ 元素后移一个位置,/ 插入x,/ 表长加1,核心语句：,32,由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。用结构类型来定义顺序表类型。 # define ListSize 100 typedef int DataType; typedef struc DataType dataListSize; int length; Sqlist;,33,线性表的插入运算是指在表的第I(1in+1)个位置上，插入一个新结点x，使长度为n的线性表 (a1，a i-1，ai，an) 变成长度为n+1的线性表 (a1，a i-1，x，ai，an),34,算法2.3 P23 Void InsertList(Sqlist*L，DataType x，int I) int j; if(Il.length+1) printf(“Position error”); return ERROR ;,35,if(L.length=ListSize) printf(“overflow”); exit(overflow); for(j=L.length-1;j=I-1;j-) L.dataj+1=L.dataj; L.dataI-1=x; L.length+; ,36,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,37,实现步骤： 将第i 至第n 位的元素向