溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
怎么在JavaScript中利用線性表表示鏈式？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
線性表的鏈式存儲結構用一組任意的存儲單元存儲線性表的數據元素。所以，每一個數據元素除了存儲自身的信息之外，還需要存儲一個指向其后繼的存儲位置的信息。這兩部分信息組成了元素的存儲映像，稱為結點。
結點包括兩個域：數據域和指針域。
數據域是元素中存儲數據元素的信息。
指針域是元素中存儲的后繼存儲位置的信息。
n個結點鏈接成為鏈表，就是線性表的鏈式存儲結構，又由于此鏈表的每個結點中只包含一個指針域，所有又稱為線性鏈表或單鏈表。
舉一個例子
上圖表示的線性表為
ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG
這樣應該就好理解多了吧。
下面我們通過js代碼來實現鏈表的插入和刪除還有查找操作
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8"/>
<script type = "text/javascript">
var Node = function(newData){//創建節點對象
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){//移除某一位置節點
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){//從某一位置前插入節點
if(pos>=this.size||pos<0)
return null;
this.size+=1;
tempNode=this.head;
var newNode = new Node(data);//將數據創造節點
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>");
};
};
//運行測試:
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("查找操作下標為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>運行得到結果為
先分析一下插入和刪除的代碼。
this.InsertBefore=function(data,pos){//從某一位置前插入節點
if(pos>=this.size||pos<0)
return null;
this.size+=1;
tempNode=this.head;
var newNode = new Node(data);//將數據創造節點
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){//移除某一位置節點
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;
};可以看出，插入和刪除的世界復雜度都為o(n)。因為在第i個結點前插入或刪除都得找到第i-1個元素。
再來看看初始化方法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方法的時間復雜度也是o(n)。
下面介紹一下另外一種形式的鏈式存儲結構，就是循環鏈表。它的特點就表中的最后一個結點的指針域指向頭結點，整個鏈表形成一個環。有時候，在循環鏈表中設立尾指針而不設立頭指針，可以簡化操作。比如兩個線性表集合為一個表時，僅需將一個表的表尾和另一個表的表頭相接。這個操作的時間復雜度是o(1)。
如下圖所示
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
