- Ngăn xếp, hàng đợi và danh sách móc nối. - Những nguyên lý này được coi như nền tảng tư tưởng của phương pháp lập trình cấu trúc đã được tích hợp trong các ngôn ngữ lập trình. - Các nguyên lý cơ bản được giới thiệu trong chương này bao gồm: 9 Nguyên lý lệnh - lệnh có cấu trúc - cấu trúc dữ liệu. - SƠ LƯỢC VỀ LỊCH SỬ LẬP TRÌNH CẤU TRÚC Lập trình là một trong những công việc nặng nhọc nhất của khoa học máy tính. - Sau đó Dahl, Hoare, Dijiksta đã phát triển thành ngôn ngữ lập trình cấu trúc. - CẤU TRÚC LỆNH, LỆNH CÓ CẤU TRÚC, CẤU TRÚC DỮ LIỆU 1.2.1. - Cấu trúc lệnh (cấu trúc điều khiển) Mỗi chương trình máy tính về bản chất là một bản mã hoá thuật toán. - Các thao tác trong một ngôn ngữ lập trình cụ thể được điều khiển bởi các lệnh hay các cấu trúc điều khiển, còn các đối tượng chịu thao tác thì được mô tả và biểu diễn thông qua các cấu trúc dữ liệu. - Trong các ngôn ngữ lập trình cấu trúc, những cấu trúc lệnh sau được sử dụng để xây dựng chương trình. - Cấu trúc lặp FOR For (E1. - 6 Chương 1: Đại cương về kỹ thuật lập trình cấu trúc 1.2.2. - là cấu trúc con trong thân của else. - Cấu trúc dữ liệu Các ngôn ngữ lập trình cấu trúc nói chung đều giống nhau về cấu trúc lệnh và cấu trúc dữ liệu. - Điểm khác nhau duy nhất giữa các ngôn ngữ lập trình cấu trúc là phương pháp đặt tên, cách khai báo, cú pháp câu lệnh và tập các phép toán được phép thực hiện trên các cấu trúc dữ liệu cụ thể. - 7 Chương 1: Đại cương về kỹ thuật lập trình cấu trúc Ví dụ 1.1. - 8 Chương 1: Đại cương về kỹ thuật lập trình cấu trúc a-=n Ù a = a - n. - 9 Chương 1: Đại cương về kỹ thuật lập trình cấu trúc Ví dụ 1.2: Viết chương trình kiểm tra các toán tử thao tác bít. - R 10 Chương 1: Đại cương về kỹ thuật lập trình cấu trúc. - Thao tác trên các kiểu dữ liệu có cấu trúc Tập thao tác trên string: char *strchr(const char *s, int c. - 11 Chương 1: Đại cương về kỹ thuật lập trình cấu trúc int strcmp(const char *s1, const char *s2. - Tập thao tác trên cấu trúc: Định nghĩa cấu trúc: struct struct_name{ type_1 parameter_name_1. - Phép truy nhập tới thành phần cấu trúc: 12 Chương 1: Đại cương về kỹ thuật lập trình cấu trúc struct_parameter_name.parameter_name. - Phép tham trỏ tới thành phần của con trỏ cấu trúc: pointer_struct_parameter_name. - 13 Chương 1: Đại cương về kỹ thuật lập trình cấu trúc #include #include #include #include int a, b. - 14 Chương 1: Đại cương về kỹ thuật lập trình cấu trúc a=1. - Cần sớm phát hiện những mâu thuẫn giữa cấu trúc dữ liệu và thao tác để kịp thời khắc phục. - Tuy nhiên, trên thực tế có nhiều lỗi nhập nhằng giữa phép toán và cấu trúc dữ liệu mà chúng ta cần hiểu rõ. - Ngược lại, ta không 15 Chương 1: Đại cương về kỹ thuật lập trình cấu trúc thể lấy modul của hai số thực hoặc thực hiện các thao tác dịch chuyển bít trên nó, vì những thao tác đó không nằm trong định nghĩa của kiểu. - 57 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối Thao tác Insert: thêm X vào hàng đợi Q. - 58 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối else i = pq->front+1. - if(i==MAX-1) 60 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối i=0. - 61 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối case ‘4’: printf("\n Hang moi nhap. - DANH SÁCH LIÊN KẾT ĐƠN 3.3.1. - Bản chất động là một trong những tính chất chính của danh sách móc nối. - Mỗi đỉnh trong danh sách đều gồm hai phần. - Dữ liệu có thể chỉ là một biến đơn hoặc là một cấu trúc (hoặc con trỏ cấu trúc) có kiểu nào đó. - Vì vậy có thể dễ dàng sử dụng các đỉnh của danh sách qua một cấu trúc tự trỏ hoặc đệ qui. - 63 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối 9 Thiết lập liên kết với đỉnh mới. - 9 Di chuyển con trỏ tới phần tử cuối danh sách. - Thêm node mới vào cuối danh sách. - 64 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối void Push_Bottom( NODEPTR *plist, int x. - chuyển con trỏ tới cuối danh sách while (q-> next. - q là node cuối cùng của danh sách liên kết q. - Phép thêm phần tử vào giữa danh sách liên kết đơn. - Trong trường hợp còn lại, ta thực hiện như sau: 9 Dùng node p trỏ tới đầu danh sách. - node p trỏ tới đầu danh sách. - danh sách rỗng (*plist. - danh sách có một node Del_Top(plist). - else { 66 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối p = *plist. - p là node cuối danh sách. - Loại bỏ node ở giữa danh sách (trước node p): Cần để ý rằng, nếu trước node p là NULL (p->next==NULL) thì ta không thực hiện loại bỏ được. - Làm như vậy, chúng ta thu được một cấu trúc dữ liệu mới gọi là danh sách liên kết kép. - định nghĩa con trỏ tới node 67 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối Null L I R L I R L I R Null Hình 3.8. - Mô tả một danh sách liên kết kép. - Các thao tác trên danh sách liên kết kép cũng tương tự như danh sách liên kết đơn. - Thao tác thêm node mới vào đầu danh sách liên kết kép: 9 Cấp phát bộ nhớ cho node mới. - 9 Nếu danh sách không rỗng chúng ta thực hiện như sau. - Chuyển con trỏ tới node cuối trong danh sách. - //gán giá trị thích hợp //chuyển con trỏ tới node cuối danh sách 68 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối q = *plist. - //q là node cuối cùng trong danh sách q. - 9 Dùng node p trỏ tới đầu danh sách. - 69 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối 9 Loại bỏ liên kết với node p. - //p là node đầu tiên trong danh sách (*plist. - 9 Nếu danh sách có nhiều hơn một node thì. - chuyển con trỏ tới node cuối danh sách while (p->right!=NULL) p =p->right. - p là node cuối của danh sách q = p ->left. - 70 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối 9 Nếu node p là node cuối thì cũng không thể loại bỏ. - 9 Những ứng dụng lớn thường được cài đặt trên các cấu trúc dữ liệu động. - 72 Chương 3: Ngăn xếp, hàng đợi và danh sách móc nối BÀI TẬP CHƯƠNG 3 Bài 1. - Ví dụ: cấu trúc tổ chức thư mục (directory) của dos là một cấu trúc cây. - Ví dụ về một cây thư mục 77 Chương 4: Cấu trúc dữ liệu cây (Tree) Một cây được gọi là rỗng nếu nó không có bất kỳ một node nào. - nếu node có thực và chưa có node trái 84 Chương 4: Cấu trúc dữ liệu cây (Tree) else p ->left = Makenode(x. - 85 Chương 4: Cấu trúc dữ liệu cây (Tree) o Thiết lập liên kết mới cho node p. - 87 Chương 4: Cấu trúc dữ liệu cây (Tree) return(p. - 88 Chương 4: Cấu trúc dữ liệu cây (Tree) 4.5.2. - 89 Chương 4: Cấu trúc dữ liệu cây (Tree) 4.6. - Dưới đây là một cài đặt cụ thể cho cây nhị phân tìm kiếm bằng danh sách móc nối. - 90 Chương 4: Cấu trúc dữ liệu cây (Tree. - 91 Chương 4: Cấu trúc dữ liệu cây (Tree) rp->right = p->right. - 92 Chương 4: Cấu trúc dữ liệu cây (Tree) p->left=NULL. - 93 Chương 4: Cấu trúc dữ liệu cây (Tree) Postrav(proot->right). - else { 94 Chương 4: Cấu trúc dữ liệu cây (Tree) f=p. - 95 Chương 4: Cấu trúc dữ liệu cây (Tree) printf("\n 0-Thoat khoi chuong trinh. - 96 Chương 4: Cấu trúc dữ liệu cây (Tree) if(ptree==NULL) printf("\n Cay rong. - 97 Chương 4: Cấu trúc dữ liệu cây (Tree) NHỮNG NỘI DUNG CẦN GHI NHỚ 9 Định nghĩa cây, cây nhị phân, cây cân bằng và cây hoàn toàn cân bằng. - 98 Chương 4: Cấu trúc dữ liệu cây (Tree) BÀI TẬP CHƯƠNG 4 Bài 1. - 99 Chương 4: Cấu trúc dữ liệu cây (Tree) Bài 5. - Ví dụ: với hình trên file input & output được tổ chức như sau: cay.in cay.out Chương 5: Đồ thị (Graph) CHƯƠNG 5: ĐỒ THỊ (GRAPH) Đồ thị là một cấu trúc dữ liệu rời rạc nhưng lại có ứng dụng hiện đại. - 9 Các thuật toán tìm kiếm trên đồ thị. - Đồ thị (Graph) là một cấu trúc dữ liệu rời rạc bao gồm các đỉnh và các cạnh nối các cặp đỉnh này. - b c d a f e g Hình 5.6 Đồ thị vô hướng G. - Đường đi trên đồ thị. - Ma trận kề, ma trận trọng số Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau, ta cần phải biểu diễn đồ thị trên máy tính, đồng thời sử dụng những cấu trúc dữ liệu thích hợp để mô tả đồ thị. - Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả thuật toán. - Vì vậy, lựa chọn cấu trúc dữ liệu thích hợp biểu diễn đồ thị sẽ phụ thuộc vào từng bài toán cụ thể. - Đồ thị trọng số G. - Danh sách cạnh (cung ) Trong trường hợp đồ thị thưa (đồ thị có số cạnh m ≤ 6n), người ta thường biểu diễn đồ thị dưới dạng danh sách cạnh. - Danh sách cạnh (cung) của đồ thị vô hướng, đồ thị có hướng, đồ thị trọng số: Dau Cuoi Dau Cuoi Dau Cuoi Trongso Danh sách cạnh cung hình Đồ thị có hướng Danh sách trọng số 109 Chương 5: Đồ thị (Graph) 5.2.3. - Để biểu diễn List(i), ta có thể dùng các kiểu dữ liệu kiểu tập hợp, mảng hoặc danh sách liên kết. - Đồ thị vô hướng G Kết quả duyệt