Giáo trình mô đun Cấu trúc dữ liệu và giải thuật

ỦY BAN NHÂN DÂN TỈNH BR – VT TRƯỜNG CAO ĐẲNG NGHỀ GIÁO TRÌNH MÔ ĐUN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGHỀ CÔNG NGHỆ THÔNG TIN TRÌNH ĐỘ CAO ĐẲNG Ban hành kèm theo Quyết định số: 01/QĐ-CĐN ngày 04 tháng 01 năm 2016 của Hiệu trưởng trường Cao đẳng nghề tỉnh Bà Rịa – Vũng Tàu Bà Rịa – Vũng Tàu, năm 2016 TUYÊN BỐ BẢN QUYỀN Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo. Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm. LỜI GIỚI THIỆU Giáo trình cấu trúc dữ liệu và giải thuật dùng cho học sinh hệ Cao Đẳng và Trung cấp của nghề lập trình máy tính và hệ cao đẳng chuyên ngành công nghệ thông tin ứng dụng phần mềm trong trường Cao đẳng nghề Tỉnh BR – VT. Nhằm cung cấp cho sinh viên các thuật toán tổng quát, danh sách liên kết, và các giải thuật sắp xếp, tìm kiếm. Từ đó sinh viên sẽ từng bước cải tiến thuật toán để xây dựng được những chương trình hiệu quả và có tính ứng dụng cao. Mục đích của giáo trình là trang bị cho học viên những kiến thức và kỹ năng phân tích xây dựng được thuật toán kết hợp với giải thuật Để có thể nắm bắt các kiến thức học sinh cần được trang bị các kiến thức về môn lập trình căn bản. Ngôn ngữ lập trình được chọn để minh họa các kiến thức trên là Dev C++. Trong qua trình biên soạn giáo trình, chắn chắn rằng trong giáo trình sẽ còn nhiều khiếm khuyết, tác giả mong muốn nhận được các ý kiến quí báu đóng góp của đồng nghiệp cũng như bạn đọc để giáo trình này có thể hoàn thiện hơn nữa về mặt nội dung cũng như hình thức trong lần tái bản sau. Bà Rịa – Vũng Tàu, ngày 02 tháng 01 năm 2016 Biên soạn Nguyễn Thị Mai MỤC LỤC TRANG CHƯƠNG TRÌNH MÔ ĐUN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mã số mô đun: MĐ15 VỊ TRÍ, TÍNH CHẤT CỦA MÔ ĐUN: -Vị trí: Mô đun này được học sau mô đun Tin học văn phòng, Lập trình căn bản, cơ sở dữ liệu. -Tính chất: Mô đun này yêu cầu phải có tư duy logic và các kiến thức về lập trình căn bản . MỤC TIÊU MÔ ĐUN: - Trình bày được các kiểu dữ liệu - Phân tích và xây dựng được thuật toán - Phân tích được các loại dữ liệu, giải thuật và kết hợp được dữ liệu và giải thuật. - Thực hiện được các thao tác trên các kiểu dữ liệu -Cài đặt được các thuật toán sắp xếp và tìm kiếm. - Cài đặt được các thuật toán trên các cấu trúc dữ liệu: mảng, danh sách, danh sách liên kết đơn. - Có tinh thần trách nhiệm, ý thức tổ chức kỷ luật, tác phong công nghiệp, tinh thần hợp tác trong công việc - Có ý chủ động, độc lập trong công việc, tự học cập nhật kiến thức, nâng cao trình độ chuyên môn. NỘI DUNG CỦA MÔ ĐUN: STT Tên các bài trong mô đun Thời gian Hình thức giảng dạy 1 Giới thiệu cấu trúc dữ liệu và giải thuật 3 Tích hợp 2 Làm việc với con trỏ 5 Tích hợp 3 Làm việc với kiểu cấu trúc 5 Tích hợp 4 Làm việc với kiểu tập tin 5 Tích hợp Kiểm tra bài 1,2,3,4 1 5 Thêm phần tử trong danh sách đặc 5 Tích hợp 6 Xóa phần tử trong danh sách đặc 4 Tích hợp Kiểm tra bài 5,6 1 7 Làm việc với danh sách liên kết 5 Tích hợp 8 Chèn phần tử trong danh sách liên kết 5 Tích hợp 9 Xóa phần tử trong danh sách liên kết 5 Tích hợp 10 Làm việc với ngăn xếp 7 Tích hợp 11 Làm việc với hàng đợi 7 Tích hợp Kiểm tra bài 7,8,9,10,11 1 12 Sử dụng các phương pháp sắp xếp 10 Tích hợp 13 Sử dụng các phương pháp tìm kiếm 5 Tích hợp Kiểm tra bài 12,13 1 Cộng 75 BÀI 1 GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Giới thiệu: Giải thuật là cách phân tích 1 vấn đề, từ thực tiễn cho tới chương trình, cách thiết kế một giải pháp cho vấn đề theo cách giải quyết bằng máy tính. Tiếp theo, các phương pháp phân tích, đánh giá độ phức tạp và thời gian thực hiện giải thuật . Qua bài học này sẽ giới thiệu một cách thật cụ thể về cấu trúc dữ liệu và giải thuật. Mục tiêu: - Trình bày được kiến thức cở bản về cấu trúc dữ liệu, giải thuật, kiểu dữ liệu, mô hình dữ liệu - Phân tích được giải thuật - Sử dụng được các phương pháp phân tích, thiết kế giải thuật. - Rèn luyện tính cẩn thận, kiên trì, sáng tạo. - Bảo đảm an toàn và vệ sinh cho người và thiết bị trong phòng máy. Nội dung 1. Mối liên hệ giải thuật và cấu trúc dữ liệu. 1.1. Giải thuật Giải thuật là các bước cần tác động theo một thứ tự nhất định nào đó trên cơ sở bổ dữ liệu vào để đạt dữ liệu ra đúng với chân lý của nó. Giải thuật Dữ liệu vào Input Dữ liệu ra Out put Dữ liệu ra 1.2. Dữ liệu Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu để xử lý. Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian hoặc dữ liệu đưa ra(output data). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho chương trình có ý nghĩa rất quan trọng trong toàn bộ hệ thống chương trình. Việc xây dựng cấu trúc dữ liệu quyết định rất lớn đến chất lượng cũng như công sức của người lập trình trong việc thiết kế, cài đặt chương trình. 1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật Mối quan hệ giữa cấu trúc dữ liệu và Giải thuật có thể minh họa bằng đẳng thức: Cấu trúc dữ liệu + Giải thuật = Chương trình Như vậy, khi đã có cấu trúc dữ liệu tốt, nắm vững giải thuật thực hiện thì việc thể hiện chương trình bằng một ngôn ngữ cụ thể chỉ là vấn đề thời gian. Khi có cấu trúc dữ liệu mà chưa tìm ra thuật giải thì không thể có chương trình và ngược lại không thể có giải thuật khi chưa có cấu trúc dữ liệu. Một chương trình máy tính chỉ có thể được hoàn thiện khi có đầy đủ cả Cấu trúc dữ liệu để lưu trữ dữ liệu và Giải thuật xử lý dữ liệu theo yêu cầu của bài toán đặt ra. 2. Kiểu dữ liệu, mô hình dữ liệu, kiểu dữ liệu trừu tượng 2.1.Khái niệm về kiểu dữ liệu Kiểu dữ liệu T có thể xem như là sự kết hợp của 2 thành phần: - Miền giá trị mà kiểu dữ liệu T có thể lưu trữ: V, - Tập hợp các phép toán để thao tác dữ liệu: O. T = Mỗi kiểu dữ liệu thường được đại diện bởi một tên (định danh). Mỗi phần tử dữ liệu cókiểu T sẽ có giá trị trong miền V và có thể được thực hiện các phép toán thuộc tập hợpcác phép toán trong O. Để lưu trữ các phần tử dữ liệu này thường phải tốn một số byte(s) trong bộ nhớ, sốbyte(s) này gọi là kích thước của kiểu dữ liệu. 2.2. Mô hình kiểu dữ liệu Hầu hết các ngôn ngữ lập trình đều có cung cấp các kiểu dữ liệu cơ sở. Tùy vào mỗi ngôn ngữ mà các kiểu dữ liệu cơ sở có thể có các tên gọi khác nhau song chung quy lại có những loại kiểu dữ liệu cơ sở như sau: - Kiểu số nguyên: Có thể có dấu hoặc không có dấu và thường có các kích thước sau: + Kiểu số nguyên 1 byte + Kiểu số nguyên 2 bytes + Kiểu số nguyên 4 bytes Kiểu số nguyên thường được thực hiện với các phép toán: O = {+, -, *, /, DIV, MOD, , =, =, } - Kiểu số thực: Thường có các kích thước sau: + Kiểu số thực 4 bytes + Kiểu số thực 6 bytes + Kiểu số thực 8 bytes + Kiểu số thực 10 bytes Kiểu số thực thường được thực hiện với các phép toán: O = {+, -, *, /, , =, =, } - Kiểu ký tự: Có thể có các kích thước sau: + Kiểu ký tự byte + Kiểu ký tự 2 bytes Kiểu ký tự thường được thực hiện với các phép toán: O = {+, -, , =, =, ORD,CHR, } - Kiểu chuỗi ký tự: Có kích thước tùy thuộc vào từng ngôn ngữ lập trình Kiểu chuỗi ký tự thường được thực hiện với các phép toán: O = {+, &, , =, =,Length, Trunc, } - Kiểu luận lý: Thường có kích thước 1 byte Kiểu luận lý thường được thực hiện với các phép toán: O = {NOT, AND, OR, XOR, ,=, =, } 2.3. Kiểu dữ liệu trừu tượng Kiểu dữ liệu trừu tượng là một mô hình toán học cùng với một tập hợp các phép toán trên nó. Có thể nói kiểu dữ liệu trừu tượng là một kiểu dữ liệu do chúng ta định nghĩa ở mức khái niệm (conceptual), nó chưa được cài đặt cụ thể bằng một ngôn ngữ lập trình. Khi cài đặt một kiểu dữ liệu trừu tượng trên một ngôn ngữ lập trình cụ thể, chúng ta phải thực hiện hai nhiệm vụ: - Biểu diễn kiểu dữ liệu trừu tượng bằng một cấu trúc dữ liệu hoặc một kiểu dữ liệu trừu tượng khác đã được cài đặt. - Viết các chương trình con thực hiện các phép toán trên kiểu dữ liệu trừu tượng mà ta thường gọi là cài đặt các phép toán. 3. Thiết kế và phân tích giải thuật 3.1. Thiết kế thuật toán. Người ta thường dùng phương pháp chia nhỏ bài toán hay chiến thuật chia để trị để thiết kế giải thuật. Nếu gọi bài toán là một modul chính thì ta chia modul chính thành các modul con rồi lại chia các modul con thành các modul con nhỏ hơn cho đến khi ta được các modul đã biết cách giải rồi. -> Chiến thuật chia để trị 3.2. Phân tích tính đúng đắn của giải thuật Ta phải chứng minh giải thuật là đúng Người ta thường làm : Cho chương trình chạy thử với một bộ dữ liệu đã biết kết quả Nếu kết quả chương trình khác với kết quả đã biết thì chắc chắn chương trình sai; nếu bằng thì cũng chưa có kết luận, do đó đây chỉ là phương pháp tìm ra cái sai mà chưa chứng minh cái đúng - Cho chạy chương trình rồi xem kết quả có phù hợp với thực tế không, nếu phù hợp thì hi  vọng đúng, còn không thì chắc chắn sai - Để chứng minh tính chính xác thì phải dùng toán học – hay dùng qui nạp (rất khó) 3.3. Phân tích tính đơn giản Tùy thuộc bài toán được dùng thường xuyên hay không, nếu chương trình chỉ dùng một ít lần rồi bỏ đi thì ta ưu tiên tính đơn giản Bài toán được sử dụng thường xuyên thì ta ưu tiên tính hiệu quả của thuật toán Tính hiệu quả thể hiện về hai mặt - Không gian (Chương trình bé chiếm ít bộ nhớ) - Thời gian (Chương trình chạy nhanh) 4. Một số ví dụ về thiết kế và phân tích giải thuật - Ví dụ 1: Tìm số lớn nhất trong một dãy các số từ a1,, an Input : Số nguyên dương N và dãy a1, a2, ,..., aN. Output : Tìm Max là giá trị lớn nhất của dãy đã cho Khởi tạo Max=a1. Với mỗi i, nếu ai > Max thì thay giá trị Max= ai Phân tích giải thuật như sau: B1. Nhập N và dãy a1, ..., aN B2. Đặt Max = a1, i = 2. B3. Nếu i > N thì đến B5. B4. Nếu ai > Max thì Max = ai. Đặt i=i+1 rồi quay b.3. B5. Đưa ra Max rồi kết thúc. -Ví dụ 2: Thiết kế và phân tích giải thuật giải phương trình bậc 2. Input: Các hệ số a,b,c. Ouput: Nghiệm của phương trình. Yêu cầu phải có công thức tính Delta = b2 – 4ac. Phân tích giải thuật như sau: B1. Nhập vào các hệ số a,b,c B2. Tính Delta = b2 – 4ac B3. - Nếu Delta > 0 nhảy đến B4. - Nếu Delta = 0 nhảy đến B4. - Nếu Delta < 0 nhảy đến B4. B4. Đưa ra số nghiệm của phương trình. Câu hỏi, bài tập: Thiết kế và phân tích giải thuật các bài toán sau: 1.1: Giải phương trình bậc nhất 1.2: Tìm giá trị lớn nhất và nhỏ nhất của hai số a,b 1.3: Tính tổng : s=1+2+3++ n Yêu cầu đánh giá - Phân tích được giải thuật của các bài toán - Sử dụng được các phương pháp phân tích, thiết kế giải thuật. BÀI 2 LÀM VIỆC VỚI CON TRỎ Giới thiệu: Con trỏ là đặc trưng và là một trong những sức mạnh lớn nhất trong lập trình C++. Vì thế việc tìm hiểu và vận dụng con trỏ là điều không thể thiếu đối với một lập trình viên. Bài viết này sẽ giúp cho người đọc có cái nhìn sâu sắc hơn về con trỏ trong lập trình C. Qua đó sẽ giúp các bạn sử dụng con trỏ một cách linh hoạt, tránh được những sai sót và làm việc một cách hiệu quả. Mục tiêu: - Trình bày được khái niệm con trỏ - Nêu được các thao tác trên con trỏ - Thực hiện được khai báo biến con trỏ - Trình bày và vận dụng các phép toán trên biến con trỏ vào các bài toán - Trình bày và vận dụng được con trỏ vào mảng một chiều và mảng nhiều chiều - Rèn luyện tính cẩn thận, kiên trì, sáng tạo, độc lập và hoạt động nhóm. - Bảo đảm an toàn và vệ sinh cho người và thiết bị trong phòng máy. Nội dung : 1. Biến con trỏ 1.1. Khái niệm con trỏ ( pointer ) Con trỏ là biến dùng để chứa địa chỉ của biến khác hoặc có thể là một hàm. Do có nhiều loại địa chỉ nên cũng có nhiều loại biến con trỏ. Con trỏ kiểu int dùng để chứa địa chỉ của kiểu int. Con trỏ kiểu float dùng để chứa địa chỉ kiểu float. - Muốn sử dụng được pointer, trước tiên phải có được địa chỉ của biến mà ta cần quan tâm bằng phép toán lấy địa chỉ & . Kết quả của phép lấy địa chỉ & sẽ là 1 phần tử hằng. 1.2. Khai báo một biến con trỏ: Ø Cú pháp: * Ø Ý nghĩa: Khai báo một biến có tên là Tên con trỏ dùng để chứa địa chỉ của các biến có kiểu dữ liệu Ø Ví dụ 1: Khai báo 2 biến a,b có kiểu int và 2 biến pa, pb là 2 biến con trỏ kiểu int. int a, b, *pa, *pb; Ø Ví dụ 2: Khai báo biến f kiểu float và biến pf là con trỏ float float f, *pf; Ghi chú: Nếu chưa muốn khai báo kiểu dữ liệu mà con trỏ ptr đang chỉ đến, ta sử dụng: void *ptr; Sau đó, nếu ta muốn con trỏ ptr chỉ đến kiểu dữ liệu gì cũng được. Tác dụng của khai báo này là chỉ dành ra 2 bytes trong bộ nhớ để cấp phát cho biến con trỏ ptr. 1.3. Gán địa chỉ của biến cho biến con trỏ Toán tử & dùng để định vị con trỏ đến địa chỉ của một biến đang làm việc. Ø Cú pháp: =& - Giải thích: Ta gán địa chỉ của biến Tên biến cho con trỏ Tên biến con trỏ. - Ví dụ: Gán địa chỉ của biến a cho con trỏ pa, gán địa chỉ của biến b cho con trỏ pb. pa=&a; pb=&b; - Lưu ý: Khi gán địa chỉ của biến tĩnh cho con trỏ cần phải lưu ý kiểu dữ liệu của chúng. Ví dụ sau đây không đúng do không tương thích kiểu: int Bien_Nguyen; float *Con_Tro_Thuc; ... Con_Tro_Thuc=&Bien_Nguyen; Phép gán ở đây là sai vì Con_Tro_Thuc là một con trỏ kiểu float (nó chỉ có thể chứa được địa chỉ của biến kiểu float); trong khi đó, Bien_Nguyen có kiểu int. 1.4. Cấp phát vùng nhớ cho biến con trỏ Trước khi sử dụng biến con trỏ, ta nên cấp phát vùng nhớ cho biến con trỏ này quản lý địa chỉ. Việc cấp phát được thực hiện nhờ các hàm malloc(), calloc() trong thư viện alloc.h. Ø Cú pháp các hàm: void *malloc(size_t size): Cấp phát vùng nhớ có kích thước là size. void *calloc(size_t nitems, size_t size): Cấp phát vùng nhớ có kích thước là nitems*size. Ø Ví dụ: Giả sử ta có khai báo: int a, *pa, *pb; pa = (int*)malloc(sizeof(int)); /* Cấp phát vùng nhớ có kích thước bằng với kích thước của một số nguyên */ pb= (int*)calloc(10, sizeof(int)); /* Cấp phát vùng nhớ có thể chứa được 10 số nguyên*/ 1.5. Giải phóng vùng nhớ cho biến con trỏ Một vùng nhớ đã cấp phát cho biến con trỏ, khi không còn sử dụng nữa, ta sẽ thu hồi lại vùng nhớ này nhờ hàm free(). Ø Cú pháp: void free(void *block) Ø Ý nghĩa: Giải phóng vùng nhớ được quản lý bởi con trỏ block. Ø Ví dụ: Ở ví dụ trên, sau khi thực hiện xong, ta giải phóng vùng nhớ cho 2 biến con trỏ pa & pb: free(pa); free(pb); 1.6. Một số phép toán trên con trỏ Ø Phép gán con trỏ: Hai con trỏ cùng kiểu có thể gán cho nhau. Ví dụ: int a, *p, *a ; float *f; a = 5 ; p = &a ; q = p ; /* đúng */ f = p ; /* sai do khác kiểu */ Ta cũng có thể ép kiểu con trỏ theo cú pháp: (*) Chẳng hạn, ví dụ trên được viết lại: int a, *p, *a ; float *f; a = 5 ; p = &a ; q = p ; /* đúng */ f = (float*)p; /* Đúng nhờ ép kiểu*/ Ø Cộng, trừ con trỏ với một số nguyên Ta có thể cộng (+), trừ (-) 1 con trỏ với 1 số nguyên N nào đó; kết quả trả về là 1 con trỏ. Con trỏ này chỉ đến vùng nhớ cách vùng nhớ của con trỏ hiện tại N phần tử. - Ví dụ: Cho đoạn chương trình sau: int *pa; pa = (int*) malloc(20); /* Cấp phát vùng nhớ 20 byte=10 số nguyên*/ int *pb, *pc; pb = pa + 7; pc = pb - 3; Ø Con trỏ NULL: là con trỏ không chứa địa chỉ nào cả. Ta có thể gán giá trị NULL cho 1 con trỏ có kiểu bất kỳ. 2. Con trỏ và mảng một chiều Giữa mảng và con trỏ có một sự liên hệ rất chặt chẽ. Những phần tử của mảng có thể được xác định bằng chỉ số trong mảng, bên cạnh đó chúng cũng có thể được xác lập qua biến con trỏ. - Ví dụ 1 : int A[5] ; * p ; P = A ; + Mảng bố trí 5 ô nhớ liên tiếp ( mỗi ô chiếm 2 byte ). + Tên mảng là 1 hằng địa chỉ ( không thay đổi được ), chính là địa chỉ của phần tử đầu tiên. => A tương đương với &A[0] (A + i ) tương đương với &A[i] *(A + i ) tương đương với A[i] p = A => p = &A[0] ( p trỏ tới phần tử A[0]) *(p + i ) tương đương với A[i]. =>bốn cách viết như sau là tương đương : A[i], * ( A + i ), * ( p + i ), p[i]. - Ví dụ 2 : Nhập 5 số nguyên vào 1 mảng gồm 5 phần tử ( a[5]) sau đó sắp xếp tăng dần #include #include #define n 5 main ( ) { int a[n], t , *p, i , j ; int s ; p = a ; for ( i = 0; i < n ; i ++ ) { printf(" a[%d] = " , i ) ; scanf( " %d ", p + i ); } /* sapxep tăng dan */ for ( i = 0 ; i < n-1 ; i ++ ) for ( j = i + 1 ; j<n ; j++) if (*(a + i)> * ( a + j ) ) { t = * ( a + i ) ; *(a + i ) = * ( a + j) ; *(a + j ) = t ; } printf(" mang sau khi sap xep"); for ( i = 0; i < n ; i ++ ) printf("%5d",a[i]); s= 0 ; for ( i=0 ; i < n ; ++i ) s= s+ a[ i]; printf ("\n Tong = %5d ", s ); getch ( ); } 3. Con trỏ và mảng nhiều chiều Ta có thể sử dụng con trỏ thay cho mảng nhiều chiều như sau: Giả sử ta có mảng 2 chiều và biến con trỏ như sau: int a[n][m]; int *contro_int; Thực hiện phép gán contro_int=a; Khi đó phần tử: a[0][0] được quản lý bởi contro_int; a[0][1] được quản lý bởi contro_int+1; a[0][2] được quản lý bởi contro_int+2; ... a[1][0] được quản lý bởi contro_int+m; a[1][1] được quản lý bởi contro_int+m+1; ... a[n][m] được quản lý bởi contro_int+n*m; Tương tự như thế đối với mảng nhiều hơn 2 chiều. Câu hỏi, bài tập 2.1. Kết quả của đoạn chương trình sau là gì? #include main() { int A[5] = {10, 20, 30, 40, 50}; int *pa = A; *pa += 2; printf("%d",*pa); } a. 10 c. 30 b. 12 d. 32 2.2. Giả sử có các khai báo biến và các phép gán như sau : int i, *p; float x, *q; 1. p = &i; 2. q = i; 3. p = &x; 4. q = p; 5. q = & x; Các phép gán không hợp lệ là: a. 1,3,4,5 c. 1,2,4 b. 2,3 d. 2, 3,4 2.3. Lập trình thực hiện các công việc sau : - Nhập vào mảng một chiều một dãy số nguyên a1,a2,a3an - Tính trung bình của các nguyên tử đã nhập vào - Tìm và in giá trị lớn nhất, nhỏ nhất của mảng - Xuất ra dãy các số chăn, số lẻ Yêu cầu đánh giá - Biết được khai báo biến con trỏ và các phép toán trên con trỏ - Áp dụng các phép toán trên biến con trỏ vào các bài toán - Áp dụng được con trỏ vào mảng một chiều và mảng nhiều chiều - Viết được chương trình và chạy, kiểm tra được kết quả BÀI 3 LÀM VIỆC VỚI KIỂU CẤU TRÚC Giới thiệu: Bên cạnh những kiểu dữ liệu có sẵn như char, int, float, C cũng cho phép chúng ta tự định nghĩa kiểu dữ liệu để phù hợp với mục đích cũng như tạo mã nguồn tối ưu nhất. Bài viết này sẽ tiếp tục trình bày về kiểu dữ liệu người dùng tự định nghĩa là struct. Mục tiêu: - Trình bày được khái niệm biến cấu trúc - Khai báo được biến kiểu cấu trúc - Truy cập được đến các thành phần của cấu trúc - Nhập dữ liệu được cho biến cấu trúc - Vận dụng kiểu cấu trúc làm các bài toán trong lập trình - Rèn luyện tính cẩn thận, kiên trì, sáng tạo, độc lập và hoạt động nhóm. - Bảo đảm an toàn và vệ sinh cho người và thiết bị trong phòng máy. Nội dung chính: 1. Khái niệm cấu trúc -Kiểu cấu trúc (Structure) là kiểu dữ liệu bao gồm nhiều thành phần có thể thuộc nhiều kiểu dữ liệu khác nhau. Các thành phần được truy cập qua tên - Sự khác biệt giữa kiểu cấu trúc và kiểu mảng là: các phần tử của mảng là cùng kiểu còn các phần tử của kiểu cấu trúc có thể có kiểu khác nhau. 2. Khai báo kiểu cấu trúc. struct [tên_cấu_trúc] { khai báo các thành phần } [danh sách các biến cấu trúc]; Trong đó: - struct là từ khóa đứng trước một khai báo cấu trúc, - Tên_cấu_trúc là một tên hợp lệ được dùng làm tên cấu trúc; - danh sách các biến cấu trúc: liệt kê các biến có kiểu cấu trúc vừa khai báo, - Khai báo các thành phần: là một danh sách các khai báo tên và kiểu dữ liệu của các thành phần tạo nên cấu trúc này. ® Ví dụ câu lệnh struct hoc_sinh { char ho_ten[20]; float diem; } dshs[100]; khai báo một kiểu cấu trúc có tên là hoc_sinh gồm hai thành phần: + Họ tên học sinh (ho_ten) + Ðiểm thi (diem) của học sinh. + Kèm theo khai báo kiểu cấu trúc, chúng ta định nghĩa hai biến: hs là một biến đơn, còn dshs là một mảng có các thành phần là cấu trúc hoc_sinh. Cú pháp Ngôn ngũ C cho phép ta đặt lại tên kiểu cho riêng mình bằng câu lệnh như sau: Ø Đặt tên kiểu dữ liệu bằng typedef - Cú pháp: typedef struct [kiểu_đã_có ] [tên_kiểu_mới]; Trong đó : + Kiểu_đã_có là kiểu dữ liệu mà ta muốn