Bài giảng Cấu trúc dữ liệu 1: Chương 3 - Lương Trần Hy Hiến

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

68
lượt xem 4
download

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

Chương 3 của bài giảng Cấu trúc dữ liệu 1 giới thiệu về danh sách đặc (mảng). Trong chương này, người học sẽ lần lượt tìm hiểu các nội dung: Định nghĩa mảng, các thao tác xử lý cơ bản trên mảng, stack, queue. Mời các bạn tham khảo.

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 1: Chương 3 - Lương Trần Hy Hiến

ðại Họ Học Sư Phạ Phạm Tp. Hồ Hồ Chí Chí Minh Nội dung 1. ðịnh nghĩa 2. Các phép toán trên mảng CẤU TRÚC DỮ LIỆU 1 3. Stack 4. Queue ặc (Mả Chương 3: Danh sách ñặ ảng) 1. ðịnh nghĩa 2. Các thao tác xử lý cơ bản trên mảng Bài tập 1: Viết chương trình nhập vào một dãy số nguyên. In • Mảng là tập hợp của các biến cùng kiểu ñược dãy số vừa nhập theo thứ tự ngược lại. xếp liên tiếp nhau trong bộ nhớ trong. • Các loại mảng: Input : số lượng các phần tử trong dãy (N>0). – Mảng 1 chiều N số nguyên. • tên_mảng [số_phần_tử] Output: N số nguyên theo thứ tự ngược lại. – Mản nhiều chiều • tên_mảng ðối tượng dữ liệu : int N [số_phần_tử_chiều_1][số_phần_tử_chiều_2]…[số_phần int a[] _tử_chiều_n] Thao tác xử lý: Nhập số lượng phần tử Nhập dãy số Xuất dãy số
2. Các thao tác xử lý cơ bản trên mảng #include Bài tập 2: Viết chương trình nhập vào một dãy số nguyên int n; dương. In ra dãy số sau khi chèn một phần tử nguyên dương int a[100]; vào một vị trí cho trước của dãy. void main(){ coutn; N là số lượng các phần tử. int N, X, K for (int i=0; i
b) Thao tác xóa 1 phần tử của mảng 2. Các thao tác xử lý cơ bản trên mảng K Bài tập 4: Viết chương trình nhập vào một dãy số nguyên. In N ra vị trí của giá trị X nhập vào từ bàn phím hoặc thông báo 0 1 2 3 4 5 6 7 8 9 không tìm thấy. 4 1 6 7 3 5 8 ~ 9 ~ ~ Input : ðối tượng dữ liệu: i N là số lượng các phần tử. int N, X N số nguyên dương int A[] Mô tả for ( i = K; i
c) Thao tác tìm kiếm tuyến tính c) Thao tác tìm kiếm tuyến tính X=3 N X=3 N 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 4 1 6 7 3 5 8 ~ 9 ~ ~ 4 1 6 7 0 5 8 39 ~ ~ 1. I =0; int linearSearch(int a[], int N, 1. I =0; A[N] = X int linearSearch(int a[], int N, int X) { int X) { 2. Trong khi I
c) Thao tác tìm kiếm nhị phân L R N int BinarySearch (int a[],int n, int x) { 0 1 2 3 4 5 6 7 8 int left = 0; X=4 1 3 5 6 7 8 9 ~ 9 ~ int right = n-1; while(lefta[mid] : left= mid +1; //tìm tiếp trong dãy amid+1 …aright } Bước 3: Nếu left
3. Stack Ví dụ về stack • Một stack là một cấu trúc • Stack rỗng: dữ liệu mà việc thêm vào và loại bỏ ñược thực hiện • ðẩy (push) Q vào: Q tại một ñầu (gọi là ñỉnh – top của stack). A Q • Là một dạng vào sau ra • ðẩy A vào: trước – LIFO (Last In A First Out) • Lấy (pop) ra một => ñược A: Q • Lấy ra một => ñược Q và stack rỗng: Q Ứng dụng: ðảo ngược danh sách Các phép toán trên ngăn xếp • Yêu cầu: ðảo ngược một danh sách nhập vào • empty(A): kiểm tra ngăn xếp có rỗng? • Giải thuật: • length(A): Cho biết số phần tử ngăn xếp. 1. Lặp lại n lần • push(A, x): Thêm phần tử x vào ngăn xếp A. 1.1. Nhập vào một giá trị 1.2. ðẩy nó vào stack • pop(A): Loại phần tử ở ñỉnh ngăn xếp. 2. Lặp khi stack chưa rỗng • getTop(A): Lấy phần tử ở ñỉnh ngăn xếp. 2.1. Lấy một giá trị từ stack 2.2. In ra
ðảo ngược danh sách – Ví dụ ðảo ngược danh sách – Mã C++ Cần nhập 4 số vào #include sử dụng STL Ban ñầu Nhập 1 Nhập 5 Nhập 7 Nhập 3 using namespace std; (Standard Template Library) 3 int main( ) { khai báo một stack có kiểu dữ liệu của các phân tử bên trong là double 7 7 int n; double item; 5 5 5 stack numbers; 1 1 1 1 cout > n; ñẩy một số vào trong stack Stack ñã rỗng for (int i = 0; i < n; i++) { Lấy ra => 3 Lấy ra => 7 Lấy ra => 5 Lấy ra => 1 Ngừng kiểm tra xem stack có khác rỗng không cin >> item; numbers.push(item); 3 } lấy giá trị trên ñỉnh của stack ra, stack không ñổi 7 7 while (!numbers.empty( )) { 5 5 cout
Thiết kế stack Thiết kế các phương thức template bool Stack::empty() const; enum Error_code {fail, success, overflow, underflow}; Pre: Không có Post: Trả về giá trị true nếu stack hiện tại là rỗng, ngược lại thì trả về false template template class Stack { Error_code Stack::push(const Entry &item); public: Pre: Không có Post: Nếu stack hiện tại không ñầy, item sẽ ñược thêm vào ñỉnh của stack. Stack(); //constructor Ngược lại trả về giá trị overflow của kiểu Error_code và stack không ñổi. bool empty() const; //kiểm tra rỗng Error_code push(const Entry &item); //ñẩy item vào template Error_code Stack::pop() const; Error_code pop(); //bỏ phần tử trên ñỉnh Pre: Không có Error_code top(Entry &item); //lấy giá trị trên ñỉnh Post: Nếu stack hiện tại không rỗng, ñỉnh của stack hiện tại sẽ bị hủy bỏ. //khai báo một số phương thức cần thiết khác Ngược lại trả về giá trị underflow của kiểu Error_code và stack không ñổi. private: template //khai báo dữ liệu và hàm phụ trợ chỗ này Error_code Stack::top(Entry &item) const; }; Pre: Không có Post: Nếu stack hiện tại không rỗng, ñỉnh của stack hiện tại sẽ ñược chép vào tham biến item. Ngược lại trả về giá trị fail của kiểu Error_code. Hiện thực stack liên tục Khai báo stack liên tục const int maxstack = 10; //small number for testing template class Stack { public: Stack( ); bool empty( ) const; Error_code pop( ); Error_code top(Entry &item) const; Error_code push(const Entry &item); private: int count; Entry entry[maxstack]; };
ðẩy một phần tử vào stack Bỏ phần tử trên ñỉnh stack • Giải thuật: • Giải thuật: 1. Nếu còn chỗ trống trong stack 1. Nếu còn phần tử trong stack 1.1. Tăng vị trí ñỉnh lên 1 1.1. Giảm vị trí ñỉnh ñi 1 1.2. Chứa giá trị vào vị trí ñỉnh của stack 1.2. Giảm số phần tử ñi 1 1.3. Tăng số phần tử lên 1 top 7 7 top 5 5 1 count=2 count=3 1 count=3 count=2 Thêm/Bỏ phần tử - Mã C++ Lấy giá trị trên ñỉnh stack template Error_code Stack:: push(const Entry &item) { • Giải thuật: if (count >= maxstack) 1. Nếu còn phần tử trong stack return overflow; else 1.1. Trả về giá trị tại vị trí ñỉnh entry[count++] = item; • Mã C++: return success; } template Error_code Stack:: top(Entry &item) { template if (count == 0) Error_code Stack:: pop() { if (count == 0) return underflow; return underflow; else else item = entry[count - 1]; count--; return success; return success; } }
Ký pháp Ba Lan ñảo Ký pháp Ba Lan ñảo – Thiết kế chức năng • Mô tả bài toán: • Tập lệnh: – Các toán hạng ñược ñọc vào trước và ñẩy vào – ‘?’: ñọc một giá trị rồi ñẩy vào stack stack – Toán tử ‘+’, ‘-’, ‘*’, ‘/’: lấy 2 giá trị trong stack, – Khi ñọc vào toán tử, lấy hai toán hạng ra từ stack, tính toán và ñẩy kết quả vào stack tính toán với toán tử này, rồi ñẩy kết quả vào stack – Toán tử ‘=’: in ñỉnh của stack ra • Thiết kế phần mềm: – ‘q’: kết thúc chương trình – Cần một stack ñể chứa toán hạng – Cần hàm get_command ñể nhận lệnh từ người dùng – Cần hàm do_command ñể thực hiện lệnh Ký pháp Ba Lan ñảo – Ví dụ Ký pháp Ba Lan ñảo - Hàm get_command char get command( ) { Tính toán biểu thức: 3 5 + 2 * = char command; bool waiting = true; cout > command; 3 3 3 8 command = tolower(command); if (command == ‘?’ || command == ‘=‘ || command == ‘+’ || Ban ñầu Toán tử ? Toán tử ? Toán tử + ðẩy 8 vào command == ‘−’|| command == ‘*’ || command == ‘/’ || Nhập vào 3 Nhập vào 5 Lấy ra 5 và 3 command == ‘q’) waiting = false; Tính 3 + 5 => 8 else { cout
Ký pháp Ba Lan ñảo - Giải thuật tính toán Ký pháp Ba Lan ñảo - Toán tử cộng Algorithm Op_process if (numbers.top(p) == underflow) Input: toán tử op, stack chứa các toán hạng cout
4. Queue Queue trừu tượng • Một queue là một cấu trúc dữ liệu mà các phép toán • Một queue kiểu T: thực hiện ở 2 ñỉnh, một ñỉnh gọi là ñầu hàng, một – Một dãy hữu hạn kiểu T ñỉnh gọi là cuối hàng. – Một số tác vụ: • Phần tử vào trước sẽ ra trước – FIFO (First In First • 1. Khởi tạo queue rỗng (create) Out) • 2. Kiểm tra rỗng (empty) • 3. Thêm một giá trị vào cuối của queue (append) • 4. Bỏ giá trị ñang có ở ñầu của queue (serve) • 5. Lấy giá trị ở ñầu của queue, queue không ñổi (retrieve) Thiết kế queue Thiết kế các phương thức template bool Queue::empty() const; enum Error_code {fail, success, overflow, underflow}; Pre: Không có Post: Trả về giá trị true nếu queue hiện tại là rỗng, ngược lại thì trả về false template template class Queue { Error_code Queue::append(const Entry &item); public: Pre: Không có Queue(); //constructor Post: Nếu queue hiện tại không ñầy, item sẽ ñược thêm vào cuối của queue. Ngược lại trả về giá trị overflow của kiểu Error_code và queue không ñổi. bool empty() const; //kiểm tra rỗng Error_code append(const Entry &item); //ñẩy item vào template Error_code serve(); //bỏ 1 phần tử ở ñầu Error_code Queue::serve() const; Pre: Không có Error_code retrieve(Entry &item); //lấy giá trị ở ñầu Post: Nếu queue hiện tại không rỗng, ñầu của queue hiện tại sẽ bị hủy bỏ. //khai báo một số phương thức cần thiết khác Ngược lại trả về giá trị underflow của kiểu Error_code và queue không ñổi. private: template //khai báo dữ liệu và hàm phụ trợ chỗ này Error_code Queue::retrieve(Entry &item) const; }; Pre: Không có Post: Nếu queue hiện tại không rỗng, ñầu của queue hiện tại sẽ ñược chép vào tham biến item. Ngược lại trả về giá trị underflow của kiểu Error_code.
Mở rộng queue Tính thừa hưởng • Có thêm các tác vụ: • Dùng tính thừa hưởng: – Kiểm tra ñầy (full) – Extended_queue có ñầy ñủ các thành phần của Queue – Tính kích thước (size) – Giải phóng queue (clear) – Thêm vào ñó các thành phần riêng của mình – Lấy giá trị ở ñầu và bỏ ra khỏi queue (serve_and_retrieve) • Mã C++: template class Extended_queue: public Queue { public: bool full( ) const; Có các khả năng public, int size( ) const; protected, private void clear( ); Error_code serve_and_retrieve(Entry &item); }; Queue liên tục Queue là array vòng (circular array) • Dùng một array: Có xu hướng dời về cuối array • Hai cách hiện thực ñầu tiên: – Khi lấy một phần tử ra thì ñồng thời dời hàng lên một vị trí. A B C D B C D B C D E Ban ñầu Lấy ra 1 phần tử: Thêm vào 1 phần tử dời tất cả về trước – Chỉ dời hàng về ñầu khi cuối hàng không còn chỗ A B C D B C D B C D E Ban ñầu Lấy ra 1 phần tử Thêm vào 1 phần tử: dời tất cả về trước ñể trống chỗ thêm vào
Array vòng với ngôn ngữ C++ ðiều kiện biên của queue vòng • Xem array như là một vòng: – phần tử cuối của array nối với phần tử ñầu của array • Tính toán vị trí kề: – i = ((i + 1) == max) ? 0 : (i + 1); – if ((i + 1) == max) i = 0; else i = i + 1; – i = (i + 1) % max; Một số cách hiện thực queue liên tục Hiện thực queue liên tục • Một array với front là phần tử ñầu và tất cả các phần const int maxqueue = 10; // small value for testing tử sẽ ñược dời lên khi lấy ra một phần tử. template • Một array có hai chỉ mục luôn tăng chỉ ñến phần tử class Queue { ñầu và cuối. public: • Một array vòng có chỉ mục front và rear và một ô Queue( ); bool empty( ) const; luôn trống. Error_code serve( ); • Một array vòng có chỉ mục front và rear và một cờ Error_code append(const Entry &item); (flag) cho biết queue là ñầy (rỗng) chưa. Error_code retrieve(Entry &item) const; protected: • Một array vòng với chỉ mục front và rear có các giá int count; trị ñặc biệt cho biết queue ñang rỗng. int front, rear; Entry entry[maxqueue]; • Một array vòng với chỉ mục front và rear và một số chứa }; số phần tử của queue.
Khởi tạo và kiểm tra rỗng Thêm một giá trị vào queue • Khởi tạo: • Giải thuật: template 1. Nếu hàng ñầy Queue::Queue( ) { 1.1. Báo lỗi overflow count = 0; 2. Tính toán vị trí cuối mới theo array vòng rear = maxqueue − 1; 3. Gán giá trị vào vị trí cuối mới này front = 0; 4. Tăng số phần tử lên 1 } 4. Báo success • Kiểm tra rỗng: Dùng biến count ñể front rear biết số phần tử template trong queue bool Queue::empty( ) const { A B C D return count == 0; } Loại một giá trị khỏi queue Thêm/loại một giá trị – Mã C++ • Giải thuật: template Error_code Queue::append(const Entry &item) { 1. Nếu hàng rỗng if (count >= maxqueue) return overflow; 1.1. Báo lỗi underflow count++; 2. Tính toán vị trí ñầu mới theo array vòng rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1); 3. Giảm số phần tử ñi 1 entry[rear] = item; return success; 3. Báo success } template Error_code Queue::serve() { front rear if (count
Ứng dụng: Giả lập phi trường Giả lập phi trường – Hàng ñợi • Mô tả: enum Runway_activity {idle, land, takeoff}; – 1. Sử dụng hàng ñợi runway cho việc cất và hạ cánh. class Runway { – 2. Một máy bay có thể cất hoặc hạ cánh trong một ñơn vị public: thời gian. Runway(int limit); Error_code can_land(const Plane &current); – 3. Tại một thời ñiểm, số máy bay ñến là ngẫu nhiên. Error_code can_depart(const Plane &current); – 4. Máy bay hạ cánh ñược ưu tiên trước máy bay cất cánh. Runway_activity activity(int time, Plane &moving); void shut_down(int time) const; – 5. Các máy bay chờ cất/hạ cánh ñược chứa vào các hàng private: ñợi tương ứng và với số lượng giới hạn. Extended queue landing; Extended queue takeoff; int queue_limit; … }; Giả lập phi trường – Hạ cánh Giả lập phi trường – Xử lý Error_code Runway :: can_land(const Plane &current) { Runway_activity Runway::activity(int time, Plane &moving) { Error_code result; Runway_activity in_progress; if (landing.size( ) < queue_limit) if (!landing.empty( )) { result = landing.append(current); landing.retrieve(moving); else in_progress = land; result = fail; landing.serve( ); num_land_requests++; } else if (!takeoff.empty( )) { if (result != success) takeoff.retrieve(moving); num_land_refused++; in_progress = takeoff; else takeoff.serve( ); num_land_accepted++; } else return result; in_progress = idle; } return in_progress; }
Giả lập phi trường – Giả lập Câu hỏi và thảo luận for (int current_time = 0; current_time < end_time; current_time++) { int number_arrivals = variable.poisson(arrival_rate); for (int i = 0; i < number_arrivals; i++) { Plane current_plane(flight_number++, current_time, arriving); if (small_airport.can_land(current_plane) != success) current_plane.refuse( ); } int number_departures = variable.poisson(departure_rate); for (int j = 0; j < number_departures; j++) { Plane current_plane(flight_number++, current_time, departing); if (small_airport.can_depart(current_plane) != success) current_plane.refuse( ); } Plane moving_plane; switch (small_airport.activity(current_time, moving_plane)) { case land: moving_plane.land(current_time); break; case takeoff: moving_plane.fly(current_time); break; case idle: run_idle(current_time); } } 66