Senin, 25 Juni 2012

Linked List


BAB V
LINKED LIST
Konsep dasar struktur data dinamis adalah alokasi memori yang dilakukan secara dinamis. Pada konsep ini, terdapat suatu struktur yang disebut dengan struktur referensi diri (self-referntial structure), mempunyai anggota pointer yang menunjuk ke struktur yang sama dengan dirinya sendiri. Struktur data dinamis sederhana dapat dibagi menjadi empat jenis, yaitu :
1. Linked list
2. Stack
3. Queue
4. Binary tree
DEFINISI LINKED LIST
Linked list adalah suatu cara untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data yang diperlukan. Program akan berisi suatu struct atau definisi kelas yang berisi variabel yang memegang informasi yang ada didalamnya, dan mempunyai suatu pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya. Struktur dinamis ini mempunyai beberapa keuntungan disbanding struktur array yang bersifat statis. Struktur ini lebih dinamis, karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya bersifat tetap. Manipulasi setiap elemen seperti menyisipkan, menghapus, maupun menambah dapat dilakukan dengan lebih mudah.
Contoh:
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct nod {
            int data;
            struct nod *next;
} NOD, *NODPTR;

void CiptaSenarai(NODPTR *s)
{
            *s = NULL;
}

NODPTR NodBaru(int m)
{
            NODPTR n;

            n = (NODPTR) malloc(sizeof(NOD));
            if(n != NULL) {
                        n -> data = m;
                        n -> next = NULL;
}
return n;
}

void SisipSenarai (NODPTR *s, NODPTR t, NODPTR p)
{
            if (p==NULL) {
                        t -> next = *s;
                        *s = t;
            }
            else {
                        t -> next = p -> next;
                        p ->next = t;
            }
}

void CetakSenarai (NODPTR s)
{
            NODPTR ps;
            for (ps = s; ps != NULL; ps = ps -> next)
                        printf("%d -->", ps -> data);
            printf("NULL\n");
}

int main ()
{
            NODPTR pel;
            NODPTR n;

            CiptaSenarai(&pel);
            n = NodBaru(55);
            SisipSenarai(&pel, n, NULL);
            n= NodBaru(75);
            SisipSenarai(&pel, n, NULL);
            CetakSenarai(pel);
            return 0;
}

Tampilan


CONTOH LATIHAN:
Buatlah program untuk memeasukkan beberapa data dalam sebuah senarai (linked list), jika akan mengakhiri tekan n maka akan muncul semua node yang masuk ke dalam linked list tersebut.
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<stdlib.h>
typedef struct NODE {
int lkey;
char name[10];
struct NODE* next;
} TNODE;
TNODE *first, *last;
int LoadNode(TNODE *p);
void FreeNode(TNODE *p);
void PrintNode(TNODE *p);
void CreateList()
{
TNODE *p;
int n = sizeof (TNODE);
first=last=0;
for(;;)
{
if((p=(TNODE*)malloc(n))==0)
{
printf("\nmemori tidak cukup");
break;
}
if (LoadNode(p) !=1)
{
FreeNode (p);
break;
}
p->next=0;
if (first==0)
first=last=p;
else{
last->next=p;
last=p;
}
}
}
int LoadNode(TNODE *p)
{
char opt;
printf("\nMasukkkan node baru ?");
opt=getche();
opt=toupper(opt);
if (opt!= 'N') {
puts("\nMasukan data untuk node : ");
printf("\nname :\t");
if (scanf("%d", &(p->lkey))!=1)
return 0;
printf("\nname:\t"); if
(scanf("%s",p->name)!=1)
return 0;
return 1;
}
else
return -1;
}
void FreeNode(TNODE *p){
free(p);
}
void ViewAllList()
{
TNODE *p;
p=first;
while(p){
PrintNode(p);
p=p->next;
}
}
TNODE* FindNode(int key)
{
TNODE *p;
p=first;
while(p) {
if(p->lkey == key) return p;
p=p->next;
}
return 0;
}
void PrintNode(TNODE *p)
{
if (p) printf("\n%d\t%s",p->lkey,p->name);
}
TNODE* InsertBeforeFirst()
{
TNODE *p;
int n=sizeof(TNODE);
if (((p=(TNODE*)malloc(n))!=0)
&& (LoadNode(p)==1))
{
if (first==0){
p->next=0;
first=last=p;
}
else{
p->next=first;
first=p;
}
return p;
}
if(p==0)
printf("\nMemori tidak cukup");
else
FreeNode(p);
return 0;
}
TNODE* InsertBeforeKey(int key)
{
TNODE *p,*q,*ql;
int n=sizeof(TNODE);
ql=0;
q=first;
while(q){
if(q->lkey==key)break;
ql=q;
q=q->next;
}
if(q==0){
printf("\nTidak ada node yang mempunyai kunci atau senarai kosong");
return 0;
}
if (((p=(TNODE*)malloc(n))!=0)
&& (LoadNode(p)==1)){
if (q==first){
p->next=first;
first=p;
}
else {
p->next=q;
ql->next=p;
}
return p;
}
if(p==0)
printf("\nMemori tidak cukup");
else
FreeNode(p);
return 0;
}
TNODE* InsertAfterKey(int key)
{
TNODE *p, *q;
int n=sizeof(TNODE);
q = first;
while(q){
if(q->lkey == key) break;
q=q->next;
}
if(q==0){
printf("\nTidak ada nod yang mempunyai kunci atau senarai yang kosong");
return 0;
}
if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1))
{
if (q==last){
p->next=0;
last->next=p;
last=p;
}
else {
p->next=q->next;
q->next=p;
}
return p;
}
if (p==0)
printf("\nMemori Tidak cukup ");
else
FreeNode(p);
return 0;
}
TNODE* InsertAfterLast()
{
TNODE *p;
int n=sizeof(TNODE);
if (((p=(TNODE*)malloc(n))!=0)&&
(LoadNode(p)==1))
{
p->next=0;
if (first==0)
first=last=p;
else {
last->next=p;
last=p;
}
return p;
}
if(p==0)
printf("\nMemori todak cukup");
else
FreeNode(p);
return 0;
}
void RemoveFirst()
{
TNODE *p;
if (first==last){
FreeNode(first);
first=last=0;
return;
}
p=first;
first=first->next;
FreeNode(p);
}
void RemoveLast()
{
TNODE *p, *q;
if(first==0)
return;
if (first==last){
FreeNode(first);
first=last=0;
return;
}
q=0;
p=first;
while(p!=last){
q=p;
p=p->next;
}
p=last;
FreeNode(p);
q->next=0;
last=q;
}
void RemoveByKey(int key)
{
TNODE *p, *q;
if (first==0)
return;
q=0;
p=first;
while(p){
if(p->lkey==key) break;
q=p;
p=p->next;
}
if(!p){
printf("\nTidak ada node yang mempunyai kunci");
return;
}
if (first==last){
FreeNode(first);
first=last=0;
return;
}
if(p==first){
first=first->next;
FreeNode(p);
return;
}
if(q==last){
q->next=0;
last=q;
FreeNode(p);
return;
}
q->next=p->next;
FreeNode(p);
}
void DeletList()
{
TNODE *p;
p=first;
while(p){
first=first->next;
FreeNode(p);
p=first;
}
last=0;
}
void main()
{
CreateList();
ViewAllList();
InsertAfterLast();
ViewAllList();
RemoveFirst();
ViewAllList();
InsertAfterKey(1);
ViewAllList();
RemoveByKey(1);
ViewAllList();
DeletList();
ViewAllList();
}





Tampilan
Analisa : Diatas merupakan salah satu program yang menggunakan Linked List, Linked List adalah adalah suatu cara untuk menyimpan data dengan struktur sehingga dapat  secara otomatis menciptakan suatu tempat baru untuk meyimpan data yang diperlukan. dapat berisi struct atau definisi kelas yang berisi variable yang memegang informasi  yang ada di dalamnya dan mempunyai satu pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya. Bias d liat program nya diatas.
LATIHAN
1. 
#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <stdio.h>
#include <alloc.h>

int pil;
int tdkblhsm();
void pilih();
void buat_baru();
int tambah();
void hapus();
void tampil();

struct simpul
{
      char nama [20];
      long int nim;
      struct simpul *next;
} mhs, *baru, *awal=NULL, *akhir=NULL,*hps, *bantu;

int x=0;

int tdkblhsm(int cari)
{
      struct simpul *baru;
      int ketemu=0;

      if(awal==NULL)
       ketemu=0;
      else
      {
        baru=awal;
        while(baru!=NULL)
        {
             if(cari==baru->nim)
                  {
                    ketemu=1;
                    break;
                  }
             baru=baru->next;
        }
      }
      return ketemu;

}

int main()
{
      do
      {
            clrscr();
            cout<<"MENU SINGLE LINKEDLIST"<<endl;
            cout<<"1. Tambah "<<endl;
            cout<<"2. Hapus"<<endl;
            cout<<"3. Tampilkan"<<endl;
            cout<<"4. Selesai"<<endl;
            cout<<"Pilihan Anda : ";
            cin>>pil;
            pilih();
      } while(pil!=4);
      return 0;
}

void pilih()
{
      if(pil==1)
            tambah();
      else if(pil==2)
            hapus();
        else if(pil==3)
            tampil();
      else
            cout<<"selesai";
}

int tambah()
{
      baru=(struct simpul *)malloc(sizeof(struct simpul));
      cout<<"input nim   : ";cin>>baru->nim;
      if(tdkblhsm(baru->nim)!=0)
      {
       cout<<"NIM sudah ada, silahkan input NIM yang lain";
       getch();
       return 0;
      }
      cout<<"input nama  : ";cin>>baru->nama;

      baru->next=NULL;

      if(awal==NULL)
      {
            awal=baru;
            akhir=baru;
      }
      //jika data hanya 1
      else if (baru->nim < awal->nim)
      {
            baru->next=awal;
            awal=baru;
      }
      else
      {
            bantu=awal;
            while(bantu->next!=NULL && baru->nim > bantu->next->nim)
            {
                  bantu=bantu->next;
            }
            baru->next=bantu->next;
            bantu->next=baru;
      }
}
void hapus()
{
      long int nim_cari;
      struct simpul *bantu1;
      if (awal==NULL)
            cout<<"Simpul Kosong";
      else
      {
            cout<<" Masukan NIM yang akan dihapus : ";
            cin>>nim_cari;
            bantu=awal;
            {
                  while(bantu!=NULL && bantu->nim!=nim_cari)
                        bantu=bantu->next;
                  if (bantu==NULL)
                        cout<<"Data tidak ditemukan";
                  else if (bantu==awal)
                  {
                        awal=awal->next;
                        free(bantu);
                  }
                  else if (bantu==akhir)
                  {
                        bantu=awal;
                        while (bantu1->next!=akhir)
                              bantu1=bantu1->next;
                        akhir=bantu1;
                        akhir->next=NULL;
                        free(bantu);
                  }
                  else
                  {
                        bantu1=awal;
                        while(bantu1->next!=bantu)
                              bantu1=bantu1->next;
                        bantu1->next=bantu->next;
                        free (bantu);
                  }
            }
      }
      getch();
}

void tampil()
{
       if (awal==NULL)
              cout<<"Tidak Ada Data";
       else
       {
             bantu=awal;
             while(bantu!=NULL)
             {
                  cout<<"Nim : "<<bantu->nim;
                  cout<<"Nama : "<<bantu->nama;
                  bantu=bantu->next;
             }
       }
       getch();
}

Tampilan



Analisa : Diatas merupakan salah satu program yang menggunakan Linked List, Linked List adalah adalah suatu cara untuk menyimpan data dengan struktur sehingga dapat  secara otomatis menciptakan suatu tempat baru untuk meyimpan data yang diperlukan. dapat berisi struct atau definisi kelas yang berisi variable yang memegang informasi  yang ada di dalamnya dan mempunyai satu pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya.
2.
int tambah()
{
      baru=(struct simpul *)malloc(sizeof(struct simpul));
      cout<<"input nim   : ";cin>>baru->nim;
      if(tdkblhsm(baru->nim)!=0)
      {
       cout<<"NIM sudah ada, silahkan input NIM yang lain";
       getch();
       return 0;
      }
      cout<<"input nama  : ";cin>>baru->nama;

      baru->next=NULL;

      if(awal==NULL)
      {
            awal=baru;
            akhir=baru;
      }
      //jika data hanya 1
      else if (baru->nim < awal->nim)
      {
            baru->next=awal;
            awal=baru;
      }
      else
      {
            bantu=awal;
            while(bantu->next!=NULL && baru->nim > bantu->next->nim)
            {
                  bantu=bantu->next;
            }
            baru->next=bantu->next;
            bantu->next=baru;
      }
}

Tampilan










Analisa : Diatas merupakan salah satu program yang menggunakan Linked List, Linked List adalah adalah suatu cara untuk menyimpan data dengan struktur sehingga dapat  secara otomatis menciptakan suatu tempat baru untuk meyimpan data yang diperlukan. dapat berisi struct atau definisi kelas yang berisi variable yang memegang informasi  yang ada di dalamnya dan mempunyai satu pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya. Struktur ini lebih dinamis, karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya bersifat tetap.
3.
void tampil()
{
       if (awal==NULL)
              cout<<"Kosong";
       else
       {
             bantu=awal;
             while(bantu!=NULL)
             {
                  cout<<"nim : "<<bantu->nim;
                  cout<<"  nama : "<<bantu->nama;
                  bantu=bantu->next;
             }
       }
       getch();
}

Tampilan





Analisa : Diatas merupakan salah satu program yang menggunakan Linked List, Linked List adalah adalah suatu cara untuk menyimpan data dengan struktur sehingga dapat  secara otomatis menciptakan suatu tempat baru untuk meyimpan data yang diperlukan. dapat berisi struct atau definisi kelas yang berisi variable yang memegang informasi  yang ada di dalamnya dan mempunyai satu pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya. Struktur ini lebih dinamis, karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya bersifat tetap.
5.
1.      void hapus()
{
      long int nim_cari;
      struct simpul *bantu1;
      if (awal==NULL)
            cout<<"Simpul Kosong";
      else
      {
            cout<<" Masukan NIM yang akan dihapus : ";
            cin>>nim_cari;
            bantu=awal;
            {
                  while(bantu!=NULL && bantu->nim!=nim_cari)
                        bantu=bantu->next;
                  if (bantu==NULL)
                        cout<<"Data tidak ditemukan";
                  else if (bantu==awal)
                  {
                        awal=awal->next;
                        free(bantu);
                  }
                  else if (bantu==akhir)
                  {
                        bantu=awal;
                        while (bantu1->next!=akhir)
                              bantu1=bantu1->next;
                        akhir=bantu1;
                        akhir->next=NULL;
                        free(bantu);
                  }
                  else
                  {
                        bantu1=awal;
                        while(bantu1->next!=bantu)
                              bantu1=bantu1->next;
                        bantu1->next=bantu->next;
                        free (bantu);
                  }
            }
      }
      getch();
}

Tampilan



Analisa : Diatas merupakan salah satu program yang menggunakan Linked List, Linked List adalah adalah suatu cara untuk menyimpan data dengan struktur sehingga dapat  secara otomatis menciptakan suatu tempat baru untuk meyimpan data yang diperlukan. dapat berisi struct atau definisi kelas yang berisi variable yang memegang informasi  yang ada di dalamnya dan mempunyai satu pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya. dan merupakan sebuah fungsi untuk menghapus sebuah node berdasarkan input nim.
6.
#include<stdio.h>
#include<iostream.h>
#include<conio.h>

struct batang
{
int data;
batang *lanjut;
} *kepala, *buntut, *baru, *hapus, *bantuan;

main()
{
int jml,d;
char pilih;
menu:
clrscr();
printf("Menu:\n");
printf("1. Tambah data dari depan\n");
printf("2. Tambah data dari belakang\n");
printf("3. Hapus data dari depan\n");
printf("4. Hapus data dari belakang\n");
printf("5. Tampil data\n");
pilih=getch();

if (pilih=='1')
{
clrscr();
printf("Berapa data yang akan dimasukan? ");scanf("%i",&jml);
for (int i=1;i<=jml;i++)
{
baru = new batang;
printf("Masukan data ke - %i = ",i);scanf("%i",&baru->data);
if (kepala==NULL)
{
kepala = buntut = baru;
buntut->lanjut = NULL;
}
else
{
baru->lanjut=kepala;
kepala=baru;
}
}
goto menu;
}

if (pilih=='2')
{
clrscr();
printf("Berapa data yang akan dimasukan? ");scanf("%i",&jml);
for (int i=1;i<=jml;i++)
{
baru = new batang;
printf("Masukan data ke - %i = ",i);scanf("%i",&baru->data);
baru->lanjut=NULL;
if (kepala==NULL)
{
kepala = baru;
buntut = baru;
buntut->lanjut = NULL;
}
else
{
buntut->lanjut=baru;
buntut=baru;
}
}
goto menu;
}

if (pilih=='3')
{
clrscr();
printf("Berapa data yang ingin anda hapus dari depan? ");scanf("%i",&jml);
for (int i=1;i<=jml;i++)
{
if(kepala!=buntut)
{
hapus = kepala;
d = hapus->data;
kepala = kepala->lanjut;
delete hapus;
}
else
{
d = buntut->data;
kepala=buntut=NULL;
}
printf("%i terhapus\n",d);
}
getch();
goto menu;
}

if (pilih=='4')
{
clrscr();
printf("Berapa data yang ingin anda hapus dari belakang? ");scanf("%i",&jml);
for (int i=1;i<=jml;i++)
{
bantuan=kepala;
if(kepala!=buntut)
{
while (bantuan->lanjut!=buntut)
{
bantuan = bantuan->lanjut;
}
hapus = buntut;
buntut = bantuan;
d = hapus->data;
delete hapus;
buntut->lanjut=NULL;
}
else
{
d = buntut->data;
kepala=buntut=NULL;
}
printf("%i terhapus\n",d);
}
getch();
goto menu;
}

if (pilih=='5')
{
clrscr();
bantuan = kepala;
while (bantuan!=NULL)
{
printf("%i ",bantuan->data);
bantuan=bantuan->lanjut;
}
getch();
goto menu;
}

else goto menu;

}

Tampilan


Analisa : Diatas merupakan salah satu program yang menggunakan Linked List, Linked List adalah adalah suatu cara untuk menyimpan data dengan struktur sehingga dapat  secara otomatis menciptakan suatu tempat baru untuk meyimpan data yang diperlukan. dapat berisi struct atau definisi kelas yang berisi variable yang memegang informasi  yang ada di dalamnya dan mempunyai satu pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya.
7.
#include<stdio.h>
#include<iostream.h>
#include<conio.h>

struct batang
{
int data;
batang *lanjut;
} *kepala, *buntut, *baru, *hapus, *bantuan;

main()
{
int jml,d;
char pilih;
menu:
clrscr();
printf("Menu:\n");
printf("1. Tambah data dari depan\n");
printf("2. Tambah data dari belakang\n");
printf("3. Hapus data dari depan\n");
printf("4. Hapus data dari belakang\n");
printf("5. Tampil data\n");
pilih=getch();

if (pilih=='1')
{
clrscr();
printf("Berapa data yang akan dimasukan? ");scanf("%i",&jml);
for (int i=1;i<=jml;i++)
{
baru = new batang;
printf("Masukan data ke - %i = ",i);scanf("%i",&baru->data);
if (kepala==NULL)
{
kepala = buntut = baru;
buntut->lanjut = NULL;
}
else
{
baru->lanjut=kepala;
kepala=baru;
}
}
goto menu;
}

if (pilih=='2')
{
clrscr();
printf("Berapa data yang akan dimasukan? ");scanf("%i",&jml);
for (int i=1;i<=jml;i++)
{
baru = new batang;
printf("Masukan data ke - %i = ",i);scanf("%i",&baru->data);
baru->lanjut=NULL;
if (kepala==NULL)
{
kepala = baru;
buntut = baru;
buntut->lanjut = NULL;
}
else
{
buntut->lanjut=baru;
buntut=baru;
}
}
goto menu;
}

if (pilih=='3')
{
clrscr();
printf("Berapa data yang ingin anda hapus dari depan? ");scanf("%i",&jml);
for (int i=1;i<=jml;i++)
{
if(kepala!=buntut)
{
hapus = kepala;
d = hapus->data;
kepala = kepala->lanjut;
delete hapus;
}
else
{
d = buntut->data;
kepala=buntut=NULL;
}
printf("%i terhapus\n",d);
}
getch();
goto menu;
}

if (pilih=='4')
{
clrscr();
printf("Berapa data yang ingin anda hapus dari belakang? ");scanf("%i",&jml);
for (int i=1;i<=jml;i++)
{
bantuan=kepala;
if(kepala!=buntut)
{
while (bantuan->lanjut!=buntut)
{
bantuan = bantuan->lanjut;
}
hapus = buntut;
buntut = bantuan;
d = hapus->data;
delete hapus;
buntut->lanjut=NULL;
}
else
{
d = buntut->data;
kepala=buntut=NULL;
}
printf("%i terhapus\n",d);
}
getch();
goto menu;
}

if (pilih=='5')
{
clrscr();
bantuan = kepala;
while (bantuan!=NULL)
{
printf("%i ",bantuan->data);
bantuan=bantuan->lanjut;
}
getch();
goto menu;
}

else goto menu;

}

Tampilan




Analisa : Diatas merupakan salah satu program yang menggunakan Linked List, Linked List adalah adalah suatu cara untuk menyimpan data dengan struktur sehingga dapat  secara otomatis menciptakan suatu tempat baru untuk meyimpan data yang diperlukan. dapat berisi struct atau definisi kelas yang berisi variable yang memegang informasi  yang ada di dalamnya dan mempunyai satu pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya. user dapat memilih sesuai menu yang ada yaitu menambah simpul baru berserta datanya, membaca semua data pada senarai, menghapus simpul dengan data  yang ditentukan user dan dapat menghapus semua simpul yang ada.

Diposting oleh di
Label:

Tidak ada komentar:

Posting Komentar

Langganan: Posting Komentar (Atom)