Trang chủ » Công Nghệ Thông Tin » Hệ thống thông tin quản lý

38 trang

49 lượt xem

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - Trường ĐH Văn Lang

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 cung cấp cho người học những kiến thức như: Ngăn xếp; hàng đợi; bài tập stack và queue. Mời các bạn cùng tham khảo!

trangxanh0906

KHOA CÔNG NGHỆ THÔNG TIN

Cơ chế: Last In First Out LIFO

Stack

KHOA CÔNG NGHỆ THÔNG TIN

Mảng 1 chiều

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

Cấp phát động!

Kích thước stack khi quá thiếu, lúc quá thừa

Push/Pop khá dễ dàng

Push / Pop hơi phức tạp

KHOA CÔNG NGHỆ THÔNG TIN

• Để khai báo một stack, ta cần một mảng 1 chiều S,

biến nguyên t cho biết chỉ số của đầu stack và hằng

số N cho biết kích thước tối đa của

struct Stack{

Data D [N]; count; int }

KHOA CÔNG NGHỆ THÔNG TIN

• Lệnh count = 0 sẽ tạo ra một stack S rỗng. • Giá trị của count sẽ cho biết số phần tử hiện

hành có trong stack

• Khi cài đặt bằng mảng 1 chiều, stack có kích thước tối đa nên cần xây dựng thêm một thao tác phụ cho stack:

• IsFull(): Kiểm tra xem stack có đầy chưa. • Khi stack đầy, việc gọi đến hàm push() sẽ

phát sinh ra lỗi.(overflow error)

KHOA CÔNG NGHỆ THÔNG TIN

class StackByArray

{

int[] iData; // lưu dữ liệu của stack int icount; // số phần tử stack đang lưu trữ public StackByArray(int size) {

iData = new int[size]; icount = 0;

}

KHOA CÔNG NGHỆ THÔNG TIN

Thêm một phần tử x vào stack S

void Push(Stack S,Data x)

if(S.count < N) // stack chưa đầy

{

S.D[count] = x;

{

S.count++;

}

else puts("Stack đầy");

}

KHOA CÔNG NGHỆ THÔNG TIN

public bool Push( int ivalue)

{

if (icount < iData.Length) // stack chưa đầy

{

iData[icount] = ivalue;// bỏ giá trị vào stack

icount++; // tăng số phần tử trong stack

return true; // thêm phần tử thành công

}

else

{

// stack đầy, overflow error

return false; // thêm phần tử thất bại

}

KHOA CÔNG NGHỆ THÔNG TIN

Trích thông tin và huỷ phần tử ở đỉnh stack S

Data Pop(Stack S)

{

Data

x;

if(S.count > 0) // stack khác rỗng

S.count--;

{

x = S.D[count];

return x;

}

else puts("Stack rỗng")

}

KHOA CÔNG NGHỆ THÔNG TIN

public int Pop()

{

if (icount>0) {

icount--; // giảm số lượng phần tử trong stack return iData[icount + 1]; // trả giá trị đỉnh stack về

} else

{

// stack không có phần tử, underflow error return int.MinValue; // trả min số nguyên về để biết mảng không có phần tử

}

} KHOA CÔNG NGHỆ THÔNG TIN

• Lệnh count = 0 sẽ tạo ra một stack S rỗng. • Giá trị của count sẽ cho biết số phần tử hiện

hành có trong stack

• Khi cài đặt bằng mảng 1 chiều, stack có kích thước tối đa nên cần xây dựng thêm một thao tác phụ cho stack:

• IsFull(): Kiểm tra xem stack có đầy chưa. • Khi stack đầy, việc gọi đến hàm push() sẽ

phát sinh ra lỗi.

KHOA CÔNG NGHỆ THÔNG TIN

Kiểm tra stack rỗng hay không char IsEmpty(Stack S) {

if(S.count == 0) // stack rỗng return 1; else return 0;

} Kiểm tra stack đầy hay không char IsFull(Stack S) {

if(S.count>= N) // stack đầy

return 1;

else

return 0;

}

KHOA CÔNG NGHỆ THÔNG TIN

• Xem thông tin của phần tử ở đỉnh stack S Data Top() {

Data x; if(count > 0) // stack khác rỗng x = S.D[S.count-1]; {

return x;

} else puts("Stack rỗng")

}

KHOA CÔNG NGHỆ THÔNG TIN

 Nhận xét: • Các thao tác trên đều làm việc với chi phí O(1). • Việc cài đặt stack thông qua mảng một chiều đơn giản và khá hiệu

quả.

• Tuy nhiên, hạn chế lớn nhất của phương án cài đặt này là giới hạn về kích thước của stack N. Giá trị của N có thể quá nhỏ so với nhu cầu thực tế hoặc quá lớn sẽ làm lãng phí bộ nhớ.

KHOA CÔNG NGHỆ THÔNG TIN

• Dùng danh sách liên kết đơn

Head

Đầu ds

Class Node {

info; public Data public Node next;

} Class Stack # Định nghĩa Stack {

public Node Head;

Con trỏ trỏ đến đỉnh của Stack

}

KHOA CÔNG NGHỆ THÔNG TIN

• Các thao tác

 Push

 InitStack

 Pop

 IsEmpty

Head

Đầu ds

KHOA CÔNG NGHỆ THÔNG TIN

• Push: Thêm 1 phần tử x vào Stack

3

• Tạo node mới có dữ liệu x • Thêm vào đầu danh sách

s

2

1 s

2

3

1 p

New

Hàm thêm 1 phần tử có giá trị x vào Stack

Public void (Data x) {…}

KHOA CÔNG NGHỆ THÔNG TIN

• Pop: Lấy 1 phần tử ra khỏi ngăn xếp

• Lấy ra phần tử đầu danh sách • Trả về nội dung và giải phóng nút

s

p

3 3

2

1

3 s

2 1

X=

Hàm lấy một phần tử từ Stack

Public Data Pop() {…}

KHOA CÔNG NGHỆ THÔNG TIN

• Khử đệ quy

• Bài toán đổi số, tháp Hà Nội

• Áp dụng cho bài toán dùng cơ chế LIFO

• Chuyển biểu thức trung tố (Infix) sang biểu thức hậu tố

(Postfix)

• Tính giá trị biểu thức hậu tố

KHOA CÔNG NGHỆ THÔNG TIN

• Nhập 1 số nguyên (VD: nhập n=13) và cơ số (VD: CoSo=2) , xuất biểu diễn của số theo cơ số này.

13 2

11

6

2

00

3

2 Ngưng chia

11 1 2

1 1

0

1

0 1

1 0 1

1 1 0 1 23

KHOA CÔNG NGHỆ THÔNG TIN

1. Hiện thực Stack và các tác vụ của Stack bằng danh sách liên kết.

2. Viết chương trình đổi một số thập phân sang cơ số bất kỳ vận

dụng Stack.

3. Viết chương trình cài đặt bài toán chuyển biểu thức trung tố

sang hậu tố, sau đó tính giá trị biểu thức hậu tố.

KHOA CÔNG NGHỆ THÔNG TIN

• Hàng đợi là một vật chứa (container) các đối tượng làm việc theo cơ chế FIFO (First In First Out)  việc thêm một đối tượng vào hàng đợi hoặc lấy một đối tượng ra khỏi hàng đợi được thực hiện theo cơ chế “Vào trước ra trước”.

• Các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi.