溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
怎么在JavaScript中利用線性表表示鏈?zhǔn)?？很多新手?duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素。所以，每一個(gè)數(shù)據(jù)元素除了存儲(chǔ)自身的信息之外，還需要存儲(chǔ)一個(gè)指向其后繼的存儲(chǔ)位置的信息。這兩部分信息組成了元素的存儲(chǔ)映像，稱為結(jié)點(diǎn)。
結(jié)點(diǎn)包括兩個(gè)域：數(shù)據(jù)域和指針域。
數(shù)據(jù)域是元素中存儲(chǔ)數(shù)據(jù)元素的信息。
指針域是元素中存儲(chǔ)的后繼存儲(chǔ)位置的信息。
n個(gè)結(jié)點(diǎn)鏈接成為鏈表，就是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，又由于此鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，所有又稱為線性鏈表或單鏈表。
舉一個(gè)例子
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8"/>
<script type = "text/javascript">
var Node = function(newData){//創(chuàng)建節(jié)點(diǎn)對(duì)象
this.next = null;
this.data = null;
this.Init = function(){
this.data = newData;
};
this.Init();
}
//定義鏈表類
var List = function(){
this.head = null;
this.size = 0;
this.Init = function(){
this.head = null;
this.size = 0;
}
this.Init();
this.Insert = function(newData){//初始批量插入操作
this.size += 1;
var newNode = new Node(newData);
if(this.head == null){
this.head = newNode;
return;
}
var tempNode = this.head;
while(tempNode.next != null)
tempNode = tempNode.next;//找到鏈表尾部
tempNode.next = newNode;//將新元素插入到鏈表尾部
};
this.GetData = function(pos){//查找操作
if(pos >= this.size || pos < 0)
return null;
else{
tempNode = this.head;
for(i = 0;i < pos;i++)
tempNode = tempNode.next; //找到所處位置
return tempNode.data;
}
};
this.Remove = function(pos){//移除某一位置節(jié)點(diǎn)
if(pos >= this.size || pos < 0)
return null;
this.size -= 1;
tempNode = this.head;
if(pos == 0){
this.head = this.head.next;
return this.head;
}
for(i = 0;i < pos - 1;i++){
tempNode = tempNode.next;
}
tempNode.next = tempNode.next.next;
return tempNode.next;
};
this.InsertBefore=function(data,pos){//從某一位置前插入節(jié)點(diǎn)
if(pos>=this.size||pos<0)
return null;
this.size+=1;
tempNode=this.head;
var newNode = new Node(data);//將數(shù)據(jù)創(chuàng)造節(jié)點(diǎn)
if(pos==0){
newNode.next=tempNode;
return newNode.next;
}
for(i=0;i<pos-1;i++){
tempNode=tempNode.next;//找到插入的位置
}
newNode.next=tempNode.next;//插入操作
tempNode.next=newNode;
return newNode.next;
};
this.Print = function(){//輸出
document.write("鏈表中元素: <br>");
tempNode = this.head;
while(tempNode != null){
document.write(tempNode.data + " ");
tempNode = tempNode.next;
}
document.write("<br>");
};
};
//運(yùn)行測試:
var list = new List();
var array = new Array(1,2,3,4,5,6);
for(i = 0;i < array.length;i++){
list.Insert(array[i]);
}
list.Print();
document.write("查找操作下標(biāo)為4的元素: <br>");
var data= list.GetData(4);
document.write(data+"<br>");
document.write("刪除操作: <br>");
list.Remove(5);
list.Print();
document.write("插入操作: <br>");
list.InsertBefore(8,3);
list.Print();
document.write("鏈表大小: " + list.size);
</script>
</head>
<body>
</body>
</html>
運(yùn)行得到結(jié)果為
this.InsertBefore=function(data,pos){//從某一位置前插入節(jié)點(diǎn)
if(pos>=this.size||pos<0)
return null;
this.size+=1;
tempNode=this.head;
var newNode = new Node(data);//將數(shù)據(jù)創(chuàng)造節(jié)點(diǎn)
if(pos==0){
newNode.next=tempNode;
return newNode.next;
}
for(i=0;i<pos-1;i++){
tempNode=tempNode.next;//找到插入的位置
}
newNode.next=tempNode.next;//插入操作
tempNode.next=newNode;
return newNode.next;
};
this.Remove = function(pos){//移除某一位置節(jié)點(diǎn)
if(pos >= this.size || pos < 0)
return null;
this.size -= 1;
tempNode = this.head;
if(pos == 0){
this.head = this.head.next;
return this.head;
}
for(i = 0;i < pos - 1;i++){
tempNode = tempNode.next;
}
tempNode.next = tempNode.next.next;
return tempNode.next;
};
可以看出，插入和刪除的世界復(fù)雜度都為o(n)。因?yàn)樵诘趇個(gè)結(jié)點(diǎn)前插入或刪除都得找到第i-1個(gè)元素。
再來看看初始化方法Insert，
this.Insert = function(newData){//初始批量插入操作
this.size+= 1;
var newNode = new Node(newData);
if(this.head == null){
this.head = newNode;
return;
}
var tempNode = this.head;
while(tempNode.next != null)
tempNode = tempNode.next;//找到鏈表尾部
tempNode.next= newNode;//將新元素插入到鏈表尾部
};初始的插入Insert方法的時(shí)間復(fù)雜度也是o(n)。
下面介紹一下另外一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，就是循環(huán)鏈表。它的特點(diǎn)就表中的最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。有時(shí)候，在循環(huán)鏈表中設(shè)立尾指針而不設(shè)立頭指針，可以簡化操作。比如兩個(gè)線性表集合為一個(gè)表時(shí)，僅需將一個(gè)表的表尾和另一個(gè)表的表頭相接。這個(gè)操作的時(shí)間復(fù)雜度是o(1)。
如下圖所示
看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝您對(duì)億速云的支持。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼