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.


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
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ụ:
4 Lập trình cơ bản C
Tên
tác giả
Lần
xuất bản
Tên sách
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

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:
Các Kiểu dữ liệu Nâng cao và Sắp xếp 5
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ụ, để

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()
{
struct strucintcal xyz; /* Declares a variable */
void intcal(struct strucintcal);
Các Kiểu dữ liệu Nâng cao và Sắp xếp 7
clrscr();
/* Accepts data into the structure */
printf("\nEnter Customer name: ");
gets(xyz.name);
printf("\nEnter Customer number: ");
scanf("%d", &xyz.numb);
printf("\nEnter Principal amount: ");
scanf("%f", &xyz.amt);
intcal(xyz); /* Passes the structure to a function */
getch();
}
void intcal(struct strucintcal abc)

báo,
books[4].author
sẽ tương ứng là thành phần author của phần tử thứ tư trong mảng books.
Các Kiểu dữ liệu Nâng cao và Sắp xếp 9
19.1.8 Khởi tạo mảng cấu trúc
Một mảng kiểu bất kỳ được khởi tạo bằng cách liệt kê danh sách giá trị của các phần tử trong một cặp
dấu móc. Luật này vẫn đúng khi các phần tử mảng là các cấu trúc. Vì mỗi phần tử của mảng là một
cấu trúc, mà giá trị khởi tạo của một cấu trúc được đặt trong cặp dấu móc, nên ta phải sử dụng các cặp
dấu móc lồng nhau khi khởi tạo mảng các cấu trúc. Xét ví dụ sau:
struct unit
{
char ch;
int i;
};
struct unit series[3] =
{
{‘a’, 100},
{‘b’, 200},
{‘c’, 300},
};
Đoạn lệnh này khai báo series là một mảng cấu trúc gồm 3 phần tử, mỗi phần tử có kiểu unit. Khi
khởi tạo, vì mỗi phần tử là một cấu trúc nên giá trị của nó được đặt trong cặp dấu móc, và toàn bộ
giá trị các phần tử được đóng trong dấu móc để cho biết đang khởi tạo một mảng.
10 Lập trình cơ bản C
19.1.9 Con trỏ cấu trúc
C hỗ trợ con trỏ cấu trúc, nhưng có một số khía cạnh đặc biệt đối với con trỏ cấu trúc. Giống như các
kiểu con trỏ khác, con trỏ cấu trúc được khai báo bằng cách đặt dấu * trước tên của biến cấu trúc. Ví
dụ, câu lệnh sau đây khai báo con trỏ ptr_bk của kiểu cấu trúc cat.
struct cat *ptr_bk;
Bây giờ để gán địa chỉ của biến cấu trúc books kiểu cat cho ptr_bk, câu lệnh sẽ như sau:

float có thể được định nghĩa sử dụng deci như sau:
deci amt;
Ở đây, amt là một biến số thực kiểu deci, chính là một tên khác của float. Sau khi được định nghĩa,
deci có thể được sử dụng như một kiểu dữ liệu trong câu lệnh typedef để gán một tên khác cho kiểu
float. Chẳng hạn,
typedef deci point;
Câu lệnh trên báo cho trình biên dịch biết để nhận dạng point như là một tên khác của deci, cũng
chính là một tên khác của float. Đặc tính typedef đặc biệt tiện lợi khi định nghĩa các cấu trúc, vì ta
không cần nhắc lại nhãn struct mỗi khi một sử dụng cấu trúc. Khi đó việc sử dụng cấu trúc sẽ thuận
tiện hơn. Thêm vào đó, tên một kiểu cấu trúc do người dùng định nghĩa thường gợi nhớ đến mục đích
của cấu trúc trong chương trình. Một cách tổng quát, một cấu trúc do người dùng định nghĩa có thể
được viết như sau:
typedef struct new_type
{
type var1;
type var2;
}
Ở đây, new_type là kiểu cấu trúc do người dùng định nghĩa và nó không phải là một biến cấu trúc.
Bây giờ, các biến kiểu cấu trúc có thể được định nghĩa theo kiểu dữ liệu mới.Ví dụ:
typedef struct
{
int day;
int month;
int year;
} date;
date due_date;
Ở đây, date là một kiểu dữ liệu mới và due_date là một biến kiểu date.
Cần nhớ rằng typedef không thể sử dụng với storage classes.
19.3 Sắp xếp mảng (Sorting Arrays)
Sắp xếp có nghĩa là xếp mảng dữ liệu theo một thứ tự xác định như tăng dần hay giảm dần. Khi mảng

90 90 16 23
16 16 90 90
25 25 25 25
9 9 9
16 16 16
23 23 23
90 25 25
25 90 90
9 9
16 16
23 23
25 25
90 90
9
Các Kiểu dữ liệu Nâng cao và Sắp xếp 13
16
23
25
90
Figure 19.2: Bubble Sort
Chương trình thực hiện sắp xếp mảng theo phương pháp bubble sort:
Ví dụ 2:
#include <stdio.h>
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 */
{

sắp xếp tiếp tục cho đến khi phần tử cuối cùng trong mảng đã được so sánh và đặt vào vị trí đúng
của nó.
Ở cuối quá trình sắp xếp, mỗi phần tử được xen vào đúng vị trí của nó. Hình 19.3 minh họa cách làm
việc của insertion sort.
23 23
90 90
9 9
25 25
16 16
23 9
90 23
9 90
25 25
16 16
9 9 9 9
23 23 23 23
90 90 90 25
25 25 25 90
16 16 16 16
9 9 9
23 23 16
25 25 23
90 90 25
Các Kiểu dữ liệu Nâng cao và Sắp xếp 15
16 16 90
Figure 19.3: Insertion Sort
Chương trình thực hiện sắp xếp mảng theo phương pháp insertion sort :
Ví dụ 3:
#include<stdio.h>
void main()

arrnum[x] = arrnum[x - 1];
/*Insert the number*/
arrnum[x] = temp;
16 Lập trình cơ bản C
}
Các Kiểu dữ liệu Nâng cao và Sắp xếp 17
Tóm tắt
 .Một cấu trúc là tập các biến có thể có kiểu dữ liệu khác nhau được nhóm lại với nhau dưới cùng
một tên.
 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 phần tử độc lập của cấu trúc được truy cập bằng cách sử dụng toán tử chấm (.), hay còn được
gọi là toán tử thành viên.
 Các giá trị của một biến cấu trúc có thể được gán cho một biến khác có cùng kiểu bằng cách sử
dụng câu lệnh gán đơn giản.
 Có thể có một cấu trúc nằm 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ó.
 Một biến cấu trúc có thể được truyền vào một hàm như là một tham số.
 Cách sử dụng thông dụng nhất của cấu trúc là dưới hình thức mảng cấu trúc.
 Toán tử -> được sử dụng để truy cập vào các phần tử của một cấu trúc thông qua một con trỏ trỏ
đến cấu trúc đó.
 Một kiểu dữ liệu mới có thể được định nghĩa bằng từ khóa typedef.
 Hai phương pháp dùng để sắp xếp một mảng là bubble sort và insertion sort.
 Trong bubble sort, giá trị của các phần tử được so sánh với giá trị của phần tử kế tiếp. Trong
phương pháp này, các phần tử nhỏ hơn nổi lên dần, và cuối cùng mảng sẽ được sắp xếp.
 Trong insertion sort, ta xét mỗi phần tử trong mảng và chèn vào vị trí đúng của nó giữa các phần
tử đã được sắp xếp.
18 Lập trình cơ bản C
Kiểm tra tiến độ học tập
1. Một __________ nhóm một số mẫu dữ liệu lại với nhau, các mẫu dữ liệu này không nhất thiết