Data Structures
Class 3 – Pengenalan Struktur Data dan ADT
McGraw-Hill Technology Education
Copyright © 2006 by The McGraw-Hill Companies, Inc. All rights reserved.
“I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” Linus Torvalds, 2006 2
Definisi • Struktur Data • adalah cara penyimpanan dan pengorganisasian data-data pada memori komputer secara efektif sehingga dapat digunakan secara efisien, termasuk operasi-operasi di dalamnya.
• Data • adalah representasi dari fakta dunia nyata. • Data serangkaian item-item dasar.
• Fakta • adalah keterangan tentang kenyataan yang dapat disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol.
Organizing Data Any organization for a collection of records can be searched, processed in any order, or modified. The choice of data structure and algorithm can make the difference between a program running in a few seconds or many days.
Efficiency • A solution is said to be efficient if it solves the problem within its resource constraints. • Space • Time
• The cost of a solution is the amount of resources that the solution consumes.
Selecting a Data Structure Select a data structure as follows: 1. Analyze the problem to determine the basic operations that must be supported. 2. Quantify the resource constraints for each operation. 3. Select the data structure that best meets these requirements.
Costs and Benefits • Each data structure has costs and benefits. • Rarely is one data structure better than another in all situations. • Any data structure requires: • space for each data item it stores, • time to perform each basic operation, • programming effort.
Costs and Benefits (cont) • Each problem has constraints on available space and time. • Only after a careful analysis of problem characteristics can we know the best data structure for the task. • Bank example: • Start account: a few minutes • Transactions: a few seconds • Close account: overnight
• Programmer perlu memahami : 1. Bagaimana struktur data diciptakan dalam komputer. 2. Terdapat perbedaan antara bayang difikiran kita tentang data, dan cara data tersebut tersimpan dalam memory komputer sebagai sebuah struktur data. 3. Banyak kelebihan dan kekurangan dari bermacam struktur data yang harus dipertimbangkan programmer ketika menulis program. 4. Setiap struktur data memiliki operasi-operasi tertentu yang secara alami sesuai dengan struktur data tertentu. 5. Seringkali operasi-operasi yang dapat dilakukan pada struktur data terpaket langsung dengan struktur data tersebut (data type). 9
Manfaat •
Pemakaian struktur data yang tepat di dalam proses pemrograman akan menghasilkan : 1. Algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana. 2. Membuat program lebih ringkas, lebih bersih, lebih elegan, lebih mudah dan lebih mampu berkinerja tinggi (karena efisien dalam penggunaan memori dan waktu). E.g. satu program berjalan membutuhkan waktu beberapa detik, di mana struktur yang lain mungkin akan membutuhkan ribuan detik.
3. Supaya data yang disimpan dapat lebih mudah/efisien dalam pengaksesan/pemrosesan data tersebut.
• Secara umum struktur data diklasifikasikan atas : 1. Primitive data structures 2. Non primitive data structure.
1. Primitive data structure: • adalah data structures yang dapat dimanipulasi secara langsung oleh machine instructions. • Dalam bahasa C, beberapa primitive data structures adalah int, float, char, double.
2. Non primitive data structures: • Tidak dapat dimanipulasi langsung oleh instruksi mesin. • E.g. linked lists, files dll. • Diklasifikasikan menjadi 2 jenis : a. linear data structures dan, b. non-linear data structures. 12
Klasifikasi Struktur Data Dasar
13
• Linear Data Structure: • Data structure dimana setiap elemennya memiliki akses paling banyak pada satu elemen sebelum dan satu elemen sesudahnya. • Example: Stack, Queue, etc.
• Linear Data Structures :
15
• Non-linear Data Structure: •
data structure dimana setiap elemennya dapat mengakses data sebelum dan data sesudahnya dalam jumlah yang tidak terbatas.
•
Example: Tree, Graphs, etc.
• Non Linear Data Structures :
17
Static VS Dynamic Data Structures • Static Data Structure: • data structure dimana jumlah elemen-elemen penyusunnya bersifat tetap. • Example: Arrays
• Dynamic Data Structure: • data structure dimana jumlah elemenelemen penyusunnya bersifat tidak tetap. • Example: Linked List.
bagaimanakah struktur data di-support dalam bahasa pemrograman? 1. Sebagai fitur built-in pada bahasa pemrograman. • Arrays pada umumnya di-support oleh bahasa tingkat tinggi. • Linked list pada beberapa bahasa pemrograman. • Classes pada OOP
2. Sebagai fitur yang didefinisikan dalam library atau paket (package). 19
Tipe Data, Obyek Data & Struktur Data • Tipe data adalah jenis data yang mampu ditangani oleh suatu bahasa pemrograman pada komputer. • Tiap-tiap bahasa pemrograman memiliki tipe data yang memungkinkan: • Deklarasi terhadap variabel tipe data tersebut. • Menyediakan kumpulan operasi yang mungkin terhadap variabel bertipe data tersebut. • Jenis obyek data yang mungkin. • Contoh tipe data di C? Java? Pascal? .NET?
Pascal : Str25
= String[25];
TBookRec
= Record Title, Author, ISBN : Str25; Price : Real; End;
i : Integer; myIntArray myBoolArray
: Array[1..20] of Integer; : Array[1..20] of Boolean;
C: char name[100]; int age; 21
Tipe Data, Obyek Data & Struktur Data • Obyek Data adalah kumpulan elemen yang mungkin untuk suatu tipe data tertentu. • Mis: integer mengacu pada obyek data -32768 s/d 32767, byte 0 s/d 255, string adalah kumpulan karakter maks 255 huruf.
• Struktur Data adalah cara penyimpanan dan pengorganisasian data-data pada memori komputer secara efektif sehingga dapat digunakan secara efisien, termasuk operasi-operasi di dalamnya.
Tipe Data Standar Tipe data standar merupakan tipe data yang tersedia pada kebanyakan komputer sebagai built-in features. Tipe data standar yaitu : -Integer -Real - Boolean - Char
Tipe Data • Bahasa pemrograman bisa memiliki tipe data: 1. Built-in (tipe data standar) : • sudah tersedia oleh bahasa pemrograman tersebut • Tidak berorientasi pada persoalan yang dihadapi. • Contoh : int, float, dll.
2. UDT : User Defined Type, dibuat oleh pemrogram. • Mendekati penyelesaian persoalan yang dihadapi • Contoh: record pada Pascal, struct pada C, class pada Java
3. ADT : Abstract Data Type • memperluas konsep UDT dengan menambahkan pengkapsulan atau enkapsulasi, berisi sifat-sifat dan operasi-operasi yang bisa dilakukan terhadap kelas tersebut. • Contoh: class pada Java
ADT (Abstract Data Type) atau Tipe Data Bentukan … • ADT adalah sebuah tipe data yang propertinya (yaitu data dan operasi) dispesifikasikan tanpa tergantung pada implementasi tertentu. • Contoh : Stack ADT. • ADT dapat memiliki beberapa implementasi berbeda. • Implementasi yang berbeda dapat memiliki efisiensi yang berbeda. 25
Abstract Data Types (ADTs) • An abstract data type (ADT) is an abstraction of a data structure • An ADT specifies: • Data stored • Operations on the data • Error conditions associated with operations
• Example: ADT modeling a simple stock trading system • The data stored are buy/sell orders • The operations supported are • order buy(stock, shares, price) • order sell(stock, shares, price) • void cancel(order)
• Error conditions: • Buy/sell a nonexistent stock 26 • Cancel a nonexistent order
