Bài giảng Kỹ thuật lập trình - Chương 5: Dữ liệu kiểu cấu trúc - Nguyễn Thị Hiền

Chương 5. Dữ liệu
kiểu cấu trúc
Chương 5. Dữ liệu kiểu cấu trúc
 Khái niệm
 Khai báo cấu trúc
 Các thao tác trên biến cấu trúc
 Mảng cấu trúc
 Con trỏ cấu trúc và địa chỉ cấu trúc
 Truyền biến cấu trúc cho hàm
 Cấu trúc tự trỏ và ứng dụng
Khái niệm
 Cấu trúc là tập hợp của một hoặc nhiều biến, 
chúng có thể có kiểu dữ liệu khác nhau, được
nhóm lại dưới một tên duy nhất để tiện xử lý. 
 Cấu trúc còn gọi là bản ghi trong một số ngôn
ngữ lập trình khác, chẳng hạn như PASCAL.
Khái niệm
 Một số ví dụ về cấu trúc:
 Phiếu ghi lương, gồm có: tên, địa chỉ, lương, phụ
cấp,  một số trong các thuộc tính này lại có thể là
một cấu trúc bởi trong nó có thể chứa nhiều thành
phần: Tên ( Họ, đệm, tên ), Địa chỉ ( Phố, số nhà ), ...
 Danh sách sinh viên, gồm có: mã sinh viên, họ tên, 
ngày sinh, điểm toán, điểm lý, điểm hóa; trong đó, 
ngày sinh có thể chứa nhiều thành phần ngày, tháng, 
năm.
 Những dạng như vậy sử dụng cấu trúc.
Định nghĩa kiểu cấu trúc
 Định nghĩa cấu trúc bằng struct:
struct tên_kiểu_cấu_trúc{
Khai báo các thành phần của cấu trúc };
 Ý nghĩa:
 struct: từ khoá
 tên_kiểu_cấu_trúc: do người lập trình tự đặt.
 thành phần của cấu trúc có thể là: biến, mảng, cấu trúc khác
đã được định nghĩa trước đó
 Ví dụ:
struct ngay
{int ngaythu;
char thang[12];
int nam;
};
Định nghĩa kiểu cấu trúc
 Định nghĩa cấu trúc bằng typedef
typedef ;
 Ví dụ:
typedef struct
{ int ngaythu;
char thang[12];
int nam;
} ngay;
Khai báo biến cấu trúc
 Giống như khai báo biến thông thường
 Cú pháp:
struct
;
 Ví dụ:
struct ngay ngaydi, ngayden;
 Chú ý: Các biến kiểu cấu trúc được khai báo
theo mẫu trên sẽ được cấp phát bộ nhớ một
cách đầy đủ cho tất cả các thành phần của nó.
Khai báo biến cấu trúc
 Có thể khai báo biến cấu trúc đồng thời với định nghĩa
cấu trúc
 Cú pháp:
struct {
Thành phần cấu trúc};
 Ví dụ:
struct ngay {
int ngaythu;
char thang[12];
int nam;
} ngaydi, ngayden; 
Các thao tác trên biến cấu trúc
 Truy cập đến các thành phần của cấu trúc: 
 Sử dụng dấu . để truy cập đến thành phần của cấu trúc.
tên_biến_cấu_trúc.tên_thành_phần
tên_biến_cấu_trúc.tên_cấu_trúc_con.tên_thành_phần
 Ví dụ:
ngay a;
a.ngaythu=15;
printf(“%d”,a.ngaythu);
Các thao tác trên biến cấu trúc
 Truy cập đến các thành phần của cấu trúc: 
 Chú ý: 
 Có thể sử dụng phép toán lấy địa chỉ đối với các thành phần
của cấu trúc để nhập số liệu trực tiếp vào các thành phần
của cấu trúc. Ví dụ như ta viết:
scanf("%d",&a.nam);
 Tuy nhiên ta nên nhập số liệu vào một biến trung gian sau đó
mới gán cho thành phần của cấu trúc như sau:
int year;
scanf("%d",&year);
a.nam=year;
Các thao tác trên biến cấu trúc
 Phép gán cấu trúc:
 Có thể thực hiện phép gán trên các biến và phần tử
mảng kiểu cấu trúc cùng kiểu.
Mỗi một phép gán trên tương đương với một dãy
phép gán các thành phần tương ứng.
Mảng cấu trúc
 Có thể sử dụng một kiểu cấu trúc đã mô tả để khai báo
các biến kiểu cấu trúc và mảng kiểu cấu trúc.
 Cú pháp:
struct 
 Ví dụ:
struct canbo cb1,cb2,nhom1[10],nhom2[7];
double tongluong=0;
for (i=0;i<10;++i)
tongluong+=nhom1[i].luong;
 Không dùng toán tử địa chỉ với các thành phần của
mảng cấu trúc: không cho phép viết &nhom1[i].luong
Con trỏ cấu trúc
 Con trỏ cấu trúc: 
 Cú pháp:
struct 
*;
 Ví dụ:
struct ngay*p,*p1,*p2,nc1,nc2,ds[100];
p1=&nc1; /* Gán địa chỉ nc1 cho p1 */
p2=&ds[4]; /* Gán địa chỉ ds[4] cho p2 */
p=ds; /* Gán địa chỉ ds[0] cho p */
Con trỏ cấu trúc
 Con trỏ cấu trúc: (t.)
 Truy cập các thành phần của con trỏ cấu trúc:
 Cú pháp:
Cách 1: Tên_con_trỏ->Tên_thành_phần
Cách 2: (*Tên_con_trỏ).Tên_thành_phần
 Ví dụ:
struct ngay *p,*p1,*p2,nc1,nc2,ds[100];
nc1. nam;
p1-> nam;
ds[4]. thang;
(*p2).thang;
Cấu trúc tự trỏ
 Khái niệm
 Là cấu trúc có ít nhất một thành phần là con trỏ kiểu
cấu trúc đang định nghĩa
 Ví dụ:
struct person{
char name[50];
int age;
struct person *next;
}
Cấu trúc tự trỏ
 Ứng dụng
 Cấu trúc tự trỏ được dùng để xây dựng danh sách
liên kết.
 Danh sách liên kết:
Quản lý con trỏ lưu trữ cấu trúc đầu tiên của danh
sách
 Trong cấu trúc (trừ cấu trúc cuối cùng), chứa địa chỉ
cấu trúc tiếp theo của danh sách
 Cấu trúc cuối chứa hằng NULL
Cấu trúc tự trỏ
 Một số danh sách liên kết sử dụng cấu trúc tự
trỏ:
 Stack (ngăn xếp): hoạt động theo phương thức Last 
In – First Out (LIFO)
Queue (hàng đợi): hoạt động theo phương thức First 
In – First Out (FIFO)
 Binary tree (cây nhị phân):
 Là một cây, trong đó mỗi node cha có 2 node con
 Node con trái có giá trị nhỏ hơn node cha
 Node con phải có giá trị lớn hơn node cha
Ứng dụng: DSLK đơn
 Khái niệm: Danh sách liên
kết đơn là một cấu trúc dữ
liệu bao gồm một tập các
node, mỗi node gồm:
 Dữ liệu cần lưu trữ
 Liên kết đến node tiếp theo
(địa chỉ của node tiếp theo)
Link
Data
Node
Add
60
1000
800 45
800
90 55
90
0 NULL
start
Ứng dụng: DSLK đơn
 Ưu điểm:
 DSLK là cấu trúc động, các node được cấp phát/giải
phóng khi chương trình đang chạy -> Kích thước danh
sách không cần phải khai báo trước
 DSLK thích hợp khi thực hiện các phép toán trên những
danh sách (tập hợp) thường bị biến động như chèn, 
xóa phần tử.
 Hạn chế: 
Mỗi node của DSLK phải chứa thêm trường next nên
tốn thêm bộ nhớ
 Tìm kiếm trên DSLK chậm do ta không thể truy xuất được
ngẫu nhiên, chỉ truy xuất được tuần tự từ đầu danh sách
Ứng dụng: DSLK đơn
 Ví dụ 1: DSLK lưu thông tin 
sinh viên:
struct TTSV
{
char Hoten[20];
int Tuoi;
}
struct node
{
struct TTSV data;
struct node* next;
}
struct node *First;
 Ví dụ 2: DSLK lưu số
nguyên
struct node
{
int data;
struct node* next;
}
struct node *First;
Ứng dụng: DSLK đơn
 Khai báo 1 DSLK
 Khởi tạo DS: void Init(List*);
 Tạo một node có nội dung x: struct node* NewNode(int);
 Tìm một node có nội dung x: struct node* FindNode(List ,int);
 Thêm một node vào đầu DS: int InsertFirst(List*, int);