›
›

Cơ sở dữ liệu - Mảng dữ liệu

pdf 15 trang vanle 2920
Download
Bạn đang xem tài liệu "Cơ sở dữ liệu - Mảng dữ liệu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfco_so_du_lieu_mang_du_lieu.pdf

Nội dung text: Cơ sở dữ liệu - Mảng dữ liệu

  1. NMLTNMLT MMҦҦNGNG DDӲӲ LILIӊӊUU Trҫn Phѭӟc Tuҩn tranphuoctuan.khoatoan.dhsp@gmail.com MMҧҧngng –– ArrayArray „ 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 12/23/2009 2
  2. MMҧҧngng –– Mӝt sӕ tínhnh chchҩtt „ 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 12/23/2009 3 MMҧҧngng –– Khai báoo trongtrong CC 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 12/23/2009 4
  3. MMҧҧngng –– Ví dө #define#define SIZE SIZE 1010 intint a[5];a[5]; //a//adãydãy ggӕӕmm 55 ssӓӓ nguyênnguyên longlong int int big[100]; big[100]; // // big: big: chichiӁӁmm 400 400 bytes!bytes! doubledouble d[100];d[100]; // // d: d: chi chiӁӁmm 800 800 bytes!bytes! longlong doubledouble v[SIZE];// v[SIZE];// v:10 v:10 long long doublesdoubles NHҰP MÔN LҰP TRÌNH 12/23/2009 5 khӣi trӏ cho 5 MMҧҧngng –– Ví dө thành phҫn intint a[5]a[5] == {{ 10,10, 20,20, 30,30, 40,40, 50};50}; doubledouble d[100]d[100] == {{ 1.5,1.5, 2.7};2.7}; shortshort primes[]primes[] == {{ 1,1, 2,2, 3,3, 5,5, 7,7, 11,11, 13};13}; longlong 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ӏ Wҩt cҧ các intint ii = = 7;7; thành phҫn bҵng 0 constconst int int c c == 5;5; intint a[i];a[i]; doubledouble d[c];d[c]; shortshort primes[];primes[]; NHҰP MÔN LҰP TRÌNH 12/23/2009 6
  4. MMҧҧngng –– Truy xuҩtt ccácc phphҫ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ӕ intint main() main() a {{ 0 int a[6]; int a[6]; 1 intint ii == 7;7; a[0]a[0] == 59;59; 2 a[5]a[5] == -10;-10; 3 a[i/2]a[i/2] == 2;2; 4 a[6]a[6] == 0;0; 5 a[-1]a[-1] == 5;5; returnreturn 0;0; }} NHҰP MÔN LҰP TRÌNH 12/23/2009 7 TruyӅӅn tham sӕ MMҧ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) intint add_elements(int add_elements(int a[], a[], int int size) size) {{ intint add_elements(int add_elements(int *p, *p, int int size) size) {{ NHҰP MÔN LҰP TRÌNH 12/23/2009 8
  5. Ví dө Ví dө primes #include#include 1 void sum(long [], int); void sum(long [], int); 2 intint main(void) main(void) {{ 3 longlong primes[6] primes[6] == {{ 1,1, 2,2, 3,3, 5,5, 7,7, 1111 };}; 5 sum(primes,sum(primes, 6);6); 7 printf("%li\n", primes[0]); printf("%li\n", primes[0]); 11 returnreturn 0;0; }} a voidvoid sum(long sum(long a[],a[], int int sz)sz) {{ sz 6 intint i;i; longlong total total == 0;0; dùng ÿӇ kiӇm tra for(ifor(i == 0;0; ii << sz; sz; i++)i++) giӟi hҥn chӍ Vӕ totaltotal +=+= a[i];a[i]; a[0] = total; Wәng ÿѭӧc lѭu vào a[0] = total; phҫn tӱ ÿҫu tiên }} NHҰP MÔN LҰP TRÌNH 12/23/2009 9 MMӝӝtt ssӕӕ thaothao ttáácc ccѫѫ ssӣӣ „ 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 12/23/2009 10
  6. MMҧҧngng –– Nhұpp ddӳ liӋӋu voidvoid ReadData(int ReadData(int a[], a[], int int size)size) { { duyӋt qua tҩt cҧ các intint i; i; phҫn tӱ for(ifor(i == 0;0; ii << size; size; i++) i++) {{ printf(“Nhapprintf(“Nhap thanhthanh phanphan %d:%d: ”,”, i);i); scanf(“%d”,scanf(“%d”, &a[i]);&a[i]); }} }} nhұp dӳ liӋu cho a[i] NHҰP MÔN LҰP TRÌNH 12/23/2009 11 MMҧҧngng –– Xuҩt dӳ liӋӋu ra màn hìnhnh voidvoid WriteData(int WriteData(int a[], a[], int int size)size) {{ intint i; i; for(ifor(i == 0;0; ii << size; size; i++) i++) printf(“%dprintf(“%d ”,”, a[i]);a[i]); printf(“\n”);printf(“\n”); }} NHҰP MÔN LҰP TRÌNH 12/23/2009 12
  7. MMҧҧngng –– Nhұpp xuxuҩtt ddӳ liliӋuu #include#include voidvoid ReadData(int ReadData(int [],[], intint );); voidvoid WriteData(int WriteData(int [],[], intint );); voidvoid main() main() {{ intint a[100], a[100], n;n; clrscr();clrscr(); printf(“Nhapprintf(“Nhap soso thanhthanh phanphan cuacua day:day: “);“); scanf(“%d”,scanf(“%d”, &n);&n); printf(“Nhapprintf(“Nhap caccac thanhthanh phanphan cuacua day:day: “);“); ReadData(a,ReadData(a, n);n); printf(“Dayprintf(“Day vuavua nhap:nhap: \n“);\n“); WriteData(a,WriteData(a, n);n); }} NHҰP MÔN LҰP TRÌNH 12/23/2009 13 MMҧҧngng –– Tìm vӏ trtrí X trong dãy „ 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ӵ //input://input: dãydãy (a,(a, N),N), XX //output://output: VV͔͔ trítrí c cͰͰaa X,X, -1-1 nn͈͈uu khôngkhông cócó intint Search(intSearch(int a[],a[], intint N,N, intint X)X) {{ forfor (int(int ii == 0;0; ii << N;N; ii ++)++) ifif (a[i](a[i] === X)X) returnreturn i;i; returnreturn 1;1; }} NHҰP MÔN LҰP TRÌNH 12/23/2009 14
  8. MMҧҧngng –– ThêmThêm mmӝt thànhnh phphҫ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 12/23/2009 15 MMҧҧngng –– ThêmThêm XX vvàào cuӕii dãydãy Thêm 15 vào (a, 7) 01234567 12 2 8 5 1 6 4 N = 78 a[N]a[N] == X;X; 15 NXN ++;++; NHҰP MÔN LҰP TRÌNH 12/23/2009 16
  9. MMҧҧngng –– ChChèn X vào dãy tăăngng ddҫnn Chèn 6 vào (a, 7) pos 01234567 1 2 4 5 8 12 15 N = 78 X 6 9ӏ trí thích hӧp: 4 NHҰP MÔN LҰP TRÌNH 12/23/2009 17 MMҧҧngng –– Chèn X vàào dãy tăng dҫnn //input://input: dãydãy (a,(a, N)N) WăWăngng dd̰̰n,n, XX //output://output: dãydãy (a,(a, N)N) ÿÿãã cócó X X ͨͨ ÿÿúngúng vv͔͔ trítrí voidvoid Insert(intInsert(int a[],a[], intint &N,&N, intint X)X) {{ intint pos;pos; forfor (pos(pos == N;N; (pos>0)&&(a[pos(pos>0)&&(a[pos-1]>X);-1]>X); pospos )) a[pos]a[pos] == a[posa[pos ––1]; 1]; a[pos]a[pos] == X;X; NN ++;++; }} NHҰP MÔN LҰP TRÌNH 12/23/2009 18
  10. MMҧҧngng –– LoLoҥi bӓ mmӝtt ththà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 12/23/2009 19 MMҧҧngng –– LoLoҥi bӓ XX rara khkhӓii dãydãy ttăăngng Loҥi 5 khӓi (a, 8) pos 01234567 12 2 8 5 1 6 4 15 N = 87 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
  11. MMҧҧngng –– Loҥi bӓ XX rara khkhӓii dãydãy ttăng //input://input: dãydãy (a,(a, N),N), XX //output://output: dãydãy (a,(a, N)N) ÿÿãã lolo̪̪ii bb͘͘ 11 thànhthành phph̰̰nn XX intint Remove(intRemove(int a[],a[], intint &N,&N, intint X)X) {{ intint pospos == Search(a,Search(a, N,N, X);X); ifif (pos(pos === 1)1) //không//không ccóó X X trongtrong dãydãy returnreturn 0;0; NN ;; forfor (;(; (pos(pos << N);N); pospos ++)++) a[pos]a[pos] == a[posa[pos ++ 1];1]; returnreturn 1;1; }} NHҰP MÔN LҰP TRÌNH 12/23/2009 21 MMҧҧngng –– Sҳpp xxӃӃ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 12/23/2009 22
  12. MMҧҧngng –– Sҳpp xxӃӃp ÿәi chәә j 12345678 1212 8 5 1 6 4 15 i NHҰP MÔN LҰP TRÌNH 12/23/2009 23 MMҧҧngng –– SSҳҳpp xxӃӃpp ÿÿәәii chchәә j 12345678 1 1228 5 2 6 4 15 i NHҰP MÔN LҰP TRÌNH 12/23/2009 24
  13. MMҧҧngng –– SSҳҳpp xxӃӃpp ÿÿәәii chchәә j 12345678 1 2 1248 5 6 4 15 i NHҰP MÔN LҰP TRÌNH 12/23/2009 25 MMҧҧngng –– SSҳҳpp xxӃӃpp ÿÿәәii chchәә j 12345678 1 2 4 1258 6 5 15 i NHҰP MÔN LҰP TRÌNH 12/23/2009 26
  14. MMҧҧngng –– SSҳҳpp xxӃӃpp ÿÿәәii chchәә 12345678 1 2 4 5 6 8 12 15 NHҰP MÔN LҰP TRÌNH 12/23/2009 27 MMҧҧngng –– SSҳҳpp xxӃӃpp ÿÿәәii chchәә voidvoid Swap(intSwap(int &x,&x, intint &y)&y) {{ intint tt == x;x; xx == y;y; yy == t;t; }} voidvoid InterchangeSort(intInterchangeSort(int a[],a[], intint N)N) {{ intint i,i, j;j; forfor (i(i == 00 ;; i<N-1i<N-1 ;; i++)i++) forfor (j(j =i+1;=i+1; jj << NN ;; j++)j++) if(a[j]<if(a[j]< a[i])a[i]) Swap(a[i],a[j]);Swap(a[i],a[j]); }} NHҰP MÔN LҰP TRÌNH 12/23/2009 28
  15. MMҧҧngng nhinhiӅӅuu chichiӅӅuu „ 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 floatfloat rainfall[12][365];rainfall[12][365]; thành phҫn, mӛi thành phҫn là Pҧng gӗm 365 sӕ float “exam_marks” là mҧng gӗm shortshort 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 constconst int int brightonbrighton = = 7;7; intint day_of_year day_of_year == 238;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 TTóómm llѭѭӧӧcc „ 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 NHҰP MÔN LҰP TRÌNH 12/23/2009 30