数据结构第2章线性表.pptVIP

3.单链表的插入*在链表中插入一个元素x的示意图如下：xsabp链表插入的核心语句：Step1：s-next=p-next;Step2：p-next=s；p-nexts-next思考：Step1和2能互换么？x结点的生成方式：S=(node*)malloc(m);S-data=x;S-next=p-nextbap插入x线性结构的定义：* 若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、栈、队列、字符串、数组等，其中最典型、最常用的是------线性表见第2章一对一(1:1)2.1线性表的逻辑结构*（a1,a2,…ai-1，ai,ai＋1，…,an）1.线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点（A,B,C,D,……,Z）*例1分析26个英文字母组成的英文表是什么结构。学号姓名性别年龄班级012002009524刘禹圻男182002级计科0201班012002009613武锐男182002级计科0202班012002009710彭隽男172002级计科0203班012002009801郭芳女182002级计科0204班012002009904张珍珍女182002级计科0205班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！2.2.1顺序表的表示*用一组地址连续的存储单元依次存储线性表的元素。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：简言之：逻辑上相邻的元素，物理上也相邻可以利用数组V[n]来实现。注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1]线性表顺序存储特点：*1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）对上述公式的解释如图所示：线性表的顺序存储结构示意图*a1a2……aiai+1……an地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)L设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是113例1因此：LOC(M[3])=98+5×(3-0)=113解：已知地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）2.2.2顺序表的实现（或操作）*回忆：数据结构基本运算操作有：修改、插入、删除、查找、排序1)修改通过数组的下标便可访问某个特定元素并修改之。核心语句:V[i]=x;显然，顺序表修改操作的时间效率是T(n)=O(1)2)插入在线性表的第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];