1、学习情境 线性表学习情境学习情境 线性表线性表2.1 任务一任务一 认识线性表认识线性表2.2 任务二任务二 程序实现线性表的顺序存储结构及操作程序实现线性表的顺序存储结构及操作2.3 任务三任务三 程序实现线性表的链式存储结构及操作程序实现线性表的链式存储结构及操作2.4 任务四任务四 线性表的应用线性表的应用解决约瑟夫环问题解决约瑟夫环问题学习情境 线性表线性表是组成数据间具有线性关系的一种数据结构。对线性表的基本操作主要有初始化、插入、删除、查找、替换、显示等，这些操作可以在线性表中的任何位置进行。线性表可以采用顺序存储结构表示。本学习情境的任务是学习线性表抽象数据类型，线性表的两种存储
2、结构的操作算法及程序实现，比较这两种程序实现的特点，以及各种基本操作算法的效率。学习情境 线性表2.1 任务一任务一 认识线性表认识线性表2.1.1 子任务子任务1 初识线性表初识线性表1定义线性表定义线性表(linear list)线性表是许多实际应用领域中表结构的抽象形式，因此，线性表中数据在不同的场合可以有不同的含义。例如，在字母表(A，B，C，Z)中，每个数据是一个字母；在一个学生成绩中，每个数据是一个学生的成绩信息，其中可能包含学号、姓名、成绩等字段。但要注意，在同一个表中各数据的类型或数据结构是一致的。学习情境 线性表线性表定义：由n(n0)个类型相同的数据a0，a1，an-1组成
3、的有限序列，记作：LinearList=(a0，a1，an-1)本教程约定线性表中数据序号从0开始计数。其中，数据ai可以是数字、字符、也可以是其他对象。n是线性表的数据个数，称为线性表长度。若n=0，则LinearList为空表。若n0，则a0没有前驱数据，an-1没有后继数据，ai(0in-1)有且仅有一个直接前驱数据ai-1和一个直接后继数据ai+1。线性表的图形如图2-1所示。学习情境 线性表图2-1 线性表学习情境 线性表2操作线性表操作线性表线性表结构是许多实际应用中所用到的表结构的抽象，因而对线性表的实际操作可以有很多种，例如，对我们所熟知的成绩表就有很多操作的要求。为便于教学和
4、学习领会，只讨论常用基本操作。在此基础上，学习者可以举一反三地实现需要的操作。线性表常用的基本操作有如下8个：(1)初始化线性表initiate()：建立线性表的初始结构，即建空表。这也是各种数据结构都经常用到的操作。(2)显示线性表中数据displayData()：显示线性表中全部数据，可以直接验证程序是否正确实现，是非常必要的操作。(3)求线性表数据个数getSize()：得到线性表中的数据个数。学习情境 线性表(4)追加数据add()：在线性表最后增加数据。(5)插入数据insert()：在线性表的第i个数据位置上插入值为x的数据。显然，若表中的数据个数为n，则插入序号i应满足0in-1
5、。(6)删除数据delete(int i)：删除线性表中序号为i的数据。显然，待删除数据的序号应满足0in-1。(7)查找数据getData()：得到表中序号为i的数据并显示。(8)修改数据updateData()：修改表中序号为i的数据。虽然只给出了8个基本操作，但借助这些基本操作可以构造出其他更为复杂的操作。例如，如果要求删除线性表中值为x的数据，则可用上述操作中的两个操作来实现：先引用list_locate求出数据x的位置，再用list_delete来实现删除。尽管这一实现的时间性能不太好，但在讨论基本操作时，主要还是侧重于其逻辑上的实现，而不是具体程序上的实现。学习情境 线性表2.1.
6、2 子任务子任务2 认识线性表的存储结构认识线性表的存储结构线性表的存储结构主要有两种，常用的有顺序存储结构和链式存储结构。1顺序存储结构顺序存储结构线性表中的元素按照其逻辑次序依次存储到这一存储区中，方法是用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存储次序与它们在线性表的逻辑次序相同，如图2-2所示。学习情境 线性表图2-2 线性表顺序存储结构 学习情境 线性表2链式存储结构链式存储结构用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息，如图2-3中的箭头表示元素之间的前后顺序关系。因此，对每个表元素，除了存储元素本身的值外
7、，还带有一个指向其后继元素的地址(指针)，链式存储结构如图2-3所示。学习情境 线性表图2-3 线性表链式存储学习情境 线性表2.2 任务二任务二 程序实现线性表的顺序存储结构及操作程序实现线性表的顺序存储结构及操作2.2.1 子任务子任务1 认识线性表的顺序存储结构认识线性表的顺序存储结构1顺序存储结构特点顺序存储结构特点线性表的数据元素顺序存放在数组中，数据元素在数组中的物理顺序与线性表中元素的顺序关系完全相同。学习情境 线性表2顺序存储结构的数据存储地址顺序存储结构的数据存储地址如图2-2所示，线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素，元素在内存中的物理存储次序与它
8、们在线性表中的逻辑次序相同，即元素ai与其连接前驱ai-1及直接后续ai+1的存储位置相邻。顺序存储的线性表也称为顺序表(sequential list)。线性表的元素属于同一种数据类型，设每个元素占用c字节，a0的存储地址为address(a0),则ai的存储地址为address(a0)+i*c。学习情境 线性表3顺序存储结构的时间复杂度顺序存储结构的时间复杂度顺序表元素ai的存储地址是它在线性表中位置i的线性函数，如图2.2所示，与线性表长度n无关，而计算一个元素地址所需时间是一个常量，与元素位置i无关。因此，存取任何一个元素的时间复杂度是O(l)。换言之，顺序表是一种随机存取结构。4数组
9、数组数组是顺序存储的随机存取结构，它占用一组连续的存储单元，通过下标i识别元素，元素地址是下标的线性函数。一个下标能够唯一确定一个元素，存取任何一个元素所花费的时间是O(l)。所以线性表的存储结构通常采用数组存储数据元素。学习情境 线性表5定义线性表顺序存储结构的类定义线性表顺序存储结构的类public class SeqList private int maxn=100;/线性表存储空间为100或根据需要而定 private int n=-1;/线性表个数，-1表示未初始化 private Object data;/声明线性表数据类型，Object可以存储任何类型学习情境 线性表2.2.2
10、子任务子任务2 线性表顺序存储结构的操作算法线性表顺序存储结构的操作算法下面分析线性表顺序存储结构的操作算法。1初始化线性表初始化线性表initiate()算法算法在进行线性表的各种操作前必须先建立线性表的初始结构，对顺序存储结构而言，即建立一个具有一定大小的空表。用中文描述算法：创建一个大小为maxn的数组；线性表没有数据，即n为0；用程序设计语言描述算法：data=new Objectmaxn;n=0;学习情境 线性表2显示线性表中所有数据显示线性表中所有数据displayData()算法算法显示线性表中的全部数据，可用中文描述如下：如果没有数据提示“线性表中没有数据”；否则按顺序将所有数
11、据输出；前面约定用n表示线性表的个数，所以“没有数据”的条件就是n1；“按顺序将所有数据输出”，可以很容易想到用循环控制结构来实现。学习情境 线性表用程序设计语言描述算法：if(n 1)System.out.println(线性表中没有数据);else for(int i=1;i=n;i+)/按顺序将所有数据输出 System.out.print(datai+);3求线性表数据个数求线性表数据个数getSize()算法算法线性表中的数据个数实际就是线性表的参数n，可以直接得到，用中文描述算法：返回线性表个数n用程序设计语言描述算法：return n;学习情境 线性表4追加数据追加数据add(O
12、bject obj)算法算法在线性表后面增加数据，在2.2.1子任务1中定义线性表顺序存储结构的类时，n=-1表示线性表未初始化，如果直接追回数据会造成异常，所以追加数据前先要判断线性表是否已经初始化。如果不断增加数据，达到线性表定义空间，这时就要扩展线性表空间，或者进行简单处理不让数据继续增加。用中文描述算法：如果线性表未初始化抛出未初始化异常信息如果达到线性表定义大小抛出线性表已满异常信息读入数据在线性表最后位置存入该数据线性表个数加1学习情境 线性表用程序设计语言描述算法：if(n=-1)throw new Exception(尚未初始化，请选择0进行初始化！);if(n=maxn)th
13、row new Exception(线性表已满，无法再插入);System.out.print(请输入要加进的数据：);Object obj=scan.next();datan+1=obj;/在线性表最后位置存入读入的数据 n+;/每次执行完add()之后记得将线性表长度加1学习情境 线性表5插入数据插入数据insert()算法算法在线性表的第i个数据位置上插入值为x的数据。显然，若表中的数据个数为n，则插入序号i应满足0in-1，还要判断线性表是否已满；插入操作时，插入位置后面的所有数据要从后往前依次将数据后移一位，空出位置i，将读入数据存入此位置，最后n加1，如图2-4所示。学习情境 线性
14、表图2-4 线性表顺序存储结构插入操作学习情境 线性表用中文描述算法：输入插入位置i的值如果i不满足0in-1抛出位置错误信息如果达到线性表定义大小抛出线性表已满异常信息读入数据从ai开始全部数据从后向前后移一位 学习情境 线性表用程序设计语言描述算法：System.out.println(请输入要插入第几个数据的后面);int i=scan.nextInt();if(i n)throw new Exception(位置错误，请选择1查看数据以确定插入位置);if(n=maxn)throw new Exception(线性表已满，无法再插入);学习情境 线性表System.out.printl
15、n(请输入你要输入的数据);Object obj=scan.next();/插入位置开始的所有数据要从后往前依次将数据后移一位for(int j=n;j i;j-)dataj+1=dataj;datai+1=obj;n+;6删除数据删除数据delete(int i)算法算法删除线性表中序号为i的数据，显然，待删除数据的序号应满足0in-1，顺序存储结构的线性表删除数据时，只要将此位置后面的数据依次向前移一位，覆盖前一位数据，最后将线性表的个数减1即可，如图2-5所示。学习情境 线性表图2-5 线性表顺序存储结构删除操作学习情境 线性表用中文描述算法：如果i不满足0in-1抛出位置错误信息暂存要
16、删除的数据i位置后面的数据依次往前移一位线性表个数减1返回删除的数据学习情境 线性表用程序设计语言描述算法：if(i n)throw new Exception(位置错误，请选择1查看数据以确定删除位置);Object it=datai;/暂存要删除的数据 /i位置后面的数据依次向前移一位for(int j=i;j n;j+)dataj=dataj+1;n-;return it;/返回已删除的数据 学习情境 线性表7查找数据查找数据getData()算法算法得到表中序号为i的数据并显示，先判断序号i是否在线性表的有效范围内，如果是就直接获得该位置的数据并返回。用中文描述算法：如果i不满足0in
17、-1抛出位置错误信息返回序号i位置的数据用程序设计语言描述算法：if(i n)throw new Exception(该位置无数据);System.out.println(你要查找的数为：+datai);return datai;学习情境 线性表8修改数据修改数据updateData()算法算法修改表中序号为i的数据，先判断序号i是否在线性表的有效范围内，如果是就将数组下标为i的数据置为输入数据。用中文描述算法：读入修改序号i如果i不满足0in-1抛出位置错误信息读入新的数据将数组下标为i的数据置为输入数据学习情境 线性表用程序设计语言描述算法：System.out.println(请输入你要
18、修改的第几个数);int i=scan.nextInt();if(i n)return;System.out.println(请输入修改的数据为：);Object obj=scan.next();datai=obj;/将数组下标为i的数据置为输入数据学习情境 线性表2.2.3 子任务子任务3 程序实现线性表顺序存储结构的操作程序实现线性表顺序存储结构的操作考虑到不少程序初学者在学完数据结构和算法教程后却从未完成一个能够运行的程序，本学习任务将详细介绍该程序实现的全过程。对于初学者，务必按照本任务一步一步认真学习和操作，在进行任何一步时，有错误一定要查出来并改正，必须做到无错误才能进入下一步，只
19、要掌握了本任务，后面的程序就可以轻松上手。1构建主程序构建主程序SeqListMain.java(1)新建包ch2List，在此包中新建主程序文件，文件名为SeqListMain.java，开始创建线性表操作菜单，程序如下(调试通过后再进入下一步)：学习情境 线性表package ch2List;import java.util.Scanner;public class SeqListMain public static void main(String args)Scanner scan=new Scanner(System.in);int select;do System.out.prin
20、tln(nnt=线性表操作菜单=);System.out.print(1.初始化 );System.out.print(2.显示线性表中数据 );System.out.print(3.求线性表数据个数 );System.out.print(4.追加数据 );System.out.print(5.插入数据 );学习情境 线性表 System.out.print(6.删除数据 );System.out.print(7.查找数据 );System.out.print(8.修改数据 );System.out.print(9.退出 n);System.out.print(请输入您的选择项：);selec
21、t=scan.nextInt();while(true);运行程序，结果如下：=线性表操作菜单=1.初始化 2.显示线性表中数据 3.求线性表数据个数 4.追加数据 5.插入数据 6.删除数据 7.查找数据 8.修改数据 9.退出 请输入您的选择项：学习情境 线性表(2)对菜单选择进行处理，根据用户键盘输入的选择值，即select值使用switch结构来构造响应用户选择的处理框架，程序如下：switch(select)case 1:break;case 2:break;case 3:break;case 4:break;case 5:break;学习情境 线性表 case 6:break;ca
22、se 7:break;case 8:break;case 9:System.out.print(正在退出菜单.);System.exit(0);break;运行程序，键盘输入9，回车后，就可以退出系统。接下来只有先构建线性表顺序存储结构和算法程序SeqList.java，才能继续响应其他选择。注意注意：请转而阅读“2.构建线性表顺序存储结构和算法程序SeqList.java”的第三步，然后再返回此处进行第三步操作。学习情境 线性表(3)调用initiate()方法，先在public static void main(String args)后面插入一行代码创建SeqList类的对象seqlis
23、t，代码如下，SeqList seqlist=new SeqList();接着在case 1：调用initiate()方法，程序如下：case 1：seqlist.initiate();break;学习情境 线性表运行程序，通过键盘输入1，得到如下结果，表示初始化方法编写成功：=线性表操作菜单=1.初始化 2.显示线性表中数据 3.求线性表数据个数 4.追加数据 5.插入数据 6.删除数据 7.查找数据 8.修改数据 9.退出 请输入您的选择项：1初始化成功。注意注意：先转入“2.构建线性表顺序存储结构和算法程序SeqList.java”的第四步，然后再返回此处进行下面的操作。学习情境 线性表
24、(4)在case 2：中调用displayData()方法，程序如下：case 2:seqlist.displayData();break;注意：调试通过后，转入“2.构建线性表顺序存储结构和算法程序SeqList.java”的第五步，然后再返回此处进行下面的步骤。学习情境 线性表(5)在case 3：中调用getSize()方法，得到线性表的个数n，如果n为0则表明线性表没有数据，否则输出个数，程序如下：case 3:if(seqlist.getSize()=0)System.out.println(线性表为空);else System.out.print(元素的个数为);System.ou
25、t.print(seqlist.getSize();break;注意：调试通过后，转入“2.构建线性表顺序存储结构和算法程序SeqList.java”的第六步，然后再返回此处进行下面的步骤。学习情境 线性表(6)在case 4：中调用add()方法，因为add()方法有抛出异常信息，所以在调用时要捕获异常并处理。因为add()方法是抛出线性表未初始化或已满的信息，所以处理异常就会输出add()方法异常抛出的信息(e.toString()，程序如下：case 4:System.out.print(请输入要加进的数据：);Object obj=scan.next();try seqlist.add
26、(obj);catch(Exception e)System.out.print(e.toString();break;注意：调试通过后，转入“2.构建线性表顺序存储结构和算法程序SeqList.java”的第七步，然后再返回此处进行下面的步骤。学习情境 线性表(7)在case 5：中调用方法并进行异常捕获和处理，程序如下：case 5:try seqlist.insert();catch(Exception e)System.out.print(e.toString();break;注意：调试通过后，转入“2.构建线性表顺序存储结构和算法程序SeqList.java”的第八步，然后再返回此处
27、进行下面的步骤。学习情境 线性表(8)在case 6：中调用delete(i)方法，delete(i)方法以删除序号i作为参数传递来进行删除调用，事先需要使用者从键盘输入删除位置，程序如下：case 6:/删除i位置的数据 System.out.println(请输入你要删除第几个数：);int i=scan.nextInt();if(seqlist.getSize()=0)System.out.print(顺序表已空无法删除！);if(i seqlist.getSize()System.out.print(位置错误，请选择 1 察看数据以确定删除位置);学习情境 线性表 try seqlis
28、t.delete(i);catch(Exception e)System.out.print(e.toString();break;注意：调试通过后，转入“2.构建线性表顺序存储结构和算法程序SeqList.java”的第九步，然后再返回此处进行下面的步骤。学习情境 线性表(9)在case 7：中调用getData()方法，程序如下：case 7:try seqlist.getData();catch(Exception e)System.out.print(e.toString();break;注意：调试通过后，转入“2.构建线性表顺序存储结构和算法程序SeqList.java”的第十步，然
29、后再返回此处进行下面的步骤。学习情境 线性表(10)在case 8：中调用updateData()方法，程序如下：case 8:int number=0;int index=0;seqlist.updateData();break;至此，全部程序调试通过。学习情境 线性表2构建线性表顺序存储结构和算法程序SeqList.java(1)在包ch2List中新建算法程序，文件名为SeqList.java。(2)构建线性表顺序存储结构，程序代码如下：package ch2List;import java.util.Scanner;public class SeqList Scanner scan=n
30、ew Scanner(System.in);private int maxn=100;/线性表存储空间为100或根据需要而定 private int n=-1;/线性表个数，-1表示未初始化 private Object data;/声明线性表数据类型，Object可以存储任何类型 学习情境 线性表(3)创建初始化initiate()方法，程序如下：public void initiate()/初始化 data=new Objectmaxn;n=0;System.out.println(初始化成功.);转回“1.构建主程序SeqListMain.java”的第三步，调用该方法。学习情境 线性表
31、(4)创建显示所有数据displayData()方法，程序如下：public void displayData()if(n 1)System.out.println(线性表中没有数据);else for(int i=1;i=n;i+)/按顺序将所有数据输出 System.out.print(datai+);转回“1.构建主程序SeqListMain.java”的第四步，调用该方法。学习情境 线性表(5)获得线性表数据个数getSize()方法，程序如下：public int getSize()return n;转回“1.构建主程序SeqListMain.java”的第五步，调用该方法。(6)追
32、加数据add()方法，要算法分析时，需要抛出异常信息，如线性表未初始化或已满等信息，所以在创建add()方法时要用throws Exception抛出异常，从而让调用者捕获和处理。程序如下：学习情境 线性表 public void add(Object obj)throws Exception if(n=-1)/未初始化，抛出异常信息 throw new Exception(尚未初始化，请选择0进行初始化！);if(n=maxn)/已满，抛出异常信息 throw new Exception(线性表已满，无法再插入);datan+1=obj;/在线性表最后位置存入读入的数据 n+;/每次执行完a
33、dd()之后记得将线性表长度加1 转回“1.构建主程序SeqListMain.java”的第六步，调用该方法。学习情境 线性表(7)插入数据insert()方法，与add()方法相同，要用throws Exception抛出异常，从而让调用者捕获和处理。程序如下：public void insert()throws Exception System.out.println(请输入要插入第几个数据的后面);int i=scan.nextInt();if(i n)throw new Exception(位置错误，请选择1查看数据以确定插入位置);if(n=maxn)throw new Except
34、ion(“线性表已满，无法再插入”);学习情境 线性表 System.out.println(请输入你要输入的数据);Object obj=scan.next();/插入位置开始的所有数据要从后往前依次将数据后移一位 for(int j=n;j i;j-)dataj+1=dataj;datai+1=obj;n+;转回“1.构建主程序SeqListMain.java”的第七步，调用该方法。学习情境 线性表(8)删除数据delete(int i)方法，用throws Exception抛出异常，从而让调用者捕获和处理。程序如下：public Object delete(int i)throws E
35、xception Object it=datai;/获得要删除的数据 if(i n)throw new Exception(位置错误，请选择1查看数据以确定删除位置);/i位置后面的数据依次往前移一位 for(int j=i;j n;j+)dataj=dataj+1;n-;return it;/返回已删除的数据 转回“1.构建主程序SeqListMain.java”的第八步，调用该方法。学习情境 线性表(9)查找数据getData()方法，用throws Exception抛出异常，从而让调用者捕获和处理。程序如下：public Object getData()throws Exception
36、 /获取i位置的数据并返回 System.out.println(请输入你要查找的第几个数);int i=scan.nextInt();if(i n)throw new Exception(该位置无数据);System.out.println(你要查找的数为：+datai);return datai;转回“1.构建主程序SeqListMain.java”的第九步，调用该方法。学习情境 线性表(10)修改数据updateData()方法，程序如下：public void updateData()System.out.println(请输入你要修改的第几个数);int i=scan.nextInt
37、();if(i n)return;System.out.println(请输入修改的数据为：);Object obj=scan.next();datai=obj;/将数组的下标为i的数据设置为输入数据 转回“1.构建主程序SeqListMain.java”的第十步，调用该方法。学习情境 线性表3完整源程序完整源程序(1)SeqListMain.java程序。package ch2List;import java.util.Scanner;public class SeqListMain public static void main(String args)SeqList seqlist=ne
38、w SeqList();Scanner scan=new Scanner(System.in);int select;学习情境 线性表 do System.out.println(nnt=线性表操作菜单=);System.out.print(1.初始化 );System.out.print(2.显示线性表中数据 );System.out.print(3.求线性表数据个数 );System.out.print(4.追加数据 );System.out.print(5.插入数据 );System.out.print(6.删除数据 );System.out.print(7.查找数据 );System.
39、out.print(8.修改数据 );System.out.print(9.退出 n);System.out.print(请输入您的选择项：);select=scan.nextInt();学习情境 线性表 switch(select)case 1:seqlist.initiate();break;case 2:seqlist.displayData();break;case 3:if(seqlist.getSize()=0)System.out.println(线性表为空);else System.out.print(数据的个数为);System.out.print(seqlist.getSi
40、ze();break;学习情境 线性表 case 4:System.out.print(请输入要加进的数据：);Object obj=scan.next();try seqlist.add(obj);catch(Exception e)System.out.print(e.toString();break;case 5:try seqlist.insert();catch(Exception e)System.out.print(e.toString();break;学习情境 线性表 case 6:/删除i位置的数据 System.out.println(请输入你要删除第几个数：);int i
41、=scan.nextInt();if(seqlist.getSize()=0)System.out.print(顺序表已空无法删除！);if(i seqlist.getSize()System.out.print(位置错误，请选择1查看数据以确定删除位置);try seqlist.delete(i);catch(Exception e)System.out.print(e.toString();break;学习情境 线性表 case 7:try seqlist.getData();catch(Exception e)System.out.print(e.toString();break;cas
42、e 8:int number=0;int index=0;seqlist.updateData();break;学习情境 线性表 case 9:System.out.print(正在退出菜单.);System.exit(0);break;while(true);学习情境 线性表(2)SeqList.java程序。package ch2List;import java.util.Scanner;public class SeqList Scanner scan=new Scanner(System.in);private int maxn=100;/线性表存储空间为100或根据需要而定 priv
43、ate int n=-1;/线性表个数，-1表示未初始化 private Object data;/声明线性表数据类型，Object可以存储任何类型学习情境 线性表 public void initiate()/初始化 data=new Objectmaxn;n=0;System.out.println(初始化成功.);public void displayData()if(n 1)System.out.println(线性表中没有数据);else for(int i=1;i=n;i+)/按顺序将所有数据输出 System.out.print(datai+);学习情境 线性表 public i
44、nt getSize()return n;public void add(Object obj)throws Exception if(n=-1)/未初始化，抛出异常信息 throw new Exception(尚未初始化，请选择0进行初始化！);if(n=maxn)/已满，抛出异常信息 throw new Exception(线性表已满，无法再插入);datan+1=obj;/在线性表最后位置存入读入的数据 n+;/每次执行完add()之后记得将线性表长度加1 学习情境 线性表 public void insert()throws Exception System.out.println(请
45、输入要插入第几个数据的后面);int i=scan.nextInt();if(i n)throw new Exception(位置错误，请选择1查看数据以确定插入位置);if(n=maxn)throw new Exception(线性表已满，无法再插入);System.out.println(请输入你要输入的数据);Object obj=scan.next();/插入位置开始的所有数据要从后往前依次将数据后移一位 for(int j=n;j i;j-)dataj+1=dataj;datai+1=obj;n+;学习情境 线性表 public Object delete(int i)throws
46、Exception if(i n)throw new Exception(位置错误，请选择1查看数据以确定删除位置);Object it=datai;/暂存要删除的数据 /i位置后面的数据依次往前移一位 for(int j=i;j n;j+)dataj=dataj+1;n-;return it;/返回已删除的数据 学习情境 线性表 public Object getData()throws Exception /获取i位置的数据并返回 System.out.println(请输入你要查找的第几个数);int i=scan.nextInt();if(i n)throw new Exception
47、(该位置无数据);System.out.println(你要查找的数为：+datai);return datai;学习情境 线性表 public void updateData()System.out.println(请输入你要修改的第几个数);int i=scan.nextInt();if(i n)return;System.out.println(请输入修改的数据为：);Object obj=scan.next();datai=obj;/将数组下标为i的数据设置为输入数据 学习情境 线性表2.3 任务三任务三 程序实现线性表的链式存储结构及操作程序实现线性表的链式存储结构及操作2.3.1
48、子任务子任务1 认识线性表的链式存储结构认识线性表的链式存储结构1线性表的链式存储结构线性表的链式存储结构线性表的链式存储有别于顺序存储，逻辑上相邻的数据在物理位置上不一定相邻，用地址分散的存储单元存储线性表的数据时，各存储单元之间必须采用附加信息表示数据之间的顺序关系。所以，对每个线性表数据，除了存储数据本身的值外，还带有一个指向其后继数据的地址，即每个数据采用图2-6所示的结构表示。学习情境 线性表图2-6 线性表链式存储结构 学习情境 线性表线性表数据具有两个域，一个数据域，一个指针域。其中，数据域用data表示存储数据的值；指针域一般用Next或Link存储后继数据的地址，也称为地址域
49、或链。上述结构通常称为节点。图2-6所示的节点只有一个指针，由一个指针的节点构成的线性表称单链表；还可以有两个或更多的指针，比如两个指针(一般称为左指针和右指针)的节点构成的线性表称为双链表，两个指针分别为前继节点和后继节点，如图2-7所示。双指针节点结构的线性表操作与单指针的链表操作相似，只要真正理解单链表的操作，双链表的操作就可以类似解决，所以本教程重点讲解单链表的操作。学习情境 线性表图2-7 线性表链式存储的双指针节点学习情境 线性表2定义线性表链式存储的节点定义线性表链式存储的节点在C语言中，可以使用结构体和指针来定义链式存储结构的节点数据和指针；在C+语言中，采用指针类型存储地址来
50、实现链式存储结构。Java语言不支持指针类型，提供引用方式保存地址在内的结构化信息。引用是比指针更健壮、更安全的链接方式，它不仅实现了指针类型的所有功能，而且避免了因指针使用不当而产生的不安全性。因此，采用Java语言的引用类型可以更好地实现链式存储结构。学习情境 线性表定义的程序实现如下：public class SingleLinkList private Object data;/声明线性表数据类型，Object可以存储任何类型 private SingleLinkList next;/声明链表引用(指针)private SingleLinkList front;/定义线性表的头节点 学
