CBDS2103 - struktur data - contoh jawapan kepada latihan dalam buku modul (UNIT 3)

CBDS2103 - struktur data - contoh jawapan kepada latihan dalam buku modul - unit 3 (bab 8-10)

perhatian:
1 jangan terus salin jawapan; cuba buat sendiri dahulu soalan latihan tersebut sebelum melihat kepada jawapan.
2 tidak semua latihan saya sempat cari jawapannya
3 jawapan ini hanyalah untuk pelajar di bawah tutoran saya sahaja
4 walaupun usaha sebaik mungkin telah diambil untuk memastikan jawapan adalah tepat, tidak ada jaminan semua
jawapan adalah semestinya tepat

latihan 8.1
Nota: ini adalah isihan pilihan mudah, sama dengan aturcara seperti di ms 100. Untuk langkah demi langkah, sila lihat contoh di rajah 8.4 (ms 99)

latihan 9.1
tidak, sebab ia akan mencari indeks yang terkecil. Ia memerlukan tatasusunan yang telah diisih terlebih dahulu.

latihan 9.2
1 tidak boleh
2 perlu isih senarai tersebut terlebih dahulu

latihan 9.3
1 rujuk ms 113
2 (a) isih terlebih dahulu
(b) gelintar seperti di ms 113

latihan 10.1
soalan 1
3
/ 1 4
\ 2 5
6

soalan 2
5
/ 1 6
3
/ 2 4

soalan 3
bentuk pokok yang terhasil adalah bergantung kepada turutan data diselitkan, bukannya set data. Set data yang sama tidak akan menjamin bahawa bentuk PGD yang dihasilkan akan sama.


latihan 10.2
fungsi ini boleh didapati dari laman web berikut: http://www.stanford.edu/~blp/avl/libavl.html/BST_item_deletion_function.c.txt
sila dapatkan penerangan lanjut dari laman web berikut: http://www.stanford.edu/~blp/avl/libavl.html/Deleting-from-a-BST.html
nota: laman web yg dinyatakan di ms 130 tidak berfungsi lagi kerana ia telah digantikan dengan yg tersebut di atas.

soalan tutorial 1 (ms 131)
jawapan adalah hampir sama dengan aturcara di ms 129, cuma bezanya adalah bil data:30 (bukan 10) dan buang fungsi postorder dan preorder.

soalan tutorial 2
rujuk ms 99

contoh aturcara
[dibuat kerana kadangkala ada kesilapan pada aturcara yang tertera pada nota modul, dan aturcara pada nota modul itu tidak lengkap - saya taipkan ini semula untuk membantu pelajar. Sila kompil dan larikan.]

contoh aplikasi isihan (ms 109)
#include
#define bil 5

void bacaData(int x[],int n);
void selectSort(int x[],int n);

void main() {
int i;
int data[bil];
int pilihan;

printf("baca data: \n");
bacaData(data,bil);

printf("isih pilihan\n");
selectSort(data,bil);
for (i=0;i0;i--) {
indx=0;
large=x[0];
printf("1 x[0] is currently %d\n",x[0]);
printf("1 indx is currently %d\n",indx);
printf("1 i is currently %d\n",i);
for (j=1;j<=i;j++) if (x[j]>large) {
large=x[j];
indx=j;
}
x[indx]=x[i];
x[i]=large;
printf("2 x[0] is currently %d\n",x[0]);
printf("2 indx is currently %d\n",indx);
printf("2 i,x[indx],x[i] is currently %d,%d,%d\n",i,x[indx],x[i]);
}
}

contoh aturcara gelintar (ms 116)
#include

int gelintarJujukan(int list[],int lastIndx,int target);

void main() {
int i,data[12];
int nom,jumpa;

for (i=0;i<12;i++) jumpa="gelintarJujukan(data,i,nom);" indx="0;indx<="lastIndx;indx++)" target="="list[indx])">
#include

typedef struct PokokDedua {
int data;
struct PokokDedua *anak_kiri;
struct PokokDedua *anak_kanan;
} POKOK_DEDUA;
typedef POKOK_DEDUA PGD;

void ciptaPGD(PGD **pokok);
void selitPGD(PGD **p2, int Item);
PGD *nodBaruPGD(int item);
void inOrder(PGD *j);
void postOrder(PGD *j);
void preOrder(PGD *j);

void main() {
int a, data;
PGD *pgd;
ciptaPGD(&pgd);

for (a=1;a<=10;a++) { printf("Masukkan satu nombor:"); scanf("%d",&data); selitPGD(&pgd,data); } printf("Penjelajahan dalam-tertib: "); inOrder(pgd); printf("\nPenjelajahan pasca-tertib: "); postOrder(pgd); printf("\nPenjelajahan pra-tertib: "); preOrder(pgd); } void ciptaPGD(PGD **pokok) { *pokok=NULL; } void selitPGD(PGD **p2, int item) { PGD *t,*b; t=*p2; b=NULL; while ((t) && (item!=t->data)) {
b=t;
if (itemdata)
t=t->anak_kiri;
else
t=t->anak_kanan;
}

if (t!=NULL)
printf("\nRalat: data telah wujud");
else {
t=nodBaruPGD(item);
if (b==NULL)
*p2=t;
else {
if (itemdata)
b->anak_kiri=t;
else
b->anak_kanan=t;
}
}
}

PGD *nodBaruPGD(int item) {
PGD *p=NULL;
p=(PGD*) malloc (sizeof(PGD));
if (p==NULL)
printf("ralat");
else {
p->data=item;
p->anak_kiri=NULL;
p->anak_kanan=NULL;
}
return p;
}

void inOrder(PGD *j) {
if (j) {
inOrder(j->anak_kiri);
printf("%d ",j->data);
inOrder(j->anak_kanan);
}
}

void postOrder(PGD *j) {
if (j) {
postOrder(j->anak_kiri);
postOrder(j->anak_kanan);
printf("%d ",j->data);
}
}

void preOrder(PGD *j) {
if (j) {
printf("%d ",j->data);
preOrder(j->anak_kiri);
preOrder(j->anak_kanan);
}
}