Bài giảng môn Ngôn ngữ lập trình C - 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);  Thêm một node vào cuối DS: int InsertAfter(List*, int);  Thêm một node vào giữa DS: int Insert(List*, int);  Xóa một node đầu DS: int DeleteFirst(List*);  Xóa một node cuối DS: int DeleteAfter(List*);  Xóa một node giữa DS: int Delete(List*);  Duyệt DS: void Travel(List); struct node { int data; struct node *next; }; typedef struct node* List; Ứng dụng: DSLK đơn void Init(List *First) { *First = NULL; } First NULL  Khởi tạo danh sách: Ứng dụng: DSLK đơn  Tạo 1 node mới có nội dung x: struct node* NewNode(int x) { struct node *p; p = (struct node *)malloc(sizeof(struct node); if (p!=NULL) {p -> data = x; p -> next = NULL;} return (p) } x next newNode NULL Ứng dụng: DSLK đơn  Thêm một node vào DSLK:  Thêm vào đầu danh sách:  Tạo node mới có nội dung x; (newNode = NewNode(x))  Phần next của node trỏ tới đầu DSLK.  Trỏ First tới newNode NULLL newNode x Ứng dụng: DSLK đơn  Thêm một node vào DSLK (.t):  Thêm vào cuối danh sách  Tìm con trỏ trỏ tới node cuối cùng (temp)  Tạo node mới newNode(x)  Phần next của node temp tới newNode v NULLL temp newNode Ứng dụng: DSLK đơn  Thêm một node vào DSLK (.t):  Thêm vào giữa danh sách:  Tìm con trỏ (temp) trỏ tới node trước vị trí cần thêm  Tạo node mới newNode(x)  Trỏ phần next của newNode tới node sau temp  Trỏ phần next của temp tới newNode NULL L v newNode temp x Ứng dụng: DSLK đơn  Xóa một node trong DSLK:  Xóa node ở đầu danh sách:  Tạo một con trỏ temp trỏ vào node đầu danh sách  Trỏ First tới node thứ 2 trong danh sách  Thu hồi vùng nhớ node đầu tiên (được trỏ bởi temp) NULL temp L Ứng dụng: DSLK đơn  Xóa một node trong DSLK (t.):  Xóa node ở cuối danh sách:  Tìm con trỏ p trỏ tới node áp cuối, con trỏ temp trỏ tới node cuối cùng  Phần next của p trở tới NULL  Thu hồi vùng nhớ của node cuối (được trỏ bởi temp) v v NULL vtemp v v p L Ứng dụng: DSLK đơn  Xóa một node trong DSLK (t.):  Xóa node ở giữa danh sách:  Trỏ temp tới node cần xóa, p tới node trước node cần xóa  Phần next của p tới node sau node temp  Giải phóng vùng nhớ của node cần xóa (được trỏ bởi temp) NULL vtemp p x L Ứng dụng: DSLK đơn  Danh sách liên kết vòng v v vfirst last • Danh sách liên kết đôi first last v NULLv vNULL Ứng dụng: DSLK đơn  Tìm node có nội dung x x NULLL p struct node* FindNode(List L ,int x) { struct node *p; p = L; while (p!=NULL) { if (p->Info == x) return p; p = p->Next; } return (p) }