Xem mẫu

  1. 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];
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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].
  7. 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
  8. 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
  9. 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