zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Ngôn ngữ lập trình C - Chương 7 - Bài 2. Stack

Chia sẻ: Nguyen Duc Anh | Ngày: | Loại File: PDF | Số trang:10

Báo xấu

225
lượt xem 43
download

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

Stack (ngăn xếp) - Là một cấu trúc dữ liệu mà các thao tác xử lý chỉ được thực hiện ở phía đáy (cuối) của nó

Chủ đề:

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

Lưu

Nội dung Text: Ngôn ngữ lập trình C - Chương 7 - Bài 2. Stack

4/28/2010 Chương 7. Bài 2. Stack ĐỖ BÁ LÂM ViỆN CNTT&TT, TRƯỜNG ĐHBK HÀ NỘI Nội dung  1. Khái niệm stack  2. Xây dựng stack  2.1. Sử dụng mảng  2.2. Sử dụng danh sách liên kết 2 1. Khái niệm stack  Stack (ngăn xếp)  Là một cấu trúc dữ liệu mà các thao tác xử lý chỉ được thực hiện ở phía đáy (cuối) của nó  Cấu trúc dạng LIFO (Last In First Out) – “Vào sau ra trước”  Thao tác xử lý • Đẩy vào PUSH • Lấy ra POP 3 1
4/28/2010 1. Khái niệm stack Đỉnh Đáy 1. Khái niệm stack Push(B) Pop() Pop() Push(A) A B A B B A A A Stack rỗng Stack có 1 phần tử: Stack có 2 phần tử: Stack còn 1 phần tử: Stack lại rỗng A AB A Ứng dụng của Stack  Lưu trữ các trang web đã từng được duyệt trên Web browser  Cài đặt thao tác Undo trong các phần mềm soạn thảo  Lưu danh sách các lời gọi hàm trong Java Virtual Machine 2
4/28/2010 Ghi nhớ  Stack được hình dung như một ngăn xếp chứa các quyển sách với 2 thao tác đưa vào và lấy ra theo nguyên tắc:  Quyển sách nào được đưa vào sau sẽ lấy ra trước – LIFO (Last In First Out) Ví dụ - Bài toán chuyển cơ số  Nguyên tắc đổi một số nguyên từ thập phân sang nhị phân: Các số dư lấy ra sau được hiển thị trước Cơ chế sắp xếp của Stack Giải pháp  Dùng stack để lưu trữ số dư qua từng phép chia:  Khi thực hiện phép chia: Đưa số dư vào Stack  Khi hiển thị kết quả: Lấy chúng lần lượt từ Stack 3
4/28/2010 Giải pháp 1 1 1 PUSH 0 0 0 PUSH 0 0 0 0 1 1 0 0 1 1 1 POP 0 0 0 0 0 0 0 Giải thuật 1. Nhap N 2. while N != 0 R = N% 2; //Tính số dư trong phép chia N cho 2 PUSH (S, R); //Đẩy R vào đỉnh Stack S N=N/2; //Thay N bằng N/2 3. while S chưa rỗng POP(S,R); //Lấy phần tử từ stack đưa vào R Hien_thi R; 2. Xây dựng Stack  Lưu trữ được các đối tượng dữ liệu (quyển sách)  Xây dựng 2 thao tác Push và Pop theo nguyên tắc LIFO  Có hai cách cài đặt stack  Sử dụng mảng  Sử dụng danh sách liên kết 4
4/28/2010 2.1. Sử dụng mảng Đáy Stack  Mỗi phần tử của stack được lưu như một phần tử của mảng  Đáy: phần tử có chỉ số 0  Đỉnh: phần tử được đưa vào cuối cùng, có chỉ số T  Khởi tạo T=-1  Stack rỗng (empty) T = -1, stack đầy T = MAX-1 13 2.1. Sử dụng mảng  #define MAX 100 //So phan tu lon nhat cua Stack  //Khai bao Stack va T la 2 bien toan cuc  ElemType Stack[MAX];  int T=-1; 14 2.1. Sử dụng mảng  Stack được biểu diễn thông qua mảng S[MAX]  int push(ElemType N){ if (T==MAX-1) return 0; else{ //mảng chưa đầy T++; S[T]=N; } return 1; } 5
4/28/2010 2.1. Sử dụng mảng  int pop(ElemType *N){ if (T== -1) return 0; else{ *N = S[T--]; return 1; } } 2.2. Sử dụng danh sách liên kết Head  Stack là cấu trúc LIFO (Last In First Out)  Thao tác Push, Pop? 17 2.2. Sử dụng danh sách liên kết  Push  Thêm một nút vào đầu danh sách  Pop  Lấy giá trị nút đầu tiên trong danh sách  Loại bỏ nút này khỏi danh sách 18 6
4/28/2010 2.2. Sử dụng danh sách liên kết struct node { ElemType data; struct node *next; }; //Khai báo con trỏ đầu là biến toàn cục struct node *top; Push Temp void push(ElemType N) { top struct node *temp; 45 temp=(struct node *) 7 malloc(sizeof(struct node)); temp->data = N; 1 temp->next = top; top = temp; 8 \ } Push Temp void push(ElemType N) { top struct node *temp; 45 temp=(struct node *) 7 malloc(sizeof(struct node)); temp->data = N; 1 temp->next = top; top = temp; 8 \ } 7
4/28/2010 Push Temp void push(ElemType N) { top struct node *temp; 45 temp=(struct node *) 7 malloc(sizeof(struct node)); temp->data = N; 1 temp->next = top; top = temp; 8 \ } Pop int pop(ElemType *N){ Temp top struct node *temp; 45 if(top==NULL) return 0; else{ 7 *N = top->data; temp = top; top = top->next; 1 free(temp); return 1; } 8 } \ Giá trị của thành phần top cần lưu lại trước khi giải phóng vùng nhớ Pop int pop(ElemType *N){ Temp top struct node *temp; 45 if(top==NULL) return 0; else{ 7 *N = top->data; temp = top; top = top->next; 1 free(temp); return 1; } 8 } \ 8
4/28/2010 Pop int pop(ElemType *N){ Temp top struct node *temp; if(top==NULL) return 0; else{ 7 *N = top->data; temp = top; top = top->next; 1 free(temp); return 1; } 8 } \ Bài toán  Demo dS_Array.c, dS_List.c  Bài tập 1.  Viết chương trình chuyển một số nguyên dương từ hệ cơ số 10 sang hệ cơ số 2 sử dụng stack (bằng mảng và danh sách liên kết) Bài toán  Bài tập 2. Cộng hai số nguyên lớn  Kiểu dữ liệu số nguyên chỉ biểu diễn số trong phạm vi nhất định  Mục đích: thực hiện thao tác cộng, trừ, nhân, chia trên các số nằm ngoài phạm vi biểu diễn 27 9
4/28/2010 Bài toán  Thực hiện phép cộng trên hai số nguyên “lớn”  Hai số được lưu dưới dạng xâu kí tự 28 Bài toán  Cải tiến  Trong cách xây dựng stack bằng mảng, thay vì tách rời mảng và biến T chúng ta định nghĩa một cấu trúc gồm 2 trường là mảng và biến T này  Áp dụng làm lại các bài tập ở trên. 29 Thảo luận 30 10

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.