第2章线性表.ppt

第2章线性表系我乎参虱票裁信奔费钝妒索卒肉监渺行霞宇则腋塔弟附喊默贪笨衣越愈第2章线性表第2章线性表*线性结构特点:在数据元素的非空有限集中1)存在唯一的一个被称作“第一个”的数据元素2)存在唯一的一个被称作“最后一个”的数据元素3)除第一个外,集合中的每个数据元素均只有一个前驱4)除最后一个外,:是具有相同属性的数据元素的一个有限序列。所含元素个数为表的长度,用n表示,n≥0。n=0表示空表。一般表示:(a1,a2,…ai-1,ai,ai+1,…an)或A=(a1,a2,…ai-1,ai,ai+1,…an)a1为第1个元素,也叫表头元素,a2为第2个元素,an为最后一个元素,也叫表尾元素。线性表中的元素按照前后位置线性有序,即第i个元素ai在逻辑上第i-1个元素ai-1的后继,是第i+1个元素ai+1的前驱,第一个元素无前驱,最后一个元素无后继。:linear_list=(A,R)A={ai|1≤i≤n,n≥0,ai∈ElemType}R={r}r={<ai,ai+1>|1≤i≤n-1}元素类型ElemType是一种通用数据类型标识,可能通过typedef语句在使用前把它定义为任何一种具体类型。如:typedefintElemType;逻辑图:,则称该字段为有序字段,该线性表为有序表,否则若不存在任何有序字段,则为无序表。举例:B=(’a’,’b’,’c’,’4’,’7’,’+’,’-’,’*’,’/’)C=(25,38,12,49,63,54,20,18,34,47)D=(”BASIC”,”PASCAL”,”FORTRAN”,”COBOL”,”VC++”,”JAVA”)E=(”序号”,”姓名”,”性别”,”年龄”,”单位”,”职称”,”联系电话”,”E-mail”)F=(a,b,c,d,e,f,g,h,i,j,k,x,y,z)。数据部分为一个线性表,假定用标识符L表示,它可以采用顺序、链接、散列、索引等任一种方法存储到计算机中,其存储类型假定用标识符ListType表示。操作部分为对线性表所做的各种操作(运算),如向线性表插入一个元素,从线性表中删除一个元素,求线性表长度,判断线性表是否为空等。泞桃豢冗秃吕村麻***:一个具有ListType类型的线性表LOperation:voidInitList(ListType&L);voidClearList(ListType&L);intLenthList(ListType&L);boolEmptyList(ListType&L);ElemTypeGetList(ListType&L,intpos);voidTraverseList(ListType&L);(ListType&L,ElemType&item);boolUpdateList(ListType&L,constElemType&item);boolInsertList(ListType&L,ElemTypeitem,intpos);boolDeleteList(ListType&L,ElemType&item,intpos);voidSortList(ListType&L);end