Giáo trình Cấu trúc dữ liệu và giải thuật

BỘ NÔNG NGHIỆP VÀ PHÁT TRIỂN NÔNG THÔN

TRƯỜNG CAO ĐẲNG CƠ GIỚI NINH BÌNH

GIÁO TRÌNH

MÔN HỌC: MH19_CẤU TRÚC DỮ LIỆU

VÀ GIẢI THUẬT

NGHỀ: LẬP TRÌNH MÁY TÍNH

TRÌNH ĐỘ: Cao đẳng/ trung cấp

Ban hành kèm theo Quyết định số:

/QĐ-…TCGNB ngày…….tháng….năm ....

của Hiệu trưởng Trường Cao Đẳng Cơ giới Ninh Bình

Ninh Bình, năm 2018

1

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.

2

Lời giới thiệu

Các kiến thức về cấu trúc dữ liệu (CTDL) và giải thuật đóng vai trò quan

trọng trong việc đào tạo nghề Lập trình máy tính. Sách này đựơc hình thành trên cơ

sở các bài giảng về CTDL và giải thuật mà tôi cùng các đồng nghiệp đã đọc nhiều

năm tại khoa Toán-Cơ-Tin học - Trường Đại học Khoa học Tự nhiên – Đại học

Quốc Gia Hà Nội; Khoa Công nghệ thông tin - Đại học Bách Khoa Hà Nội; Khoa

Công nghệ thông tin - Đại học Giao thông vận tải. Sách được biên soạn chủ yếu để

làm tài liệu tham khảo cho học sinh, sinh viên nghề Lập trình máy tính, nhưng nó

cũng rất bổ ích cho các độc giả khác cần có hiểu biết đầy đủ hơn về CTDL và giải

thuật.

Giáo trình này gồm bốn chương

Chương 1. Giới thiệu về cấu trúc dữ liệu và giải thuật

Chương 2. Kiểu dữ liệu nâng cao

Chương 3. Danh sách

Chương 4. Ngăn xếp và hàng đợi

Chương 5. Sắp xếp và tìm kiếm

Để biên soạn giáo trình này, chúng tôi đã tham khảo các tài liệu: Cấu trúc dữ

liệu và giải thuật, PTS Đinh Mạnh Tường; Lê Minh Hoàng, Cấu trúc dữ liệu và

giải thuật.

Giáo trình Cấu trúc dữ liệu và giải thuật đã được Hổi đồng thẩm định

Trường Cao đẳng nghề Cơ Giới Ninh Bình xét duyệt. Tuy nhiên trong quá trình

biên soạn không tránh khỏi những sai sót, rất mong được sự đóng góp quý báu

chân thành của bạn đọc.

Ninh Bình, ngày tháng năm 2018

Tham gia biên soạn:

1. Chủ biên Đoàn Xuân Luận

2. Phạm Thị Thoa

3. Nguyễn Anh Văn

3

Mục lục

Lời giới thiệ u .............................................................................................................3

Mục lục ......................................................................................................................4

Chương 1. Giới thiệu cấu trúc dữ liệu và giải thuật ..................................................8

1. Mối liên hệ giữa cấu trúc dữ liệu và giải thuậ t ..................................................9

1.1. Xây dựng cấu trúc dữ liệu ..........................................................................9

1.2. Xây dựng giải thuật ....................................................................................9

1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuậ t .......................................10

2. Kiểu dữ liệu và mô hình dữ liệ u ......................................................................10

2.1. Biểu diễn dữ liệu ......................................................................................10

2.3. Hệ kiểu của ngôn ngữ Pascal....................................................................14

2.4. Mô hình dữ liệu và kiểu dữ liệu trừu tượng .............................................16

3. Thiết kế và giải thuậ t .......................................................................................20

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

3.2. Đánh giá độ phức tạp của thuật toán ........................................................21

Chương 2. Các kiểu dữ liệu nâng cao......................................................................22

1. Mảng ................................................................................................................22

2. Con tr ỏ .............................................................................................................24

2.1. Con trỏ và địa chỉ .....................................................................................24

2.2. Con trỏ và mảng một chiều ......................................................................26

2.3. Con trỏ và mảng nhiều chiều ....................................................................30

2.4. Kiểu con trỏ, kiểu địa chỉ, các phép toán trên con tr ỏ ..............................32

3. Cấu trúc và hợp ................................................................................................39

3.1. Cấu trúc (struct)........................................................................................39

3.2. Kiểu union ................................................................................................40

4. File...................................................................................................................41

4.1. Khái niệm về tệp tin .................................................................................41

4.2. Khai báo sử dụng tệp - một số hàm thường dùng khi thao tác trên tệp ...43

Chương 3. Danh sách ..............................................................................................49

1. Các khái niệ m ..................................................................................................49

1.1. Khái niệm về danh sách............................................................................49

4

1.2. Các phép toán trên danh sác h ...................................................................49

2. Lưu tữ kế tiếp đối với danh sách tuyến tín h ....................................................51

2.1. Định nghĩa ................................................................................................51

2.2. Danh sách liên kết đơn (Singly Linked List)............................................51

3. Lưu trữ móc nối đối với danh sách tuyến tính.................................................76

3.1. Cấu trúc dữ liệu ........................................................................................76

3.2. Các thao tác trên danh sách ......................................................................78

Chương 4. Ngăn xếp và hàng đợ i ..........................................................................100

1. Định nghĩa ngăn xếp (stack)..........................................................................100

2. Lưu trữ stack bằng mản g ...............................................................................102

2.1. Khởi tạo ngăn xếp ...................................................................................102

2.2. Thêm (Đẩy) một phần tử vào ngăn xếp (Push) ......................................102

2.3. Lấy nội dung một phần tử trong ngăn xếp ra để xử lý (Pop) .................103

2.4. Hủy ngăn xếp ..........................................................................................104

3.Ví dụ về ứng dụng stac k .................................................................................104

4. Định nghĩa hàng đợi(Queue ).........................................................................108

5. Lưu trữ queue bằng mảng ..............................................................................110

5.1. Khởi tạo hàng đợi (Initialize) .................................................................110

5.2. Thêm (Đưa) một phần tử vào hàng đợi (Add)........................................111

5.3. Lấy nội dung một phần tử trong hàng đợi ra để xử lý (Get) ..................112

5.4. Hủy hàng đợi ..........................................................................................113

6. Stack và queue móc nối .................................................................................113

6.1. Stack móc nối .........................................................................................113

6.2. Queue móc nối ........................................................................................116

Chương 5. Sắp xếp và tìm kiếm ............................................................................119

1. Giới thiệu về sắp xếp và tìm kiếm .................................................................119

1.1. Giới thiệu về sắp xế p ..............................................................................119

1.2. Giới thiệu về tìm kiếm ............................................................................120

2. Các phương pháp sắp xếp ..............................................................................121

2.1. Sắp xếp kiểu chọn (Selection sort ).........................................................121

2.2. Thuật toán sắp xếp nổi bọt (bubble sort )................................................122

5

MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

Tên Môn học: Cấu trúc dữ liệu và giải thuật

Mã môn học: MH19

Vị trí, tính chất, ý nghĩa và vai trò của môn học:

- Vị trí môn học: Môn học này được học sau môn học Tin học căn bản, Lập trình

căn bản.

- Tính chất môn học: Môn học này yêu cầu phải có tư duy logic và các kiến thức

về lập trình căn bản, lập trình hướng đối tượng.

- Ý nghĩa, vai trò của môn học: Đây là môn học cơ sở ngành của các ngành liên

quan đến công nghệ thông tin, cung cấp cho sinh viên các kiến thức cơ bản về

lập trình.

Mục tiêu của môn học:

- Kiến thức:

+ Trình bày được mối liên hệ giữa cấu trúc dữ liệu và giải thuật; cách khai báo

và sử dụng các kiểu dữ liệu nâng cao;

+ Trình bày được các kỹ thuật ngăn xếp và hàng đợi, các thuật toán sắp xếp và

tìm kiếm, các loại danh sách liên kết.

- Kỹ năng:

+ Phân tích được các loại dữ liệu, giải thuật và kết hợp được dữ liệu và giải

thuật;

+ Cài đặt được các thuật toán sắp xếp và tìm kiếm;

+ Cài đặt được các thuật toán trên các cấu trúc dữ liệu: mảng, danh sách, danh

sách liên kết.

- Thái độ:

+ Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, sáng tạo, làm việc độc lập và theo

nhóm;

+ Rèn luyện kỹ năng lập trình;

+ Đảm bảo an toàn cho người và trang thiết bị.

Nội dung của môn học:

7

Thời gian

Lý Thực Kiểm

thuyết hành

Số

Tên chương mục

Tổng

số

TT

tra

0

I

Chương 1: Giới thiệu cấu trúc dữ liệu và

giải thuật

5

0

1. Mỗi liên hệ giữa cấu trúc dữ liệu và giải

thuật

1

2. Kiểu dữ liệu và mô hình dữ liệu

3. Thiết kế và giải thuật

2

5

1

2

1

6

2

II Chương 2: Kiểu dữ liệu nâng cao

1. Kiểu mảng

20

5

14

4

1

2. Con trỏ

5

4

3. Cấu trúc và hợp

5

3

4. File

5

3

1

III Chương 3: Danh sách

1. Các khái niệm

20

5

13

3

1

2. Lưu trữ kế tiếp đối với danh sách tuyến

tính

7

5

3. Lưu trữ móc nối đối với danh sách tuyến

tính

8

2

5

1

IV Chương 4: Ngăn xếp và hàng đợi

1. Định nghĩa ngăn xếp (stack)

2. Lưu trữ stack bằng mảng

3.Ví dụ về ứng dụng stack

4. Định nghĩa hàng đợi(Queue)

5. Lưu trữ queue bằng mảng

6. Stack và queue móc nối

IV Chương 5: Sắp xếp và tìm kiếm

1. Giới thiệu về sắp xếp và tìm kiếm

2. Các phương pháp sắp xếp

3. Các phương pháp tìm kiếm

Cộng

20

1

8

1

11

1

3

1

2

3

4

1

2

1

5

2

3

5

2

1

25

3

6

18

1

2

10

12

90

2

8

2

9

1

30

56

4

8

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.

Mục tiêu:

- 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.

Nội dung:

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

- Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu

để xử lý. Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian hoặc

dữ liệu đưa ra (output data). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho

chương trình có ý nghĩa rất quan trọng trong toàn bộ hệ thống chương trình.

Việc xây dựng cấu trúc dữ liệu quyết định rất lớn đến chất lượng cũng như công

sức của người lập trình trong việc thiết kế, cài đặt chương trình.

1.2. Xây dựng 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, …

9

- 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.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

- 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.

2. Kiểu dữ liệu và mô hình dữ liệu

2.1. Biểu diễn dữ liệu

- Trong máy tính điện tử (MTĐT), các dữ liệu dù có bản chất khác nhau như thế

nào (số nguyên, số thực, hay xâu ký tự, ...), đều được biểu diễn dưới dạng nhị

phân. Mỗi dữ liệu được biểu diễn dưới dạng một dãy các số nhị phân 0 hoặc 1.

Về mặt kỹ thuật đây là cách biểu diễn thích hợp nhất, vì các giá trị 0 và 1 dễ

dàng được mã hoá bởi các phần tử vật lý chỉ có hai trạng thái. Chúng ta sẽ

không quan tâm đến cách biểu diễn này của dữ liệu, cũng như các cách tiến

hành các thao tác, các phép toán trên các dữ liệu được biểu diễn dưới dạng 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 ...) đã giải phóng con người khỏi những khó khăn khi làm việc

với cách biểu diễn trong máy của dữ liệu. Trong các ngôn ngữ lập trình bậc cao,

10

các dữ liệu, hiểu theo một nghĩa nào đó, là sự trìu tượng hoá các tính chất của

các đối tượng trong thế giới hiện thực. Nói dữ liệu là sự trìu tượng hoá từ thế

giới hiện thực, vì ta đã bỏ qua những nhân tố, tính chất mà ta cho là không cơ

bản, chỉ giữ lại những tính chất đặc trưng cho các đối tượng thuộc phạm vi bài

toán đang xét. Chẳng hạn, vị trí của một đối tượng trong thực tiễn, được đặc

trưng bởi cặp số thực (x,y) (đó là toạ đoạ đê-các của một điểm trong mặt

phẳng). Do đó, trong ngôn ngữ Pascal, vị trí một đối tượng được biểu diễn bởi

bản ghi gồm hai trường tương ứng với hoành độ và tung độ của một điểm.

Trong toán học có các khái niệm biểu diễn đặc trưng về mặt số lượng và các

quan hệ của các đối tượng trong thế giới hiện thực, đó là các khái niệm số

nguyên, số thực, số phức, dãy, ma trận, ... Trên cơ sở các khái niệm toán học

này, người ta đã đưa vào trong các ngôn ngữ lập trình bậc cao các dữ liệu kiểu

nguyên, thực, phức, mảng, bản ghi, ... Tuy nhiên do tính đa dạng của các bài

toán cần xử lý bằng MTĐT, chỉ sử dụng các kiểu dữ liệu có sẵn trong các ngôn

ngữ lập trình bậc cao là chưa đủ để mô tả các bài toán. Chúng ta phải cần đến

các cấu trúc dữ liệu. Đó là các dữ liệu phức tạp, được xây dựng nên từ các dữ

liệu đã có, đơn giản hơn bằng các phương pháp liên kết nào đó.

- Để giải quyết một bài toán bằng MTĐT, ta cần xây dựng mô hình dữ liệu mô tả

bài toán. Đó là sự trìu tượng hoá các đặc trưng của các đối tượng thuộc phạm vi

vấn đề mà ta quan tâm, các mối quan hệ giữa các đối tượng đó. Dùng làm các

mô hình dữ liệu trong tin học, chúng ta sẽ 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ệ, đồ thị, ... Mô hình dữ liệu sẽ được

biểu diễn bởi các cấu trúc dữ liệu. Thông thường một mô hình dữ liệu có thể

được biểu hiện bởi nhiều cấu trúc dữ liệu khác nhau. Tuỳ từng ứng dụng, ta sẽ

chọn cấu trúc dữ liệu nào mà các thao tác cần thực hiện là hiệu quả nhất có thể

được.

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, các dữ liệu được phân lớp thành các lớp

dữ liệu dựa vào bản chất của dữ liệu. Mỗi một lớp dữ liệu được gọi là một kiểu

dữ liệu. Như vậy, một kiểu T là một tập hợp nào đó, các phần tử của tập được

gọi là các giá trị của kiểu. Chẳng hạn, kiểu integer là tập hợp các số nguyên,

11

kiểu char là một tập hữu hạn các ký hiệu. Các ngôn ngữ lập trình khác nhau có

thể có các kiểu dữ liệu khác nhau. Fortran có các kiểu dữ liệu là integer, real,

logical, complex và double complex. Các kiểu dữ liệu trong ngôn ngữ C là int,

float, char, con trỏ, struct..., Kiểu dữ liệu trong ngôn ngữ Lisp lại là các S-biểu

thức. Một cách tổng quát, mỗi ngôn ngữ lập trình có một hệ kiểu của riêng

mình. Hệ kiểu của một ngôn ngữ bao gồm các kiểu dữ liệu cơ sở và các phương

pháp cho phép ta từ các kiểu dữ liệu đã có xây dựng nên các kiểu dữ liệu mới.

- 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 = , < >, < , < =, >, > =.

- Thông thường trong một hệ kiểu của một ngôn ngữ lập trình sẽ có một số kiểu

dữ liệu được gọi là kiểu dữ liệu đơn hay kiểu dữ liệu phân tử (atomic).

- Chẳng hạn, trong ngôn ngữ Pascal, các kiểu dữ liệu integer, real, boolean , char

và các kiểu liệt kê được gọi là các kiểu dữ liệu đơn. Sở dĩ gọi là đơn, vì các giá

trị của các kiểu này được xem là các đơn thể đơn giản nhất không thể phân tích

thành các thành phần đơn giản hơn được nữa.

- Như đã nói, khi giải quyết các bài toán phức tạp, chỉ sử dụng các dữ liệu đơn là

không đủ, ta phải cần đến các cấu trúc dữ liệu. Một cấu trúc dữ liệu bao gồm

một tập hợp nào đó các dữ liệu thành phần, các dữ liệu thành phần này được

liên kết với nhau bởi một phương pháp nào đó. Các dữ liệu thành phần có thể là

12

dữ liệu đơn, hoặc cũng có thể là một cấu trúc dữ liệu đã được xây dựng. Có thể

hình dung một cấu trúc dữ liệu được tạo nên từ các tế bào (khối xây dựng), mỗi

tế bào có thể xem như một cái hộp chứa dữ liệu thành phần.

- Trong Pascal và trong nhiều ngôn ngữ thông dụng khác có một cách đơn giản

nhất để liên kết các tế bào, đó là sắp xếp các tế bào chứa các dữ liệu cùng một

kiểu thành một dãy. Khi đó ta có một cấu trúc dữ liệu được gọi là mảng (array).

Như vậy, có thể nói, một mảng là một cấu trúc dữ liệu gồm một dãy xác định

các dữ liệu thành phần cùng một kiểu. Ta vẫn thường nói đến mảng các số

nguyên, mảng các số thực, mảng các bản ghi, ... Mỗi một dữ liệu thành phần

của mảng được gắn với một chỉ số từ một tập chỉ số nào đó. Ta có thể truy cập

đến một thành phần nào đó của mảng bằng cách chỉ ra tên mảng và chỉ số của

thành phần đó.

- Một phương pháp khác để tạo nên các cấu trúc dữ liệu mới, là kết hợp một số tế

bào (có thể chứa các dữ liệu có kiểu khác nhau) thành một bản ghi (record).

Các tế bào thành phần của bản ghi được gọi là các trường của bản ghi. Các bản

ghi đến lượt lại được sử dụng làm các tế bào để tạo nên các cấu trúc dữ liệu

khác. Chẳng hạn, một trong các cấu trúc dữ liệu hay được sử dụng nhất là mảng

các bản ghi.

- Còn một phương pháp quan trọng nữa để kiến tạo các cấu trúc dữ liệu, đó là sử

dụng con trỏ. Trong phương pháp này, mỗi tế bào là một bản ghi gồm hai phần

INFOR và LINK, phần INFOR có thể có một hay nhiều trường dữ liệu, còn

phần LINK có thể chứa một hay nhiều con trỏ trỏ đến các tế bào khác có quan

hệ với tế bào đó. Chẳng hạn, ta có thể cài đặt một danh sách bởi cấu trúc dữ liệu

danh sách liên kết, trong đó mỗi thành phần của danh sách liên kết là bản ghi

gồm hai trường

type Cell = record

element : Item ;

next : ^Cell ;

end ;

13

- Ở đây, trường element có kiểu dữ liệu Item, một kiểu dữ liệu nào đó của các

phần tử của danh sách. Trường next là con trỏ trỏ tới phần tử tiếp theo trong

danh sách. Cấu trúc dữ liệu danh sách liên kết biểu diễn danh sách (a₁, a₂,...., a_n)

có thể được biểu diễn như trong hình

a₁

a₂

a_n

.

Hình 1.1: Cấu trúc dữ liệu danh sách liên kết.

- Sử dụng con trỏ để liên kết các tế bào là một trong các phương pháp kiến tạo

các cấu trúc dữ liệu được áp dụng nhiều nhất. Ngoài danh sách liên kết, người

ta còn dùng các con trỏ để tạo ra các cấu trúc dữ liệu biểu diễn cây, một mô

hình dữ liệu quan trọng bậc nhất.

- Trên đây chúng ta đã nêu ba phương pháp chính để kiến tạo các cấu trúc dữ

liệu. (Ở đây chúng ta chỉ nói đến các cấu trúc dữ liệu trong bộ nhớ trong, các

cấu trúc dữ liệu ở bộ nhớ ngoài như file chỉ số, B-cây sẽ được đề cập riêng.)

- Một kiểu dữ liệu mà các giá trị thuộc kiểu không phải là các dữ liệu đơn mà là

các cấu trúc dữ liệu được gọi là kiểu dữ liệu có cấu trúc. Trong ngôn ngữ

Pascal, các kiểu dữ liệu mảng, bản ghi, tập hợp, file đều là các kiểu dữ liệu có

cấu trúc.

2.3. Hệ kiểu của ngôn ngữ Pascal

- Pascal là một trong các ngôn ngữ có hệ kiểu phong phú nhất. Hệ kiểu của

Pascal chứa các kiểu cơ sở, integer, real, boolean, char và các quy tắc, dựa vào

đó ta có thể xây dựng nên các kiểu phức tạp hơn từ các kiểu đã có. Từ các kiểu

cơ sở và áp dụng các quy tắc, ta có thể xây dựng nên một tập hợp vô hạn các

kiểu. Hệ kiểu của Pascal có thể được định nghĩa định quy như sau :

Các kiểu cơ sở

1. Kiểu integer

2. Kiểu real

3. Kiểu boolean

14

4. Kiểu char

5. Kiểu liệt kê

Giả sử obj1, obj2,.... objn là các đối tượng nào đó. khi đó ta có thể tạo nên

kiểu liệt kê T bằng cách liệt kê ra tất cả các đói tượng đó.

type T = (obj1, obj2,...objn)

- Chú ý. Tất cả các kiểu đơn đều là các kiểu có thứ tự, tức là với hai giá trị bất kỳ

a và b thuộc cùng một kiểu, ta luôn có a  b hoặc a   b. trừ kiểu real, các

kiểu còn lại đều là kiểu có thứ tự đếm được.

6. Kiểu đoạn con

type T = min . max

- Trong đó min và max là cận dưới và cận trên của khoảng ; min và max là các

giá trị thuộc cùng một kiểu integer, char, hoặc các kiểu liệt kê, đồng thời min

max. Kiểu T gồm tất cả các giá trị từ min đến max.

- Các phép toán trong hệ kiểu Pascal

- Như đã nói với mỗi kiểu dữ liệu ta chỉ có thể thực hiện một số phép toán nhất

định trên các dữ liệu của kiểu. Ta không thể áp dụng một phép toán trên các dữ

liệu thuộc kiểu này cho các dữ liệu có kiểu khác. Ta có thể phân tập hợp các

phép toán trên các kiểu dữ liệu của Pascal thành hai lớp sau :

A. Các phép toán truy cập đến các thành phần của một đối tượng dữ liệu, chẳng

hạn truy cập đến các thành phần của một mảng, đến các trường của một bản

ghi.

+ Giả sử A là một mảng với tập chỉ số I, khi đó A[i] cho phép ta truy cập đến

thành phần thứ i của mảng. Còn nếu X là một bản ghi thì việc truy cập đến

trường F của nó được thực hiện bởi phép toán X.F.

B. Các phép toán kết hợp dữ liệu.

15

+ Pascal có một tập hợp phong phú các phép toán kết hợp một hoặc nhiều dữ

liệu đã cho thành một dữ liệu mới. Sau đây là một số nhóm các phép toán

chính.

1. Các phép toán số học. Đó là các phép toán + , -, * , / trên các số thực ; các

phép toán +, - *, /, div, mod trên các số nguyên.

2. Các phép toán so sánh. Trên các đối tượng thuộc các kiểu có thứ tự (đó là các

kiểu cơ sở và kiểu tập), ta có thể thực hiện các phép toán so sánh =, < >, <, <=,

>, >=. Cần lưu ý rằng, kết quả của các phép toán này là một giá trị kiểu boolaen

(tức là true hoặc false).

3. Các phép toán logic. Đó là các phép toán and, or, not được thực hiện trên hai

giá trị false và truc của kiểu boolean.

4. Các phép toán tập hợp. Các phép toán hợp, giao, hiệu của các tập hợp trong

pascal được biểu diễn bởi +, *, - tương ứng. Việc kiểm tra một đối tượng x có là

phần tử của tập A hay không được thực hiện bởi phép toán x in A. Kết quả của

phép toán này là một giá boolean.

2.4. Mô hình dữ liệu và kiểu dữ liệu trừu tượng

- Để giải quyết một vấn đề trên MTĐT thông thường chúng ta cần phải qua một

số giai đoạn chính sau đây :

1. Đặt bài toán

2. Xây dựng mô hình

3. Thiết kế thuật toán và phân tích thuật toán

4. Viết chương trình

5. Thử nghiệm.

- Chúng ta sẽ không đi sâu phân tích từng giai đoạn. Chúng ta chỉ muốn làm sáng

tỏ vai trò của mô hình dữ liệu trong việc thiết kế chương trình. Xét ví dụ sau.

- Ví dụ. Một người giao hàng, hàng ngày anh ta phải chuyển hàng từ một thành

phố đến một số thành phố khác rồi lại quay về thành phố xuất phát. Vấn đề của

anh ta là làm thế nào có được một hành trình chỉ qua mỗi thành phố một lần với

đường đi ngắn nhất có thể được.

16

- Chúng ta thử giúp người giao hàng mô tả chính xác bài toán. Trước hết, ta cần

trả lời câu hỏi, những thông tin đã biết trong bài toán người giao hàng là gì ? Đó

là tên của các thành phố anh ta phải ghé qua và độ dài các con đường có thể có

giữa hai thành phố. Chúng ta cần tìm cái gì ? Một hành trình mà người giao

hàng mong muốn là một danh sách các thành phố A1,A2...An+1 (giả sử có n

thành phố), trong đó các A1 (i=1,2,...,n+1) đều khác nhau, trừ An+1 = A1.

- Với một vấn đề đặt ra từ thực tiễn, ta có thể mô tả chính xác vấn đề đó hoặc các

bộ phận của nó (vấn đề con) bởi một mô hình toán học nào đó. Chẳng hạn, mô

hình toán học thích hợp nhất để mô tả bài toán người giao hàng là đồ thị. Các

đỉnh của đồ thị là các thành phố, các cạnh của đồ thị là các đường nối hai thành

phố. Trọng số của các cạnh là độ dài các đường nối hai thành phố. Trong thuật

ngữ của lý thuyết đồ thị, danh sách các thành phố biểu diễn hành trình của

người giao hàng, là một chu trình qua tất cả các đỉnh của đồ thị. Như vậy, bài

toán người giao hàng được qui về bài toán trong lý thuyết đồ thị. Tìm một chu

trình xuất phát từ một đỉnh qua tất cả các đỉnh còn lại với độ dài ngắn nhất.

- Bài toán người giao hàng là một trong các bài toán đã trở thành kinh điển. Nó

dễ mô hình hoá, song cũng rất khó giải. Chúng ta sẽ quay lại bài toán này.

- Cần lưu ý rằng, để tìm ra cấu trúc toán học thích hợp với một bài toán đã cho,

chúng ta phải phân tích kỹ bài toán để tìm ra câu trả lời cho các câu hỏi sau.

+ Các thông tin quan trọng của bài toán có thể biểu diễn bởi các đối tượng toán

học nào ?

+ Có các mối quan hệ nào giữa các đối tượng ?

+ Các kết quả phải tìm của bài toán có thể biểu diễn bởi các khái niệm toán

học nào.

- Sau khi đã có mô hình toán học mô tả bài toán, một câu hỏi đặt ra là, ta phải

làm việc với mô hình như thế nào để tìm ra lời giải của bài toán ? Chúng ta sẽ

thiết kế thuật toán thông qua các hành động, các phép toán thực hiện trên các

đối tượng của mô hình.

- Một mô hình toán học cùng với các phép toán có thể thực hiện trên các đối

tượng của mô hình được gọi là mô hình dữ liệu. Chẳng hạn, trong mô hình dữ

liệu đồ thị, trong số rất nhiều các phép toán, ta có thể kể ra một số phép toán sau

17

: tìm các đỉnh kề của mỗi đỉnh, xác định đường đi ngắn nhất nối hai đỉnh bất kỳ,

tìm các thành phần liên thông, tìm các đỉnh treo,.. Về mặt toán học, danh sách

là một dãy hữu hạn n phần tử (a₁, a₂, ..., a_n). Trong mô hình dữ liệu danh sách,

chúng ta cũng có thể thực hiện một tập hợp rất đa dạng các phép toán, chẳng

hạn như, xác định độ dài của danh sách, xen một phần tử mới vào danh sách,

loại một phần từ nào đó khỏi danh sách, sắp xếp lại danh sách theo một trật tự

nào đó, gộp hai danh sách thành một danh sách.

- Trở lại bài toán người giao hàng. Có nhiều thuật toán giải bài toán này. Chẳng

hạn, ta có thể giải bằng phương pháp vét cạn : giả sử có n thành phố, khi đó mỗi

hành trình là một hoán vị của n-1 thành phố (trừ thành phố xuất phát), thành lập

(n-1)! hoán vị, tính độ dài của hành trình ứng với mỗi hoán vị và so sánh, ta sẽ

tìm được hành trình ngắn nhất. Ta cũng có thể giải bài toán bằng phương pháp

qui hoạch động (Phương pháp này sẽ được trình bày ở tập 2 của sách này). Sau

đây ta đưa ra một thuật toán đơn giản. Thuật toán này tìm ra rất nhanh nghiệm

"gần đúng", trong trường hợp có đường đi nối hai thành phố bất kỳ. Giả sử G là

một đồ thị (Graph), V là tập hợp các đỉnh (Node), E là tập hợp các cạnh của nó.

Giả sử c(u,v) là độ dài (nguyên dương) của cạnh (u,v). Hành trình (Tour) của

người giao hàng có thể xem như một tập hợp nào đó các cạnh. Cost là độ dài

của hành trình. Thuật toán được biểu diễn bởi thủ tục Salesperson.

procedure Salespersen (G : Graph ; var Tour : set of E ;

var cost : integer) ;

var v, w : Node

U : set of V ;

begin

Tour : = [ ] ;

Cost : = 0 ;

v : = v_o; {v_o- đỉnh xuất phát}

U : = V - [v_o] ;

while

U < > [ ] do

18

begin

Chọn (v, w) là cạnh ngắn nhất với w thuộc U ;

Tour : = Tour + [(v, w)] ;

Cost : = Cost + c (v,w) ;

v : = w ;

U : = U - [w] ;

end ;

Tour : = Tour + [(v,v_o)] ;

Cost : = Cost + c(v,v_o) ;

end;

- Thuật toán Salesperson được xây dựng trên cơ sở mô hình dữ liệu đồ thị và mô

hình dữ liệu tập hợp. Nó chứa các thao tác trên đồ thị, các phép toán tập hợp.

Tư tưởng của thuật toán như sau. Xuất phát từ Tour là tập rỗng. Giả sử ta xây

dựng được đường đi từ đỉnh xuất phát v₀tới đỉnh v. Bước tiếp theo, ta sẽ thêm

vào Tour cạnh (v,w), đó là cạnh ngắn nhất từ v tới các đỉnh w không nằm trên

đường đi từ v₀tới v. Để có được chương trình, chúng ta phải biểu diễn đồ thị,

tập hợp bởi các cấu trúc dữ liệu. Sau đó viết các thủ tục (hoặc hàm) thực hiện

các thao tác, các phép toán trên đồ thị, tập hợp có trong thuật toán.

- Tóm lại, quá trình giải một bài toán có thể quy về hai giai đoạn kế tiếp như sau:

+ Xây dựng các mô hình dữ liệu mô tả bài toán. Thiết kế thuật toán bằng cách

sử dụng các thao tác, các phép toán trên các mô hình dữ liệu.

+ Biểu diễn các mô hình dữ liệu bởi các cấu trúc dữ liệu. Với các cấu trúc dữ

liệu đã lựa chọn, các phép toán trên các mô hình dữ liệu được thể hiện bởi

các thủ tục (hàm) trong ngôn ngữ lập trình nào đó.

- Toán học đã cung cấp cho Tin học rất nhiều cấu trúc toán học có thể dùng làm

mô hình dữ liệu. Chẳng hạn, các khái niệm toán học như dãy, tập hợp, ánh xạ,

cây, đồ thị, quan hệ, nửa nhóm, nhóm, otomat,...Trong các chương sau chúng ta

sẽ lần lượt nghiên cứu một số mô hình dữ liệu quan trọng nhất, được sử dụng

thường xuyên trong các thuật toán. Đó là các mô hình dữ liệu danh sách, cây,

19

tập hợp. Với mỗi mô hình dữ liệu chúng ta nghiên cứu các cách cài đặt nó bởi

các cấu trúc dữ liệu khác nhau. Trong mỗi cách cài đặt, một số phép toán trên

mô hình có thể được thực hiện dễ dàng, nhưng các phép toán khác có thể lại

không thuận tiện. Việc lựa chọn cấu trúc dữ liệu nào để biểu diễn mô hình phụ

thuộc vào từng áp dụng.

- Như đã nói, với mỗi mô hình dữ liệu, chúng ta có thể thực hiện một tập hợp các

phép toán rất đa dạng, phong phú. Song trong nhiều áp dụng, chúng ta chỉ sử

dụng mô hình với một số xác định các phép toán nào đó. Khi đó chúng ta sẽ có

một kiểu dữ liệu trừu tượng.

- Như vậy, một kiểu dữ liệu trừu tượng (abstract data type) là một mô hình dữ

liệu được xét cùng với một số xác định các phép toán nào đó. Chẳng hạn, các

tập hợp chỉ xét với các phép toán : thêm một phần tử vào một tập đã cho, loại

một phần tử khỏi một tập hợp đã cho, tìm xem một phần tử đã cho có nằm trong

một tập hợp hay không, lập thành kiểu dữ liệu trừu tượng (KDLTT) từ điển

(dictionnaire).

- Còn KDLTT hàng (hàng đợi) là mô hình dữ liệu danh sách cùng với hai phép

toán chính là : thêm một phần tử mới vào một đầu danh sách, và loại một phần

tử ở một đầu khác của danh sách. Chúng ta sẽ nghiên cứu kỹ một số kiểu dữ

liệu trừu tượng quan trọng nhất : hàng, ngăn xếp (stack), từ điển, hàng ưu tiên.

Với mỗi KDLTT, các cấu trúc dữ liệu để biểu diễn nó sẽ được nghiên cứu.

Chúng ta cũng sẽ đánh giá hiệu quả của các phép toán trong từng cách cài đặt.

3. Thiết kế và giải thuật

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

- Để đá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:

- Phản ánh đúng thực tế : Đây là tiêu chuẩn quan trọng nhất, quyết định tính đúng

đắn của toàn bộ bài toán. Cần xem xét kỹ lưỡng cũng như dự trù các trạng thái

biến đổi của dữ liệu trong chu trình sống để có thể chọn cấu trúc dữ liệu lưu trữ

thể hiện chính xác đối tượng thực tế.

- Ví dụ : Một số tình huống chọn cấu trúc lưu trữ sai :

+ Chọn một biến số nguyên int để lưu trữ tiền thưởng bán hàng (được tính

theo công thức tiền thưởng bán hàng = trị giá hàng * 5%), do vậy sẽ làm tròn

20

Giáo trình Cấu trúc dữ liệu và giải thuật - Nghề: Lập trình máy tính