Mảng và dánh sách

Khái niệm

Mảng là một tập hợp có thứ tự gồm một số cố định các phần tử. Không có phép bổ sung phần tử hoặc loại bỏ phần tử được thực hiện.

Các phép toán thao tác trên mảng bao gồm : phép tạo lập (create) mảng, phép tìm kiếm (retrieve) một phần tử của mảng, phép lưu trữ (store) một phần tử của mảng.

Các phần tử của mảng được đặc trưng bởi chỉ số (index) thể hiện thứ tự của các phần tử đó trong mảng.

Mảng bao gồm các loại:

+ Mảng một chiều: Mảng mà mỗi phần tử a_i của nó ứng với một chỉ số i.

Ví dụ : Véc tơ a[i] trong đó 0 = 1 . . n cho biết véc tơ là mảng một chiều gồm có n phần tử.

Khai báo : kiểu phần tử A[0...n]

A: Tên biến mảng; Kiểu phần tử: Chỉ kiểu của các phần tử mảng (integer, real, . . .)

+ Mảng hai chiều: Là mảng mà mỗi phần tử a_ij của nó ứng với hai chỉ số i và j

Ví dụ : Ma trận A[i],[j] là mảng 2 chiều có i là chỉ số hàng của ma trận và j là chỉ số cột của ma trận.

i = 0 . . n; j = 0 . . m

n: Số hàng của ma trận; m : số cột của ma trận.

Khai báo : kiểu phần tử A[n][m];

+ Mảng n chiều : Tương tự như­ mảng 2 chiều.

Cấu trúc lưu trữ của mảng.

Cấu trúc dữ liệu đơn giản nhất dùng địa chỉ tính được để thực hiện lưu trữ và tìm kiếm phần tử, là mảng một chiều hay véc tơ.

Thông thư­ờng thì một số từ máy sẽ được dành ra để lưu trữ các phần tử của mảng. Cách lưu trữ này được gọi là cách lưu trữ kế tiếp (sequential storage allocation).

Trường hợp một mảng một chiều hay véc tơ có n phần tử của nó có thể lưu trữ được trong một từ máy thì cần phải dành cho nó n từ máy kế tiếp nhau. Do kích thước của véc tơ đã được xác định nên không gian nhớ dành ra cũng được ấn định trước.

Véc tơ A có n phần tử, nếu mỗi phần tử a_i (0 ≤ i ≤ n) chiếm c từ máy thì nó sẽ được lưu trữ trong cn từ máy kế tiếp như­ hình vẽ:

L₀ – Địa chỉ của phần tử a₀

Địa chỉ của a_i được tính bởi công thức:

Loc(a_i) = L₀ + c * i

trong đó :

L₀ được gọi là địa chỉ gốc - đó là địa chỉ từ máy đầu tiên trong miền nhớ kế tiếp dành để lưu trữ véc tơ (gọi là véc tơ lưu trữ).

f(i) = c * i gọi là hàm địa chỉ (address function)

Đối với mảng nhiều chiều việc lưu trữ cũng tương tự như­ vậy nghĩa là vẫn sử dụng một véc tơ lưu trữ kế tiếp như­ trên.

a01

a11

. . .

aij

. . .

anm

Giả sử mỗi phần tử trong ma trận n hàng m cột (mảng nhiều chiều) chiếm một từ máy thì địa chỉ của a_ij sẽ được tính bởi công thức tổng quát như­ sau:

Loc(a_ij) = L₀ + j * n + i { theo thứ tự ­ưu tiên cột (column major order }

Cũng với ma trận n hàng, m cột cách lưu tr­ữ theo thứ tự ­ưu tiên hàng (row major order) thì công thức tính địa chỉ sẽ là:

Loc(a_ij) = L₀ + i * m + j

+ Trường hợp cận dưới của chỉ số không phải là 1, nghĩa là ứng với a_ij thì b₁ ≤ i ≤ u₁, b₂ ≤ j ≤ u₂ thì ta sẽ có công thức tính địa chỉ như­ sau:

Loc(a_ij) = L₀ + (i - b₁) * (u₂ - b₂ + 1) + (j - b₂)

vì mỗi hàng có (u₂ - b₂ + 1) phần tử.

Ví dụ : Xét mảng ba chiều B có các phần tử b_ijk với 1 ≤ i ≤ 2;

1 ≤ j ≤ 3; 1 ≤ k ≤ 4; được lưu trữ theo thứ tự ­ưu tiên hàng thì các phần tử của nó sẽ được sắp đặt kế tiếp như­ sau:

b₁₁₁, b₁₁₂, b₁₁₃, b₁₁₄, b₁₂₁, b₁₂₂, b₁₂₃, b₁₂₄, b₁₃₁, b₁₃₂, b₁₃₃, b₁₃₄, b₂₁₁, b₂₁₂, b₂₁₃, b₂₁₄, b₂₂₁, b₂₂₂, b₂₂₃, b₂₂₄, b₂₃₁, b₂₃₂, b₂₃₃, b₂₃₄.

Công thức tính địa chỉ sẽ là :

Loc(a_ijk) = L₀ + (i - 1) *12 + (j - 1) * 4 + (k - 1)

VD Loc(b₂₂₃) = L₀ + 22.

Xét trường hợp tổng quát với mảng A n chiều mà các phần tử là :

A[s₁, s₂, . . ., s_n] trong đó b_i ≤ s_i ≤ u_i ( i = 1, 2, . . ., n), ứng với thứ tự ­ưu tiên hàng ta có:

đặc biệt p_n = 1.

Chú ý :

1. Khi mảng được lưu trữ kế tiếp thì việc truy nhập vào phần tử của mảng được thực hiện trực tiếp dựa vào địa chỉ tính được nên tốc độ nhanh và đồng đều đối với mọi phần tử.
2. Mặc dầu có rất nhiều ứng dụng ở đó mảng có thể được sử dụng để thể hiện mối quan hệ về cấu trúc giữa các phần tử dữ liệu, như­ng không phải không có những trường hợp mà mảng cũng lộ rõ những như­ợc điểm của nó.

Ví dụ : Xét bài toán tính đa thức của x,y chẳng hạn cộng hai đa thức sau:

(3x² - xy + y² + 2y - x)

+ (x² + 4xy - y² +2x)

= (4x² + 3xy + 2y + x)

Ta biết khi thực hiện cộng 2 đa thức ta phải phân biệt được từng số hạng, phân biệt được các biến, hệ số và số mũ.

Để biểu diễn được một đa thức với 2 biến x,y ta có thể dùng ma trận: hệ số của số hạng xⁱy^j sẽ được lưu trữ ở phần tử có hàng i cột j của ma trận. Nếu ta hạn chế kích thước của ma trận là n × n thì số mũ cao nhất của x,y chỉ xử lý được với đa thức bậc n-1 thôi.

Với cách biểu diễn kiểu này thì việc thực hiện phép cộng hai đa thức chỉ là cộng ma trận mà thôi. Như­ng nó có một số hạn chế : số mũ của đa thức bị hạn chế bởi kích thước của ma trận do đó lớp các đa thức được xử lý bị giới hạn trong một phạm vi hẹp. Mặt khác ma trận biểu diễn có nhiều phần tử bằng 0, dẫn đến sự lãng phí bộ nhớ.

Lưu trữ mảng trong ngôn ngữ lập trình C

Hay như để lưu trữ các từ khóa của ngôn ngữ lập trình C, ta cũng dùng đến một mảng để lưu trữ chúng.

Ví dụ 1: Viết chương trình cho phép nhập 2 ma trận a, b có m dòng n cột, thực hiện phép toán cộng hai ma trận a,b và in ma trận kết quả lên màn hình.

Trong ví dụ này, ta sẽ sử dụng hàm để làm ngắn gọn hơn chương trình của ta. Ta sẽ viết các hàm: nhập 1 ma trận từ bàn phím, hiển thị ma trận lên màn hình, cộng 2 ma trận.

#include<conio.h>

#include<stdio.h>

void Nhap(int a[][10],int M,int N)

{

int i,j;

for(i=0;i<M;i++)

for(j=0; j<N; j++){

printf("Phan tu o dong %d cot %d: ",i,j);

scanf("%d",&a[i][j]);

}

}

void InMaTran(int a[][10], int M, int N)

{

int i,j;

for(i=0;i<M;i++){

for(j=0; j< N; j++)

printf("%d ",a[i][j]);

printf(" ");

}

}

/* Cong 2 ma tran A & B ket qua la ma tran C*/

void CongMaTran(int a[][10],int b[][10],int M,int N,int c[][10]){

int i,j;

for(i=0;i<M;i++)

for(j=0; j<N; j++)

c[i][j]=a[i][j]+b[i][j];

}

int main()

{

int a[10][10], b[10][10], M, N;

int c[10][10];/* Ma tran tong*/

printf("So dong M= "); scanf("%d",&M);

printf("So cot M= "); scanf("%d",&N);

printf("Nhap ma tran A ");

Nhap(a,M,N);

printf("Nhap ma tran B ");

Nhap(b,M,N);

printf("Ma tran A: ");

InMaTran(a,M,N);

printf("Ma tran B: ");

InMaTran(b,M,N);

CongMaTran(a,b,M,N,c);

printf("Ma tran tong C: ");

InMaTran(c,M,N);

getch();

return 0;

}

Lưu trữ mảng trong ngôn ngữ lập trình C#

Array là một cấu trúc dữ liệu cấu tạo bởi một số biến được gọi là những phần tử mảng. Tất cả các phần tử này đều thuộc một kiểu dữ liệu. Bạn có thể truy xuất phần tử thông qua chỉ số (index). Chỉ số bắt đầu bằng zero.

Có nhiều loại mảng (array): mảng một chiều, mảng nhiều chiều.

 Cú pháp :

              type[ ] array-name;

 thí dụ: int[] myIntegers; // mảng kiểu số nguyên string[] myString ; // mảng kiểu chuổi chữ Bạn khai báo mảng có chiều dài xác định với từ khoá new như sau: // Create a new array of 32 ints int[] myIntegers = new int[32]; integers[0] = 35;// phần tử đầu tiên có giá trị 35 integers[31] = 432;// phần tử 32 có giá trị 432 Bạn cũng có thể khai báo như sau:

int[] integers; integers = new int[32]; string[] myArray = {"first element", "second element", "third element"};

Làm việc với mảng (Working with Arrays)

Ta có thể tìm được chiều dài của mảng sau nhờ vào thuộc tính Length thí dụ sau : int arrayLength = integers.Length

Nếu các thành phần của mảng là kiểu định nghĩa trước (predefined types), ta có thể sắp xếp tăng dần vào phương thức gọi là static Array.Sort() method: Array.Sort(myArray);

Cuối cùng chúng ta có thể đảo ngược mảng đã có nhờ vào the static Reverse() method: Array.Reverse(myArray); string[] artists = {"Leonardo", "Monet", "Van Gogh", "Klee"}; Array.Sort(artists); Array.Reverse(artists); foreach (string name in artists) {     Console.WriteLine(name); }

Mảng nhiều chiều (Multidimensional Arrays in C#)

Cú pháp :

type[,] array-name;

              }