PHP 计算循环单链表中的节点数

 PHP 数据结构

计算循环单链表中的节点在处理它时非常有用。它需要创建一个指向列表头部的临时节点和一个名为i的变量，初始值为0。如果临时节点不为空，则将i增加1并使用 temp next 移动到下一个节点。重复该过程，直到临时节点到达头部。 i的最终值将是循环单链表中的节点总数。

函数countNodes就是为此目的而创建的。这是一个 4 步过程。

public function countNodes() {
  
  //1.创建一个指向 head 的临时节点
  $temp = new Node();
  $temp = $this->head;
  
  //2。创建一个变量来计算节点数
  $i = 0;

  //3。如果临时节点不为空则增加
  // i减1并移动到下一个节点，重复
  //直到temp变为null的过程
  if ($temp != null) {
    $i++;
    $temp = $temp->next;
  }
  while($temp != $this->head) {
    $i++;
    $temp = $temp->next;
  }  

  //4。返回计数
  return $i;  
}  

下面是一个完整的程序，它使用上面讨论的计算单向循环的节点总数的概念

<?php
//节点结构
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //在列表末尾添加新元素
  public function push_back($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null; 
    if($this->head == null) {
      $this->head = $newNode;
      $newNode->next = $this->head;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next !== $this->head) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
      $newNode->next = $this->head;
    }    
  }

  //计算列表中的节点数
  public function countNodes() {
    $temp = new Node();
    $temp = $this->head;
    $i = 0;
    if ($temp != null) {
      $i++;
      $temp = $temp->next;
    }
    while($temp != $this->head) {
      $i++;
      $temp = $temp->next;
    }  
    return $i;  
  }  

  //显示列表内容
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while(true) {
        echo $temp->data." ";
        $temp = $temp->next;
        if($temp == $this->head)
          break;        
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }    
};

//测试代码
$MyList = new LinkedList();

//在列表中添加四个元素。
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->push_back(40);

//显示列表内容。
$MyList->PrintList();

//链表中的节点数
echo "No. of nodes: ".$MyList->countNodes();
?>

上面的代码将给出以下输出:

The list contains: 10 20 30 40
No. of nodes: 4