IT計(jì)算機(jī)課件鏈表3_第1頁
IT計(jì)算機(jī)課件鏈表3_第2頁
IT計(jì)算機(jī)課件鏈表3_第3頁
IT計(jì)算機(jī)課件鏈表3_第4頁
IT計(jì)算機(jī)課件鏈表3_第5頁
已閱讀5頁,還剩43頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

第三章線性表

3.1線性表

3.1.1線性表的定義

如果一個(gè)數(shù)據(jù)元素序列滿足:

(1)除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外,每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)

元素;

(2)第一個(gè)數(shù)據(jù)元素沒有前驅(qū)數(shù)據(jù)元素;

(3)最后一個(gè)數(shù)據(jù)元素沒有后繼數(shù)據(jù)元素。

則稱這樣的數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。

線性表是相同類型的數(shù)據(jù)元素的有限序列。是一種可以在任意位置進(jìn)行插入和刪除數(shù)據(jù)元素

操作的線性結(jié)構(gòu)。

一個(gè)有n個(gè)數(shù)據(jù)元素aO,al,a2,…,an-1的線性表通常用符號(aO,al,a2,an-1)表示,其中

符號ai(OWiWn-1)表示第i個(gè)抽象數(shù)據(jù)元素。其中n為表的長度,n=0為空表。

3.1.2線性表的順序存儲(chǔ)

線性表的順序存儲(chǔ),就是把線性表的數(shù)據(jù)元素存儲(chǔ)在一塊連續(xù)地址空間的內(nèi)存單元中。這樣

線性表中,邏輯上相鄰的數(shù)據(jù)元素在物理存儲(chǔ)地址上也相鄰,數(shù)據(jù)元素間的邏輯上的前驅(qū)、后繼

邏輯關(guān)系就表現(xiàn)在數(shù)據(jù)元素的存儲(chǔ)單元的物理前后位置關(guān)系上。

實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)的方法是使用數(shù)組。

順序表的存儲(chǔ)結(jié)構(gòu)如圖所示。

%

"o4a24%

0123456maxSize-l

size=6

其中,a0,al,a2等表示順序表中存儲(chǔ)的數(shù)據(jù)元素,listArray表示存儲(chǔ)數(shù)據(jù)元素的數(shù)組,maxSize

表示數(shù)組的最大允許數(shù)據(jù)元素個(gè)數(shù),size表示數(shù)組的當(dāng)前數(shù)據(jù)元素個(gè)數(shù)。

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個(gè)位置上插入新元素

(1)算法步驟

先將第i到第n個(gè)元素后移一個(gè)位置,然后在第i個(gè)位置上插入給定值。

(2)程序?qū)崿F(xiàn)

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(“數(shù)組已滿,無法插入!”);

)

4.刪除順序表的第I個(gè)元素

(1)算法步驟

將第i+1到第n個(gè)元素依次前移一個(gè)位置。

(2)程序?qū)崿F(xiàn)

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.順序表的算法分析

插入和刪除是順序表中時(shí)間復(fù)雜度最高的成員函數(shù)。插入時(shí).,主要的耗時(shí)部分是循環(huán)移動(dòng)數(shù)

據(jù)元素部分。循環(huán)移動(dòng)數(shù)據(jù)元素的效率和插入的位置i有關(guān),最壞情況是i=0,需移動(dòng)size個(gè)數(shù)據(jù)

元素;最好情況是i=size,需移動(dòng)0個(gè)數(shù)據(jù)元素。平均次數(shù)為:

&=Zp,(〃-Q=々

,=o〃+1”02

類似地,刪除時(shí),平均次數(shù)為:

〃-1I〃-1n—}

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

/=o〃/=02

順序表中的其余操作都和數(shù)據(jù)元素個(gè)數(shù)n無關(guān),因此在順序表中插入和刪除一個(gè)數(shù)據(jù)元素成

員函數(shù)的時(shí)間愛雜度為O(n)o

順序表支持隨機(jī)讀取,因此,順序表取數(shù)據(jù)元素的時(shí)間復(fù)雜度為O(1)。

順序表的主要優(yōu)點(diǎn)是:支持隨機(jī)讀取,以及內(nèi)存空間利用效率高。

順序表的主要缺點(diǎn)是:需要預(yù)先給出(很難準(zhǔn)確)數(shù)組的最大數(shù)據(jù)元素個(gè)數(shù),另外,插入和

刪除操作時(shí)需要移動(dòng)較多的數(shù)據(jù)元素。

3.2線性鏈表

3.2.1概述

Java語言雖然刪除了Pointer類型,但是還可以運(yùn)用數(shù)組來模擬出鏈表。不僅如此,Java語言

中還有一個(gè)Java..utility的類庫供了鏈表的類供程序設(shè)計(jì)者使用,讀者如果對于這個(gè)鏈表的類有興

趣可在JDK的目錄下,找到一個(gè)叫src.jar的文件,使用解壓縮軟件來打開這個(gè)文件,就可以在

\src\java\util的目錄下找到一個(gè)叫LinkedList.java的文件,其中就是鏈表的相關(guān)程序代碼。

本書的重點(diǎn)在于幫助讀者建立數(shù)據(jù)結(jié)構(gòu)概念,而非面向?qū)ο蟪绦蚣夹g(shù),所以本章有時(shí)不使用

Java所提供的LinkedList類,而采用數(shù)組來模擬鏈表。LinkedList類的使用方法比較簡單,這里記

錄了Java.utility中Linkedlist類的使用方法及其方法的功能供讀者參考。

1.LinkedList類的使用方法

Importjava.util.LinkedList;

2.LinkedList類的構(gòu)造方法

?publicLindedList():建立一個(gè)空的鏈表。

?publicLinkedList(Collectionc):將CollectionC中的數(shù)據(jù)依序建立一個(gè)鏈表達(dá)式。

3.LinkedList類的方法

?publicObjectgetFirst():返回鏈表中一個(gè)元素。

?publicObjectgetLast():返回鏈表中最后一個(gè)元素。

?publicObjectremoveFirst():刪除鏈表中第一個(gè)元素,并將該值返回。

?publicObjectremoveLast():刪除鏈表中最后一個(gè)元素,并將該值返回。

?publicvoidaddFirst(Objecto):將Object插入在鏈表開頭位置。

?publicvoidaddLast(Objecto):將Object插入在鏈表結(jié)尾位置。

?publicbooleancontains(Objecto):檢查Objecto是否在鏈表中,如果存在則返回ture,

反之則返回falsec

?publicintsize():返回鏈表的元素個(gè)數(shù)。

?publicbooleanadd(Objecto):將Objecto插入在鏈表結(jié)尾位置,并返回tureo

?publicbooleanremove(Objecto):將Objecto在鏈表中第一次出現(xiàn)的元素刪除,成功的

話則返回tureo

?publicbooleanaddAll(Collectionhc):將Collectionc中的數(shù)據(jù)依序插入在鏈表尾端。

?publicbooleanaddAll(intindex,collectionc):將Collectionc中的數(shù)據(jù)依序插入在鏈表中

index位置之后,并將index位置之后的元素依序插入在Collectionc之后,連接成,個(gè)

完整的鏈表。

?publicvoidclear():刪除鏈表中所有的元素。

?publicObjectget(intindex):返回鏈表中index位置的元素。

?publicObjectset(intindex,Objectelement):以O(shè)bjectelement取代鏈表中index位置的元

素。

?publicvoidadd(intindex,Objectelement):將Objectelement插入在鏈表中index位置之

后,并將index位置之后的數(shù)據(jù)插入在Objectelement之后,連接成一個(gè)完整的鏈表。

?publicObjectremove(intindex):刪除鏈表中index位置的元素。

?publicintindwxdOf(Objecto):返回Objecto在鏈表中第一次出現(xiàn)的位置,如果不存在

則返回

?publicintlastIndexOf(Objecto):返回Objecto在鏈表中最后出現(xiàn)的位置,如果不存在則

返回?1

?publicListiteratorlistlterator(intindex):返回從鏈表index位置開始的元素內(nèi)容。

3.2.2線性鏈表

鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),是把線性表的數(shù)據(jù)元素存放在結(jié)點(diǎn)中,結(jié)點(diǎn)是有數(shù)據(jù)域和一

個(gè)或幾個(gè)指針域組成,指針指向后繼或其他結(jié)點(diǎn)的地址。以動(dòng)態(tài)內(nèi)存配置的鏈表,在插入或刪除

元素時(shí),只需將指針改變指向即可。

1.單鏈表結(jié)構(gòu)定義

單鏈表的的頭指針為head,指向鏈表中第一個(gè)結(jié)點(diǎn)的地址,結(jié)構(gòu)如下圖所示:

head

DataPointerDataPointerDataPointerDataPointer

A—BC—?DNULL

1.單向鏈表的結(jié)點(diǎn)結(jié)構(gòu)

classNode

intData[]=newint[ArraySize];//用于存儲(chǔ)鏈表的數(shù)據(jù)

intNext[]=newint[ArraySize];〃用于存儲(chǔ)下一個(gè)結(jié)點(diǎn)的位置

2.聲明一個(gè)變量為結(jié)點(diǎn)結(jié)構(gòu)

Node變量名稱=NewNode();

同時(shí),需要增加一個(gè)變量Header作為記錄第1個(gè)結(jié)點(diǎn)開始的位置。假設(shè)第一個(gè)結(jié)點(diǎn)從0開始。

Intheader=0;.若結(jié)點(diǎn)為鏈表中最后一個(gè)結(jié)點(diǎn),則該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)位置則以“-1”表示指向

NULL。

2.建立單鏈表

現(xiàn)在要把3個(gè)結(jié)點(diǎn)依次串連起來,則操作過程如下:

Header=Node_l;〃設(shè)Node」的位置為首結(jié)點(diǎn)位置

NewList.Next[Node_l]=Node_2;

NewList.Next[Node_2]=Node_3;

Node3NULL

下面用?個(gè)程序?qū)嵗齺碚f明鏈表的建立

1.程序目的

設(shè)計(jì)一個(gè)將輸入的數(shù)據(jù)建立成鏈表、輸出鏈表數(shù)據(jù)的程序。

2.程序構(gòu)思

(1)鏈表的建立:先聲明一個(gè)結(jié)點(diǎn),并記錄其位于Header,而且將NewList.Next[Header]

設(shè)為-1。每輸入一個(gè)數(shù)據(jù)就把原鏈表尾端的Next數(shù)組值設(shè)為新數(shù)據(jù)的位置。并且將新

數(shù)據(jù)的Next。數(shù)組值設(shè)為-2。

(2)鏈表中可用空間的查找:從鏈表數(shù)組中查找一個(gè)未用的空間,并將該空間的下標(biāo)值返

回。

(3)鏈表數(shù)據(jù)的輸出:先將pointer設(shè)為Header的值,將Pointer結(jié)點(diǎn)(即第一個(gè)結(jié)點(diǎn))的

數(shù)據(jù)輸出。然后再找出Pointer結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)位置,將Pointer設(shè)為下一個(gè)結(jié)點(diǎn)的

位置,再將Pointer結(jié)點(diǎn)的數(shù)據(jù)輸出。重復(fù)執(zhí)行此步驟直到Pointer指針指向-2為止。

3.程序源代碼

01importConsoleReader.*;〃引入已定義的數(shù)據(jù)輸入類

02

03publicclasscreate

04{

05publicstaticvoidmain(Stringargs[])

06

07NodeNewList=newNode();〃產(chǎn)生一個(gè)Node類

08intHeader=0;〃鏈表首結(jié)點(diǎn)位置

09intDataNum=0;〃數(shù)據(jù)的編號

10StringDataName;〃數(shù)據(jù)的名稱

11intFreeNode;〃可用結(jié)點(diǎn)位置

12

13while(true)

14

15DataNumH;//數(shù)據(jù)編號遞增

16〃查找可用結(jié)點(diǎn)位置

17FreeNode=NewLIst.FindFree();

18ConsoleReaderconsole=newConsoleRcader(System.in);

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

20〃讀入數(shù)據(jù)的名稱

21DataName=console.readLine();

22〃結(jié)束條件

23if(DataName.equals("0"))

24Break;

25

26NewList.Create(Header,FreeNode,DataNum,DataName);

27

28NewList.PrintList(Header);〃輸出鏈表數(shù)據(jù)

29

30

31

32ClassNode

33

34intMaxLength=20;//定義鏈及最大長度

35intNum[]=newint[MaxLength];〃鏈表的數(shù)據(jù)項(xiàng)

36StringName[]=newString[MaxLength];//鏈表的數(shù)據(jù)項(xiàng)

37intNext[]=newint[MaxLength];〃鏈表的下一個(gè)結(jié)點(diǎn)位置

38

39publicNode()//Node構(gòu)造方法

40

41for(inti=0;i<MaxLength;i++)

42Next[i]=-2;//-2表示未用結(jié)點(diǎn)

43

44

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

46〃查找可用結(jié)點(diǎn)位置

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

48publicintFindFree()

49

50inti;

51

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

53if(Next[i]=-2)

54break;

55returni;

56

57

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

59輸出鏈表數(shù)據(jù)

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;〃現(xiàn)在的結(jié)點(diǎn)位置

80

81iHeader==FreeNode)〃新的鏈表

82

83Num[Header]=DataNum;//設(shè)定數(shù)據(jù)編號

84Name[Header]=DataName;//設(shè)定數(shù)據(jù)名稱

85Next[Header]=-l;〃設(shè)定下個(gè)結(jié)點(diǎn)的位置,-1表示空結(jié)點(diǎn)

86i

87else

88

89Pointer=Header;〃現(xiàn)在的結(jié)點(diǎn)為首結(jié)點(diǎn)

90Num[FreeNode]=DataNum;〃設(shè)定數(shù)據(jù)編號

91〃設(shè)定數(shù)據(jù)名稱

92Name[FreeNode]=DataName;

93Next[FreeNode]=-1;〃設(shè)定下個(gè)結(jié)點(diǎn)的位置,表示空結(jié)點(diǎn)

94〃查找鏈表尾端

95

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

97Pointer=Next[Pointer];

98〃將新結(jié)點(diǎn)串連在原鏈表尾端

99

100Next[Pointer]=FreeNode;

101

102

103

3.2.3單鏈表的操作

1.單鏈表的查找

在單鏈表中查找數(shù)據(jù),只能采用順序查找,即從第一個(gè)結(jié)點(diǎn)開始,依次按指針往下一個(gè)結(jié)點(diǎn)

查找。

下面用一個(gè)程序?qū)嵗齺碚f明如何在單鏈表中查找數(shù)據(jù)

1.程序目的

設(shè)計(jì)一個(gè)查找鏈表中數(shù)據(jù)的程序

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();〃產(chǎn)生一個(gè)Node類的對象

12intDataNum;〃數(shù)據(jù)的編號

13intDataTotal;〃數(shù)據(jù)的總數(shù)

14intHeader=0;//首結(jié)點(diǎn)位置

15intFreeNode;//可用結(jié)點(diǎn)

16inti;//循環(huán)計(jì)數(shù)變量

17intSearchTime;〃查找次數(shù)

18

19fbr(i=0;i<10;i++)

20

21FreeNode=NewList.FindFree()

22DataNum=Data[0][i];//設(shè)定數(shù)據(jù)編號

23DataTotal=Data[1][i];〃設(shè)定數(shù)據(jù)總數(shù)

24

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

26}

27

28Systcm.out.printCTleaseinputthedatanumbcr:^^);

29〃讀入數(shù)據(jù)的編號

30ConsoleReaderconsole=newConsoleReader(System.in);

31

32DataNum=console.readlnt();

33

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

35

36if(searchTime>0)//查找鏈表數(shù)據(jù)

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

38else

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

40

41

42)

43

44classNode

45(

46intMaxLength=20;〃定義鏈表最大長度

47intNum[]=newint[MaxLength];〃鏈表的數(shù)據(jù)項(xiàng)

48intTotal[]=newint[MaxLength];〃鏈表的數(shù)據(jù)項(xiàng)

49intNext[]=newint[MaxLength];〃鏈表的下一個(gè)結(jié)點(diǎn)位置

50

51publicNode()//Node構(gòu)造方法

52{

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

54Next[i]=-2;//-2表示未用結(jié)點(diǎn)

55

56

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

58〃查找可用結(jié)點(diǎn)位置

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

60publicintFindFree()

61(

62inti;

63

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

65ifl[Next[i]==2)

66break;

67returni;

68

69

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

71〃查找鏈表數(shù)據(jù)

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

73publicintSearch(intKeyValue,intHeader)

74(

75intPointer;

76intSearchTime=0;〃查找次數(shù)

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;〃現(xiàn)在的結(jié)點(diǎn)位置

99

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

101

102Num[Header]=DataNum;〃設(shè)定數(shù)據(jù)編號

103Total[Header]=DataTota1;〃設(shè)定數(shù)據(jù)名稱

104Next[Header]=-l;//設(shè)定下個(gè)結(jié)點(diǎn)的位置,-1表示空結(jié)點(diǎn)

105}

106else

107

108Pointer=Header;〃現(xiàn)在的結(jié)點(diǎn)為首結(jié)點(diǎn)

109Num[FreeNode]=DataNum;〃設(shè)定數(shù)據(jù)編號

110〃設(shè)定數(shù)據(jù)名稱

111Tota1[FreeNode]=DataTota1;

112Next[FreeNode]=-l;〃設(shè)定下個(gè)結(jié)點(diǎn)的位置,-1表示空結(jié)點(diǎn)

113〃查找鏈表尾端

114while(Next[Pointer]!=-1)

115Pointer=Next[Pointer];

116

117〃將新結(jié)點(diǎn)串連在原鏈表尾端

118Next[Pointer]=FreeNode;

119}

120}

121}

2.單鏈表的結(jié)點(diǎn)插入

(I).插入點(diǎn)在鏈表開頭

新的結(jié)點(diǎn)插入在鏈表的開頭,需要將新結(jié)點(diǎn)的指針指向鏈表的首結(jié)點(diǎn),并將鏈表的首結(jié)點(diǎn)設(shè)

為新結(jié)點(diǎn)。

NewList.Next[NewNode]=Pointer

HEAD=NewNode

(2)插入點(diǎn)在鏈表中間

插入前:

Head」|二...」141IINULL

PointerPointer->Next

插入后:

NewNode

Head__>NULL

新的結(jié)點(diǎn)插入在鏈表的中間,如果我們找到Pointer結(jié)點(diǎn),則需要將新結(jié)點(diǎn)的指針指向Pointer

結(jié)點(diǎn)的指針(即下一個(gè)結(jié)點(diǎn)),但不能讓鏈表斷裂。所以首先將新結(jié)點(diǎn)的指針指向Pointer結(jié)點(diǎn)的指

針,再將Pointer結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)。

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

NewList.Next[Pointer]=NewNode

(3).插入點(diǎn)在鏈表尾端

新的結(jié)點(diǎn)插入在鏈表的尾端(pointer結(jié)點(diǎn)),首先將新結(jié)點(diǎn)的指針指向Pointer結(jié)點(diǎn)的指針

(NULL),再將Pointer結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)。

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

NewList.Next[Pointer]=NewNode

(4).在鏈表中插入結(jié)點(diǎn)的程序?qū)崿F(xiàn)

?程序目的

設(shè)計(jì)一個(gè)鏈表內(nèi)插入結(jié)點(diǎn)的程序

?程序構(gòu)思

(1)聲明一個(gè)新結(jié)點(diǎn)

(2)聲明一個(gè)結(jié)點(diǎn)指針指向頭指針

(3)若指針不空,持續(xù)往下一個(gè)結(jié)點(diǎn),直到結(jié)點(diǎn)內(nèi)容等于Key或結(jié)點(diǎn)指針為NULL(即

找不到該結(jié)點(diǎn))。

①如果該結(jié)點(diǎn)不存在,則插入在首結(jié)點(diǎn)前:

NewList.Next[NewNode]=Header;

Header=NewNode;

②如果找到該結(jié)點(diǎn),貝小

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

NewList.Next[Pointer]=NewNode;

?程序源代碼

01importConsoleReader.*〃引入己定義的數(shù)據(jù)輸入類

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();//產(chǎn)生一個(gè)Node類的對象

10intDataNum;〃數(shù)據(jù)的編號

11intDataTotal;〃數(shù)據(jù)的總數(shù)

12intKeyValue;//欲插入位置

13intHeader=0;〃首結(jié)點(diǎn)位置

14intFreeNode;〃可用結(jié)點(diǎn)

15intNewNode;//新結(jié)點(diǎn)位置

16inti;

17

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

19(

20FreeNode=NewList.FindFree();

21DataNum=Data[0][i];//設(shè)定數(shù)據(jù)編號

22DataTotal=Data[l][i];〃設(shè)定數(shù)據(jù)總數(shù)

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〃讀入數(shù)據(jù)的編號

35ConsoleReaderconsole=newConsoleReader(System.in);

36

37DataNum=console.readlnt();

38

39if(DataNum==0)

40break;

41

42System.out.printCTleaseinputthedatatotal:,,);

43〃讀入數(shù)據(jù)的總數(shù)

44DataTotal=console.readInt();

45

46NewList.Num[NewNode]=DataNum;

47NewList.Total[NewNode]=DataTotal;

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

49〃讀入欲插入位置

50KeyValue=console.readInt();

51〃調(diào)用插入結(jié)點(diǎn)

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

53NewList.PrintList(Header);

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

55

56

57

58

59

60classNode

61

62intMaxLength=20;//定義鏈表最大長度

63intNum[]=newintfMaxLength];〃鏈表的數(shù)據(jù)項(xiàng)

64intTotal[]=NewInt[MaxLength];〃鏈表的數(shù)據(jù)項(xiàng)

65intNext[]=newint[MaxLength];〃鏈表的下一個(gè)結(jié)點(diǎn)位置

66

67publicNode()//Node構(gòu)造方法

68{

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

70Next[i]=-2;//-2表示未用結(jié)點(diǎn)

71)

72

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

74〃查找可用結(jié)點(diǎn)位置

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;〃現(xiàn)在的結(jié)點(diǎn)位置

92

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

94{

95Num[Header]=DataNum;〃設(shè)定數(shù)據(jù)編號

96Total[Header]=DataTotal;〃設(shè)定數(shù)據(jù)名稱

97Next[Header]=-l;〃設(shè)定下個(gè)結(jié)點(diǎn)的位置,-1表示空結(jié)點(diǎn)

98

99Else

100

101Pointer=Header;〃現(xiàn)在的結(jié)點(diǎn)為首結(jié)點(diǎn)

102Num[FreeNode]=DataNum;〃設(shè)定數(shù)據(jù)編號

103〃設(shè)定數(shù)據(jù)名稱

104Total[FreeNode]=DataTotal;

105Next[FreeNode]=-l;〃設(shè)定下個(gè)結(jié)點(diǎn)的位置,表示空結(jié)點(diǎn)

106//查找鏈表尾端

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

108Pointcr=Next[Pointer];

109

110//將新結(jié)點(diǎn)串連在原鏈表尾端

111Next[Pointer]=FreeNode;

112)

113

114

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

116〃輸入鏈表數(shù)據(jù)

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〃插入結(jié)點(diǎn)至鏈表內(nèi)

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

135PublicintInsert(intHeader,intNewNode,intKeyValue)

136{

137intPointer;//結(jié)點(diǎn)說明

138

139Pointer=Header;//Pointer指針設(shè)為首結(jié)點(diǎn)

140

141While(ture)

142

143if(Pointer==-l)〃插入在首結(jié)點(diǎn)前

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];〃往下一個(gè)結(jié)點(diǎn)

156)

157returnHeader;

158}

159)

3.單鏈表的結(jié)點(diǎn)刪除

(1).刪除鏈表首結(jié)點(diǎn)

刪除的結(jié)點(diǎn)在鏈表的開頭,需要將首結(jié)點(diǎn)指向首結(jié)點(diǎn)的指針(即下?個(gè)結(jié)點(diǎn)),并將原來的結(jié)

點(diǎn)從內(nèi)存中釋放。

Header=NewList.Next[Pointer];

NewList.Next[Pointer]=-2

(2).刪除鏈表中間結(jié)點(diǎn)

刪除前:

NULL

Header_k|一口_?|一廠一廠—F4*?…!—F4*

BackPointerNextfPointer]

刪除后:

],NULL

刪除的結(jié)點(diǎn)在鏈表的中間,如果我們找到Pointer結(jié)點(diǎn),則需要將前一個(gè)結(jié)點(diǎn)的指針指向

Pointer結(jié)點(diǎn)的指針(即下一個(gè)結(jié)點(diǎn)),并將原來的結(jié)點(diǎn)從內(nèi)存中釋放。

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

NewList.Next[Pointer]=-2

(3).刪除鏈表尾端的結(jié)點(diǎn)

刪除的結(jié)點(diǎn)在鏈表的尾端(Pointer結(jié)點(diǎn)),如果我們找到Pointer結(jié)點(diǎn),則需要將前一個(gè)結(jié)點(diǎn)

的指針指向Pointer結(jié)點(diǎn)的指針(NULL),并將原來的結(jié)點(diǎn)從內(nèi)存中釋放。

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

NewList.Next[Pointer]=-2;

(4).在單鏈表中刪除結(jié)點(diǎn)的程序?qū)嵗?/p>

?程序目的

設(shè)計(jì)一個(gè)刪除鏈表內(nèi)結(jié)點(diǎn)的程序

?程序構(gòu)思

持續(xù)往下一個(gè)結(jié)點(diǎn)查找欲刪除結(jié)點(diǎn),直到結(jié)點(diǎn)內(nèi)容找到或結(jié)點(diǎn)指針為NULL(即找不到該

結(jié)點(diǎn))。在刪除時(shí),必須記錄前一個(gè)結(jié)點(diǎn)的位置(Back)。

(1)如果該結(jié)點(diǎn)不存在,輸出消息說結(jié)點(diǎn)不存在。

(2)如果該結(jié)點(diǎn)存在,且是首結(jié)點(diǎn):

Header=NewList.Next[Pointer];

NewList.Next[Pointer]=-2;

(3)如果該結(jié)點(diǎn)存在,但非首結(jié)點(diǎn)(即鏈表的中間結(jié)點(diǎn)或尾端結(jié)點(diǎn)),貝IJ:

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

NewList.Next[Pointer]=-2;

?程序源代碼

01importConSolereader.*;〃引入已定義的數(shù)據(jù)輸入類

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();//產(chǎn)生一個(gè)Node類

10intDataNum;]//數(shù)據(jù)的編號

11intDataTotal;〃數(shù)據(jù)的總數(shù)

12intKeyValue;//欲插入位置

13intHeader=0;〃首結(jié)點(diǎn)位置

14intFreeNode;//可用結(jié)點(diǎn)

15inti;//循環(huán)計(jì)數(shù)變量

16

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

18{

19FreeNode=NewList.FindFree();

20DataNum=Data[0][i];〃設(shè)定數(shù)據(jù)編號

21DataTotal=Data[l][i];〃設(shè)定數(shù)據(jù)總數(shù)

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〃調(diào)用刪除結(jié)點(diǎn)

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

39NewList.PrintList(Header);

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

41}

42

43

44

45

46ClassNode

47(

48intMaxLength=20;//定義鏈表最大長度

49intNum[]=newint[MaxLength];〃鏈表的數(shù)據(jù)項(xiàng)

50intTotal[]=newint[MaxLength];〃鏈表的數(shù)據(jù)項(xiàng)

51intNext[]=newint[MaxLength];〃鏈表的下一個(gè)結(jié)點(diǎn)位置

52

53PublicNode()//Node構(gòu)造方法

54{

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

56Next[i]=-2;//-2表示未用結(jié)點(diǎn)

57

58

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

60〃查找可用結(jié)點(diǎn)位置

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論