Table[j]=table[j+1];
Table[n-1]=0;
n--;
}
Else
System.out.println（k+”值未找到，无法删除!
”）;
}
5.顺序表的算法分析
插入和删除是顺序表中时间复杂度最高的成员函数。
插入时，主要的耗时部分是循环移动数据元素部分。
循环移动数据元素的效率和插入的位置i有关，最坏情况是i=0，需移动size个数据元素；最好情况是i=size，需移动0个数据元素。
平均次数为：
类似地，删除时，平均次数为：
顺序表中的其余操作都和数据元素个数n无关，因此在顺序表中插入和删除一个数据元素成员函数的时间复杂度为O（n）。
顺序表支持随机读取，因此，顺序表取数据元素的时间复杂度为O
（1）。
顺序表的主要优点是：
支持随机读取，以及内存空间利用效率高。
顺序表的主要缺点是：
需要预先给出（很难准确）数组的最大数据元素个数，另外，插入和删除操作时需要移动较多的数据元素。
3．2线性链表
3.2.1概述
Java语言虽然删除了Pointer类型，但是还可以运用数组来模拟出链表。
不仅如此，Java语言中还有一个Java..utility的类库供了链表的类供程序设计者使用，读者如果对于这个链表的类有兴趣可在JDK的目录下，找到一个叫src.jar的文件，使用解压缩软件来打开这个文件，就可以在\src\java\util的目录下找到一个叫LinkedList.java的文件，其中就是链表的相关程序代码。
本书的重点在于帮助读者建立数据结构概念，而非面向对象程序技术，所以本章有时不使用Java所提供的LinkedList类，而采用数组来模拟链表。
LinkedList类的使用方法比较简单，这里记录了Java.utility中Linkedlist类的使用方法及其方法的功能供读者参考。
1．LinkedList类的使用方法
Importjava.util.LinkedList;
2．LinkedList类的构造方法
●publicLindedList（）：
建立一个空的链表。
●publicLinkedList（Collectionc）：
将CollectionC中的数据依序建立一个链表达式。
3．LinkedList类的方法
●publicObjectgetFirst（）：
返回链表中一个元素。
●publicObjectgetLast（）：
返回链表中最后一个元素。
●publicObjectremoveFirst（）：
删除链表中第一个元素，并将该值返回。
●publicObjectremoveLast（）：
删除链表中最后一个元素，并将该值返回。
●publicvoidaddFirst（Objecto）：
将 Object插入在链表开头位置。
●publicvoidaddLast（Objecto）：
将Object插入在链表结尾位置。
●publicbooleancontains（Objecto）：
检查Objecto是否在链表中，如果存在则返回ture,反之则返回false。
●publicintsize（）：
返回链表的元素个数。
●publicbooleanadd（Objecto）：
将Objecto插入在链表结尾位置，并返回ture。
●publicbooleanremove（Objecto）：
将Objecto在链表中第一次出现的元素删除，成功的话则返回ture。
●publicbooleanaddAll（Collectionhc）：
将Collectionc中的数据依序插入在链表尾端。
●publicbooleanaddAll（intindex,collectionc）：
将Collectionc中的数据依序插入在链表中index位置之后，并将index位置之后的元素依序插入在Collectionc之后，连接成一个完整的链表。
●publicvoidclear（）：
删除链表中所有的元素。
●publicObjectget（intindex）：
返回链表中index位置的元素。
●publicObjectset（intindex,Objectelement）：
以Objectelement取代链表中index位置的元素。
●publicvoidadd（intindex,Objectelement）：
将Objectelement插入在链表中index位置之后，并将index位置之后的数据插入在Objectelement之后，连接成一个完整的链表。
●publicObjectremove（intindex）：
删除链表中index位置的元素。
●publicintindwxdOf（Objecto）：
返回Objecto在链表中第一次出现的位置，如果不存在则返回-1。
●publicintlastIndexOf（Objecto）：
返回Objecto在链表中最后出现的位置，如果不存在则返回-1
●publicListIteratorlistIterator（intindex）：
返回从链表index位置开始的元素内容。
3.2.2线性链表
链表是线性表的链式存储结构，是把线性表的数据元素存放在结点中，结点是有数据域和一个或几个指针域组成，指针指向后继或其他结点的地址。
以动态内存配置的链表，在插入或删除元素时，只需将指针改变指向即可。
1.单链表结构定义
单链表的的头指针为head，指向链表中第一个结点的地址，结构如下图所示：
head
Data
Pointer
D
NULL
Data
Pointer
A
Data
Pointer
C
Data
Pointer
B
1．单向链表的结点结构
classNode
{
intData[]=newint[ArraySize];//用于存储链表的数据
intNext[]=newint[ArraySize];//用于存储下一个结点的位置
}
2．声明一个变量为结点结构
Node变量名称=NewNode（）；
同时，需要增加一个变量Header作为记录第１个结点开始的位置。
假设第一个结点从0开始。
Intheader=0;.若结点为链表中最后一个结点，则该结点的下一个结点位置则以“-1”表示指向NULL。
2.建立单链表
现在要把3个结点依次串连起来，则操作过程如下：
Header=Node_1;//设Node_1的位置为首结点位置
NewList.Next[Node_1]=Node_2;
NewList.Next[Node_2]=Node_3;
Data
Next
Alan
Node_1
Data
Next
Bob
Node_2
Data
Next
Bob
NULL
Node_3
下面用一个程序实例来说明链表的建立
1．程序目的
设计一个将输入的数据建立成链表、输出链表数据的程序。
2．程序构思
（1）链表的建立：
先声明一个结点，并记录其位于Header，而且将NewList.Next[Header]设为-1。
每输入一个数据就把原链表尾端的Next数组值设为新数据的位置。
并且将新数据的Next。
数组值设为-2。
（2）链表中可用空间的查找：
从链表数组中查找一个未用的空间，并将该空间的下标值返回。
（3）链表数据的输出：
先将pointer设为Header的值，将Pointer结点（即第一个结点）的数据输出。
然后再找出Pointer结点的下一个结点位置，将Pointer设为下一个结点的位置，再将Pointer结点的数据输出。
重复执行此步骤直到Pointer指针指向-2为止。
3．程序源代码
01importConsoleReader.*;//引入已定义的数据输入类
02
03publicclasscreate
04{
05publicstaticvoidmain（Stringargs[]）
06{
07NodeNewList=newNode（）;//产生一个Node类
08 intHeader=0;//链表首结点位置
09 intDataNum=0;//数据的编号
10StringDataName;//数据的名称
11 intFreeNode;//可用结点位置
12
13 while（true）
14{
15DataNum++;//数据编号递增
16 //查找可用结点位置
17 FreeNode=NewLIst.FindFree（）;
18ConsoleReaderconsole=newConsoleReader（System.in）;
19System.out.print（“Pleaseinputthedatname:
”）;
20//读入数据的名称
21DataName=console.readLine（）;
22 //结束条件
23if（DataName.equals（“0”））
24Break;
25
26NewList.Create（Header,FreeNode,DataNum,DataName）;
27}
28NewList.PrintList（Header）; //输出链表数据
29}
30}
31
32ClassNode
33{
34intMaxLength=20; //定义链表最大长度
35intNum[]=newint[MaxLength];//链表的数据项
36StringName[]=newString[MaxLength];//链表的数据项
37intNext[]=newint[MaxLength];//链表的下一个结点位置
38
39publicNode（） //Node构造方法
40{
41for（inti=0;i42Next[i]=-2;//-2表示未用结点
43}
44
45//--------------------------------------------------------------------------------------------------------------
46//查找可用结点位置
47 //--------------------------------------------------------------------------------------------------------------
48 publicintFindFree（）
49{
50inti;
51
52for（i=0;i53if（Next[i]==-2）
54break;
55returni;
56}
57
58//----------------------------------------------------------------------------------------------------
59输出链表数据
60//-----------------------------------------------------------------------------------------------------
61publicvoidPrintList（intHeader）
62{
63intPointer;
64
65Pointer=Header;
66while（Pointer!
=-1）
67{
68System.out.println（“##InputData##”）;
69System.out.println（“DataNumber:
”+Num[Pointer]）;
70System.out.println（“DataName:
”+Name[Pointer]）;
71Pointer=Next[pointer];
72}
73}
74//----------------------------------------------------------------------------------------------------------
75//建立链表
76//-----------------------------------------------------------------------------------------------------------
77publicvoidCreate（intHeader,intFreeNode,intDataNum,StringDataName）
78{
79intPointer;//现在的结点位置
80
81if（Header==FreeNode）//新的链表
82 {
83Num[Header]=DataNum;// 设定数据编号
84Name[Header]=DataName; //设定数据名称
85Next[Header]=-1;//设定下个结点的位置，-1表示空结点
86}
87else
88{
89Pointer=Header; //现在的结点为首结点
90Num[FreeNode]=DataNum;//设定数据编号
91 //设定数据名称
92Name[FreeNode]=DataName;
93Next[FreeNode]=-1; //设定下个结点的位置，-1表示空结点
94 //查找链表尾端
95
96While（Next[Pointer]!
=-1）
97Pointer=Next[Pointer];
98 //将新结点串连在原链表尾端
99
100Next[Pointer]=FreeNode;
101}
102}
103}
3.2.3单链表的操作
1．单链表的查找
在单链表中查找数据，只能采用顺序查找，即从第一个结点开始，依次按指针往下一个结点查找。
下面用一个程序实例来说明如何在单链表中查找数据
１．程序目的
设计一个查找链表中数据的程序
2．程序源代码
01importConsoleReader.*;
02
03publicclasssearch
04{
05
06publicstaticvoidmain（Stringargs[]）
07{
08intData[][]={{3,9,25,5,7},{26,65,80,2,6},
09{1050,3850,1000,5670,2250},{9650,2380,1700,3000,2000}};
10
11NodeNewList=newNode（）;//产生一个Node类的对象
12intDataNum;//数据的编号
13intDataTotal; //数据的总数
14intHeader=0;//首结点位置
15intFreeNode;//可用结点
16inti;//循环计数变量
17intSearchTime;//查找次数
18
19for（i=0;i<10;i++）
20{
21FreeNode=NewList.FindFree（）
22DataNum=Data[0][i];//设定数据编号
23DataTotal=Data[1][i];//设定数据总数
24
25NewList.Create（Header,FreeNode,DataNum,DataTotal）;
26}
27
28System.out.print（“Pleaseinputthedatanumber:
”）;
29 //读入数据的编号
30ConsoleReaderconsole=newConsoleReader（System.in）;
31
32DataNum=console.readInt（）;
33
34SearchTime=NewList.Search（DataNum,Header）;
35
36if（searchTime>0）//查找链表数据
37System.out.println（“SearchTime=”+SearchTime）;
38else
39System.out.println（“NotFound!
”）;
40}
41
42}
43
44classNode
45{
46intMaxLength=20;//定义链表最大长度
47intNum[]=newint[MaxLength];//链表的数据项
48intTotal[]=newint[MaxLength];//链表的数据项
49intNext[]=newint[MaxLength]; //链表的下一个结点位置
50
51publicNode（） //Node构造方法
52{
53for（i=0;i54Next[i]==-2;//-2表示未用结点
55}
56
57//-------------------------------------------------------------------------------------------------------
58//查找可用结点位置
59//--------------------------------------------------------------------------------------------------------
60publicintFindFree（）
61{
62inti;
63
64for（i=0;i65if（Next[i]==2）
66break;
67returni;
68}
69
70//-------------------------------------------------------------------------------------------------------
71//查找链表数据
72//-------------------------------------------------------------------------------------------------
升级会员 