Thiết kế và giải thuật
II Chương 2: Kiểu dữ liệu nâng cao 20 5 14 1
2 Lưu trữ kế tiếp đối với danh sách tuyến tính
3 Lưu trữ móc nối đối với danh sách tuyến tính
IV Chương 4: Ngăn xếp và hàng đợi 20 8 11 1
1 Định nghĩa ngăn xếp (stack) 1 1
2 Lưu trữ stack bằng mảng 3 1 2
3.Ví dụ về ứng dụng stack 4 1 3
4 Định nghĩa hàng đợi(Queue) 2 1 1
5 Lưu trữ queue bằng mảng 5 2 3
6 Stack và queue móc nối 5 2 2 1
IV Chương 5: Sắp xếp và tìm kiếm 25 6 18 1
1 Giới thiệu về sắp xếp và tìm kiếm 3 2 1
2 Các phương pháp sắp xếp 10 2 8
3 Các phương pháp tìm kiếm 12 2 9 1
Chương 1 Giới thiệu cấu trúc dữ liệu và giải thuật
Mã chương: MH19_CH01 Giới thiệu:
Bài này giới thiệu về mối liên hệ giữa cấu trúc dữ liệu và giải thuật.
- Trình bày được kiến thức cở bản về cấu trúc dữ liệu, giải thuật, kiểu dữ liệu, mô hình dữ liệu;
- Phân tích được giải thuật;
- Sử dụng được các phương pháp phân tích, thiết kế giải thuật;
- Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, sáng tạo, thực hiện các thao tác an toàn với máy tính.
1 Mối liên hệ giữa cấu trúc dữ liệu và giải thuật
1.1 Xây dựng cấu trúc dữ liệu
Mọi chương trình máy tính đều cần dữ liệu để xử lý, bao gồm dữ liệu đầu vào, dữ liệu trung gian và dữ liệu đầu ra Do đó, việc tổ chức và lưu trữ dữ liệu là rất quan trọng trong toàn bộ hệ thống chương trình Cấu trúc dữ liệu được xây dựng sẽ ảnh hưởng lớn đến chất lượng và công sức của lập trình viên trong quá trình thiết kế và cài đặt chương trình.
Giải thuật, hay còn gọi là thuật giải, là phương pháp dùng để giải quyết vấn đề Nó có thể được diễn đạt bằng ngôn ngữ tự nhiên, sơ đồ hoặc mã giả Trong thực tế, giải thuật thường được thể hiện bằng mã giả dựa trên một hoặc nhiều ngôn ngữ lập trình, như C hay Pascal, mà lập trình viên chọn để triển khai thuật toán.
Khi đã xác định cấu trúc dữ liệu phù hợp, lập trình viên sẽ bắt đầu xây dựng thuật giải dựa trên cấu trúc đó Để giải quyết vấn đề, có nhiều phương pháp khác nhau, vì vậy việc chọn phương pháp thích hợp là rất quan trọng Sự lựa chọn này không chỉ ảnh hưởng đến hiệu quả giải quyết vấn đề mà còn giúp giảm bớt công việc trong việc cài đặt thuật toán trên ngôn ngữ lập trình cụ thể.
1.3 Mối quan hệ giữa cấu trúc dữ liệu và giải thuật
- 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
Để phát triển một chương trình máy tính hoàn chỉnh, việc có cấu trúc dữ liệu tốt và nắm vững thuật giải là điều kiện tiên quyết Khi đã có cấu trúc dữ liệu, việc lựa chọn ngôn ngữ lập trình chỉ còn là vấn đề thời gian Ngược lại, nếu không có cấu trúc dữ liệu, việc tìm ra thuật giải sẽ không khả thi Do đó, cả cấu trúc dữ liệu và thuật giải đều cần thiết để xử lý dữ liệu theo yêu cầu của bài toán.
2 Kiểu dữ liệu và mô hình dữ liệu
Trong máy tính điện tử, tất cả dữ liệu, bao gồm số nguyên, số thực và xâu ký tự, đều được chuyển đổi thành dạng nhị phân Mỗi loại dữ liệu này được biểu diễn dưới dạng các dãy số nhị phân 0 và 1.
Biểu diễn dữ liệu dưới dạng nhị phân là phương pháp tối ưu nhất, vì các giá trị 0 và 1 có thể dễ dàng mã hóa bằng các phần tử vật lý với hai trạng thái Trong bài viết này, chúng ta sẽ không đi sâu vào cách thức biểu diễn hay thực hiện các thao tác và phép toán trên dữ liệu nhị phân.
- Cách biểu diễn nhị phân của dữ liệu rất không thuận tiện đối với con người. Việc xuất hiện các ngôn ngữ lập trình bậc cao (FORTRAN, BASIC, PASSCAL,
Công nghệ đã giúp con người vượt qua những khó khăn trong việc xử lý dữ liệu bằng cách biểu diễn chúng trong máy tính Trong các ngôn ngữ lập trình bậc cao, dữ liệu là sự trừu tượng hóa các đặc tính của các đối tượng trong thế giới thực, nơi mà những yếu tố không cơ bản bị loại bỏ, chỉ giữ lại các đặc trưng quan trọng cho bài toán Ví dụ, vị trí của một đối tượng trong không gian được biểu diễn bằng cặp số thực (x,y) trong ngôn ngữ Pascal Các khái niệm toán học như số nguyên, số thực, số phức, dãy, và ma trận đã được áp dụng vào các ngôn ngữ lập trình, tạo ra các kiểu dữ liệu như nguyên, thực, phức, mảng và bản ghi Tuy nhiên, do tính đa dạng của các bài toán, việc chỉ sử dụng các kiểu dữ liệu có sẵn là không đủ, do đó cần thiết phải có các cấu trúc dữ liệu phức tạp, được xây dựng từ các dữ liệu đơn giản hơn thông qua các phương pháp liên kết.
Để giải quyết một bài toán bằng mô hình toán học, cần xây dựng mô hình dữ liệu mô tả các đặc trưng và mối quan hệ giữa các đối tượng trong vấn đề Chúng ta sử dụng các mô hình toán học như danh sách, cây, tập hợp, ánh xạ, quan hệ, và đồ thị để biểu diễn mô hình dữ liệu qua các cấu trúc dữ liệu Mỗi mô hình dữ liệu có thể được thể hiện bằng nhiều cấu trúc dữ liệu khác nhau, và tùy vào ứng dụng cụ thể, chúng ta sẽ chọn cấu trúc dữ liệu mang lại hiệu quả cao nhất cho các thao tác cần thực hiện.
2.2 Kiểu dữ liệu và cấu trúc dữ liệu
Trong các ngôn ngữ lập trình bậc cao, dữ liệu được phân loại thành các kiểu dữ liệu dựa trên bản chất của chúng Mỗi kiểu dữ liệu, như kiểu integer hay char, là một tập hợp các giá trị cụ thể Các ngôn ngữ lập trình khác nhau có các kiểu dữ liệu riêng, ví dụ, Fortran sử dụng các kiểu như integer, real, logical, complex và double complex, trong khi C có int, float, char, con trỏ và struct Ngôn ngữ Lisp lại sử dụng S-biểu thức Mỗi ngôn ngữ lập trình sở hữu một hệ kiểu riêng, bao gồm các kiểu dữ liệu cơ sở và các phương pháp để xây dựng kiểu dữ liệu mới từ các kiểu đã có.
- Khi nói đến một kiểu dữ liệu, chúng ta cần phải đề cập đến hai đặc trưng sau đây:
1 Tập hợp các giá trị thuộc kiểu Chẳng hạn, kiểu integer trong ngôn ngữ Pascal gồm tất cả các số nguyên được biểu diễn bởi hai byte, tức là gồm các số nguyên từ -32768 đến + 32767 Trong các ngôn ngữ lập trình bậc cao mỗi hằng, biến, biểu thức hoặc hàm cần phải được gắn với một kiểu dữ liệu xác định Khi đó, mỗi biến (biểu thức, hàm) chỉ có thể nhận các giá trị thuộc kiểu của biến (biểu thức, hàm) đó
Ví dụ , nếu X là biến có kiểu boolean trong Pascal (var X : boolean) thì X chỉ có thể nhận một trong hai giá trị true, false
2 Với mỗi kiểu dữ liệu, cần phải xác định một tập hợp nào đó các phép toán có thể thực hiện được trên các dữ liệu của kiểu Chẳng hạn, với kiểu real, các phép toán có thể thực hiện được là các phép toán số học thông thường +, -, *, / , và các phép toán so sánh = , < >, < , < =, >, > =.
Trong hệ kiểu của một ngôn ngữ lập trình, thường có các kiểu dữ liệu đơn, còn được gọi là kiểu dữ liệu phân tử (atomic).
Trong ngôn ngữ Pascal, các kiểu dữ liệu như integer, real, boolean, char và các kiểu liệt kê được phân loại là các kiểu dữ liệu đơn Chúng được gọi là đơn vì giá trị của chúng là những đơn thể cơ bản nhất, không thể tách rời thành các thành phần đơn giản hơn.
Khi giải quyết các bài toán phức tạp, việc chỉ sử dụng dữ liệu đơn là không đủ; chúng ta cần đến các cấu trúc dữ liệu Cấu trúc dữ liệu bao gồm một tập hợp các dữ liệu thành phần, được liên kết với nhau thông qua một phương pháp cụ thể Các dữ liệu thành phần này có thể là dữ liệu đơn hoặc là các cấu trúc dữ liệu đã được xây dựng Có thể hình dung cấu trúc dữ liệu như một tập hợp các tế bào, trong đó mỗi tế bào giống như một hộp chứa dữ liệu thành phần.
Trong Pascal và nhiều ngôn ngữ lập trình phổ biến khác, cách đơn giản nhất để liên kết các tế bào là sắp xếp chúng thành một dãy, với các tế bào chứa dữ liệu cùng kiểu Cấu trúc dữ liệu này được gọi là mảng (array).
File
2 Lưu trữ kế tiếp đối với danh sách tuyến tính
3 Lưu trữ móc nối đối với danh sách tuyến tính
IV Chương 4: Ngăn xếp và hàng đợi 20 8 11 1
1 Định nghĩa ngăn xếp (stack) 1 1
2 Lưu trữ stack bằng mảng 3 1 2
3.Ví dụ về ứng dụng stack 4 1 3
4 Định nghĩa hàng đợi(Queue) 2 1 1
5 Lưu trữ queue bằng mảng 5 2 3
6 Stack và queue móc nối 5 2 2 1
IV Chương 5: Sắp xếp và tìm kiếm 25 6 18 1
1 Giới thiệu về sắp xếp và tìm kiếm 3 2 1
2 Các phương pháp sắp xếp 10 2 8
3 Các phương pháp tìm kiếm 12 2 9 1
Chương 1 Giới thiệu cấu trúc dữ liệu và giải thuật
Mã chương: MH19_CH01 Giới thiệu:
Bài này giới thiệu về mối liên hệ giữa cấu trúc dữ liệu và giải thuật.
- Trình bày được kiến thức cở bản về cấu trúc dữ liệu, giải thuật, kiểu dữ liệu, mô hình dữ liệu;
- Phân tích được giải thuật;
- Sử dụng được các phương pháp phân tích, thiết kế giải thuật;
- Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, sáng tạo, thực hiện các thao tác an toàn với máy tính.
1 Mối liên hệ giữa cấu trúc dữ liệu và giải thuật
1.1 Xây dựng cấu trúc dữ liệu
Mọi chương trình máy tính đều cần dữ liệu để hoạt động, bao gồm dữ liệu đầu vào, dữ liệu trung gian và dữ liệu đầu ra Do đó, việc tổ chức và lưu trữ dữ liệu là rất quan trọng trong hệ thống chương trình Cấu trúc dữ liệu ảnh hưởng lớn đến chất lượng và công sức của lập trình viên trong quá trình thiết kế và cài đặt chương trình.
Giải thuật, hay còn gọi là thuật giải, là phương pháp để giải quyết vấn đề Giải thuật có thể được thể hiện qua ngôn ngữ tự nhiên, sơ đồ hoặc mã giả Trong thực tế, giải thuật thường được minh họa bằng mã giả dựa trên một hoặc nhiều ngôn ngữ lập trình, như C hay Pascal, tùy thuộc vào lựa chọn của lập trình viên.
Khi đã xác định cấu trúc dữ liệu phù hợp, lập trình viên sẽ bắt đầu xây dựng thuật giải theo yêu cầu của bài toán Có nhiều phương pháp để giải quyết một vấn đề, vì vậy việc lựa chọn phương pháp thích hợp là rất quan trọng Sự lựa chọn này không chỉ ảnh hưởng đến hiệu quả của thuật toán mà còn giúp giảm bớt công việc trong quá trình cài đặt trên ngôn ngữ lập trình cụ thể.
1.3 Mối quan hệ giữa cấu trúc dữ liệu và giải thuật
- 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
Khi đã thiết lập được cấu trúc dữ liệu tốt và nắm vững giải thuật, việc triển khai chương trình bằng một ngôn ngữ lập trình cụ thể chỉ còn là vấn đề thời gian Cấu trúc dữ liệu và giải thuật là hai yếu tố không thể thiếu; thiếu một trong hai, chương trình sẽ không thể hoàn thiện Một chương trình máy tính chỉ có thể hoạt động hiệu quả khi kết hợp đầy đủ cả cấu trúc dữ liệu để lưu trữ và giải thuật để xử lý dữ liệu theo yêu cầu của bài toán.
2 Kiểu dữ liệu và mô hình dữ liệu
Trong máy tính điện tử, mọi loại dữ liệu, bao gồm số nguyên, số thực và xâu ký tự, đều được chuyển đổi thành định dạng nhị phân Mỗi loại dữ liệu này được biểu diễn dưới dạng một chuỗi các số nhị phân 0 và 1.
Biểu diễn dữ liệu dưới dạng nhị phân là phương pháp tối ưu nhất, vì các giá trị 0 và 1 có thể dễ dàng được mã hóa bằng các phần tử vật lý với hai trạng thái Chúng ta sẽ không đi sâu vào cách biểu diễn này hay các thao tác, phép toán liên quan đến dữ liệu nhị phân.
- Cách biểu diễn nhị phân của dữ liệu rất không thuận tiện đối với con người. Việc xuất hiện các ngôn ngữ lập trình bậc cao (FORTRAN, BASIC, PASSCAL,
Công nghệ đã giúp con người vượt qua những khó khăn trong việc làm việc với dữ liệu Trong các ngôn ngữ lập trình bậc cao, dữ liệu được coi là sự trừu tượng hóa các đặc điểm của đối tượng trong thế giới thực, chỉ giữ lại những thuộc tính quan trọng cho bài toán đang giải quyết Ví dụ, vị trí của một đối tượng trong thực tế được biểu diễn bằng cặp số thực (x,y) trong mặt phẳng, và trong ngôn ngữ Pascal, điều này được thể hiện qua bản ghi với hai trường tương ứng Các khái niệm toán học như số nguyên, số thực, số phức, và ma trận đã được tích hợp vào các ngôn ngữ lập trình, nhưng do tính đa dạng của các bài toán, chỉ sử dụng các kiểu dữ liệu có sẵn là không đủ Do đó, cần có các cấu trúc dữ liệu phức tạp, được xây dựng từ các dữ liệu đơn giản hơn thông qua các phương pháp liên kết.
Để giải quyết bài toán bằng mô hình toán học, cần xây dựng mô hình dữ liệu mô tả các đặc trưng và mối quan hệ giữa các đối tượng liên quan Chúng ta sử dụng các mô hình toán học như danh sách, cây, tập hợp, ánh xạ, quan hệ và đồ thị để biểu diễn mô hình dữ liệu qua các cấu trúc dữ liệu Mỗi mô hình dữ liệu có thể được thể hiện bằng nhiều cấu trúc khác nhau, và tùy thuộc vào ứng dụng cụ thể, chúng ta sẽ lựa chọn cấu trúc dữ liệu phù hợp nhất để thực hiện các thao tác một cách hiệu quả.
2.2 Kiểu dữ liệu và cấu trúc dữ liệu
Trong các ngôn ngữ lập trình bậc cao, dữ liệu được phân loại thành các kiểu dữ liệu dựa trên bản chất của chúng Mỗi kiểu dữ liệu, như kiểu integer hoặc char, là một tập hợp các giá trị cụ thể Các ngôn ngữ lập trình khác nhau có các kiểu dữ liệu riêng, ví dụ, Fortran sử dụng các kiểu integer, real, logical, complex và double complex, trong khi C có int, float, char, con trỏ và struct Lisp lại sử dụng S-biểu thức Mỗi ngôn ngữ lập trình sở hữu một hệ kiểu riêng, bao gồm các kiểu dữ liệu cơ sở và các phương pháp để xây dựng các kiểu dữ liệu mới từ những kiểu đã có.
- Khi nói đến một kiểu dữ liệu, chúng ta cần phải đề cập đến hai đặc trưng sau đây:
1 Tập hợp các giá trị thuộc kiểu Chẳng hạn, kiểu integer trong ngôn ngữ Pascal gồm tất cả các số nguyên được biểu diễn bởi hai byte, tức là gồm các số nguyên từ -32768 đến + 32767 Trong các ngôn ngữ lập trình bậc cao mỗi hằng, biến, biểu thức hoặc hàm cần phải được gắn với một kiểu dữ liệu xác định Khi đó, mỗi biến (biểu thức, hàm) chỉ có thể nhận các giá trị thuộc kiểu của biến (biểu thức, hàm) đó
Ví dụ , nếu X là biến có kiểu boolean trong Pascal (var X : boolean) thì X chỉ có thể nhận một trong hai giá trị true, false
2 Với mỗi kiểu dữ liệu, cần phải xác định một tập hợp nào đó các phép toán có thể thực hiện được trên các dữ liệu của kiểu Chẳng hạn, với kiểu real, các phép toán có thể thực hiện được là các phép toán số học thông thường +, -, *, / , và các phép toán so sánh = , < >, < , < =, >, > =.
Trong một hệ kiểu của ngôn ngữ lập trình, thường có các kiểu dữ liệu đơn, hay còn gọi là kiểu dữ liệu phân tử (atomic).
Trong ngôn ngữ Pascal, các kiểu dữ liệu như integer, real, boolean, char và kiểu liệt kê được phân loại là các kiểu dữ liệu đơn Chúng được gọi là đơn vì giá trị của những kiểu này là những đơn thể cơ bản, không thể phân tách thành các thành phần đơn giản hơn.
Khi giải quyết các bài toán phức tạp, việc chỉ sử dụng dữ liệu đơn không đủ, mà cần đến các cấu trúc dữ liệu Cấu trúc dữ liệu bao gồm một tập hợp các dữ liệu thành phần liên kết với nhau bằng một phương pháp nhất định Các dữ liệu thành phần này có thể là dữ liệu đơn hoặc là các cấu trúc dữ liệu đã được xây dựng Có thể hình dung cấu trúc dữ liệu như một tập hợp các tế bào, trong đó mỗi tế bào giống như một hộp chứa dữ liệu thành phần.
Trong Pascal và nhiều ngôn ngữ lập trình phổ biến khác, cách đơn giản nhất để liên kết các tế bào là sắp xếp chúng thành một dãy, với các tế bào chứa dữ liệu cùng kiểu Cấu trúc dữ liệu này được gọi là mảng (array).
