数据结构课件-线性表顺序表

线 性 表 程序 = 数据结构+算法数据结构的研究内容： 逻辑结构：数据元素间的客观联系 存储结构：数据在计算机内部的存储方法 算法研究数据结构线性结构：线性表，栈，队列非线性结构：树，图 在各种程序设计与软件开发中都要涉及到对数据的组织、存储、管理和处理在环境领域：不同环境监测点的监测指标统计在土地领域：不同宗地的属性在测绘领域：外业测绘信息的存储，各测点三维坐 标的存储 最常见的数据组织方式：表格形式的数据编号名称SO2含量水质指标悬浮物指标宗地号周长面积使用者土地等级 点号等级X Y H学号姓名性别籍贯年龄成绩 2.1 线性表的基本概念和运算2.1.1 逻辑结构定义定义：线性表是由n（n0）个数据元素a1,a2,，an构成的有限序列。n为表的长度，n=0时称为空表。非空的线性表（n0）记作（ a1,a2,，an ）。 数据元素可以有不同的含义，但同一线性表中的元素必须具有相同的特性。 9119辽宁男李铁02 20年龄87北京男杨晨01成绩籍贯性别姓名学号9520上海男祁宏30 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2(或没有后继)；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1 (或没有前趋) ；其余的内部结点ai(2 i n-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( 取结点 getElem(L, index, while(ilistLength(list) getElem(list, i, j=i+1; while(j”，不用“.” 说明：用结构体类型定义指针 struct student stu-1; struct student *p; p= 以下三种形式等价： (*p).成员名 p-成员名 结构体变量.成员名如(*p).age, p-age, stu-1.age等价 void clearList(sequencelist * pList) pList - length = 0; void initList(sequencelist * pList) pList - length = 0; 2 插入运算序号成绩01 7802 9003 84 30 83 9002 7801成绩序号8331 8404 8703 a1a2ai-1aian-1a n 移动后a1a2ai-1aiai+1a n 插入前插入x下标0 1i-2i-1in-1last a1a2ai-1xaia n-1an 插入后last insertElem(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 return a1a2ai-1aia n-1an 移动后a1a2ai-1aiai+1a n 插入前插入x下标0 1i-2i-1in-1last int 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 删除运算序号成绩01 7802 9003 84 29 839002 7801成绩序号8330 8404 8703 9002 7801成绩序号8330 8404 a1a2ai-1ai+1an删除a1a2ai-1aiai+1an删除前删除x下标0 1i-2i-1in-1last a1a2ai-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-1 int 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 ）。