Bài giảng Cấu trúc dữ liệu chương 5: Trịnh Xuân (tóm tắt, chi tiết)

I. Stack – Ngăn xếp:

CHƯƠNG V: STACK - QUEUE

8/4/16

2(cid:1)

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

1. Giới thiệu:

* Các thao tác cơ bản với Stack

! initStack (Stack): Khởi tạo Stack rỗng ! isEmpty (Stack): Kiểm tra Stack có rỗng

hay không?

!  Ngăn xếp là một kiểu danh sách tuyến tính với hai phép toán bổ sung một phần tử vào cuối danh sách và loại bỏ một phần tử cũng ở cuối của danh sách

! isFull (Stack): kiểm tra danh sách đầy ! Push (Stack, Item): Đẩy phần tử item vào

!  Trong ngăn xếp một phần tử vào sau sẽ bị đẩy ra trước và phần tử vào trước sẽ bị đấy ra sau " gọi là danh sách LIFO (Last In First Out)

Stack

! Pop (Stack): Hủy bỏ một phần tử khỏi Stack ! Top (Stack): Xem nội dung của phần tử đầu

tiên của Stack

top

8/4/16

empty stack push an element push another pop

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

2. Cài đặt Stack

a. Cài đặt Stack bằng mảng

!  bằng mảng

#  Sử dụng mảng một chiều để chứa các phần tử #  Cần chỉ số top để chỉ đỉnh

Top

! Thêm – xóa trên vị trí Top #  Chỉ số đầu (0) để chỉ đáy

!  bằng danh sách liên kết

#  Sử dụng một danh sách liên kết đơn #  khai báo và định nghĩa phần tử đầu (Top) để chỉ đỉnh

! Khai báo Cấu trúc DL Stack #define max … struct Stack { int top; Data nut[max]; };

!  Thêm-xóa thực hiện tại vị trí Top #  Phần tử cuối là đáy danh sách

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

* Khởi tạo Stack rỗng:

* Kiểm tra ngăn xếp rỗng

s.top = -1

return 1;

void InitStack ( Stack &s ) { }

if ( s.top == -1 ) else

return 0;

int isEmpty ( Stack s) { }

Top

Top=-1

Top

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

* Kiểm tra danh sách đầy

* Bổ sung một phần tử vào ngăn xếp

void Push( Stack &s, Data x) {

printf((cid:1)Stack day(cid:2));

exit(1); }

return 1;

return 0;

s.top = s.top + 1; s.nut[ s.top ] = x;

int isFull( Stack s) { if (s.top == Max – 1) else }

if ( isFull(s) == 1) { else { }

}

Top

Top=max-1

Top

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

*Lấy một phần tử (xóa) ra khỏi danh sách

* Lấy nội dung của phần tử đầu tiên

Data Pop( Stack &s) {

Data Top( Stack *s) {

tg = s.nut[s.top];

Data tg; tg = s.nut[s.top]; s.top = s.top – 1; return tg;

Data tg; if ( isEmpty(s) = = 1 ) { printf((cid:1)Ngan xep rong(cid:2)); exit(1); } else { } return tg;

if ( isEmpty(s) == 1 ) { printf((cid:1)Ngan xep rong(cid:2)); exit(1); } else { }

}

Top

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

b. Cài đặt Stack bằng Danh sách liên kết

* Khai báo cấu trúc dữ liệu

! Stack là một danh sách liên kết đơn. Được

định nghĩa với cấu trúc:

! Ngăn xếp được cài đặt bằng danh sách liên kết có kích thước gần như (cid:1)vô hạn(cid:2)

3

top

2

1

struct StackNode { Data info; struct StackNode *next; }; struct Stack { Node top; };

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

* Khởi tạo Stack

* Kiểm tra ngăn xếp rỗng

s.top = NULL;

return 1;

void InitStack( Stack &s) { }

return 0;

int isEmpty( Stack s ) { if (s.top == NULL) else }

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

* Thêm phần tử vào danh sách:

* Lấy phần tử khỏi danh sách:

void Push ( Stack &s, Data x ) {

Data Pop ( Stack &s ) {

printf((cid:1)Stack rong(cid:2)); exit(1);

}

StackNode *p; p = new StackNode; If (p==NULL) {cout<<“Khong cap phat duoc”; exit(1); } p->info = x; p->next = s.top; s.top = p;

}

p = s.top; s.top = s.top->next;

tg = p->info; delete p;

StackNode *p; Data tg; if (isEmpty(s) == 1) { else { } return tg;

}

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

* Lấy nội dung phần tử đầu tiên Stack:

3. Ứng dụng ngăn xếp

Data Top (Stack *s) {

printf((cid:1)Stack rong(cid:2)); exit(1); }

! Đảo ngược xâu ký tự ! Chuyển đổi cơ số ! Tính giá trị của một biểu thức ! Chuyển biểu thức dạng trung tố sang hậu tố ! Thuật toán sắp xếp QuickSort

tg = s->top.info;

Node *p; Data tg; if ( isEmpty(s) == 1 ) { else { } return tg;

}

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

a. Bài toán đảo ngược xâu ký tự

* Cài đặt

! Bài toán: cho một chuỗi ký tự, yêu cầu đảo ngược chuỗi

ký tự đã có (ứng dụng Stack)

… //định nghĩa các thao tác cơ bản của Stack chứa ký tự void main() {

char *st; int i; stack *s;

! Thuật toán

InitStack(s);

# Bước 1: Tạo ngăn xếp

printf((cid:1)Nhap chuoi ky tu:(cid:2)); gets(st);

for (int i=0; i

Push( s, st[i]);

! Duyệt từ đầu xâu đến cuối xâu ! Lần lượt cho các ký tự vào ngăn xếp – cho hết các ký tự vào ngăn xếp

# Bước 2: Lấy từ ngăn xếp ra

! Lần lượt lấy các phần tử từ ngăn xếp và in ra

printf((cid:1)%c(cid:2), Pop(s));

printf((cid:1)\n Xau dao nguoc:(cid:2)); while (!isEmpty(s)) getch();

}

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

b. Bài toán chuyển đổi cơ số

*Thuật toán

! Tính

! Cho số nguyên n trong hệ thập phân và cơ số

cần chuyển sang là b

# 5310 = ?2 # 7210 = ?4

! Chuyển một số từ hệ thập phân sang hệ cơ

! Bước 1: Khởi tạo Stack rỗng ! Bước 2: Tạo Stack

số bất kỳ 7210 = 1.43 + 0.42 + 2.41 + 0.40= 10204

# Tính kết quả = n % b. Đẩy vào Stack. # Thay n = n / b (để tìm các số tiếp theo). # Quá trình lặp cho đến khi n = 0.

5310 = 1.25 + 1.24 + 0.23 + 1.22 + 0.21 + 1.20=

= 1101012

! Bước 3: Đọc từ Stack

# Lấy lần lượt các chữ số lưu trong Stack, chuyển sang dạng ký tự tương ứng với hệ cơ số trước khi in ra kết quả

28(cid:1)

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

Cài đặt chuyển đổi cơ số

//Cài đặt các thao tác của Stack

- Khai báo CTDL - Đ/n hàm khởi tạo - Đ/n hàm kiểm tra rỗng - Đ/n hàm kiểm tra đầy - Đ/n hàm bổ sung phần tử - Đ/n hàm lấy và xóa phần tử //Cài đặt hàm main thực hiện thuật toán

…

int main() { }

30(cid:1)

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

II. Queue – Hàng đợi

1. Giới thiệu:

$  Hàng đợi là một kiểu danh sách trong đó có phép toán bổ sung một phần tử vào cuối danh sách và loại bỏ một phần tử ở đầu danh sách.

$  Trong hàng đợi một phần tử vào trước sẽ bị đẩy ra trước và phần tử vào sau sẽ bị đẩy ra sau " gọi là danh sách FIFO (First In First Out)

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

* Các thao tác cơ bản với Queue

2. Biểu diễn Queue:

!  Mảng

# Dùng hai chỉ số Rear và Front để lưu giữ điểm

! InitQueue (Queue): Khởi tạo Queue rỗng ! isEmpty (Queue): Kiểm tra Queue có rỗng

đầu và điểm cuối hàng đợi

hay không?

!  Danh sách liên kết

! isFull (Queue): kiểm tra danh sách đầy

# Dùng DSLK đôi với điểm đầu Rear và điểm cuối

! Put (Queue, Item): Đẩy một phần tử vào

Front ! Thêm vào Rear ! Lấy ra từ Front

Queue

! Get (Queue): Hủy bỏ một phần tử khỏi

Queue

t n o r F

r a e R

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

*Cài đặt Queue bằng Danh sách liên kết

$ Khai báo cấu trúc:

!  Khởi tạo

Rear

struct NodeQueue { Data info; struct NodeQueue *next; struct NodeQueue *pre;

Q.Rear = NULL; Q.Front = NULL;

void InitQueue(Queue &Q) { }

}; struct Queue {

NodeQueue *Rear, *Front;

Front

} Queue Q;

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

* Thêm phần tử vào Queue:

Kiểm tra hàng đợi rỗng

x

Int isEmpty( Queue q) {

Đưa thành phần x vào đầu Queue void Put( Queue &Q, Data x) {

p->next = NULL; p->pre = NULL;

Rear

NodeQueue *p; p = new NodeQueue; if ( p == NULL ){ printf((cid:1)Ko bo sung duoc(cid:2)); exit(1); } p->info = x; if ( Q.Rear = = NULL) {

if (Q.Rear == NULL) return 1; else

return 0;

Q.Font = p;

Q.Rear = p;

}

} else //Chèn thêm phần tử mới vào cuối danh sách {

Q.Rear->pre = p;

p->next = Q.Rear; Q.Rear = p;

}

Font

}

54(cid:1)

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

* Hủy bỏ phần tử khỏi danh sách:

3. Ứng dụng của hàng đợi

Rear

x

Hủy bỏ phần tử tại vị trí Front của DS Data Get ( Queue &Q ) {

Data x;

QueueNode *p; if ( Q.Front = = NULL ) {

printf((cid:1)\n Ko huy bo duoc(cid:2)); exit(1);

Q.Front->next = NULL;

} p = Q.Front; x = p->info; Q.Front = p->pre; free(p); return x;

Front

}

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

Bài toán cộng 2 đa thức

Kiểm tra chuỗi Palindromes

%  Chuỗi Palindrome là chuỗi mà đọc xuôi giống đọc ngược %  Ví dụ: Able was I ere I saw Alba

% Thuật toán

!  Mỗi nút của danh sách

$  Đọc lần lượt chuỗi trên vào Stack và Queue $  So sánh từng phần tử của Stack và Queue, nếu giống nhau từng cặp thì đó là chuỗi Palindrome, ngược lại thì chuỗi trên không phải là chuỗi Palindrome

HS SM Next

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân

Biểu diễn đa thức

Kiểm Tra giữa kỳ

! Thực hiện lần lượt các yêu cầu sau:

# Khai báo CTDL dạng DSLK đơn để quản lý một đối

tượng nào đó trong BTL của mình

# Định nghĩa các CTC thực hiện:

! Nhập danh sách đối tượng ! In danh sách đối tượng ! Đếm số các đối tượng trong ds theo điều kiện nào đó ! Sắp xếp DS các đối tượng theo thứ tự tăng dần của một

điều kiện nào đó

! Cho biết thông tin của đối tượng có giá trị lớn nhất của

một yêu cầu nào đó

# Chương trình chính: Áp dụng các yêu cầu trên

! Ghi rõ Họ tên – lớp – số nhóm ! Ghi rõ đề bài cụ thể trước khi làm

61(cid:1)

8/4/16

CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân