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

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

Thêm vào BST

Báo xấu

29
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

3 KHOA CÔNG NGHỆ THÔNG TIN
4 KHOA CÔNG NGHỆ THÔNG TIN
Cơ chế: Last In First Out LIFO Stack 5 KHOA CÔNG NGHỆ THÔNG TIN
Mảng 1 chiều Danh sách liên kết đơn Cấp phát Kích thước stack động! khi quá thiếu, lúc quá thừa Push/Pop Push / Pop hơi khá dễ dàng phức tạp 6 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]; int count; } 7 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) 8 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; } } 9 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"); } 10 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 } } 11 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") } 12 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ử } 13 } 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. 14 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; } 15 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") } 16 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ớ. 17 KHOA CÔNG NGHỆ THÔNG TIN
• Dùng danh sách liên kết đơn Head Đầu ds Class Node { public Data info; public Node next; } Class Stack # Định nghĩa Stack { public Node Head; Con trỏ trỏ đến đỉnh của Stack } 18 KHOA CÔNG NGHỆ THÔNG TIN
• Các thao tác  InitStack  Push  IsEmpty  Pop Head Đầu ds 19 KHOA CÔNG NGHỆ THÔNG TIN
• Push: Thêm 1 phần tử x vào Stack • Tạo node mới có dữ liệu x • Thêm vào đầu danh sách 3 s 2 1 2 s p 3 1 New Public void (Data x) {…} Hàm thêm 1 phần tử có giá trị x vào Stack 20 KHOA CÔNG NGHỆ THÔNG TIN