版權(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度外來單位施工安全責(zé)任承諾書(設(shè)備進(jìn)場版)3篇
- 2025年度橡膠加工設(shè)備購買合同(高性能)2篇
- 共享志愿服務(wù):公益活動(dòng)的新平臺(tái)
- 2025年度模板木方廢舊回收利用采購合同范本3篇
- 人工智能在法律行業(yè)的應(yīng)用
- 2025年度民間融資合同范本:民間融資合同范本(2025)6篇
- 2024年版建筑風(fēng)管保溫工程施工合同
- 2021高考英語一輪課下限時(shí)訓(xùn)練及答案(人教新課標(biāo)必修3Unit-2)
- 數(shù)據(jù)要素協(xié)同對制造業(yè)企業(yè)價(jià)值的影響研究
- 2024年中國輔酶Q10膠囊行業(yè)投資分析、市場運(yùn)行態(tài)勢、未來前景預(yù)測報(bào)告
- FANUC機(jī)器人培訓(xùn)教程(完成版)
- 玉溪大紅山鐵礦二期北采區(qū)采礦施工組織設(shè)計(jì)
- 中醫(yī)診療技術(shù)操作規(guī)程
- 2024年《多媒體技術(shù)與應(yīng)用》 考試題庫及答案
- 2024年外研版九年級英語上冊知識(shí)點(diǎn)總結(jié)
- 2024新教科版四年級上冊科學(xué)知識(shí)點(diǎn)總結(jié)精簡版
- (完整)北京版小學(xué)英語1至6年級詞匯(帶音標(biāo))
- 《朝花夕拾》閱讀推進(jìn)課 教學(xué)設(shè)計(jì)-2023-2024學(xué)年統(tǒng)編版語文七年級下冊
- 項(xiàng)目駐場服務(wù)合同協(xié)議書
- 終止合同告知函 委婉
評論
0/150
提交評論