Giáo trình Cấu trúc dữ liệu và giải thuật (Ngành: Công nghệ thông tin - Cao đẳng liên thông) - Trường Cao đẳng Xây dựng số 1

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:70

Thêm vào BST

Báo xấu

10
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giáo trình "Cấu trúc dữ liệu và giải thuật (Ngành: Công nghệ thông tin - Cao đẳng liên thông)" được biên soạn với mục tiêu nhằm giúp sinh viên nắm được các kiến thức về: Các khái niệm cơ bản về giải thuật, đánh giá độ phức tạp của giải thuật; các kiểu cấu trúc dữ liệu thông dụng và một số giải thuật trên các kiểu cấu trúc dữ liệu đó. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Cấu trúc dữ liệu và giải thuật (Ngành: Công nghệ thông tin - Cao đẳng liên thông) - Trường Cao đẳng Xây dựng số 1

BỘ XÂY DỰNG TRƯỜNG CAO ĐẲNG XÂY DỰNG SỐ 1 GIÁO TRÌNH MÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGÀNH: CÔNG NGHỆ THÔNG TIN (ỨNG DỤNG PHẦN MỀM) TRÌNH ĐỘ: CAO ĐẲNG LIÊN THÔNG Ban hành kèm theo Quyết định số: 374ĐT/QĐ- CĐXD1 ngày 16 tháng 08 năm 2022 của Hiệu trưởng trường CĐXD số 1 Hà Nội, năm 2022
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 NÓI ĐẦU Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT được biên soạn nhằm phục vụ cho giảng dạy và học tập cho trình độ Cao đẳng liên thông ngành Công nghệ thông tin (Ứng dụng phần mềm) ở trường Cao đẳng Xây dựng số 1. Cấu trúc dữ liệu và giải thuật là môn học cơ sở ngành nhằm cung cấp các kiến thức cơ bản về các kiểu cấu trúc dữ liệu thông dụng và một số giải thuật trên các kiểu cấu trúc dữ liệu đó trong ngành Công nghệ thông tin. Giáo trình này được viết theo đề cương môn học Cấu trúc dữ liệu và giải thuật Nội dung gồm 04 chương như sau: Chương 1: Giải thuật Chương 2: Danh sách Chương 3: Mô hình cây và đồ thị Chương 4: Các giải thuật sắp xếp và tìm kiếm Mặc dù có nhiều cố gắng, nhưng trong quá trình biên soạn, biên tập và in ấn khó tránh khỏi những thiếu sót. Chúng tôi rất mong nhận được sự đóng góp ý kiến từ phía các thầy cô và bạn đọc để hoàn thiện giáo trình hơn! Xin trân trọng cảm ơn! Hà Nội, ngày……tháng……năm……… Tham gia biên soạn Trần Thị Mơ - Chủ biên 3
MỤC LỤC CHƯƠNG 1: GIẢI THUẬT ................................................................................. 7 1.1. Các khái niệm ............................................................................................. 8 1.1.1. Giải thuật ............................................................................................. 8 1.1.2. Cấu trúc dữ liệu ................................................................................... 8 1.2. Các đặc trưng của giải thuật ....................................................................... 8 1.2.1. Dữ liệu vào .......................................................................................... 9 1.2.2. Dữ liệu ra ............................................................................................. 9 1.3. Ngôn ngữ diễn đạt ...................................................................................... 9 1.3.1. Ngôn ngữ thông thường ...................................................................... 9 1.3.2. Lưu đồ ................................................................................................. 9 1.3.3. Ngôn ngữ lập trình ............................................................................ 11 1.4. Phương pháp thiết kế giải thuật................................................................ 12 1.4.1. Phân rã bài toán thành các bài toán nhỏ hơn..................................... 12 1.4.2. Phương pháp tinh chỉnh từng bước ................................................... 12 CHƯƠNG 2: DANH SÁCH ............................................................................... 15 2.1. Danh sách tuyến tính ................................................................................ 16 2.1.1. Khái niệm chung ............................................................................... 16 2.1.2. Kiểu mảng ......................................................................................... 16 2.1.3. Kiểu ngăn xếp.................................................................................... 17 2.1.4. Kiểu hàng đợi .................................................................................... 19 2.2. Danh sách liên kết .................................................................................... 20 2.2.1. Danh sách liên kết đơn (singly linked list) ....................................... 21 2.2.3. Danh sách liên kết vòng (circular linked list) ................................... 29 CHƯƠNG 3: MÔ HÌNH CÂY VÀ ĐỒ THỊ ...................................................... 32 3.1. Mô hình cây .............................................................................................. 33 3.1.1. Định nghĩa ......................................................................................... 33 3.1.2. Cây nhị phân...................................................................................... 33 3.2. Đồ thị ........................................................................................................ 35 4
3.2.1. Định nghĩa ......................................................................................... 35 3.2.2. Biểu diễn đồ thị ................................................................................. 37 2.2.3. Phép duyệt đồ thị ............................................................................... 39 CHƯƠNG 4: CÁC GIẢI THUẬT SẮP XẾP VÀ TÌM KIẾM........................... 43 4.1. Các giải thuật sắp xếp .............................................................................. 46 4.1.1. Bài toán sắp xếp ................................................................................ 46 4.1.2. Sắp xếp kiểu đổi chỗ trực tiếp ........................................................... 47 4.1.3. Sắp xếp kiểu chèn.............................................................................. 48 4.1.4. Sắp xếp kiểu chọn ............................................................................. 50 4.1.5. Sắp xếp kiểu vun đống ...................................................................... 51 4.1.6. Sắp xếp nhanh ................................................................................... 59 4.2. Các giải thuật tìm kiếm ............................................................................ 62 4.2.1. Bài toán tìm kiếm .............................................................................. 62 4.2.2. Tìm kiếm tuần tự ............................................................................... 62 4.2.3. Tìm kiếm nhị phân ............................................................................ 63 4.2.4. Cây nhị phân tìm kiếm ...................................................................... 64 5
Tên môn học: CẦU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mã môn học: MH09 Thời gian thực hiện môn học: 45 giờ; (Lý thuyết: 15 giờ; Thực hành, thí nghiệm, thảo luận, bài tập: 28 giờ; Kiểm tra: 02 giờ) I. Vị trí, tính chất của môn học: - Vị trí: Môn học Cấu trúc dữ liệu và giải thuật là môn học bắt buộc thuộc nhóm các môn học cơ sở trong chương trình đào tạo nghề Công nghệ thông tin. - Tính chất: Môn học có tính ứng dụng cao trong các lĩnh vực tin học, góp phần nâng cao chất lượng đào tạo nghề và phát triển nguồn nhân lực trong giai đoạn mới. II. Mục tiêu môn học: - Về kiến thức: Các khái niệm cơ bản về giải thuật, đánh giá độ phức tạp của giải thuật. Các kiểu cấu trúc dữ liệu thông dụng và một số giải thuật trên các kiểu cấu trúc dữ liệu đó. - Về kỹ năng: Thiết kế được một số giải thuật sắp xếp, tìm kiếm. Vận dụng các kiểu cấu trúc dữ liệu thông dụng và các giải thuật để giải một số bài toán thực tiễn. - Về năng lực tự chủ và trách nhiệm: Tích cực nghiên cứu những kiến thức về cấu trúc dữ liệu, giải thuật. Rèn luyện ý thức chấp hành kỷ luật lao động, phát huy tinh thần chủ động nghiên cứu, học hỏi, sáng tạo trong học tập và làm việc. 6
CHƯƠNG 1: GIẢI THUẬT Mục tiêu bài học 1. Cung cấp cho người học các kiến thức cơ bản về cơ bản về giải thuật: các đặc trưng giải thuật, ngôn ngữ diễn đạt giải thuật, phương pháp thiết kế giải thuật, đánh giá độ phức tạp của giải thuật trong một số bài toán cụ thể. 7
CHƯƠNG 1: GIẢI THUẬT 1.1. Các khái niệm 1.1.1. Giải thuật Khái niệm giải thuật hay thuật giải mà nhiều khi còn được gọi là thuật toán dùng để chỉ phương pháp hay cách thức (method) để giải quyết vần đề. Giải thuật có thể được minh họa bằng ngôn ngữ tự nhiên (natural language), bằng sơ đồ (flow chart) hoặc bằng mã giả (pseudo code). Trong thực tế, giải thuật thường được minh họa hay thể hiện bằng mã giả tựa trên một hay một số ngôn ngữ lập trình nào đó (thường là ngôn ngữ mà người lập trình chọn để cài đặt thuật toán), chẳng hạn như C, Pascal, ? Khi đã xác định được cấu trúc dữ liệu thích hợp, người lập trình sẽ bắt đầu tiến hành xây dựng thuật giải tương ứng theo yêu cầu của bài toán đặt ra trên cơ sở của cấu trúc dữ liệu đã được chọn. Để giải quyết một vấn đề có thể có nhiều phương pháp, do vậy sự lựa chọn phương pháp phù hợp là một việc mà người lập trình phải cân nhắc và tính toán. Sự lựa chọn này cũng có thể góp phần đáng kể trong việc giảm bớt công việc của người lập trình trong phần cài đặt thuật toán trên một ngôn ngữ cụ thể. 1.1.2. Cấu trúc dữ liệu 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ó Thuật giải 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. Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí sau: - Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong) - Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán - Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu. 1.2. Các đặc trưng của giải thuật - Tính xác định: Mỗi bước của thuật giải cần phải được mô tả một cách chính xác, chỉ có một cách hiểu duy nhất. Bởi vì, nếu một bước có thể hiểu theo nhiều cách khác nhau, thì cùng một dữ liệu vào, những người thực hiện thuật giải khác nhau có thể cho ra kết quả khác nhau. Nếu ta mô tả thuật giải bằng ngôn ngữ tự nhiên, không có gì đảm bảo người đọc hiểu đúng ý của người viết thuật giải, bởi ngôn ngữ tự nhiên thường là đa nghĩa. Để đảm bảo đòi hỏi này, thuật giải cần được mô tả trong một ngôn ngữ lập trình, chẳng hạn một ngôn ngữ lập trình (Pascal, C...). trong các ngôn ngữ này, các mệnh đề được tạo thành theo các qui tắc cú pháp nghiêm nghặt và chỉ có một ý nghĩa duy nhất. 8
- Tính khả thi: Tất cả các phép giải có mặt trong các bước của thuật giải phải đủ đơn giản. Điều đó có nghĩa là các phép giải phải sao cho, ít nhất về nguyên tắc có thể thực hiện được bởi con người trong một khoảng thời gian hữu hạn. Chẳng hạn trong thuật giải Euclid, ta chỉ cần thực hiện các phép chia các số nguyên, các phép gán và các phép so sánh. - Tính dừng: Với mọi bộ dữ liệu vào thoả mãn điều kiện qui định, thuật giải phải dừng lại sau một số hữu hạn bước thực hiện. Chẳng hạn đối với thuật giải Euclid là thuật giải thoả mãn điều kiện này. Bởi vì số dư r luôn nhỏ hơn n, nếu r0 thì giá trị của n ở bước sau là giá trị của r ở bước trước, ta có n>r=n1>r1=n2>r2.....Dãy số nguyên dương giảm dần cần phải kết thúc ở 0, do đó sau một số bước giá trị của r=0 thuật giải dừng. 1.2.1. Dữ liệu vào - Input: Mỗi thuật giải cần có một số (có thể bằng không) dữ liệu vào. Đó là giá trị cần đưa vào khi thuật giải bắt đầu làm việc. 1.2.2. Dữ liệu ra - Output: Mỗi thuật giải cần có một hoặc nhiều dữ liệu ra. Đó là các giá trị có quan hệ xác định với giá trị vào và là kết quả của sự thực hiện thuật giải. 1.3. Ngôn ngữ diễn đạt 1.3.1. Ngôn ngữ thông thường Trong cách biểu diễn thuật giải theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kê các bước của thuật giải (Các ví dụ về thuật giải trong mục 1 của chương sử dụng ngôn ngữ tự nhiên). Phương pháp biểu diễn này không yêu cầu người viết thuật giải cũng như người đọc thuật giải phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật giải, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật giải bằng ngôn ngữ tự nhiên 1.3.2. Lưu đồ Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật giải. Biểu diễn thuật giải bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật giải. Phương pháp lưu đồ thường được dùng trong những thuật giải có tính rắc rối, khó theo dõi được quá trình xử lý. Các nút biểu diễn giải thuật bằng sơ đồ khối: Nút thao tác Nút điều khiển: trong đó ghi điều kiện cần kiểm tra trong quá trình tính toán. 9
Nút khởi đầu, kết thúc Cung Vẽ lưu đồ hoặc sơ đồ khối, mỗi khối mô tả một bước. Sử dụng mũi tên nối khối này với khối kia để chỉ trình tự thực hiện các bước. Để dễ dàng nhận biết chức năng của từng khối, mỗi khối được thể hiện ở một dạng như sau: Ví dụ: Tìm nghiệm thực của phương trình bậc hai ax2+bx+c=0. Thuật toán gồm các bước sau: + Nhập dữ liệu a, b, c. + Tính biệt số  = b2-4ac. + So sánh  với 0. Bước tiếp theo sẽ phụ thuộc vào giá trị của . + Nếu 0, tính và ghi đáp số trị của hai nghiệm phân biệt: . Lưu đồ biểu diễn thuật toán này được thể hiện như sau: 10
1.3.3. Ngôn ngữ lập trình Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán nhưng lại cồng kềnh. Để mô tả một thuật toán nhỏ ta phải dùng một không gian rất lớn. Đôi khi, ta có thể thể hiện thuật toán bằng ngôn ngữ lập trình nào đó. Mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Như vậy, có thể tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng hiểu chính xác thuật toán. Một khi đã vay mượn cú pháp và khái niệm của ngôn ngữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó. Một đoạn mã giả của thuật toán giải phương trình bậc hai: if Delta > 0 then begin end else if delta = 0 then xuất kết quả : phương trình có nghiệm kép là -b/(2*a) else {trường hợp delta < 0 } xuất kết quả : phương trình vô nghiệm x1=(-b+sqrt(delta))/(2*a) x2=(-b-sqrt(delta))/(2*a) 11
xuất kết quả : phương trình có hai nghiệm là x1 và x2 1.4. Phương pháp thiết kế giải thuật 1.4.1. Phân rã bài toán thành các bài toán nhỏ hơn Các bài toán giải trên máy tính càng ngày càng đa dạng và phong phú dẫn tới quy mô chương trình ngày càng lớn. Quy mô càng lớn dẫn tới việc lập và kiểm soát chương tình càng gặp nhiều khó khăn hơn. Ta cần chia bài toán lớn thành nhiều bài toán nhỏ, do đó người ta sử dụng một phương pháp thiết kế: Từ trên xuống (top)-down design: Phân tích tổng quát toàn bộ vấn đề và mục tiêu đặt ra, đề cập tới những công việc chủ yếu, sau đó dần giải quyết các phần việc cụ thể một cách chi tiết hơn. Ví dụ: Cần lập một hệ chương trình quản lý bảo trì hồ sơ về lương của cán bộ. Chương trình được phân tích theo sơ đồ sau: Ưu điểm cho phương pháp thiết kế từ trên xuống: - Giúp cho việc giải quyết bài toán được định hướng rõ ràng, tránh sa đà vào các chi tiết phụ. - Cho phép tách bài toán thành các thành phần độc lập, mỗi phần có thể được giao cho các nhóm lập trình khác nhau. Các nhóm làm việc độc lập với nhau. - Thấy cấu trúc rõ ràng của chương trình, từ đó có thể dễ dàng hiểu, nắm vững và bao quát chương trình, việc tìm và sửa lỗi cũng trở nên dễ dàng hơn. 1.4.2. Phương pháp tinh chỉnh từng bước Phương pháp tinh chỉnh từng bước là phương pháp thiết kế giải thật gắn liền với lập trình Ví dụ: Lập chương trình sắp xếp một dãy số gồm n số nguyên theo thứ tự tăng dần Các bước tinh chỉnh sẽ như sau: 12
1. Readln(n) 2. Lần lượt nhập các số a1, a2, ..., an 3. For i:=1 to n do Begin - Tìm số nhỏ nhất a_min trong dãy ai, ai+1, ... , an - đổi chỗ a_min với ai End Tới đây ta thấy trong phần 3 chỉ có 2 nhiệm vụ cần làm rõ: Tìm số nhỏ nhất a_min đổi chỗ a_min với ai Số nhỏ nhất được xác định bằng cách chỉ ra vị trí của nó, tức là xác định chỉ số của nó. Việc này được thực hiện bằng cáh luôn ghi nhớ chỉ số của Số nhỏ nhất vào 1 biến, cụ thể là: min:=i; For k:=i+1 to n do If ai < amin then min:=k; Việc đổi chỗ a_min với ai được thực hiện giống nhau như khi ta muốn chuyển 2 thứ nước trong 2 chai từ chai nọ sang chai kia, ta dùng 1 chai thứ 3 làm trung gian. tg:=ai; a:=amin; amin:=tg; Sau khi tinh chỉnh lần 2, chương trình có dạng: 1. Readln(n) 2. Lần lượt nhập các số a1, a2, ..., an 3. For i:=1 to n do Begin 3.1. min:=i; For k:=i+1 to n do If a[k] < a[min] then min:=k; 3.2. tg:=a[i]; a[i]:=a[min]; a[min]:=tg; End 13
Hệ thống kiến thức chương 1 1. Yêu cầu về lý thuyết - Kiến thức cơ bản về giải thuật: các đặc trưng giải thuật, ngôn ngữ diễn đạt giải thuật, phương pháp thiết kế giải thuật, đánh giá độ phức tạp của giải thuật trong một số bài toán cụ thể. 2. Yêu cầu về bài tập: Làm bài tập của chương 1 3. Hệ thống các kiến thức đã học: - Tổng quan về giải thuật: + Các đặc trưng của giải thuật + Ngôn ngữ diễn đạt giải thuật + Phương pháp thiết kế giải thuật + Đánh giá độ phức tạp của giải thuật trong một số bài toán. 4. Các câu hỏi, bài tập chương 1: Câu hỏi 1: Giải thuật là gì? Nêu các đặc trưng của giải thuật? Câu hỏi 2: Kể tên những loại ngôn ngữ nào diễn đạt giải thuật? Bài tập 1: Viết giải thuật xác định n là số nguyên tố? Bài tập 2: Giải thuật tìm phần tử thứ n của dãy số Fibonacci 14
CHƯƠNG 2: DANH SÁCH Mục tiêu bài học 1. Cung cấp cho người học các kiến thức cơ bản về một số kiểu dữ liệu dạng danh sách và một số thao tác trên kiểu dữ liệu đó. 15
CHƯƠNG 2: DANH SÁCH Danh sách là tập hợp các phần tử có kiểu dữ liệu xác định và giữa chúng có một mối liên hệ nào đó. Số phần tử của danh sách gọi là chiều dài của danh sách. Một danh sách có chiều dài bằng 0 là một danh sách rỗng. 2.1. Danh sách tuyến tính 2.1.1. Khái niệm chung Là tập hợp các phần tử dữ liệu có cùng kiểu được cấu trúc, sắp xếp (logic) theo một trật tự tuyến tính Như vậy, danh sách tuyến tính là: + Một chuỗi các phần tử + Tồn tại phần tử đầu và phần tử cuối + Mỗi phần tử có phần tử trước và phần tử sau - Một danh sách tuyến tính có: + Số phần tử biến đổi + Một phần tử thường là một bản ghi (record trong Pascal) hoặc một cấu trúc (struct trong C) - Các thao tác thường sử dụng nhất: + Thêm phần tử + Xóa phần tử - Các thao tác khác: + Tìm kiếm + Ghép 2 danh sách + Tách 1 danh sách thành nhiều danh sách + Sao chép danh sách + Cập nhật 2.1.2. Kiểu mảng - Ưu điểm: + Tìm kiếm dễ dàng (tuần tự hoặc tìm kiếm nhị phân) + Truy cập nhanh (ngẫunhiên, thời gian truy cập đến mọi phần tử là như nhau) + Duyệt các phần tử dễ dàng sử dụng chỉ số: for(i = 0; i Không biết trước số phần tử 16
+ Tốn bộ nhớ vì phải cấp phát nhiều hơn cần thiết để giữ chỗ. - Thêm một phần tử thứ i vào mảng + Chuyển các phần tử từ I đến n xuống các vị trí từ i+1 đến n+1; + Thêm phần tử cần thêm vào vị trí thứ i. + Xóa phần tử thứ i khỏi mảng + Chuyển các phần tử từ i+1 đến n vào các vị trí từ i đến n-1: Không hiệu quả vì luôn phải dịch chuyển phần tử. 2.1.3. Kiểu ngăn xếp Ngăn xếp (stack) là một cấu trúc dữ liệu tuyến tính, hoạt động theo cơ chế LIFO (Last In First Out), tạm dịch là “vào sau ra trước”. Có nghĩa là phần tử nào được thêm vào sau trong stack thì sẽ được lấy ra trước. 17
- Một ngăn xếp (stack) là một mô hình (cơ cấu) mà các tác động vào nó chỉ được thực hiện tại một phía của nó. Phía này được gọi là đỉnh của ngăn xếp. - Trong tin học, một ngăn xếp là là một danh sách tuyến tính mà các tác động vào nó chỉ được thực hiện tại một phía của nó. Phía này được gọi là đỉnh của ngăn xếp. Ta hình dung ngăn xếp như một ngăn kéo đựng tài liệu (của một bàn làm việc) mà ta chỉ có thể thêm vào hoặc bớt đi các phần tử (tài liệu) trong đó từ mặt trên (đỉnh) của ngăn kéo; Đoạn đảo chiều toa xe lửa; Hộp băng đạn của súng AK hay một chồng các đồ vật cùng kiểu (sách, bát, áo, đồng xu, hộp đạn súng máy AK47) Vì vậy mà có tên gọi Stack (danh sách kiểu xếp chồng) Với kiểu ngăn xếp, ta chỉ có thể thực hiện các thao tác sau: + Khởi tạo một ngăn xếp. + Đẩy (push) một phần tử mới vào ngăn xếp nếu ngăn xếp chưa đầy. Phần tử dữ liệu mới luôn được thêm tại đỉnh. + Lấy (pop) một phần tử ra khỏi ngăn xếp nếu ngăn xếp khác rỗng. Phần tử bị loại là phần tử đang nằm tại đỉnh. + Kiểm tra xem ngăn xếp có hay không có phần tử (rỗng hay không). + Kiểm tra xem ngăn xếp đã đầy hay chưa Như vậy: - Các phần tử của ngăn xếp có cùng một kiểu nào đó - Ngăn xếp là một trường hợp riêng của danh sách, được sử dụng trong các ứng dụng có liên quan đến sự đảo ngược. Trong CTDL ngăn xếp, việc thêm hay lấy dữ liệu chỉ được thực hiện tại một đầu. Dữ liệu thêm vào sau sẽ lấy ra trước, tính chất này còn được gọi là vào sau ra trước (Last In First Out -LIFO). - Khi nói đến ngăn xếp ta hiểu đó là danh sách kiểu LIFO ❖ Ví dụ: Đổi một số nguyên dương, chẳng hạn 23, sang cơ số 2, ta thực hiện như sau: 18
2.1.4. Kiểu hàng đợi Một hàng đợi (queue) là một mô hình (cơ cấu) mà tác động bổ sung vào nó được thực hiện ở một phía của nó và tác động loại bỏ một phần tử được thực hiện ở phía còn lại. Trong tin học, một hàng đợi là một danh sách tuyến tính mà thao tác bổ sung chỉ được thực hiện ở một đầu và thao tác bớt đi được thực hiện ở phía còn lại của nó. Ta hình dung hàng đợi như một dãy người xếp hàng tại một quầy hàng để mua một mặt hàng nào đó mà chỉ có thể thêm vào hàng đợi từ cuối và bớt đi phần tử ở đầu của hàng đợi; Một dãy các công việc trong một hệ thống máy tính đang chờ một thiết bị nào đó (chẳng hạn như máy in) hoặc một dãy máy bay đang trong đường dẫn ra đường băng để chuẩn bị cất cánh Hàng đợi là một cấu trúc dữ liệu trừu tượng, là một danh sách tuyến tính. Tuy nhiên điểm khác căn bản, có thể xem như đối lập với ngăn xếp là trong khi ngăn xếp hoạt động theo nguyên lý vào sau - ra trước (LiFo Last in - First out) thì hàng đợi hoạt động theo nguyên lý vào trước - ra trước (FiFo First in - First out). Với kiểu hàng đợi, ta quy ước chỉ có thể thực hiện các thao tác sau: + Khởi tạo một hàng đợi. 19
+ Đặt (put) một phần tử mới vào hàng đợi nếu hàng đợi chưa đầy. Phần tử dữ liệu mới luôn được thêm tại đuôi. + Nhận lại (get) một phần tử từ hàng đợi nếu hàng đợi khác rỗng. Phần tử bị loại là phần tử đang nằm tại đầu. + Kiểm tra xem hàng đợi có hay không có phần tử (rỗng hay không). + Kiểm tra xem hàng đợi đã đầy hay chưa  Mọi tác động khác vào hàng đợi đều phải thông qua các thao tác này. Như vậy: + Các phần tử của hàng đợi có cùng một kiểu nào đó + Hàng đợi là một trường hợp riêng của danh sách, được sử dụng trong các ứng dụng có liên quan đến sự bâor tồn thứ tự. Trong CTDL hàng đợi, dữ liệu thêm vào trước sẽ lấy ra trước, tính chất này còn được gọi là vào trước ra trước (First In First Out -FIFO).  Vì vậy, khi nói đến hàng đợi ta hiểu đó là danh sách kiểu FIFO Thực hiện mô hình hóa hàng đợi: - Ta cần tạo một cấu trúc danh sách tuyến tính và chuẩn bị các thao tác để có thể làm việc với danh sách này với tư cách là một hàng đợi. - Cần định nghĩa một kiểu danh sách để coi nó như hàng đợi, bao gồm cấu trúc dữ liệu được sử dụng và các đối tượng làm đầu và đuôi của hàng đợi. Do đó có thể chọn danh sách liên kết đơn với một con trỏ đến đầu danh sách và một con trỏ trỏ đến cuối (đuôi) hoặc mảng một chiều với hai tham số nguyên chỉ vị trí đầu và đuôi của hàng đợi. - Đôi khi cần gắn thêm một biến nguyên để lưu trữ thông tin về kích thước thực tế của hàng đợi. - Cần tạo các thủ tục/hàm để thao tác trên danh sách này với tư cách là thao tác hàng đợi bao gồm 5 thao tác đã nói ở trên. 2.2. Danh sách liên kết Danh sách liên kết là tập hợp các phần tử mà giữa chúng có một sự nối kết với nhau thông qua vùng liên kết của chúng. Sự nối kết giữa các phần tử trong danh sách liên kết đó là sự quản lý, ràng buộc lẫn nhau về nội dung của phần tử này và địa chỉ định vị phần tử kia. Tùy thuộc vào mức độ và cách thức nối kết mà danh sách liên kết có thể chia ra nhiều loại khác nhau: - Danh sách liên kết đơn (singly linked list); - Danh sách liên kết đôi/kép (doubly linked list); - Danh sách liên kết vòng (vòng đơn, vòng đôi) (circular linked list). Mỗi loại danh sách sẽ có cách biểu diễn các phần tử (cấu trúc dữ liệu) riêng và các thao tác trên đó. Danh sách liên kết (Linked List) là một cấu trúc dữ liệu tuyến tính, bao gồm một chuỗi các node kết nối với nhau. Mỗi node có thể xem như một phần tử trong 20