Abstrak Tipe Data dan Struktur Data

Cukup sulit bagi saya untuk memahami istilah-istilah ini. Saya mencari di Google dan membaca sedikit di Wikipedia tetapi saya masih tidak yakin. Sejauh ini saya telah menentukan bahwa:

Abstrak Tipe Data adalah definisi tipe baru, menggambarkan sifat dan operasinya.

Struktur Data adalah implementasi dari ADT. Banyak ADT dapat diimplementasikan sebagai Struktur Data yang sama.

Jika saya pikir benar, array sebagai ADT berarti kumpulan elemen dan sebagai Struktur Data, bagaimana itu disimpan dalam memori. Stack adalah ADT dengan operasi push, pop, tetapi dapatkah kita katakan tentang struktur data stack jika saya maksud saya menggunakan stack yang diimplementasikan sebagai array dalam algoritma saya? Dan mengapa heap bukan ADT? Ini dapat diimplementasikan sebagai pohon atau array.

Sederhananya, ADT (Tipe Data Abstrak) lebih merupakan deskripsi logis, sedangkan Struktur Data konkret.

Anggap ADT sebagai gambar data dan operasi untuk memanipulasi dan mengubahnya.

Struktur Data adalah hal yang nyata dan konkret . Itu dapat diimplementasikan dan digunakan dalam suatu algoritma.

ADT adalah antarmuka ( apa fungsinya ) apa struktur data untuk kelas ( bagaimana melakukannya ).

Beberapa contoh:

ADT: List
DS:  ArrayList, LinkedList...

ADT: Map
DS:  HashMap, TreeMap...

Saya kira Anda mengerti maksudnya.

Abstrak Tipe Data: ADT dapat didefinisikan sebagai sekumpulan nilai data dan operasi terkait yang secara spesifik ditentukan independen dari implementasi tertentu. Dengan demikian Tipe Data Abstrak adalah kumpulan informasi yang terorganisir dan serangkaian operasi yang digunakan untuk mengelola informasi tersebut. Himpunan operasi menentukan antarmuka ADT. Selama ADT memenuhi persyaratan antarmuka, tidak terlalu penting bagaimana ADT diimplementasikan. Karena, dalam ADT, nilai data dan operasi didefinisikan dengan presisi matematis, dan bukan sebagai implementasi dalam bahasa komputer, kami dapat mempertimbangkan efek dari operasi, hubungan dengan tipe data abstrak lainnya apakah suatu program mengimplementasikan tipe data, dll.

Perbedaan mendasar antara tipe data abstrak (ADT) dan tipe data konkret adalah bahwa yang terakhir memungkinkan kita untuk melihat representasi konkret, sedangkan yang sebelumnya menyembunyikan representasi dari kita. ADT mungkin ADT murni atau ADT yang dapat diupdate. ADT murni adalah operasi di mana semua operasi adalah fungsi murni. Ini berarti bahwa operasi tidak memiliki efek samping. Secara khusus, mereka tidak mengubah atau memperbarui argumen input yang ada. Mereka hanya menggunakan argumen ini untuk menghasilkan output, yang merupakan nilai segar dari ADT (atau jenis lainnya). Kebanyakan jenis beton murni. Misalnya, tidak ada operasi pada bilangan bulat yang benar-benar memodifikasi bilangan bulat. Sebagai gantinya, semua operasi seperti '+' menghasilkan keluaran baru.

ADT yang dapat diperbarui adalah operasi di mana beberapa operasi benar-benar mengubah nilai ADT. Sebagai contoh, misalkan kita memiliki operasi yang disebut 'pop' yang mengambil tumpukan sebagai argumen dan memodifikasinya. ("Di tempat", "destruktif") dengan menghapus item prioritas tertinggi. Operasi ini akan dianggap tidak murni dan seluruh ADT kemudian akan menjadi tidak murni juga. ADT mungkin adalah ADT yang ditentukan pengguna.

Kita tahu bahwa Tipe Data Abstrak adalah tipe data yang memenuhi dua kondisi berikut:

1. Representasi, atau definisi, dari jenis dan operasi terkandung dalam unit sintaksis tunggal.

2. Representasi objek tipe tersembunyi dari unit program yang menggunakan tipe, jadi hanya operasi langsung yang mungkin dilakukan pada objek tersebut yang disediakan dalam definisi tipe.

Tipe Data Abstrak yang ditentukan pengguna harus menyediakan:

1. Definisi tipe yang memungkinkan unit program untuk mendeklarasikan variabel dari tipe, tetapi menyembunyikan representasi dari variabel-variabel ini.

2. Seperangkat operasi untuk memanipulasi objek jenis.

Contoh tipe data abstrak yang ditentukan pengguna adalah struktur. 'C' menyediakan empat tipe dasar: int, char, float, dan double. Namun, 'C' juga memberikan programmer dengan kemampuan untuk menentukan jenisnya sendiri. Struktur adalah salah satu contohnya. Struktur adalah agregat dari bagian yang berbeda, di mana setiap bagian dari jenis yang ada.

struct abc

{int x;

float y;

};

Definisi struktur di atas tidak membuat variabel apa pun, melainkan membuat tipe baru. Variabel jenis ini dapat dibuat dengan cara yang mirip dengan variabel tipe bawaan.

struct abc a;

Kata kunci typedef memungkinkan kita membuat nama tipe baru untuk tipe baru kita.

Sebagai contoh:

typedef struct abc AB;

di mana AB adalah nama tipe baru yang sekarang dapat digunakan untuk membuat tipe baru.

AB b;

Struktur Data: Berikut ini adalah fitur karakteristik dari struktur data:

1. Ini berisi komponen data komponen, yang mungkin berupa atom atau struktur data lain (masih berupa domain).

2. Serangkaian operasi pada satu atau lebih item komponen.

3. Menentukan aturan tentang bagaimana komponen terkait satu sama lain dan dengan struktur secara keseluruhan (pernyataan).

Struktur data:

Struktur data mungkin statis atau dinamis. Struktur data statis memiliki ukuran tetap. Arti ini berbeda dari arti pengubah statis. Array adalah statis; begitu kita menentukan jumlah elemen yang bisa dipegangnya, jumlahnya tidak berubah. Struktur data yang dinamis tumbuh dan menyusut pada waktu eksekusi seperti yang disyaratkan oleh kontennya. Struktur data dinamis diimplementasikan menggunakan tautan.

Struktur data selanjutnya dapat dikategorikan ke dalam struktur data linier dan struktur data non-linear. Dalam struktur data linier, setiap komponen memiliki pendahulu dan penerus yang unik, kecuali elemen pertama dan terakhir, sedangkan dalam kasus struktur data non-linear, tidak ada batasan seperti itu karena elemen dapat diatur dengan cara yang diinginkan dibatasi oleh cara yang kita gunakan untuk mewakili tipe seperti itu.

Pertama-tama, Terminologi dalam Struktur data bisa sangat membingungkan.

ADT seperti teori atau model atau pedoman dll. Yang memberi tahu bagaimana struktur data harus berperilaku, operasi apa yang harus didukungnya, dll. Tiga tipe data abstrak mendasar adalah kontainer, kamus, dan antrian prioritas. Sebagai contoh kamus, ini memberitahu kita bahwa setiap struktur data yang mengimplementasikan kamus ini ADT harus mendukung pasangan nilai kunci, mencari berdasarkan kunci, memasukkan item, menemukan penerus dan pendahulu dari kunci yang diberikan dll.

Sekarang segala sesuatu yang mengimplementasikan ADT di atas adalah struktur Data (DS) , struktur data adalah hal-hal nyata yang Anda implementasikan dalam masalah Anda dan temukan di dalam perpustakaan. Dalam hal kamus, Anda dapat memilih untuk mengimplementasikannya melalui daftar Array atau Linked.

Saya pikir kebingungan nyata muncul ketika seseorang menamai DS mereka sebagai ADT, misalnya beberapa orang akan menyebut DS yang disebutkan sebelumnya sebagai 'Kamus' daripada DictImplementation yang sangat legal, itu hanya menyebabkan beberapa kebingungan.

Ref: Skiena: Manual perancangan algoritma