PHP 在循环双向链表中搜索元素

 PHP 数据结构

在循环双向链表中搜索元素需要创建一个指向链表头部的临时节点。除此之外，还需要两个变量来跟踪当前节点的搜索和跟踪索引。如果临时节点在开始时不为空，则遍历列表以检查当前节点值是否与搜索值匹配。如果匹配则更新搜索跟踪器变量并停止遍历列表，否则继续遍历列表。如果临时节点在开始时为空，则列表不包含任何项目。

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

public function SearchElement($searchValue) {
  
  //1.创建一个指向 head 的临时节点
  $temp = new Node();
  $temp = $this->head;

  //2。创建两个变量:found - to track
  // 搜索，idx - 跟踪当前索引
  $found = 0;
  $i = 0;

  //3。如果临时节点不为空，请检查
  //带有searchValue的节点值，如果找到的话
  //更新变量并打破循环，否则
  //继续搜索直到临时节点不是头节点
  if($temp != null) {
    while(true) {
      $i++;
      if($temp->data == $searchValue) {
        $found++;
        break;
      }
      $temp = $temp->next;
      if($temp == $this->head) {break;}
    }
    if ($found == 1) {
      echo $searchValue." is found at index = ".$i.".\n";
    } else {
      echo $searchValue." is not found in the list.\n";
    }
  } else {
    
    //4。如果临时节点在开始时为空，
    //列表为空
    echo "The list is empty.\n";
  }
}  

下面是一个完整的程序，它使用上面讨论的概念来搜索给定循环双向链表中的元素。

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

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //在列表末尾添加新元素
  public function push_back($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null; 
    $newNode->prev = 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;
      $newNode->prev = $temp;
      $this->head->prev = $newNode;
    }    
  }

  //搜索列表中的一个元素
  public function SearchElement($searchValue) {
    $temp = new Node();
    $temp = $this->head;
    $found = 0;
    $i = 0;

    if($temp != null) {
      while(true) {
        $i++;
        if($temp->data == $searchValue) {
          $found++;
          break;
        }
        $temp = $temp->next;
        if($temp == $this->head) {break;}
      }
      if ($found == 1) {
        echo $searchValue." is found at index = ".$i.".\n";
      } else {
        echo $searchValue." is not found in the list.\n";
      }
    } else {
      echo "The list is empty.\n";
    }
  }  

  //显示列表内容
  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->PrintList();

//在列表中搜索元素
$MyList->SearchElement(10);
$MyList->SearchElement(15);
$MyList->SearchElement(20);
?>

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

The list contains: 10 20 30 
10 is found at index = 1.
15 is not found in the list.
20 is found at index = 2.