Giáo trình Kinh tế: cấu trúc dữ liệu và giải thuật ngành quản trị mạng

Tài liệu chuyên sâu về cấu trúc dữ liệu và giải thuật dành cho sinh viên ngành quản trị mạng với lý thuyết và bài tập thực hành đầy đủ.

• Tác giả: Tổ Bộ Môn Tin Học
• Trường học: Trường Cao đẳng Công nghiệp Hải Phòng
• Chuyên ngành: Cấu trúc dữ liệu và Giải thuật
• Đề tài: Cấu trúc dữ liệu và Giải thuật
• Loại tài liệu: Giáo trình
• Địa điểm: Hải Phòng

Tóm tắt

I. Khái niệm cơ bản về Cấu trúc dữ liệu và Giải thuật

Cấu trúc dữ liệu và giải thuật là những kiến thức nền tảng trong lĩnh vực công nghệ thông tin và lập trình máy tính. Cấu trúc dữ liệu đề cập đến cách tổ chức, lưu trữ và quản lý dữ liệu trong bộ nhớ máy tính, trong khi giải thuật là tập hợp các bước hoặc quy trình để giải quyết một bài toán cụ thể. Giáo trình này được biên soạn dựa trên chương trình đào tạo Cao đẳng và Trung cấp nghề Quản trị mạng máy tính, gồm 7 chương với nội dung từ cơ bản đến nâng cao. Học viên sẽ nắm vững các kiểu dữ liệu cơ bản, kiểu dữ liệu cấu trúc, và kiểu dữ liệu trừu tượng. Giáo trình cố gắng kết nối các kiến thức giữa các chương và môn học trước đó, giúp sinh viên phát triển kỹ năng lập trình và khả năng chọn cấu trúc dữ liệu phù hợp để xây dựng giải thuật hiệu quả.

1.1. Cấu trúc lưu trữ và Cấu trúc dữ liệu

Cấu trúc lưu trữ là cách bố trí dữ liệu trong bộ nhớ vật lý máy tính, được xác định bởi ngôn ngữ lập trình. Ngược lại, cấu trúc dữ liệu là mô hình logic để tổ chức dữ liệu, độc lập với cách lưu trữ cụ thể. Sự khác biệt giữa hai khái niệm này rất quan trọng để lập trình viên hiểu cách dữ liệu được quản lý ở cả mức độ logic và vật lý.

1.2. Các tiêu chuẩn đánh giá Cấu trúc dữ liệu

Khi chọn cấu trúc dữ liệu, cần xem xét các tiêu chuẩn như hiệu suất truy cập, tốc độ chèn/xóa, không gian bộ nhớ, và độ phức tạp của các phép toán. Mỗi cấu trúc dữ liệu có ưu điểm riêng, ví dụ mảng nhanh chóng truy cập nhưng chèn/xóa chậm, trong khi danh sách liên kết linh hoạt hơn nhưng tốc độ truy cập thấp hơn.

II. Giải thuật và Đánh giá Độ phức tạp

Giải thuật là một chuỗi các bước logic để giải quyết một bài toán cụ thể. Trong lĩnh vực lập trình, việc hiểu và thiết kế giải thuật tối ưu là kỹ năng thiết yếu. Giáo trình cung cấp ba cách biểu diễn giải thuật: sử dụng ngôn ngữ tự nhiên, lưu đồ giải thuật, và ngôn ngữ diễn đạt giải thuật (mã giả). Một giải thuật tốt phải có những đặc trưng như tính xác định, có đầu vào và đầu ra rõ ràng, hữu hạn các bước, và có thể thực hiện được. Độ phức tạp tính toán của giải thuật được đánh giá qua ký hiệu O lớn, giúp lập trình viên so sánh hiệu suất của các giải thuật khác nhau trước khi áp dụng vào thực tế.

2.1. Biểu diễn Giải thuật

Có ba phương pháp chính để biểu diễn giải thuật: thứ nhất là sử dụng ngôn ngữ tự nhiên với lời tả chính xác; thứ hai là dùng lưu đồ giải thuật với các ký hiệu hình học; thứ ba là ngôn ngữ mã giả gần với mã lập trình nhưng dễ hiểu hơn. Mỗi cách biểu diễn có ưu điểm riêng, giúp người học và người phát triển phần mềm dễ dàng giao tiếp và hiểu rõ ý tưởng.

2.2. Xác định Độ phức tạp Tính toán

Độ phức tạp tính toán được xác định bằng cách phân tích số lần thực hiện các phép toán cơ bản trong giải thuật. Ký hiệu O lớn (Big O) được sử dụng để mô tả tốc độ tăng của thời gian thực hiện khi kích thước dữ liệu tăng. Các mức độ phức tạp thường gặp là O(1), O(n), O(n²), O(log n), và O(n log n).

III. Cấu trúc dữ liệu Cơ bản Danh sách Stack và Queue

Danh sách tuyến tính là một trong những cấu trúc dữ liệu cơ bản nhất, được cài đặt bằng hai phương pháp chính: mảng và danh sách liên kết. Cài đặt bằng mảng có ưu điểm truy cập nhanh nhưng hạn chế về kích thước, trong khi danh sách liên kết linh hoạt hơn. Giáo trình cũng giới thiệu hai cấu trúc dữ liệu đặc biệt là Stack (ngăn xếp) và Queue (hàng đợi). Stack hoạt động theo nguyên tắc LIFO (Last In First Out), thích hợp cho các ứng dụng như kiểm tra dấu ngoặc, đảo ngược chuỗi. Queue hoạt động theo nguyên tắc FIFO (First In First Out), được sử dụng trong quản lý tài nguyên, lập lịch công việc. Mỗi cấu trúc có các phép toán cơ bản như thêm, xóa, và truy cập phần tử.

3.1. Danh sách Liên kết và ứng dụng

Danh sách liên kết sử dụng con trỏ hoặc mối nối để kết nối các phần tử, khắc phục nhược điểm của cấu trúc mảng. Có ba loại chính: danh sách liên kết đơn, danh sách liên kết kép, và danh sách liên kết nối vòng. Mỗi loại phù hợp với các tình huống sử dụng khác nhau, từ duyệt tuyến tính đến duyệt hai chiều.

3.2. Stack và Queue trong Lập trình

Stack và Queue là hai cấu trúc dữ liệu quan trọng được cài đặt từ danh sách liên kết hoặc mảng. Stack dùng cho các bài toán liên quan đến kiểm tra cấu trúc, đảo ngược, tính toán biểu thức. Queue được áp dụng trong bài toán BFS, quản lý bộ đệm, và lập lịch công việc trong hệ điều hành.

IV. Các Phương pháp Sắp xếp và Tìm kiếm

Sắp xếp và tìm kiếm là những bài toán cơ bản và quan trọng trong khoa học máy tính. Giáo trình giới thiệu năm phương pháp sắp xếp phổ biến: Insertion Sort (sắp xếp chèn) có độ phức tạp O(n²), thích hợp với dữ liệu nhỏ; Selection Sort (sắp xếp chọn) cũng O(n²); Bubble Sort (sắp xếp nổi bọt) dễ hiểu nhưng chậm; Interchange Sort (sắp xếp đổi chỗ) là cải tiến của Bubble Sort; và Quick Sort (sắp xếp nhanh) với trung bình O(n log n), hiệu quả hơn với dữ liệu lớn. Đối với tìm kiếm, giáo trình cung cấp hai phương pháp: tìm kiếm tuyến tính O(n) áp dụng cho dữ liệu chưa sắp xếp, và tìm kiếm nhị phân O(log n) cho dữ liệu đã sắp xếp. Việc chọn giải thuật phù hợp phụ thuộc vào kích thước dữ liệu, tính chất dữ liệu, và yêu cầu hiệu suất.

4.1. So sánh các Phương pháp Sắp xếp

Mỗi phương pháp sắp xếp có ưu và nhược điểm khác nhau. Insertion Sort tốt cho dữ liệu nhỏ; Bubble Sort dễ cài đặt nhưng kém hiệu quả; Quick Sort là lựa chọn tốt cho dữ liệu lớn với độ phức tạp trung bình O(n log n). Việc hiểu độ phức tạp của từng phương pháp giúp lập trình viên chọn giải pháp tối ưu.

4.2. Chiến lược Tìm kiếm Hiệu quả

Tìm kiếm tuyến tính là phương pháp cơ bản, kiểm tra tuần tự từng phần tử. Tìm kiếm nhị phân yêu cầu dữ liệu được sắp xếp nhưng nhanh hơn nhiều lần. Lựa chọn giải thuật tìm kiếm phù hợp tùy thuộc vào trạng thái dữ liệu và tần suất tìm kiếm.

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

CHƯƠNG 1 PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT Muc tiêu: Trình bày được khái niệm vê câu truc dư liêu, giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Đánh giá được độ phức tạp của giải thuật. Trình bày được các kiểu dữ liệu cơ bản, các kiểu dữ liệu cấu trúc và kiểu dữ liệu trừu tượng. Khái niệm cấu trúc dữ liệu và giải thuật, cấu trúc lưu trữ và cấu trúc dữ liệu.

Khái niệm cấu trúc dữ liệu và giải thuật Algorithms + Data Structures = Programs " Giai thuật + Cấu trúc dữ liệu = Chương trình " Đo la nhan đê cuốn sách đươc xuât ban năm 1975, bơi nha khoa hoc may tinh Thuy sy Niklaus Wirth Emil, cuôn sach đa đươc công nhân rông rai va vân con hưu dung đên ngay nay. Năm vưng câu truc dư liêu va giai thuât la cơ sơ giup sinh viên có khả năng đi sâu thêm vào các môn học chuyên ngành. Giải thuật(Algorithms): Đó là một dãy các câu lệnh (statements) chặt chẽ và rõ ràng xác định một trình tự các thao tác trên một số các đối tượng nào đó, sao cho sau một số hữu hạn bước thực hiện ta đạt đươc kết quả mong muốn. Dữ liệu (Data): Là đối tượng của giải thuật để khi tác động bởi các thao tác của giải thuật ta nhận được kết quả mong muốn.

Giải thuật chỉ phản ánh các phép xử lí, còn đối tượng để xử lí trên MTĐT, chính là dữ liệu (data) chúng biểu diễn các thông tin cần thiết cho bài toán: Các dữ kiện đưa vào, các kết quả trung gian va kêt qua đâu ra cua bai toan.1: Chương trinh tìm ươc chung lớn nhất của 2 số nguyên dương a và b. Dư kiên đưa vao (input): a, b nguyên dương Phep xư ly (Process) : Dưa theo thuât toan Euclid, thuât toan nôi tiêng nhât co tư thơi cô đai. Bươc 1: Tim r, la phân dư cua phep chia a cho b. Thi: Gan gia tri cua b cho E (E←b) va dưng lai Nêu ngươc lai (r ≠ 0).

Thi: Gan gia tri b cho a ( a←b). Gan gia tri r cho b (b←r) va quay lai bươc 1. 11 Kêt qua ra (Output): E, Ươc chung lơn nhât cua a va b. Cấu trúc dữ liệu (Data Structures): Cách sắp xếp, tổ chức dữ liệu, tạo quan hệ nội tại giữa các phần tử dữ liệu, tạo thuận lợi cho các phép xử lý và nâng cao hiệu quả của chúng.

Bản thân các phần tử của dữ liệu có mối quan hệ với nhau, ngoài ra nếu lại biết “tổ chức” theo các cấu trúc thích hợp thì việc thực hiện các phép xử lí trên các dữ liệu càng thuận lợi hơn, đạt hiệu quả cao hơn.2: Viêt chương trinh thưc hiên công viêc sau: Nhâp vao tư ban phim n sô nguyên bât ky Tinh tông cac sô vưa nhâp va đưa kêt qua ra man hinh Dư kiên đưa vao (input): so, tong la 2 biên sô nguyên và n là số lượng số nguyên. Phep xư ly (Process) : Thưc hiên n lân công viêc sau: - Nhâp gia tri cho biên so - Công gia tri biên so vao biên tong Kêt qua ra (Output): tong, tông n sô nguyên vưa nhâp Vơi 2 yêu câu (a, b) cua bai toan, ta chi cân môt biên so đê lưu gia tri tưng sô nguyên nhâp vao va công gôp dân gia tri ngay vao môt biên tong.3: Viêt chương trinh thưc hiên công viêc sau: Nhâp vao tư ban phim n sô nguyên bât ky. Tinh tông cac sô vưa nhâp va đưa kêt qua ra man hinh. Săp xêp day sô theo chiều tăng dần va đưa day đa săp xêp ra man hinh.

Dư kiên đưa vao (input): tong la biên sô nguyên. M la môt biên mang kiểu phân tư là kiêu sô nguyên. n là số lượng số nguyên. Phai cân môt biên mang M đê lưu gia tri n sô nguyên nhâp vao tư ban phim va day sô nguyên đa đươc săp xêp.

(nhiều ngôn ngư lâp trinh đêu đinh nghia sẵn kiêu dư liêu mang (array): gôm môt tâp hơp hưu han cac phần tư có cùng kiêu dư liêu, ta chỉ cần khai bao tên kiêu mang, sô lương phần tư va kiêu dư liêu cua phần tư khi cầ̀n sử dụng.) So sanh 2 vi du trên ta nhân thây co sư khac biêt sau : Ví dụ Dữ kiện đưa vào Phép xử lý Kết quả đưa ra Ví dụ 1.2 Chi cân môt biên Viêc tinh tông Gia tri biên tong so đê lưu giư tưng được thực hiện sô nguyên ngay sau mỗi lần nhâp sô nguyên Ví dụ 1.3 Phai cân biên Co thê tach riêng Gia tri biên tong va mảng M để lưu viêc tinh tông sau biên mả̉ ng M chứa n giư n sô nguyên khi nhâp giá trị sô nguyên đa đươc cho n sô nguyên sắp xếp tăng dần Tom lai, giữa cấu trúc dữ liệu và giải thuật có mối quan hệ mật thiết, không thể nói tới giải thuật mà không nghĩ tới: Giải thuật đó́ được tác động trên dữ liệu nào, còn khi xét tới dữ liệu thì cũng phải hiểu: Dữ liệu ấy cầ̀n được tác động bởi giải thuật gì để đưa tới kết quả mong muốn. Với một cấu trúc dư liệu đã chọn ta sẽ có giải thuật xử ly tương ứng. Cấu trúc dữ liệu thay đổi, giải thuật cũng có thể thay đổi theo. Cấu trúc dữ liệu và cấu trúc lưu trữ Cách biểu diễn một câu truc dư liêu (CTDL) trong bộ nhớ được gọi là cấu trúc lưu trữ (storage sructures).

Đó chính là cách cài đặt cấu trúc ấy trên may tinh điên tư và trên cơ sở cấu trúc lưu trữ này mà thực hiện các phép xử lí. Sự phân biệt giữa CTDL và cấu trúc lưu trữ tương ứng, cần phải được đặt ra. Có́ thể có́ nhiều cấu trúc lưu trữ khác nhau cho cù̀ng một CTDL, cũng như có́ thể có́ những CTDL khác nhau mà được thể hiện trong bộ nhớ bởi cù̀ng một kiểu cấu trúc lưu trữ 13 (thường khi xử lí, mọi chú ý đều hướng tới cấu trúc lưu trữ nên ta dễ quên mất CTDL tương ứng). Phân biệt lưu trữ trong và lưu trữ ngoài: Lưu trữ trong: Là lưu trữ ở bộ nhớ trong.

Lưu trữ ngoài: Là lưu trữ ở bộ nhớ ngoài (đĩa từ, đĩa quang,.4: CTDL kiểu mảng và Stack cùng được lưu trữ trong bộ nhớ bởi vectơ lưu trữ a[0] A[1] a[2]. a[1] a[0] Đáy Cấu trúc dữ liệu Trong môi bài toán, Lưạ chọn một CTDL thích hợp để tổ chức dữ liệu vào và trên cơ sở đó xây dựng được giải thuật xử ly hữu hiệu đưa tới kết quả mong muốn cho bài toán, đó là một khâu rất quan trọng. Muốn vậy cần nắm vững đặc điểm và các phép toán cơ bản của từng kiểu dữ liệu được sử dụng trong mỗi ngôn ngữ lập trình là yêu cầu cần thiết. Các kiểu dữ liệu cơ bản Các loại dữ liệu cơ bản là các loại dữ liệu đơn giản, cơ sở.

Chúng thường là các giá trị vô hướng như các số nguyên, số thực, các ký tự, các giá trị logic. Các loại dữ liệu này, do tính thông dụng và đơn giản của mình, thường được các ngôn ngữ lập trình (NNLT) cấp cao xây dựng sẵn như một thành phần của ngôn ngữ để giảm nhẹ công việc cho người lập trình. Thông thường, các kiểu dữ liệu cơ bản bao gồm: Kiểu có́ thứ tự rời rạc: số nguyên, ký tự, logic , liệt kê, miền con … Kiểu không rời rạc: số thực. Ví dụ: Các kiểu dữ liệu định sẵn trong C gồm: Tên kiểu Sô bytes Miền giá trị Ghi chú Char 1 -128 đến 127 Có thể dùng như số nguyên 1 byte có dấu hoặc kiểu ký tự unsigned char 1 0 đến 255 Số nguyên 1 byte không dấu Enum 2 -32,768 đến 32,767 14 Int 2 -32738 đến 32767 unsigned int 2 0 đến 65335 Có thể gọi tắt là unsigned Long 4 -232 đến 231 -1 unsigned long 4 0 đến 232-1 Float 4 3.4E38 Giới hạn chỉ trị tuyệt đối.

Tuy nhiên kiểu float chỉ có 7 chữ số có nghĩa. Các kiểu dữ liệu cấu trúc. Đó là CTDL tiên định rất hay dùng đã được cài đặt sẵn trong các ngôn ngữ lập trình, người lập trình chỉ việc dùng như: Tập hợp, mảng, bản ghi, tệp,.và cung cấp cơ chế cho lập trình viên tự định nghĩa kiểu dữ liệu mới. (Khi nghiên cứu đến môt ngôn ngữ nào đó́ cầ̀n phải nghiên cứu kỹ cac kiêu dư liêu câu truc của nó́ .) Kiểu tập hợp : Một tập hợp bao gồm một số các đối tượng nào đó có cùng bản chất, được mô tả bởi cùng một kiểu, kiểu này là kiểu cơ bản (kiểu vô hướng đếm được hay đoạn con, liệt kê), không được là kiểu số thực.

Các đối tượng này được gọi là các phần tử của tập hợp. Số lượng phần tử của tập hợp thông thường là từ 0 (gọi là tập rỗng) đến tối đa là 255 phần tử. Kiểu Mảng : Là một tập hợp gồm một số cố định các phần tử có cùng kiểu dữ liệu. Mỗi phần tử của mảng ngoài giá trị còn được đặc trưng bởi chỉ số (Index) thể hiện thứ tự của phần tử đó trong mảng (Vectơ là mảng 1 chiều, mỗi phần tử ai của nó ứng với một chỉ số i.

Ma trận là mảng 2 chiều mỗi phần tử aij của nó ứng với 2 chỉ số i và j,. Kiểu bản ghi (kiểu cấu trúc): là một tập hợp các phần tử dữ liệu (field), mỗi phần tử dữ liệu có thể được mô tả bởi một kiểu dữ liệu khác nhau nhưng có liên kết với nhau, dùng để mô tả một đối tượng (Record). Tệp tin (File): Là một tập hợp các dữ liệu có liên quan với nhau và có cùng kiểu dữ liệu được nhóm lại tạo thành một dãy. Chúng thường được chứa trong môt thiết bị nhớ ngoài của máy tính với một cái tên nào đó.5 : Để mô tả một đối tượng sinh viên, cần quan tâm đến các thông tin sau: Mã sinh viên: chuỗi ký tự.

Tên sinh viên: chuỗi ký tự. 15 Ngày sinh: kiểu ngày tháng. Điểm thi: số thực. Các kiểu dữ liệu cơ sở cho phép mô tả một số thông tin như : float Diemthi; Các thông tin khác đòi hỏi phải sử dụng các kiểu có cấu trúc như : char masv[15]; char tensv[25]; Để thể hiện thông tin về ngày tháng năm sinh cần phải xây dựng một kiểu bản ghi.

typedef struct Date { unsigned char ngay; unsigned char thang; unsigned int nam; }; Cuối cùng, ta có thể xây dựng kiểu dữ liệu thể hiện thông tin về một sinh viên: typedef struct SinhVien { char masv[15]; char tensv[25]; Date ngsinh; float Diemthi; }; Giả sử đã có cấu trúc phù hợp để lưu trữ một sinh viên, nhưng thực tế lại cần quản lý nhiều sinh viên, lúc đó nảy sinh nhu cầu xây dựng kiểu dữ liệu mới (kiểu mảng bản ghi,…).