数据结构第2章线性表--2.12.2南京工程学院通信工程学院.ppt

线性结构的特点：,第2章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加,其中数据元素的个数n定义为表的长度。 当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，an) 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。,线性表(Linear List) ：由 n (n0) 个数据元素 a1, a2, , an 组成的 有限并且有序的序列。,2.1 线性表的类型定义,例3、学生健康情况登记表如下：,线性表的抽象数据类型定义,2-1 利用两个线性表La和Lb分别表示两个集合A和B，现要求一个新的集合A=AB。,void union(List if(!LocateEem(La，e，equal) ListInsert(La，+La_len，e) ,例2-2 巳知线性表La和线性表Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的元素仍按值非递减有序排列。,void mergelist(list La，list Lb，list ,while(i=La_len) GetElem(La，i+，ai); ListInsert(Lc，+k，ai); while(j=Lb_len) GetElem(Lb，j+，bj); ListInsert(Lc，+k，bi); ,2.2 线性表的顺序表示和实现,线性表的顺序表示：在计算机中用一组地址连续的存储单元 依次存储线性表的各个数据元素，称作线性表的顺序存储结构或 顺序映象。用这种方法存储的线性表称作顺序表。,顺序表的特点：,以物理位置相邻表示逻辑关系。,任一元素均可随机存取。,顺序表的优点：,顺序表中数据元素存储位置的计算：,所有数据元素的存储位置均可由第一个数据元素的存 储位置得到： LOC(ai ) = LOC(a1) + (i -1) l,顺序表存储结构示意图,用数组表示线性表的顺序存储结构：,在高级程序设计语言中，通常利用数组来表示线性表的顺序 存储结构。这是因为数组具有如下特点： (1)、数组中的元素间的地址是连续的，有随机存取的特点； (2)、数组中所有元素的数据类型是相同的。 而这与线性表的顺序存储空间结构是类似的。,typedef struct ElemType dataMaxSize; int length; SqList; /*顺序表类型*/ 其中,data成员存放元素, length成员存放线性表的实际长度。 说明：由于C/C+中数组的下标从0开始，线性表的第i个元素ai存放顺序表的第i-1位置上。为了清楚，我们ai在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物理位序。,顺序表的存储结构,2.2.2 顺序表基本运算的实现,一旦采用顺序表存储结构,我们就可以用C/C+语言实现线性表的各种基本运算。,该运算的结果是构造一个空的线性表L。,1 初始化线性表InitList(L),本算法的时间复杂度为O(1)。,该方法是将给定的含有n个元素的数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度成员。,2 建立顺序表,void CreateList(SqList ,该方法在顺序表L的第i个位置(1iListLength(L)+1)上插入新的元素e。,3 插入数据元素ListInsert(L,i,e),插入数据元素算法实现,删除顺序表L中的第i(1iListLength(L)个元素。 如果i值不正确,则显示相应错误信息；否则将线性表第i个元素以后元素均向前移动一个位置,这样覆盖了原来的第i个元素,达到删除该元素的目的,最后顺序表长度减1。,4 删除数据元素ListDelete(L,i,e),删除数据元素算法实现,顺序表插入算法的时间复杂度分析,由此可见，在顺序表上做插入运算，平均要移动表上一半元 素。当表长 n 较大时，算法的效率相当低。算法的平均时间复杂 度为 O(n)。,算法的复杂度分析：,假设在表中任何位置(1 i n+1)上插入结点的机会是均等的， 则,假设在表中任何位置(1 i n)删除结点的机会是均等的，则,由此可见，在顺序表上做删除运算，平均约要移动表上一半 元素。当表长 n 较大时，算法的效率相当低。算法的