第二章、线性表逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构线性表线性表类型的定义（a1,a2,…ai-1，ai,ai＋1，…,an）例1分析26个英文字母组成的英文表a1练：判断下列叙述的正误：3、线性表的操作BACK进一步说明:（1）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。2.2线性表的顺序存储和实现2.2.1顺序表的顺序存储表示线性表顺序存储特点：线性表的顺序存储结构示意图一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是2.2.2顺序表的实现2）顺序表的操作实现操作接口publicbooleanadd(intindex,Eelement);//在第index个位置插入对象element插入前：(a0,…,ai-1,ai,…,an-1)插入后：(a0,…,ai-1,item,ai,…,an-1)插入操作图示33插入：在顺序表的第index个位置插入一个元素JAVA具体实现：publicbooleanadd(intindex,Eelement){if(element==null)returnfalse;//不能插入nullif(this.n==table.length){//若数组满，则需要扩充顺序表容量Object[]temp=this.table;this.table=newObject[temp.length*2];for(inti=0;i<temp.length;i++)//复制数组元素this.table[i]=temp[i];}if(index<0)index=0;//下标容错if(index>this.n)index=this.n;for(intj=this.n-1;j>=index;j--)//元素后移this.table[j+1]=this.table[j];this.table[index]=element;this.n++;returntrue;}操作接口publicEremove(intindexx)删除前：(a1,…,ai-1,ai,ai+1,…,an)删除后：(a1,…,ai-1,ai+1,…,an)删除操作图示例：（35,33,12,24,42），删除index=2的数据元素。实现步骤：获得index位置上要删除的元素值;将位置为index至this.n-1的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置index是否合法?应当有0≤index<this.nJAVA具体实现：publicEremove(intindex){if(this.n!=0&&index>=0&&index<this.n){Eold=(E)this.table[index];for(intj=index;j<this.n-1;j++)//元素前移this.table[j]=this.table[j+1];this.table[this.n-1]=null;this.n--;returnold;}returnnull;}5)按位查找实现2.2.3顺序表的算法效率分析讨论2：若在长度为n的线性表上删除第i位元素，向前移动元素的次数f(n)为：f(n)=线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素；缺点：(1)在插入，删除某一元素时，平均要移动一半元素，平均时间复杂度O(n)。⑵表的容量难以确定，表的容量难以扩充；⑶易造成存储空间的碎片。为克服这些缺点，我们引入另一种存储形式：链式存储。2.3线性表的链式存储和实现链表：线性表的链接存储结构。存储思想：用一组任意的存储单元存放线性表的元素。链表是由若干结点构成的；每个结点结构有两个部分组成：2、有关的术语头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志或表长等信息;首元结点是指链表中存储线性表第一个数据元素a1。上例链表的逻辑结构示意图有以下两种形式：答：publicclassNode<E>{//单链表结点类publicEdata;//数据域，保存数据元素publicNode<E>next;//地址域，引用后继结点2.3.2单链表的操作实现1、单链表的遍历操作接口：基本步骤：从首结点开始，一个一个输出至尾结点。算法实现：2、单链表插入(1)空表插入/头插入如何