Apa yang dimaksud dengan “meratakan”?

13

Jika saya memiliki pohon, akan "meratakan" secara intuitif menyiratkan

dapatkan daftar semua item di pohon, melintasi dari kiri ke kanan?

Jika saya memiliki daftar tertaut, akan "meratakan" secara intuitif menyiratkan

dapatkan daftar semua item, mulai dengan yang ini

Sebagai contoh, daftar tertaut akan terdiri dari pengecualian yang menggabungkan pengecualian batinnya. Apakah adil untuk menyebutkan metode pengecualian "flattenInnerExceptions" dengan harapan akan mengembalikan urutan pengecualian, pengecualian terluar terlebih dahulu, dan pengecualian paling dalam - terakhir?

naming GregC
sumber

Jawaban:

25

Jika saya memiliki daftar daftar, "ratakan" akan menjadi operasi yang mengembalikan daftar semua elemen daun secara berurutan, yaitu sesuatu yang berubah:

[[a, b, c], [d, e, f], [g, h i]]

Ke

[a, b, c, d, e, f, g, h, i]

Untuk pohon, flatting menghasilkan daftar semua daun dalam urutan traversal alami (NB: karena hanya daun yang ada di hasilnya, tidak masalah apakah Anda menganggap ini sebagai pre-, in-or post-order traversal.)

Sebagai akibatnya, untuk daftar sederhana operasi "perataan" menurut definisi merupakan transformasi identitas.

Meratakan dapat dilakukan secara bertahap, atau derajat. Contohnya:

[[[a, b], [c, d]], [[e, f], [g, h]]]

dapat diratakan ke:

[[a, b, c, d], [e, f, g, h]]

dan kemudian ke:

 [a, b, c, d, e, f, g, h]
Donal Fellows
sumber
@Donal Fellows: Ini membahas sebagian pertanyaan tentang pohon. Bagaimana dengan daftar tertaut? Apakah intuitif untuk membicarakannya dengan istilah "Ratakan?"
GregC
@GregC, mungkin Anda ingin menambahkan contoh dari apa yang Anda anggap sebagai daftar tertaut.
Mengedit pertanyaan dengan contoh.
GregC
3
@GregC: Daftar tertaut hanyalah implementasi dari jenis abstrak urutan. (Array juga merupakan implementasi dari tipe abstrak pada setidaknya satu level, dan ya ada perbedaan signifikan; tipe abstrak bukan keseluruhan cerita.) Kebanyakan sistem alokasi memori membuat daftar yang ditautkan cukup mahal karena fakta bahwa Anda kembali membayar overhead alokasi memori per sel daftar (overhead yang sering sekitar 8 byte pada sistem 32-bit) jadi saya tidak akan merekomendasikan menggunakannya kecuali Anda punya kebutuhan untuk memasukkan dan menghapus waktu konstan.
Donal Fellows
1
@BarisDemiray Ya. Itu akan menjadi hasil dari perataan tingkat pertama, dan yang lainnya akan terjadi setelah dua putaran ...
Donal Fellows