"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.
AMBIENT/
Chủ đề:
Nội dung Text: 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.com
1 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 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
2 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 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.
3 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 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.
4 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 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).
5 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 2.2. Biểu diễn mảng 1 chiều (1D) (2/3)
6 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 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.
7 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 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.
8 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 2.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ính tổng trong của 2 mảng. void add(int a[],int b[],int c[],int n) {
#include int i;
#include for(i=0;i
- 2.4. Một số ví dụ về mảng (4/14)
Ví dụ 4: Đảo danh sách. void display(int d[],int n) {
#include int i;
#include printf("Gia tri cac phan tu trong mang \n");
void read(int *,int);
for(i=0;i
- 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) sort(a,5);
#include printf("Mang thu nhat duoc sap:\n");
#include display(a,5);
void read(int *,int);
sort(b,5);
void display(int *,int);
printf("Mang thu hai duoc sap:\n");
void sort(int *,int);
display(b,5);
void merge(int *,int *,int *,int,int);
merge(a,b,c,5,5); // noi hai mang
void main() {
int a[5],b[5],c[10]; printf("Cac phan tu trong mang moi, sau khi noi
\n");
printf("Nhap cac phan tu cua mang 1th \n");
display(c,10);
read(a,5);
getch();
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);
17 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 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 sort(int arr[] ,int n)
void read(int c[],int n) {
{ int temp;
int i;
int i,j;
for(i=0;i
- 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) while(ptra
- 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 void read(int c[],int n) {
#include int i;
#include for(i=0;i
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
