Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 2: Mảng - Ngô Hữu Phước

Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com Cấu trúc dữ liệu và giải thuật Bài 2. MẢNG @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University1 Bài 2. Mảng Nộ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 Hashing @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University2 2.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. @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University3 2.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. @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University4 2.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). @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University5 2.2. Biểu diễn mảng 1 chiều (1D) (2/3) @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University6 2.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. @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University7 2.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. @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University8 2.3. Biểu diễn mảng 2 chiều (2D) (2/5) @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University9 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) @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University10 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. @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University11 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) @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University12 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 các thành phần của danh sách. #include #include void read(int *,int); void dis(int *,int); void main() { int a[5],i,sum=0; printf("Nhap cac phan tu cho mang \n"); read(a,5); printf("Gia tri cua cac phan tu trong mang \n"); dis(a,5); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University13 void read(int c[], int i) { int j; for(j=0;j<i;j++) scanf("%d",&c[j]); fflush(stdin); } void dis(int d[],int i) { int j; for(j=0;j<i;j++) printf("%d ",d[j]); printf("\n"); } 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. #include #include void read(int *,int); void dis(int *,int); void main() { int a[5],i,sum=0; printf("Nhap gia tri cho mang \n"); read(a,5); printf("Cac gia tri da nhap \n"); dis(a,5); for(i=0;i<5;i++) sum+=a[i]; printf("Tong cac phan tu trong mang %d\n",sum); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University14 void read(int c[],int i) { int j; for(j=0;j<i;j++) scanf("%d",&c[j]); fflush(stdin); } void dis(int d[],int i) { int j; for(j=0;j<i;j++) printf("%d ",d[j]); printf("\n"); } 2.4. Một số ví dụ về mảng (3/14) Ví dụ 3: Tính tổng trong của 2 mảng. #include #include void read(int *,int); void dis(int *,int); void add(int *,int *,int * ,int); void main() { int a[5],b[5],c[5]; printf("Nhap gia tri cho mang thu nhat \n"); read(a,5); printf("Cac gia tri da nhap cua mang 1 \n"); dis(a,5); printf("Nhap gia tri cho mang thu hai \n"); read(b,5); printf("Cac gia tri da nhap cua mang 2 \n"); dis(b,5); add(a,b,c,5); printf("Gia tri cua mang ket qua \n"); dis(c,5); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University15 void add(int a[],int b[],int c[],int n) { int i; for(i=0;i<n;i++) c[i]=a[i]+b[i]; } void read(int c[],int n) { int i; for(i=0;i<n;i++) scanf("%d",&c[i]); fflush(stdin); } void dis(int d[],int n) { int i; for(i=0;i<n;i++) printf("%d ",d[i]); printf("\n"); } 2.4. Một số ví dụ về mảng (4/14) Ví dụ 4: Đảo danh sách. #include #include void read(int *,int); void display(int *,int); void inverse(int *,int); void main() { int a[5]; read(a,5); display(a,5); inverse(a,5); display(a,5); getch(); } void read(int c[],int n) { int i; printf("Nhap cac phan tu cho mang \n"); for(i=0;i<n;i++) scanf("%d",&c[i]); fflush(stdin); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University16 void display(int d[],int n) { int i; printf("Gia tri cac phan tu trong mang \n"); for(i=0;i<n;i++) printf("%d ",d[i]); printf("\n"); } void inverse(int inver_a[],int n) { int i,temp; for(i=0;i<(n/2);i++) { temp=inver_a[i]; inver_a[i]=inver_a[n-1-i]; inver_a[n-1-i]=temp; } } 2.4. Một số ví dụ về mảng (5/14) Ví dụ 5: Nối 2 mảng đã sắp xếp (1/3) #include #include void read(int *,int); void display(int *,int); void sort(int *,int); void merge(int *,int *,int *,int,int); void main() { int a[5],b[5],c[10]; printf("Nhap cac phan tu cua mang 1th \n"); read(a,5); printf("Cac phan tu da nhap cua mang 1th \n"); display(a,5); printf("Nhap cac phan tu cua mang 2rd \n"); read(b,5); printf("Cac phan tu da nhap cua mang 2rd \n"); display(b,5); @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University17 sort(a,5); printf("Mang thu nhat duoc sap:\n"); display(a,5); sort(b,5); printf("Mang thu hai duoc sap:\n"); display(b,5); merge(a,b,c,5,5); // noi hai mang printf("Cac phan tu trong mang moi, sau khi noi \n"); display(c,10); getch(); } 2.4. Một số ví dụ về mảng (6/14) Ví dụ 5: Nối 2 mảng đã sắp xếp (2/3) void read(int c[],int n) { int i; for(i=0;i<n;i++) scanf("%d",&c[i]); fflush(stdin); } void display(int d[],int n) { int i; for(i=0;i<n;i++) printf("%d ",d[i]); printf("\n"); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University18 void sort(int arr[] ,int n) { int temp; int i,j; for(i=0;i<n;i++) { for(j=0;j<n-i-1;j++) { if(arr[j]>arr[j+1]) { temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } } 2.4. Một số ví dụ về mảng (10/14) Ví dụ 5: Nối 2 mảng đã sắp xếp(3/3) void merge(int a[],int b[],int c[],int k1, int k2) { int ptra=0,ptrb=0,ptrc=0; while(ptra<k1 && ptrb<k2) { if(a[ptra] < b[ptrb]) { c[ptrc]=a[ptra]; ptra++; } else { c[ptrc]=b[ptrb]; ptrb++; } ptrc++; } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University19 while(ptra<k1) { c[ptrc]=a[ptra]; ptra++;ptrc++; } while(ptrb<k2) { c[ptrc]=b[ptrb]; ptrb++; ptrc++; } } 2.4. Một số ví dụ về mảng (7/14) Ví dụ 6: Tính tích vô hướng của 2 vecto #include #include void read(int *,int); void dis(int *,int); int multi(int *,int *,int); void main() { int a[5],b[5]; int sum=0; printf("Nhap gia tri cho mang 1 \n"); read(a,5); printf("Cac gia tri da nhap cua mang 1 \n"); dis(a,5); printf("Nhap gia tri cho mang 2 \n"); read(b,5); printf("Cac gia tri da nhap cua mang 2 \n"); dis(b,5); sum=multi(a,b,5); printf("Gia tri cua tich vo huong: %d",sum); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University20 void read(int c[],int n) { int i; for(i=0;i<n;i++) scanf("%d",&c[i]); fflush(stdin); } void dis(int d[],int n) { int i; for(i=0;i<n;i++) printf("%d ",d[i]); printf("\n"); } int multi(int a[],int b[],int n) { int i, sum=0; for(i=0;i<n;i++) { sum+=a[i]*b[i]; } return sum; } 2.4. Một số ví dụ về mảng (8/14) Ví dụ 7: Tính khoảng cách Euclide giữa 2 vecto #include #include #include void read(int *,int); void dis(int *,int); float euclide(int *,int *,int); void main() { int a[5],b[5]; printf("Nhap gia tri cho mang 1 \n"); read(a,5); printf("Cac gia tri da nhap cua mang 1 \n"); dis(a,5); printf("Nhap gia tri cho mang 2 \n"); read(b,5); printf("Cac gia tri da nhap cua mang 2 \n"); dis(b,5); printf("Gia tri cua tich vo huong: %f",euclide(a,b,5)); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University21 void read(int c[],int n) { int i; for(i=0;i<n;i++) scanf("%d",&c[i]); fflush(stdin); } void dis(int d[],int n) { int i; for(i=0;i<n;i++) printf("%d ",d[i]); printf("\n"); } float euclide(int a[],int b[],int n) { int i; float e=0.0; for(i=0;i<n;i++) { e+=pow((float)(a[i]-b[i]),2); } return sqrt(e); } 2.4. Một số ví dụ về mảng (9/14) Ví dụ 8: Tính tích chập giữa 2 vecto #include #include #include void read(int *,int); void display(int *,int); void convolution(int *,int *,int *,int, int); void main() { int a[5],b[3],c[5]; printf("Nhap gia tri cho mang 1 \n"); read(a,5); printf("Cac gia tri da nhap cua mang 1 \n"); display(a,5); printf("Nhap gia tri cho mang 2 \n"); read(b,3); printf("Cac gia tri da nhap cua mang 2 \n"); display(b,3); convolution(a,b,c,5,3); printf("Gia tri cua tich chap \n"); display(c,5); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University22 void read(int c[],int n) { int i; for(i=0;i<n;i++) scanf("%d",&c[i]); fflush(stdin); } void display(int d[],int n) { int i; for(i=0;i<n;i++) printf("%d ",d[i]); printf("\n"); } void convolution(int a[],int b[],int c[],int k1, int k2) { int i,j; for(i=0;i<k1;i++) { c[i]=0; for(j=i-k2+1;j<=i;j++) if(j>=0) c[i]+=a[j]*b[j+k2-1-i]; } } 2.4. Một số ví dụ về mảng (11/14) Ví dụ 9: Chuyển vị ma trận (1/2) #include #include #define ROW 3 #define COL 3 void read(int a[][COL],int,int); void display(int a[][COL],int,int); void trans(int a[][COL],int,int); void main() { int a[ROW][COL]; read(a,ROW,COL); printf("\nMa tran da nhap \n"); display(a,ROW,COL); trans(a,ROW,COL); printf("Ma tran sau khi da chuyen vi\n"); display(a,ROW,COL); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University23 void read(int c[ROW][COL] ,int row ,int column) { int i,j; printf("Nhap ma tran \n"); for(i=0;i<row;i++) for(j=0;j<column;j++) scanf("%d",&c[i][j]); fflush(stdin); } void display(int d[ROW][COL],int row,int column) { int i,j; for(i=0;i<row;i++) { for(j=0;j<column;j++) printf("%d ",d[i][j]); printf("\n"); } } 2.4. Một số ví dụ về mảng (12/14) Ví dụ 9: Chuyển vị ma trận (2/2) void trans(int mat[][COL],int row ,int column) { int i,j,temp; for(i=0;i<row;i++) for(j=i+1;j<column;j++) { temp=mat[i][j]; mat[i][j]=mat[j][i]; mat[j][i]=temp; } } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University24 2.4. Một số ví dụ về mảng (13/14) Ví dụ 10: Tìm điểm yên ngựa trong ma trận (1/2) #include "stdio.h" #include "conio.h" #include "stdlib.h" #define ROW 3 #define COL 3 void read(int c[][COL],int,int); void display(int d[][COL],int,int); int sadd_pt(int a[][COL],int,int,int *,int*); void main() { int i,a[ROW][COL],m=0,n=0; read(a,ROW,COL); printf("\nMa tran nhap vao \n"); display(a,ROW,COL); i=sadd_pt(a,ROW,COL,&m,&n); printf("Diem yen ngua %d tai hang : %d cot : %d\n",i,m+1,n+1); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University25 void read(int c[][COL] ,int row ,int column) { int i,j; printf("Nhap ma tran \n"); for(i=0;i<row;i++) for(j=0;j<column;j++) scanf("%d",&c[i][j]); fflush(stdin); } void display(int d[][COL],int row,int column) { int i,j; for(i=0;i<row;i++) { for(j=0;j<column;j++) printf("\t%d",d[i][j]); printf("\n"); } } 2.4. Một số ví dụ về mảng (14/14) Ví dụ 10: Tìm điểm yên ngựa trong ma trận (1/2) int sadd_pt(int mat[][COL],int row ,int column,int *r,int *c) { int min,i=0,j,m,n,p=0; while(i<row) { min=mat[i][0]; m=i; p=0; n=0; for(j=0;j<column;j++) { if(mat[i][j]<min) { min=mat[i][j]; n=j; } } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University26/26 for(j=0;j<row;j++) if(min>=mat[j][n]) p++; if(p==COL) { *r=m; *c=n; return(min); } i++; } printf("Khong co diem yen ngua\n"); getch(); exit(0); }