Rangkuman Mata Kuliah Struktur Data di Kelas

A. Pembukaan

     Sesuai dengan tugas yang diberikan oleh dosen Mata Kuliah Struktur data, pada kesempatan ini saya memposting rangkuman dari mata kuliah ini, dan mohon maaf apabila banyak kesalahan - kesalahan baik itu mengenai materi yang saya cantumkan maupun mengenai tindakan - tindakan yang mungkin tidak sepatutnya saya lakukan. sebelum itu izinkan saya memperkenalkan diri terlebih dahulu.

• Nama             : Muhammad Kurniawan
• Nim                : 6311069
• Alamat            : Jl. Bina Warga no.2 Cimahi
• Kelas              : 1 TI - 5
• Mata Kuliah    : Teori Struktur Data
• Nama Dosen   : Bapak Dadan Nurdin Bagenda, S.T
• Kampus          : PKN & STIMIK LPKIA

B. Materi - materi Struktur Data yang didapat selama perkuliahan semester II berlangsung

1.     Struktur Data

• Pengertian Struktur Data              

          Seperti apa yang saya dapat dan saya fahami selama ini, Struktur data adalah sebuah skema organisasi, seperti struktur dan array, yang diterapkan pada data sehingga data dapat diinterprestasikan dan sehingga operasioperasi spesifik dapat dilaksanakan pada data tersebut. Struktur data juga dapat disebut dengan cara penyimpanan atau merepresentasikan data didalam computer agar bias dipakai secara efisien. Sedangkan data adalah reperesentasi dari fakta dunia nyata. untuk apa - apa saja yang termasuk kedalam struktur data dapat kita lihat Mind Mapping dibawah ini.

        Seperti yang terlihat diatas Struktur Data terbagi kedalam 2 bagian yaitu sederhana dan Majemuk, dimana dari kedua bagian ini masing - masing memiliki beberapa bidang lagi didalamnya.

a. Struktur data sederhana meliputi

• Array;
• Record;
• DLL.

b. Struktur data Majemuk Meliputi

• Pointer
• Struktur Data majemuk Linear dan
• Struktur Data majemuk non Linear

   Dapat kita lihat pada Mind Map yang ada diatas tertera untuk Struktur Data Majemuk Linear ini meliputi Linked List dan Struktur Data Majemuk Non Linear memiliki 2 bagian lagi yaitu Graph dan Binary Tree.

Binary Tree dan Graph

1. Pengertian Binary Tree

          binary search tree (bst) adalah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. value pada semua node subpohon sebelah kiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing – masing subpohon tersebut (kiri&kanan) itu sendiri adalah juga bst. Contoh Program dapat dilihat Disini.

     2.  Pengertian Graph

          sesuai dengan yang saya amati dari gambar - gambar yang ada, menurut saya Graph ini merupakan sebuah program dalam C++ yg digunakan untuk membentuk sebuah Grafik yang sangat kompleks. untuk source codenya dapat dilihat disini.

Contoh Program Graph

#include <iostream.h>
#include <conio.h>

class graph
{
private:int n;
int **a;
int *reach;
int *pos;
public:graph(int k=10);
void create();
void dfs();
void dfs(int v,int label);
int begin(int v);
int nextvert(int v);
};
void graph::graph(int k)
{
n=k;
a=new int *[n+1];
reach=new int[n+1];
pos=new int [n+1];
for(int i=1;i<=n;i++)
pos[i]=0;
for(int j=1;j<=n;j++)
a[j]=new int[n+1];
}
void graph::create()
{
for(int i=1;i<=n;i++)
{
cout<<"Enter the "<<i<<"th row of matrix a:
";
for(int j=1;j<=n;j++)
cin>>a[i][j];
}
for(int k=1;k<=n;k++)
reach[k]=0;
}
void graph::dfs()
{
int label=0;
for(int i=1;i<=n;i++)
if(!reach[i])
{
label++;
dfs(i,label);
}
cout<<"
The contents of the reach array is:
;
for(int j=1;j<=n;j++)
cout<<reach[j]<<" ";
}
void graph::dfs(int v,int label)
{
cout<<v<<" ";
reach[v]=label;
int u=begin(v);
while(u)
{
if(!reach[u])
dfs(u,label);
u=nextvert(v);
}
}
int graph::begin(int v)
{
if((v<1)&&(v>n))
cout<<"Bad input
";
else
for(int i=1;i<=n;i++)
if(a[v][i]==1)
{
pos[v]=i;
return i;
}
return 0;
}
int graph::nextvert(int v)
{
if((v<1)&&(v>n))
cout<<"Bad input
";
else
for(int i=pos[v]+1;i<=n;i++)
if(a[v][i]==1)
{
pos[v]=i;
return i;
}
return 0;
}
void main()
{
clrscr();
int x;
cout<<"Enter the no of vertices:
";
cin>>x;
graph g(x);
g.create();
cout<<"dfs is.....";
g.dfs();
getch();
}

Pengertian, Macam - macam, dan Penggunaan Linked List dalam C++

Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian Linked list juga merupakan suatu cara untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data yangdiperlukan. Struktur ini lebih dinamis karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya tetap. berikut gambaran kecil mengenai linked list.

Didalam Linked List terdapat beberapa bagian lagi


       1. Linked List Circular


Double Linked List 
       Pengertian secara umumnya DLLC itu Linked list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu:
1 field pointer yang menunjuk pointer berikutnya "next",
1 field menunjuk pointer sebelumnya " prev ", 
1 field yang berisi data untuk node tersebut .


Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC

untuk Contoh Klik saja Disini.

• Single Linked List    

             Single Linked List Circular (SLLC) adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya. untuk Contoh Klik disini.

  

         2. Linked List Non Circular


Double Linked List Non Circular (DLLNC)


             adalah Double Linked List yang memiliki 2 buah pointer yaitu pointernext dan prev.
Pointer next menunjuk pada node setelahnya dan pointer prev menunjuk pada node sebelumnya.


Pengertian: 
Double : artinya field pointer-nya dua buah dan dua arah, ke node sebelum dan sesudahnya.
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Non Circular : artinya pointer prev dan next-nya akan menunjuk pada NULL. 

untuk potongan - potongan Source Code DLLNC klik disini.

Single Linked List Non Circular (SLLNC)

             Adalah Linked List yang pointer nya selalu mengarah ke Node yang menampung *next bernilai NULL, jadi arahnya tidak menunjuk pointer didepannya sehingga tidak dapat kembali ke pointer - pointer sebelumnya. SLLNC ini juga memiliki 2 bagian, ada Tambah dan ada Hapus, masing - masing bagian ini juga masih meliputi 3 fungsi lain yaitu Belakang, Tengah, dan depan. untuk Contoh Tambah & Hapus (Depan & belakang), Klik disini. 

Pengertian dan Penggunaan Pointer

Pointer adalah sebuah Variabel penunjuk alamat dari sebuah data yang ada dalam memory. jadi kita tidak perlu langsung memanggil variabel dari data yang ingin kita akses dan kita hanya perlu mengakses melalu alamatnya saja. dibawah ini adalah contoh program sederhana Pointer.



#include<constream.h>
void main()
{
clrscr();
char *nama = "UNIVERSITAS";
char cari = 'S', tmp;

cout<<"Kata = "<<nama;
cout<<"\nHuruf yang dicari adalah = "<<cari<<endl<<endl;
for(int i=0; i<11; i++){
if(nama[i]==cari)
tmp=nama[i];
//cout<<nama[i]<<" TRUE\n";
//else cout<<nama[i]<<" FALSE\n";
}
if(tmp==cari)
cout<<"Huruf Ditemukan";
else
cout<<"Huruf tidak Ditemukan";
getch();
}

Pengertian Array

Array adalah organisasi kumpulan data homogen yang ukuran atau jumlah elemen maksimumnya telah diketahui dari awal, yang secara otomatis array ini bersifat statis karena memiliki batasan maksimum yg telah ditentukan. berikut Contoh Source Code sederhana penggunaan Array dalam C++.

#include<constream.h>
void main()
{
 clrscr();


 char x[20][20];
 int u[10],p;


 cout<<"jumlah data : ";cin>>p;
 for(int y=1; y<=p; y++)
 {
  cout<<"Data Ke - "<<y<<":"<<endl;
  cout<<"Nama :";cin>>x[y];
  cout<<"Umur :";cin>>u[y];
 }
  for(int z= 1; z<= p; z++)
 {
  cout<<"data ke - "<<z<<" adalah :"<<endl;
  cout<<"Nama :"<<x[z]<<endl;
  cout<<"umur :"<<u[z]<<endl;
 }
 getch();
}

Contoh Program Binary Tree

#include <iostream>


#include <cstdlib>
using namespace std;


class BinarySearchTree
{
    private:
        struct tree_node
        {
           tree_node* left;
           tree_node* right;
           int data;
        };
        tree_node* root;
    public:
        BinarySearchTree()
        {
           root = NULL;
        }
        bool isEmpty() const { return root==NULL; }
        void print_inorder();
        void inorder(tree_node*);
        void print_preorder();
        void preorder(tree_node*);
        void print_postorder();
        void postorder(tree_node*);
        void insert(int);
        void remove(int);
};


void BinarySearchTree::insert(int d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;


  if(isEmpty()) root = t;
  else
  {


    tree_node* curr;
    curr = root;


    while(curr)
    {
        parent = curr;
        if(t->data > curr->data) curr = curr->right;
        else curr = curr->left;
    }


    if(t->data < parent->data)
       parent->left = t;
    else
       parent->right = t;
  }
}


void BinarySearchTree::remove(int d)
{


    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    while(curr != NULL)
    {
         if(curr->data == d)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(d>curr->data) curr = curr->right;
             else curr = curr->left;
         }
    }
    if(!found)
         {
        cout<<" Data not found! "<<endl;
        return;
    }




    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
    {
       if(curr->left == NULL && curr->right != NULL)
       {
           if(parent->left == curr)
           {
             parent->left = curr->right;
             delete curr;
           }
           else
           {
             parent->right = curr->right;
             delete curr;
           }
       }
       else
       {
          if(parent->left == curr)
           {
             parent->left = curr->left;
             delete curr;
           }
           else
           {
             parent->right = curr->left;
             delete curr;
           }
       }
     return;
    }




         if( curr->left == NULL && curr->right == NULL)
    {
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
                  delete curr;
                  return;
    }




    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else
        {


            if((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                   lcurrp = lcurr;
                   lcurr = lcurr->left;
                }
                                    curr->data = lcurr->data;
                delete lcurr;
                lcurrp->left = NULL;
           }
           else
           {
               tree_node* tmp;
               tmp = curr->right;
               curr->data = tmp->data;
                              curr->right = tmp->right;
               delete tmp;
           }


        }
         return;
    }


}


void BinarySearchTree::print_inorder()
{
  inorder(root);
}


void BinarySearchTree::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) inorder(p->left);
        cout<<" "<<p->data<<" ";
        if(p->right) inorder(p->right);
    }
    else return;
}


void BinarySearchTree::print_preorder()
{
  preorder(root);
}


void BinarySearchTree::preorder(tree_node* p)
{
    if(p != NULL)
    {
        cout<<" "<<p->data<<" ";
        if(p->left) preorder(p->left);
        if(p->right) preorder(p->right);
    }
    else return;
}


void BinarySearchTree::print_postorder()
{
  postorder(root);
}


void BinarySearchTree::postorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) postorder(p->left);
        if(p->right) postorder(p->right);
        cout<<" "<<p->data<<" ";
    }
    else return;
}


int main()
{
    BinarySearchTree b;
    int n,ch,tmp,tmp1;
    cout<<"\tOperasi Pohon Biner Lukman Reza \n\n";
    cout<<"Masukkan banyak data: ";
           cin>>n;
                    for (int i=0; i<=n; i++){
                    cout<<"Angka :";cin>>i;
                    b.insert(i);}
                  
                    cout<<"\n\nIn-Order Traversal "<<endl;
                    cout<<"-------------------"<<endl;
                    b.print_inorder();
                  
                    cout<<"\n\nPre-Order Traversal "<<endl;
                    cout<<"-------------------"<<endl;
                    b.print_preorder();
                
                    cout<<"\n\nPost-Order Traversal "<<endl;
                    cout<<"--------------------"<<endl;
                    b.print_postorder();
                    cout<<endl;
                  
           system("pause");
                    return 0;
                  
  
}

Contoh Program Single Linked List Non Circular (Tambah : Depan & belakang dan Hapus : Depan & Belakang)

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#include <alloc.h>

int pil;

void pilih();

void buat_baru();

void tambah_belakang();

void tambah_depan();

void hapus_belakang();

void hapus_depan();

void tampil();

struct simpul

{

    char nim[8], nama [20];

    int umur;

    struct simpul *next;

} mhs, *baru, *awal=NULL, *akhir=NULL,*hapus,*bantu;

int main()

{

    do

    {

        clrscr();

        cout<<"MENU SINGLE LINKEDLIST"<<endl;

        cout<<"1. Tambah Depan"<<endl;

        cout<<"2. Tambah Belakang"<<endl;

        cout<<"3. Hapus Depan"<<endl;

        cout<<"4. Hapus Belakang"<<endl;

        cout<<"5. Tampilkan"<<endl;

        cout<<"6. Selesai"<<endl;

        cout<<"Pilihan Anda : ";

        cin>>pil;

        pilih();

    } while(pil!=6);

    return 0;

}

void pilih()

{

    if(pil==1)

        tambah_depan();

    else if(pil==2)

        tambah_belakang();

    else if(pil==3)

        hapus_depan();

     else if(pil==4)

        hapus_belakang();

      else if(pil==5)

        tampil();

    else

        cout<<"selesai";

}

void buat_baru()

{

    baru=(simpul*)malloc(sizeof(struct simpul));

    cout<<"input nim   : ";cin>>baru->nim;

    cout<<"input nama  : ";cin>>baru->nama;

    cout<<"input umur  : ";cin>>baru->umur;

    baru->next=NULL;

}

void tambah_belakang()

{

    buat_baru();

    if(awal==NULL)

    {

        awal=baru;

    }

    else

    {

        akhir->next=baru;

    }

    akhir=baru;

    akhir->next=NULL;

    cout<<endl<<endl;

    tampil();

}

void tambah_depan()

{

    buat_baru();

    if(awal==NULL)

    {

        awal=baru;

        akhir=baru;

        akhir->next=NULL;

    }

    else

    {

        baru->next=awal;

        awal=baru;

    }

    cout<<endl<<endl;

    tampil();

}

void hapus_depan()

{

    if (awal==NULL)

        cout<<"Kosong";

    else

    {

        hapus=awal;

        awal=awal->next;

        free(hapus);

    }

   cout<<endl<<endl;

    tampil();

}

void hapus_belakang()

{

    if (awal==NULL)

        cout<<"Kosong";

    else if(awal==akhir)

    {

         hapus=awal;

         awal=awal->next;

         free(hapus);

    }

    else

    {

        hapus=awal;

        while(hapus->next!=akhir)

             hapus=hapus->next;

        akhir=hapus;

        hapus=akhir->next;

        akhir->next=NULL;

        free(hapus);

    }

    cout<<endl<<endl;

    tampil();

}

void tampil()

{

     if (awal==NULL)

          cout<<"Kosong";

     else

     {

         bantu=awal;

         while(bantu!=NULL)

         {

            cout<<"nim : "<<bantu->nim;

            cout<<"  nama : "<<bantu->nama;

            cout<<"  umur : "<<bantu->umur<<endl;

            bantu=bantu->next;

         }

     }

     getch();

}