Praktikum Algoritma & Struktur Data

Praktikum ASDPraktikum Algoritma & Struktur Data Login

Butuh Bantuan Asisten?

Info

Soal 1 dan 2 bersumber dari naskah UTS ASD 2022. Editor berisi scaffold lengkap — implementasikan fungsi yang bertanda TODO, lalu klik Run untuk melihat hasilnya sekaligus!

Perhatian

Kunci CLL: Node terakhir selalu menunjuk kembali ke First. Setiap kali InsertFirst atau DeleteFirst, telusuri node terakhir terlebih dahulu dan update pointer-nya!

Soal 1 — Lengkapi Subprogram CLL

Implementasikan kelima subprogram berikut dan verifikasi dengan main yang sudah ada:

cpp

void InsertFirst(List *L, infotype x) { /* ??? */ }
void InsertLast(List *L, infotype x)  { /* ??? */ }
void InsertAfter(List *L, address P, infotype x) { /* ??? */ }
void DeleteFirst(address *P, List *L) { /* ??? */ }
void DeleteLast(address *P, List *L)  { /* ??? */ }

Output yang diharapkan dari Soal 1:

=== Soal 1 ===
List kosong!
3X
4->3X
4->2->3X
6->4->2->3X
6->4->2->3->5X
4->2->3->5X
4->2->3X

Lihat Implementasi Soal 1

cpp

void InsertFirst(List *L, infotype x) {
    address P = Allocation(x);
    if (!P) return;
    if (IsEmpty(*L)) { First(*L) = P; Next(P) = P; return; }
    address Last = First(*L);
    while (Next(Last) != First(*L)) Last = Next(Last);
    Next(P) = First(*L); Next(Last) = P; First(*L) = P;
}

void InsertLast(List *L, infotype x) {
    if (IsEmpty(*L)) { InsertFirst(L, x); return; }
    address P = Allocation(x);
    if (!P) return;
    address Last = First(*L);
     ((Last) != (*L)) Last = (Last);
    (Last) = P; (P) = (*L);
}

{
    address New = (x);
     (New && P) { (New) = (P); (P) = New; }
}

{
     (!(*L)) {
        *P = (*L);
         (((*L)) == (*L)) { (*L) = ; ; }
        address Last = (*L);
         ((Last) != (*L)) Last = (Last);
        (*L) = ((*L)); (Last) = (*L);
    }
}

{
     (!(*L)) {
         (((*L)) == (*L)) { *P = (*L); (*L) = ; ; }
        address Prev = (*L);
         (((Prev)) != (*L)) Prev = (Prev);
        *P = (Prev); (Prev) = (*L);
    }
}

Soal 2 — Trace Output CLL (Variasi)

Dengan implementasi fungsi yang sama dari Soal 1, gambarkan output dari main program Soal 2 berikut tanpa menjalankan kode terlebih dahulu:

cpp

CreateEmpty(&L2);        PrintList(L2);   // 1?
InsertFirst(&L2, 1);     PrintList(L2);   // 2?
InsertLast(&L2, 7);      PrintList(L2);   // 3?
InsertFirst(&L2, 9);     PrintList(L2);   // 4?
InsertAfter(&L2, temp2, 5); PrintList(L2); // 5? (temp2 = First = 9)
InsertLast(&L2, 3);      PrintList(L2);   // 6?
DeleteFirst(&temp2, &L2); PrintList(L2);  // 7?
DeleteFirst(&temp2, &L2); PrintList(L2);  // 8?
DeleteLast(&temp2, &L2);  PrintList(L2);  // 9?

Lihat Kunci Jawaban Soal 2

=== Soal 2 ===
List kosong!
1X
1->7X
9->1->7X
9->5->1->7X
9->5->1->7->3X
5->1->7->3X
1->7->3X
1->7X

Soal 3 — RotateLeft & FindNth

Implementasikan dua fungsi berikut:

RotateLeft — jadikan First->next sebagai First baru (node lama jadi terakhir).
FindNth(L, N) — kembalikan nilai node ke-N secara sirkuler (N bisa lebih besar dari panjang list).

Output yang diharapkan dari Soal 3:

=== Soal 3 ===
Awal:       1->2->3->4->5X
Rotate x1:  2->3->4->5->1X
Rotate x2:  3->4->5->1->2X
Elemen ke-3: 5
Elemen ke-7: 4

Lihat Kunci Jawaban Soal 3

cpp

void RotateLeft(List *L) {
    if (IsEmpty(*L) || Next(First(*L)) == First(*L)) return;
    First(*L) = Next(First(*L));
}

infotype FindNth(List L, int N) {
    if (IsEmpty(L)) return -1;
    int len = 0;
    address tmp = First(L);
    do { len++; tmp = Next(tmp); } while (tmp != First(L));

    int steps = (N - 1) % len;
    tmp = First(L);
    for (int i = 0; i < steps; i++) tmp = Next(tmp);
     (tmp);
}