V.2.  Mảng 1 chiều 

V.2.1 - Định nghĩa mảng 

Cú pháp    Ki ểu_mảng   tên_mảng  [ số_phần_tử]; 

Trong đó: 

- Kiểu_mảng:  đây là kiểu của mảng, là tên một kiểu dữ liệu đã tồn tại, có thể là kiểu chuẩn hoặc kiểu dữ liệu do người lập trình định nghĩa .

 - tên_mảng :  là tên của mảng, do người lập trình đặt, theo quy tắc về tên của C. 

- số_phần_tử  : là  hằng (hoặc biểu thức hằng) nguyên, dương là số phần tử của mảng.

 Ví dụ:  int   vector [15]; // tên mảng: vector, có 15 phần tử,

 kiểu int float MT[10], D[20]; // có hai mảng

 kiểu float: MT có 10 phần tử, D có 20 phần tử

  char * s[30];  //  s là mảng có 30 phần tử 

kiểu char * (mảng các con trỏ)

 Khi gặp (dòng lệnh) định nghĩa một mảng, chương trình dịch sẽ cấp phát một vùng nhớ (lên tiếp) cho đủ các phần tử liên tiếp của mảng, 

ví dụ vector[15] sẽ được cấp phát một vùng nhớ có kích thước 15*sizeof(int) =30 byte. 

V.2.2 -  Truy xuất các phần tử

 Cú pháp : tên_mảng [chỉ_số] 

ví dụ vector[1], MT[3], D[0];  chỉ_số là số thứ tự của phần tử trong mảng, các phần tử của mảng được đánh chỉ số bắt đầu từ 0. Với mảng có n phần tử thì các phần tử của nó có chỉ số là 0, 1,..,n-1. 

 ví dụ mảng vector có các phần tử vector[0], vector[1],...,vector[14] 

Lưu ý: Các chương trình dịch của C không bắt lỗi khi người dùng truy xuất phần tử mảng vượt ra ngoài phạm vi của mảng,  tức là có chỉ số nhỏ hơn 0 hoặc  lớn hơn số_phần_tử-1. 

V.2.3 - Khởi tạo giá trị các phần tử mảng một chiều 

 Các phần tử của mảng cũng như các biến đơn, chúng ta có thể  khởi tạo giá trị ban đầu cho chúng trên dòng định nghĩa mảng (gọi là khởi đầu) với cú pháp sau: 

Kiểu_mảng   tên_mảng  [ số_phần_tử ] = {gt_0, gt_1,..,gt_k};

hoặc Kiểu_mảng   tên_mảng  [  ] = {gt_0, gt_1,..,gt_k}; 

 Trong đó các thành phần Kiểu_mảng ,  tên_mảng,   số_phần_tử  như trong phần định nghĩa (V.1).  gt_0,  gt_1,.., gt_k là các giá trị khởi đầu (gọi là bộ khởi đầu) cho các phần tử tương ứng của mảng,  tức là gán tuần tự các giá trị  trong bộ khởi đầu cho các phần tử của mảng từ trái qua phải.  

Trong dạng thứ nhất, số giá trị trong bôn khởi đầu chỉ có thể <= số phần tử của mảng (k ≤ số_phần_tử). Khi đó những phần tử mảng thừa ra (không có giá trị khởi đầu) sẽ tự động được  gán bằng 0 (trong trường hợp mảng số, nếu là con trỏ sẽ là NULL (rỗng) ).

 Ví dụ:    

 int a[3] ={ 1,3,4}; 

  thì giá trị  của a[0] là 1,  a[1] là 3,  a[2] là 4. 

int b[5] ={1,2};   

   thì giá trị của b[0] là 1, b[1] là 2, b[3]=b[4] là 0.    

Trong dạng thứ hai, chúng ta không xác định số phần tử của mảng, trong trường hợp này chương trình biên dịch sẽ tự động xác định kích thước (số phần tử) của mảng theo số giá trị trong bộ khởi đầu.  

Ví dụ:   int a[] ={1,3,4};  

thì a là mảng có 3 phần tử,  giá trị  của a[0] là 1,  a[1] là 3,  a[2] là 4.  

V.2.4 - Một số ví dụ 

 Ví dụ V.1: Chương trình  nhập một mảng A có n phần tử kiểu nguyên , n<=20 nhập từ bàn phím, in các phần tử của mảng theo trật tự xuôi, ngược (theo thứ tự chỉ số). 

Giải: Trong chương trình chúng ta cần định nghĩa một mảng A có 20 phần tử kiểu int. Một biến nguyên n là số phần tử thực sự của A sẽ được nhập. Số nguyên n được nhập từ bàn phím phải thoả mãn 1<=n<=20.  Các phần tử A[i] -1 của A được nhập từ bàn phím tương tự như các biến đơn bằng câu lệnh (hàm)  scanf:  scanf“.  Và được in ra bằng hàm printf, như sau printf “, nếu ta sử dụng vòng lặp với i từ 0 tới n-1 ta được các phần tử theo trật tự xuôi của chỉ số:  for0 printf"; ngược lại các bạn cho chạy theo thứ tự từ n-1 tới 0 chúng sẽ có các phần tử theo số thứ tự ngược for-1 printf";  Chương trình minh hoạ như sau: 

 #include <stdio.h>

 #include <conio.h>

 void main){ <; 

const int max =20;

 int A[max];

int n,i; 

do{

 printf("\nNhap so phan tu mang  = "); 

scanf"; 

}while(n<1 || n>max); //nhập số pt mảng 1<=n<=max    

printf"\nNhapmangco; for0  { printf"A[; 

scanf";  } printf("\nCac phan tu mang theo thu tu xuoi la  \n"); for0 

printf";  printf("\nCac phan tu mang theo thu tu nguoc la  \n"); for-1 

printf"; getch); < các số nguyên, tính và in mảng C = A+B. Giải: Việc nhập 2 mảng A, B cũng tương tự như trong ví dụ trước. Mảng C là tổng của A và B tức là các phần tử C[i] = A[i]+B[i] -1.  

#include <stdio.h>

 #include <conio.h>

 void main){<; 

const int max = 10;

 int A[max], B[max], C[max];

 int n,i; 

do{

 printf("\nNhap so phan tu mang  = "); 

scanf"; }while(n<1 || n>max); //nhập số pt mảng 1<=n<=max

 printf"\nNhapmangAco

; for0 

 {

 printf"A[;

 scanf"; 

 }  

printf"\nNhapmangBco; 

for0 

 { printf"B[; scanf"; 

 }

 // Tính C=A+B

 for0 C[i]= A[i]+B[i]; 

printf("\nCac phan tu mang ket qua C la \n");

 for0 printf";

 getch0 đó là biểu diễn các phần tử đó là một mảng các phần tử. ¾

 Sắp xếp mảng: 

  Bài toán sắp xếp mảng nói chung được  phát biểu như sau: Cho một mảng  có n  phần tử, và k là khoá của mỗi phần tử, các phần tử có thể so sánh với nhau theo khoá k, hãy sắp xếp mảng theo thứ tự tăng (hoặc giảm) của khoá k.  

 Khoá k chúng ta có thể hiểu là một thành phần nào đó của các phần tử như là tuổi của một người, hay điểm trung bình học tập của một sinh viên, hoặc là một tiêu chí nào đó áp dụng cho các phần tử của mảng.  Trong trường hợp đơn giản như các mảng số mà chúng ta sẽ nói trong ví dụ sau đây thì khoá k chính là giá trị của các phần tử.   Hiện nay có nhiều thuật toán để sắp xếp một mảng:

 thuật toán nối bọt, thuật toán đổi chỗ, thuật toán chọn, thuật toán chia đôi,.. 

trong giáo trình này chúng tôi giới thiệu ba thuật toán sắp xếp đơn giản để sắp một mảng A có n phần tử kiểu số nguyên. 

a. Sắp xếp bằng phương pháp nổi bọt

Ý tưởng của phương pháp này là có n phần tử (“bọt nước”) đều có xu hướng nổi lên trên mặt nước, thì phần tử nào nhỏ hơn (‘nhẹ hơn’) sẽ được ưu tiên nổi lên trên. Tức là với mọi cặp phần tử kề nhau nếu phần tử sau (dưới) nhỏ hơn phần tử phía trước thì phần tử nhỏ hơn sẽ nổi lên trên, phần tử nặng hơn sẽ chìm xuống dưới.  

b. Sắp xếp bằng phương pháp đổi chỗ trực tiếp

Ý tưởng của phương pháp này cũng rất đơn giản là: giả sử các phần tử đầu mảng A[0], A[1],.., A[i-1] đã được sắp đúng vị trí tức là đã có:                A[0] <=A[1] <=,..<A[i-1] <= min{A[i],A[i+1],..,A[n-1]} (i=0,1,..)  Công việc tiếp theo là sắp các phần tử còn lại vào đúng vị trí của nó. Các bạn thấy vị trí thứ i là vị trí đầu tiên chưa được sắp, nếu được sắp thì A[i] phải có giá trị nhỏ nhất trong các phần tử còn lại đó {A[i],A[i+1],..,A[n-1]}, vậy chúng ta sẽ duyệt các phần tử mảng trong phần còn lại  A[j] với j =i+1 tới n-1, nếu A[j] < A[i] thì chúng ta đổi chỗ A[i] với A[j]. Như vậy phần tử i đã được xếp đúng vị trí.  Vậy chúng ta thực hiện lặp công việc trên với i từ 0 tới n-2 chúng ta sẽ có mảng được  sắp.  

 c. Sắp xếp bằng phương pháp chọn

Các bạn có nhận xét là trong phương pháp đổi chỗ trực tiếp để đặt được phần tử vào vị trí i có thể phải sử dụng -1 phép đổi chỗ. Trong khi đó chỉ có một phần tử sẽ đặt tại đó.  Phương pháp chọn cũng xuất phát từ ý tưởng như phương pháp đổi chỗ trực tiếp nhưng thay vì đổi chỗ A[i] với Ạ[j] trong mỗi bước duyệt (theo j) thì chúng ta xác định  phần tử nhỏ nhất trong các phần tử A[i+1],..A[n-1]  giả sử là A[k], sau đó dổi chỗA[k] và A[i]. Như vậy với mỗi vị trí i chương trình  chỉ thực hiện đổi chỗ một lần, và người ta tính thời gian thực hiện trung bình của phương pháp này ít hơn thời gian trung bình của hai phương pháp trên. 

Ví dụ V.3: chương trình minh hoạ sắp xếp mảng bằng phương pháp nổi bọt 

 #include <stdio.h> 

#include <conio.h>

 void main){ <;

  scanf"; 

}while(n<2); 

printf"\nNhapmangco;

 for0 { 

  printf"a[;  

    scanf";  

 } 

 for-1

  for-1 

 if-1    

  {  

tg=a[j];

 a[j]=a[j-1];

 a[j-1]=tg;

}  

printf("Mang sau khi sap la \n");

  for0  

  printf";

 Tìm kiếm trên mảng 

 Giả sử cho trước một mảng các số nguyên A(n), và một số x. hãy kiểm tra x có thuộc mảng A hay không? Với bài toán tìm kiếm trên mảng nói chung, chúng ta phân  hai trường hợp:

 ƒ Trường hợp 1: Mảng A không  có trật tự (chưa được sắp) thì để tìm kiếm một  giá trị  nào đó thì chúng ta  phải duyệt tuần tự mảng từ phần tử đầu tiên cho tới khi gặp giá trị đó hoặc tới phần tử cuối cùng thì mới khẳng định được giái trị đó có thuộc mảng hay không. Như vậy trong trường hợp kém nhất thì số lần so sánh là n.  

 có thể minh hoạ như sau:

 // Nhập n, A(n), x i = 0 ; 

while((i <n)&&(A[i] !=x)) i++;

 if-1 printf“; 

else  printf“; 

ƒ Trường hợp 2: Mảng A đã được sắp (không mất tổng quát giả sử tăng dần), trong trường hợp này chúng ta có thể áp dụng phương pháp tìm kiếm nhị phân để giảm số bước phải so sánh.

 Ý tưởng là ta chia đôi mảng A thành hai phần, so sánh x với phần tử ở giữa của mảng  A[g] xảy ra ba trường hợp : 

 A[g] = = x  thì kết luận x thuộc vào A và kết thúc

 A[g]   >  x  thì chúng ta lặp lại việc tìm x trong nửa cuối của mảng

 A[g]   <  x  thì chúng ta lặp lại việc tìm x trong nửa đầu của mảng 

Như vậy sau một bước so sánh chúng ta có thể giảm số phần tử cần duyệt còn một nửa. Như vậy số lần kiểm tra so sánh trung bình sẽ giảm so với phương pháp duyệt tuần tự.    có thể minh hoạ như sau: 

// Nhập n, A(n), x

 // Mảng A theo thứ tụ tăng dần

 l = 0, r =n-1 ; 

  // l, r chỉ số đầu, cuối của các phần tử cần duyệt

 while(l <= r)  { 

 g =  0/2; 

  // lấy phần tử giữa   

   if (A[g] ==x) printf“; 

return;

 if (A[g] > x)  l = g+1 ;

 // lặp timg trong nửa cuối 

  }  

 else  r = g-1; 

 // tim trong nửa đầu.  

      } 

 printf“;

 //....... 

Ví dụ V.4: Chương trình sinh ngẫu nhiên một mảng có n phần tử, sắp xếp mảng đó theo thứ tự tăng bằng phương pháp chọn, Nhập x từ bàn phím kiẻm tra x có trong mảng hay không