数据结构线性表.pptx

1线性结构的定义:若结构是非空有限集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为:(a1,a2,……,an)简言之,线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点;特点②除首尾结点外,其他结点只有一个直接前驱和一个直接后继。线性结构包括:线性表、栈、队列、字符串、数组等,其中最典型、最常用的是------线性表见第2章一对一(1:1)2(a1,a2,…ai-1,ai,ai+1,…,an):用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标,是元素的序号,表示元素在表中的位置n为元素总个数,即表长空表线性终点3例1分析26个英文字母组成的英文表是什么结构。(A,B,C,D,……,Z)学号姓名性别年龄班级0**********刘禹圻男182002级计科0201班0**********武锐男182002级计科0202班0**********彭隽男172002级计科0203班0**********郭芳女182002级计科0204班0**********张珍珍女182002级计科0205班:::::例2分析学生情况登记表是什么结构。分析:数据元素都是同类型(记录),元素间关系是线性的。分析:数据元素都是同类型(字母),元素间关系是线性的。注意:同一线性表中的元素必定具有相同特性!。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义:顺序存储方法:简言之:逻辑上相邻的元素,物理上也相邻可以利用数组V[n]来实现。注意:在C语言中数组的下标是从0开始,即:V[n]的有效范围是从V[0]~V[n-1]5线性表顺序存储特点:,其物理上也相邻;,则其他元素存放位置亦可求出(利用数组V[n]的下标)。设首元素a1的存放地址为LOC(a1)(称为首地址),设每个元素占用存储空间(地址长度)为L字节,则表中任一数据元素的存放地址为:LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*(i-1)对上述公式的解释如图所示:6线性表的顺序存储结构示意图a1a2……aiai+1……an地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)L7设有一维数组M,下标的范围是0到9,每个数组元素用相邻的5个字节存储。存储器按字节编址,设存储数组元素M[0]的第一个字节的地址是98,则M[3]的第一个字节的地址是113例1因此:LOC(M[3])=98+5×(3-0)=113解:已知地址计算通式为:LOC(ai)=LOC(a1)+L*(i-1)(或操作)回忆:数据结构基本运算操作有:修改、插入、删除、查找、排序1)修改通过数组的下标便可访问某个特定元素并修改之。核心语句:V[i]=x;显然,顺序表修改操作的时间效率是T(n)=O(1)92)插入在线性表的第i个位置前插入一个元素实现步骤:将第n至第i位的元素向后移动一个位置;将要插入的元素写到第i个位置;表长加1。注意:事先应判断:插入位置i是否合法?表是否已满?应当有1≤i≤n+1或i=[1,n+1]for(j=n;j>=i;j--)a[j+1]=a[j];a[i]=x;n++;//元素后移一个位置//插入x//表长加1核心语句:10在线性表的第i个位置前插入一个元素的示意图如下:121321242830427712132124252830427712345678123456789插入25