(数据结构)三讲 线性表的定义及顺序表ppt课件.ppt

第三讲线性表及顺序存储结构本讲主要内容:一、线性表的定义及逻辑结构二、线性表的顺序存储结构三、顺序表的实现一、线性表的定义及逻辑结构学生成绩登记表姓名英语数据结构高数学号丁一9678870101李二8790780102张三6786860103孙红6981960104王冬8774660105职工工资登记表姓名岗位津贴基本工资奖金职工号丁一6002782000101李二3001901000102张三3001861000103孙红5002182000104王冬3001901000105数据元素之间的关系是什么?线性表:简称表,是n(n≥0)个具有相同类型的数据元素的有限序列。线性表的长度:线性表中数据元素的个数,一般用n表示,n≥0。空表:长度等于零的线性表,即n=0,记为:L=()。线性表的定义非空表记为:L=(a1,a2,…,ai-1,ai,…,an)ai(1≤i≤n)称为数据元素;下角标i表示该元素在线性表中的位置或序号(逻辑序号)。a1是表中第一个元素,称为表头元素;a2是表中第二个元素;……an是最后一个元素,称为表尾元素;线性表中各元素在位置上是有序的,:L1=():L1是一个空的线性表;L2=(a,b,c,d,e):L2线性表中有5个元素,其长度为5。a是表头元素、e是表尾元素。c的直接前驱元素是b,c的直接后继元素是d。a元素的序号是1,c元素的序号是3。线性表的定义a1a3a4ana2线性表(a1,a2,…,ai-1,ai,…,an)的图形表示如下:线性表的图形表示元素ai和ai+1之间的先后关系用<ai,ai+1>(a1,a2,…,ai-1,ai,…,an)的二元组表示如下:线性表的二元组表示线性表L=(D,R),其中D={ai|1≤i≤n,n≥0,ai属于ElemType类型}R={r}R={<ai,ai+1>|1≤i≤n-1}注意:ElemType类型是C++的类型标识符,:线性表中数据元素的个数是有穷的。:线性表中数据元素的类型是同一的。:线性表中相邻的数据元素ai-1和ai之间存在序偶关系<ai-1,ai>,即ai-1是ai的前驱,ai是ai-1的后继;a1无前驱,an无后继,其它每个元素有且仅有一个前驱和一个后继。线性表的特性