Xem mẫu
- tv n
Trong r t nhi u bài toán chúng ta c n thao tác
Chương 4 trên m t dãy (ho c m t b ng, ...) g m h u h n
các ph n t cùng ki u. Ch ng h n:
- m t l p h c: có các ph n t là sinh viên.
- m t ma tr n: có các ph n t là s th c.
M ng & các gi i thu t v i m ng
Khi ó c n có các c u trúc d li u phù h p, ó
chính là m ng.
M ng là dãy h u h n, có th t các ph n t
có cùng m t ki u d li u.
M ng có th có 1 ho c nhi u chi u.
tv n (tt) Khai báo m ng
Thông tin v sinh viên ư c lưu tr trong m t ph n t [gi ih nchi u1]... [gi ih nchi uk]
sv[0] sv[0] sv[k]
Ví d :
dãy sinh viên
2 0 1 4 //m ng 1 chi u g m 10 pt a[0]->a[9]:
4 5 10 3
int a[10];
0 9 6 0
//m ng 2 chi u g m 12 ph n t b[0][0]->b[2][3]:
ma tr n
float b[3][4];
- Lưu tr m ng Lưu tr m ng (tt)
M ng ư c lưu tr m t vùng nh liên
t c trong RAM.
2 0 1 4
H th ng s qu n lý a ch ph n t u
tiên (th 0) c a m ng, t ó có th truy 4 5 10 3
xu t n ph n t b t kỳ b ng cách tính a ch g c th hi n logic
ra a ch c a ph n t ó. c a m ng
Theo quy ư c: tên m ng chính là a ch 2 0 1 4 4 5 10 3 0 9 6 0
c a ph n t u tiên c a m ng. th hi n v t lý trong RAM
a == &a[0]
Truy xu t m ng Truy xu t m ng (tt)
Quy t c: truy xu t m ng thông qua t ng ph n Ví d 2: Hàm sau ây s nh p d li u cho m ng n s
nguyên (gi s a và n ư c khai báo toàn c c).
t c a nó.
void nhapDL()
[ch s 1]...[ch s k]
{
Ví d 1: Gi s có int a[10], b[3][4]; int i;
khi ó: for(i=0;i
- M ng và con tr M ng và con tr (tt)
Trong trư ng h p m ng dùng làm tham s cho m t hàm ta có 2 Ví d 2: hàm in ma tr n b, n dòng, m c t ra màn hình
cách s d ng sau:
(gi s b ư c khai báo s c t là 10).
Cách 1: S d ng khai báo hình th c.
Ví d 1: void inMT(int b[][10], int n, int m)
void nhapDL(int a[], int n) {
{ i v i m ng 2 chi u, c n ch
int i,j;
int i; rõ s c t khai báo
for(i=0;i
- M ng và con tr (tt) M ng và con tr (tt)
Gi i thích: Ví d 2: hàm in ma tr n ra màn hình
void inMT(int *p, int n, int m)
int x[100], n;
{
... int i,j;
l i g i hàm nh p d li u s có d ng: for(i=0;i
- Các gi i thu t trên m ng Các gi i thu t trên m ng (tt)
Tính toán trên m ng: Gi i thích: i=0 t=0+a[0]=2
Ví d 1: Tính t ng các ph n t dương i=1 t=2
c a m ng nguyên a, n ph n t . 0 1 2 3 4 5 6 7 i=2 t=2+a[2]=3
2 0 1 4 -3 2 -8 1
i=3 t=3+a[3]=7
int tongDuong(int *p, int n)
{ i=4 t=7
int i,t=0;
for(i=0;i0)t+=p[i];
i=6 t=9
return t;
} i=7 t=9+a[7]=10
Các gi i thu t trên m ng (tt) Các gi i thu t trên m ng (tt)
Tìm max-min: Gi i thích: i=0 m=0
Cho m ng a, n s nguyên. Hãy tìm ch i=1 m=0
s c a ph n t l n nh t. 0 1 2 3 4 5 6 7 i=2 m=0
2 0 1 4 -3 2 -8 1
i=3 m=3
int max(int *p, int n)
{ i=4 m=3
int i,m=0;
for(i=1;i
- Các gi i thu t trên m ng (tt) Các gi i thu t trên m ng (tt)
Tìm ki m: Gi i thích:
Cho m ng a, n s nguyên. Tìm v trí xu t i=0 x!=a[0]
hi n ph n t x. 0 1 2 3 4 5 6 7 i=1 x!=a[1]
2 0 1 4 -3 2 -8 1
int timKiem(int *p, int n, int x) i=2 x=a[2]
{ x=1
int i=0;
while(i a[n-1] r i hoán v min v i a[1].
tăng d n. ...
ây trình bày 2 phương pháp s p x p: Bư c i: Tìm ph n t min trong các ph n t a[i]
-> a[n-1] r i hoán v min v i a[i].
- Phương pháp ch n (selection).
...
- Phương pháp hoán i tr c ti p Bư c n-2: Tìm ph n t min gi a a[n-2] và a[n-
(interchange). 1] r i hoán v min v i a[n-2].
- Phương pháp s p x p ch n (tt) Phương pháp s p x p ch n (tt)
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
Minh h a: void selection(int a[], int n)
2 0 1 4 -3 2 -8 1 -8 0 1 4 -3 2 2 1 {
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 int i,j,t,m;
-8 0 1 4 -3 2 2 1 -8 -3 1 4 0 2 2 1 for(i=0;i
- Phương pháp interchange (tt) Ví d v m ng 2 chi u
void interchange(int a[], int n)
Ví d 1: Cho ma tr n nguyên A, n dòng,
{
int i,j,t; m c t. Hãy vi t các hàm:
for(i=0;i
- Ví d v m ng 2 chi u (tt) H i áp
//hàm tìm ph n t max:
int timMax(int *p, int n, int m, int M)
{
int i,j,d,c;
d=c=0;
for(i=0;i
nguon tai.lieu . vn