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

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.
Nội dung trích xuất từ tài liệu:
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 Ic) 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ầ ...