IT计算机课件链表3

第三章线性表

3.1线性表

3.1.1线性表的定义

如果一个数据元素序列满足：

(1)除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据

元素；

(2)第一个数据元素没有前驱数据元素；

(3)最后一个数据元素没有后继数据元素。

则称这样的数据结构为线性结构。

线性表是相同类型的数据元素的有限序列。是一种可以在任意位置进行插入和删除数据元素

操作的线性结构。

一个有n个数据元素aO,al,a2,…,an-1的线性表通常用符号(aO,al,a2,an-1)表示，其中

符号ai(OWiWn-1)表示第i个抽象数据元素。其中n为表的长度，n=0为空表。

3.1.2线性表的顺序存储

线性表的顺序存储，就是把线性表的数据元素存储在一块连续地址空间的内存单元中。这样

线性表中，逻辑上相邻的数据元素在物理存储地址上也相邻，数据元素间的逻辑上的前驱、后继

逻辑关系就表现在数据元素的存储单元的物理前后位置关系上。

实现顺序存储结构的方法是使用数组。

顺序表的存储结构如图所示。

%

"o4a24%

0123456maxSize-l

size=6

其中，a0,al,a2等表示顺序表中存储的数据元素，listArray表示存储数据元素的数组，maxSize

表示数组的最大允许数据元素个数，size表示数组的当前数据元素个数。

3.1.3线性表的操作

1.查找

intlistFind(SeqLists,intx){

fbr(inti=0;i<s.size;i++){

if(s.list[i]==x)returni;

|

return-1;

2.逆置

publicvoidconverse(SeqLists)

intmid,i;

intx;

mid=s.size/2;

fbr(i=0;i<mid;i++)

{

x=s.list[i];

s.list[i]=s.list[s.size-l-i];

s.list[s.size-l-i]=x;

3.在顺序表的第I个位置上插入新元素

(1)算法步骤

先将第i到第n个元素后移一个位置，然后在第i个位置上插入给定值。

(2)程序实现

Publicvoidinsert(intI,intk)

|

Intj;

If(!isfull())

(

If(i<=0)i=l;

If(i>n)i=n+l;

For(j=n-l;j>=i-l;j-)

Table[j+1]=table[j];

Table[i-l]=k;

N++;

}

Else

Syatem.out.println(“数组已满，无法插入！”);

)

4.删除顺序表的第I个元素

(1)算法步骤

将第i+1到第n个元素依次前移一个位置。

(2)程序实现

Punlicvoiddelete9intk)

(

Inti=indexof(k);

If(i!=-1)

For(intj=I;j<n-l;j++)

Table[j]=table|j+1];

Table[n-l]=O;

Else

System.out.println（k+”值未找到，无法删除巧;

5.顺序表的算法分析

插入和删除是顺序表中时间复杂度最高的成员函数。插入时.，主要的耗时部分是循环移动数

据元素部分。循环移动数据元素的效率和插入的位置i有关，最坏情况是i=0,需移动size个数据

元素；最好情况是i=size,需移动0个数据元素。平均次数为：

&=Zp，（〃-Q=々

,=o〃+1”02

类似地，删除时，平均次数为：

〃-1I〃-1n—}

&=Z0--Z（〃-Q=丁

/=o〃/=02

顺序表中的其余操作都和数据元素个数n无关，因此在顺序表中插入和删除一个数据元素成

员函数的时间爱杂度为O（n）o

顺序表支持随机读取，因此，顺序表取数据元素的时间复杂度为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,

反之则返回falsec

•publicintsize()：返回链表的元素个数。

•publicbooleanadd(Objecto)：将Objecto插入在链表结尾位置，并返回tureo

•publicbooleanremove(Objecto)：将Objecto在链表中第一次出现的元素删除，成功的

话则返回tureo

•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在链表中第一次出现的位置，如果不存在

则返回

•publicintlastIndexOf(Objecto)：返回Objecto在链表中最后出现的位置，如果不存在则

返回・1

•publicListiteratorlistlterator(intindex)：返回从链表index位置开始的元素内容。

3.2.2线性链表

链表是线性表的链式存储结构，是把线性表的数据元素存放在结点中，结点是有数据域和一

个或几个指针域组成，指针指向后继或其他结点的地址。以动态内存配置的链表，在插入或删除

元素时，只需将指针改变指向即可。

1.单链表结构定义

单链表的的头指针为head,指向链表中第一个结点的地址，结构如下图所示:

head

DataPointerDataPointerDataPointerDataPointer

A—BC—»DNULL

1.单向链表的结点结构

classNode

intData[]=newint[ArraySize];//用于存储链表的数据

intNext[]=newint[ArraySize];〃用于存储下一个结点的位置

2.声明一个变量为结点结构

Node变量名称=NewNode()；

同时，需要增加一个变量Header作为记录第1个结点开始的位置。假设第一个结点从0开始。

Intheader=0;.若结点为链表中最后一个结点，则该结点的下一个结点位置则以“-1”表示指向

NULL。

2.建立单链表

现在要把3个结点依次串连起来，则操作过程如下：

Header=Node_l;〃设Node」的位置为首结点位置

NewList.Next[Node_l]=Node_2;

NewList.Next[Node_2]=Node_3;

Node3NULL

下面用•个程序实例来说明链表的建立

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类

08intHeader=0;〃链表首结点位置

09intDataNum=0;〃数据的编号

10StringDataName;〃数据的名称

11intFreeNode;〃可用结点位置

12

13while(true)

14

15DataNumH;//数据编号递增

16〃查找可用结点位置

17FreeNode=NewLIst.FindFree();

18ConsoleReaderconsole=newConsoleRcader(System.in);

19System.out.print(uPleaseinputthedatname:")；

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;i<MaxLength;i++)

42Next[i]=-2;//-2表示未用结点

43

44

45//----------------------------------------------------------------------------

46〃查找可用结点位置

47//----------------------------------------------------------------------------

48publicintFindFree()

49

50inti;

51

52fbr(i=O;i<MaxLength;i-H-)

53if(Next[i]=-2)

54break;

55returni;

56

57

58//-------------------------------------------------------------------------

59输出链表数据

60//--------------------------------------------------------------------------

61publicvoidPrintList(intHeader)

62

63intPointer;

64

65Pointer=Header;

66while(Pointer!=-l)

67(

68System.out.println(46##InputData##");

69System.out.println(uDataNumber:,,-i-Num[Pointer]);

70System.out.println(4fcDataName:"+Name[PointeH);

71Pointer=Next[pointer];

72}

73)

74//-----------------------------------------------------------------------------

75〃建立链表

76//------------------------------------------------------------------------------

77publicvoidCreate(intHeader,intFreeNode,intDataNum,StringDataName)

78{

79intPointer;〃现在的结点位置

80

81iHeader==FreeNode)〃新的链表

82

83Num[Header]=DataNum;//设定数据编号

84Name[Header]=DataName;//设定数据名称

85Next[Header]=-l;〃设定下个结点的位置，-1表示空结点

86i

87else

88

89Pointer=Header;〃现在的结点为首结点

90Num[FreeNode]=DataNum;〃设定数据编号

91〃设定数据名称

92Name[FreeNode]=DataName;

93Next[FreeNode]=-1;〃设定下个结点的位置，表示空结点

94〃查找链表尾端

95

96While(Next[Pointer]!=-1)

97Pointer=Next[Pointer];

98〃将新结点串连在原链表尾端

99

100Next[Pointer]=FreeNode;

101

102

103

3.2.3单链表的操作

1.单链表的查找

在单链表中查找数据，只能采用顺序查找，即从第一个结点开始，依次按指针往下一个结点

查找。

下面用一个程序实例来说明如何在单链表中查找数据

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

19fbr(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

28Systcm.out.printCTleaseinputthedatanumbcr:^^);

29〃读入数据的编号

30ConsoleReaderconsole=newConsoleReader(System.in);

31

32DataNum=console.readlnt();

33

34SearchTime=NewList.Search(DataNum,Header);

35

36if(searchTime>0)//查找链表数据

37System.out.printlnC'SearchTime=,,+SearchTime);

38else

39System.out.println(tfcNotFound!^^);

40

41

42)

43

44classNode

45(

46intMaxLength=20;〃定义链表最大长度

47intNum[]=newint[MaxLength];〃链表的数据项

48intTotal[]=newint[MaxLength];〃链表的数据项

49intNext[]=newint[MaxLength];〃链表的下一个结点位置

50

51publicNode()//Node构造方法

52{

53fbr(i=O;i<MaxLength;i++)

54Next[i]=-2;//-2表示未用结点

55

56

57//------------------------------------------------------------------------

58〃查找可用结点位置

59//------------------------------------------------------------------------

60publicintFindFree()

61(

62inti;

63

64fbr(i=O;i<MaxLength;i++)

65ifl[Next[i]==2)

66break;

67returni;

68

69

70//------------------------------------------------------------------------

71〃查找链表数据

72//------------------------------------------------------------------------

73publicintSearch(intKeyValue,intHeader)

74(

75intPointer;

76intSearchTime=0;〃查找次数

77

78Pointer=Header;

79while(Pointer!=-l)

80(

81SearchTime++;

82if(KeyValue==Num[Pointer])

83(

84System.out.println(46##InputData##");

85System.out.println(4€DataNumberi^+NumfPointer]);

86System.out.println(<4DataTotak^+TotaltPointer]);

87returnSearchTime;

88)

89Pointer=Next[Pointer];

90}

91return0;

92}

93//----------------------------------------------------------------------

94〃建立链表

95//----------------------------------------------------------------------

96publicvoidCreate(intHeader,intFreeNode,intDataNum,intDataTotal)

97(

98intPointer;〃现在的结点位置

99

100if(Header=FreeNode)〃新的链表

101

102Num[Header]=DataNum;〃设定数据编号

103Total[Header]=DataTota1;〃设定数据名称

104Next[Header]=-l;//设定下个结点的位置，-1表示空结点

105}

106else

107

108Pointer=Header;〃现在的结点为首结点

109Num[FreeNode]=DataNum;〃设定数据编号

110〃设定数据名称

111Tota1[FreeNode]=DataTota1;

112Next[FreeNode]=-l;〃设定下个结点的位置,-1表示空结点

113〃查找链表尾端

114while（Next[Pointer]!=-1）

115Pointer=Next[Pointer];

116

117〃将新结点串连在原链表尾端

118Next[Pointer]=FreeNode;

119}

120}

121}

2.单链表的结点插入

（I）.插入点在链表开头

新的结点插入在链表的开头，需要将新结点的指针指向链表的首结点，并将链表的首结点设

为新结点。

NewList.Next[NewNode]=Pointer

HEAD=NewNode

（2）插入点在链表中间

插入前：

Head」|二...」141IINULL

PointerPointer->Next

插入后:

NewNode

Head__>NULL

新的结点插入在链表的中间，如果我们找到Pointer结点，则需要将新结点的指针指向Pointer

结点的指针（即下一个结点），但不能让链表断裂。所以首先将新结点的指针指向Pointer结点的指

针，再将Pointer结点的指针指向新结点。

NewList.Next[NewNode]=NewList.Next[Pointer]

NewList.Next[Pointer]=NewNode

（3）.插入点在链表尾端

新的结点插入在链表的尾端（pointer结点），首先将新结点的指针指向Pointer结点的指针

（NULL）,再将Pointer结点的指针指向新结点。

NewList.Next[NewNode]=NewList.Next[Pointer]

NewList.Next[Pointer]=NewNode

（4）.在链表中插入结点的程序实现

•程序目的

设计一个链表内插入结点的程序

•程序构思

（1）声明一个新结点

（2）声明一个结点指针指向头指针

（3）若指针不空，持续往下一个结点，直到结点内容等于Key或结点指针为NULL（即

找不到该结点）。

①如果该结点不存在，则插入在首结点前：

NewList.Next[NewNode]=Header;

Header=NewNode;

②如果找到该结点，贝小

NewList.Next[NewNode]=NewList.Next[pointer];

NewList.Next[Pointer]=NewNode;

•程序源代码

01importConsoleReader.*〃引入己定义的数据输入类

02

03Publicclassinsert

04{

05Publicstaticvoidmain（Stringargs[]）

06{

07intData□□={{1,3,5,7,2,4,6,8,9,0},{15,35,10,67,25,65,38,70,30,20）};

08

09NodeNewList=newNode（）;//产生一个Node类的对象

10intDataNum;〃数据的编号

11intDataTotal;〃数据的总数

12intKeyValue;//欲插入位置

13intHeader=0;〃首结点位置

14intFreeNode;〃可用结点

15intNewNode;//新结点位置

16inti;

17

18fbr(i=0;i<10;i-H-)

19(

20FreeNode=NewList.FindFree();

21DataNum=Data[0][i];//设定数据编号

22DataTotal=Data[l][i];〃设定数据总数

23

24NewList.Create(Header,FreeNode,DataNum,DataToal);

25}

26

27NewList.PrintList(Header);

28System.out.println(46Enter0toEXIT")；

29

30while(true)

31(

32NewNode=NewList.FindFree();

33System.out.printf'Pleaseinputthedatanumber:'');

34〃读入数据的编号

35ConsoleReaderconsole=newConsoleReader(System.in);

36

37DataNum=console.readlnt();

38

39if(DataNum==0)

40break;

41

42System.out.printCTleaseinputthedatatotal:,,);

43〃读入数据的总数

44DataTotal=console.readInt();

45

46NewList.Num[NewNode]=DataNum;

47NewList.Total[NewNode]=DataTotal;

48System.out.print(44pleaseinputthedatanumberfbrInsert:,,);

49〃读入欲插入位置

50KeyValue=console.readInt();

51〃调用插入结点

52Header=NewList.Insert(Header,NewNode,KeyValue);

53NewList.PrintList(Header);

54System.out.println(<4Enter0toEXIT9);

55

56

57

58

59

60classNode

61

62intMaxLength=20;//定义链表最大长度

63intNum[]=newintfMaxLength];〃链表的数据项

64intTotal[]=NewInt[MaxLength];〃链表的数据项

65intNext[]=newint[MaxLength];〃链表的下一个结点位置

66

67publicNode()//Node构造方法

68{

69fbr(inti=O;i<MaxLength;i++)

70Next[i]=-2;//-2表示未用结点

71)

72

73//----------------------------------------------------------

74〃查找可用结点位置

75//-----------------------------------------------------------

76publicintFindFree()

77{

78inti;

79

80for(i=O;i<MaxLength;i++)

81if(Next[i]==-2)

82break;

83returni;

84

85

86//-----------------------------------------------------------

87〃建立链表

88//------------------------------------------------------------

89publicvoidCreate(intHeader,intFreeNodeJntDataNum,intDataTotal)

90|

91intPointer;〃现在的结点位置

92

93ieader==FreeNode)//新的链表

94{

95Num[Header]=DataNum;〃设定数据编号

96Total[Header]=DataTotal;〃设定数据名称

97Next[Header]=-l;〃设定下个结点的位置，-1表示空结点

98

99Else

100

101Pointer=Header;〃现在的结点为首结点

102Num[FreeNode]=DataNum;〃设定数据编号

103〃设定数据名称

104Total[FreeNode]=DataTotal;

105Next[FreeNode]=-l;〃设定下个结点的位置,表示空结点

106//查找链表尾端

107While(Next[Pointer]!=-1)

108Pointcr=Next[Pointer];

109

110//将新结点串连在原链表尾端

111Next[Pointer]=FreeNode;

112)

113

114

115//------------------------------------------------------------

116〃输入链表数据

117//-------------------------------------------------------------------

118publicvoidPrintList(intHeader)

119(

120intPointer;

121

122Pointer=Header;

123While(Pointer!=-l)

124(

125System,out.print(u+Num[Pointer]v);

126System.out.print("J+Total[Pointer]+")”);

127Pointer=Next[Pointer];

128}

129System.out.printlnC4

130

131

132//-----------------------------------------------------------------------

133〃插入结点至链表内

134//------------------------------------------------------------------------

135PublicintInsert(intHeader,intNewNode,intKeyValue)

136{

137intPointer;//结点说明

138

139Pointer=Header;//Pointer指针设为首结点

140

141While(ture)

142

143if(Pointer==-l)〃插入在首结点前

144{

145Next[NewNode]=Header;

146Header=NewNode;

147break;

148}

149If(Num[Pointer]=KeyValue)〃插入在链表中间或尾端

150(

151Next[NewNode]=Next[Pointer];

152Next[pointer]=NewNode;

153break;

154}

155Pointer=Next[Pointer];〃往下一个结点

156)

157returnHeader;

158}

159)

3.单链表的结点删除

（1）.删除链表首结点

删除的结点在链表的开头，需要将首结点指向首结点的指针（即下•个结点），并将原来的结

点从内存中释放。

Header=NewList.Next[Pointer];

NewList.Next[Pointer]=-2

（2）.删除链表中间结点

删除前：

NULL

Header_k|一口_►|一厂一厂—F4*•…!—F4*

BackPointerNextfPointer]

删除后：

],NULL

删除的结点在链表的中间，如果我们找到Pointer结点，则需要将前一个结点的指针指向

Pointer结点的指针（即下一个结点），并将原来的结点从内存中释放。

NewList.Next[Back]=NewLIst.Next[pointer];

NewList.Next[Pointer]=-2

（3）.删除链表尾端的结点

删除的结点在链表的尾端（Pointer结点），如果我们找到Pointer结点，则需要将前一个结点

的指针指向Pointer结点的指针（NULL）,并将原来的结点从内存中释放。

NewList.Next[Back]=NewList.Next[Pointer];

NewList.Next[Pointer]=-2;

（4）.在单链表中删除结点的程序实例。

•程序目的

设计一个删除链表内结点的程序

•程序构思

持续往下一个结点查找欲删除结点，直到结点内容找到或结点指针为NULL（即找不到该

结点）。在删除时，必须记录前一个结点的位置（Back）。

（1）如果该结点不存在，输出消息说结点不存在。

（2）如果该结点存在，且是首结点：

Header=NewList.Next[Pointer];

NewList.Next[Pointer]=-2;

（3）如果该结点存在，但非首结点（即链表的中间结点或尾端结点），贝IJ：

NewList.Next[Back]=NewList.Next[Pointer];

NewList.Next[Pointer]=-2;

•程序源代码

01importConSolereader.*;〃引入已定义的数据输入类

02

03publicclassdelete

04{

05publicstaticvoidmain(Stringargs[])

06{

07intData[][]={{!,3,5,7,2,4,6,8,9,0},{15,35,10,67,25,65,38,70,30,20)};

08

09NodeNewList=newNode();//产生一个Node类

10intDataNum;]//数据的编号

11intDataTotal;〃数据的总数

12intKeyValue;//欲插入位置

13intHeader=0;〃首结点位置

14intFreeNode;//可用结点

15inti;//循环计数变量

16

17fbr(i=0;i<10;i-H-)

18{

19FreeNode=NewList.FindFree();

20DataNum=Data[0][i];〃设定数据编号

21DataTotal=Data[l][i];〃设定数据总数

22

23NewList.Create(Header,FreeNode,DataNum,DataTotal);

24

25

26NewList.PrintList(Header);

27System.out.println(<4Enter0toEXIT");

28

29while(true)

30{

31System.out.print(44PleaseinputthedatanumberforInsert:");

32//读入删除位置

33Consolereaderconsole=newConsolereader(System.in);

34KeyValue=console.readInt();

35if(KeyValue=0)

36Break;

37〃调用删除结点

38Header=NewList.Delete(Header,KeyValue);

39NewList.PrintList(Header);

40System.out.println(<4Enter0toEXIT");

41}

42

43

44

45

46ClassNode

47(

48intMaxLength=20;//定义链表最大长度

49intNum[]=newint[MaxLength];〃链表的数据项

50intTotal[]=newint[MaxLength];〃链表的数据项

51intNext[]=newint[MaxLength];〃链表的下一个结点位置

52

53PublicNode()//Node构造方法

54{

55fbr(inti=O;i〈MaxLength;i++)

56Next[i]=-2;//-2表示未用结点

57

58

59//-------------------------------------------------------------------------------------------------------------

60〃查找可用结点位置

61//---------------------------------------------------------------------------------------------------------------

62PublicintFindFree()

63{

64inti;

65

66fdr(i=0;i<MaxLength;i++)

67if(Next[i]=-2)

68break;

69returni;

70

71

72//------------------------------------------------------------------------

73〃建立链表

74//-------------------------------------------------------------------------

75PublicvoidCreate(intHeader,intFreeNode,intDataNum,intD