Penjelasan terperinci senarai terpaut dalam php

Pengendalian senarai terpaut jauh lebih rumit daripada senarai berjujukan. Oleh kerana PHP sememangnya telah menyelesaikan banyak masalah operasi tatasusunan untuk kami, kami boleh mengendalikan tatasusunan dengan sangat mudah, dan kami tidak perlu mentakrifkan banyak operasi logik untuk tatasusunan. Sebagai contoh, dalam C, tatasusunan mempunyai had panjang, tetapi dalam PHP kami tidak akan mempertimbangkan isu ini.

Takrifan struktur terpaut

Pertama sekali, dalam artikel pertama tentang jadual linear, kita bercakap tentang takrif senarai terpaut, di sini, mari kita semak gambar rajah senarai terpaut sebelumnya untuk memahami konsep senarai terpaut dengan lebih jelas.

Kami mewakili Nod nod dalam graf sebagai kelas:

/**
 * 链表结构
 */
class LinkedList
{
    public $data;
    public $next;
}

Kelas senarai terpaut boleh dianggap sebagai nod dalam senarai terpaut , ia mengandungi dua kandungan, data mewakili data, dan seterusnya mewakili penunjuk nod seterusnya. Sama seperti rantai, satu pautan di dalam satu lagi, ini ialah struktur senarai terpaut legenda.

Jana senarai terpaut dan mulakan operasi

/**
 * 生成链表
 */
function createLinkedList()
{
    $list = new LinkedList();
    $list->data = null;
    $list->next = null;
    return $list;
}

/**
 * 初始化链表
 * @param array $data 链表中要保存的数据，这里以数组为参考
 * @return LinkedList 链表数据
 */
function Init(array $data)
{
    // 初始化
    $list = createLinkedList();
    $r = $list;
    foreach ($data as $key => $value) {
        $link = new LinkedList();
        $link->data = $value;
        $link->next = null;
        $r->next = $link;
        $r = $link;
    }
    return $list;
}

$link = Init(range(1, 10));

print_r($link);
// LinkedList Object
// (
//     [data] =>
//     [next] => LinkedList Object
//         (
//             [data] => 1
//             [next] => LinkedList Object
//                 (
//                     [data] => 2
//                     [next] => LinkedList Object
//                         (
//                             [data] => 3
//                             [next] => LinkedList Object
//                                 (
//                                     [data] => 4
//                                     [next] => LinkedList Object
//                                         (
//                                             [data] => 5
//                                             [next] => LinkedList Object
//                                                 (
//                                                     [data] => 6
//                                                     [next] => LinkedList Object
//                                                         (
//                                                             [data] => 7
//                                                             [next] => LinkedList Object
//                                                                 (
//                                                                     [data] => 8
//                                                                     [next] => LinkedList Object
//                                                                         (
//                                                                             [data] => 9
//                                                                             [next] => LinkedList Object
//                                                                                 (
//                                                                                     [data] => 10
//                                                                                     [next] =>
//                                                                                 )

//                                                                         )

//                                                                 )

//                                                         )

//                                                 )

//                                         )

//                                 )

//                         )

//                 )

//         )

// )

Apabila menggunakan senarai terpaut, kami biasanya membuat nod pertama tidak mengandungi sebarang data, sama seperti nod kosong Menuding ke nod pertama dengan data. Kita boleh memanggil nod jenis ini sebagai nod kepala Jika anda perlu menilai sama ada senarai terpaut kosong, anda hanya perlu menilai sama ada nod pertama yang seterusnya kosong. Dalam kod di atas, fungsi createLinkedList() sebenarnya menjana nod kepala sedemikian.

Kemudian, kami membina senarai terpaut ini melalui fungsi permulaan Init(). Proses pembinaannya agak mudah Di sini kita lulus dalam tatasusunan dan membina senarai terpaut mengikut struktur tatasusunan Sudah tentu, dalam aplikasi praktikal, kita boleh menggunakan sebarang data untuk membina senarai terpaut. Proses pembinaan tidak rumit. Hanya tetapkan nod semasa kepada pembolehubah r, kemudian buat nod baharu dan buat r->sebelah sama dengan nod yang baru dibuat. Struktur yang dicetak terus daripada senarai terpaut yang dibina ialah borang dalam ulasan.

Melintasi senarai terpaut

function IteratorLinkedList(LinkedList $link)
{
    while (($link = $link->next) != null) {
        echo $link->data, ',';
    }
    echo PHP_EOL;
}

Adakah traversal senarai terpaut sangat serupa dengan pengendalian kursor sesetengah pangkalan data, atau seperti pengendalian mod lelaran? Betul, sebenarnya, struktur kursor dan iterator ialah satu bentuk senarai terpaut. Kami terus mencari $next sehingga tiada nod seterusnya, sekali gus melengkapkan traversal senarai terpaut. Dapat dilihat bahawa kerumitan masa proses ini ialah O(n).

Sisipan dan pemadaman

/**
 * 链表指定位置插入元素
 * @param LinkedList $list 链表数据
 * @param int $i 位置
 * @param mixed $data 数据
 */
function Insert(LinkedList &$list, int $i, $data)
{
    $j = 0;
    $item = $list;
    // 遍历链表，找指定位置的前一个位置
    while ($j < $i - 1) {
        $item = $item->next;
        $j++;
    }

    // 如果 item 不存在或者 $i > n+1 或者 $i < 0
    if ($item == null || $j > $i - 1) {
        return false;
    }

    // 创建一个新节点
    $s = new LinkedList();
    $s->data = $data;

    // 新创建节点的下一个节点指向原 i-1 节点的下一跳节点，也就是当前的 i 节点
    $s->next = $item->next;
    // 将 i-1 节点的下一跳节点指向 s ，完成将 s 插入指定的 i 位置，并让原来的 i 位置元素变成 i+1 位置
    $item->next = $s;

    return true;
}

/**
 * 删除链表指定位置元素
 * @param LinkedList $list 链表数据
 * @param int $i 位置
 */
function Delete(LinkedList &$list, int $i)
{
    $j = 0;
    $item = $list;
    // 遍历链表，找指定位置的前一个位置
    while ($j < $i - 1) {
        $item = $item->next;
        $j++;
    }
    // 如果 item 不存在或者 $i > n+1 或者 $i < 0
    if ($item == null || $j > $i - 1) {
        return false;
    }

    // 使用一个临时节点保存当前节点信息，$item 是第 i-1 个节点，所以 $item->next 就是我们要找到的当前这个 i 节点
    $temp = $item->next;
    // 让当前节点，也就是目标节点的上一个节点， i-1 的这个节点的下一跳（原来的 i 位置的节点）变成原来 i 位置节点的下一跳 next 节点，让i位置的节点脱离链条
    $item->next = $temp->next;

    return true;
}

// 插入
Insert($link, 5, 55);
// 遍历链表
IteratorLinkedList($link); // 1,2,3,4,55,5,6,7,8,9,10,

// 删除
Delete($link, 7);
// 遍历链表
IteratorLinkedList($link); // 1,2,3,4,55,5,7,8,9,10,

Sisipan dan pemadaman senarai terpaut sebenarnya sangat serupa. Kedua-duanya perlu mencari elemen sebelumnya bagi kedudukan sisipan atau pemadaman, iaitu i-1 elemen kedudukan. Kemudian penyisipan dan pemadaman elemen senarai terpaut dilaksanakan dengan mengendalikan penunjuk seterusnya elemen ini.

Kod dalam dua fungsi penghakiman traversal dan kedudukan sebenarnya sama Perbezaannya ialah apabila mencipta, anda perlu mencipta nod baharu, dan kemudian biarkan nod seterusnya menghala ke i sebelumnya. -1 kedudukan elemen seterusnya, dan kemudian halakan elemen seterusnya pada kedudukan i-1 ke nod yang baru dibuat. Operasi pemadaman adalah untuk menyimpan nod pada kedudukan i untuk dipadamkan ke dalam pembolehubah sementara, dan kemudian halakan elemen seterusnya pada kedudukan i-1 ke seterusnya pada kedudukan i yang dipadam.

Penjelasan di atas perlu dilihat langkah demi langkah bersama dengan kod tersebut, kita juga boleh mempelajarinya bersama-sama dengan gambar di bawah. Operasi sisipan dan pemadaman ialah teras operasi senarai terpaut dan bahagian paling kompleks, yang memerlukan banyak pemahaman dan penguasaan.

Cari berdasarkan lokasi, cari berdasarkan data

/**
 * 根据位置查找元素位置
 * @param LinkedList $list 链表数据
 * @param int $i 位置
 */
function GetElem(LinkedList &$list, int $i)
{
    $item = $list;
    $j = 1; // 从第一个开始查找，0是头结点 
    while ($item && $j <= $i) {
        $item = $item->next;
        $j++;
    }

    if (!$item || $j > $i + 1) {
        return false;
    }
    return $item->data;

}

/**
 * 根据数据查找数据元素所在位置
 * @param LinkedList $list 链表数据
 * @param mixed $data 数据
 */
function LocateElem(LinkedList &$list, $data)
{
    $item = $list;
    $j = 1; // 从第一个开始查找，0是头结点 
    while (($item = $item->next)!=null) {
        if($item->data == $data){
            return $j;
        }
        $j++;
    }

    return false;
}

// 获取指定位置的元素内容
var_dump(GetElem($link, 5)); // int(55)

// 获取指定元素所在的位置
var_dump(LocateElem($link, 55)); // int(5)

Terdapat dua bentuk carian dalam senarai terpaut, satu ialah memberikan lokasi, sebagai contoh, saya mahu Kandungan elemen pada kedudukan kelima adalah untuk mencari nilai elemen berdasarkan kedudukan yang ditentukan, sama seperti subskrip tatasusunan. Walau bagaimanapun, perlu diingatkan bahawa indeks senarai terpaut bermula dari 1, kerana kedudukan 0 adalah nod kepala kami. Sudah tentu, kita juga boleh menukar kod untuk mengabaikan nod pusingan U dan menjadikannya konsisten dengan tatasusunan, tetapi dalam kes ini, ciri senarai terpaut tidak akan jelas, jadi kita masih bermula dengan 1 dalam kod ujian di sini.

Satu lagi jenis carian ialah memberikan kandungan data dan mencari kedudukannya dalam senarai terpaut. Malah, kedua-dua algoritma merentasi keseluruhan senarai terpaut, dan pada dasarnya tiada perbezaan. Memandangkan senarai terpaut tidak mempunyai keupayaan untuk melanggan seperti tatasusunan, kerumitan masa operasi cariannya ialah O(n).

Ringkasan

Bagaimana pula, kesukarannya semakin tinggi. Pengendalian senarai terpaut akan menjadi lebih rumit. Jangan risau, ini hanyalah pembuka selera. Kandungan yang akan anda pelajari kemudian pada asasnya akan berkisar pada dua bentuk senarai berurutan (tatasusunan) dan senarai terpaut. Dan kajian senarai terpaut kami belum berakhir Dalam artikel seterusnya, kami akan melihat dengan lebih mendalam pada bentuk senarai terpaut yang lain: senarai terpaut berganda, senarai terpaut bulat dan senarai terpaut dua kali ganda.

Kod ujian:

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.线性表/source/2.3%20链表的相关逻辑操作.php

Pembelajaran yang disyorkan: Tutorial video php

Atas ialah kandungan terperinci Penjelasan terperinci senarai terpaut dalam php. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!