圖說演算法-JavaScript – 頁面 9

5-3-3單向鏈結串列刪除節點

在單向鏈結型態的資料結構中，如果要在串列中刪除一個節點，如同一列火車拿掉原有的車廂，依據所刪除節點的位置有三種不同的情形：

演算法如下：

top=head;
head=head.next;

演算法如下：

ptr.next=tail;
ptr.next=null;

演算法如下：

Y=ptr.next;
ptr.next=Y.next;

class employee{
constructor() {
this.num=0;
this.salary=0;
this.name=”;
this.next=null;
}
}

JS del_node.js

class employee{
	constructor(){
		this.num=0;
		this.salary=0;
		this.name='';
		this.next=null;
	}
}

var del_ptr=(head,ptr)=>{   //刪除節點副程式
	top=head;
	if (ptr.num==head.num) {  //[情形1]：刪除點在串列首
		head=head.next;
		process.stdout.write('已刪除第' +ptr.num+' 號員工 姓名：'+ptr.
			name+' 薪資：'+ptr.salary);
	}
	else {
		while (top.next!=ptr)  //找到刪除點的前一個位置
			top=top.next;
		if(ptr.next==null) {   //刪除在串列尾的節點
			top.next=null;
			process.stdout.write('已刪除第'+ptr.num+' 號員工 姓名：'+ptr.
				name+' 薪資：'+ptr.salary+'\n');
		}
		else{
			top.next=ptr.next;
			process.stdout.write('已刪除第 '+ptr.num+' 號員工 姓名：'+ptr.
				name+' 薪資：' +ptr.salary+'\n');
		}		
	}
	return head;
}

findword=0;
namedata=['Allen','Scott','Mary','John','Mark','Ricky',
		  'Lisa','Jasica','Hanson','Daniel','Axel','Jack'];
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]];
process.stdout.write('員工編號 薪水 員工編號 薪水 員工編號 薪水 員工編號 薪水\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();
}

head=new employee(); //建立串列首
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;
}
const prompt = require('prompt-sync')();
while(true)  {
	const findword = parseInt(prompt('請輸入要刪除的員工編號，要結束刪除過程，請輸入-1：'));
	if (findword==-1)  //迴圈中斷條件
		break;
	else {
		ptr=head;
		find=0;
		while (ptr!=null) {
			if (ptr.num==findword){
				ptr=del_ptr(head,ptr);
				find=find+1;
				head=ptr;
			}
			ptr=ptr.next;
		}
		if (find==0)
			process.stdout.write('//////////沒有找到///////////\n');
	}
}
ptr=head;
process.stdout.write('\t座號\t  姓名\t成績\n');  //列印剩餘串列資料
process.stdout.write('\t======================\n');  
while (ptr!=null)  {
	process.stdout.write('\t['+ptr.num+' ]\t[ '+ptr.name+' ]\t[ '
		+ptr.salary+']\n');
	ptr=ptr.next;
}

5-3-4單向鏈結串列的反轉

看完了節點的刪除及插入後，各位可以發現在這種具有方向性的鏈結串列結構中增刪節點是相當容易的一件事。而要從頭到尾印整個串列似乎也不難，不過如果要反轉過來列印就真的需要某些技巧了。我們知道在鏈結串列中的節點特性是知道下一個節點的位置，可是卻無從得知它的上一個節點位置，不過如果要將串列反轉，則必須使用三個指標變數。請看下圖說明：

演算法如下：

class employee{
    constructor() {
     this.num=0;
     this.salary=0;
     this.name='';
     this.next=null;
    }
}
var invert=(x)=> { //x為串列的開始指標
     p=x;    //將p指向串列的開頭
     q=null; //q是p的前一個節點
     while (p!=null) {
        r=q;       //將r接到q之後
        q=p;       //將q接到p之後
        p=p.next   //p移到下一個節點
        q.next=r;  //q連結到之前的節點
     }
     return q;
}

JS rev_node.js

class employee {
	constructor() {
		this.num=0;
		this.salary=0;
		this.name='';
		this.next=null;
	}
}

findword=0;
namedata=['Allen','Scott','Marry','John','Mark','Ricky',
			'Lisa','Jasica','Hanson','Daniel','Axel','Jack'];
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]];

head = new employee();//建立串列首
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;
}

ptr=head;
i=0;
process.stdout.write('原始員工串列節點資料：\n');
while (ptr !=null) { //列印串列資料
	process.stdout.write('['+ptr.num+'\t'+ptr.name+'\t'
							+ptr.salary+'] -> ');
	i=i+1;
	if (i>=3) { //三個元素為一列
		console.log();
		i=0;
	}
	ptr=ptr.next;
}

ptr=head;
before=null;
process.stdout.write('\n反轉後串列節點資料：\n');
while (ptr!=null) { //串列反轉，利用三指標
	last=before;
	before=ptr;
	ptr=ptr.next;
	before.next=last;
}
ptr=before;
while (ptr!=null) {
	process.stdout.write('['+ptr.num+'\t'+ptr.name+'\t'
							+ptr.salary+'] ->');
	i=i+1;
	if (i>=3) { //三個元素為一列
		console.log();
		i=0;
	}
	ptr=ptr.next;
}

PHP 陣列函數

array_pop() 刪除陣列最後一個元素。
array_push() 將一個或多個元素加入末端。
array_reverse() 以相反的順序返回陣列。
array_shift() 刪除首個元素。
array_slice() 刪除指定位置的元素，返回陣列。

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;
}

分類：圖說演算法-JavaScript

圖說演算法使用JavaScript(十)

5-3-3單向鏈結串列刪除節點

5-3-4單向鏈結串列的反轉

圖說演算法使用JavaScript(九)

5-3徹底完轉單向串列演算法

5-3-1單向鏈結串列的連結

5-3-2單向串列插入新節點

七月 2025
一	二	三	四	五	六	日
« 六月
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31