Bài giảng Lập trình C cơ bản: Tuần 4

Chia sẻ: Cố Dạ Bạch | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

12
lượt xem 1
download

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

Bài giảng Lập trình C cơ bản: Tuần 4 cung cấp cho sinh viên những nội dung gồm: ngăn xếp; cài đặt dựa trên mảng; cài đặt dựa trên danh sách liên kết; bài tập;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

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 Lập trình C cơ bản: Tuần 4

C Programming Basic – week 4
Chủ đề • Ngăn xếp – Cài đặt dựa trên mảng – Cài đặt dựa trên danh sách liên kết • Bài tập 2
Ngăn xếp • Ngăn xếp là một cấu trúc dữ liệu tuyến tính mà chỉ có thể truy cập ở một đầu để lưu trữ và truy vấn dữ liệu • Cấu trúc LIFO (Last In First Out) E top D top D D top C top C C C B top B B B B top A A A A A Chèn và xóa phần tử trong ngăn xếp 3
Các thao tác trên ngăn xếp • initialize(stack) --- xóa ngăn xếp • empty(stack) --- kiểm tra rỗng pop push • full(stack) --- kiểm tra đầy • push(el,stack) --- đưa phần tử el vào đầu ngăn xếp full • pop(stack) --- lấy phần tử trên O cùng của ngăn xếp F I • Cài đặt ngăn xếp ntn? L empty 4
Phân tách cài đặt vs đặc tả • INTERFACE: (giao diện) cung cấp các đặc tả của các thao tác • IMPLEMENTATION: (cài đặt) cung cấp mã nguồn của thao tác • CLIENT: chương trình sử dụng các thao tác • Cài đặt dựa trên mảng hoặc danh sách liên kết • Client có thể làm việc ở mức trừu tượng cao 5
Cài đặt sử dụng mảng 0 1 2 3 4 5 6 7 S 10 5 8 9 T: top • Các phần tử được lưu trữ trên mảng • Ngăn xếp rỗng: top= 0 • Ngăn xếp đầy: top = Max_Element 6
Đặc tả ngăn xếp (stack.h) Top of stack #define Max 50 typedef int Eltype; typedef Eltype StackType[Max]; int top; void Initialize(StackType stack); int empty(StackType stack); int full(StackType stack); void push(Eltype el, StackType stack); Eltype pop(StackType stack); 7
Cài đặt ngăn xếp (stack.c) Initialize(StackType stack) push(Eltype el, StackType stack) { { top = 0; if (full(*stack)) } printf(“stack overflow”); empty(StackType stack) else stack[top++] = el; { } return top == 0; Eltype pop(StackType stack) } { full(StackType stack) if (empty(stack)) { printf(“stack underflow”); return top == Max; else return stack[--top]; } } 8
Cài đặt dựa trên cấu trúc • Ngăn xếp được khai báo như một cấu trúc với hai trường: một để lưu trữ, một để quản lý vị trí trên cùng #define Max 50 typedef int Eltype; typedef struct StackRec { Eltype storage[Max]; int top; }; typedef struct StackRec StackType; 9
Cài đặt dựa trên cấu trúc (2) Initialize(StackType *stack) push(Eltype el, StackType *stack) { { (*stack).top=0; if (full(*stack)) } printf(“stack overflow”); empty(StackType stack) else (*stack).storage[ (*stack).top++]=el; { } return stack.top ==0; Eltype pop(StackType *stack) } { full(StackType stack) if (empty(*stack)) { printf(“stack underflow”); return stack.top == Max; else return (*stack).storage[-- (*stack).top];; } } 10
Biên dịch với thư viện Ta có các tệp stack.h, stack.c và test.c Chèn dòng sau #include "stack.h" vào stack.c và test.c gcc – c stack.c gcc –c test.c gcc – o test.out test.o stack.o 11
Chương trình sử dụng ngăn xếp • Viết chương trình chuyển đổi số thập phân sang dạng nhị phân tương ứng sử dụng thư viện ngăn xếp • Mở rộng để chuyển đổi sang dạng thập lục phân 12
Cài đặt dựa trên danh sách liên kết • Điểm khác biệt giữa danh sách liên kết thông thường và ngăn xếp dựa trên danh sách liên kết là một số thao tác không thực hiện được • Thao tác chèn: push(). – Tương tự chèn vào đầu danh sách • Thao tác xóa: pop() – Tương tự xóa ở đầu danh sách 13
Khai báo struct node { int data; struct node *link; }; 14
Push top Temp struct node *push(struct node *p, int value) 7 { 45 struct node *temp; temp=(struct node *)malloc(sizeof(struct 1 node)); if(temp==NULL) { printf("No Memory available Error\n"); 8 exit(0); \ } temp->data = value; temp->link = p; p = temp; return(p); } 15
Push (2) Temp top 45 struct node *push(struct node *p, int value) 7 { struct node *temp; temp=(struct node *)malloc(sizeof(struct 1 node)); if(temp==NULL) { printf("No Memory available Error\n"); 8 exit(0); \ } temp->data = value; temp->link = p; p = temp; return(p); } 16
Push (3) Temp top 45 struct node *push(struct node *p, int value) 7 { struct node *temp; temp=(struct node *)malloc(sizeof(struct 1 node)); if(temp==NULL) { printf("No Memory available Error\n"); 8 exit(0); \ } temp->data = value; temp->link = p; p = temp; return(p); } 17
Pop top Temp 45 struct node *pop(struct node *p, int *value) 7 { struct node *temp; if(p==NULL) { 1 printf(" The stack is empty can not pop Error\n"); exit(0); } 8 *value = p->data; \ temp = p; p = p->link; free(temp); Value at top element need return(p); to be save before pop operation } 18
Pop (2) top Temp 45 struct node *pop(struct node *p, int *value) 7 { struct node *temp; if(p==NULL) { 1 printf(" The stack is empty can not pop Error\n"); exit(0); } 8 *value = p->data; \ temp = p; p = p->link; free(temp); return(p); } 19
Pop (3) top Temp struct node *pop(struct node *p, int *value) 7 { struct node *temp; if(p==NULL) { 1 printf(" The stack is empty can not pop Error\n"); exit(0); } 8 *value = p->data; \ temp = p; p = p->link; free(temp); return(p); } 20