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) - Trường Cao đẳng Xây dựng số 1

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

Thêm vào BST

Báo xấu

13
lượt xem 5
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)" đượ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) - 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 TRÌNH ĐỘ: CAO ĐẲNG Ban hành kèm theo Quyết định số: 368ĐT/QĐ- CĐXD1 ngày 10 tháng 08 năm 2021 của Hiệu trưởng trường CĐXD số 1 Hà Nội, năm 2021
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.
MỤC LỤC CHƯƠNG 1: GIẢI THUẬT ................................................................................. 2 1.1. Các khái niệm ............................................................................................. 2 1.1.1. Giải thuật ............................................................................................. 2 1.1.2. Cấu trúc dữ liệu ................................................................................... 2 1.2. Các đặc trưng của giải thuật ....................................................................... 2 1.2.1. Dữ liệu vào .......................................................................................... 3 1.2.2. Dữ liệu ra ............................................................................................. 3 1.2.3. Tính hiệu quả....................................................................................... 3 1.2.4. Tính chính xác ..................................................................................... 3 1.2.5. Tính ứng dụng ..................................................................................... 3 1.2.6. Tính hữu hạn ....................................................................................... 3 1.3. Ngôn ngữ diễn đạt ...................................................................................... 3 1.3.1. Ngôn ngữ thông thường ...................................................................... 3 1.3.2. Lưu đồ ................................................................................................. 3 1.3.3. Ngôn ngữ lập trình .............................................................................. 5 1.4. Phương pháp thiết kế giải thuật.................................................................. 6 1.4.1. Mô-đun hóa và việc giải quyết bài toán .................................................. 6 1.4.2. Tinh chỉnh từng bước .......................................................................... 6 1.5. Đánh giá độ phức tạp của giải thuật ........................................................... 8 1.5.1. Đặt vấn đề............................................................................................ 8 1.5.2. Độ phức tạp tính toán của giải thuật ................................................... 8 1.5.3. Xác định độ phức tạp tính toán ........................................................... 8 CHƯƠNG 2: DANH SÁCH ............................................................................... 11 2.1. Danh sách tuyến tính ................................................................................ 11 2.1.1. Khái niệm chung ............................................................................... 11 2.1.2. Kiểu mảng ......................................................................................... 11 2.1.3. Kiểu ngăn xếp.................................................................................... 12 2.1.4. Kiểu hàng đợi .................................................................................... 14 ii
2.2. Danh sách liên kết .................................................................................... 15 2.2.1. Danh sách liên kết đơn (singly linked list) ....................................... 16 2.2.3. Các dạng khác của danh sách liên kết ............................................... 24 CHƯƠNG 3: MÔ HÌNH CÂY VÀ ĐỒ THỊ ...................................................... 29 3.1. Mô hình cây .............................................................................................. 29 3.1.1. Định nghĩa và các phép toán ............................................................. 29 3.1.2. Cây nhị phân...................................................................................... 29 3.2. Đồ thị ........................................................................................................ 31 3.2.1. Định nghĩa và các phép toán ............................................................. 31 3.2.2. Biểu diễn đồ thị ................................................................................. 33 3.3. Phép duyệt đồ thị ...................................................................................... 35 3.3.1. Duyệt theo chiều rộng ....................................................................... 35 3.3.2. Duyệt theo chiều sâu ......................................................................... 37 3.4. Áp dụng .................................................................................................... 38 3.4.1. Tìm đường đi ngắn nhất của đồ thị ................................................... 38 3.4.2. Tìm cây khung nhỏ nhất của đồ thị ................................................... 39 CHƯƠNG 4: CÁC GIẢI THUẬT SẮP XẾP VÀ TÌM KIẾM........................... 46 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 iii
iv
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 chính quy 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 v
Tên môn học: CẦU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mã môn học: MH13 Thời gian thực hiện môn học: 60 giờ; (Lý thuyết: 30 giờ; Thực hành, thí nghiệm, thảo luận, bài tập: 27giờ; Kiểm tra:3 giờ) I. Vị trí, tính chất của môn học: - Vị trí: Môn 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, mô đun đào tạo ngành Công nghệ thông tin. - Tính chất: Môn Cấu trúc dữ liệu được ứng dụng rộng rãi 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. vi
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ể.
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. - 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ể 2
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.2.3. Tính hiệu quả Một giải thuật nên là có thể thi hành được với các nguồn có sẵn, tức là có khả năng giải quyết hiệu quả vấn đề trong điều kiện thời gian và tài nguyên cho phép. 1.2.4. Tính chính xác Giải thuật nên rõ ràng và không mơ hồ. Mỗi một giai đoạn (hay mỗi bước) nên rõ ràng và chỉ mang một mục đích nhất định. 1.2.5. Tính ứng dụng Một giải thuật có tính phổ biến nếu giải thuật này có thể giải quyết được một lớp các vấn đề tương tự. 1.2.6. Tính hữu hạn Các giải thuật phải kết thúc sau một số hữu hạn các bước. 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ý. 3
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. 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: 4
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) 5
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. Mô-đun hóa và việc giải quyết bài toá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. 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: 6
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 7
1.5. Đánh giá độ phức tạp của giải thuật 1.5.1. Đặt vấn đề Tính hiệu quả của thuật toán thông thường được đo bằng thời gian tính (thời gian được sử dụng để tính bằng máy hoặc bằng phương pháp thủ công) khi các giá trị đầu vào có kích thước xác định. Tính hiệu quả của thuật toán cũng được xem xét theo thước đo dung lượng bộ nhớ đã sử dụng để tính toán khi kích thước đầu vào đã xác định. Hai thước đo trên liên quan đến độ phức tạp tính toán của một thuật toán, được gọi là độ phức tạp thời gian và độ phức tạp không gian (còn gọi là độ phức tạp dung lượng nhớ). 1.5.2. Độ phức tạp tính toán của giải thuật Độ phức tạp thuật toán là một hàm phụ thuộc đầu vào. Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm bậc O - lớn. Bậc O - lớn: Gọi n là độ lớn đầu vào, độ phức tạp của bài toán phụ thuộc vào n. Ở đây, ta không chỉ đặc trưng độ phức tạp bởi số lượng phép tính, mà dùng một đại lượng tổng quát là tài nguyên cần dùng R(n). Nếu tìm được hằng số C sao cho n đủ lớn, các hàm R(n), g(n) đều dương và R(n) < C.g(n) thì ta nói thuật toán có độ phức tạp cỡ O(g(n)). 1.5.3. Xác định độ phức tạp tính toán Độ phức tạp hằng số, O(1): Số phép tính/ thời gian chạy/ dung lượng bộ nhớ không phụ thuộc vào độ lớn đầu vào. Độ phức tạp tuyến tính, O(n): Số phép tính/ thời gian chạy/ dung lượng bộ nhớ có xu hướng tỉ lệ thuận với độ lớn đầu vào; Độ phức tạp đa thức, O(P(n)), với P là đa thức bậc cao (từ 2 trở lên); Độ phức tạp logarit, O(logn) (chú ý: Bậc của nó thấp hơn so với O(n)); Độ phức tạp hàm mũ O (an). Trường hợp này bất lợi nhất và sẽ rất phi thực tế nếu thực hiện thuật toán với độ phức tạp này. 8
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 9
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 đó. 10
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ử 11
+ 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. 12
- 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: 13