Bài 19 Các Ki u d li u Nâng cao và S p x pể ữ ệ ắ ế
M c tiêu:ụ
K t thúc bài h c này, b n có th :ế ọ ạ ể
Tìm hi u c u trúc (structure) và công d ng c a chúngể ấ ụ ủ
Đ nh nghĩa c u trúcị ấ
Khai báo các bi n ki u c u trúcế ể ấ
Tìm hi u cách truy c p vào các ph n t c a c u trúcể ậ ầ ử ủ ấ
Tìm hi u cách kh i t o c u trúcể ở ạ ấ
Tìm hi u cách s d ng c u trúc v i câu l nh gánể ử ụ ấ ớ ệ
Tìm hi u cách truy n tham s ki u c u trúc ể ề ố ể ấ
S d ng m ng c u trúcử ụ ả ấ
Tìm hi u cách kh i t o các m ng c u trúcể ở ạ ả ấ
Tìm hi u con tr đ n c u trúcể ỏ ế ấ
Tìm hi u cách truy n đ i s ki u con tr c u trúc vào hàm .ể ề ố ố ể ỏ ấ
Tìm hi u t khóa typedefể ừ
Tìm hi u hai thu t toán s p x p m ng là Insertion sort và Bubble sort.ể ậ ắ ế ả
Gi i thi uớ ệ
Các ch ng trình ng d ng trong th c t đòi h i l u tr các ki u d li u khác nhau. Tuy nhiên, cácươ ứ ụ ự ế ỏ ư ữ ể ữ ệ
ki u d li u c a C mà chúng ta đã đ c h c có th không đ trong các tr ng h p đó. Vì v y, Cể ữ ệ ủ ượ ọ ể ủ ườ ợ ậ
cho phép t o ra các ki u d li u do ng i dùng đ nh nghĩa. M t trong nh ng ki u nh v y là ạ ể ữ ệ ườ ị ộ ữ ể ư ậ c uấ
trúc (structure). M t c u trúc là m t t p các bi n đ c nhóm l i v i nhau có cùng tên. M t ki uộ ấ ộ ậ ế ượ ạ ớ ộ ể
d li u cũng có th đ c đ t tên m i b ng cách s d ng t khóa ữ ệ ể ượ ặ ớ ằ ử ụ ừ typedef.
Các ng d ng th ng l u tr m t s l ng d li u r t l n. Trong nh ng tr ng h p này, vi cứ ụ ườ ư ữ ộ ố ượ ữ ệ ấ ớ ữ ườ ợ ệ
đ nh v m t m c d li u nào đó có th t n nhi u th i gian. S p x p các giá tr theo m t tr t t nàoị ị ộ ụ ữ ệ ể ố ề ờ ắ ế ị ộ ậ ự
đó s làm cho công vi c tìm ki m nhanh chóng và d dàng h n. Trong ch ng này, chúng ta cũngẽ ệ ế ễ ơ ươ
s xem m t s gi i thu t dùng đ s p x p các m ng. ẽ ộ ố ả ậ ể ắ ế ả
19.1 C u trúcấ
Bi n đ c s d ng đ l u gi m t m u d li u t i m t th i đi m và m ng đ c s d ng đ l uế ượ ử ụ ể ư ữ ộ ẫ ữ ệ ạ ộ ờ ể ả ượ ử ụ ể ư
gi m t s m ud li u có cùng ki u. Tuy nhiên, m t ch ng trình có th yêu c u x lý các m cữ ộ ố ẫ ữ ệ ể ộ ươ ể ầ ử ụ
d li u có ki u khác nhau trong cùng m t đ n v chung. tr ng h p này, c bi n và m ng đ uữ ệ ể ộ ơ ị Ở ườ ợ ả ế ả ề
không thích h p đ s d ng.ợ ể ử ụ
Ví d , m t ch ng trình đ c vi t đ l u tr d li u v m t danh m c sách. Ch ng trình đòi h iụ ộ ươ ượ ế ể ư ữ ữ ệ ề ộ ụ ươ ỏ
ph i nh p và l u tr tên c a m i quy n sách (m t m ng chu i), tên c a tác gi (m t m ng chu iả ậ ư ữ ủ ỗ ể ộ ả ỗ ủ ả ộ ả ỗ
khác), l n xu t b n (m t s nguyên), giá c a quy n sách (m t s th c). M t m ng đa chi u khôngầ ấ ả ộ ố ủ ể ộ ố ự ộ ả ề
th s d ng đ làm đi u này, vì các ph n t c a m t m ng ph i có cùng ki u. Trong tr ng h pể ử ụ ể ề ầ ử ủ ộ ả ả ể ườ ợ
này, vi c s d ng c u trúc s làm cho m i vi c tr nên đ n gi n h n.ệ ử ụ ấ ẽ ọ ệ ở ơ ả ơ
Các Ki u d li u Nâng cao và S p x pể ữ ệ ắ ế 3
M t c u trúc bao g m m t s m u d li u, không c n ph i cùng ki u, đ c nhóm l i v i nhau.ộ ấ ồ ộ ố ẫ ữ ệ ầ ả ể ượ ạ ớ
Trong ví d trên, m t c u trúc s bao g m tên sách, tên tác gi , l n xu t b n, và giá c a quy nụ ộ ấ ẽ ồ ả ầ ấ ả ủ ể
sách. C u trúc có th l u gi bao nhiêu m u d li u cũng đ c.ấ ể ư ữ ẫ ữ ệ ượ
Hình 19.1 Minh h a s khác bi t gi a m t bi n, m t m ng và m t c u trúc.ọ ự ệ ữ ộ ế ộ ả ộ ấ
I
L
L
U
S
I I
1 L O
Biế
n
L N
U S
S B
I A
O C
N H
S
M nả
g
1
C uấ
trúc
Hình 19.1. S khác nhau gi a m t bi n, m t m ng và m t c u trúc.ự ữ ộ ế ộ ả ộ ấ
19.1.1 Đ nh nghĩa m t c u trúcị ộ ấ
Vi c đ nh nghĩa c u trúc s t o ra ki u d li u m i cho phép ng i dùng s d ng chúng đ khaiệ ị ấ ẽ ạ ể ữ ệ ớ ườ ử ụ ể
báo các bi n ki u c u trúc. Các bi n trong c u trúc đ c g i là các ph n t hay các thành ph n c aế ể ấ ế ấ ượ ọ ầ ử ầ ủ
c u trúc.ấ
M t cách t ng quát, các ph n t c a m t c u trúc quan h v i nhau m t cách logic vì chúng liênộ ổ ầ ử ủ ộ ấ ệ ớ ộ
quan đ n m t th c th duy nh t. Ví d , m t danh m c sách có th đ c bi u di n nh sau:ế ộ ự ể ấ ụ ộ ụ ể ượ ễ ễ ư
struct cat
{
char bk_name [25];
char author [20];
int edn;
float price;
};
Câu l nh trên đ nh nghĩa m t ki u d li u m i có tên là ệ ị ộ ể ữ ệ ớ struct cat. M i bi n c a ki u này bao g mỗ ế ủ ể ồ
b n ph n t - bk_name, author, edn, và price. Câu l nh không khai báo b t kỳ bi n nào và vì v yố ầ ử ệ ấ ế ậ
ch ng trình không đ dành b t kỳ vùng nh nào trong b nh . Nó ch đ nh nghĩa c u trúc c a ươ ể ấ ớ ộ ớ ỉ ị ấ ủ cat.
T khóa ừstruct báo cho trình biên d ch bi t r ng m t structure đ c đ nh nghĩa. Nhãn ị ế ằ ộ ượ ị cat không
ph i là tên bi n, vì không ph i ta đang khai báo bi n. Nó là m t ả ế ả ế ộ tên ki uể. Các ph n t c a c u trúcầ ử ủ ấ
đ c đ nh nghĩa trong d u móc, và k t thúc toàn b câu l nh b ng m t d u ch m ph y.ượ ị ấ ế ộ ệ ằ ộ ấ ấ ẩ
19.1.2 Khai báo bi n ki u c u trúcế ể ấ
4 L p trình c b n Cậ ơ ả
Tên
tác giả
L n ầ
xu t b nấ ả
Tên sách
Khi m t c u trúc đã đ c đ nh nghĩa, chúng ta 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 gi t t c các m c trong m t c u trúc. Khai báo trênệ ẽ ủ ớ ể ư ữ ấ ả ụ ộ ấ
th c hi n ch c năng t ng t nh các khai báo bi n: ự ệ ứ ươ ự ư ế int xyz và float ans. Nó báo v i trình biênớ
d ch dành ra m t vùng l u tr cho m t bi n v i ki u nào đó và gán tên cho bi n.ị ộ ư ữ ộ ế ớ ể ế
Cũng nh v i ư ớ int, float và các ki u d li u khác, ta có th có m t s b t kỳ các bi n có ki u c uể ữ ệ ể ộ ố ấ ế ể ấ
trúc đã cho. Trong m t ch ng trình, có th khai báo hai bi n books1 và books2 có ki u c u trúc ộ ươ ể ế ể ấ cat
. Đi u này có th th c hi n đ c theo nhi u cách.ề ể ự ệ ượ ề
struct cat
{
char bk_name[25];
char author[20];
int edn;
float price;
} books1, books2;
ho cặ
struct cat books1, books2;
ho c ặ
struct cat books1;
struct cat books2;
Các khai báo này s dành vùng nh cho hai bi n books1 và books2.ẽ ớ ế
Các ph n t c a c u trúc đ c truy c p thông qua vi c s d ng toán t ch m (.), toán t này cònầ ử ủ ấ ượ ậ ệ ử ụ ử ấ ử
đ c g i là toán t thành viên ượ ọ ử membership. Cú pháp t ng quát dùng đ truy c p m t ph n t c aổ ể ậ ộ ầ ử ủ
c u trúc là:ấ
structure_name.element_name
Ví d nh mã l nh sau đây truy c p đ n tr ng bk_name c a bi n ki u c u trúc books1 đã khaiụ ư ệ ậ ế ườ ủ ế ể ấ
báo trên.ở
books1.bk_name
Đ đ c vào tên c a quy n sách, câu l nh s là:ể ọ ủ ể ệ ẽ
scanf(“%s”, books1.bk_name);
Đ in ra tên sách, câu l nh s là:ể ệ ẽ
printf(“The name of the book is %s”, books1.bk_name);
19.1.3 Kh i t o bi n c u trúcở ạ ế ấ
Các Ki u d li u Nâng cao và S p x pể ữ ệ ắ ế 5
Gi ng nh các bi n và m ng, các bi n ki u c u trúc có th đ c kh i t o t i th i đi m khai báo.ố ư ế ả ế ể ấ ể ượ ở ạ ạ ờ ể
Hình th c t ng t nh cách kh i t o m ng. Xét c u trúc sau dùng đ l u s th t và tên nhânứ ươ ự ư ở ạ ả ấ ể ư ố ứ ự
viên:
struct employee
{
int no;
char name[20];
};
Các bi n ếemp1 và emp2 có ki u ểemployee có th đ c khai báo và kh i t o nh sau:ể ượ ở ạ ư
struct employee emp1 = {346, “Abraham”};
struct employee emp2 = {347, “John”};
đây, sau khi khai báo ki u c u trúc, hai bi n c u trúc Ở ể ấ ế ấ emp1 và emp2 đ c khai báo và kh i t o.ượ ở ạ
Vi c khai báo và kh i t o c a chúng đ c th c hi n cùng lúc b i m t câu l nh duy nh t. Vi cệ ở ạ ủ ượ ự ệ ở ộ ệ ấ ệ
kh i t o c u trúc t ng t nh kh i t o m ng – ki u bi n, tên bi n, và toán t gán, cu i cùng làở ạ ấ ươ ự ư ở ạ ả ể ế ế ử ố
danh sách các giá tr đ c đ t trong c p móc và đ c phân cách b i d u ph y.ị ượ ặ ặ ượ ở ấ ẩ
19.1.4 Th c hi n câu l nh gán v i các bi n c u trúcự ệ ệ ớ ế ấ
Có th gán giá tr c a m t bi n c u trúc cho m t bi n khác cùng ki u b ng cách s d ng câu l nhể ị ủ ộ ế ấ ộ ế ể ằ ử ụ ệ
gán đ n gi n. 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;
Cũng có nh ng tr ng h p không th dùng câu l nh gán tr c ti p, thì có th s d ng hàm t o s nữ ườ ợ ể ệ ự ế ể ử ụ ạ ẵ
memcpy(). Nguyên m u c a hàm này là:ẫ ủ
memcpy (char * destn, char &source, int nbytes);
Hàm này th c hi n sao chép ự ệ nbytes đ c l u tr b t đ u t đ a ch ượ ư ữ ắ ầ ừ ị ỉ source đ n m t vùng nh khácế ộ ớ
có đ a ch b t đ u t ị ỉ ắ ầ ừ destn. Hàm đòi h i ng i s d ng ph i ch ra kích c c a c u trúc (nbytes),ỏ ườ ử ụ ả ỉ ỡ ủ ấ
kích c này có th đ t đ c b ng cách s d ng toán t ỡ ể ạ ượ ằ ử ụ ử sizeof(). S d ng hàm ử ụ memcpy(), có thể
sao chép n i dung c a ộ ủ books1 sang books2 nh sau:ư
memcpy (&books2, &books1, sizeof(struct cat));
19.1.5 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ó. R t nhi u tr ng h p th c t đòi h i có m t c u trúc n m trong m t c u trúc khác. Xétấ ề ườ ợ ự ế ỏ ộ ấ ằ ộ ấ
ví d , đ l u tr thông tin v nh ng ng i m n sách và chi ti t c a quy n sách đ c m n taụ ể ư ữ ề ữ ườ ượ ế ủ ể ượ ượ
có th s d ng c u trúc sau:ể ử ụ ấ
struct issue
{
char borrower [20];
char dt_of_issue[8];
struct cat books;
}issl;
6 L p trình c b n Cậ ơ ả
Câu l nh này khai báo ệbooks là m t thành ph n c a c u trúc ộ ầ ủ ấ issue. B n thân thành ph n này là m tả ầ ộ
c u trúc ki u ấ ể struct cat. Bi n c u trúc trên có th đ c kh i t o nh sau:ế ấ ể ượ ở ạ ư
struct issue issl = {“Jane”, “04/22/03”, {“Illusions”,
“Richard Bach”, 2, 150.00}};
Các d u ngo c l ng nhau đ c s d ng đ kh i t o m t c u trúc n m trong m t c u trúc.ấ ặ ồ ượ ử ụ ể ở ạ ộ ấ ằ ộ ấ
Đ i v i bi n c u trúc có thành ph n là m t c u trúc khác, vi c truy c p các thành ph n c a bi nố ớ ế ấ ầ ộ ấ ệ ậ ầ ủ ế
này hoàn toàn t ng t đ i v i m t bi n c u trúc thông th ng. Ch ng h n, đ truy c p vào tênươ ự ố ớ ộ ế ấ ườ ẳ ạ ể ậ
c a ng i m n ta dùng l nh là: ủ ườ ượ ệ
issl.borrower
Tuy nhiên, đ truy c p thành ph n ể ậ ầ author c a bi n c u trúc ủ ế ấ cat mà bi n c u trúc này l i là thànhế ấ ạ
ph n c a m t bi n c u trúc ầ ủ ộ ế ấ issl ta s d ng l nh sau:ử ụ ệ
issl.books.author
M c đ l ng c a các c u trúc ch b gi i h n b i dung l ng hi n th i c a b nh . Có th có m tứ ộ ồ ủ ấ ỉ ị ớ ạ ở ượ ệ ờ ủ ộ ớ ể ộ
c u trúc l ng trong m t c u trúc r i l ng trong m t c u trúc khác và v.v… Tên c a các bi nấ ồ ộ ấ ồ ồ ộ ấ ủ ế
th ng đ c đ t theo cách th c g i nh n i dung thông tin mà nó l u tr . Ví d nh :ườ ượ ặ ứ ợ ớ ộ ư ữ ụ ư
company.division.employee.salary
Cũng c n nh r ng n u m t c u trúc đ c l ng trong m t c u trúc khác, nó ph i đ c khai báoầ ớ ằ ế ộ ấ ượ ồ ộ ấ ả ượ
tr c c u trúc khác s d ng nó.ướ ấ ử ụ
19.1.6 Truy n tham s ki u c u trúcề ố ể ấ
Ki u tham s c a m t hàm có th là c u trúc. Đây là m t ph ng ti n h u d ng khi ta 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. Tuy nhiên, khi m t c u trúc đ c s d ng nh m t tham s , c n ph iề ừ ầ ộ ộ ấ ượ ử ụ ư ộ ố ầ ả
l u ý r ng ki u c a tham s th c ph i trùng v i ki u c a tham s hình th c.ư ằ ể ủ ố ự ả ớ ể ủ ố ứ
Ch ng h n nh , m t c u trúc đ c khai báo đ l u tr tên, mã s khách hàng và s ti n g i g cẳ ạ ư ộ ấ ượ ể ư ữ ố ố ề ử ố
vào tài kho n c a khách hàng. D li u đ c nh p trong hàm ả ủ ữ ệ ượ ậ main(), vi c toán s ti n lãi ph i trệ ố ề ả ả
đ c th c hi n b ng cách g i hàm intcal() có m t tham s ki u c u trúc. Đo n l nh nh sau:ượ ự ệ ằ ọ ộ ố ể ấ ạ ệ ư
Ví d 1:ụ
#include <stdio.h>
struct strucintcal /* Defines the structure */
{
char name[20];
int numb;
float amt;
};
void main()
Các Ki u d li u Nâng cao và S p x pể ữ ệ ắ ế 7