Giáo trình Kỹ thuật: cấu trúc dữ liệu ngành hệ thống thông tin thiết kế

Tìm hiểu giáo trình cấu trúc dữ liệu chuyên ngành hệ thống thông tin và thiết kế trang web công nghệ thông tin với kiến thức chuyên sâu và ứng dụng thực tế.

• Tác giả: Võ Đào Thị Hồng Tuyết
• Trường học: Trường Cao Đẳng Kinh Tế Kỹ Thuật Thành Phố Hồ Chí Minh
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Cấu Trúc Dữ Liệu Và Giải Thuật
• Loại tài liệu: Giáo trình
• Năm xuất bản: 2020
• Địa điểm: Thành Phố Hồ Chí Minh

Tóm tắt

I. Giới thiệu về Cấu Trúc Dữ Liệu trong Hệ Thống Thông Tin

Cấu trúc dữ liệu là một trong những môn học cơ bản và quan trọng nhất đối với sinh viên ngành Công Nghệ Thông Tin. Đây là nền tảng thiết yếu giúp sinh viên hiểu rõ cách lưu trữ và quản lý dữ liệu hiệu quả trong máy tính. Nắm vững cấu trúc dữ liệu không chỉ giúp xây dựng phần mềm chất lượng cao mà còn tối ưu hóa hiệu suất của các ứng dụng. Mối liên hệ chặt chẽ giữa cấu trúc dữ liệu và thuật toán quyết định đến thành công của mỗi dự án phát triển phần mềm. Giáo trình này được biên soạn theo chương trình đào tạo cấp cao đẳng tại Trường Cao Đẳng Kinh Tế Kỹ Thuật Thành phố Hồ Chí Minh, nhằm trang bị cho sinh viên những kiến thức cơ bản và thực tiễn nhất về lĩnh vực này.

1.1. Khái niệm Cấu Trúc Dữ Liệu

Cấu trúc dữ liệu là phương pháp tổ chức, lưu trữ và quản lý dữ liệu trong máy tính một cách khoa học và hiệu quả. Nó định nghĩa cách dữ liệu được sắp xếp, truy cập và thao tác để đạt hiệu suất tối ưu. Lựa chọn đúng cấu trúc dữ liệu ảnh hưởng trực tiếp đến tốc độ xử lý và tiêu thụ tài nguyên của ứng dụng, từ đó tác động lớn đến thiết kế phần mềm và hệ thống thông tin hiệu quả.

1.2. Tầm Quan Trọng trong Công Nghệ Thông Tin

Hiểu và vận dụng các cấu trúc dữ liệu là cơ sở để tiếp cận thiết kế và xây dựng phần mềm chuyên nghiệp cũng như sử dụng các công cụ lập trình hiện đại. Cấu trúc dữ liệu và thuật toán không thể tách rời nhau, chúng có mối liên hệ đặc biệt với nhau. Việc lựa chọn một cấu trúc dữ liệu thích hợp sẽ quyết định lựa chọn thuật toán áp dụng, từ đó ảnh hưởng đến hiệu năng của toàn hệ thống thông tin.

II. Nội Dung Chính của Giáo Trình Cấu Trúc Dữ Liệu

Giáo trình Cấu Trúc Dữ Liệu gồm 4 chương chính, trình bày toàn diện về các cấu trúc dữ liệu và giải thuật cơ bản trong tin học. Mỗi chương được thiết kế để xây dựng kiến thức từ cơ bản đến nâng cao, giúp sinh viên nắm vững lý thuyết và ứng dụng thực tiễn. Ngoài ra, giáo trình còn cung cấp phụ lục hướng dẫn chi tiết, mã nguồn tham khảo và các tài liệu tham khảo hữu ích. Mục tiêu chính là trang bị cho sinh viên ngành Hệ Thống Thông Tin, Thiết Kế Trang Web, Công Nghệ Thông Tin những kỹ năng cần thiết để thành công trong sự nghiệp.

2.1. Chương 1 Thiết Kế Giải Thuật và Thuật Giải Đệ Qui

Chương 1 trình bày về phân tích và thiết kế thuật toán, bắt đầu từ việc phân tích vấn đề thực tiễn cho đến chuyển đổi thành chương trình máy tính. Nội dung tập trung vào đệ qui - một khái niệm cơ bản trong toán học và lập trình. Sử dụng thuật giải đệ qui cho phép giải quyết các vấn đề phức tạp chỉ bằng vài câu lệnh, đặc biệt là những vấn đề mang bản chất đệ qui.

2.2. Chương 2 4 Các Thuật Giải và Cấu Trúc Dữ Liệu Chuyên Biệt

Chương 2 đề cập thuật giải sắp xếp và tìm kiếm, các kỹ thuật cơ sở cho lập trình máy tính. Chương 3, 4 trình bày các cấu trúc dữ liệu thông dụng như mảng, danh sách liên kết, ngăn xếp, hàng đợi và cây. Các cấu trúc này gần gũi với thực tiễn và được sử dụng rộng rãi trong thiết kế hệ thống và phát triển ứng dụng.

III. Phương Pháp Giảng Dạy và Ngôn Ngữ Lập Trình

Giáo trình này được biên soạn với phương pháp lý thuyết kết hợp thực hành để giúp sinh viên hiểu sâu sắc hơn. Các cấu trúc dữ liệu và giải thuật có thể được biểu diễn bằng bất kỳ ngôn ngữ lập trình hiện đại nào. Tuy nhiên, để cung cấp phân tích sâu sắc và kết quả thực tế, tác giả chọn sử dụng ngôn ngữ lập trình C làm công cụ chính để minh hoạ. Ngôn ngữ C được coi là nền tảng của lập trình hiện đại, giúp sinh viên hiểu rõ cơ chế hoạt động của cấu trúc dữ liệu ở mức thấp. Mỗi chương kết thúc bằng câu hỏi và bài tập để sinh viên ôn luyện và tự kiểm tra kiến thức.

3.1. Sử Dụng Ngôn Ngữ C trong Giáo Trình

Ngôn ngữ lập trình C được lựa chọn vì khả năng biểu diễn chi tiết các cấu trúc dữ liệu và thuật toán. Sinh viên không chỉ học lý thuyết mà còn thực hành cài đặt các cấu trúc dữ liệu và giải thuật một cách cụ thể. Ngoài kiến thức cơ bản về tin học, sinh viên cần có kiến thức vững chắc về ngôn ngữ lập trình C để tận dụng tối đa giáo trình này.

3.2. Cấu Trúc Các Phần Bài Giảng

Mỗi phần bài giảng được chia thành các phần nhỏ hợp lý với heading rõ ràng và hình ảnh minh hoạ. Cuối mỗi chương, sinh viên sẽ tìm thấy danh mục hình ảnh, câu hỏi ôn tập và bài tập thực hành. Tài liệu cũng bao gồm phụ lục hướng dẫn trả lời và mã nguồn tham khảo để hỗ trợ quá trình học tập hiệu quả.

IV. Ứng Dụng và Mục Tiêu Học Tập

Giáo trình Cấu Trúc Dữ Liệu được thiết kế cho sinh viên cấp cao đẳng của các ngành Hệ Thống Thông Tin, Thiết Kế Trang Web và Công Nghệ Thông Tin (Ứng Dụng Phần Mềm). Mục tiêu chính là trang bị cho sinh viên kiến thức và kỹ năng để tìm hiểu, thiết kế, và xây dựng các ứng dụng phần mềm hiệu quả và tối ưu. Sinh viên sẽ học cách phân tích bài toán, lựa chọn cấu trúc dữ liệu phù hợp, thiết kế giải thuật tối ưu và cài đặt chúng trên máy tính. Những kỹ năng này là nền tảng vững chắc cho sự phát triển sự nghiệp trong lĩnh vực Công Nghệ Thông Tin và phát triển phần mềm.

4.1. Mục Tiêu Chính của Giáo Trình

Giáo trình nhằm giúp sinh viên nắm vững các khái niệm về cấu trúc dữ liệu, giải thuật cơ bản, phương pháp sắp xếp và tìm kiếm. Sinh viên sẽ hiểu được mối liên hệ giữa cấu trúc dữ liệu và hiệu suất ứng dụng, từ đó có khả năng lựa chọn đúng cấu trúc dữ liệu cho từng bài toán cụ thể trong phát triển hệ thống thông tin.

4.2. Kỹ Năng Thực Tiễn Đạt Được

Sau khi hoàn thành giáo trình, sinh viên sẽ có khả năng cài đặt các cấu trúc dữ liệu như mảng, danh sách liên kết, ngăn xếp, hàng đợi và cây. Sinh viên cũng sẽ thành thạo các thuật giải tìm kiếm và sắp xếp cơ bản, biết cách tối ưu hóa code và phân tích độ phức tạp thuật toán. Những kỹ năng này là chìa khóa để thành công trong lập trình, thiết kế phần mềm và phát triển ứng dụng chuyên nghiệp.

Trích đoạn nội dung tài liệu

Chương 1: Thiết kế giải thuật – thuật giải đệ qui Bước 5: Kiểm chứng và hoàn thiện chương trình. (thử nghiệm bằng nhiều số liệu và đánh giá) Kỹ thuật lập trình I-P-O Cycle (Input-Pprocess-Output Cycle) (Quy trình nhập-xử lý-xuất) Quy trình xử lý cơ bản của máy tính gồm I-P-O. Input Output Process Hình 1. 1 Quy trình xử lý cơ bản của máy tính Ví dụ 1: Xác định Input, Process, Output của việc làm 1 ly nước chanh nóng Input : ly, đường, chanh, nước nóng, muỗng.

Process : - cho hỗn hợp đường, chanh, nước nóng vào ly. - dùng muỗng khuấy đều. Output : ly chanh nóng đã sẵn sàng để dùng. Ví dụ 2: Xác định Input, Process, Output của chương trình tính tiền lương công nhân tháng 10/2002 biết rằng lương = lương căn bản * ngày công Input : lương căn bản, ngày công Process : nhân lương căn bản với ngày công Output : lương Ví dụ 3: Xác định Input, Process, Output của chương trình giải phương trình bậc nhất ax + b = 0 Input : hệ số a, b Process : chia – b cho a Output : nghiệm x Ví dụ 4: Xác định Input, Process, Output của chương trình tìm số lớn nhất của 2 số a và b.

Input : a, b Process : Nếu a > b thì Output = a lớn nhất Ngược lại Output = b lớn nhất Với mỗi vấn đề cần giải quyết, ta có thể tìm ra nhiều thuật toán khác nhau. Có những thuật toán thiết kế đơn giản, dễ hiểu, dễ lập trình và sửa lỗi, tuy nhiên thời gian KHOA CÔNG NGHỆ THÔNG TIN Trang 3 Chương 1: Thiết kế giải thuật – thuật giải đệ qui thực hiện lớn và tiêu tốn nhiều tài nguyên máy tính. Ngược lại, có những thuật toán thiết kế và lập trình rất phức tạp, nhưng cho thời gian chạy nhanh hơn, sử dụng tài nguyên máy tính hiệu quả hơn. Khi đó, câu hỏi đặt ra là ta nên lựa chọn giải thuật nào để thực hiện? Đối với những chương trình chỉ được thực hiện một vài lần thì thời gian chạy không phải là tiêu chí quan trọng nhất.

Đối với bài toán kiểu này, thời gian để lập trình viên xây dựng và hoàn thiện thuật toán đáng giá hơn thời gian chạy của chương trình và như vậy những giải thuật đơn giản về mặt thiết kế và xây dựng nên được lựa chọn. Đối với những chương trình được thực hiện nhiều lần thì thời gian chạy của chương trình đáng giá hơn rất nhiều so với thời gian được sử dụng để thiết kế và xây dựng nó. Khi đó, lựa chọn một giải thuật có thời gian chạy nhanh hơn (cho dù việc thiết kế và xây dựng phức tạp hơn) là một lựa chọn cần thiết. Trong thực tế, trong giai đoạn đầu của việc giải quyết vấn đề, một giải thuật đơn giản thường được thực hiện trước như là 1 nguyên mẫu (prototype), sau đó nó sẽ được phân tích, đánh giá, và cải tiến thành các phiên bản tốt hơn.

Thuật giải đệ quy 2.Khái niệm về đệ qui Khái niệm: Vấn đề đệ quy là vấn đề được định nghĩa bằng chính nó. 2 Mô tả các bước tính tổng S(n)=1+2+3+…+n với S(10) và S(11) KHOA CÔNG NGHỆ THÔNG TIN Trang 4 Chương 1: Thiết kế giải thuật – thuật giải đệ qui 2 điều kiện quan trọng: - Tồn tại bước đệ quy. - Điều kiện dừng.Thiết kế giải thuật đệ qui 2.Hệ thức truy hồi Khái niệm: Hệ thức truy hồi của 1 dãy An là công thức biểu diễn phần tử An thông qua 1 hoặc nhiều số hạng trước của dãy. 3 Mô tả hệ thức truy hồi Ví dụ 1: Vi trùng cứ 1 giờ lại nhân đôi.

Vậy sau 5 giờ sẽ có mấy con vi trùng nếu ban đầu có 2 con? Giải pháp - Gọi Vh là số vi trùng tại thời điểm h. - Ta có: • Vh = 2Vh-1 • V0 = 2 Đệ quy tuyến tính với V(h)=2*V(h-1) và điều kiện dừng V(0) = 2 Ví dụ 2: Gửi ngân hàng 1000 USD, lãi suất 12%/năm. Số tiền có được sau 30 năm là bao nhiêu? Giải pháp - Gọi Tn là số tiền có được sau n năm. - Ta có: • Tn = Tn-1 + 0.Chia để trị (divide & conquer) Khái niệm: - Chia bài toán thành nhiều bài toán con.

KHOA CÔNG NGHỆ THÔNG TIN Trang 5 Chương 1: Thiết kế giải thuật – thuật giải đệ qui - Giải quyết từng bài toán con. - Tổng hợp kết quả từng bài toán con để ra lời giải. Thuật toán mô tả chia để trị: { if (P đủ nhỏ) Xử lý P else { Chia P  P1, P2, …, Pn for (int i=1;i<=n;i++) Trị(Pi); Tổng hợp kết quả } } Ví dụ 1: Cho dãy A đã sắp xếp thứ tự tăng. Tìm vị trí phần tử x trong dãy (nếu có) Giải pháp - mid = (l + r) / 2; - Nếu A[mid] = x  trả về mid.

- Ngược lại • Nếu x < A[mid]  tìm trong đoạn [l, mid – 1] • Ngược lại  tìm trong đoạn [mid + 1, r] Sử dụng đệ quy nhị phân. Ví dụ 2: Tính tích 2 chuỗi số cực lớn X và Y Giải pháp - X = X2n-1…XnXn-1…X0, Y = Y2n-1…YnYn-1…Y0 - Đặt XL=X2n-1…Xn, XN=Xn-1…X0  X=10nXL+XN - Đặt YL=Y2n-1…Yn, YN=Yn-1…Y0  Y=10nYL+YN X*Y = 102nXLYL + 10n(XLYL+XNYN)+XNYN KHOA CÔNG NGHỆ THÔNG TIN Trang 6 Chương 1: Thiết kế giải thuật – thuật giải đệ qui và XLYL+XNYN = (XL-XN)(YN-YL)+XLYL+XNYN Nhân 3 số nhỏ hơn (độ dài ½) đến khi có thể nhân được ngay.Lần ngược (Backtracking) Khái niệm - Tại bước có nhiều lựa chọn, ta chọn thử 1 bước để đi tiếp. - Nếu không thành công thì “lần ngược” chọn bước khác. - Nếu đã thành công thì ghi nhận lời giải này đồng thời “lần ngược” để truy tìm lời giải mới.

- Thích hợp giải các bài toán kinh điển như bài toán 8 hậu và bài toán mã đi tuần. 4 Mô tả lần ngược (Backtracking) 2.Áp dụng thuật giải đệ qui Một số bài toán kinh điển Hình 1. 5 Một số bài toán kinh điển 2. Tháp Hà Nội Mô tả bài toán: Có 3 cột A, B và C và cột A hiện có N đĩa.

Tìm cách chuyển N đĩa từ cột A sang cột C sao cho: - Một lần chuyển 1 đĩa - Đĩa lớn hơn phải nằm dưới. - Có thể sử dụng các cột A, B, C làm cột trung gian. KHOA CÔNG NGHỆ THÔNG TIN Trang 7 Chương 1: Thiết kế giải thuật – thuật giải đệ qui Hình 1. 6 Bài toán tháp Hà Nội 2.

Tám hậu Mô tả bài toán: Cho bàn cờ vua kích thước 8x8. Hãy đặt 8 hoàng hậu lên bàn cờ này sao cho không có hoàng hậu nào “ăn” nhau: - Không nằm trên cùng dòng, cùng cột - Không nằm trên cùng đường chéo xuôi, ngược. Các dòng Các cột Các đường chéo xuôi Các đường chéo ngược Các dòng Hình 1. 7 Bài toán tám hậu KHOA CÔNG NGHỆ THÔNG TIN Trang 8 Chương 1: Thiết kế giải thuật – thuật giải đệ qui DANH MỤC HÌNH ẢNH CHƯƠNG 1 Hình 1.

1 Quy trình xử lý cơ bản của máy tính. 2 Mô tả các bước tính tổng S(n)=1+2+3+…+n với S(10) và S(11). 3 Mô tả hệ thức truy hồi. 4 Mô tả lần ngược (Backtracking).

5 Một số bài toán kinh điển. 6 Bài toán tháp Hà Nội. 7 Bài toán tám hậu. 8 KHOA CÔNG NGHỆ THÔNG TIN Trang 9 Chương 1: Thiết kế giải thuật – thuật giải đệ qui CÂU HỎI VÀ BÀI TẬP 1.

Hãy trình bày một số ví dụ về định nghĩa theo kiểu đệ qui. Một chương trình đệ qui khi gọi chính nó thì bài toán khi đó có kích thước như thế nào so với bài toán ban đầu? Để chương trình đệ qui không bị lặp vô hạn thì cần phải làm gì? 3. Hãy cho biết tại sao khi chương trình có thể viết dưới dạng lặp hoặc cấu trúc khác thì không nên sử dụng đệ qui? 4. Viết chương trình đệ qui tính tổng các số lẻ trong khoảng từ 1 đến 2n+1.

Hãy cho biết các bước thực hiện chuyển đĩa trong bài toán tháp Hà Nội với số lượng đĩa là 5. KHOA CÔNG NGHỆ THÔNG TIN Trang 10 Chương 2 : Các thuật giải sắp xếp và tìm kiếm CHƯƠNG 2: CÁC THUẬT GIẢI SẮP XẾP VÀ TÌM KIẾM Mục tiêu: Trình bày được các giải thuật sắp xếp và tìm kiếm. Phân biệt được các thuật toán sắp xếp và tìm kiếm. Sinh viên có khả năng cài đặt được các thuật toán sắp xếp và tìm kiếm.

Một số phương pháp sắp xếp đơn giản Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử Sắp xếp dãy số a1 , a2 ,. ,aN là thực hiện việc bố trí lại các phần tử sao cho hình thành được dãy mới ak1 , ak2 ,. ,akN có thứ tự ( giả sử xét thứ tự tăng) nghĩa là aki  aki-1. Mà để quyết định được những tình huống cần thay đổi vị trí các phần tử trong dãy, cần dựa vào kết quả của một loạt phép so sánh.

Chính vì vậy, hai thao tác so sánh và gán là các thao tác cơ bản của hầu hết các thuật toán sắp xếp. Đổi chỗ trực tiếp (Interchange Sort) a. Khái niệm nghịch thế: - Xét một mảng các số a[0], a[1], … a[n-1] - Nếu có i<j và a[i] > a[j], thì ta gọi đó là một nghịch thế - Mảng chưa sắp xếp sẽ có nghịch thế - Mảng đã có thứ tự sẽ không chứa nghịch thế - a[0] a[1]  …  a[n -1] b. Ý tưởng Nhận xét: Để sắp xếp một dãy số, ta có thể xét các nghịch thế có trong dãy và làm triệt tiêu dần chúng đi Ý tưởng: - Xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế - Lặp lại xử lý trên với các phần tử tiếp theo trong dãy c.

Ví dụ: Cho dãy số a : 12 2 8 5 1 6 4 15 KHOA CÔNG NGHỆ THÔNG TIN Trang 11 Chương 2 : Các thuật giải sắp xếp và tìm kiếm Sắp xếp dãy a theo trình tự tăng dần, trình bày các bước (có thay đổi) chạy giải thuật sắp xếp theo phương pháp đổi chổ trực tiếp (Interchange Sort)?