Bài giảng Stack Queue

Chia sẻ: Cvcxbv Cvcxbv | Ngày: | Loại File: PPT | Số trang:34

Thêm vào BST

Báo xấu

128
lượt xem 10
download

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

Bài giảng Stack Queue nêu Stack là 1 vật chứa các đối tượng làm việc theo cơ chế LIFO (Last In First Out), từc việc thêm 1 đối tượng vào Stack hoặc lấy 1 đối tượng ra khỏi Stack được thực hiện theo cơ chế “vào sau ra trước"

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 Stack Queue

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Cấu trúc dữ liệu và thuật giải NỘI DUNG STACK - QUEUE Click To Edit Master Title Style 1
STACK To Edit Master Title Style Click  Stack (ngăn xếp): Là 1 vật chứa các đối tượng làm việc theo cơ chế LIFO (Last In First Out), từc việc thêm 1 đối tượng vào Stack hoặc lấy 1 đối tượng ra khỏi Stack được thực hiện theo cơ chế “vào sau ra trước” Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 2
CácClicktác trên Stack thao To Edit Master Title Style • Push(o): Thêm đối tượng o vào Stack • Pop(): Lấy đối tượng từ Stack • isEmpty(): Kiểm tra Stack có rỗng hay không • Top(): Trả về giá trị của phần tử nằm đầu Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Stack mà không hủy nó khỏi Stack. 3
Cài Click To đặt Stack Edit Master Title Style  Dùng mảng 1 chiều Data S [N]; int t; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Dùng danh sách liên kết đơn S 4 6 5 1 8 2 List S  Thêm và hủy cùng phía 4
Cài Click bằng mảng 1 chiều Stack To Edit Master Title Style  Cấu trúc dữ liệu của Stack typedef struct tagStack { int a[max]; int t; Cấu trúc dữ liệu và thuật giải }Stack; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Khởi tạo Stack: void CreateStack(Stack &s) { s.t=-1; } 5
Click To Edit Master Title Style Kiểm tra tính rỗng và đầy của Stack int IsEmpty(Stack s)//Stack có rỗng hay không { if(s.t==-1) return 1; else return 0; } Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT int IsFull(Stack s) //Kiểm tra Stack có đầy hay không { if(s.t>=max) return 1; else return 0; } 6
Thêm 1 phTo tEdit Master Click ần ử vào Stack Title Style int Push(Stack &s, int x) { if(IsFull(s)==0) { s.t++; Cấu trúc dữ liệu và thuật giải s.a[s.t]=x; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT return 1; } else return 0; } 7
LấyClick n tử Edit Master 1 phầ To từ Stack Title Style int Pop(Stack &s, int &x) { if(IsEmpty(s)==0) { x=s.a[s.t]; Cấu trúc dữ liệu và thuật giải s.t--; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT return 1; } else return 0; } 8
Click To NHẬN XÉT Title Style Edit Master • 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 Cấu trúc dữ liệu và thuật giải N. Giá trị của N có thể quá nhỏ so với nhu cầu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT thực tế hoặc quá lớn sẽ làm lãng phí bộ nhớ. 9
Cài Click bằng danh sách liên kết Style Stack To Edit Master Title • Kiểm tra tính rỗng của Stack int IsEmpty(List &s) { if(s.pHead==NULL)//Stack rong return 1; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT else return 0; } 10
Thêm 1 phTo tEdit Master Click ần ử vào Stack Title Style void Push(List &s,Node *Tam) { if(s.pHead==NULL) { s.pHead=Tam; s.pTail=Tam; } Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT else { Tam->pNext=s.pHead; s.pHead=Tam; } } 11
LấyClick n tử Edit Master 1 phầ To từ Stack Title Style int Pop(List &s,int &trave) { Node *p; if(IsEmpty(s)!=1) { if(s.pHead!=NULL) { p=s.pHead; trave=p->Info; s.pHead=s.pHead->Next; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT if(s.pHead==NULL) s.Tail=NULL; return 1; delete p; } } return 0; } 12
STACK Click To Edit Master Title Style Mảng 1 chiều Danh sách LK Kích thước stack Cấp phát khi quá thiếu, lúc động! quá thừa Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Push/Pop khá dễ dàng Push / Pop hơi phức tạp 13
Click To ng dụMaster Title Style Ứ Edit ng Stack • Trình biên dịch, thông dịch: Khi thực hiện các thủ tục thì stack được dùng để lưu môi trường của các thủ tục • Khử đệ qui • Lưu vết các quá trình quay lui, vét cạn. Lưu dữ Cấu trúc dữ liệu và thuật giải liệu khi giải một số bài toán về lý thuyết đồ thị, CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ví dụ như bài toán tìm đường đi 14
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Cấu trúc dữ liệu và thuật giải VD Click To Edit Master Title Style 15
ClickỨng Edit Master Title p To dụng của ngăn xế Style  Chuyển đổi cơ số đếm  Giải các bài toán đệ quy Cấu trúc dữ liệu và thuật giải  Soạn thảo văn bản CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Định giá biểu thức số học 16
Click ịTo giá biMaster Titleọc Đ nh Edit ểu thức số h Style • Sử dụng ngăn xếp chuyển biểu thức dạng trung tố có dấu ngoặc sang dạng hậu tố E=((a+b)*a-b)/c-a+(a+b)/(a-b) Trung tố (infix) E1=+-/-*+ababca/+ab-ab Tiền tố (prefix) Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT E2=ab+a*b-c/a-ab+ab-/ Hậu tố (postfix) • Sử dụng ngăn xếp định giá biểu thức dạng hậu tố 17
Click To Editbiểu thức sTitle Style Định giá Master ố học Thuật toán 1 : Chuyển biểu thức dạng trung tố có dấu ngoặc sang dạng hậu tố Cấu trúc dữ liệu và thuật giải • Sử dụng ngăn xếp rỗng có đáy là $ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT • Sử dụng hàm pri với pri($)
ClickĐTo giá biểMaster Title Style ịnh Edit u thức số học Bước 1 – Đọc lần lượt từng thành phần của biểu thức trung tố giả sử đó là x Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT • Nếu x là ngoặc mở đẩy x vào ngăn xếp • Nếu x là toán hạng thì viết x vào bên phải của biểu thức hậu tố 19
ClickĐTo giá biểMaster Title Style ịnh Edit u thức số học • Nếu x là toán tử thì : – Xét phần tử đỉnh của ngăn xếp giả sử đó là y – Nếu pri(y)>=pri(x) thì loại y ra khỏi ngăn xếp, Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT viết y vào bên phải của biểu thức hậu tố và lại xét phần tử đỉnh của ngăn xếp – Nếu pri(y)