Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu cơ bản

ữ ệ

ấ

ả

C u trúc d li u và gi

ậ i thu t

CÁC CẤU TRÚC DỮ LiỆU CƠ BẢN

Giảng viên: Đậu Ngọc Hà Dương

Nội dung trình bày

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Danh sách liên kết

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Nội dung

 Giới thiệu

 Các loại danh sách liên kết

 Các thao tác trên danh sách liên kết

 So sánh danh sách liên kết và mảng

 Ứng dụng ấ C u trúc d li u và gi

ữ ệ ả ậ i thu t – HCMUS 2012

Giới thiệu

 Mảng: cấu trúc dữ liệu quen thuộc

ứ ự

ậ

 T p có th t

ố ượ

ầ ử ố ị

 S l

ng ph n t

c đ nh (tĩnh)

ấ

ớ

ụ  C p phát vùng nh liên t c

ầ ử

ỉ ố

ấ  Truy xu t ph n t

thông qua ch s

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Giới thiệu

 Đánh giá thao tác trên mảng:

ầ ử ấ  Truy xu t ph n t ?

ậ

 C p nh t?

ầ ử  Chèn ph n t ?

ầ ử  Xoá ph n t ?

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Giới thiệu

 Thực tế:

ị

ượ

ố ượ

ầ ử

 Không xác đ nh đ

c chính xác s l

ng ph n t

 Danh sách bệnh nhân: tăng/giảm.

 Danh sách sinh viên: tăng/giảm.

ử ụ

ổ

ớ

 Vùng nh thay đ i trong quá trình s d ng

=> Không đủ vùng nhớ cấp phát liên tục.

ữ ệ ậ ả

=> Cấu trúc dữ liệu động đáp ứng nhu cầu ấ C u trúc d li u và gi i thu t – HCMUS 2012

Các loại danh sách liên kết

 Danh sách liên kết đơn

 singly linked list

 unidirectional linked list

 Danh sách liên kết kép

 doubly linked list

 bidirectional linked list

 Danh sách liên kết vòng

 circularly linked list ậ



ấ ả i thu t – HCMUS 2012

ữ ệ C u trúc d li u và gi ring list

Danh sách liên kết đơn

 Mỗi phần tử có MỘT liên kết đến phần tử phía

sau nó.

9 9

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Danh sách liên kết đơn

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Danh sách liên kết kép

 Mỗi phần tử có HAI liên kết đến phần tử đứng

sau và trước nó.

9 9

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Danh sách liên kết vòng

 Có mối liên kết giữa phần tử cuối và phần tử

đầu

9 9

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Phần tử trên danh sách liên kết

 Phần tử (Node, Element)

ầ ử

ữ ệ

 Ph n t

ế = D li u + Liên k t

 Ví d :ụ

 Phần tử có 1 liên kết

9 9

 Phần tử có 2 liên kết

 Phần tử rỗng

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Ví dụ

 Ví dụ:

ầ ử

ữ ệ

ầ

ồ

 Ph n t

có d li u g m 1 thành ph n

number

ầ ử

ầ

 Ph n t

ồ có d li u g m 3 thành ph n name number

ữ ệ id

name

ầ ử

id ữ ệ

ấ

 Ph n t

number ồ có d li u g m 1 c u trúc

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Cài đặt

 Sinh viên tự viết phần cài đặt cho các ví dụ trên

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Tổ chức

 Mỗi danh sách liên kết bao gồm:

ầ ử ầ

ặ

ố

ỏ ế  Con tr đ n ph n t

đ u (ho c/và cu i) danh sách.

ầ ử

 (Các) ph n t

trên danh sách

 Dữ liệu

 Các mối liên kết

9 9

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Tổ chức

9 9

pHead

9 9

pHead

pTail

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Các thao tác trên danh sách liên kết

 Thêm phần tử

 Duyệt danh sách

 Xoá phần tử

 Truy xuất phần tử

 Xoá danh sách ấ ữ ệ ậ C u trúc d li u và gi

ả i thu t – HCMUS 2012

Thêm phần tử

 Vào đầu danh sách

 Sau một phần tử

 Vào cuối danh sách

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Thêm phần tử

 Vào đầu danh sách:

ế

ỗ

 N u danh sách r ng

 Phần tử vừa thêm là phần tử đầu danh sách

ượ ạ  Ng c l 1

9 9

pHead

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Thêm phần tử

 Sau một phần tử (pNode):

ế

ỗ

 N u danh sách r ng?

ế

ỗ

 N u danh sách khác r ng?

 Tạo node mới có dữ liệu là Data.

 Cập nhật lại liên kết của pNode và node vừa tạo.

X

9 9

pNode

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Duyệt danh sách

 Đảm bảo việc truy xuất đến tất cả các phần tử

trên danh sách

 Thuật toán:

ắ ầ ừ ầ ử ầ

 B t đ u t

ph n t

đ u tiên

ư ế

 Trong khi ch a h t danh sách

 Xử lý phần tử hiện hành

 Di chuyển đến phần tử kế tiếp

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Xoá phần tử

 Đầu danh sách

 Cuối danh sách

 Sau một phần tử

 Theo khóa k

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Xoá phần tử

 Đầu danh sách

ế

ỗ

 N u danh sách r ng:

ế

ỗ

 N u danh sách khác r ng:

 Cập nhật lại pHead

 Xóa con trỏ pHead cũ

9 9

pHead

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Xoá phần tử

 Cuối danh sách:

 Danh sách r ng?ỗ

ỗ

 Danh sách khác r ng:

 tìm con trỏ cuối danh sách pTail

 Xóa pTail cũ

 Cập nhật lại pTail 9 9

pTail

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Xoá phần tử

 Sau một phần tử (pNode)

ườ

ng h p chung:

ợ pNode

9 9

ầ c n xóa

ườ

pNode

ặ

ệ

ng h p đ c bi

pNode ợ

pHead

9 9 pHead

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Xoá danh sách

 Danh sách liên kết bao gồm các phần tử được

cấp phát động.

 Phải xoá các phần tử trên danh sách sau khi đã

sử dụng xong danh sách.

 Thuật toán:

ầ ử

ệ

 Duy t qua các ph n t

trên danh sách

ầ ử ừ  Xoá t ng ph n t ữ ệ ậ i thu t – HCMUS 2012

ấ ả C u trúc d li u và gi

Danh sách liên kết là gì?

 Một dãy tuần tự các phần tử (node)

 Giữa hai phần tử có liên kết với nhau.

 Các phần tử không cần phải lưu trữ liên tiếp

nhau trong bộ nhớ

 Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung

lượng bộ nhớ)

 Thao tác Chèn/Xóa không cần phải dịch chuyển

phần tử

 Có thể truy xuất đến các phần tử khác thông

qua các liên kết ậ

ữ ệ ấ ả C u trúc d li u và gi i thu t – HCMUS 2012

So sánh danh sách liên kết và mảng

 Danh sách liên kết

 Mảng

 Số phần tử không cần xác định

 Cần xác định trước số phần tử.

trước.

 Cấp phát vùng nhớ riêng lẻ cho

 Cần cấp phát vùng nhớ liên tục lãng

từng phần tử.

đủ lớn để lưu trữ mảng (cid:0) phí nếu không dùng hết.

 Truy xuất ngẫu nhiên, đơn giản,

nhanh chóng.

 Truy xuất tuần tự, danh sách liên kết đơn chỉ có thể duyệt 1 chiều.

 Không cần

 Cần nhiều bộ nhớ hơn để lưu

 Thêm/xóa phần tử cuối: O(1)

trữ các liên kết ấ C u trúc d li u và gi

 Thêm/xóa phần tử giữa: O(n)

 Thêm/xóa phần tử cuối: O(n)

 Thêm/xóa phần tử giữa: O(1)

ữ ệ ả ậ i thu t – HCMUS 2012

Ứng dụng

 Là cấu trúc dữ liệu chính cho ngôn ngữ lập trình LISP (LIst Processing Language) – ngôn ngữ lập trình hàm.

 Giúp nâng cao hiệu quả của một số thuật toán

sắp xếp: Quick Sort, Radix Sort

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Bài tập 1

 Cho một DSLK đơn, mỗi node trong DSLK lưu

thông tin là 1 số nguyên và con trỏ đến node kế. Tạo 2 DSLK đơn mới (không phá huỷ DSLK đã cho).

ố ẻ ủ

ứ

 M t danh sách ch a các s l

c a danh sách đã

ộ cho.

ố ẵ ủ

ứ

 M t danh sách ch a các s ch n c a danh sách đã

ộ cho.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Bài tập 1

ườ

ự

ừ

ng ch y

 In ra các đ

ạ t

nhiên t

DSLK đã cho:

ể

ễ

ầ

ố

VÍ DỤ: DSLK ban đ u bi u di n các s : 1 5 6 4 8 3 7

In ra các dãy số: 1 5 6

4 8

3 7

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Bài tập 2

 Cho danh sách liên kết đơn L, lập giải thuật

thực hiện các phép sau đây:

ố ượ

 Tính s l

ủ ng các nút c a danh sách.

ớ

ứ

 Tìm t

i nút th k trong danh sách, n u có nút th k

ế ị

ỉ ủ

ượ ạ ả ề

thì cho bi

t đ a ch c a nút đó, ng

i tr v null.

ế c l

ộ

ổ

 B sung m t nút vào sau nút k.

ạ ỏ

ứ

ướ

 Lo i b nút đ ng tr

c nút k.

ượ

ả  Đ o ng

c danh sách đã cho.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Bài tập 3

 Hàm MoveToFront có tác dụng di chuyển 1 node trong xâu lên đầu xâu, như hình sau:

9 9

pHead

pNode

 Chọn kiểu khai báo hàm phù hợp và viết code void MoveToFront(NODE (cid:0) (cid:0) pHead, NODE (cid:0) (cid:0) pTail, NODE (cid:0) (cid:0) pNode ) Lưu ý: các kí hiệu (cid:0) có thể là *, & hoặc khoảng ấ C u trúc d li u và gi trắng

ữ ệ ậ ả i thu t – HCMUS 2012

Ngăn xếp - stack

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Nội dung

 Giới thiệu

 Các thao tác cơ bản

 Ký pháp Ba Lan

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Giới thiệu

 Một số hình ảnh thông dụng:

ở ở

ộ

ồ  M t ch ng sách v

trên bàn

ộ

ồ

 M t ch ng đĩa

ơ ấ ủ

ứ ạ

ườ

ộ ộ  C c u c a m t h p ch a đ n súng tr

ng.

ậ

ữ ệ ậ i thu t – HCMUS 2012 ụ ấ C u trúc d li u và gi ừ Nh n xét gì t ả các ví d trên?

Giới thiệu

 Định nghĩa:

Đỉnh

ế

ố

ứ ơ

ệ

ượ t sau ra tr

ậ  Ngăn x p là v t ch a các đ i ế vào ng làm vi c theo c ch “ cướ ” (Last In First Out)

c thêm vào đ i ố c

ỏ

ấ

ố ượ ể ượ  Đ i t ng có th đ ư ấ ỉ b t kì lúc nào, nh ng ch có ượ ớ ượ ng vào sau cùng m i đ t ế . phép l y ra kh i ngăn x p

Đáy

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Các thao tác trên ngăn xếp

 Các thao tác cơ bản:

ầ ử

ế

 Push: Thêm 1 ph n t

vào ngăn x p

ầ ử

ế

ỏ

ấ  Pop: L y 1 ph n t

ra kh i ngăn x p

 Các thao tác khác:

ế ữ  L u tr ngăn x p

ế ỗ

ể

 Ki m tra ngăn x p r ng

ấ

ầ ử ầ

ủ

ế

đ u ngăn x p

 L y thông tin c a ph n t ả

ữ ệ ậ ấ i thu t – HCMUS 2012 C u trúc d li u và gi

Lưu trữ ngăn xếp

 Lưu trữ bằng mảng

ề

ả

ớ

 Khai báo m ng 1 chi u v i kích th

ướ ố c t

i đa N.



→

ị

ủ

ế

ẽ

đ nh c a ngăn x p

t s thay

ầ ử ỉ ạ ộ

ổ

ỉ ủ t là đ a ch c a ph n t ế đ i khi ngăn x p ho t đ ng.

 Ngăn xếp rỗng thì giá trị của t là 0

ế

ằ

ạ

ả

 T o ngăn x p S và qu n lý ngăn x p b ng bi n t:

Data S[N];

ấ ả ậ

int t; ữ ệ

C u trúc d li u và gi i thu t – HCMUS 2012

Lưu trữ ngăn xếp

 Lưu trữ bằng DSLK:

ỉ ủ ỉ

ỏ

ế ư ị  Dùng con tr pHead l u đ a ch c a đ nh ngăn x p

ế ỗ

 Ngăn x p r ng khi pHead = NULL

9 9

pHead

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Kiểm tra ngăn xếp rỗng

 Input:

 Output:

ế ỗ

ế

 TRUE n u ngăn x p r ng

ế

ỗ

 FALSE n u ngăn x p không r ng

 Ngăn xếp rỗng:

ầ ử ả

m ng là 0

ng ph n t ậ i thu t – HCMUS 2012

ố ượ ả  M ng: s l ả ữ ệ C u trúc d li u và gi  DSLK: pHead = NULL

ấ

Kiểm tra ngăn xếp đầy

 Input:

 Output:

ế

ầ  TRUE n u ngăn x p đ y

ỗ ố

ế

 FALSE n u ngăn x p còn ch tr ng

 Ngăn xếp đầy:

ầ ử ả

m ng

ả ữ ệ C u trúc d li u và gi

ấ

ư ế  M ng: đã l u h t các ph n t ả i thu t – HCMUS 2012 ượ  DSLK: không c p phát đ

ớ ớ c vùng nh m i cho ngăn

x pế

ậ ấ

Thêm phần tử vào ngăn xếp (push)

 Input: phần tử cần thêm

 Output:

 Giải thuật:

ể

ầ

ế  Ki m tra ngăn x p có đ y không?

ế

 N u không

 Bổ sung phần tử mới vào

 Cập nhật địa chỉ của con trỏ đến đỉnh ngăn xếp

ấ ữ ệ ậ ả C u trúc d li u và gi i thu t – HCMUS 2012

Thêm phần tử vào ngăn xếp (push)

 Ví dụ:

Đỉnh = 4

Đỉnh = 3

Ngăn xếp ban đầu

Ngăn xếp sau khi thêm push(5)

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Lấy phần tử ra khỏi ngăn xếp (pop)

 Input:

 Output: giá trị của đối tượng đầu ngăn xếp

 Thuật toán:

ế ỗ

ể

 Ki m tra ngăn x p r ng hay không?

ế

 N u không:

 Cập nhật địa chỉ của con trỏ đến đỉnh ngăn xếp

Xóa phần tử ở đỉnh khỏi ngăn xếp

(cid:0)

 Trả về giá trị của phần tử ở đỉnh

ấ ữ ệ ậ ả C u trúc d li u và gi i thu t – HCMUS 2012

Lấy phần tử ra khỏi ngăn xếp (pop)

 Ví dụ:

Đỉnh = 3

Đỉnh = 2

Ngăn xếp sau khi pop()

2 Ngăn xếp ban đầu

return 4;

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Lấy thông tin đỉnh ngăn xếp

 Chỉ lấy giá trị của phần tử đầu mà không hủy nó

khỏi ngăn xếp.

 Input:

 Output: giá trị tại đỉnh ngăn xếp

 Giải thuật:

ế

ỗ

ả ề

ị ủ

ầ ử ở ỉ

ế

 Tr v giá tr c a ph n t

đ nh ngăn x p

ấ ậ ả ữ ệ C u trúc d li u và gi ể i thu t – HCMUS 2012  Ki m tra xem ngăn x p có r ng không?

Lấy thông tin đỉnh ngăn xếp

 Ví dụ

Đỉnh = 3

Ngăn xếp sau khi gettop()

2 Ngăn xếp ban đầu

return 4;

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Bài tập

 Cho biết nội dung của stack sau khi thực hiện

các thao tác trong dãy (từ trái sang phải):

EASYQUEST***I*ON

Mỗi chữ cái hoặc dấu * tương ứng một thao tác

trên stack trong đó:

ộ

ượ

ữ

ng tr ng cho thao tác thêm ch cái đó

ữ  M t ch cái t vào stack



ấ

ộ

ng tr ng cho thao tác l y n i dung m t

ấ D u * t ầ ử ph n t

ượ ồ trong stack ra r i in lên màn hình.

ữ ệ ậ ả i thu t – HCMUS 2012

Cho biết kết quả xuất ra màn hình sau khi hoàn ấ C u trúc d li u và gi tất chuỗi trên?

Bài tập

 Cho biết nội dung của stack và giá trị của các

biến sau khi thực hiện liên tiếp các thao tác sau:

 (Ban đầu các biến được khởi tạo: A= 5, B = 3,

C= 7)

a. Tạo stack

b. push A

c. push C*C

d. pop rồi lưu trữ vào biến B

ậ

e. push B+A ấ ữ ệ ả C u trúc d li u và gi

i thu t – HCMUS 2012

f. pop rồi lưu trữ vào biến A

g. pop rồi lưu trữ vào biến B

Ký pháp Ba Lan

 Biểu thức dạng trung tố: dấu của các phép toán

hai ngôi luôn được đặt giữa 2 toán hạng

ụ

 Ví d : A + B * C

A + B * C D

(A+B) * C

(A + B )* (C – D)

ứ ự ư

ủ

ị Qui đ nh th t

u tiên c a các phép toán

(cid:222)

ặ ể

ấ

ệ

ứ ự ự

ệ

Dùng d u ngo c đ phân bi

t th t

th c hi n.

(cid:222)

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Ký pháp Ba Lan

 Biểu thức dạng tiền tố:

Trung tố

Tiền tố

A + B

+ A B

(A+B)*C

*+ A B C

(A + B )* (C – D)

* + A B – C D

ế

Trung tố

 Biểu thức dạng hậu tố: Hậu tố

Không c n ầ ả t ph i thi dùng d u ấ ngo cặ

A + B

A B +

(A+B)*C

A B + C *

(A + B )* (C – D)

A B + C D - *

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Chuyển trung tố sang hậu tố

 Mã giả: P là biểu thức trung tố ban đầu, Q là

biểu thức kết quả dạng hậu tố

0.1 push(‘(‘);

0.2 Thêm ‘)’ vào P

while (chưa hết biểu thức P)

{

1. đọc 1 kí tự x trong P (từ trái qua phải)

2. if (x là toán hạng)

Thêm x vào Q

ữ ệ ậ ấ C u trúc d li u và gi i thu t – HCMUS 2012 ả 3. if (x là dấu ngoặc mở)

push(x);

Chuyển trung tố sang hậu tố

Mã giả:

4. if (x là toán tử)

4.1 while( thứ tự ưu tiên tại

đỉnh >= x)

4.1.1 w = pop();

4.1.2 Thêm w vào Q

4.2 push(x);

ữ ệ ậ ấ ả

5. if (x là dấu ngoặc đóng) i thu t – HCMUS 2012

C u trúc d li u và gi

5.1 while( chưa gặp ngoặc mở)

4.1.1 w = pop();

4.1.2 Thêm w vào Q

5.2 pop();//đẩy ngoặc mở ra khỏi

ngăn xếp

}

Chuyển trung tố sang hậu tố

 Ví dụ 1: P = ( A + B ) * ( C - ( D + A ) )

ự ọ

đ c

( A + B )

( C -

( D +

)

Kí t cượ đ

+ +

( ( ( (

Tr ng ạ thái c a ủ ngăn x pế

- - - - - -

( ( ( ( ( ( + + ( (

* * * * * * ( ( ( * * ( * * ( ( ( ( ( ( ( ( ( ( ( ( ( ( (

Q = A B + C D A + - * ấ

ữ ệ ậ ả i thu t – HCMUS 2012 C u trúc d li u và gi

Chuyển trung tố sang hậu tố

 Ví dụ 2: đổi biểu thức trung tố

P = A + (B * C – (D / E ^ F) * G) * H

sang biểu thức dạng hậu tố

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Ứng dụng khác của ngăn xếp

 Dùng biến đổi cơ số

 Lượng giá biểu thức hậu tố

 Trong trình biên dịch, ngăn xếp được sử dụng

để lưu môi trường các thủ tục.

 Dùng trong một số bài toán của lý thuyết đồ thị.

 Khử đệ qui đuôi.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Hàng đợi - Queue

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Nội dung

 Giới thiệu

 Các thao tác cơ bản

 Ứng dụng

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Giới thiệu

 Giới thiệu:

ệ

ắ vào

ng làm vi c theo qui t c

ướ

ố ượ ứ ậ  Là v t ch các đ i t ướ (FIFO). c ra tr

 Các đ i t

ố ượ

ầ

ợ ấ c thêm vào hàng đ i b t kì thêm vào đ u tiên

Đầu

Cuối

ỏ

ng có th đ ỉ ng ợ ớ ượ l y ra kh i hàng đ i

ố ượ ể ượ ư lúc nào nh ng ch có đ i t ấ c m i đ

ở ố

ễ

ệ ấ

ễ

cu i, vi c l y ra di n ra

ở

ậ ấ i thu t – HCMUS 2012 ả  Vi c thêm vào di n ra

ữ ệ C u trúc d li u và gi ệ đ uầ

Các thao tác trên hàng đợi

 Thao tác cơ bản:

ố ượ

 Enqueue: Thêm 1 đ i t

ợ ố ng vào cu i hàng đ i

ố ượ

ấ

ở ầ

 Dequeue: L y đ i t

ợ ỏ đ u ra kh i hàng đ i

 Thao tác khác:

ợ ữ  L u tr hàng đ i

ợ ỗ

ể

 Ki m tra hàng đ i r ng

ể

ở ầ

ợ ầ  Ki m tra hàng đ i đ y ả  L y thông tin c a đ i t

ợ đ u hàng đ i

ấ ữ ệ C u trúc d li u và gi ấ ậ i thu t – HCMUS 2012 ủ ố ượ

Lưu trữ hàng đợi

 Lưu trữ bằng mảng:

ề

ả

ớ

 Khai báo m ng 1 chi u v i kích th

ướ ố c t

i đa N.

ỉ ủ

ầ ử ằ ở ầ n m

ị đ u, r là đ a ch c a

ị ph n t

ỉ ủ  f là đ a ch c a ph n t ầ ử ằ ở ố cu i n m 2 1

Hàng đợi

2 r = 6

f = 2

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Lưu trữ hàng đợi

 Lưu trữ bằng mảng:

ầ ử ủ

ể

ắ

 Các ph n t

ạ

ợ

ợ ẽ c a hàng đ i s di chuy n kh p các ô nh ớ  coi không gian dành cho hàng đ i theo d ng xoay vòng.

 Hàng đ i khi xoay vòng: 4

ợ 1

1 r = 2

2 f = 6

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Lưu trữ hàng đợi

 Lưu trữ hàng đợi bằng danh sách liên kết đơn

ầ ử ầ

ẽ

ợ

 Ph n t

đ u DSLK s là ph n t

đ u hàng đ i.

ầ ử ố

ẽ

cu i DSLK s là ph n t

ợ cu i hàng đ i

ầ ử ố  Ph n t 12

9 9

pHead

pTail

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Kiểm tra hàng đợi rỗng

 Input:

 Output:

ợ ỗ

ế

 TRUE n u hàng đ i r ng

ế

ỗ

ợ

 FALSE n u hàng đ i không r ng

 Hàng đợi rỗng:

ả ữ ệ C u trúc d li u và gi

ứ ữ ệ ớ ầ  M ng: ô nh đ u tiên không ch a d li u ả ậ i thu t – HCMUS 2012  DSLK: pHead = NULL

ấ

Kiểm tra hàng đợi đầy

 Input:

 Output:

ế

ợ ầ  TRUE n u hàng đ i đ y

ế

ợ

ầ  FALSE n u hàng đ i không đ y

 Hàng đợi đầy:

ứ ữ ệ  M ng: ô nh cu i hàng đ i đã ch a d li u

ả ữ ệ C u trúc d li u và gi

ầ ử

ợ ớ ố ậ ả i thu t – HCMUS 2012 ượ ấ  DSLK: không c p phát đ

ớ c vùng nh cho ph n t

m iớ

ấ

Thêm phần tử vào cuối hàng đợi

 Input: giá trị cần thêm

 Output:

 Giải thuật thêm phần tử (EnQueue)

ể

ầ

ợ

 Ki m tra hàng đ i đã đ y ch a?

ườ

ợ ư

ữ ằ

ề

ể

ng h p l u tr b ng m ng

ả : ki m tra đi u

 Trong tr ệ

ki n xoay vòng.

ầ ử

ố

 Thêm ph n t

ợ vào cu i hàng đ i

ậ ữ ệ C u trúc d li u và gi

ầ ử ố

ợ

ỉ

ậ ị  C p nh t đ a ch ph n t ả

cu i hàng đ i

ậ ấ i thu t – HCMUS 2012

Thêm phần tử vào cuối hàng đợi

 Ví dụ:

Hàng đợi ban đầu

2 r = 6

1 f = 2

EnQueue(9)

1 f = 2

9 r = 7

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Lấy phần tử đầu ra khỏi hàng đợi

 Input:

 Output: giá trị của phần tử đầu hàng đợi

 Giải thuật lấy phần tử ở đầu (DeQueue)

ể

ỗ

ợ  Ki m tra hàng đ i có r ng không?

ầ ử ầ

 Xóa ph n t

ợ ỏ đ u ra kh i hàng đ i

ầ ử ầ

ậ

ỉ

ậ ị  C p nh t đ a ch ph n t

ợ đ u hàng đ i

ữ ằ

ả

ề

ể

ki m tra đi u

ườ  Trong tr ng h p l u tr b ng m ng: ệ ữ ệ ả C u trúc d li u và gi i thu t – HCMUS 2012

ợ ư ki n xoay vòng ậ

ấ

Lấy phần tử đầu ra khỏi hàng đợi

 Ví dụ:

Hàng đợi ban đầu

2 r = 6

1 f = 2

DeQueue() = 1

2 r = 6

3 f = 3

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Lấy thông tin đầu hàng đợi

 Chỉ lấy thông tin của đối tượng đầu hàng đợi

mà không hủy đối tượng khỏi hàng đợi.

 Input: hàng đợi

 Output: giá trị của đối tượng đầu hàng đợi

 Giải thuật:

ợ ỗ

ể

 Ki m tra hàng đ i r ng?

ầ ử ầ

ợ đ u hàng đ i

ấ C u trúc d li u và gi ậ i thu t – HCMUS 2012 ị ủ ữ ệ ả ề ả  Tr v giá tr c a ph n t

Lấy thông tin đầu hàng đợi

 Ví dụ:

Hàng đợi ban đầu

2 r = 6

1 f = 2

GetFront() = 1

2 r = 6

1 f = 2

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Ứng dụng của hàng đợi

 Bộ đệm bàn phím của máy tính

 Xử lý các lệnh trong máy tính: hàng đợi thông điệp trong Windows, hàng đợi tiến trình …

 Thường dùng trong các hệ mô phỏng.

ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2012

Bài tập

Cho hàng đợi ban đầu như sau: (hàng đợi có tối đa 6 phần tử)

f = 1

r = 3

Vẽ tình trạng của hàng đợi, cho biết giá trị f, r tương ứng với mỗi lần thực hiện thao tác sau:

ữ ệ ậ

Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu cơ bản - Đậu Ngọc Hà Dương