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

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

55
lượt xem 4
download

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

Trong bài này sẽ trình bày về mảng dữ liệu với các nội dung cụ thể như sau: Môt số tính chất của mảng, khai báo mảng trong C, truy xuất các thành phần, một số thao tác cơ sở, mảng nhiều chiều. Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: 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 http://baigiang.tranphuoctuan.com M ng – Array M t s tính ch t Khai bá báo m ng trong C Truy xu t cá các thà 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 12/23/2009 2
M ng – M t s tính ch t M ng là là m t ki u d li u có có c u trú 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 12/23/2009 3 M ng – Khai báo trong C typedef ki uc s Tênki u[S thà thànhph n]; ki u c a m i thà thành ph n h ng s , s thà thành ph n t i a c a m ng do l p trì 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 12/23/2009 4
M ng – Ví d #define #define SIZE SIZE 10 10 int int a[5]; a[5]; // // aa dãy dãy gg mm 55 ss nguyên nguyên long long int int big[100]; big[100];// // big: big: chi chi mm 400 400 bytes! bytes! double double d[100]; d[100]; // // d: d: chi chi mm 800 800 bytes! bytes! long long double double v[SIZE];// v[SIZE];// v:10 v:10 long long doubles doubles NH P MÔN L P TRÌNH 12/23/2009 5 M ng – Ví d kh i tr cho 5 thành ph n int int a[5] a[5] == {{ 10, 10, 20, 20, 30, 30, 40, 40, 50}; 50}; double double d[100] d[100] == {{ 1.5, 2.7}; 1.5, 2.7}; short short primes[] primes[] == {{ 1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 11, 11, 13}; 13}; long long b[50] b[50] == {{ 00 }; }; 2 thành ph n u tiên c compiler xác nh kh i tr , ph n kích th c g m 7 còn l i: 0 thành ph n cách nhanh nh t kh i tr t c các int ii == 7; int 7; thành ph n b ng 0 const int c = const int c = 5; 5; int int a[i]; a[i]; double double d[c]; d[c]; short short primes[]; primes[]; NH P MÔN L P TRÌNH 12/23/2009 6
M ng – Truy xu t các ph n t 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 int main() main() a {{ 0 int int a[6]; a[6]; int i 1 int i == 7; 7; a[0] = 59; a[0] = 59; 2 a[5] a[5] == -10; -10; 3 a[i/2] a[i/2] = 2; = 2; 4 a[6] = a[6] = 0;0; a[-1] a[-1] == 5;5; 5 return return 0;0; }} NH P MÔN L P TRÌNH 12/23/2009 7 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 int add_elements(int add_elements(int a[], a[], int int size) size) {{ int int add_elements(int add_elements(int *p, *p, int int size) size) {{ NH P MÔN L P TRÌNH 12/23/2009 8
Ví d primes #include #include 1 void void sum(long [], sum(long [], int); int); 2 int main(void) int main(void) { { long 3 long primes[6] primes[6] == {{ 1, 1, 2, 2, 3, 5, 7, 11 3, 5, 7, 11 };}; 5 sum(primes, sum(primes, 6); 6); 7 printf("%li\n", printf("%li\n", primes[0]); primes[0]); 11 return 0; return 0; }} a void voidsum(long sum(long a[], a[], int int sz) sz) {{ sz 6 int int i;i; long long total total == 0; 0; dùng ki m tra for(i for(i = 0; i < sz; = 0; i < sz; i++) i++) gi i h n ch total += a[i]; total += a[i]; a[0] ng c l u vào a[0] = total; = total; }} ph n t u tiên NH P MÔN L P TRÌNH 12/23/2009 9 M t s thao tác c s Nh p Xu t Thêm m t thà thành ph n d li u Lo i b m t thà thành ph n d li u Tìm ki m S px p NH P MÔN L P TRÌNH 12/23/2009 10
M ng – Nh p d li u void void ReadData(int ReadData(int a[], a[], int int size) size) {{ duy t qua t t c các int i; int i; ph n t for(i for(i == 0; 0; ii
M ng – Nh p xu t d li u #include #include void void ReadData(int ReadData(int [], [], int int ); ); void void WriteData(int [], int ); WriteData(int [], int ); void main() void main() {{ int int a[100], a[100], n; n; clrscr(); clrscr(); printf(“Nhap printf(“Nhap soso thanh thanh phan phan cua cua day: day: “); “); scanf(“%d”, scanf(“%d”, &n); &n); printf(“Nhap printf(“Nhap cac cac thanh thanh phan phan cua cua day: day: “); “); ReadData(a, ReadData(a, n); n); printf(“Day printf(“Day vua nhap: vua nhap: \n“); \n“); WriteData(a, WriteData(a, n); n); }} NH P MÔN L P TRÌNH 12/23/2009 13 M ng – Tìm v trí X trong dãy Bài toá toán: Tì Tìm v trí trí X trên m ng a ang có có N thà thành ph n. Gi i pháp: Tìm tu n t //input: //input: dãy dãy (a, (a, N), N), XX //output: //output: VV trí trí cc aa X, X, -1 -1 nn uu không không có có int int Search(int Search(int a[], a[], int int N, N, int int X) X) {{ for for (int (int ii == 0; 0; ii
M ng – Thêm m t thành ph n d li u Bài toá toán: c n thêm thà thành ph n d li u X và 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 12/23/2009 15 M ng – Thêm X vào cu i dãy Thêm 15 vào (a, 7) 0 1 2 3 4 5 6 7 12 2 8 5 1 6 4 N=8 7 a[N] a[N] == X; X; X 15 NN ++; ++; NH P MÔN L P TRÌNH 12/23/2009 16
M ng – Chèn X vào dãy t ng d n Chèn 6 vào (a, 7) pos 0 1 2 3 4 5 6 7 1 2 4 5 8 12 15 N=8 7 X 6 trí thích h p: 4 NH P MÔN L P TRÌNH 12/23/2009 17 M ng – Chèn X vào dãy t ng d n //input: //input: dãy dãy (a, (a, N) N) ng ng dd n, n, XX //output: //output: dãy dãy (a, (a, N) N) ãã có có XX úng úng vv trí trí void void Insert(int Insert(int a[], a[], int int &N, &N, int int X) X) {{ int int pos; pos; for for (pos (pos == N; N; (pos>0)&&(a[pos- (pos>0)&&(a[pos-1]>X); pos (pos>0)&&(a[pos-1]>X); pos --) --) --) a[pos] a[pos] == a[pos a[pos –– 1]; 1]; a[pos] = X; a[pos] = X; NN ++; ++; }} NH P MÔN L P TRÌNH 12/23/2009 18
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í ví trí c a X lên tr c 1 v trí. NH P MÔN L P TRÌNH 12/23/2009 19 M ng – Lo i b X ra kh i dãy t ng Lo i 5 kh i (a, 8) pos 0 1 2 3 4 5 6 7 12 2 8 5 1 6 4 15 N=7 8 STOP X 5 Ok, found Tìm v trí c a 5 n các v trí 4, 5, 6, 7 lên NH P MÔN L P TRÌNH 12/23/2009 20
M ng – Lo i b X ra kh i dãy t ng //input: //input: dãy dãy (a, (a, N), N), XX //output: //output: dãy dãy (a, (a, N) N) ãã lo lo ii bb 11 thành thành ph ph nn XX int int Remove(int Remove(int a[], a[], int int &N, &N, int int X) X) {{ int int pos pos == Search(a, Search(a, N, N, X); X); if (pos == - 1) //không if (pos == -1) //không có có có XX trong trong dãy dãy return return 0;0; NN --; --; --; for for (; (; (pos (pos
M ng – S p x p i ch j 1 2 3 4 5 6 7 8 12 1 2 8 5 1 6 4 15 i NH P MÔN L P TRÌNH 12/23/2009 23 M ng – S p x p i ch j 1 2 3 4 5 6 7 8 1 2 12 8 5 2 6 4 15 i NH P MÔN L P TRÌNH 12/23/2009 24
M ng – S p x p i ch j 1 2 3 4 5 6 7 8 1 2 12 4 8 5 6 4 15 i NH P MÔN L P TRÌNH 12/23/2009 25 M ng – S p x p i ch j 1 2 3 4 5 6 7 8 1 2 4 12 5 8 6 5 15 i NH P MÔN L P TRÌNH 12/23/2009 26
M ng – S p x p i ch 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 NH P MÔN L P TRÌNH 12/23/2009 27 M ng – S p x p i ch void void Swap(int Swap(int &x,&x, int int &y) &y) {{ int int tt == x; x; xx == y; y; yy == t; t; }} void void InterchangeSort(int InterchangeSort(int a[], a[], int int N) N) {{ int int i,i, j; j; for for (i (i == 00 ;; i
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. “rainfall” là m ng g m 12 float float rainfall[12][365]; rainfall[12][365]; thành ph n, m i thành ph n là ng g m 365 s float “exam_marks” là m ng g m short short exam_marks[500][10]; exam_marks[500][10]; 500 thành ph n, m i thành ph n là m ng 10 s short const const int int brighton brighton == 7; 7; int day_of_year = 238; int day_of_year = 238; rainfall[brighton][day_of_year] rainfall[brighton][day_of_year] == 0.0F; 0.0F; NH P MÔN L P TRÌNH 12/23/2009 29 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à hàm Các thao tá tác: nh p, xu t, thêm/h y 1 thà thành ph n, tìm ki m, s p x p M ng nhi u chi u NH P MÔN L P TRÌNH 12/23/2009 30