Pengantar Struktur Data dan Algoritma

Pengantar Struktur Data dan Algoritma

Tinjauan

Software engineering is the study of ways in which to create large and complex computer applications and that generally involve many programmers and designers. Software engineering adalah studi tentang cara-cara untuk menciptakan komputer yang besar dan kompleks aplikasi dan yang umumnya melibatkan banyak programer dan desainer. At the heart of software engineering is with the overall design of the applications and on the creation of a design that is based on the needs and requirements of end users. Di jantung rekayasa perangkat lunak adalah dengan rancangan keseluruhan aplikasi dan pada penciptaan desain yang didasarkan pada kebutuhan dan persyaratan pengguna akhir. While software engineering involves the full life cycle of a software project, is includes many different components - specification, requirements gathering, design, verification, coding, testing, quality assurance, user acceptance testing, production, and ongoing maintenance. Sementara rekayasa perangkat lunak melibatkan seluruh siklus hidup proyek perangkat lunak, yang mencakup banyak komponen yang berbeda - spesifikasi, pengumpulan persyaratan, desain, verifikasi, coding, pengujian, jaminan mutu, pengujian penerimaan pengguna, produksi, dan pemeliharaan berkelanjutan.

Having an in-depth understanding on every component of software engineering is not mandatory, however, it is important to understand that the subject of data structures and algorithms is concerned with the coding phase. Memiliki pemahaman mendalam pada setiap komponen rekayasa perangkat lunak bukan suatu keharusan, bagaimanapun, adalah penting untuk memahami bahwa masalah struktur data dan algoritma berkaitan dengan pengkodean fase. The use of data structures and algorithms is the nuts-and-blots used by programmers to store and manipulate data. Penggunaan struktur data dan algoritma adalah kacang-dan-bercak yang digunakan oleh para programmer untuk menyimpan dan memanipulasi data.

This article, along with the other examples in this section focuses on the essentials of data structures and algorithms. Artikel ini, bersama dengan contoh-contoh lain dalam bagian ini berfokus pada hal-hal penting dari struktur data dan algoritma. Attempts will be made to understand how they work, which structure or algorithm is best in a particular situation in an easy to understand environment. Upaya-upaya akan dilakukan untuk memahami bagaimana mereka bekerja, yang struktur atau algoritma yang terbaik dalam situasi tertentu yang mudah untuk memahami lingkungan.

Data Structures & Algorithms - Defined Struktur Data & Algoritma - Ditetapkan

A data structure is an arrangement of data in a computer's memory or even disk storage. An example of several common data structures are arrays, linked lists, queues, stacks, binary trees, and hash tables. Algorithms , on the other hand, are used to manipulate the data contained in these data structures as in searching and sorting. Sebuah struktur data adalah pengaturan data dalam memori komputer atau bahkan disk penyimpanan. Sebuah contoh dari beberapa struktur data umum adalah array, terkait daftar, antrian, susunan, pohon biner, dan tabel hash. Algorithms, di sisi lain, digunakan untuk memanipulasi data yang terdapat dalam struktur data ini seperti pada pencarian dan penyortiran.

Many algorithms apply directly to a specific data structures. Banyak algoritma mendaftar secara langsung ke struktur data tertentu. When working with certain data structures you need to know how to insert new data, search for a specified item, and deleting a specific item. Ketika bekerja dengan struktur data tertentu Anda perlu tahu bagaimana untuk menyisipkan data baru, mencari item tertentu, dan menghapus item tertentu.

Commonly used algorithms include are useful for: Umum digunakan algoritma termasuk berguna untuk:

* Searching for a particular data item (or record). Mencari item data tertentu (atau catatan).

* Sorting the data. Sorting data. There are many ways to sort data. Simple sorting, Advanced sorting Ada banyak cara untuk menyortir data. Wikipedia menyortir, Advanced sorting

* Iterating through all the items in a data structure. (Visiting each item in turn so as to display it or perform some other action on these items) Iterasi melalui semua item dalam struktur data. (Mengunjungi setiap item pada gilirannya sehingga untuk menampilkan atau melakukan beberapa tindakan lain pada item ini)

Characteristics of Data Structures Karakteristik Struktur Data

Data Structure Struktur data Advantages Keuntungan Disadvantages Kekurangan
Array Array Quick inserts Cepat menyisipkan
Fast access if index known Akses cepat jika indeks dikenal Slow search Lambat pencarian
Slow deletes Lambat menghapus
Fixed size Ukuran tetap
Ordered Array Disusun Array Faster search than unsorted array Cepat cari dari unsorted array Slow inserts Lambat menyisipkan
Slow deletes Lambat menghapus
Fixed size Ukuran tetap
Stack Stack Last-in, first-out acces Last-in, pertama-keluar acces Slow access to other items Lambat akses ke item lain
Queue Antrian First-in, first-out access Pertama-in, pertama-keluar akses Slow access to other items Lambat akses ke item lain
Linked List Linked List Quick inserts Cepat menyisipkan
Quick deletes Quick menghapus Slow search Lambat pencarian
Binary Tree Pohon biner Quick search Pencarian cepat
Quick inserts Cepat menyisipkan
Quick deletes Quick menghapus
(If the tree remains balanced) (Jika pohon tetap seimbang) Deletion algorithm is complex Penghapusan algoritma rumit
Red-Black Tree Red-Black Tree Quick search Pencarian cepat
Quick inserts Cepat menyisipkan
Quick deletes Quick menghapus
(Tree always remains balanced) (Pohon selalu tetap seimbang) Complex to implement Kompleks untuk melaksanakan
2-3-4 Tree 2-3-4 Tree Quick search Pencarian cepat
Quick inserts Cepat menyisipkan
Quick deletes Quick menghapus
(Tree always remains balanced) (Pohon selalu tetap seimbang)
(Similar trees good for disk storage) (Pohon serupa baik untuk penyimpanan disk) Complex to implement Kompleks untuk melaksanakan
Hash Table Hash Tabel Very fast access if key is known Sangat cepat kunci akses jika diketahui
Quick inserts Cepat menyisipkan Slow deletes Lambat menghapus
Access slow if key is not known Akses lambat jika tombol tidak diketahui
Inefficient memory usage Tidak efisien penggunaan memori
Heap Tumpukan Quick inserts Cepat menyisipkan
Quick deletes Quick menghapus
Access to largest item Akses ke konten terbesar Slow access to other items Lambat akses ke item lain
Graph Grafik Best models real-world situations Model terbaik situasi dunia nyata Some algorithms are slow and very complex Beberapa algoritma yang lambat dan sangat kompleks
NOTE : The data structures shown above (with the exception of the array) can be thought of as Abstract Data Types (ADTs). CATATAN: struktur data yang ditampilkan di atas (dengan pengecualian dari array) dapat dianggap sebagai Tipe Data Abstrak (ADTs).

Abstract Data Types Tipe Data Abstrak

An Abstract Data Type (ADT) is more a way of looking at a data structure: focusing on what it does and ignoring how it does its job. An Abstract Data Type (ADT) lebih merupakan cara melihat struktur data: berfokus pada apa yang dilakukan dan mengabaikan bagaimana melakukan pekerjaannya. A stack or a queue is an example of an ADT. Sebuah stack atau antrian adalah contoh dari ADT. It is important to understand that both stacks and queues can be implemented using an array. Penting untuk memahami bahwa kedua tumpukan dan antrian dapat dilaksanakan dengan menggunakan sebuah array. It is also possible to implement stacks and queues using a linked list. Hal ini juga memungkinkan untuk menerapkan tumpukan dan antrian menggunakan linked list. This demonstrates the "abstract" nature of stacks and queues: how they can be considered separately from their implementation. Hal ini menunjukkan "abstrak" sifat dari tumpukan dan antrian: bagaimana mereka dapat dianggap terpisah dari pelaksanaannya.

To best describe the term Abstract Data Type, it is best to break the term down into "data type" and then "abstract". Untuk menggambarkan istilah terbaik Abstrak Data Type, yang terbaik adalah memecah istilah ke dalam "tipe data" dan kemudian "abstrak".

data type jenis data

When we consider a primitive type we are actually referring to two things: a data item with certain characteristics and the permissible operations on that data. Ketika kita mempertimbangkan tipe primitif kita sebenarnya mengacu pada dua hal: sebuah item data dan karakteristik tertentu yang diperbolehkan operasi pada data. An int in Java, for example, can contain any whole-number value from -2,147,483,648 to +2,147,483,647. Sebuah int di Jawa, misalnya, dapat berisi nomor seluruh-nilai dari -2147483648 ke 2147483647. It can also be used with the operators +, -, *, and /. Juga dapat digunakan dengan operator +, -, *, dan /. The data type's permissible operations are an inseparable part of its identity; understanding the type means understanding what operations can be performed on it. Tipe data's diperbolehkan operasi adalah bagian yang tidak terpisahkan dari identitas; memahami jenis operasi berarti memahami apa yang dapat dilakukan di atasnya.

In Java, any class represents a data type, in the sense that a class is made up of data (fields) and permissible operations on that data (methods). Di Jawa, setiap kelas menunjukkan jenis data, dalam arti bahwa sebuah kelas terdiri dari data (field) dan diperbolehkan operasi pada data (metode). By extension, when a data storage structure like a stack or queue is represented by a class, it too can be referred to as a data type. A stack is different in many ways from an int , but they are both defined as a certain arrangement of data and a set of operations on that data. Dengan ekstensi, ketika sebuah struktur penyimpanan data seperti setumpuk atau antrian yang diwakili oleh kelas, itu juga bisa disebut sebagai tipe data. Seorang tumpukan berbeda dalam banyak hal dari sebuah int tetapi mereka berdua didefinisikan sebagai pengaturan tertentu data dan sekumpulan operasi pada data.

abstract abstrak

Now lets look at the "abstract" portion of the phrase. Sekarang mari kita melihat pada "abstrak" bagian kalimat. The word abstract in our context stands for "considered apart from the detailed specifications or implementation" . Kata abstrak dalam konteks kita adalah singkatan dari "dianggap terpisah dari spesifikasi rinci atau pelaksanaan".

In Java, an Abstract Data Type is a class considered without regard to its implementation. It can be thought of as a "description" of the data in the class and a list of operations that can be carried out on that data and instructions on how to use these operations. Di Jawa, seorang Abstract Data Type adalah sebuah kelas dianggap tanpa memperhatikan pelaksanaannya. Ini dapat dianggap sebagai "deskripsi" data di dalam kelas dan daftar operasi yang dapat dilakukan pada data dan instruksi tentang cara untuk menggunakan operasi ini. What is excluded though, is the details of how the methods carry out their tasks. Apa yang dikecualikan meskipun, adalah rincian bagaimana metode melaksanakan tugas-tugas mereka. An end user (or class user), you should be told what methods to call, how to call them, and the results that should be expected, but not HOW they work. Seorang pengguna akhir (atau kelas pengguna), Anda harus diberitahu apa metode untuk memanggil, bagaimana memanggil mereka, dan hasil yang harus diharapkan, tetapi tidak BAGAIMANA mereka bekerja.

We can further extend the meaning of the ADT when applying it to data structures such as a stack and queue. Kita dapat terus memperluas arti dari ADT ketika menerapkannya pada struktur data seperti stack dan queue. In Java, as with any class, it means the data and the operations that can be performed on it. Di Jawa, seperti halnya dengan setiap kelas, itu berarti data dan operasi yang dapat dilakukan terhadapnya. In this context, although, even the fundamentals of how the data is stored should be invisible to the user. Dalam konteks ini, walaupun, bahkan dasar-dasar bagaimana data seharusnya disimpan tidak terlihat oleh pengguna. Users not only should not know how the methods work, they should also not know what structures are being used to store the data. Pengguna tidak hanya tidak tahu bagaimana metode kerja, mereka seharusnya juga tidak tahu apa struktur yang digunakan untuk menyimpan data.

Consider for example the stack class. Perhatikan misalnya kelas stack. The end user knows that push() and pop() (amoung other similar methods) exist and how they work. Pengguna akhir tahu bahwa push () dan pop () (antara lain metode yang serupa) ada dan bagaimana mereka bekerja. The user doesn't and shouldn't have to know how push() and pop() work, or whether data is stored in an array, a linked list, or some other data structure like a tree. Pengguna tidak dan seharusnya tidak perlu tahu bagaimana push () dan pop () bekerja, atau apakah data disimpan dalam array, sebuah linked list, atau beberapa struktur data lain seperti pohon.

The Interface Antarmuka

The ADT specification is often called an interface . ADT spesifikasi yang sering disebut antarmuka. It's what the user of the class actually sees. Itu apa yang user kelas benar-benar melihat. In Java, this would often be the public methods. Di Jawa, ini sering menjadi metode umum. Consider for example, the stack class - the public methods push() and pop() and similar methods from the interface would be published to the end user. Pertimbangkan untuk contoh, kelas tumpukan - metode publik push () dan pop () dan metode yang serupa dari antarmuka akan diterbitkan kepada pengguna akhir.