Kỹ thuật lập trì nh
70
CHươNG 3 CáC THUậT TOáN TRÊN CấU TRúC Dữ LIệU MảNG

I. Mảng không sắp xếp và thuật toán tìm kiếm trên
mảng chưa có thứ tự
I.1. Một số khái niệ m về mảng:

I.1.1. Định nghĩ a:
Mả ng là 1 d y cá c phầ n tử có cùng kiể u dữ liệ u đ ược sắ p xế p liê n tiế p
nhau trong bộ nhớ
0100
0102 1 int
0104 2 Mả ng n phần tử

n-1
Bộ nhớ
!
!!
!Khai báo:

Cú pháp
: Khai bá o mả ng 1 chiề u
Kiể u_DL Tê nmả ng [kí ch thước];

Kiể u_DL : là 1 trong cá c kiể u dữ liệ u cơ bả n, đó là kiể u của phầ n tử
của mả ng

Tê nmả ng: là tê n của mả ng đ ược đặt 1 cá ch hợp lệ

Kí ch thước: là 1 hằ ng nguyê n cho biế t số phầ n tử tối đa của mả ng

Ta khởi động đ ược trị cho mả ng trong 2 trường hợp sau:

Mả ng đ ược khai bá o là biế n ngoà i (main) nghĩ a là biế n toà n cục

Mả ng đ ược khai bá o cục bộ
Ví dụ 1
: int M[3] = {10,11,12}
main()
{
}
Ví dụ 2
:
main()
{ static int M[ ]={10,22,30};
............
}

Ta có thể gá n 1 hằ ng cho cả mả ng như sau:
memset (M,0,sizeof(int) *3) ; // gá n 0 cho mả ng M với M có 3 phầ n tử

Từ khóa static dùng để khai bá o 1 biế n cục bộ thường trực cho phép duy
trì giá trị riê ng của nó ở những lầ n gọi hà m sau nà y.

Khởi tạ o mả ng 2 chiề u:
int M[2][3]= {{1,2,3},
{0,1,0}};
I.1.3.Truy xuất thành phần của mảng: M[chỉ số]

Truy xuấ t thà nh phầ n thứ 2 của mả ng 1 chiề u: M[1]


liệ u của từng thà nh phầ n mả ng
Ví dụ
:
int i, n;
float M[10];
for(i = 0; i< n; i++)
printf(a[%d] = %f,i+1, M[i]);
I.2. Thuật toán tì m kiế m trê n mảng chưa có thứ tự:

Do mả ng chưa có thứ tự nê n ta á p dụng phương phá p tì m kiế m tuyế n tí nh tì m
từ đầ u mả ng cho đế n cuối mả ng. Trong chương trì nh sau đâ y, hà m Timkiế m sẽ
trả về trị -1 nế u không có m sinh viê n trong danh sá ch ds, ngược lạ i hà m sẽ trả
về vị trí của m số đó trong danh sá ch ds.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SOSV 100 // số sinh viê n tối đa trong danh sá ch
typedef struct sinhvien // định nghĩ a kiể u sinhvien
Kỹ thuật lập trì nh
73
{ char maso[6];
char hoten[30];
};

typedef struct danhsach_sv // định nghĩ a kiể u danhsach_sv
{ int tssv;
sinhvien sv[MAX_SOSV];
} ;

Kỹ thuật lập trì nh
74
}
void main()
{ struct danhsach_sv ds;
char maso[6];
int vitri;
Nhap_ds(&ds); // Gọi hà m Nhap_ds với tham số là ds
Lietke_ds(&ds);
printf("Ma so sinh vien ban can tim :");
gets(maso);
vitri = Timkiem(&ds, maso);
if (vitri !=-1)
printf("Ho ten cua sinh vien la %s",ds.sv[vitri].hoten);
else printf(" Khong co sinh vien voi ma ban nhap vao");
getch();
}
II. Các thuật toán sắp xếp
:
Trong thực tế cuộc sống cũng như trong lĩ nh vực lậ p trì nh, việ c quả n lỹ dữ liệ u
thường đòi hỏi sự tì m kiế m cá c dữ liệ u cầ n thiế t; Để thuậ n tiệ n cho việ c tì m
kiế m, dữ liệ u thường đ ược sẵ p xế p theo một thứ tự nà o đó.
Có rấ t nhiề u phương phá p sắ p thứ tự, trong bà i giả ng nà y ta chỉ khả o sát hai
phương phá p sắ p xế p là Bubble_Sort và Quick_Sort.
Để thuậ n tiệ n ta giả sử mả ng là d y số có tối đa 100 số, và cá c thuậ t toá n dưới
đâ y dùng để sắ p xế p d y số theo thứ tự tă ng dầ n.
II.1. Sắp xế p theo phương pháp Bubble_Sort
(phương pháp nổi bọt)
- Nội dung
: Ta cho i duyệ t d y a[0], .. ,a[n-1]; nế u a[i-1] lớn hơn a[i] thì ta

{ int i,n;
printf("\nSo phan tu cua mang :"); scanf("%d",&n);
for (i=0; i<n; i++)
{ printf ("A[%d] = ",i+1);
scanf("%d",&A[i]);
}
return n;
}
void Liet_ke (int A[], int n)
{ int i;
printf("\n Gia tri mang da duoc sap : \n");
for (i=0; i<n; i++)
printf ("%5d",A[i]);
getch();
}

void main()
{
size= Nhap_day_so(mang);