数据结构课件线性表顺序表.ppt
线 性 表程序=数据结构+算法数据结构的研究内容：数据结构的研究内容：逻辑结构：数据元素间的客观联系 存储结构：数据在计算机内部的存储方法 算法研究数据结构线性结构：线性表，栈，队列非线性结构：树，图 在各种程序设计与软件开发中都要涉及到对数据的组织、存储、管理和处理在环境领域：不同环境监测点的监测指标统计在土地领域：不同宗地的属性在测绘领域：外业测绘信息的存储，各测点三维坐 标的存储 最常见的数据组织方式：表格形式的数据编号名称SO2含量 水质指标悬浮物指标宗地号周长面积使用者土地等级点号等级XYH学号姓名性别籍贯年龄成绩2.1 线性表的基本概念和运算线性表的基本概念和运算2.1.1 逻辑结构定义逻辑结构定义定义定义：线性：线性表是由n（n0）个数据元素数据元素a1,a2,，an构成的有限序列有限序列。n为表的长度，n=0时称为空表。非空的线性表（n0）记作（a1,a2,，an）。数据元素可以有不同的含义，但同一线性表中的元素必须具有相同的特性。9119辽宁男李铁0220年龄87北京男杨晨01成绩籍贯性别姓名学号9520上海男祁宏30在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2(或没有后继)；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1(或没有前趋)；其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。2.1.2 线性表的线性表的ADT表示表示ADT List数据对象：L=ai|ai元素集合，i=1，2，n，n0数据关系：R=ai-1，ai|ai-1，ai元素集合，i=1，2，n基本操作：构造空表initList(&L)销毁线性表destroyList(&L)清空表 clearList(&L)求长度 listLength(L)取结点 getElem(L,index,&e)定位 locateElem(L,x)插入 insertElem(&L,index,e)删除deleteElem(&L,index,&e)取直接前趋 priorElem(L,cur_e,&prior_e)取直接后继 nextElem(L,cur_e,&next_e)2.1.3 线性表的运算线性表的运算清空表 clearList(&L)学号成绩clearList(list);取结点 getElem(L,index,&e)getElem(list,2,&e)序号成绩017802900384定位 locateElem(L,x)locateElem(list,84)=3学号成绩017802900384 插入 insertElem(&L,index,e)：在index位置插入值为e的元素 insertElem(list,3,87)学号成绩017802900384308390027801成绩学号833184048703 删除deleteElem(&L,index)deleteElem(list,3)学号 成绩017802900384298390027801成绩学号83308404870390027801成绩学号83308404 取直接前趋 priorElem(L,cur_e,&prior_e)取直接后继 nextElem(L,cur_e,&next_e)90027801成绩学号833084048703PRIOR(L,87)NEXT(L,87)对线性表的所有复杂操作都可以由以上操作完成对线性表的所有复杂操作都可以由以上操作完成e.g 清除线性表L中多余的重复结点 从i=1开始，每次取第i个元素getElem(L,i,&e)对第i个元素后的所有元素进行比较，若值相同则删除 判断完后将i+，继续执行，直到i=listLengh(L)Purge(Linear_List list)int i=1,j,x,y;while(ilistLength(list)getElem(list,i,&x);j=i+1;while(j”，不用“.”说明：用结构体类型定义指针 struct student stu-1;struct student*p;p=&stu-1;以下三种形式等价：(*p).成员名 p-成员名 结构体变量.成员名如(*p).age,p-age,stu-1.age等价 void clearList(sequencelist*pList)pList-length=0;void initList(sequencelist*pList)pList-length=0;2 插入运算序号成绩017802900384308390027801成绩序号833184048703a1a2ai-1aian-1an移动后a1a2ai-1aiai+1an插入前插入x下标0 1i-2i-1in-1lasta1a2ai-1xaian-1an插入后lastinsertElem(L,i,x)1 if(ilength+1)return wrong;2 for j=n to index step(-1)3 Lj+1=Lj4 end5 Li=x6 length=length+17 returna1a2ai-1aian-1an移动后a1a2ai-1aiai+1an插入前插入x下标0 1i-2i-1in-1lastint insertElem(sequencelist*pList,int index,datatype x)if(pList-length=maxsize)return 0;/溢出 if(index pList-length+1)/位置不合法 return 0;for(int i=pList-length ;i=index;i-)pList-datai=pList-datai-1;/元素后移 pList-dataindex-1=x;/把值写入index位置 +pList-length;/修改length return 1;3 删除运算序号 成绩017802900384298390027801成绩序号83308404870390027801成绩序号83308404a1a2ai-1ai+1an删除a1a2ai-1aiai+1an删除前删除x下标0 1i-2i-1in-1lasta1a2ai-1ai+1ai+2an删除后last算法描述：deleteElem(L,i)1 if(i length)return wrong;2 for j=i to n-13 Lj=Lj+14 end(j)5 length=length-1int deleteElem(sequencelist*pList,int index)if(index pList-length)return 0;for(int i=index;i length;i+)pList-datai-1=pList-datai;/元素前移 -pList-length;/修改length return 1;3 算法分析时间主要用于移动元素，与表长和操作位置有关。算法的时间复杂度为O(n)本节重点：1 线性表的定义及特点；2 顺序表的存储方式及算法实现，尤其是插入和删除的实现。作业：作业：1.对顺序表就地逆置；2.试写出一个高效算法，把顺序表中的所有重复元素移到表尾，返回表尾中第一个重复元素的位置（如没有重复元素，则返回 最后一个元素位置+1）。
