selama melewati semester ini, saya telah mempelajari tentang Pointer , Array, Data Structure, linked list, stack & queue, hashing, hashing table, tree, dan binary tree. Berikut adalah rangkumannya:
1. Pointer
Pengertian Pointer
Pointer/penunjuk adalah sebuah variable yang menunjuk ke alamat variable yang lain. Pointer hanya menyimpan alamat memori yang berasal dari variabel atau obyek. Kegunaan dari pointer antara lain adalah untuk menunjuk suatu memori, mendapatkan isi memori, ataupun mengubah isi memori.
Operator pada Pointer
The address operator (&) : Berfungsi untuk mendapatkan alamat memori yang dituju.
The dereferencing operator (*): Berfungsi untuk mendapatkan nilai yang dituju.
Cara Declare Pointer
Berikut adalah cara declare pointer
Tipe data *nama_pointer;
contoh:
int a;
int *pa;
pa = &a;
p = 10; atau *pa = 10;
Pointer to pointer
Dalam Bahasa C kita dapat memakai pointer yang menunjuk ke pointer yang lain. Untuk Declare pointer to pointer, kita tinggal menambahkan jumlah *.
Contoh:
Int a=10;
Int *pa, **ppa;
Pa=&a;
Ppa=&pa;
===============================================================
2. Array
Pengertian array
Array adalah variabel yang menyimpan kumpulan data yang memiliki tipe data yang sama. adi dapat dikatakan bahwa array merupakan kumpulan dari data-data tunggal yang dijadikan dalam 1 variabel.
Cara deklarasi & akses array
Berikut adalah cara deklarasi & akses array
Sintaks: tipe nama[size];
Contoh: Int angka[3];
Angka[0]=3;
Angka[1]=8;
Angka[2]=2;
Menyimpan nilai array
Menyimpan nilai ke dalam array: initialize, input, assign.
1. Initialize
Contoh: int marks[5]={3,2,6,8,9}
2. Input
Contoh: int a, marks[10];
For(i=0;i<10;i++)
Scanf(“%d”,& marks[i]);
3. Assign
Int i, arr1[10],arr2[10];
For(i=0;i<10;i++)
Arr2[i]=arr[i];
Operasi pada array
Berikut macam-macam operasi yang bisa dilakukan pada array:
1. Insertion
2. Traversal
3. Insertion
4. Searching
5. Deletion
6. Merging
7. Sorting
=======================================================
3. Data Structure
Data type
Data type adalah himpunan yang dapat ditemui pada semua data. Sebagai contoh, tipe data integer mengandung object(contohnya: ,-2,-1,0,1,2….), dan operation(contohnya: +,-,*,/…..).
Structure
Structure adalah user-defined data type yang menyimpan informasi-informasi yang berkaitan secara bersamaan. Berbeda dengan array yang hanya bisa menyimpan kumpulan tipe data yang sama, structure dapat menyimpan kumpulan tipe data yang berbeda-beda.
Cara deklarasi Structure
Berikut contoh cara deklarasi sebuah structure:
Struct murid{
Int umur;
Char nama;
Float nilai;
};
Structure assignment
Tdata a;
a.umur=18;
strcpy(a.nama,”carel”);
a.nilai=85.5;
Data structure
Data structure adalah susunan data. Berikut adalah beberapa contoh data structure: Arrays, Linked list, queue, stacks, binary trees, dan lain-lain.
===============================================================
4. Linked list
Pengertian linked list
Linked list adalah sekumpulan elemen yang memiliki tipe yang sama. Linked list memiliki urutan tertentu, setiap elemennya memiliki 2 bagian. Kelebihan linked list adalah karena sifatnya yang dinamis. Dalam linked list kita juga dapat melakukan insertion dan deletion. Link terbagi menjadi dua tipe yaitu single linked list, dan double linked list.
Bagian-bagian linked list
Sumber: http://strukdat16061089.blogspot.com/2018/07/linked-list.html
Dari gambar di atas dapat disimpulkan bahwa setiap node memiliki 2 field.
Memory Allocation: Dynamic
Dalam c/c++ kita dapat melakukan allocate memory secara dinamik , menggunakan “malloc”, dan menggunakan “free” untuk melakukan de-allocate.
Contoh:
int *pa = (int *) malloc(sizeof(int));
char *pb = (char *) malloc(sizeof(char));
*pa = 205;
*pb = ‘A’;
printf( “%d %c\n”, *pa, *pb );
free(pa);
free(pb);
single linked list
untuk membuat linked list, pertama kita harus menentukan node structure-nya.
struct tnode {
int value;
struct tnode *next;
};
struct tnode *head = 0;
Dalam code diatas dapat disimpulkan bahwa head pointer ke elemen pertama dalam linked list yang anda buat.
Single linked list: insert
struct tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = head;
head = node;
tanda -> memiliki arti yang sama dengan:
(*node).value=x;
(*node).next = head;
Single linked list: delete
Ketika melakukan delete pada single linked list ada yang sebaiknya diperhatikan yaitu : jika x ada di head node, atau jika x tidak ada di head node.
Berikut adalah contohnya: qw
struct tnode *curr = head;
// jika x ada di head note
if ( head->value == x ) {
head = head->next;
free(curr);
}
// jika x tidak ada di head note
else {
while ( curr->next->value != x ) curr = curr->next;
struct tnode *del = curr->next;
curr->next = del->next;
free(del);
};
Circular Single Linked List
Dalam circular, node terakhir mengandung pointer ke node pertama.
http://suciantinovi.blogspot.com/2014/03/linked-list-i_14.html
Doubly Linked List
Doubly linked list adalah linked list structure dengan 2 link, yaitu ke data sebelumnya dan ke data sesudahnya.
https://tutorialspoint.dev/data-structure/advanced-data-structures/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1
struct tnode {
int value;
struct tnode *next;
struct tnode *prev;
};
struct tnode *head = 0;
struct tnode *tail = 0;
Circular Doubly Linked List
Circular doubly linked list sama dengan circular linked list, tetapi total di setiap node adalah 2.
sumber: https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/
=============================================================================================================
5. Stack
Apa itu stack?
Stack adalah data structure yang menyimpan elemennya secara berurutan. Jika dianalogikan, stack seperti sebuah tumpukan piring. Ketika ingin mengambil piring, maka kita mengambilnya dari piring yang paling atas.
Stack adalah linear data structure. Stack bisa dibuat dengan menggunakan array atau linked list. Data dalam stack disimpan dengan prinsip Last in First Out(LIFO).
Array dalam stack
Array memiliki 2 variable yaitu top dan max. Top berguna untuk menyimpan alamat dari elemen teratas dalam sebuah stack. Max berguna untuk menyimpan jumlah maksimal dari elemen yang bisa disimpan oleh stack.
Linked list dalam stack
Membuat stack menggunakan array lebih mudah daripada menggunakan linked list. tapi kelemahan dari memakai array adalah jumlah data tidaklah dinamis. berbeda dengan jika kita menggunakan linked list. Dalam linked stack terdapat node. setiap node memiliki 2 bagian. yaitu, bagian yang menyimpan data, dan bagian yang menyimpan alamat node selanjutnya. Dalam linked stack, Top adalah start pointer. insertion atau deletion terjadi di node yang ditunjuk oleh top.
Macam-macam operasi dalam stack
dalam stack kita dapat melakukan beberapa operasi yaitu push(x), pop(), dan top(). Push(x) yaitu menambahkan item x di data teratas stack. pop() yaitu menghapus item dari data teratas stack, dan top() yaitu mengembalikan data teratas stack.
prefix, infix dan postfix
prefix adalah operator yang ditulis sebelum operand.berikut adalah contoh prefix: *5 10. infix adalah operator yang ditulis di antara operand. berikut adalah contoh infix: 3 * 8. postfix adalah operator yang ditulis setelah operand. berikut adalah contoh postfix: 9 3 *.
Depth First Search
Depth first search ( DFS ) adalah sebuah algoritma untuk melakukan traversing atau searching di dalam tree atau graph. DFS mempunyai beberapa manfaat. Diantaranya adalah dalam sorting topologi, dan mencari komponen yang terhubung.
==========================================================
6. queue
Queue adalah data structure yang menyimpan elemen secara berurutan. Contoh queue dalam kehidupan sehari-hari adalah mengantri masuk ke dalam bis. Orang yang mengantri pertama akan masuk lebih dulu ke dalam bisa. Sama seperti stack, kita dapat membuat queue dengan menggunakan array atau linked list. Perbedaan antara stack dan queue adalah stack menggunakan prinsip Last in First Out ( LIFO ), sedangkan queue menggunakan prinsip First In First Out ( FIFO ).
Array dalam queue
Queue memiliki 2 variable yaitu front dan rear. berikut adalah contoh representasi array dalam queue.
Dari gambar di atas dalam kita lihat front nya yaitu 0, dan rear nya yaitu 5.
Linked List dalam queue
Dalam linked queue, setiap elemen memiliki 2 bagian yaitu yang menyimpan data dan yang menyimpan alamat dari elemen selanjutnya. Dalam linked queue, Front adalah start pointer nya.
Operasi-operasi dalam queue
Operasi - operasi yang bisa dilakukan dalam queue yaitu push(x), pop(), dan front(). Push(x) adalah
menambahkan item x ke belakang queue. pop() adalah menghapus item dari depan queue. dan front() adalah mengembalikan item terdepan dalam queue.
menambahkan item x ke belakang queue. pop() adalah menghapus item dari depan queue. dan front() adalah mengembalikan item terdepan dalam queue.
pengaplikasian queue
berikut adalah beberapa pengaplikasian queue: deques, priority queues, dan Breadth First Search ( BFS ).
======================================================================
7. Hashing & hash table
Hashing
Hashing adalah proses mengubah objek menjadi angka/karakter. Hashing digunakan untuk menyimpan dan mengambil keys dengan secara cepat. Contoh hashing adalah menjadikan string menjadi bilangan.
Hash Table
Hash table adalah tabel dimana kita menyimpan string yang sebenarnya. Index dari hash table adalah hashed key ketika value nya masih original. berikut adalah contoh hash table.
Hash Function
Ada beberapa cara untuk melakukan hash. Beberapa cara untuk membuat fungsi hash antara lain adalah:
mid-square
division
folding
digit extraction
rotating hash
collision (linear probing)
collision (chaining)
=====================================================================
8. tree & binary tree
Apa itu tree
Tree adalah data structure yang merepresentasikan tentang hubungan antara data secara hierarki.
Konsep tree
Berikut adalah konsep tree. dapat dilihat pada gambar di bawah:
- tree tersebut memiliki tinggi 4.
- f adalah root.
- tree tersebut memiliki 9 nodes.
- leaves nya adalah a, c, e, dan h.
- a adalah sibling dari d
- a adalah child dari b
- d adalah parent dari c dan e
- g adalah ancestor dari I dan h
- i dan h adalah descendant dari g.
konsep binary tree
Binary tree adalah tree yang setiap node nya memiliki paling banyak 2 child.
Jenis - jenis binary tree
berikut contoh beberapa jenis binary tree:
perfect binary tree
complete binary tree
skewed binary tree
Representasi binary tree
array
linked list
expression tree
expression tree adalah binary tree yang berguna untuk mewakili ekspresi. Di dalam expression tree terdapat operand.
Prefix: +3*+5, 9, 2
infix: 3+((5+9)*2)
postfix: 3+5,9+2*
Threaded binary tree
Threaded binary tree adalah binary tree yang memfasilitasi traversal dalam urutan-urutan tertentu.
Threaded binary tree terbagi menjadi dua, yaitu single threaded binary tree, dan double threaded binary tree.
