l第02章线性表.pptVIP

第二章 线性表 教学目的与要求 本章目的是介绍线性表的逻辑结构和存储结构，以及定义在逻辑结构上的各种基本运算和这些基本运算在存储结构上的实现（即算法）。要求学生在掌握这些内容的基础上，能够针对具体应用问题的要求和性质，选择恰当的存储结构设计出相应的有效上算法，解决与线性表相关的实际问题。 教学重点和难点 本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析。难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。 线性结构特点： 在数据元素的非空有限集中: 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继 2.1 线性表的逻辑结构 定义：一个线性表是n(n≥0)个数据元素的有限序列。其中，数据元素的个数定义为表长。当n＝0时线性表称为空表，非空线性表通常记为(a1，a2，…，an) 。 线性表的基本运算： InitList(L) 线性表的初始化，即构造一个空表。 ListLength(L) 求表长，即求线性表L中的元素个数。空表的长度为0。 GetNode(L,i) 取线性表中的第i元素，要求 1≤i≤ListLength(L)。 Locate(L,x) 在线性表L中查找值为x的元素，并返回该元素在线性表L中的位置 InsertList(L,x,i) 在线性表的第i个位置插入新元素x。插入后的表长加1。 DeleteList(L,i) 删除线性表L的第i个元素，删除后的表长减1。 上述运算并不是线性表的全部运算。对于实际问题中涉及的其他更为复杂的运算，可以用基本运算的组合来实现。 2.2 线性表的顺序表示和实现 顺序表： 定义：采用顺序存贮方法，把线性表中的元素按逻辑次序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表即为线性表的顺序标示,简称为顺序表。 元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L—一个元素占用的存储单元个数 LOC(ai)—线性表第i个元素的地址 特点： 实现逻辑上相邻—物理地址相邻 实现随机存取 顺序表在程序设计语言上的表示 ： 程序设计语言中的一维数组也是采用顺序存储，故可用数组存储线性表中的元素，用一个变量来表示线性表的长度。把这二者结合起来构成结构类型作为顺序表在程序设计语言环境下的实现。定义如下： 顺序表上基本运算的实现 (1)插入算法insertlist(Seqlist *L,Datatype x,int I) 算法思想： 判断上溢和i值合法性，即1≤i≤n +1； 将第i个到第n个元素从后往前依次后 移； 将元素插入第个位置； 表长加1。 算法： void insertlist(Seqlist *L,Datatype x,int i) {//将新结插入L所指的顺序表的第i个结点之前 int j; if (i1||iL-length+1||L-length＝Listsize) error(〞position error or overflow〞); for (j＝L-legth-1;j＝i-1;j--) L-data[j+1]＝L-data[j]; L-data[i-1]＝x; l-length++; } 时间特性分析T(n)： 影响算法时间特性的主要因素是元素的后移，插入位置不同，后移操作的次数也不同。最好情况是在表末插入，不需要移动元素，时间复杂度是O（1）；最坏情况是在表头插入，需要移动全部n个元素，最坏时间复杂度是O（n）；通常，我们通过计算元素的来反映算法时间特性。 在长度为n的线性表中第i个元素前插入一个元素，须移动n-i+1个元素，考虑不同位置的插入概率pi，移动平均次数（移动次数的数学期望值）为： （2）删除算法Deletelist(seqlist *L,int i) 算法思想： 判断i值合法性，即1≤i≤n； 将第i+1个到第n个元素从前往后依次前移； 表长减1。 算法： void Deletelist(Seqlist *L,int i) {//删除L所指的顺序表的第i个结点 int j; if (i1||iL-length) error(〞position error〞); for (j＝i;j＝L-length-1;j++) L-data[j-1]＝L-data[j+1]; L-data[i-1]＝x; l-length--; } 时间特性分析： 删除算法的时间复杂度与插入算法的时间度基本相似，最好情况是删除表末元素，不需要移动元素，时