数据结构（Java语言版）课件 第三章 线性表

数据结构（Java语言版）第三章线性表2内容简介线性表是数据结构中最基本的结构之一，其应用非常广泛。按线性表的存储结构，可将其分为顺序表和链表，通过对其操作可以解决许多生活中的实际问题。

3【知识目标】

具备分析顺序表逻辑结构和存储结构的能力；

提升利用Java语言进行顺序表基本操作（查找、插入、删除）的能力；

具备分析链表逻辑结构和存储结构的能力；

提升利用Java语言进行链表基本操作（查找、插入、删除）的能力；

初步具备理解单链表、循环链表、双向链表含义的能力；

初步具备分析顺序表和链表的算法效率的能力；

提升通过线性表解决实际问题的能力。【能力目标】

具备分析顺序表逻辑结构和存储结构的能力；

提升利用Java语言进行顺序表基本操作（查找、插入、删除）的能力；

具备分析链表逻辑结构和存储结构的能力；

提升利用Java语言进行链表基本操作（查找、插入、删除）的能力；

初步具备理解单链表、循环链表、双向链表含义的能力；

初步具备分析顺序表和链表的算法效率的能力；

提升通过线性表解决实际问题的能力。定义：相同类型的n个数据元素组成的有限序列称为线性表。记为：A=(a1，a2，…ai-1，ai，ai+1，…an)其中n为表长，当n=0时称为空表。线性表的概述6举例：A=(１,３,５,７,９)

该线性表的长度为5B=(a1,a2,a3,···，am)

该线性表的长度为m线性表的概述7线性表数据元素之间的关系：(直接)前驱和后继(a1，a2，…ai-1，ai，ai+1，…an)在相邻元素中，ai是ai+1的前驱

（第一个元素a1无前驱）在相邻元素中，ai+1是ai的后继

（最后一个元素an无后继）线性表的概述8线性表的定义也可描述如下：

线性表是第一个元素无前驱，最后一个元素无后继，而其他元素都有唯一直接前驱和直接后继的表结构。

A=(a1，a2，…ai-1，ai，ai+1，…an)线性表的概述9例：B=（200101，计算机组成原理，35,35）

（200405，大学英语，35,28）

（2004036，高等数学,140,24）

（200617，计算机基础，70,18）

线性表的概述10练习1、线性表是

（）A、一个有限序列，可以为空B、一个有限序列，不能为空C、一个无限序列，可以为空D、一个无限序列，不能为空11练习2、线性表是具有n个

（）的有限序列A、数据表B、字符C、数据元素D、数据项12练习3、在线性表中，除了开始元素外，每个元素

（）A、只有唯一的前驱元素B、只有唯一的后继元素C、有多个前驱元素D、有多个后继元素131．线性表的逻辑结构与存储结构逻辑结构：相临元素之间所满足前驱和后继的逻辑关系。存储结构：分为顺序存储和链式存储两种，因此,线性表分为顺序表和链表两大类。一种逻辑结构可对应多种存储结构，而每种存储结构又有自己的存储特点和操作方式。线性表的存储结构及操作14线性表的常见操作有：

建表（初始化）

求表长

查找

插入

删除等线性表的操作注意：每种数据结构的相关操作一定不能脱离其逻辑结构和存储结构而独立存在。15线性表的存储结构可分为两种：

顺序存储结构

链式存储结构因此，线性表分为：顺序表和链表两大类。线性表的分类16

顺序表定义:使用顺序存储形式存储的线性表顺序表的基本操作及实现172．存储特点

顺序表存储在一段连续的存储单元中。

特点：线性表逻辑上相邻的数据元素（直接前驱和直接后继）在存储位置（或物理位置）上也相邻。顺序表的基本操作及实现182．存储特点假设给定起始地址Loc(a1)，L：元素占用存储单元的长度表中任意地址：

Loc(ai)=Loc(a1)+(i-1)*L(1≤i≤n)

顺序表的基本操作及实现19练习1、线性表L=(a1,a2,a3.....an)，下列说法正确的是

（）A、每个元素都有一个直接前驱和一个直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小D、除第一个和最后一个元素外，其余每个元素都有一个且只有一个直接前驱和直接后继20练习线性表的顺序存储结构是一种

（）存储结构A、随机存取B、顺序存取C、索引存取D、散列存取21线性表的基本操作在顺序表中的实现Listfind(intk)//查找ListInsert(inti,inta)//插入元素ListDelete(inti)//删除元素22根据顺序表的特点，其存储适合使用：数组注意：探讨某种数据的操作一定是在逻辑结构和存储结构之上进行。顺序表非常适合用高级语言中的数组来实现。23顺序表类：（Linelist）1）数据成员

表的内容表的长度2）方法成员

建立、输出、插入、删除、查找A=(a1，a2，…ai-1，ai，ai+1，…an)数组存储的顺序表类24publicclassLineList{privateint[]data;//定义一个存储元素的数组privateintlength;//非数组长度，是顺序表长度publicLineList(){}数组存储的顺序表类25publicLineList(int[]a1,intlen){data=a1;length=len;}数组存储的顺序表类26//输出线性表元素publicvoidshow(){for(int

i=0;i<length;i++)

System.out.println(data[i]);}数组存储的顺序表类27 publicvoidsetData(int[]data){ this.data=data; } publicvoidsetLength(intlength){ this.length=length; } publicint[]getData(){ return(this.data); } publicintgetLength(){ return(this.length); }数组存储的顺序表类282．插入操作及算法实现例如：表中i号位置，插入元素a(75)操作步骤?

操作算法书写?

291）表满publicbooleaninsert(inti,inta){intj;if(length>=data.length){//表已满

System.out.println("溢出");returnfalse;}算法：顺序表的i位置上插入一个值为a的元素30if(i<0||i>length){//位置不正确

System.out.println("位置出错"+i);returnfalse;}2）位置不合理（分析边界）最后的合理位置31for(j=length-1;j>=i;j--)data[j+1]=data[j];//元素后移data[i]=a;//赋值length++;//线性表长度加一returntrue;}}3）插入元素a32例如：删除i号元素78删除操作33publicbooleandelete(int

i){if(i<0||i>length-1){//检查删除位置是否存在

System.out.println("位置不合理.");returnfalse;}for(intj=i;j<length-1;j++)data[j]=data[j+1];length--;returntrue;}}删除某位置上的元素341．链表的定义链表是线性表的另一种存储形式，将线性表的内容存储在一组任意的存储单元中。除了存储元素本身信息，还要存储后继元素的位置。6093717860719378线性表存储链表链表结点由两个区域构成，一个存放数据元素自身的信息，称为数据域（data）；另一个存放后继元素的地址，称为指针域（next）。datanext结点结构数据域指针域

结点的表示classLinkNode{privateintdata=-1;privateLinkNodenext=null;publicvoidsetData(intdata){this.data=data;}publicLinkNodegetNext(){ returnnext;}publicvoidsetNext(LinkNodenext){ this.next=next;}}

设计链表结点单链表双向链表循环链表

链表的分类1．单链表单链表是链表中最常用的一种，其特点从第1个元素（可能有头结点）到最后一个元素（结束标志为∧）构成的一个链，称为单链表。162012∧65H2．循环链表在单链表中，最后一个元素的存储区域是∧，如果将它指向第1个元素（头结点）位置，就构成了循环链表。循环链表priordatanext前驱指针域数据域后继指针域不带头结点的单链表为空（头指针为head）的判定条件是（）。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL练习：带头结点的单链表为空（头指针为head）的判定条件是（）。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL练习：

单链表的建立

插入

删除

元素查找

替换等单链表的操作44classLinkTable{

LinkNodehead;intcounts;

publicLinkTable(){head=null；

counts=0;}1.头指针2.结点数目3.构造方法4.输出链表5.插入结点（表头位置）6.删除特定值的结点

链表类设计a1a2an∧a3Hpublicvoidprint(){

LinkNoden=head.getNext();while(n!=null){

System.out.print(n.getData()+"");n=n.getNext();}}162012∧65headn

输出所有结点65headspublicvoidinsert(intd){}

插入结点算法122012∧65headpublicbooleandelete(intx){LinkNoden=head.getNext();LinkNodep=head;while(n!=null){if(x==n.getData())break;p=n;n=n.getNext();}if(n!=null){p.setNext(n.getNext());counts--;returntrue;}elsereturnfalse;}