Bài giảng Nhập môn lập trình: Mảng dữ liệu - Trần Phước Tuấn

NMLT M?NG D? LI?U Tr?n Ph??c Tu?n tranphuoctuan.khoatoan.dhsp@gmail.com NH?P MÔN L?P TRÌNH 212/23/2009 M?ng – Array ? M?t s? tính ch?t ? Khai báo m?ng trong C ? Truy xu?t các thành ph?n ? Truy?n tham s? ki?u m?ng cho hàm ? M?t s? thao tác c? s? ? M?ng nhi?u chi?u NH?P MÔN L?P TRÌNH 312/23/2009 M?ng – M?t s? tính ch?t ? M?ng là m?t ki?u d? li?u có c?u trúc do ng??i l?p trình ??nh ngh?a ? Dùng bi?u di?n các ??i t??ng d? li?u ? d?ng m?t dãy các thành ph?n có cùng ki?u v?i nhau – ki?u c? s? ? NNLT C luôn ch? ??nh m?t kh?i nh? liên t?c cho m?t bi?n ki?u m?ng ? Kích th??c c?a m?ng ???c xác ??nh ngay khi khai báo và không bao gi? thay ??i NH?P MÔN L?P TRÌNH 412/23/2009 M?ng – Khai báo trong C typedef ki?uc?s? Tênki?u[S?thànhph?n]; ki?u c?a m?i thành ph?n h?ng s?, s? thành ph?n t?i ?a c?a m?ng do l?p trình viên ??t tên typedef int AINT[100]; //AINT là ki?u m?ng bi?u di?n dãy g?m 100 thành ph?n int AINT a; //a: bi?n ki?u AINT NH?P MÔN L?P TRÌNH 512/23/2009 M?ng – Ví d? #define SIZE 10 int a[5]; // a dãy g?m 5 s? nguyên long int big[100]; // big: chi?m 400 bytes! double d[100]; // d: chi?m 800 bytes! long double v[SIZE];// v:10 long doubles #define SIZE 10 int a[5]; // a dãy g?m 5 s? nguyên long int big[100]; // big: chi?m 400 bytes! double d[100]; // d: chi?m 800 bytes! long double v[SIZE];// v:10 long doubles NH?P MÔN L?P TRÌNH 612/23/2009 M?ng – Ví d? int a[5] = { 10, 20, 30, 40, 50}; double d[100] = { 1.5, 2.7}; short primes[] = { 1, 2, 3, 5, 7, 11, 13}; long b[50] = { 0 }; int a[5] = { 10, 20, 30, 40, 50}; double d[100] = { 1.5, 2.7}; short primes[] = { 1, 2, 3, 5, 7, 11, 13}; long b[50] = { 0 }; int i = 7; const int c = 5; int a[i]; double d[c]; short primes[]; int i = 7; const int c = 5; int a[i]; double d[c]; short primes[]; kh?i tr? cho 5 thành ph?n 2 thành ph?n ??u tiên ???c kh?i tr?, ph?n còn l?i: 0 compiler xác ??nh kích th??c g?m 7 thành ph?n cách nhanh nh?t ?? kh?i tr? ??t c? các thành ph?n b?ng 0 NH?P MÔN L?P TRÌNH 712/23/2009 ? Các thành ph?n c?a m?ng ???c truy xu?t thông qua ch? s? c?a chúng 0..size-1 ? Thao tác truy xu?t không ki?m tra gi?i h?n c?a ch? s? int main() { int a[6]; int i = 7; a[0] = 59; a[5] = -10; a[i/2] = 2; a[6] = 0; a[-1] = 5; return 0; } int main() { int a[6]; int i = 7; a[0] = 59; a[5] = -10; a[i/2] = 2; a[6] = 0; a[-1] = 5; return 0; } 0 a 1 2 3 4 5 M?ng – Truy xu?t các ph?n t? NH?P MÔN L?P TRÌNH 812/23/2009 Truy?n tham s?M?ng cho hàm ? Tham s? ki?u m?ng ???c truy?n cho hàm chính là ??a ch? c?a ph?n t? ??u tiên trên m?ng ? S? thành ph?n trong tham s? m?ng có th? ?? tr?ng. ? S? thành ph?n th?c s? ???c s? d?ng ph?i truy?n qua m?t tham s? khác (vd: size) int add_elements(int a[], int size) { int add_elements(int a[], int size) { int add_elements(int *p, int size) { int add_elements(int *p, int size) { NH?P MÔN L?P TRÌNH 912/23/2009 Ví d? #include void sum(long [], int); int main(void) { long primes[6] = { 1, 2, 3, 5, 7, 11 }; sum(primes, 6); printf("%li\n", primes[0]); return 0; } void sum(long a[], int sz) { int i; long total = 0; for(i = 0; i < sz; i++) total += a[i]; a[0] = total; } #include void sum(long [], int); int main(void) { long primes[6] = { 1, 2, 3, 5, 7, 11 }; sum(primes, 6); printf("%li\n", primes[0]); return 0; } void sum(long a[], int sz) { int i; long total = 0; for(i = 0; i < sz; i++) total += a[i]; a[0] = total; } 1 2 3 5 7 11 primes a sz 6 ??ng ???c l?u vào ph?n t? ??u tiên dùng ?? ki?m tra gi?i h?n ch? ?? NH?P MÔN L?P TRÌNH 1012/23/2009 M?t s? thao tác c? s? ? Nh?p ? Xu?t ? Thêm m?t thành ph?n d? li?u ? Lo?i b? m?t thành ph?n d? li?u ? Tìm ki?m ? S?p x?p NH?P MÔN L?P TRÌNH 1112/23/2009 M?ng – Nh?p d? li?u void ReadData(int a[], int size) { int i; for(i = 0; i < size; i++) { printf(“Nhap thanh phan %d: ”, i); scanf(“%d”, &a[i]); } } void ReadData(int a[], int size) { int i; for(i = 0; i < size; i++) { printf(“Nhap thanh phan %d: ”, i); scanf(“%d”, &a[i]); } } duy?t qua t?t c? các ph?n t? nh?p d? li?u cho a[i] NH?P MÔN L?P TRÌNH 1212/23/2009 M?ng – Xu?t d? li?u ra màn hình void WriteData(int a[], int size) { int i; for(i = 0; i < size; i++) printf(“%d ”, a[i]); printf(“\n”); } void WriteData(int a[], int size) { int i; for(i = 0; i < size; i++) printf(“%d ”, a[i]); printf(“\n”); } NH?P MÔN L?P TRÌNH 1312/23/2009 M?ng – Nh?p xu?t d? li?u #include void ReadData(int [], int ); void WriteData(int [], int ); void main() { int a[100], n; clrscr(); printf(“Nhap so thanh phan cua day: “); scanf(“%d”, &n); printf(“Nhap cac thanh phan cua day: “); ReadData(a, n); printf(“Day vua nhap: \n“); WriteData(a, n); } #include void ReadData(int [], int ); void WriteData(int [], int ); void main() { int a[100], n; clrscr(); printf(“Nhap so thanh phan cua day: “); scanf(“%d”, &n); printf(“Nhap cac thanh phan cua day: “); ReadData(a, n); printf(“Day vua nhap: \n“); WriteData(a, n); } NH?P MÔN L?P TRÌNH 1412/23/2009 M?ng – Tìm v? trí X trong dãy //input: dãy (a, N), X //output: V? trí c?a X, -1 n?u không có int Search(int a[], int N, int X) { for (int i = 0; i < N; i ++) if (a[i] == X) return i; return -1; } //input: dãy (a, N), X //output: V? trí c?a X, -1 n?u không có int Search(int a[], int N, int X) { for (int i = 0; i < N; i ++) if (a[i] == X) return i; return -1; } ? Bài toán: Tìm v? trí X trên m?ng a ?ang có N thành ph?n. ? Gi?i pháp: Tìm tu?n t? NH?P MÔN L?P TRÌNH 1512/23/2009 M?ng – Thêm m?t thành ph?n d? li?u ? Bài toán: c?n thêm thành ph?n d? li?u X vào m?ng a ?ang có N thành ph?n. ? Hai tr??ng h?p c?n xem xét: ? Dãy ch?a có th? t? ? Thêm X vào cu?i a. ? Dãy ?ã có th? t? ? Tìm v? trí thích h?p, chèn X vào NH?P MÔN L?P TRÌNH 1612/23/2009 M?ng – Thêm X vào cu?i dãy 2 8 5 1 6 4 15 12 1 2 3 4 5 6 70 Thêm 15 vào (a, 7) N = 78 a[N] = X; N ++; a[N] = X; N ++;X NH?P MÔN L?P TRÌNH 1712/23/2009 M?ng – Chèn X vào dãy t?ng d?n 2 4 5 8 12 15 6 1 1 2 3 4 5 6 70 Chèn 6 vào (a, 7) N = 78 X ?? trí thích h?p: 4 pos NH?P MÔN L?P TRÌNH 1812/23/2009 M?ng – Chèn X vào dãy t?ng d?n //input: dãy (a, N) ??ng d?n, X //output: dãy (a, N) ?ã có X ? ?úng v? trí void Insert(int a[], int &N, int X) { int pos; for (pos = N; (pos>0)&&(a[pos-1]>X); pos --) a[pos] = a[pos – 1]; a[pos] = X; N ++; } //input: dãy (a, N) ??ng d?n, X //output: dãy (a, N) ?ã có X ? ?úng v? trí void Insert(int a[], int &N, int X) { int pos; for (pos = N; (pos>0)&&(a[pos-1]>X); pos --) a[pos] = a[pos – 1]; a[pos] = X; N ++; } NH?P MÔN L?P TRÌNH 1912/23/2009 M?ng – Lo?i b? m?t thành ph?n d? li?u ? Bài toán: lo?i b? thành ph?n d? li?u X ra kh?i m?ng a ?ang có N thành ph?n. ? ???ng gi?i quy?t: xác ??nh v? trí c?a X, n?u tìm th?y thì d?n các ph?n t? ? phía sau lên ?? l?p vào ch? tr?ng. 2 tr??ng h?p: ? Dãy không có th? t?: l?p ph?n t? cu?i lên ? Dãy ?ã th? t?: d?i t?t c? các ph?n t? ? sau ví trí c?a X lên tr??c 1 v? trí. NH?P MÔN L?P TRÌNH 2012/23/2009 N = 8 M?ng – Lo?i b? X ra kh?i dãy t?ng 2 8 5 1 6 4 1512 1 2 3 4 5 6 70 Lo?i 5 kh?i (a, 8) 7 pos Tìm v? trí c?a 5 5X STOP Ok, found ??n các v? trí 4, 5, 6, 7 lên NH?P MÔN L?P TRÌNH 2112/23/2009 M?ng – Lo?i b? X ra kh?i dãy t?ng //input: dãy (a, N), X //output: dãy (a, N) ?ã lo?i b? 1 thành ph?n X int Remove(int a[], int &N, int X) { int pos = Search(a, N, X); if (pos == -1) //không có X trong dãy return 0; N --; for (; (pos < N); pos ++) a[pos] = a[pos + 1]; return 1; } //input: dãy (a, N), X //output: dãy (a, N) ?ã lo?i b? 1 thành ph?n X int Remove(int a[], int &N, int X) { int pos = Search(a, N, X); if (pos == -1) //không có X trong dãy return 0; N --; for (; (pos < N); pos ++) a[pos] = a[pos + 1]; return 1; } NH?P MÔN L?P TRÌNH 2212/23/2009 M?ng – S?p x?p ? Bài toán: S?p x?p các thành ph?n c?a (a, N) ?? thu ???c dãy t?ng d?n ? Gi?i pháp: Tìm cách tri?t tiêu t?t c? các ngh?ch th? c?a dãy ? Thu?t toán s?p x?p ??i ch? tr?c ti?p NH?P MÔN L?P TRÌNH 2312/23/2009 M?ng – S?p x?p ??i ch? 2 8 5 1 6 4 1512 2 3 4 5 6 7 81 i j 1 NH?P MÔN L?P TRÌNH 2412/23/2009 12 8 5 2 6 4 151 2 3 4 5 6 7 81 i j 2 M?ng – S?p x?p ??i ch? NH?P MÔN L?P TRÌNH 2512/23/2009 2 12 8 5 6 4 151 2 3 4 5 6 7 81 i j 4 M?ng – S?p x?p ??i ch? NH?P MÔN L?P TRÌNH 2612/23/2009 2 4 12 8 6 5 151 2 3 4 5 6 7 81 i j 5 M?ng – S?p x?p ??i ch? NH?P MÔN L?P TRÌNH 2712/23/2009 2 4 5 6 8 12 151 2 3 4 5 6 7 81 M?ng – S?p x?p ??i ch? NH?P MÔN L?P TRÌNH 2812/23/2009 M?ng – S?p x?p ??i ch? void Swap(int &x, int &y) { int t = x; x = y; y = t; } void InterchangeSort(int a[], int N) { int i, j; for (i = 0 ; i<N-1 ; i++) for (j =i+1; j < N ; j++) if(a[j]< a[i]) Swap(a[i],a[j]); } void Swap(int &x, int &y) { int t = x; x = y; y = t; } void InterchangeSort(int a[], int N) { int i, j; for (i = 0 ; i<N-1 ; i++) for (j =i+1; j < N ; j++) if(a[j]< a[i]) Swap(a[i],a[j]); } NH?P MÔN L?P TRÌNH 2912/23/2009 M?ng nhi?u chi?u ? C không h? tr? m?ng nhi?u chi?u. Tuy nhiên có th? ti?p c?n theo h??ng: M?ng 2 chi?u là m?ng m?t chi?u mà m?i thành ph?n c?a nó là m?t m?ng m?t chi?u. float rainfall[12][365];float rainfall[12][365]; “rainfall” là m?ng g?m 12 thành ph?n, m?i thành ph?n là ??ng g?m 365 s? float short exam_marks[500][10];short exam_marks[500][10]; “exam_marks” là m?ng g?m 500 thành ph?n, m?i thành ph?n là m?ng 10 s? short const int brighton = 7; int day_of_year = 238; rainfall[brighton][day_of_year] = 0.0F; const int brighton = 7; int day_of_year = 238; rainfall[brighton][day_of_year] = 0.0F; NH?P MÔN L?P TRÌNH 3012/23/2009 Tóm l??c ? Khai báo m?ng trong C ? Truy xu?t các ph?n t? ? Truy?n tham s? ki?u m?ng cho hàm ? Các thao tác: nh?p, xu?t, thêm/h?y 1 thành ph?n, tìm ki?m, s?p x?p ? M?ng nhi?u chi?u