Ctdl c1-tong quan

  • Published on
    21-Jun-2015

  • View
    3.064

  • Download
    7

Embed Size (px)

DESCRIPTION

Tng quan v cu trc d liu v gii thut

Transcript

<ul><li> 1. C U TRC D LI U V GI I THU T DATA STRUCTURE AND ALGORITHMS GV: Phm Tun Hip Email: hiep0109@yahoo.com</li></ul> <p> 2. Ni dung mn hc 2Chng 1: T ng quan v CTDL v GTChng 2.1: Cc gi i thu t Tm ki mChng 2.2: Cc gi i thu t S p x pChng 3.1: Danh sch lin k tChng 3.2: Ng n x p - Hng iChng 4: CyCh ng 1: T ng quan v C TDL v GT 3. nh gi kt qu 3Kim tra gia k: trc nghim1. im Kim tra gia k &lt; 4 khng c thi kt thc mn hc li2. 3.Thi kt thc mn: trc nghim Kim tra thng k: thc hnhCh ng 1: T ng quan v C TDL v GT 4. Ti liu hc tp 4Tham kho: Gio trnh Cu trc d liu 1, Trn Hnh Nhi Dng Anh c, Trng HKHTN HQG TP.HCM.Phn mm lp trnh: C-Free Visual C++ Ch ng 1: T ng quan v C TDL v GT 5. Nhc nh mt s quy nh i hc ng gieo th SVKhng chung in thoi reo trong gi hcKhng nghe in thoi, nhn tin trong gi hcKhng ni chuyn ring, lm n khi nghe gingMang y ti liu hc tp ca mn hc (khi hc LT v TH): gio trnh, bi tp, tp chp bi (hoc slide bi ging), usb lu bi tp Phi lm bi tp nh Nu vi phm: Nhc nh chung B mi ra khi lp 5 Ch ng 1: T ng quan v C TDL v Xa tn khi mn hc GT 6. 6Chng 1 T NG QUAN V C U TRC D LI U V GI I THU T 7. Ni dung 7 Khi nim cu trc d liu Khi nim gii thut (thut ton, thut gii) Mi lin h gia cu trc d liu v gii thutCh ng 1: T ng quan v C TDL v GT 8. Khi nim d liu 8Ti sao s dng my tnh s l d liu? Nhanh hn, chnh xc hn Gii quyt nhiu bi ton i hi khi lng tnh ton cc ln, hoc nhng bi ton phc tp vi khi lng d liu lnCh ng 1: T ng quan v C TDL v GT 9. Khi nim d liu 9Trong tin hc: D liu biu din cc thng tin cn thit cho bi tonCc d liu my tnh: D liu u vo, d liu trung gian, d liu u raCh ng 1: T ng quan v C TDL v GT 10. Cu trc d liu l g? 10Ch ng 1: T ng quan v C TDL v GT 11. Cu trc d liu l g? 11Ch ng 1: T ng quan v C TDL v GT 12. Cu trc d liu l g? 12Khi nim: Cu trc d liu (data structure) l mt phng thc c th l u tr v t ch c d liu trong my tnh vic x l hi u quCc kiu cu trc d liu: D liu khng cu trc (kiu d liu n hay cn gi l kiu d liu c s) Mi i tng d liu l mt phn t n l V d: int, float, char,D liu c cu trc c cu thnh bi cc phn t d liu c s V d: Mng, Chui, Cu trc (struct), Ch ng 1: T ng quan v C TDL v GT 13. Kiu d liu c s 13S nguynCh ng 1: T ng quan v C TDL v GT 14. Kiu d liu c s 14S thcLun l (ng/sai)Ch ng 1: T ng quan v C TDL v GT 15. Kiu d liu c cu trc 15Ch ng 1: T ng quan v C TDL v GT 16. Kiu d liu c cu trc 16Ch ng 1: T ng quan v C TDL v GT 17. Kiu d liu c cu trc 17Kiu cu trc (struct) V d: Bng thng tin sinh vin nh sau:Ch ng 1: T ng quan v C TDL v GT 18. Khi nim gii thut 18Ch ng 1: T ng quan v C TDL v GT 19. Cc c trng ca gii thut 19 C d liu u vo (Input) C d liu kt qu u ra (Output) Tnh chnh xc (Precision): Cc bc ca gii thut c m t chnh xc Tnh hu hn (Finiteness): Gii thut phi a c u ra sau mt s bc hu hn vi mi u vo Tnh n tr (Uniqueness): Cc kt qu trung gian ca tng bc thc hin gii thut c xc nh mt cch n tr v ch ph thuc u vo v cc kt qu ca cc bc trc Tnh tng qut (Generality): Gii thut c th p dng gii mi bi ton c dng choCh ng 1: T ng quan v C TDL v GT 20. Cc cch biu din gii thut 20 Ngn ng t nhin Lu (Flow chart) M gi (Pseudo code) Ngn ng lp trnhCh ng 1: T ng quan v C TDL v GT 21. Cc k hiu lu 21Ch ng 1: T ng quan v C TDL v GT 22. Cc k hiu m gi 22 IF THEN ENDIF IF THEN ELSE ENDIF WHILE DO ENDWHILE DO UNTIL DISPLAY RETURN Ch ng 1: T ng quan v C TDL v GT 23. V d 23Bi ton: Cho 3 s nguyn a, b, c. M t gii thut tm s ln nht trong 3 s cho Phn tch u vo: 3 s nguyn a, b, c u ra: s ln nht trong 3 sCh ng 1: T ng quan v C TDL v GT 24. V d 24Dng ngn ng t nhin m t gii thut tm s ln nht trong 3 s a, b, c Bc 1. Gn max = a; Bc 2. Nu b &gt; max th gn max = b; Bc 3. Nu c &gt; max th gn max = c;Ch ng 1: T ng quan v C TDL v GT 25. V d 25Dng m gi m t gii thut tm s ln nht trong 3 s a, b, c max = a IF b &gt; max THEN max = b ENDIF IF c &gt; max THEN max = c ENDIF DISPLAY max Ch ng 1: T ng quan v C TDL v GT 26. V d 26Dng lu m t gii thut tm s ln nht trong 3 s a, b, cCh ng 1: T ng quan v C TDL v GT 27. phc tp ca gii thut 27Mt thut ton hiu qu S dng ti nguyn thp: b nh, thi gian s dng CPU, Phng php nh gi phc tp ca gii thut Da trn thi gian thc hin gii thut n khi ra c kt qu Da trn s php ton thc hin gii thutCh ng 1: T ng quan v C TDL v GT 28. Tnh thi gian thc hin gii thut 28Hon ton c th o bng cch lp trnhCh ng 1: T ng quan v C TDL v GT 29. Tnh s php ton thc hin gii thut 29 n Kch thc u vo ca d liu M t phc tp ca thut ton qua mt hm O(n) Hai nguyn tc nh gi Nguyn tc cng Nguyn tc nhnCh ng 1: T ng quan v C TDL v GT 30. Tnh s php ton thc hin gii thut 30Ch ng 1: T ng quan v C TDL v GT 31. Tnh s php ton thc hin gii thut 31Ch ng 1: T ng quan v C TDL v GT 32. Mi lin h gia CTDL v GT 32 Gii thut = php x l i tng ca gii thut chnh l d liu c t chc thnh cc cu trc CTDL &amp; GT gn cht vi nhau. Niklaus Wirth tng kt: Cu trc d liu + Gii thut = Chng trnh Nu thay i cu trc d liu th gii thut cng s thay i theoCh ng 1: T ng quan v C TDL v GT 33. Mi lin h gia CTDL v GT 33 V d qun l danh b in thoi D liu gm: H v tn S in thoiCh ng 1: T ng quan v C TDL v GT 34. Mi lin h gia CTDL v GT 34Bi ton tm s in thoi theo h tn: Nu danh b khng c t chc th dn n gii thut l tm tun t t u n cui Nu danh b (h v tn) t chc theo th t a,b,c th ta c th tm kim nhanh hnCh ng 1: T ng quan v C TDL v GT 35. Hng tip cn mn CTDL v GT 35Tm hiu v mt l thuyt v chi tit ci t cc cu trc d liu v gii thut im mnh: hiu su v bn cht, c th xy dng CTDL&amp;GT cho nhng bi ton phc tp im yu: kh hiu, i hi sinh vin nm vng c l thuyt v cng c lp trnhCh ng 1: T ng quan v C TDL v GT 36. Tng kt 36Cu trc d liu l cch t chc cc d liu c bn thnh cc cu trc nh mng, chui, file, Gii thut l tp hu hn c th t cc bc tc ng ln d liu no sau mt s hu hn ln thc hin s cho ta kt qu Vic la chn cu trc d liu v gii thut cho bi ton l rt quan trngCh ng 1: T ng quan v C TDL v GT</p>