Khoa công nghệ thông tin bài giảng LẬp trình cơ BẢn biên soạn
tải về 1.56 Mb.
|
- Điều hướng trang này:
- 1. Khái niệm
- 2. Cài đặt ngăn xếp sử dụng mảng
- 3. Cài đặt ngăn xếp sử dụng con trỏ liên kết
- 4. Một số ứng dụng của ngăn xếp
II. Ngăn xếp- Khai báo biến cố định làm lãng phí bộ nhớ do khai báo số lượng phần tử lớn nhất để lưu trữ dữ liệu - Khi thay đổi về số lượng phần tử cần phải lưu trữ thì mảng cấp phát động không thể giải quyết được tiết kiệm bộ nhớ và hạn chế các thao tác chuyển bộ nhớ. - Giải quyết vấn đề cấp phát bộ nhớ của khối dữ liệu liên tục sẽ vượt quá giới hạn quản lý bộ nhớ của một số hệ điều hành, khó trong tìm được vùng nhớ lớn phù hợp để cấp phát. - Giải pháp đưa ra kiểu cấu trúc, bản thân các đối tượng trỏ (liên kết) đến đối tượng tiếp theo trong danh sách. - Các vùng nhớ cấp phát không liên tục nên các lệnh làm việc với nhóm các đối tượng sẽ không thực hiện được. Kiểu cấu trúc liên kết được sử dụng xây dựng nhiều dạng cấu trúc khác nhau, nhưng đặc trưng là cấu trúc ngăn xếp và hàng đợi. 1. Khái niệmNgăn xếp là kiểu đặc biệt của danh sách việc loại bỏ và bổ sung đều được thực hiện trên một đầu của danh sách. Vì thế các phần tử khi bổ sung vào ngăn xếp sau sẽ được lấy ra trước nên gọi là LIFO (Last In First Out). Thao tác cơ bản của ngăn xếp là bổ sung (push), loại bỏ (pop), ngoài ra có thao tác khởi tạo, kiểm tra trạng thái. Ví dụ trực quan của ngăn xếp là chồng bát, bát mới vào luôn được đặt lên trên, thứ tự lấy bát từ trên xuống dưới. 
2. Cài đặt ngăn xếp sử dụng mảngSử dụng mảng một chiều để thể hiện ngăn xếp, dùng một biến chỉ số mô tả phần tử ở đỉnh của ngăn xếp. Biến chỉ sổ sẽ chỉ ra vị trí tiếp theo được thêm vào, và vị trí trừ đi 1 là vị trí phần tử đang có ở ngăn xếp. 
Khai báo typedef struct stack { int top;
int storage[MAX]; };
void init(stack *s) { s->top=0; } Kiểm tra ngăn xếp rỗng ///0: empty int empty(stack *s) { return s->top; } Kiểm tra ngăn xếp đầy ///0:full int full(stack *s) { if(s->top>=MAX) { return 0; } else
{ return s->top+1; } }
//-1 full of stack int push(stack *s, int value) { if(s->top==MAX) { return -1; } else
{ s->storage[s->top]=value; s->top++; } return s->top; } Lấy một phần tử khỏi ngăn xếp //-1: try to pop the empty stack int pop(stack *s, int *out) { if(s->top<=0) { out=0;
return -1; } else { s->top--; *out=s->storage[s->top]; return s->top; } }
3. Cài đặt ngăn xếp sử dụng con trỏ liên kếtCấp phát đúng số lượng phần tử mà ngăn xếp đang cần. Thao tác phức tạp. 
Khai báo typedef struct stackNode { int item; stackNode *next; }; typedef struct stack{ stackNode* top; };
void init(stack *s) { s->top=NULL; } Kiểm tra ngăn xếp rỗng ///0: empty int empty(stack *s) { if(s->top==NULL) { return 0; } else
{ return 1; } }
///-1: cant push to stack int push(stack *s,int value) { stackNode *a; a=(stackNode*)malloc(sizeof(stackNode)); if(a==NULL) { return -1; } a->item=value; a->next=s->top; s->top=a; return 0; }
Lấy một phần tử ra khỏi ngăn xếp 
int pop(stack *s,int *out) { stackNode *cur; if(s->top==NULL) { return -1; } *out=s->top->item; cur=s->top; s->top=s->top->next; free(cur); }
Ngăn xếp được sử dụng trong nhiều ứng dụng khác nhau - Đảo ngược xây ký tự - Tính giá trị biểu thức dạng hậu tố - Chuyển biểu thức dạng trung tố sang hậu tố - Sử dụng để khử đệ qui, chuyển bài toán đệ qui (sử dụng ngăn xếp của hệ thống) sang sử dụng ngăn xếp ngoài.
Ví dụ về đảo ngược xâu sử dụng ngăn xếp. Do ngăn xếp có qui luật vào trước ra sau nên lần lượt đưa các ký tự vào ngăn xếp, sau đó tiến hành lấy ra các ký tự sẽ được đảo ngược thứ tự. #include #include #include #include typedef struct stackNode { char item; stackNode *next; }; typedef struct stack{ stackNode* top; }; /// void init(stack *s); ///0: empty int empty(stack *s);; ///-1: cant push to stack int push(stack *s,char value); ///-1: pop empty stack int pop(stack *s,char *out); stack s;
int main() { int i; char v; char *c="xau dao nguoc"; init(&s); for(i=0;i {
push(&s,c[i]); while(empty(&s)!=0) { pop(&s,&v); printf("\n%c",v); } getch(); return 0; } ///implemention void init(stack *s) { s->top=NULL; } ///--------- ///0: empty int empty(stack *s) { if(s->top==NULL) { return 0; } else
{ return 1; } }
///-1: cant push to stack int push(stack *s,char value) { stackNode *a; a=(stackNode*)malloc(sizeof(stackNode)); if(a==NULL) { return -1; } a->item=value; a->next=s->top; s->top=a; return 0; } ///------------- ///-1: pop empty stack int pop(stack *s,char *out) { stackNode *cur; if(s->top==NULL) { return -1; } *out=s->top->item; cur=s->top; s->top=s->top->next; free(cur); }
Каталог: files -> FileMonHoc FileMonHoc -> NGÂn hàng câu hỏi lập trình cơ BẢn nhóm câu hỏI 2 ĐIỂM FileMonHoc -> CHƯƠng 2 giới thiệu về LÝ thuyết số FileMonHoc -> CÁc hệ MẬt khoá CÔng khai kháC FileMonHoc -> BỘ MÔn duyệt chủ nhiệm Bộ môn FileMonHoc -> Khoa công nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam FileMonHoc -> Chủ nhiệm Bộ môn Ngô Thành Long ĐỀ CƯƠng chi tiết bài giảNG FileMonHoc -> Chủ nhiệm Bộ môn Phan Nguyên Hải ĐỀ CƯƠng chi tiết bài giảNG FileMonHoc -> Khoa: CÔng nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam FileMonHoc -> MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon FileMonHoc -> Khoa cntt cộng hòa xã HỘi chủ nghĩa việt nam tải về 1.56 Mb. Chia sẻ với bạn bè của bạn:
|