ể ữ ệ ể ữ ệ

Các ki u d li u Các ki u d li u nâng cao - nâng cao - ắ ế S p x p S p x p ắ ế

Bài 11

ụ

ụM c tiêu - M c tiêu - 11

ể

ụ

ị

ể ữ ệ ấ ấ

ể ấ

c a c u trúc

ầ ử ủ ấ

ở ạ

ử ụ

ệ

ề

ử ụ

 Tìm hi u ki u d li u c u trúc và công d ng  Đ nh nghĩa c u trúc  Khai báo các bi n ki u c u trúc ế  Cách truy c p vào các ph n t ậ  Kh i t o bi n c u trúc ế ấ  S d ng bi n c u trúc trong câu l nh gán ế ấ  Cách truy n tham s c u trúc ố ấ  S d ng m ng các c u trúc ấ ả  Tìm hi u cách kh i t o m ng các c u trúc ả ở ạ

ể

ấ

Elementary Programming with C/Session 11/ Slide 2 of 23

ụ

ụM c tiêu - 2 M c tiêu - 2

ỏ ấ

ng pháp Bubble

ằ

 Con tr c u trúc ỏ ấ  Cách truy n tham s ki u con tr c u trúc ố ể ề  Tìm hi u t khóa typedef ể ừ  S p x p m ng b ng ph ươ ả ắ ế sort và Insertion sort.

Elementary Programming with C/Session 11/ Slide 3 of 23

ấ

ấC u Trúc C u Trúc

 M t c u trúc bao g m các m u d li u, không nh t ấ c nhóm l

t cùng ki u, đ

i v i nhau.

thi

ể

 M t c u trúc có th bao g m nhi u m u d li u nh ư ồ

ẫ ữ ệ

ẫ ữ ệ ạ ớ ề

ộ ấ ế ộ ấ

ồ ượ ể

v y.ậ

I L L U S I O N B A C H

1

1

Bi nế

Tên sách

Tác giả

L n ầ xu t b n ấ ả

I L L U S I O N M ngả

Elementary Programming with C/Session 11/ Slide 4 of 23

ấ ấ

Đ nh Nghĩa C u ị Đ nh Nghĩa C u ị TrúcTrúc

ể ẽ ạ ữ ệ

ấ ườ ệ ị ớ ử ụ

c g i là các ph n ầ ượ ế ấ

hay thành ph n c a c u trúc c a c u trúc ọ ầ ủ ấ ử ủ ấ

Vi c đ nh nghĩa c u trúc s t o ra ki u d li u i dùng s d ng chúng đ m i cho phép ng ể khai báo các bi n ki u c u trúc . ể ấ ế Các bi n trong c u trúc đ t Ví d :ụ

struct cat {

char bk_name [25]; char author [20]; int edn; float price;

};

Elementary Programming with C/Session 11/ Slide 5 of 23

ấ ấ

ộ ấ

ể

Khai Báo Bi n C u Trúc ế Khai Báo Bi n C u Trúc ế ượ ị ề

c đ nh nghĩa, chúng ta có ể ế ộ

t ớ ể ư ữ ấ ệ

Khi m t c u trúc đã đ th khai báo m t ho c nhi u bi n ki u này. ặ Ví d : ụ struct cat books1; Câu l nh này s dành đ vùng nh đ l u tr t ủ ẽ c các m c trong m t c u trúc. ộ ấ ả ụ

struct cat {

struct cat books1, books2; ho c ặ

char bk_name[25]; char author[20]; int edn; float price;

} books1, books2;

struct cat books1; struct cat books2; Elementary Programming with C/Session 11/ Slide 6 of 23

ậ ậ

ử ủ ử ủ

ấ ấ

Truy C p Ph n T c a C u ầ Truy C p Ph n T c a C u ầ TrúcTrúc

ầ ử ủ ấ

ậ

c a c u trúc đ ệ ử ụ này còn đ

ử

ượ toán t c g i là ọ

c truy c p ử ấ ch m ử toán t

 Các ph n t thông qua vi c s d ng (.), toán t ượ thành viên - membership.  Cú pháp:

structure_name.element_name

 Ví d :ụ

scanf(“%s”, books1.bk_name);

Elementary Programming with C/Session 11/ Slide 7 of 23

Kh i T o C u Trúc Kh i T o C u Trúc

ở ạ ở ạ

ấ ấ

ế

 Gi ng nh các bi n khác và m ng, các bi n ế i th i ờ ể ượ

ả c kh i t o t ở ạ ạ

ư ố ki u c u trúc có th đ ể ấ đi m khai báo ể struct employee

 Các bi n ế emp1 và emp2 có ki u ể employee có

int no; { char name [20]; };

c khai báo và kh i t o nh sau: ể ượ ở ạ ư

Elementary Programming with C/Session 11/ Slide 8 of 23

th đ struct employee emp1 = {346, “Abraham”}; struct employee emp2 = {347, “John”};

ử ụ ử ụ

Câu L nh Gán S D ng Câu L nh Gán S D ng Các C u Trúc - 1 Các C u Trúc - 1

ệ ệ ấ ấ

ơ

ả

ệ

ể ử ụ

ấ

ạ

ẳ

ế

ể

ệ

 Có th s d ng câu l nh gán đ n gi n đ gán giá tr c a m t bi n c u trúc cho ế ộ ị ủ ể m t bi n khác có cùng ki u ể ế ộ  Ch ng h n, n u ế books1 và books2 là các bi n c u trúc có cùng ki u, thì câu l nh ấ sau là h p l ợ ệ

books2 = books1;

Elementary Programming with C/Session 11/ Slide 9 of 23

ử ụ ử ụ

Câu L nh Gán S D ng Câu L nh Gán S D ng Các C u Trúc - 2 Các C u Trúc - 2

ệ ệ ấ ấ

ợ ể ườ

ng h p không th dùng câu l nh gán ệ ể ử d ngụ hàm t o s n ạ ẵ

Elementary Programming with C/Session 11/ Slide 10 of 23

Trong tr tr c ti p, thì có th s ự ế memcpy() Cú pháp: memcpy (char * destn, char &source, int nbytes); Ví d :ụ memcpy (&books2, &books1, sizeof(struct cat));

C u Trúc L ng Trong C u Trúc C u Trúc L ng Trong C u Trúc

ồ ồ

ấ ấ

ấ ấ

 M t c u trúc có th l ng trong m t c u trúc khác. Tuy

ộ ấ

ộ ấ

ể ồ

ể ồ

nhiên, m t c u trúc không th l ng trong chính nó. {

ộ ấ struct issue

char borrower [20]; char dt_of_issue[8]; struct cat books;

ng

ươ

c a c u trúc này t ầ ử ủ ấ ng khác,

}issl; ậ t ự ư ớ ấ

 Vi c truy c p vào các ph n t ệ nh v i c u trúc bình th ườ issl.borrower

c a c u trúc cat là m t ph n

ầ ử ủ ấ

ầ

ộ

 Đ truy c p vào ph n t ậ ể c a c u trúc issl , ủ ấ

Elementary Programming with C/Session 11/ issl.books.author Slide 11 of 23

ề ề

ố ể ấ ố ể ấ

Truy n tham s ki u c u Truy n tham s ki u c u trúc trúc

 Tham s c a hàm có th là m t c u

ộ ấ

ố ủ

ể

trúc.

ộ

ữ

ụ

ộ

ươ ề ữ ệ

 Là m t ph ố ầ

ệ

ớ ả

ế

ng ti n h u d ng khi ệ mu n truy n m t nhóm các thành ph n d li u có quan h logic v i nhau thông qua m t bi n thay vì ph i ộ truy n t ng thành ph n m t ộ ả ki u c a tham s hình th c.

ầ  Ki u c a tham s th c ph i trùng v i ớ ố ự ố

ề ừ ể ủ ể ủ

ứ

Elementary Programming with C/Session 11/ Slide 12 of 23

M ng C u Trúc ấ M ng C u Trúc ấ

ả ả

ụ

ườ

ị

ế

 M t áp d ng th ặ  M t ki u c u trúc ph i đ ả ượ ấ ể ả

ng g p là m ng c u trúc ấ ả c đ nh nghĩa c, sau đó m t bi n m ng có ki u đó ể

ộ ộ tr ướ m i đ ớ ượ

ủ

ộ c khai báo  Ví d :ụ struct cat books[50];  Đ truy c p vào thành ph n author c a ầ books: c a m ng

ả

ậ ể th t ph n t ầ ử ứ ư ủ books[4].author

Elementary Programming with C/Session 11/ Slide 13 of 23

ở ạ ở ạ

ấ ấ

ả ả

Kh i T o Các M ng C u Kh i T o Các M ng C u Trúc Trúc

ả ượ ệ

c kh i t o b ng cách li ị t kê c a nó trong m t ộ

M ng c u trúc đ ở ạ ằ ấ danh sách các giá tr ph n t ầ ử ủ c p d u móc ấ ặ  Ví d :ụ

struct unit {

char ch; int i;

}; struct unit series [3] =

Elementary Programming with C/Session 11/ Slide 14 of 23

{{‘a’, 100}{‘b’, 200}{‘c’, 300}};

Con Tr Đ n C u Trúc Con Tr Đ n C u Trúc

ỏ ế ỏ ế

ấ ấ

ượ ặ

c tên c a bi n c u trúc.

ầ

c a m t c u trúc s d ng m t con tr c dùng đ truy c p vào các ph n ậ ộ ỏ

Con tr c u trúc đ c khai báo b ng cách đ t ằ ỏ ấ d u * tr ế ấ ủ ướ ấ Toán t -> đ ể ượ ử t ộ ấ ử ụ ử ủ Ví d :ụ struct cat *ptr_bk; ptr_bk = &books;

printf(“%s”,ptr_bk->author);

ề

c truy n vào hàm, cho c a ầ ử ủ ượ ự ế ổ

Elementary Programming with C/Session 11/ Slide 15 of 23

Con tr c u trúc đ ỏ ấ phép hàm thay đ i tr c ti p các ph n t c u trúc. ấ

ừ

ừT Khóa typedef T Khóa typedef

c đ nh nghĩa ị ộ ữ ệ ể ượ

ằ

khóa ể ớ

ớ storage

ị typedef ữ ệ ể ộ  M t ki u d li u có th đ ể b ng cách s d ng t ử ụ ạ ộ

Elementary Programming with C/Session 11/ Slide 16 of 23

ừ  Nó không t o ra m t ki u d li u m i, mà ộ đ nh nghĩa m t tên m i cho m t ki u đã có. ớ  Cú pháp: typedef type name;  Ví d :ụ typedef float deci;  typedef không th s d ng v i ể ử ụ classes

S p x p m ng ắ ế S p x p m ng ắ ế

ả ả

 S p x p liên quan đ n vi c thay đ i v trí các ph n t ệ

ổ ị

ầ ử

ế

ắ

ế ứ ự

ư

ầ

ả

ị

 D li u trong m ng s d dàng tìm th y h n n u ẽ ễ

xácđ nh nh tăng d n hay gi m d n ầ ơ

ế

ấ

ả ế

theo th t ữ ệ m ng đ ả  Hai ph

c s p x p ng pháp s p x p m ng đ

c trình bày:

ượ ắ ươ

ả

ắ

ượ

ế Bubble Sort và Insertion Sort

ệ

i cùng và ph n t

ng pháp Bubble sort, vi c so sánh b t đ u ắ ầ có giá tr nh h n s ỏ ơ ẽ

ầ ử

ị

t ừ chuy n d n lên trên (n i b t)

ổ ọ

ng pháp Insertion sort, m i ph n t

ỗ

 Trong ph ươ d ph n t ầ ử ướ ầ ể ươ

ầ ử ủ

trong c xem xét, và đ t vào v trí đúng c a nó gi a ữ ị đã đ

ượ ắ

 Trong ph m ng đ ượ ả các ph n t ầ ử

ặ c s p x p ế Elementary Programming with C/Session 11/ Slide 17 of 23

Bubble Sort Bubble Sort

Elementary Programming with C/Session 11/ Slide 18 of 23

Bubble Sort - tt Bubble Sort - tt

#include void main() {

int i,j,temp,arr_num[5]={23,90,9,25,16}; clrscr(); for(i=3;i>=0;i--) /* Tracks every pass */

for(j=4;j>=4-i;j--) {

/* Compares elements */ if(arr_num[j]

{

temp=arr_num[j]; arr_num[j]=arr_num[j-1]; arr_num[j-1]=temp;

}

}                                             Contd…..

Elementary Programming with C/Session 11/ Slide 19 of 23

Bubble Sort - tt Bubble Sort - tt

printf("\nThe sorted array"); for(i=0;i<5;i++)

printf("\n%d", arr_num[i]);

getch();

Elementary Programming with C/Session 11/ Slide 20 of 23

}

Insertion Sort Insertion Sort

Elementary Programming with C/Session 11/ Slide 21 of 23

Insertion Sort - tt Insertion Sort - tt

#include void main() {

int i, j, arr[5] = { 23, 90, 9, 25, 16 }; char flag; clrscr(); /*Loop to compare each element of the unsorted part of the array*/ for(i=1; i<5; i++) /*Loop for each element in the sorted part of the array*/

for(j=0,flag='n'; j

if(arr[j]>arr[i]) {

/*Invoke the function to insert the number*/

insertnum(arr, i, j); flag='y';

}

}

printf("\n\nThe sorted array\n"); for(i=0; i<5; i++)

printf("%d\t", arr[i]);

getch();

}

Elementary Programming with C/Session 11/ Slide 22 of 23

Insertion Sort-3 Insertion Sort-3

insertnum(int arrnum[], int x, int y) {

int temp; /*Store the number to be inserted*/ temp=arrnum[x]; /*Loop to push the sorted part of the

array down from the position where the number has to inserted*/

for(;x>y; x--) arrnum[x]=arrnum[x-1]; /*Insert the number*/ arrnum[x]=temp;

}

Elementary Programming with C/Session 11/ Slide 23 of 23