Mảng và xâu ký tự

Chia sẻ: Thanhtung Vo | Ngày: | Loại File: PPT | Số trang:39

Thêm vào BST

Báo xấu

302
lượt xem 97
download

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

Tập các phần tử thuộc cùng một kiểu dữ liệu, Được sắp xếp liên tục trong bộ nhớ kích thước là cố định Có thể đánh chỉ số và truy cập theo thứ tự ngẫu nhiên C/C++: chỉ số luôn bắt đầu từ 0. Có thể truyền mảng là tham số cho một hàm, Như là tham số biến, Hàm cần phải biết kích thước của mảng thông qua một tham số phụ thông qua giá trị kết thúc mảng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Mảng và xâu ký tự

Mảng và xâu ký tự
Nội dung  Mảng  khai báo  cấu trúc, thao tác  Xâu ký tự  tạoxâu, nhập, xuất  một số hàm xâu  Một số thuật toán sắp xếp và tìm kiếm Nguyễn Việt Hà Mảng và xâu 2
Tài liệu tham khảo  C++ How to program, Chapter 7  The C programming language, Chap. 1.6, 1.9, Chap. 5 Nguyễn Việt Hà Mảng và xâu 3
Mảng  Tập các phần tử thuộc cùng một kiểu dữ liệu  Được sắp xếp liên tục trong bộ nhớ  kích thước là cố định  Có thể đánh chỉ số và truy cập theo thứ tự ngẫu nhiên  C/C++: chỉ số luôn bắt đầu từ 0 Nguyễn Việt Hà Mảng và xâu 4
Ví dụ int main() { int c[12]; for (int i=0; i> c[i]; } } Nguyễn Việt Hà Mảng và xâu 5
Nguyễn Việt Hà Mảng và xâu 6
Khai báo mảng int main() { int a[12]; int b[] = {2, 3, 5, 7}; int c[5] = {2, 4, 8, 16}; int d[2] = {1, 2, 3}; // compile error int m[5], i; … } Nguyễn Việt Hà Mảng và xâu 7
Kích thước mảng không cần biết trước int main() { int n, max = 0; cin >> n; int a[n]; for (int i=0; i> a[i]; if (a[max] < a[i]) max = i; } if (n > 0) cout
Mảng là tham số  Có thể truyền mảng là tham số cho một hàm  Như là tham số biến  Hàm cần phải biết kích thước của mảng  thông qua một tham số phụ  thông qua giá trị kết thúc mảng Nguyễn Việt Hà Mảng và xâu 9
Ví dụ: copy mảng void arrayCopy(int a[], int b[], int size) { for (int i=0; i
int linearSearch(int, int [], int); int main() { int a[100], key; … cin >> key; cout
Bài tập  Viết các hàm tính giá trị lớn nhất, giá trị nhỏ nhất, giá trị trung bình của một mảng số nguyên. Nguyễn Việt Hà Mảng và xâu 12
Mảng nhiều chiều int a[8][8]; int b[2][3] = { {1, 2, 4}, {2, 3, 5} }; for (int i=0; i
Sắp xếp và tìm kiếm  Một trong các công việc chính của các HTTT  Sắp xếp để tìm kiếm hiệu quả, vd. từ điển  Sắp xếp  đổichỗ các phần tử tạo ra một mảng có thứ tự  sắp xếp chọn, chèn, nổi bọt, nhanh, trộn,…  Tìm kiếm  tìmkiếm nhị phân (binary search)  sử dụng thuật toán băm (hashing) Nguyễn Việt Hà Mảng và xâu 14
Sắp xếp chọn (selection sort)  Tìm (chọn) phần tử nhỏ nhất, đổi lên vị trí đầu tiên  Trong số phần tử còn lại, tìm phần tử nhỏ nhất, đổi lên vị trí thứ 2  Lặp lại cho đến hết Nguyễn Việt Hà Mảng và xâu 15
6 8 7 5 2 1 4 3 1 8 7 5 2 6 4 3 1 2 7 5 8 6 4 3 1 2 3 5 8 6 4 7 1 2 3 4 8 6 5 7 1 2 3 4 5 6 8 7 1 2 3 4 5 6 8 7 1 2 3 4 5 6 7 8 Nguyễn Việt Hà Mảng và xâu 16
Sắp xếp chọn: void selectionSort(int a[], int size) { int i, j, k, tmp; for (i=0; i
Sắp xếp chèn (insertion sort)  Giả sử dãy k phần tử đầu đã sắp xếp  dãy 1 phần tử đầu tiên hiển nhiên là đã có thứ tự  Xét phần tử tiếp theo, tìm cách chèn nó vào vị trí thích hợp (dịch chuyển các phần tử lớn hơn lùi lại một vị trí)  Như vậy k+1 phần tử đã có thứ tự, xét tiếp phần tử tiếp theo,… Nguyễn Việt Hà Mảng và xâu 18
6 8 7 5 2 1 4 3 6 8 7 5 2 1 4 3 6 8 7 5 2 1 4 3 6 8 5 2 1 4 3 6 8 5 2 1 4 3 6 7 8 5 2 1 4 3 6 7 8 5 2 1 4 3 6 7 8 2 1 4 3 6 7 8 2 1 4 3 5 6 7 8 2 1 4 3 Nguyễn Việt Hà Mảng và xâu 19
Sắp xếp nổi bọt (bubble sort) Tuần tự xét các phần tử từ 2 đến n, đối với phần tử thứ k:  So sánh nó với phần tử trước đó, nếu nó nhỏ hơn thì đổi chỗ, cứ như vậy đến khi phần tử này không đổi chỗ được nữa (không nổi lên được nữa). Nguyễn Việt Hà Mảng và xâu 20