Monday, December 26, 2016

Bab 16. Soal & Penyelesaian C++


SENARAI BERANTAI





Soal & Penyelesaian
1.       Tulislah sebuah program C++ untuk merealisasikan senarai berantai.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//Simpul.cpp
//Mendemonstrasikan Simpul berantai.
#include <iostream>
#include <conio.h>
using namespace std;

class Simpul
{
    public:
        int iData;     //item data
        double dData;  //item data

        //pointe ke Simpul berikutnya
        Simpul* pBrktnya;

        Simpul(int id, double dd) : //konstruktor
        iData(id), dData(dd), pBrktnya(NULL)
        { }

        void tampilSimpul() //menampilkan Simpul
        {
            cout << "{" << iData << ", " << dData << "} ";
        }
}; //akhir kelas Simpul

class SenaraiBerantai
{
    private:
        //pointe ke Simpul pertama
        Simpul* pPertama;

    public:
        SenaraiBerantai() : pPertama(NULL) //konstruktor
        { } //(masih belum ada Simpul)

        bool apaKosong() //true jika senarai berantai kosong
        { return pPertama==NULL; }

        //menyisipkan ke awal senarai
        void sisipPertama(int id, double dd)
        { //membuat simpul baru
            Simpul* pSenaraiBaru = new Simpul(id, dd);
            pSenaraiBaru->pBrktnya = pPertama;
            pPertama = pSenaraiBaru;
        }

        Simpul* bacaPertama() //menghasilkan Simpul pertama
        { return pPertama; }

        void hapusPertama() //menghapus Simpul pertama
        { //(asumsi senarai berantai tidak kosong)
            Simpul* pTemp = pPertama; //menyimpan simpul pertama
            pPertama = pPertama->pBrktnya;
            delete pTemp;
        }

        void tampilSenarai()
        {
            cout << "Senarai Berantai (pertama-->akhir): ";
            Simpul* pSkrg = pPertama; //berawal di awal senarai

            while(pSkrg != NULL) //sampai akhir senarai,
            {
                pSkrg->tampilSimpul(); //menampilkan data

                //bergerak ke simpul berikutnya
                pSkrg = pSkrg->pBrktnya;
            }
            cout << endl;
        }
}; //akhir kelas SenaraiBerantai

int main()
{
    //menciptakan senarai berantai baru
       SenaraiBerantai senaraiBerantai;

    //menyisipkan empat item     
    senaraiBerantai.sisipPertama(22, 2.99);
    senaraiBerantai.sisipPertama(44, 4.99);
    senaraiBerantai.sisipPertama(66, 6.99);
    senaraiBerantai.sisipPertama(88, 8.99);
    senaraiBerantai.tampilSenarai(); //menampilkan senarai

    while( !senaraiBerantai.apaKosong() ) //sampai kosong,
    {
        //membaca simpul pertama
        Simpul* pTemp = senaraiBerantai.bacaPertama();

        //menampilkan kuncinya
        cout << "Menghapus simpul dengan kunci " << pTemp->iData << endl;
        senaraiBerantai.hapusPertama(); //remove it
    }

    senaraiBerantai.tampilSenarai(); //menampilkan senarai kosong

    getch();
    return 0;
} //akhir main()

Senarai Berantai (pertama-->akhir): {88, 8.99} {66, 6.99} {44, 4.99} {22, 2.99}

Menghapus simpul dengan kunci 88
Menghapus simpul dengan kunci 66
Menghapus simpul dengan kunci 44
Menghapus simpul dengan kunci 22
Senarai Berantai (pertama-->akhir):

2.       Tulislah sebuah program C++ untuk merealisasikan senarai berantai dengan operasi penghapusan dan pencarian dari simpul tertentu.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
//senaraiBerantaiSpesifik.cpp
//Mendemonstrasikan Simpul berantai dengan
//operasi pencarian dan penghapusan simpul tertentu.
#include <iostream>
#include <conio.h>
using namespace std;

class Simpul
{
    public:
        int iData;     //item data
        double dData;  //item data

        //pointe ke Simpul berikutnya
        Simpul* pBrktnya;

        Simpul(int id, double dd) : //konstruktor
        iData(id), dData(dd), pBrktnya(NULL)
        { }

        void tampilSimpul() //menampilkan Simpul
        {
            cout << "{" << iData << ", " << dData << "} ";
        }
}; //akhir kelas Simpul

class SenaraiBerantai
{
    private:
        //pointe ke Simpul pertama
        Simpul* pPertama;

    public:
        SenaraiBerantai() : pPertama(NULL) //konstruktor
        { } //(masih belum ada Simpul)

        ~SenaraiBerantai() //destruktor
        {
            Simpul* pSkrg = pPertama; //berawal di awal senarai
            while(pSkrg != NULL) //sampai senarai kosong,
            {
                Simpul* pLama = pSkrg; //menyimpan simpul skrg
                pSkrg = pSkrg->pBrktnya; //ke simpul brktnya
                delete pLama; //menghapus simpul lama
            }
        }

        //menyisipkan ke awal senarai
        void sisipPertama(int id, double dd)
        { //membuat simpul baru
            Simpul* pSenaraiBaru = new Simpul(id, dd);
            pSenaraiBaru->pBrktnya = pPertama;
            pPertama = pSenaraiBaru;
        }

        Simpul* cari(int kunci) //mencari simpul dengan kunci tertentu
        { //(asumsi senarai berantai tak-kosong)
            Simpul* pSkrg = pPertama; //berawal di awal senarai

            while(pSkrg->iData != kunci) //ketika tidak ada kecocokan,
            {
                if(pSkrg->pBrktnya == NULL) //jika akhir senarai,
                    return NULL; //tidak menemukannya
                else //tidak akhir senarai,
                    pSkrg = pSkrg->pBrktnya; //ke simpul berikutnya
            }
            return pSkrg; //ditemukan
        }

        bool hapus(int kunci) //menghapus simpul dengan kunci tertentu
        { //(asumsi senarai berantai tak-kosong)
            Simpul* pSkrg = pPertama; //mencari simpul
            Simpul* pSblmnya = pPertama;

            while(pSkrg->iData != kunci)
            {
                if(pSkrg->pBrktnya == NULL)
                    return false; //tidak ditemukan
                else
                {
                    pSblmnya = pSkrg; //ke simpul berikutnya
                    pSkrg = pSkrg->pBrktnya;
                }
            } //ditemukan

            if(pSkrg == pPertama) //jika simpul pertama,
                pPertama = pPertama->pBrktnya; //mengubah simpul pertama
            else //sebaliknya,
                pSblmnya->pBrktnya = pSkrg->pBrktnya;

            delete pSkrg; //menghapus simpul
            return true;  //penghapusan berhasil
        }

        void tampilSenarai()
        {
            cout << "Senarai Berantai (pertama-->akhir): ";
            Simpul* pSkrg = pPertama; //berawal di awal senarai

            while(pSkrg != NULL) //sampai akhir senarai,
            {
                pSkrg->tampilSimpul(); //menampilkan data

                //bergerak ke simpul berikutnya
                pSkrg = pSkrg->pBrktnya;
            }
            cout << endl;
        }
}; //akhir kelas SenaraiBerantai

int main()
{
    SenaraiBerantai senaraiBerantai; //menciptakan senarai

    senaraiBerantai.sisipPertama(22, 2.99); //menyisipkan 4 item
    senaraiBerantai.sisipPertama(44, 4.99);
    senaraiBerantai.sisipPertama(66, 6.99);
    senaraiBerantai.sisipPertama(88, 8.99);
    senaraiBerantai.tampilSenarai(); //display list

    int cariKunci = 44; //mencari item
    Simpul* pCari = senaraiBerantai.cari(cariKunci);

    if( pCari != NULL)
        cout << "Ditemukan dengan kunci " << pCari->iData << endl;
    else
        cout << "Tidak menemukan simpul yang dicari" << endl;

    int hapusKunci = 66; //menghapus item

    bool hapusOK = senaraiBerantai.hapus(hapusKunci);

    if( hapusOK )
        cout << "Dihapus simpul dengan kunci " << hapusKunci << endl;
    else
        cout << "Tidak menemukan simpul yang ingin dihapus" << endl;
   
    senaraiBerantai.tampilSenarai(); //menampilkan senarai

    getch();
    return 0;
} //akhir main()

Senarai Berantai (pertama-->akhir): {88, 8.99} {66, 6.99} {44, 4.99} {22, 2.99}

Ditemukan dengan kunci 44
Dihapus simpul dengan kunci 66
Senarai Berantai (pertama-->akhir): {88, 8.99} {44, 4.99} {22, 2.99}

3.       Tulislah sebuah program C++ untuk merealisasikan tumpukan menggunakan senarai berantai.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//senaraiBerantaiTumpukan.cpp
//Mendemonstrasikan tumpukan
//yang diimplementasikan dengan senarai berantai
#include <iostream>
#include <conio.h>
using namespace std;

class Simpul
{
    public:
    double dData; //item data

    Simpul* pBrktnya; //simpul berikutnya dalam senarai

    Simpul(double dd) : dData(dd), pBrktnya(NULL)
    { } //konstruktor

    void tampilSimpul() //menampilkan simpul
    { cout << dData << " "; }
}; //akhir kelas Simpul

class SenaraiBerantai
{
    private:
        //pointer ke item pertama pada senarai
        Simpul* pPertama;

    public:
        SenaraiBerantai() : pPertama(NULL) //konstruktor
        { }

        ~SenaraiBerantai() //destruktor (menghapus simpul)
        {
            Simpul* pSkrg = pPertama; //berawal di awal senarai
            while(pSkrg != NULL) //sampai akhir senarai,
            {
                Simpul* pLama = pSkrg; //menyimpan simpul skrg
                pSkrg = pSkrg->pBrktnya; //berpindah ke simpul brktnya
                delete pLama;
            }
        }

        bool apaKosong() //true jika senarai kosong
        { return (pPertama==NULL); }

        void sisipPertama(double dd) //menyisipkan di awal senarai
        { //menciptakan simpul baru
            Simpul* pSimpulBaru = new Simpul(dd);
            pSimpulBaru->pBrktnya = pPertama;
            pPertama = pSimpulBaru;
        }

        double hapusPertama() //delete first item
        { //(diasumsikan senarai tak-kosong)
            Simpul* pTemp = pPertama;
            pPertama = pPertama->pBrktnya;
            double kunci = pTemp->dData;
            delete pTemp;
            return kunci;
        }

        void tampilSenarai() //menampilkan semua senarai
        {
            Simpul* pSkrg = pPertama; //di awal senarai
            while(pSkrg != NULL) //sampai akhir senarai,
            {
                pSkrg->tampilSimpul(); //menampilkan data
                pSkrg = pSkrg->pBrktnya; //ke simpul berikutnya
            }
            cout << endl;
        }
}; //akhir kelas SenaraiBerantai

class TumpukanSenarai
{
    private:
        SenaraiBerantai* pSenarai; //pointer ke senarai berantai
    public:
        TumpukanSenarai() //konstruktor
              //menciptakan senarai berantai
        { pSenarai = new SenaraiBerantai; }

        ~TumpukanSenarai() //destruktor
        { delete pSenarai; } //menghapus senarai berantai

        void push(double j) //menempatkan item ke atas tumpukan
        { pSenarai->sisipPertama(j); }

        double pop() //menghapus item dari atas tumpukan
        { return pSenarai->hapusPertama(); }

        bool apaKosong() //true jika tumpukan kosong
        { return ( pSenarai->apaKosong() ); }

              void tampilTumpukan()
        {
            cout << "Tumpukan (atas-->bawah): ";
            pSenarai->tampilSenarai();
        }
}; //akhir kelas TumpukanSenarai

int main()
{
    TumpukanSenarai tumpukan; //menciptakan tumpukan

    tumpukan.push(20); //menempatkan item ke atas tumpukan
    tumpukan.push(40);

    tumpukan.tampilTumpukan(); //menampilkan tumpukan (40, 20)

    tumpukan.push(60); //menempatkan item ke atas tumpukan
    tumpukan.push(80);

    tumpukan.tampilTumpukan(); //menampilkan tumpukan (80, 60, 40, 20,)

    tumpukan.pop(); //menghapus item dari atas tumpukan (80, 60)
    tumpukan.pop();

    tumpukan.tampilTumpukan(); //menampilkan tumpukan (40, 20)

    getch();
    return 0;
} //akhir main()

Tumpukan (atas-->bawah): 40 20
Tumpukan (atas-->bawah): 80 60 40 20
Tumpukan (atas-->bawah): 40 20

4.       Tulislah sebuah program C++ untuk merealisasikan senarai berantai ganda.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//senaraiBerantaiGanda.cpp
//Mendemonstrasikan senarai berantai ganda
#include <iostream>
#include <conio.h>
using namespace std;

class Simpul
{
    public:
        double dData; //item data

        //ptr ke simpul berikutnya dalam senarai
        Simpul* pBrktnya;
        Simpul(double d) : dData(d), pBrktnya(NULL) //konstruktor
        { }

        void tampilSimpul() //menampilkan simpul
        { cout << dData << " "; }
}; //akhir kelas Simpul

class SenaraiBerantaiGanda
{
    private:
        Simpul* pPertama; //ptr ke simpul pertama
        Simpul* pAkhir; //ptr ke simpul terakhir

    public:
        //konstruktor
        SenaraiBerantaiGanda() : pPertama(NULL), pAkhir(NULL)
        { }

        ~SenaraiBerantaiGanda() //destruktor
        { // (menghapus semua simpul)
            Simpul* pSkrg = pPertama; //di awal senarai

            while(pSkrg != NULL) //sampai akhir senarai,
            {
                Simpul* pTemp = pSkrg;
                pSkrg = pSkrg->pBrktnya;
                delete pTemp;
            }
        }

        bool apaKosong() //true jika tidak ada simpul
        { return pPertama==NULL; }

        void sisipPertama(double dd) //menyisipkan di depan senarai
        {
            //menciptakan simpul baru
            Simpul* pSimpulBaru = new Simpul(dd);
            if( apaKosong() ) //jika senarai kosong,
                pAkhir = pSimpulBaru;
           
            pSimpulBaru->pBrktnya = pPertama;
            pPertama = pSimpulBaru;
        }

        //menyisipkan di akhir senarai
        void sisipAkhir(double dd)
        {
            //menciptakan simpul baru
            Simpul* pSimpulBaru = new Simpul(dd);
            if( apaKosong() ) //jika senarai kosong,
                pPertama = pSimpulBaru;
            else
                pAkhir->pBrktnya = pSimpulBaru;

            pAkhir = pSimpulBaru;
        }

        void hapusPertama() //menghapus simpul pertama
        { //(diasumsikan tak-kosong)
            Simpul* pTemp = pPertama; //mengingat simpul pertama

            //jika hanya ada satu simpul
            if(pPertama->pBrktnya == NULL)
                pAkhir = NULL; //NULL <-- akhir

            pPertama = pPertama->pBrktnya;
            delete pTemp; //menghapus
        }

        void tampilSenarai()
        {
            cout << "Senarai (pertama-->akhir): ";
            Simpul* pSkrg = pPertama; //di awal senarai
            while(pSkrg != NULL) //sampai akhir senarai,
            {
                pSkrg->tampilSimpul(); //menampilkan data
                pSkrg = pSkrg->pBrktnya; //ke simpul brktnya
            }
            cout << endl;
        }
}; //akhir kelas SenaraiBerantaiGanda

int main()
{
    SenaraiBerantaiGanda senarai; //menciptakan senarai baru

    senarai.sisipPertama(22); //menyisipkan di depan
    senarai.sisipPertama(44);
    senarai.sisipPertama(66);

    senarai.sisipAkhir(11); //menyisipkan di belakang
    senarai.sisipAkhir(33);
    senarai.sisipAkhir(55);

    senarai.tampilSenarai(); //menampilkan senarai
    cout << "Menghapus dua item pertama" << endl;

    senarai.hapusPertama(); //menghapus dua item pertama
    senarai.hapusPertama();
    senarai.tampilSenarai(); //menampilkan kembali

    getch();
    return 0;
} //akhir main()

Senarai (pertama-->akhir): 66 44 22 11 33 55
Menghapus dua item pertama
Senarai (pertama-->akhir): 22 11 33 55

5.       Tulislah sebuah program C++ untuk menciptakan sebuah antrian dengan senarai berantai.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//senaraiBerantaiAntrian.cpp
//Mendemonstrasikan antrian
//yang diimplementasikan dengan senarai berantai
#include <iostream>
#include <conio.h>
using namespace std;

class Simpul
{
    public:
    double dData; //item data

    Simpul* pBrktnya; //simpul berikutnya dalam senarai

    Simpul(double dd) : dData(dd), pBrktnya(NULL)
    { } //konstruktor

    void tampilSimpul() //menampilkan simpul
    { cout << dData << " "; }
}; //akhir kelas Simpul

class SenaraiBerantaiGanda
{
    private:
        Simpul* pPertama; //ptr ke simpul pertama
        Simpul* pAkhir; //ptr ke simpul akhir

    public:
        //konstruktor
        SenaraiBerantaiGanda() : pPertama(NULL), pAkhir(NULL)
        { }

        ~SenaraiBerantaiGanda() //destruktor
        { // (menghapus semua simpul)
            Simpul* pSkrg = pPertama; //di awal senarai

            while(pSkrg != NULL) //sampai akhir senarai,
            {
                Simpul* pTemp = pSkrg;
                pSkrg = pSkrg->pBrktnya;
                delete pTemp;
            }
        }

        bool apaKosong() //true jika tidak ada simpul
        { return pPertama==NULL; }

        //menyisipkan di akhir senarai
        void sisipAkhir(double dd)
        {
            //menciptakan simpul baru
            Simpul* pSimpulBaru = new Simpul(dd);
            if( apaKosong() ) //jika kosong,
                pPertama = pSimpulBaru;
            else
                pAkhir->pBrktnya = pSimpulBaru;
            pAkhir = pSimpulBaru;
        }

        double hapusPertama() //menghapus simpul pertama
        { //(asumsi senarai tak-kosong)
            Simpul* pTemp = pPertama; //mengingat simpul pertama
            double temp = pPertama->dData;

            //jika hanya satu simpul
            if(pPertama->pBrktnya == NULL)               
                pAkhir = NULL;

            pPertama = pPertama->pBrktnya;
            delete pTemp;
            return temp;
        }

        void tampilSenarai()
        {
            Simpul* pSkrg = pPertama; //di awal senarai
            while(pSkrg != NULL) //sampai akhir senarai,
            {
                pSkrg->tampilSimpul(); //menampilkan data
                pSkrg = pSkrg->pBrktnya; //move to next Simpul
            }
            cout << endl;
        }
}; //akhir kelas SenaraiBerantaiGanda

class SenaraiAntrian
{
    private:
        SenaraiBerantaiGanda senarai;

    public:
        bool apaKosong() //true jika antrian kosong
        { return senarai.apaKosong(); }

        void sisip(double j) //menyisipkan di belakang antrian
        { senarai.sisipAkhir(j); }

        double hapus() //menghapus dari depan antrian
        { return senarai.hapusPertama(); }

        void tampilAntrian()
        {
            cout << "Antrian (depan-->belakang): ";
            senarai.tampilSenarai();
        }
}; //akhir kelas SenaraiAntrian

int main()
{
    SenaraiAntrian antrian; //menciptakan antrian

    antrian.sisip(20); //menyisipkan item
    antrian.sisip(40);

    antrian.tampilAntrian(); //menampilkan antrian (20, 40)

    antrian.sisip(60); //menyisipkan item
    antrian.sisip(80);

    antrian.tampilAntrian(); //menampilkan antrian (20, 40, 60, 80)
   
    cout << "Menghapus dua item" << endl;
    antrian.hapus(); //menghapus item (20, 40)
    antrian.hapus();

    antrian.tampilAntrian(); //menampilkan antrian (60, 80)

    getch();
    return 0;
} //akhir main()

Antrian (depan-->belakang): 20 40
Antrian (depan-->belakang): 20 40 60 80
Menghapus dua item
Antrian (depan-->belakang): 60 80

6.       Tulislah sebuah program C++ untuk menciptakan sebuah senarai berantai terurut.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//senaraiTerurut.cpp
//Mendemonstrasikan senarai terurut
#include <iostream>
#include <conio.h>
using namespace std;

class Simpul
{
    public:
        double dData; //item data
        Simpul* pBrktnya; //simpul berikutnya dalam senarai
        Simpul(double dd) : dData(dd), pBrktnya(NULL) //konstruktor
        { }

        void tampilSimpul() //menampilkan simpul
        { cout << dData << " "; }
}; //akhir kelas Simpul

class SenaraiTerurut
{
    private:
        Simpul* pPertama; //ptr ke simpul pertama
    public:
        SenaraiTerurut() : pPertama(NULL) //konstruktor
        { }

        ~SenaraiTerurut() //destruktor
        { // (menghapus simpul-simpul)
            Simpul* pSkrg = pPertama; //mulai di awal senarai
            while(pSkrg != NULL) //sampai akhir senarai,
            {
                Simpul* pLama = pSkrg; //menyimpan simpul sekarang
                pSkrg = pSkrg->pBrktnya; //ke simpul brktnya
                delete pLama;
            }
        }

        bool apaSekarang() //true jika tidak simpul
        { return (pPertama==NULL); }

        void sisip(double kunci) //menyisipkan secara berurutan
        {
            //menciptakan simpul baru
            Simpul* pSimpulBaru = new Simpul(kunci);
            Simpul* pSblmnya = NULL; //mulai di awal senarai
            Simpul* pSkrg = pPertama;

            //sampai akhir senarai,
            while(pSkrg != NULL && kunci > pSkrg->dData)
            { //atau kunci > sekarang,
                pSblmnya = pSkrg;
                pSkrg = pSkrg->pBrktnya; //ke item berikutnya
            }

            if(pSblmnya==NULL) //di awal senarai
                pPertama = pSimpulBaru;
            else //tidak di awal senarai
                pSblmnya->pBrktnya = pSimpulBaru;
                pSimpulBaru->pBrktnya = pSkrg;
        } //akhir sisip()

        void hapus() //menghapus simpul pertama
        { //(diasumsikan senarai tak-kosong)
            Simpul* pTemp = pPertama; //simpan simpul pertama
            pPertama = pPertama->pBrktnya;
            delete pTemp;
        }

        void tampilSenarai()
        {
            cout << "Senarai (pertama-->akhir): ";
            Simpul* pSkrg = pPertama;
            while(pSkrg != NULL)
            {
                pSkrg->tampilSimpul();
                pSkrg = pSkrg->pBrktnya;
            }
            cout << endl;
        }
}; //akhir kelas SenaraiTerurut

int main()
{
    SenaraiTerurut senaraiTerurut; //menciptakan senarai baru

    senaraiTerurut.sisip(20); //menyisipkan 2 item
    senaraiTerurut.sisip(40);

    senaraiTerurut.tampilSenarai(); //menampilkan senarai (20, 40)

    senaraiTerurut.sisip(10); //menyisipkan 3 item lagi
    senaraiTerurut.sisip(30);
    senaraiTerurut.sisip(50);

    //menampilkan senarai (10, 20, 30, 40, 50)
    senaraiTerurut.tampilSenarai();

    senaraiTerurut.hapus(); //menghapus elemen terkecil

    //menampilkan senarai (20, 30, 40, 50)
    senaraiTerurut.tampilSenarai();

    getch();
    return 0;
} //akhir main()

Senarai (pertama-->akhir): 20 40
Senarai (pertama-->akhir): 10 20 30 40 50
Senarai (pertama-->akhir): 20 30 40 50

7.       Tulislah sebuah program C++ yang merealisasikan pengurutan penyusutan dengan senarai berantai.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//senaraiPengurutanPenyisipan.cpp
//Mendemonstrasikan senarai berantai terurut untuk pengurutan
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <conio.h>
using namespace std;

class Simpul
{
    public:
        double dData; //item data
        Simpul* pBrktnya; //simpul berikutnya pada senarai

        //konstruktor
        Simpul(double dd) : dData(dd), pBrktnya(NULL)
        { }
}; //akhir kelas Simpul

class SenaraiTerurut
{
    private:
        Simpul* pPertama; //ptr ke item pertama pada senarai

    public:
        //konstruktor tanpa-argumen
        SenaraiTerurut() : pPertama(NULL)
        { } //menginisialisasi senarai

        //konstruktor
        SenaraiTerurut(Simpul** arrSimpul, int panjang) : pPertama(NULL)
        { //(diinisialisasi dengan array)
            for(int j=0; j<panjang; j++) //menyalin array
                sisip( arrSimpul[j] ); //ke senarai
        }

        void sisip(Simpul* pArg) //menyisipkan scr berurutan
        {
            Simpul* pSblmnya = NULL; //di awal senarai
            Simpul* pSkrg = pPertama;

            //sampai akhir senarai,
            while(pSkrg != NULL && pArg->dData > pSkrg->dData)
            { //atau kunci > simpul skrg,
                pSblmnya = pSkrg;
                pSkrg = pSkrg->pBrktnya; //ke item brktnya
            }

            if(pSblmnya==NULL) //di awal senarai
                pPertama = pArg; //pertama --> k
            else //tidak di awal senarai
                pSblmnya->pBrktnya = pArg;
                pArg->pBrktnya = pSkrg;
        } //akhir sisip()

        Simpul* hapus() //menghasilkan dan menghapus simpul pertama
        { //(asumsi senarai tak-kosong)
            Simpul* pTemp = pPertama;
            pPertama = pPertama->pBrktnya;
            return pTemp; //menghasilkan nilai
        }
}; //akhir kelas SenaraiTerurut

int main()
{
    int j;
    time_t watkuA; //tunas bilangan acak
    srand(static_cast<unsigned>(time(&watkuA)) );

    const int ukuran = 10; //ukuran array
       //array yang memuat
    Simpul* arraySenarai[ukuran];

    //mengisi dengan pointer-pointer ke simpul-simpul
    for(j=0; j<ukuran; j++)
    {
        int n = rand() % 99; //angka acak (0 sampai 99)
        Simpul* pSimpulBaru = new Simpul(n); //menciptakan Simpul
        //menempatkan ptr ke Simpul dalam array
        arraySenarai[j] = pSimpulBaru;
    }

    cout << "Array tak-terurut: "; //menampilkan isi array
    for(j=0; j<ukuran; j++)
        cout << arraySenarai[j]->dData << " ";
    cout << endl;

    //menciptakan senarai baru
    //diinisialisasi dengan array
    SenaraiTerurut senaraiTerurut(arraySenarai, ukuran);

    for(j=0; j<ukuran; j++)
        arraySenarai[j] = senaraiTerurut.hapus();

    cout << "Array terurut: "; //menampilkan isi array
    for(j=0; j<ukuran; j++)
        cout << arraySenarai[j]->dData << " ";
    cout << endl;

    for(j=0; j<ukuran; j++) //menghapus simpul-simpul
        delete arraySenarai[j];

    getch();
    return 0;
} //akhir main()

Array tak-terurut: 41 18 60 18 29 75 57 28 93 14
Array terurut: 14 18 18 28 29 41 57 60 75 93

8.       Tulislah sebuah program C++ untuk merealisasikan senarai berantai ganda.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
//senaraiBerantaiGandaLengkap.cpp
//Mendemonstrasikan senarai berantai ganda
#include <iostream>
#include <conio.h>
using namespace std;

class Simpul
{
    public:
        double dData; //item data
        Simpul* pBrktnya; //simpul berikutnya pada senarai
        Simpul* pSblmnya; //simpul sbmnya pada senarai

    public:
        Simpul(double dd) : //konstruktor
        dData(dd), pBrktnya(NULL), pSblmnya(NULL)
        { }

        void tampilSenarai() //menampilkan simpull
        { cout << dData << " "; }
}; //akhir kelas Simpul

class SenaraiBerantaiGanda
{
    private:
        Simpul* pPertama; //pointer ke item pertama
        Simpul* pAkhir; //pointer ke item terakhir

    public:
        SenaraiBerantaiGanda() : //konstruktor
        pPertama(NULL), pAkhir(NULL)
        { }

        ~SenaraiBerantaiGanda() //destruktor (menghapus simpul)
        {
            Simpul* pSkrg = pPertama; //mulai diawal senarai
            while(pSkrg != NULL) //sampai akhir senarai,
            {
                Simpul* pLama = pSkrg;
                pSkrg = pSkrg->pBrktnya;
                delete pLama;
            }
        }

        bool apaKosong() //true jika tidak ada simpul
        { return pPertama==NULL; }

        //menyisipkan di awal senarai
        void sisipPertama(double dd)
        {
            //menciptakan simpul baru
            Simpul* pSimpulBaru = new Simpul(dd);           
            if( apaKosong() ) //jika senarai kosong,
                pAkhir = pSimpulBaru;
            else
                pPertama->pSblmnya = pSimpulBaru;
                pSimpulBaru->pBrktnya = pPertama;
                pPertama = pSimpulBaru;
        }

        void sisipAkhir(double dd) //menyisipkan di akhir senarai
        {
            //menciptakan simpul baru
            Simpul* pSimpulBaru = new Simpul(dd);           
            if( apaKosong() )
                pPertama = pSimpulBaru;
            else
            {
                pAkhir->pBrktnya = pSimpulBaru;
                pSimpulBaru->pSblmnya = pAkhir;
            }
            pAkhir = pSimpulBaru;
        }

        void hapusPertama()
        { //(asumsi senarai-kosong)
            Simpul* pTemp = pPertama;
            if(pPertama->pBrktnya == NULL)
                pAkhir = NULL;
            else
                pPertama->pBrktnya->pSblmnya = NULL;
                pPertama = pPertama->pBrktnya;
            delete pTemp;
        }

        void hapusAkhir()
        { //(asumsi senarai-kosong)
            Simpul* pTemp = pAkhir;
            if(pPertama->pBrktnya == NULL)
                pPertama = NULL;
            else
                pAkhir->pSblmnya->pBrktnya = NULL;
            pAkhir = pAkhir->pSblmnya;
            delete pTemp;
        }

        //menyisipkan tepat setelah kunci
        bool sisipSetelah(double kunci, double dd)
        { //(asumsi senarai-kosong)
            Simpul* pSkrg = pPertama;
            while(pSkrg->dData != kunci)
            {
                pSkrg = pSkrg->pBrktnya;
                if(pSkrg == NULL)
                    return false;
            }

            Simpul* pSimpulBaru = new Simpul(dd);

            if(pSkrg==pAkhir)
            {
                pSimpulBaru->pBrktnya = NULL;
                pAkhir = pSimpulBaru;
            }

            else
            {
                pSimpulBaru->pBrktnya = pSkrg->pBrktnya;
                pSkrg->pBrktnya->pSblmnya = pSimpulBaru;
            }

            pSimpulBaru->pSblmnya = pSkrg;
            pSkrg->pBrktnya = pSimpulBaru;
            return true;
        }

        bool hapusKunci(double kunci)
        { //(asumsi senarai-kosong)
            Simpul* pSkrg = pPertama;
            while(pSkrg->dData != kunci)
            {
                pSkrg = pSkrg->pBrktnya;
                if(pSkrg == NULL)
                    return false;
            }

            if(pSkrg==pPertama)
                pPertama = pSkrg->pBrktnya;
            else
                pSkrg->pSblmnya->pBrktnya = pSkrg->pBrktnya;

            if(pSkrg==pAkhir)
                pAkhir = pSkrg->pSblmnya;
            else
                pSkrg->pBrktnya->pSblmnya = pSkrg->pSblmnya;
           
            delete pSkrg;
            return true;
        }

        void tampilMaju()
        {
            cout << "Senarai (pertama-->akhir): ";
            Simpul* pSkrg = pPertama;
            while(pSkrg != NULL)
            {
                pSkrg->tampilSenarai();
                pSkrg = pSkrg->pBrktnya;
            }
            cout << endl;
        }

        void tampilMundur()
        {
            cout << "Senarai (akhir-->pertama): ";
            Simpul* pSkrg = pAkhir;
            while(pSkrg != NULL)
            {
                pSkrg->tampilSenarai();
                pSkrg = pSkrg->pSblmnya;
            }
            cout << endl;
        }
}; //akhir kelas SenaraiBerantaiGanda

int main()
{
    SenaraiBerantaiGanda senarai; //menciptakan senarai baru

    senarai.sisipPertama(22); //menyisipkan di depan
    senarai.sisipPertama(44);
    senarai.sisipPertama(66);

    senarai.sisipAkhir(11); //menyisipkan di belakang
    senarai.sisipAkhir(33);
    senarai.sisipAkhir(55);

    senarai.tampilMaju(); //menampilkan senarai secara maju
    senarai.tampilMundur(); //menampilkan senarai secara mundur

    cout << "Menghapus simpul pertama, simpul akhir, dan 11" << endl;
    senarai.hapusPertama();
    senarai.hapusAkhir();
    senarai.hapusKunci(11);

    senarai.tampilMaju(); //menampilkan senarai secara maju
   
    cout << "Menyisipkan 77 setelah simpul 22, dan 88 setelah 33" << endl;
    senarai.sisipSetelah(22, 77);
    senarai.sisipSetelah(33, 88);
    senarai.tampilMaju(); //menampilkan senarai secara maju

    getch();
    return 0;
} //akhir main()

Senarai (pertama-->akhir): 66 44 22 11 33 55
Senarai (akhir-->pertama): 55 33 11 22 44 66
Menghapus simpul pertama, simpul akhir, dan 11
Senarai (pertama-->akhir): 44 22 33
Menyisipkan 77 setelah simpul 22, dan 88 setelah 33
Senarai (pertama-->akhir): 44 22 77 33 88









Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)