មេរៀនទី១១: Data Structures

មេរៀនទី១១: Data Structures
C C++
I. Say about pointer again : 
pointer ជា variable ផ្ទុក Address (មិនមែនផ្ទុកតំលៃទេ) ដូច្នេះ  *p ជាទិន្នន័យដែលផ្ទុកក្នុង Address p.   ឬនិយាយ ម្យ៉ាងទៀត p ជា pointer point to variable ដែលផ្ទុក value *p  ។
II.  Dynamic variable: បណ្ដា variable  មានប្រភេទទិន្នន័យ, ដែលយើងធ្លាប់សិក្សាកន្លងមកដូចជា Array, int, float …

ហៅថា static  variable  ព្រោះវាត្រូវបានកំណត់និយមន័យជាស្រាច់មុនពេល Declaration  variable  ។ រយៈពេលកកើត static variable គឺជារយៈពេលនៃ ការកកើតនូវកំណាត់កមμវិធីដែលផ្ទុកវាដែរ ។ តែបណ្ដា Variable ក៏អាចត្រូវបានក៏កើតដោយរបៀប dynamic .  មានន័យថា កកើត ឡើងនៅពេលយើង Run កមμវិធី ។ ដូច្នេះ Variable នេះមិន ត្រូវ បានកំណត់និយមន័យជាមុនទេ ។ Variable ប្រភេទនេះហៅថា Dynamic variable  ។

Dynamic  variable  គμានឈេμាះទេ  (ព្រោះការដាក់ឈោμ ះការពិត  គឺការតាងអោយវានូវ Address កំណត់មួយ)   ។  ការបង្កើត Dynamic variable និងលុបវាទៅវិញ ត្រូវអនុវត្ដន៍ដោយផ្នែកបណ្ដា function ដូចជា malloc ( ) និង free ( ) ដែលមានស្រាប់ក្នុង Library  <stdlib.h>  ។  ការ Access ជាមួយ

Dynamic variable ត្រូវអនុវត្ដន៍ដោយផ្អែកបណ្ដា Variable ប្រភេទ pointer (Pointer Variable ) ។ បណ្ដា pointer Variable ត្រូវ កំណត់ ទិន្នន័យ ដូចជា Static Variable ដែរ ។ (មានន័យយថា មានឈេμាះ និងត្រូវ  Declaration  ភ្លាមនៅផ្នែកខាងដើមក្នុងផ្នែក Declaration  Variable  និងត្រូវបានប្រើដើម្បីផ្ទកុ Address របស់បណ្ដា Dynamic Variable ) ។Ex1:  Declaration pointer និងបង្កើត Dynamic Variable:

int *pNumber;    /*Declaration pointer variable*/

pNumber = (int*) malloc (100) ; /*Create Dynamic Variable*/ កំណាត់កមμវិធីខាងលើផ្ដល់អោយយើង  100 bytes ក្នុង memory និងតាង Address of memory នេះទៅអោយ pNumber   .   100 bytes នេះប្រើសំរាប់ផ្ទុក 5០ ចំនួនគត់។                                           បើចង់ បាន memory

អោយត្រឹមត្រូវសំរាប់ 75 ចំនួនគត់, យើងសរសេរដូចខាងក្រោម ៖

int *pNumber;

pNumber = (int*) malloc (75*sizeof (int));

ដូចគ្នាចំពោះបណ្ដាការ Declaration ផ្សេង, យើងសរសេរ ៖

char  *cPtr;
cPtr  = (char *) malloc (l50*sizeof (char));

float *fPtr;

fPtr =  (float*)  malloc (55*sizeof (float));

យើងនិងសិក្សាឧទាហរណ៍ស្ដីអំពិី malloc function ដូចខាងក្រោម ៖

Ex2: ប្រើ Function malloc (memory allocaion)

# include <stdio.h>

# include <conio.h>

# include <string.h>

# include <alloc.h>

# include <process.h>

int main (void)

{    char *str ;    /*allocate memry for string*/

if ((str = ( char *) malloc (10) = = NULL)

{    printf (“\n there isn’t enough memory”)

exit (1);

}

/* copy “Hello” into string */

strcpy (str, “Hello”);

/* free memory */

free (str);
return 0;

}

Note:  ក្នុងឧទាហរណ៍ខាងលើ, យើងបាន Declaration pointer string str ។ បន្ទាប់មកកំណាត់កមμវិធី

if ((str = (char*) malloc (10) = = NULL)

{    printf (“\n there isn’t enough memory”);

exit (1);

}

និងរៀបចំ dynamic  memory  សំរាប់  10  chapters និងក្នុង ដំណាក់ កាលនេះមានការត្រួតពិនិត្យមើល computer មាន memory គ្រប់ គ្រាន់ ឬអត់ ? ដោយរបៀបត្រួតពិនិត្យមើល លទ្ឋផល pointer str មានតំលៃជា NULL ឬអត់ ?

យើងអាចប្រើ function farmalloc ដើម្បីផ្ដល់នូវ memory ធំជាង malloc ។

Function exit (1) យកចេញពី file < process.h> Statement (char *) malloc (10)

យើងយល់ថា  រៀបចំផ្ដល់  dynamic  memory  ប្រភេទ  char  និង  លទ្ឋផលរបស់វាជា  Address តំបូងរបស់  memory  .  Function  នេះអនុវត្ដន៍ចំពោះប្រភេតទិន្នន័យ ៖  int,  float,  long,  char, double ….
C C++លទ្ឋផលរបស់ statement នេះជានិច្ចជាកាល ជា address មួយ  និងជា Address ដំបូងរបស់ memory ដែលត្រូវផ្ដល់, ក្នុងនោះ data type ជាទិន្នន័យ ។

 Syntax: (datatype*)

ជាប្រភេទ  pointer  ។  ឧទាហរណ៍    (float)  n  មានន័យថា  convert  n  អោយទៅជាចំនួនពិត  ។ (datatype *) convert ជាប្រភេទ pointer point to datatype ។ ដូច្នេះយើងអាចសរសេរដូចខាងក្រោម ៖
pointer malloc(sizeof(memory))

 ក្នុងការណ៍ចង់បង្កើត  Dynamic  memory  អោយប្រភេទទិន្នន័យ  មិនមែនជា  int,  float,  long, double, ពោលគឹប្រភេទ ទីន្នន័យដែលយើងជាអ្នកបង្កើត, យើងត្រូវប្រើ function calloc ( ) .
Syntax:
(datatype*) calloc (n, sizeof (object));

Ex:

struct   persont  {

char name[80];

int age;

char Address[25];

};

struct person *ptr; /*  Declaration  pointer  person  */   ហើយយើងបង្កើត memory

សំរាប់អោយ 10 នាក់ ដូចខាងក្រោម ៖
calloc (10, sizeof (struct  person));

 Ex3:   ប្រើ Function calloc អោយ string :

# include <stdio.h>

# include <alloc.h>

# include <string.h>

int main (void)

{    char *str = NULL ;

/* allocate memory for string */

str = (char *) calloc (10, sizeof (char));

/* copy “Hello” into string */

strcpy (str, “Hello”);

/* display string */

printf (“\n String is %s \n”str);

 

/* free memory */

free (str);

return 0;

}

Function realloc ( ) ជា function បង្កើតឡើងវិញនូវ memory :
(datatype *) realloc (buf_ptr, newsize);

ក្នុងនោះ buf_ptr ជា pointer កំពុង point to memory ដែលត្រូវ បានបង្កើត ផ្ដល់អោយពីលើកមុន។ newsize ជាទំហំថμី ដែលត្រូវ បង្កើត និងផ្ដល់ អាចធំជាង ឬតូចជាងមុន ។

Ex4:

# include <stdio.h>
# include <conio.h>
# include <string.h>

int main (void)

{      char  *str ;

/* allocate memory for string */

str = (char *) malloc (10);

strcpy (str, “Hello”);

printf (“ \n string %s \n Address %p \n”, str, str);

str = (char*) realloc (str,20);

printf (\n string %s \n New Address %p \n”str, str);

free (str);

return 0;

}

III. Heap memory និងរបៀបបង្កើត  Dynamic variable :

បណ្ដា dynamic variable ដែលបង្កើតឡើងដោយ malloc ត្រូវបាន C រៀបទៅក្នុង Block free memory ហៅថា HEAP  ។ ភាសា C គ្រប់ គ្រង Heap តាមរយៈ pointer of Heap គឺ HeapPtr  ។ pointer of Heap ជានិច្ចជាកាល point to bype free ដំបូងរបស់ Block free memory របស់ Heap ។ រាល់ពេល call malloc ( ), pointer  of Heap ត្រូវបាន ផ្លាស់ទីតាំងផ្នែកខាងលើនៃ block free memory បណ្ដា byte មួយចំនួនសមមូល នឹងទំហំរបស់ dynamic variable ដែលទើប បង្កើត បាន។ ចំពោះអ្នកសរសេរកមμវិធី, Heap គឺជាមូកដ្ឋានគ្រឹះដែល ត្រូវក្ដាប់អោយបាន ។

C C++Ex5:  រកចំនួន prime

 # include <stdio.h>

# include <conio.h>

main ( )

{long  *primes = NULL,  *start = NULL,  *open = NULL, trial = 0;

int  i = 0, found = 0; total = 0;

 printf (“\n How many primes :”); scanf (“%d”, &total);

primes = (long*) malloc (total*sizeof (long));

if (primes = = NULL)

{printf (“\n there isn’t enough memory !!”);

return 0;

}

/*  3 primes តំបូងដែលយើងដឹង */

*primes = 2;

*(primes+1) = 3;

*(primes+2) = 5;

open = primes + 3;  /* យក Address free បន្ដរបន្ទាប់ទៀត */

trial = 5;

do  {      trial + =2;  /* យកតំៃ់បន្ដបន្ទាប់ទៀតដើម្បីត្រួតពិនិត្យ */

start = primes;  /* start point to ផ្នែកដំបូងរបស់prime */

found = 0;

for (i = 0; i < open-primes;  i++)

if (found = (trial % *start ++) = = 0) break;

if (found = = 0)  /* រកឃើញចំនួនថμី */

*open ++ = trial;

}      while (open – primes < = total);

for (i = 0; i <5 *(total /5); i+ = 5) /*display 5 លេខម្ដង */

printf (“\n%12ld %12ld %12ld %12ld %12ld”,  *(primes + i),

* (primes +i + 1), *(primes + i +2), *(primes +i +3),

*(primes +i + 4));
printf (“\n”);

for (i = total – (total%5);  i < total; i++ )

printf (“%12d”, (primes +i ));   /*display ផ្នែកនៅសល់ */

}

The Result is

C C++IV.  Linked List : ពេលយើងចង់បង្កើត List មួយ, ឧទាហរណ៍ List of Employee, ហើយយើងដឹងចំនួន មនុស្សពិតប្រាកដ នោះយើងអាច ប្រើ Array of struct ដើម្បីបង្កើត ព្រោះវាមានលក្ខណៈងាយស្រួល ។ តែបើយើងមិនស្គាល់ចំនួនមនុស្សជាមុននោះ យើងគប្បីប្រើ Dynamic Variable, ព្រោះវាមានលកμ្ខណៈ ក្នុងការសន្សំសំចៃ memory  (ពេល ណាយើងត្រូវការទើបយើងបង្កើតវាមកប្រើ) ។ Memory ប្រើ សំរាប់ static Variable ទាំងអស់ក្នុង computer  IBM_PC គឺមានតែ 64KB ពោលគឺមួយ Segment ។

 a/   Create a Linked List: ចូរសរសេរកមμវិធីបង្កើត Linked List នៃ employee មួយ

Ex:

# include <stdio.h>

# include <conio.h>

# include <alloc.h>

struct employee  { char name[30];

int  age;

struct employee  *next;

};

main ( )

{    struct employee  *last; struct employee  *ptr; char name[30];

last = NULL;

/*  Read form Keyboard to List */

do  {  printf (“\n name :”); gets (name);

if (name[0] != ‘\0’)

{ ptr = calloc  (1, sizeof (struct employee ));

/*Read Value of employee */

strcpy (ptrÆname, name); /*ptrÆname = name */

printf (“\n Age :”);  scanf (“%d”, &ptrÆage);

while (getchar ( ) != ‘\n’);

ptrÆnext = last;

last = ptr;

}

}  while (name[0] != ‘\0’);

/*  control and read again to list */ printf (“\n\n List of Employee :”); ptr = last;

while (ptr != NULL )

{ printf (“Name : %s \n”, ptrÆname);

printf (“Age : %d \n\n”, ptrÆage);

ptr = ptrÆnext;   /* ptr point to next record */

} getch ( ); return 0;

}

Explain:  ឧបមាយើង Read បញ្ចូលតាមលំដាប់ ៖ Mr one, 1 age, Mr two, 2 age…

last គឹជា pointer Variable, ជានិច្ចជាកាល point to last of list ។   ពេលចាប់ផ្ដើម Run program គឺយើងតាង

 last = NULL មានន័យថា List Empty ។
C C++C C++Loop ទី២ៈ ptr = calloc (1, sizeof (struct employye));

strcpy (ptrÆname, name);

printf (“Age :”), scanf (“%d”, &ptrÆage);

while (getchar ( ) != ‘\n’);
C C++ptr Æ next = last;

last = ptr;

C C++Linked   List ដូចខាងលើហៅថា  LIFO  (Last  In,  First Out)     ហៅថា  Stack(ចូលមុនចេញក្រោយ, ចូលក្រោយចេញមុន) ។
Name : MrOne
Age   : 1

Name: Mr two

Age  : 2

List of Employee: Name : Mr Two

Age    :  2

Name : Mr One

Age    : 1

b/   Insert : ពេលនេះយើងចង់ថែមធាតុថμីទី៣  (Mr Three, Age 3) ទៅកណ្ដាលធាតុពីមុនៈ (ឧបមាថាយើងប្រើ last ជៅ pointer point to last of list ដូចខាងលើ )

struct employee  *Q;

Q = calloc (1, sizeof (struct employee));

strcpy (QÆname, “Three”); QÆAge = 3;

/* find position to insert */

ptr = last;

while ((ptr != NULL) && (strcmp (ptrÆname, “Mr Two”)))

ptr = ptrÆnext;

QÆnext = ptrÆnext;

ptrÆnext = Q;

C C++c/   Function Create List : ក្នុង  ផ្នែកខាងលើ,  យើងបានបង្កើត  Linked   List  ដូចក្នុងឧទាហរណ៍,  យើងចង់  updat វាថែម ទៀត ដោយ ប្រើ Function create List :

 Void create_list (struct people  ** first);

ក្នុងនោះយើងប្រើ first ជៅ pointer point to pointer point to ធាតុ មួយ របស់ list   ។ មានន័យថាយើងថែមធាតុថμី  (New record) មួយទៅក្នុង list របស់យើងត្រង់ទីតាំងដែល pointer first មុននេះ កំពុង point to នោះ ។

Ex7:  Function create list :

# include <stdio.h>

# include <conio.h>

# include <stdlib.h>

# include <alloc.h>

struct person    {char name[30];

int age;

struct person *next;

};

void create_list (struct person **first);

main ( )

{struct person  *last;

create_list (&last);

printf (“\n\n List of Employee : \n”);

ptr = last;

while (ptr!= NULL)

{printf (“Name :%s \n”, ptrÆname);

printf (“age :%d \n\n”, ptrÆage);

ptr = ptrÆnext;   /* ptr point to next record */

}

getch ( );

return 0;

 }

void create_list (struct person  **alast)

 {    struct person  *ptr;

 char name[30];

*alast = NULL;

do  {printf (“\n Name :”); gets(name);

 if (name[0]; != ‘\0’)

 { ptr = colloc (1, sizeof(struct person));

strcpy (ptrÆname, name);

printf (“Age :”);

scanf (“%d”, &ptrÆage); while (getchar ( ) != ‘\n’); ptr Æ next =  *alast;

*alast = ptr;

}

}

while (name[0] != ‘\0’);

}

 d/  Delete :

ផ្ទុយពី insert, ពោលគឺលុបមួយ Record ចេញពី List, ។    ឧទាហរណ៍ ចង់លុប record ដែលមានឈេμាះ Tree ចេញពី list ពេលនោះ យើងត្រូវ ប្រើ Q ក្នុងពេលរក Record ដែលមានឈេμាះ Three ។ ពេលរកឃើញហើយយើងលុបវាចេញ ដោយរបៀប ពីរយ៉ាងខុសគ្នា ។

Struct  person *Q, *P;

/*  Search record for delete */ P = last; name = “three”;

while ((P != NULL ) && (strcmp (PÆname, name )))

{    Q = P;

P = PÆnext ;

 }

/* delete */

if ( P == last ) last = PÆnext;

else QÆnext = PÆnext;

 e/  Parameter is a pointer dynamic :

dynamic Variable អាចប្រើជា Parameter  របស់ subprogram បាន, ឧទាហរណ៍ យើងសរសេរ Function Insert  ដូចខាងក្រោមៈ

void insert (person  * Q);

{ …

} ;

យើងអាចសរសេរ Function មួយដែលមានលទ្ឋផលជា pointer ។

* person TT (peron *last);

{    struct person  *p1,  *p2;

p1 = last;

last = NULL;

do  { p2 = p1Ænext; p1Ænext = last; last = p1;

p1 = p2;

} while (p1 == NULL );

return last;

};

+  មុនពេលហៅ Q = TT (last);

C C+++  ក្រោយពីហៅ Q = TT (last); Q

C C++f/ ប្រភេទទិន្នន័យ FIFO :FIFO (First In First Out) ជាប្រភេទ Memory ដែលទិន្នន័យណាចូលមុន ចេញមុន ចូលក្រោយ ចេញក្រោយ។

 Ex8:

# include <stdio.h>

# include <conio.h>

# include <alloc.h>

# include <stdlib.h>

struct  person  {char name[30];

int age;

struct  person  *next;

 }  people;

 main ( )

{    struct person  *last, *first, *ptr;

char name[30];

first = NULL;

do  {prinf (“\n Name :”); gets (name);

if (strcmp (name, “”))         /* create new record */

{ptr = colloc (1, sizeof (struct person));

strcpy (ptr Æ name, name );

printf (“Age : “);  scanf (“%d”, &ptr Æ age);

ptr Æ next = NULL;

if (first != NULL)  last Æ next = ptr;

else first = ptr;

last = ptr;

while (getchar ( ) != ‘\n’);

};

} while (name[0] != ‘\0’);

C C++

/* Record FIFO again */

ptr = first;

while (ptr != NULL)

{printf (“%s\n”, ptr Æ name);

printf (“%d\n”, ptr Æ age);

ptr = ptr Æ next;

};

}

 

សំនួរ

 1.    ឧបមាមាន x និង y មានប្រភេទជា pointer ដូចគ្នា ។ សួរថា ប្រមាណវិធីខាងក្រោម ៖

x = y ;

និង *x = *y ;

តើសមមូលនឹងគ្នាឬអត ់ ? (ចូរពន្យល ់) ?

2.     អធិប្បាយសកមμភាពរបស ់  FIFO  ដោយគូសកំនូសបំព្រួញជាមួយ  Algorithm  delete  និង

insert ។

3.     ចូរ print Address របស់ Variable ណាមួយមកលើ screen ។

4.     សរសេរកមμវិធីអធិប្បាយពីការបង្កើត Linked list

5.     ចូរពិនិត្យកមμវិធីខាងក្រោមមានកំហុសអ្វីខ្លះ ? ចូរកែកំហុស ?

struct   Myrecord { int  Num; Myrecord *next;

};

 struct   Myrecord  *Head, * Tail, *T;

{    /* ឧបមាយើងបានបង្កើត linked list 20 node, ដែល Head និង Tail point to node

ដំបូងនិង node ចុងក្រោយ ។ យើងត្រូវលុប node ទាំងអស់ក្នុងពេលតែមួយ */
T = Head;

while (T != NULL)

{Dsiplose (Head);

Head = Head Æ Next; T = Head;

};

Head NULL; Tail NULL; T NULL;

}