第二章顺序表

07:17,1,上章课要点回顾,数据结构定义数据结构内容算法效率指标,指互相有关联的数据元素的集合，用D_S=(D,S)数据的逻辑结构、存储结构和运算时间效率和空间效率,2,数据结构课程的内容,逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构,3,近3周上课内容,第2章线性表第3章栈和队列第4章串第5章数组和广义表,线性结构,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。,可表示为：（a1,a2,an）,线性结构的定义：,（逻辑、存储和运算）,4,线性结构的特点：,只有一个首结点和尾结点；除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构表达式：（a1,a2,an）,线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是-,线性表,简言之，线性结构反映结点间的逻辑关系是一对一的,见第2章,5,第2章线性表,2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例（一元多项式的表示及相加）,作业,6,（a1,a2,ai-1，ai,ai1，,an）,2.1线性表的类型定义,1.线性表的定义：是零个或多个元素的有穷序列，通常可以表示为：,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,线性终点,线性表的逻辑结构可以用二元组=来表示，其中K=a0,a1,an-1R=|0in-2,7,例子,（1，2，3，4，.，9，10）,8,数据元素都是数字;元素间关系是线性,9,例2分析26个英文字母组成的英文表,（A,B,C,D,Z）,例3分析学生情况登记表,数据元素都是记录;元素间关系是线性,数据元素都是字母;元素间关系是线性,同一线性表中的元素必定具有相同特性,10,11,12,13,14,（a1,a2,ai-1，ai,ai1，,an）,这里的数据元素ai（1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。,2线性表的特征从线性表的定义可以看出线性表的特征：（1）有且仅有一个开始结点(表头结点)a1，它没有直接前驱，只有一个直接后继;（2）有且仅有一个终端结点(表尾结点)an，它没有直接后继，只有一个直接前驱;（3）其它结点都有一个直接前驱和直接后继；（4）元素之间为一对一的线性关系。线性表是一种典型的线性结构,线性表是一种典型的线性结构，用二元组表示为：linear_list=(A,R)其中A=ai1in,n0,aielemtypeR=rr=1in-1,对应的逻辑结构图如图2-1所示。,线性表的运算,常见线性表的运算有：1置空表SETNULL（V0=a;for(i=1;i=i;j-)L.aj+1=L.aj;/元素后移L.ai=x;/插入元素L.len+;/表长度增加1,核心语句：,31,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,插入运算Insert(j=L.len;j+)L.aj-1=L.aj;/元素前移L.len-;/表长度减1,34,删除顺序表中某个指定的元素的示意图如下：,删除运算Delete(若在an-1后面插入，要后移1个元素；若在尾结点an之后插入，则后移0个元素；所有可能的元素移动次数合计：0+1+n=n(n+1)/2,所以平均移动次数为：n(n+1)/2（n+1）n/2O(n),共有多少种插入形式?连头带尾有n+1种,同理可证：顺序表删除一元素的时间效率为:T（n)=(n-1)/2O(n),39,本节小结,线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素；缺点：在插入，删除某一元素时，需要移动大量元素。为克服这一缺点，我们引入另一种存储形式：,链式存储结构,见2.3节,练习,1.在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。2.线性表中结点的集合是的，结点间的关系是的。3.向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时，需向后移动个元素。4.向一个长度为n的向量中删除第i个元素(1in)时，需向前移动个元素。5.在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表也称为的数据结构。,40,表中一半,表长和该元素在表中的位置,有限,一对一,n-i+1,n-i,O(1),随机存取,单项选择题（）1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110（B）108（C）100（D）120（）3.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A)访问第i个结点（1in）和求第i个结点的直接前驱(2in)(B)在第i个结点后插入一个新结点（1in）（C）删除第i个结点（1in）（D）将n个结点从小到大排序（）4.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8（B）63.5（C）63（D）7,41,C,B,A,B,42,作业：,自行上机练习题：设有线性表LA（3,5,8,11）和LB=（2,6,8,9,11,15,20）；若LA和LB分别表示两个集合A和B，求新集合AA