武汉理工大学-信息工程学院-数据结构-ppt-课件ch02-1-线性表1-定义与顺序表示

第2章线性表数据结构讲义-定义与顺序表示信息工程学院魏洪涛Email:[e-mail]（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的逻辑结构1.线性表的定义：是n个数据元素的有限序列n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点例1分析26个英文字母组成的英文表（A,B,C,D,……,Z）学号姓名性别年龄班级2001011810205于春梅女182001级电信016班2001011810260何仕鹏男182001级电信017班2001011810284王爽女182001级通信011班2001011810360王亚武男182001级通信012班：：：：：例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性线性表的抽象数据类型的定义：ADTList{数据对象：D={ai|ai∈Elemset,i=1,2,…,n,n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…,n}基本操作：InitList(&l)操作结果：构造一个空的线性表LDestroyList(&l)初始条件：线性表已存在操作结果：销毁线性表LClearList(&l)初始条件：线性表已存在操作结果：置线性表L为空表ListEmpty(L)初始条件：线性表已存在操作结果：若线性表L为空表，则返回TRUE，否则返回FALSEListLenght(L)初始条件：线性表已存在操作结果：返回线性表L数据元素个数GetElem(L,i,&e)初始条件：线性表已存在（1≤i≤ListLenght(L)）操作结果：用e返回线性表L中第i个数据元素的值locatElem(L,e,compare())初始条件：线性表已存在,comare()是数据元素判定函数操作结果：返回线性表L中第1个与e满足关系compare()的数据元素的位序PriorElem(L,cur_e,&pre_e)初始条件：线性表已存在操作结果：若cur_e是线性表L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义NextElem(L,cur_e,&)初始条件：线性表已存在操作结果：若cur_e是线性表L的数据元素，且不是第最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义ListInsert(&L,i,e)初始条件：线性表已存在（1≤i≤ListLenght(L)+1）操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1ListDelete(&L,i,&e)初始条件：线性表已存在（1≤i≤ListLenght(L)）操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1ListTraverse(L,visit())初始条件：线性表已存在操作结果：依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，则操作失败}ADTList上述是线性表抽象数据类型的定义，其中只是一些基本操作，另外可以更复杂。如：将两个线性表合并等。复杂的操作可用基本操作实现。例2-2voidMergeList(Listla,Listlb,list&lc){IninList(lc);i=j=1;k=0;la_len=ListLength(la);lb_len=ListLength(lb);while(i=la_len&&j=lb_len){GetElem(la,i,ai);GetElem(lb,j,bj);if(ai=bj){ListInsert(lc,++k,ai);i++;}else{ListInsert(lc,k++,bj);j++;}}while(i=la_len){GetElem(la,i++,ai);ListInsert(lc,k++,ai);}while(j=lb_len){GetElem(lb,j++,bj);ListInsert(lc,k++,bj);}}线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。2.2.1顺序表的表示2.2线性表的顺序表示和实现线性表顺序存储特点：1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是：设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai)=LOC(a1)+L*（i-1）LOC(ai+1)=LOC(ai)+L线性表的顺序存储结构示意图a1a2……aiai+1……an地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)L一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是113例1因此：LOC(M[3])=98+5×(3-0)=113解：地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）线性表的顺序存储结构定义（静态）#defineMAXSIZE100typedefstruct{ElemTypeelem[MAXSIZE];intlength;}SqList;2.2.2顺序表的实现（或操作）数据结构基本运算操作有：初始化、插入、删除、查找、排序、修改1）初始化：StatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}2)插入在线性表的第i个位置前插入一个元素实现步骤：•将第n至第i位的元素向后移动一个位置；•将要插入的元素写到第i个位置；•表长加1。注意：事先应判断:插入位置i是否合法?表是否已满?长度为n的线性表变为长度为n+1的线性表（a1,a2,…,ai-1,ai,…,an）（a1,a2,…,ai-1,x,ai,…,an）程序：StatusListInsert_sq(SqList&l,inti,elemtypex){if(i0||il.length)return(ERROR);if(l.length==MAXSIZE)return(OVERFLOW);for(j=l.length;j=i;j--)l.elem[j]=l.elem[j-1];l.elem[j]=x;l.length++;return(OK);}顺序表插入的演示实现步骤：将第i+1至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法?3)删除删除线性表的第i个位置上的元素使：长度为n的线性表变为长度为n-1的线性表。（a1,a2,…,ai-1,ai,ai+1,…,an）（a1,a2,…,ai-1,ai+1,…,an）StatusListDelete_sq(Sqlist&L，inti,ElemType&e){if(i1||iL.length)returnERROR;for(j=i;j=L.length-1;j++)L.elem[j-1]=L.elem[j];L.length--;}顺序表删除的演示删除顺序表中某个指定的元素的代码和示意图如下：4)顺序表的合并参见例【2-2】2.2.3顺序表的运算效率分析时间效率分析:插入算法花费的时间，主要在于循环中元素的后移。但是，插入的位置是不固定的，当插入位置i=1时，全部元素都得移动，需n次移动，当i=n时，不需移动元素，故在i位置插入时移动次数为n-i+1。删除算法花费的时间，主要在于循环中元素的前移.但是，删除的位置是不固定的，当删除位置i=1时，全部元素都得移动，需n-1次移动，当i=n时，不需移动元素，故在i位置删除时移动次数为n-i-1.假定在表中任意位置插入、删除元素都是等概率的，插入概率p(i)=1/(n+1)，删除概率q(i)=1/n，则：插入操作时间效率（平均移动次数）2)1(11)1(1111ninninpEniniiis删除操作时间效率（平均移动次数）21)(1)(11ninninqEniniidl显然，顺序表的空间复杂度S(n)=O(1)（没有占用辅助空间）本节小结线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素O(1)；存储空间使用紧凑缺点：在插入，删除某一元素时，需要移动大量元素O(n);预先分配空间需按最大空间分配，利用不充分;表容量难以扩充为克服这一缺点，我们引入另一种存储形式：链式存储结构作业&实验：表的应用一、实验目的：掌握线性表的基本结构和操作方法，培养学生灵活使用结构解决实际问题的能力。二、实验内容：一条记录有学号和成绩两个数据项，建立两个有序表（按成绩由大到小），并合并成一个有序表。第一个表输入的数据如下（学号，成绩）：(1,70),(2,85),(3,75),(4,90)；第二个表输入的数据如下：(5,60),(6,80),(7,76),(8,50)。ch1_stable.c