Bài giảng Cấu trúc dữ liệu 1 - Chương 01: Mở đầu về cấu trúc dữ liệu - Lương Trần Hy Hiến

Nội dung text: Bài giảng Cấu trúc dữ liệu 1 - Chương 01: Mở đầu về cấu trúc dữ liệu - Lương Trần Hy Hiến

1. ði H c Sư Ph m Tp. H Ch í Minh Thơng tin ging viên • LƯƠNG TR N HY HI N CU TR ÚC D LI U 1 • B Mơn Tin Hc • Khoa Tốn – Tin hc • Phone: 0989 366 990 • Email: hienlth@hcmup.edu.vn Chương 01: M đu v CTDL Chương 1. Gii thiu v cu trúc d liu 1.1 Vai trị ca cu trúc d liu 1.1 Vai trị ca cu trúc d liu 1.2 Mt s tiêu chun chn CTDL 1.3 Kiu d liu Thơng tin Bài tốn Thao tác nghip v nghip v 1.4 ð phc tp gii thut thc t thc t Bài tốn trên ði tưng Yêu c u d liu máy tính x lý
2. 1.1 Vai trị ca cu trúc d liu 1.1 Vai trị ca cu trúc d liu Yêu c u Cu trúc d liu + gii thut = chương trình ði tưng Bài tốn trên d liu máy tính x lý  Ví d 1: Chương trình qun lý đim sinh viên ca mt Khi gii quyt các bài tốn thc t cn quan tâm: khĩa hc. Mi sinh viên hc 4 mơn hc và các đim
   T chc biu din các đi tưng thc t tương ng như sau: Chn cu trúc d liu phù hp Mơn 1 Mơn 2 Mơn 3 Mơn 4
   Xây dng các thao tác x lý d liu Sinh viên 1 7 8 5 6 Tìm gii thut gii quyt bài tốn. Sinh viên 2 8 6 4 5 Sinh viên 3 3 7 9 5 Cu trúc d liu + gii thut = chương trình Sinh viên 4 9 7 6 5 1.1 Vai trị ca cu trúc d liu 1.1 Vai trị ca cu trúc d liu ði tưng d liu  Phân tích ví d 1  Phương án 1 Chương Dùng mng mt chiu Mơn 1 Mơn 2 Mơn 3 Mơn 4 trình qun lưu tr đim ca tt Sinh viên 1 7 8 5 6 lý đim c các sinh viên Sinh viên 2 8 6 4 5 Sinh viên 3 3 7 9 5 Sinh viên 4 9 7 6 5 ði tưng d liu Yêu cu x lý Mơn 1 Mơn 2 Mơn 3 Mơn 4
   Nhp đim Sinh viên 1 Sinh viên 2 Sinh viên 3 Sinh viên 4 Sinh viên 1 7 8 5 6
   Xut danh sách đim Sinh viên 2 8 6 4 5
   Tính đim trung bình R 7 8 5 6 8 6 4 5 3 7 9 5 9 7 6 5 Sinh viên 3 3 7 9 5
   Thng kê t l đu, hng Sinh viên 4 9 7 6 5
   Các thao tác tìm kim theo đim R[ I] = Bng đim( dịng ( I / s mơn) , ct ( I % s mơn) )
3. 1.1 Vai trị ca cu trúc d liu 1.1 Vai trị ca cu trúc d liu ði tưng d liu  Phương án 1  Phương án 2 Dùng mng hai chiu Mơn 1 Mơn 2 Mơn 3 Mơn 4 7 8 5 6 8 6 4 5 3 7 9 5 9 7 6 5 R lưu tr đim ca tt Sinh viên 1 7 8 5 6 R[ I] = Bng đim( I / s mơn , I % s mơn ) c các sinh viên Sinh viên 2 8 6 4 5 Sinh viên 3 3 7 9 5 int R[16 ] = { 7,8,5,6, 8,6,4,5 ,3,7,9,5 ,9,7,6,5}; Sinh viên 4 int SO_MON = 4; 9 7 6 5 int SO_SV = 4; R Ct 0 Ct 1 Ct 2 Ct 3 void xuat() { Dịng 0 R[0][0]= 7 R[0][1]= 8 R[0][2]= 5 R[0][3]= 6 for ( int I =0 ; I < SO_MON *SO_SV ; I++) { int SV = I / SO_MON ; Dịng 1 R[1][1]= 8 R[0][1]= 6 R[0][1]= 4 R[0][3]= 5 int MON = I % SO_MON ; Dịng 2 R[2][1]= 3 R[0][1]= 7 R[0][1]= 9 R[0][3]= 5 cout<< “Diem mon “<<MON<<“ cua sv “<<SV<<“ = “<< R[I]; Dịng 3 } R[3][1]=9 R[0][1]=7 R[0][1]=6 R[0][3]=5 } R[ I][ J] = Bng đim( dịng I , ct J ) 1.1 Vai trị ca cu trúc d liu 1.1 Vai trị ca cu trúc d liu ði tưng d liu  Phương án 2  Phương án 3 Mơn 1 Mơn 2 Mơn 3 Mơn 4 R[ I][ J] = Bng đim( dịng I , ct J ) Dùng mng mt chiu, các phn t cĩ kiu Sinh viên 1 7 8 5 6 int R[4][4] = { {7,8,5,6}, Sinh viên 2 8 6 4 5 {8,6,4,5}, cu trúc nhm lưu Sinh viên 3 {3,7,9,5} , tr đim ca tt c 3 7 9 5 {9,7,6,5}}; các sinh viên Sinh viên 4 9 7 6 5 int SO_MON = 4; R int SO_SV = 4; R[0].Mon1= 7 R[1].Mon1= 8 R[2].Mon1= 3 R[3].Mon1=9 void xuat() { for ( int I=0 ; I < SO_SV ; ++ I) R[0].Mon2= 8 R[1].Mon2= 6 R[2].Mon2= 7 R[3].Mon2=7 for ( int J=0 ; J < SO_MON ; ++ J) R[0].Mon3= 5 R[1].Mon3= 4 R[2].Mon3= 9 R[3].Mon3=6 cout<< “Diem mon“<<J<<“ cua sv “<<I<<“ = ”<< R[I][ J]; } R[0].Mon4= 3 R[1].Mon4= 5 R[2].Mon4= 5 R[3].Mon4=5 R[ I ] lưu tr tt c các đim ca sinh viên th I
4. 1.1 Vai trị ca cu trúc d liu 1.2 Mt s tiêu chí chn cu trúc d liu  Phương án 3 a. CTDL phi phn ánh đúng thc t. ðây là yu t quyt đnh tính đúng đn ca bài tốn. Cn R[ I][ J] = Bng đim( dịng I , ct J ) xem xét trng thái bin đi ca d liu nhm chn CTDL struct DiemSV { phù hp. int Mon1,Mon2,Mon3,Mon4; b. CTDL phi phù hp vi thao tác trên đĩ. }; DiemSV R[4]; Tiêu chun này giúp tăng tính hiu qu ca bài tốn.Mi int SO_SV = 4; CTDL cĩ các thao tác đi tương ng. Nên chn CTLD sao void xuat() { cho các thao tác đưc x lý đưc đơn gin và t nhiên. for ( int I=0 ; I vi: ví d 2: Gi s cĩ kiu d liu Contact = V : tp các giá tr hp l mà đi tưng kiu T cĩ th lưu tr V = {H và tên, đa ch, s điên thoi} O : tp các thao tác x lý cĩ th thi hành trên đi tưng đĩ O = {Gán giá tr, so sánh} ví d 1: Gi s cĩ kiu d liu Alphabet = Gi s cĩ kiu d liu ContactList = V = {a – z, A – Z} V = {danh sách các đi tưng cĩ kiu Contact } O = {ly mã ASCII ca ký t, đi ký t sang dng ch hoa, ch O = { Thêm, xĩa, sa, so sánh, tìm kim, sp xp} thưng} Gi s cĩ kiu d liu Number = V = {0 255} O = { + , , * , / , %}
5. 1.3 Kiu d liu 1.3 Kiu d liu 1.3.2 Các kiu d liu cơ bn 1.3.1 ðnh nghĩa kiu d liu
   Kiu d liu cĩ th t ri rc: S nguyên, ký t, logic, Các thuc tính cn quan tâm v kiu d liu: lit kê, min con
   Kiu d liu khơng ri rc: s thc
   Tên kiu d liu Mt s kiu d liu cơ bn trong ngơn ng C
   Min giá tr Tên kiu d liu Kích thưc Min giá tr
   Kích thưc lưu tr char 01 Byte 128 đn 127 unsign char 01 Byte 0 đn 255
   Tp các tốn t, thao tác x lý tác đng lên int 02 byte 0 đn 65535 đi tưng cĩ kiu d liu long 04 byte 231 đn 2 31 1 unsign long 04 byte 0 đn 2 32 1 float 04 Byte 3.4E38 đn 3.4E38 double 08 byte 1.7E308 đn 1.7E308 long double 10 byte 3.4E4932 đn 1.1E4932 1.3 Kiu d liu 1.3 Kiu d liu 1.3.2 Các kiu d liu cĩ cu trúc 1.3.2 Các kiu d liu cĩ cu trúc Ví d: ð mơ t thơng tin sinh viên cn quan tâm đn thơng tin sau: Các thao tác trên chui Mã s sinh viên : 12 ký t Tên hàm Cơng dng Tên sinh viên : 30 ký t strcmp (s1,s2) So sánh 2 chui s1 và s2 Ngày sinh : kiu ngày strcpy (dest,src) Sao chép src vào dest Nơi sinh : 255 ký t strstr (s1,s2) Kim tra s2 cĩ nm trong ðim trung bình : S thc chui s1 khong? a. Kiu chui ký t itoa (n,s,c) ði s nguyên n thành Chui ký t trong là mt dãy các ký t liên tip kt thúc bng ký chui dng cơ s c atoi (sn) , atof (sf), atol (sl) ði 1 chui thành s t cĩ mã ASCII bng 0. Chui ký t cĩ ti đa 65535 ký t gets (st) Nhp mt chui Ví d: char S[10]; puts (st) Xut mt chui char S[] = “ABC”; char *S = “ABC”;
6. 1.3 Kiu d liu 1.3 Kiu d liu b. Kiu mng c. Kiu mu tin(cu trúc) Mng là kiu d liu lưu tr các phn t cùng kiu. Mi phn t Kiu mu tin là kiu d liu mà mi phn t ca nĩ là tp hp đưc xác đnh bi mt v trí trí ca nĩ trong mng. các giá tr cĩ th khác cu trúc. Kiu mu tin cho phép mơ t các Khai báo mng 1 chiu đi tưng cĩ cu trúc phc tp. [ ]; Khai báo int a[100]; struct { int a[5]={4, 3, 6, 7, 2}; ; int a[ ] = {1, 4 , 3, 5, 6}; ; Khai báo mng 2 chiu . [ ][ ]; }; int a[10][10]; int a[3][2]={{4, 3},{ 6, 7},{2,3}}; 1.3 Kiu d liu 1.4 ðánh giá đ phc tp ca thut tốn d. Kiu Union Phương pháp thc nghim: Kiu Union ging như Struct, nhưng các trưng dùng chung  Cài đt thut tốn, chn các b d liu th, thng kê các vùng nh. thơng s nhn đưc. Khai báo  Mt s nhưc đim: union {  Ph thuc vào ngơn ng lp trình dùng đ cài đt ; ;  Ph thuc vào trình đ ca ngưi cài đt .  Vic chn ra b d liu th đc trưng cho tt c các }; trưng hp rt khĩ khăn.  Ph thuc vào phn cng khi thc thi thut tốn
7. 1.4 ðánh giá đ phc tp ca thut tốn 1.4 ðánh giá đ phc tp ca thut tốn Phương pháp hình thc: S phân lp các đ phc tp ca thut tốn  ðây là phương pháp đánh giá ít ph thuc vào mơi
   ð phc tp là hng s O(1) trưng cũng như phn cng.ðánh giá theo hưng xp
   ð phc tp là logN O(logN) x tim cn thơng qua khái nim tốn hc Oln O().
   ð phc tp là N O(N)  Thi gian tính tốn s ph thuc vào kích thưc
   ð phc tp là NlogN O(NlogN) ca d liu đu vào(thưng gi là N) và đánh giá theo
   ð phc tp là N2 O(N 2) 3 trưng hp:
   ð phc tp là N3 O(N 3)  Trưng hp tt nht
   ð phc tp là 2N O(2 N)  Trưng hp xt nht  Trưng hp trung bình
   ð phc tp là N! O(N!) Câu hi và tho lun 27