Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 2: Mảng

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 2: Mảng" trình bày khái niệm về mảng, biểu diễn mảng 1 chiều, biểu diễn mảng 2 chiều, các phép toán trên mảng 1D, các phép toán trên mảng 2D.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 2: Mảng Cấu trúc dữ liệu và giải thuật Bài 2. MẢNG Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com1 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical UniversityBài 2. MảngNội dung: 1. Khái niệm về mảng. 2. Biểu diễn mảng 1 chiều (1D). 3. Biểu diễn mảng 2 chiều (2D). 4. Các phép toán trên mảng 1D. 5. Các phép toán trên mảng 2D.Tham khảo: Deshpande Kakde – C and data structures Chapter 18 – Arrays, Searching, and Sorting Chapter 23 – Problem in Arrays, Searching, Sorting, and Hashing2 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University2.1. Khái niệm về mảng (1/2) Mảng là cấu trúc dữ liệu do người dùng định nghĩa, có kích thước cố định và đồng nhất.  Theo tính chất đồng nhất, các thành phần có cùng kiểu, được gọi là element type hoặc base type.  Theo tính chất có kích thước cố định, ta không thể thay đổi kích thước của mảng khi đang sử dụng. Mảng có thể coi là cấu trúc dữ liệu cho phép truy cập ngẫu nhiên thông qua chỉ số của chúng.3 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University2.1. Khái niệm về mảng (2/2) Các thành phần của mảng được truy cập thông qua chỉ số, chỉ số là số nguyên để chỉ vị trí của thành phần đó trong mảng. Như vậy, một mảng được hình thành bởi một cặp (value, index); Nếu chỉ số là 1 số, mảng được gọi là mảng 1 chiều. Nếu chỉ số có dạng {i1, i2, i3,….., in}, mảng được gọi là mảng n chiều.4 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University2.2. Biểu diễn mảng 1 chiều (1D) (1/3)• Mảng được thể hiện trong bộ nhớ bằng ánh xạ tuần tự.• Đặc tính cơ bản của ánh xạ tuần tự cho mỗi phần tử của mảng có “khoảng cách” cố định với phần tử đầu của mảng.• Như vậy, nếu phần tử thứ i ánh xạ tới vị trí a thì phần tử thứ (i+1) ánh xạ tới vị trí (a+1).5 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University2.2. Biểu diễn mảng 1 chiều (1D) (2/3)6 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University2.2. Biểu diễn mảng 1 chiều (1D) (3/3) • Địa chỉ của phần tử đầu tiên trong mảng được gọi là địa chỉ cơ sở (base address - LB). • Địa chỉ của phần tử thứ i được xác định: Base address + offset of the ith element from base address trong đó, offset được tính: Offset of the ith element = number of elements before the ith * size of each element. • Nếu LB là lower bound (cận dưới), offset được xác định: offset = (i − LB) * size.7 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University2.3. Biểu diễn mảng 2 chiều (2D) (1/5)• Mảng 2 chiều có thể được hiểu thông qua mảng 1D, trong đó, mỗi phần tử của nó là mảng 1D – Mảng của Mảng.• Mảng 2D có thể xem là 1 cột của các hàng• Cách biểu diễn này được gọi là row-major representation.8 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University2.3. Biểu diễn mảng 2 chiều (2D) (2/5)9 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University 2.3. Biểu diễn mảng 2 chiều (2D) (3/5)  Địa chỉ của phần tử tại hàng i, cột j được xác định: addr(a[i, j]) = ( number of rows placed before ith row * size of a row) + (number of elements placed before the jth element in the ith row * size of element) trong đó:  Number of rows placed before ith row = (i – LB1), với LB1 là lower bound của chiều thứ nhất.  Size of a row = number of elements in a row * a size of element.  Number of elements in a row = (UB2 – LB2+1), với UB2 và LB2 là cận trên và cận dưới của chiều thứ 2.  Như vậy: addr(a[i, j]) = ((i−LB1)*(UB2−LB2+1)*size)+((j−LB2)*size)10 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University 2.3. Biểu diễn mảng 2 chiều (2D) (4/5)  Mảng 2D có thể xem là một hàng các cột.  Cách biểu diễn này được gọi là column- major representation.11 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University 2.3. Biểu diễn mảng 2 chiều (2D) (5/5)  Địa chỉ của phần tử có hàng i, cột j được xác định: addr(a[i, j]) = ( number of columns placed before jth column * size of a column) + (number of elements placed before the ith element in the jth column * size of each element)  Number of columns placed before jth column = (j − LB2), với LB2 là cận dưới của chiều thứ 2.  Size of a column = number of elements in a column * size of element  Number of elements in a column = (UB1 – LB1 + 1), với UB1 và LB1 là cận trên và cận dưới của chiều thứ nhất.  Như vậy: addr(a[i, j]) = ((j − LB2) * (UB1 − LB1+1) * size) + ((i − LB1)*size) hoặc addr(a[i, j]) = ((i−LB1)*(UB2−LB2+1)*size)+((j−LB2)*size)12 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University 2.4. Một số ví dụ về mảng (1/14) Ví dụ 1: Chương trình cho phép truy cập tới void read(int c[], int i) { các thành phần của danh sách. int j; #include for(j=0;j 2.4. Một số ví dụ về mảng (2/14) Ví dụ 2: Tính tổng các phần tử trong mảng. void read(int c[],int i) #include { #include int j; void read(int *,int); void dis(int *,int); for(j=0;j 2.4. Một số ví dụ về mảng (3/14) Ví dụ 3: T ...