Kỹ thuật lập trình - Mảng và các giải thuật với mảng

Chia sẻ: Phan Giang | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

311
lượt xem 115
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo chuyên ngành công nghệ thông tin - Kỹ thuật lập trình - Mảng và các giải thuật với mảng

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Kỹ thuật lập trình - Mảng và các giải thuật với mảng

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