Khi chuyển từ các ngôn ngữ lập trình được học ở trường như C/C++, Java, Pascal, … sang PHP một điều khiến ta rất bỡ ngỡ đó là sự biến mất của các cấu trúc dữ liệu cơ bản như stack, queue, linked list, hash, map, tree, graph, heap, … Thứ duy nhất còn tồn tại là mảng (array), không lẽ PHP không hỗ trợ các cấu trúc dữ liệu kia. Không thể thế, PHP là một ngôn ngữ lập trình bậc cao nó tất nhiên sẽ phải hỗ trợ các cấu trúc dữ liệu trên bởi cấu trúc dữ liệu được coi là nền móng xây dựng mọi chương trình. Hóa ra PHP xây dựng cấu trúc dữ liệu mảng rất linh hoạt có khả năng tối ưu để sử dụng thay thế các cấu trúc dữ liệu cơ bản khác.

Mảng trong PHP thực chất là gì

Theo wikipedia: https://vi.wikipedia.org/wiki/Mảng_(tin_học)

Mảng là một tập hợp các phần tử cố định có cùng một kiểu, được lưu trữ liên tiếp nhau trong các ô nhớ. Kiểu phần tử có thể là có các kiểu bất kỳ: ký tự, số, chuỗi ký tự…; cũng có khi ta sử dụng kiểu mảng để làm kiểu phần tử cho một mảng (trong trường hợp này ta gọi là mảng của mảng hay mảng nhiều chiều).

Đối chiếu với định nghĩa kia có thể thấy mảng trong PHP thực chất không phải là mảng. Dễ dàng lấy 1 ví dụ như sau:

    $array = array(
        "foo" => "bar",
        "bar" => "foo",
        100   => -100,
        -100  => 100,
    );
    var_dump($array);

The above example will output:

    array(4) {
  ["foo"]=>
  string(3) "bar"
  ["bar"]=>
  string(3) "foo"
  [100]=>
  int(-100)
  [-100]=>
  int(100)
}

Có thể thấy mảng trong PHP ở đây không phải một tập hợp các phần tử cố định có cùng một kiểu.

Khi sử dụng mảng trong PHP ta thấy nó rất khác với cách dùng mảng thông thường ở những ngôn ngữ lập trình như C/C++, Java, Pascal. Nó linh hoạt hơn rất nhiều. Do đó mảng trong PHP thực chất là 1 ordered map hay ordered dictionary. Khi lập trình .Net dictionary được dùng tương tự như map trong C còn trong PHP nó được gọi là Associative Array về bản chất 3 tên gọi này đều chỉ chung một cấu trúc dữ liệu ánh xạ (mapping) key tới value (Có vẻ dùng map trong C là chuẩn nhất).

Theo docs của PHP: http://php.net/manual/en/language.types.array.php

Thì mảng trong PHP có thể được tối ưu cho nhiều mục đích sử dụng khác nhau nó có thể được sử dụng như 1 array, list (vector), hash table (an implementation of a map), dictionary, collection, stack, queue, và hơn nữa.

Xây dựng cấu trúc dữ liệu trong PHP

Thực tế, từ PHP 5 Standard PHP Library (SPL) đã được bổ sung vào PHP trong đó có cả cấu trúc dữ liệu như

  • SplDoublyLinkedList
  • SplStack
  • SplQueue
  • SplHeap
  • SplMaxHeap
  • SplMinHeap
  • SplPriorityQueue
  • SplFixedArray
  • SplObjectStorage

http://php.net/manual/en/spl.datastructures.php

Nhưng đến thời điểm hiện tại vẫn không nhiều người chú ý tới nó và số lượng người sử dụng nó còn ít hơn. Lý do có thể là bởi PHP được sử dụng chủ yếu như một ngôn ngữ lập trình web vậy nên chương trình thường xử lí các dữ liệu nhỏ và đơn giản trong khi đó mảng trong PHP vừa linh hoạt được hỗ trợ rất tốt các function của mảng có thể nói là vượt trội hơn cả. Do đó mọi người thường có xu hướng xử dụng mảng làm việc để tận dụng tiện ích của mảng.

Tuy nhiên trong nhiều trường hợp cần phải xây dựng cấu trúc dữ liệu để làm việc ta có thể xây dựng chúng dựa trên mảng và các hàm của mảng như sau

Stack and Queue in PHP

//implement stack
    protected $stack;
    protected $limit;
    
    public function __construct($limit = 69) {
        $this->stack = [];
        $this->limit = $limit;
    }

    public function push($item) {
        if (count($this->stack) < $this->limit) {
            array_unshift($this->stack, $item);
        } else {
            echo "Full";
        }
    }

    public function pop() {
        if ($this->isEmpty()) {
            echo "Empty";
	  } else {
            return array_shift($this->stack);
        }
    }

    public function top() {
        return current($this->stack);
    }

    public function isEmpty() {
        return empty($this->stack);
  }

Tree in PHP

Nhờ tính linh hoạt của mảng trong PHP mà mỗi giá trị của mảng ta có thể coi nó như 1 cây con khác. Chẳng hạn khi cần xây dựng cấu trúc cây thư mục và lưu trữ nó vào database

Ta có thể lưu trữ nó vào database như bảng sau:

directories

id name parent_id
1 system NULL
2 config 1
3 lib 1
4 Access 3
5 Plugin 3
6 templates 1
7 tests 1

Ta có thể sử dụng mảng $directoryTree để xây dựng cây thư mục như sau:

    $directoryTree = [
        [
            'id' => 1,
            'name' => 'system',
            'parent_id' => NULL,
            'childrens' => [
                [
                     'id' => 2,
                    'name' => 'config',
                    'parent_id' => 1,
                    'childrens' => [],
                 [
                     'id' => 3,
                    'name' => 'lib',
                    'parent_id' => 1,
                    'childrens' => [
                        [
                             'id' => 4,
                            'name' => 'lib',
                            'parent_id' => 3,
                            'childrens' => []
                        ],
                        [
                             'id' => 5,
                            'name' => 'lib',
                            'parent_id' => 3,
                            'childrens' => []
                        ],
                ],
                 [
                     'id' => 6,
                    'name' => 'templates',
                    'parent_id' => 1,
                    'childrens' => [],
                 [
                     'id' => 7,
                    'name' => 'system',
                    'parent_id' => 1,
                    'childrens' => [],
                ]
           ]
        ],
    ]

Hàm dựng cây thư mục

    public function buildDirectoryTree($directories, $parentId = 0) {
    $branch = [];

    foreach ($directories as $directory) {
        if ($directory['parent_id'] == $parentId) {
            $children = buildTree($directories, $directory['id']);
            if ($children) {
                $directory['children'] = $children;
            }
            $branch[] = $directory;
        }
    }

    return $branch;
}

Heap (Binary Heap)

    protected $heap = [];

    public function isEmpty() {
        return empty($this->heap);
    }

    public function extract() {
        $root = array_shift($this->heap);

        if (!$this->isEmpty()) {
            $last = array_pop($this->heap);
            array_unshift($this->heap, $last);
            $this->heapify(0);
        }

        return $root;
    }

    public function heapify($root) {
            $heap = $this->heap;
            if (
              (isset($heap[(2 * $root) + 1]) &&
                $this->compare($heap[$root], $heap[(2 * $root) + 1]) < 0)
              || (isset($heap[(2 * $root) + 2]) &&
                $this->compare($heap[$root], $heap[(2 * $root) + 2]) < 0)
            ) {
                if (isset($h[(2 * $root) + 1]) && isset($h[(2 * $root) + 2])) {
                  $j = ($this->compare($h[(2 * $root) + 1], $h[(2 * $root) + 2]) >= 0)
                      ? (2 * $root) + 1: (2 * $root) + 2;
                }
                else if (isset($h[(2 * $root) + 2])) {
                  $j = (2 * $root) + 1;
                }
                else {
                  $j = (2 * $root) + 2;
                }

                  list($this->heap[$root], $this->heap[$j]) = [
                      $this->heap[$j],
                      $this->heap[$root],
                  ];
                  
                $this->heapify($j);
            }
        }
    }
    
    public function compare($item1, $item2) {
        if ($item1 === $item2) {
            return 0;
        }
        return ($item1 > $item2 ? 1 : -1);
    }

LEAVE A REPLY

Please enter your comment!
Please enter your name here