Bài giảng Cấu trúc dữ liệu và giải thuật: Stack - Queue

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

Thêm vào BST

Báo xấu

106
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: Stack - Queue" cung cấp cho người đọc các kiến thức: Khái niệm, các thao tác trên Stack, cài Stack bằng mảng 1 chiều, kiểm tra tính rỗng và đầy của Stack, cài Stack bằng danh sách liên kết,... Mời các bạn cùng tham khảo nội dung chi tiết.

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: 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 Click To Edit NỘIMaster STACK - QUEUE DUNGTitle Style 1
Click To Edit Master Title Style STACK  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ácClick To trên thao tác EditStack 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àiClick To Edit đặt Stack 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àiClick Stack To Edit bằng Master mảng 1 chiềuTitle 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 Kiểm To rỗng tra tính Editvà Master đầy củaTitle StackStyle 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
Click Thêm To Edit 1 phần tử vàoMaster 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 TotửEdit 1 phần Master 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 N. Cấu trúc dữ liệu và thuật giải 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àiClick Stack To Edit bằng Master danh Title sách liên kết Style • 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
Click Thêm To Edit 1 phần tử vàoMaster 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 TotửEdit 1 phần Master 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 Edit Ứng Master dụng StackTitle Style • 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 To Edit dụngMaster Title của ngăn xếpStyle  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Định To Edit Master giá biểu thức Title số họcStyle • 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 Edit Định Master giá biểu Title thức số học Style 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Định To giá Edit Master biểu thức số Title học Style 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Định To giá Edit Master biểu thức số Title học Style • 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)