review 1 semester

Linked list adalah salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara sekuensial, saling berhubungan dan juga dinamis. suatu linked list dapat diartikan juga sebagaia suatu simpul/ node yang dikaitkan dengan simpul lain dalam suatu urutan tertentu dan dimana simpul dapat berbentuk struktur atau class dan mempunyai satu atau lebih dari elemen struktur atau class.

Jenis jenis linked list

Linked list dibagi menjadi 3, yaitu:

1.                Circular Single Linked List

2.                Doubly Linked List

3.                Circular Doubly Linked List

Circular single linked list

Single Linked List merupakan suatu linked list yang hanya memiliki satu variable pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menujuk ke NULL. Tetapi untuk Circular Single Linked List ada pointer dari tail menuju ke head, sehingga tidak ada pointer yang menujuj ke NULL.

Double Linked List
Double Linked List merupakan suatu linked list yang memiliki dua variable pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. setiap head dan tailnya juga menunjuk ke NULL. 

Circular Doubly Linked List

Dan untuk yang terakhir adalah Circular Doubly Linked List, yaitu linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya( next), 1 field menunjuk pointer sebelumnnya(prev), serta sebuah field yang berisi data untuk node tersebut. Double Linked List Circular pinter next dan prev nya menunjuk ke dirinya sendiri secara circular.

Hash Table & Binary Tree

         Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

operasi yang terdapat pada hash table adalah

    1. insert  : diberikan sebuah key dan nilai, insert nilai pada table

    2. find      : diberikan sebuah key, temukan nilai yang berhubungan dengan key

    3. remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut

                4. getIterator : mengambalikan iterator,yang memeriksa nilai satu demi satu

BINARY TREE

Pohon (Tree) adalah graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung maka pada pohon selalu terdapat path atau jalur yang menghubungkan kedua simpul di dalam pohon. Pohon dilengkapi dengan Root (akar).

Pohon binar (binary tree) adalah himpunan simpul yang terdiri dari 2 subpohon (yang disjoint / saling lepas) yaitu subpohon kiri dan subpohon kanan.Setiap simpul dari pohon binar mempunyai derajat keluar maksimum = 2.

Pendefinisian pohon  binar bersifat rekursif. Pohon binar acapkali disajikan dalam bentuk diagram.

 

Sebuah pohon binar T didefinisikan terdiri atas sebuah himpunan hingga elemen yang disebut simpul(node), sedemikian sehingga :

a.T adalah hampa (disebut pohon null) atau;

b.T mengandung simpul R yang dipilih(dibedakan dari yang lain), disebut “akar: atau “roof” dari T, dan simpul sisanya membentuk 2 pohon binary (subpohon kiri dan subpohon kanan dari akar R).

Terminologi Pada Pohon Binar

Terminologi hubungan keluarga banyak digunakan dalam terminology pada pohon binary. Misalnya istilah anak kiri dan anak kanan, untuk menggantikan suksesor kiri dan suksesor kanan , serta istilah ayah untuk pengganti prodesesor. Selain itu juga istilah saudara (brother) yang diberikan kepada kedua simpul yang mempunyai ayah yang sama. Jelas bahwa setiap simoul kecuali akar mempunyai ayah yang tunggal.

Pohon Binar Lengkap

Setiap simpul dari pohon binary paling banyak mempunyai dua anak. Suatu pohon binar T dikatakan lengkap atau complete, bila  setiap tingkatnya kecuali mungkin tingkat yang terakhir, mempunyai semua simpul yang mungkin yakni 21 simpul untuk tingkat ke-r, dan bila semua simpul pada tingkat terakhir muncul dibagian kiri pohon. Jadi, pohon binary lengkap dengan simpul, T adalah tunggal(dalam hal ini mengabaikan label simpul).

Pohon-2

Pohon Binar T dikatakan pohon-2 atau pohon binar yang dikembangkan(extended binary tree) bila setiap simpul mempunyai 0 atau 2 anak. Dalam kasus ini, simpul dengan dua anak disebut simpul internal, sedanglan simpul tanpa anak disebut simpul eksternal. Dalam diagramnya, seringkali diadakan perbedaan antara simpul internal dan eksternal. Simpul internal digambar sebagai lingkaran, sedangkan simpul eksternal sebagai bujur sangkar.

Penyajian Pohon Binar Dalam Memori

Kita dapat menyajikan suatu pohon binary T dalam memori dengan dua cara. Cara pertama adalah penyajian kait (link).  Cara ini biasa digunakan. Ia analaog dengan cara list berkaitan (linked list) ketika disajikan dalam memori. Cara kedua adalah dengan menggunakan sebuah array tunggal disebut penyajian sekuensial T.

 

Kebutuhan utama yang harus dipenuhi pada setiap penyajian T bahwa seseorang dapat mempunyai akses langsung ke akar R dan T, bila diberikan sembarang simpul N, seseorang harus dapat akses langsung ke anak dari N.

Stack (Tumpukan) sebenarnya secara mudah dapat diartikan sebagai list (urutan) dimana penambahan dan pengambilan elemen hanya dilakukan pada satu sisi yang disebut top (puncak) dari stack.

Dengan melihat definisi tersebut maka jelas bahwa pada stack berlaku aturan LIFO (Last In First Out), yaitu elemen yang terakhir masuk akan pertama kali diambil atau dilayani. Salah satu analogi yang dapat dikemukakan di sini adalah tumpukan piring atau barang lain.

Queue (Antrian) sebenarnya juga merupakan suatu list. Salah satu sifat yang membedakan queue dengan stack adalah bahwa pada queue penambahan elemen dilakukan pada salah satu ujung (ujung depan) dan pengambilan dilakukan pada ujung yang lain (ujung belakang) . Dengan demikian queue menggunakan prinsip FIFO (First In First Out), yaitu elemen yang pertama masuk akan pertama kali pula dikeluarkan.

berikut codingan untuk dreamer market

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct data{
 char nama[50];
 int banyak,harga;
 struct data *next;
 struct data *prev;
}*head=NULL,*tail=NULL,*curr;
struct data* createnode(char name[],int qnty){
 struct data *node = (struct data*)malloc(sizeof(struct data));
 strcpy(node->nama,name);
 node->banyak=qnty;
 node->harga=(rand()%(499000))+1000;
 node->next = node->prev=NULL;
 return node;
};
void pushhead(struct data *node){
 if(head==NULL){
  head=tail=node;
 }
 else{
  node->next=head;
  head->prev=node;
  head=node;
 }
}
void pushtail(struct data *node){
 tail->next=node;
 node->prev=tail;
 tail= node;
}
void insertdata(char name[],int qnty){
 struct data *node = createnode(name,qnty);
 if(head==NULL){
  pushhead(node);
 }
 else{
  if(strcmp(head->nama,name)>0){
   pushhead(node);
  }
  else if(strcmp(tail->nama,name)<0){
   pushtail(node);
  }
  else{
   struct data *temp = head;
   while(temp!=NULL){
    if(strcmp(temp->nama,name)>0) break;
    temp = temp->next;
   }
   node->next = temp;
   node->prev = temp->prev;
   temp->prev->next=node;
   temp->prev = node;
  }
 }
}
void printll(){
 struct data *node= head;
 int i=1;
 int total=0;
 printf("\nNO -    Nama (quantity)  -   Price\n");
 printf("===================================\n");
 while(node!=NULL){
 printf("%d - %s(%d) - %-7d\n",i,node->nama,node->banyak,node->harga);
  total+=(node->harga*node->banyak);
  node=node->next;
  i++;
 }
 printf("Total harga = Rp%d\n\n",total);
}
//void printbelakang(){
// struct data *node = tail;
// while(node!=NULL){
//  printf("%s  %d  %d\n",node->nama,node->banyak,node->harga);
//  node=node->prev;
// }
//}
void pophead(){
 if(!head){
  return;
 }
 else if(head==tail){
  head = tail =NULL;
  free(head);
 }
 else{
  data *temp = head->next;
  head->next=temp->prev=NULL;
  free(head);
  head=temp;
 }
}
void poptail(){
 struct data *temp = tail->prev;
 temp->next=tail->prev=NULL;
 free(tail);
 tail=temp;
}
void popmid(char temp[]){
 curr=head;
 while(curr!=NULL){
  if(strcmp(curr->nama,temp)==0){
   break;
  }
  curr=curr->next;
 }
 if(curr==NULL){
 }
 else{
  curr->prev->next=curr->next;
  curr->next->prev=curr->prev;
  free(curr);
 }
}
void deletes(char temp[]){
 if(strcmp(head->nama,temp)==0){
  pophead();
 }
 else if(strcmp(tail->nama,temp)==0){
  poptail();
 }
 else{
  popmid(temp);
 }
}
bool search (char temp[]){
 curr=head;
 while(curr!=NULL){
  if(strcmp(curr->nama,temp)==0){
   break;
  }
  else{
   curr=curr->next;
  }
 }
 if(curr==NULL){
  return false;
 }
 else{
  return true;
 }
}
int main(){
 char tempnama[50];
 int tempbanyak;
 int menu=0;
 char temp[50];
 int change;
 do{
  printf("    Dreamer Market\n");
  printf("=======================\n");
  printf("1. Add item\n");
  printf("2. View item\n");
  printf("3. Edit quantity\n");
  printf("4. Delete item\n");
  printf("5. Checkout\n");
  printf(">> ");
  scanf("%d",&menu);getchar();
  switch(menu){
   case 1:
    printf("\n  Add item\n");
    printf("=============\n");
    printf("Item name: ");
    scanf("%s",&tempnama);getchar();
    printf("Item quantity: ");
    scanf("%d",&tempbanyak);getchar();
    insertdata(tempnama,tempbanyak);
    printf("\nItem added\n\n");
    break;
   
   case 2:
    printll();
    break;
  
   case 3:
    printf("\n    Edit item\n");
    printf("=================\n");
    printf("Item name: ");
    scanf("%s",&temp);
    if(search(temp)){
     printf("Total Quantity: %d",curr->banyak);
     printf("Insert Quantity to be changed: ");
     scanf("%d",&change);getchar();
     curr->banyak=change;
     printf("\nItem updated\n\n");
    }
    else{
     printf("\nItem is not found\n\n");
    }
    break;
   
   case 4:
    printf("\n  Delete item\n");
    printf("================\n");
    printf("Item name: ");
    scanf("%s",&temp);
    deletes(temp);
    printf("\nItem deleted\n\n");
    break;
   
   case 5:
    break;
  }
 }while(menu!=5);
 printll();
 printf("It's on us, Kindness is Free, Stay safe from corona :)\n");
 return 0;
}