5-3徹底完轉單向串列演算法
在JavaScript語言中，如果以動態配置產生鏈結串列的節點，必須先行自訂一個類別，接著在該類別中定義一個指標欄位，用意在指向下一個鏈結點，及至少一個資料欄位。例如我們宣告一學生成績串列節點的結構宣告，並且包含下面兩個資料欄位；姓名name、成績score，與一個指標欄位next。可以宣告如下：
class student{
constructor(){
this.name='';
this.score=0;
this.next=null;
}
}
當各位完成節點類別的宣告後，就可以動態建立鏈結串列中的每個節點。假設我們現在要新增一個節點至串列尾端，且ptr指向串列的第一個節點，在程式上必須設計四個步驟：
1.動態配置記憶體空間給新節點使用。
2.將原列尾端的指標欄next指向新元素所在的記憶體位置。
3.將ptr指標指向新節點的記憶體位置，表示這是新的串列尾端。
4.由於新節點目前為串列最後一個元素，所以將它的指標欄next指向null。
例如要將s1的next變數指向s2，而且s2的next變數指向null：
s1.next = s2;
s2.next = null;
由於串列的基本特性就是next變數將會指向下一個節點，這時s1節點與s2節點間的關係就如下圖所示：
5-3-1單向鏈結串列的連結
JS concatlist.js
/[示範]：單向串列的連結功能
var concatlist=(ptr1,ptr2)=>{
ptr=ptr1;
while (ptr.next!=null) ptr=ptr.next;
ptr.next=ptr2;
return ptr1;
}
class employee{
constructor() {
this.num=0;
this.salary=0;
this.name='';
this.next=null;
}
}
findword=0;
data=[];
namedata1=['Allen','Scott','Marry','Jon',
'Mark','Ricky','Lisa','Jasica',
'Hanson','Amy','Bob','Jack'];
namedata2=['May','John','Michal','Andy',
'Tom','Jane','Yoko','Axel',
'Alex','Judy','Kelly','Lucy'];
for (i=0; i<12;i++){
data[i]=[];
data[i][0]=i+1;
data[i][1]=Math.floor(51+Math.random()*50);
}
const head1=new employee(); //建立第一組串列首
if (!head1) {
console.log('Error!! 記憶體配置失敗');
return;
}
head1.num=data[0][0];
head1.name=namedata1[0];
head1.salary=data[0][1];
head1.next=null;
ptr=head1;
for(i=1; i<12; i++){
//建立第一組鏈結串列
newnode=new employee();
newnode.num = data[i][0];
newnode.name=namedata1[i];
newnode.salary=data[i][1];
newnode.next=null;
ptr.next=newnode;
ptr=ptr.next;
}
for(i=0; i<12; i++){
data[i][0]=i+13;
data[i][1]=Math.floor(51+Math.random()*50);
}
const head2=new employee();
if (!head2){
console.log('Error!! 記憶體配置失敗!!');
return;
}
head2.num=data[0][0];
head2.name=namedata2[0];
head2.salary=data[0][1];
head2.next=null;
ptr=head2;
for(i=1; i<12; i++){
//建立第二組鏈結串列
newnode=new employee();
newnode.num=data[i][0];
newnode.name=namedata2[i];
newnode.salary=data[i][1];
newnode.next=null;
ptr.next=newnode;
ptr=ptr.next;
}
i=0;
ptr=concatlist(head1,head2);//將串列相連
console.log('兩個鏈結串列相聯的結果：');
while(ptr!=null){
process.stdout.write('['+ptr.num+' '+ptr.name+' '+ptr.salary+']=> ');
i=i+1;
if(i>3){
console.log();
i=0;
}
ptr=ptr.next;
}
用一維方式來算
PHP concatlist.php
$namedata1=array('Allen','Scott','Marry','Jon',
'Mark','Ricky','Lisa','Jasica',
'Hanson','Amy','Bob','Jack');
$namedata2=array('May','John','Michal','Andy',
'Tom','Jane','Yoko','Axel',
'Alex','Judy','Kelly','Lucy');
$namedata=array();
function add_score($arr){
$count_arr=count($arr);
$new_arr=array();
for ($i=0; $i<$count_arr; $i++){
$score = rand(60,100);
$temp = $arr[$i].",".$score;
array_push($new_arr,$temp);
}
return $new_arr;
}
function join_arr($arr1,$arr2){
$count_arr=count($arr2);
for($i=0; $i<$count_arr; $i++){
array_push($arr1,$arr2[$i]);
}
return $arr1;
}
$new_namedata1=add_score($namedata1);
$new_namedata2=add_score($namedata2);
$namedata=join_arr($new_namedata1,$new_namedata2);
foreach ($namedata as $key => $item) {
echo $item." ";
}後記：
PHP
使用二維陣列，很難去加、刪，只好用一維陣列並加上符號,來加資料。
array_push()函數，前面不能加變數，會出錯。
$my_arr=array_push($my_arr,$add_data);
會出現錯誤的訊息
array_push() expects parameter 1 to be array
PHP concatlist.php
用二維方式來算
$namedata1=array('Allen','Scott','Marry','Jon',
'Mark','Ricky','Lisa','Jasica',
'Hanson','Amy','Bob','Jack');
$namedata2=array('May','John','Michal','Andy',
'Tom','Jane','Yoko','Axel',
'Alex','Judy','Kelly','Lucy');
$namedata=array();
function add_score($arr){
$count_arr=count($arr);
$new_arr=array();
$temp_arr=array();
for ($i=0; $i<$count_arr; $i++){
$score = rand(60,100);
$temp = $arr[$i];
$temp_arr=array($temp,$score);
array_push($new_arr,$temp_arr);
}
return $new_arr;
}
function join_arr($arr1,$arr2){
$count_arr=count($arr2);
for($i=0; $i<$count_arr; $i++){
array_push($arr1,$arr2[$i]);
}
return $arr1;
}
$new_namedata1=add_score($namedata1);
$new_namedata2=add_score($namedata2);
$namedata=join_arr($new_namedata1,$new_namedata2);
foreach ($namedata as $key => $item) {
foreach($item as $value){
echo $value." ";
}
echo "<br>";
}後記 PHP二維參考資料
PHP 先存成陣列，再用array_push去加
for ($i=0; $i<$count_arr; $i++){
$score = rand(60,100);
$temp = $arr[$i];
$temp_arr=array($temp,$score);
array_push($new_arr,$temp_arr);
}
用佇列(Quene)方式來算
PHP concalist_quene.php
5-3-2單向串列插入新節點
在單向鏈結串列中插入新節點，如同一列火車加入新的車廂，有三種情況：加於第1個節點之前、加於最後一個節點之後，以及加於此串列中間任一位置。
演算法如下：
newnode.next=first;
first=newnode;
演算法如下：
ptr.next=newnode;
newnode.next=null;
演算法如下：
newnods.next=x.next;
x.next=newnods;
JS insert_node.js
class employee {
constructor() {
this.num=0;
this.salary=0;
this.name='';
this.next=null;
}
}
var findnode=(head,num)=>{
ptr=head;
while (ptr!=null){
if (ptr.num==num) return ptr;
ptr=ptr.next;
}
return ptr;
}
var insertnode=(head,ptr,num,salary,name)=>{
InsertNode=new employee();
if (!InsertNode) return null;
InsertNode.num=num;
InsertNode.salary=salary;
InsertNode.name=name;
InsertNode.next=null;
if(ptr==null) { //插入第一個節點
InsertNode.next=head;
return InsertNode;
}
else{
if(ptr.next==null) //插入最後一個節點
ptr.next=InsertNode;
else{ //插入中間點
InsertNode.next=ptr.next;
ptr.next=InsertNode;
}
}
return head;
}
position=0;
data=[[1001,32367],[1002,24388],[1003,27556],[1007,31299],
[1012,42660],[1014,25676],[1018,44145],[1043,52182],
[1031,32769],[1037,21100],[1041,32196],[1046,25776]];
namedata=['Allen','Scott','Marry','John','Mark','Ricky',
'Lisa','Jasica','Hanson','Daniel','Axel','Jack'];
process.stdout.write('員工編號 薪水\t員工編號 薪水\t員工編號 薪水\t員工編號 薪水\n');
process.stdout.write('-------------------------------------------------------------\n');
for (i=0; i<3; i++) {
for(j=0; j<4; j++)
process.stdout.write(data[j*3+i][0]+ '\t' +data[j*3+i][1]+'\t');
console.log();
}
console.log('-------------------------------------------------------------');
head=new employee(); //建立串列首
head.next=null;
if(!head) {
console.log('Error!! 記憶體配置失敗');
return;
}
head.num=data[0][0];
head.name=namedata[0];
head.salary=data[0][1];
head.next=null;
ptr=head;
for (i=1; i<12; i++){//建立串列
newnode=new employee();
newnode.next=null;
newnode.num=data[i][0];
newnode.name=namedata[i];
newnode.salary=data[i][1];
newnode.next=null;
ptr.next=newnode;
ptr=ptr.next;
}
while(true) {
process.stdout.write('請輸入要插入其後的員工編號，如輸入的編號不在此串列中，\n');
const prompt = require('prompt-sync')();
const position=parseInt(prompt('新輸入的員工節點將視為此串列的串列首，要結束插入的過程，請輸入-1'));
if (position ==-1)
break;
else{
ptr=findnode(head,position);
new_num = parseInt(prompt('請輸入新插入的員工編號：'));
new_salary=parseInt(prompt('請輸入新插入員工的薪水：'));
new_name=prompt('請輸入新插入的員工姓名：');
head=insertnode(head,ptr,new_num,new_salary,new_name);
}
console.log();
}
ptr=head;
console.log('\t員工編號 姓名\t薪水');
console.log('\t===========================');
while (ptr!=null) {
process.stdout.write('\t['+ptr.num+' ]\t[ '+ptr.name+' ]\t['+ptr.salary+']\n');
ptr=ptr.next;
}
