Bài giảng Cấu trúc dữ liệu 1 - Chương 3: Danh sách đặc (mảng) - 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 3: Danh sách đặc (mảng) - Lương Trần Hy Hiến

1. ði H c Sư Ph m Tp. H Ch ớ Minh Ni dung 1. ðnh nghĩa CU TR ÚC D LI U 1 2. Cỏc phộp toỏn trờn mng 3. Stack 4. Queue Chương 3: Danh sỏch ủ ặặặc (M ảảảng) 1. ðnh nghĩa 2. Cỏc thao tỏc x lý cơ bn trờn mng • Mng là tp hp ca cỏc bin cựng kiu ủưc Bài tp 1: Vit chương trỡnh nhp vào mt dóy s nguyờn. In dóy s va nhp theo th t ngưc li. xp liờn tip nhau trong b nh trong. • Cỏc loi mng: Input : s lưng cỏc phn t trong dóy (N>0). – Mng 1 chiu N s nguyờn. • tờn_mng [s_phn_t] Output : N s nguyờn theo th t ngưc li. – Mn nhiu chiu • tờn_mng ði tưng d liu : int N [s_phn_t_chiu_1 ][ s_phn_t_chiu_2 ] [s_phn int a[] _t_chiu_n ] Thao tỏc x lý : Nhp s lưng phn t Nhp dóy s Xut dóy s
2. 2. Cỏc thao tỏc x lý cơ bn trờn mng #include Bài tp 2: Vit chương trỡnh nhp vào mt dóy s nguyờn int n; dương. In ra dóy s sau khi chốn mt phn t nguyờn dương int a[100]; vào mt v trớ cho trưc ca dóy. void main() { cout > n;
   N là s lưng cỏc phn t.
   int N, X, K for (int i=0; i > a[i];
   K là v trớ cn chốn
   Nhp dóy s } Output :
   Chốn X vào dóy ti v trớ K for (i = n-1; i >= 0; i )
   Dóy s sau khi chốn
   Xut dóy s cout = K ; i)
   Dóy s sau khi xúa
   Chốn phn t ti v trớ K 1. Di cỏc phn t t v trớ N1
   Xut dóy s ủn K v phớa sau 1 ụ a[ i+1 ] = a[ i] 2. ðt giỏ tr X vào v trớ th K a[K] = X; 3. Tăng s lưng phn t N = N +1
3. b) Thao tỏc xúa 1 phn t ca mng 2. Cỏc thao tỏc x lý cơ bn trờn mng K N Bài tp 4: Vit chương trỡnh nhp vào mt dóy s nguyờn. In ra v trớ ca giỏ tr X nhp vào t bàn phớm hoc thụng bỏo 0 1 2 3 4 5 6 7 8 9 khụng tỡm thy. 4 1 6 7 3 5 8 ~9 ~ ~ i Input : ði tưng d liu:
   N là s lưng cỏc phn t.
   int N, X
   N s nguyờn dương
   int A[] Mụ t for ( i = K; i <= N2 ; i++)
   X là giỏ tr cn tỡm Thao tỏc x lý 1. Di cỏc phn t t v trớ K+1 a[ i] = a[ i+1 ]; Output :
   Nhp dóy s ủn N1 v phớa trưc 1 ụ N = N 1;
   V trớ ca X hoc thụng
   Tỡm giỏ tri X 2. Gim s lưng phn t ủi 1 bỏo khụng tỡm thy.
   Xut thụng tin tỡm kim. c) Thao tỏc tỡm kim tuyn tớnh c) Thao tỏc tỡm kim tuyn tớnh X= 3 N X= 3 N 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 4 1 6 7 3 5 8 ~9 ~ ~ 4 1 6 7 3 5 8 ~9 ~ ~ Gii thut 1. I = 0  N1 int linearSearch(int a[ ], int N, int X){ 1.1 Nu A[i] =X thỡ for (int i=0; i<N;i++){ Tin hành so sỏnh x ln lưt vi phn t th – Print I if (a[i] == X) 0, th 1, ca mng cho ủn khi gp khúa – Dng return i cn tỡm, hoc ht mng mà khụng tỡm thy 2. Nu I=N thỡ } return -1; giỏ tr. print 1 }
4. c) Thao tỏc tỡm kim tuyn tớnh c) Thao tỏc tỡm kim tuyn tớnh X= 3 N X= 3 N 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 4 1 6 7 3 5 8 ~9 ~ ~ 4 1 6 7 0 5 8 39 ~ ~ 1. I =0; int linearSearch(int a[], int N, 1. I =0; A[N] = X int linearSearch(int a[], int N, int X) { 2. Trong khi I a[mid] : right = mid 1; //tỡm tip trong dóy a a kt qu so sỏnh này ủ quyt ủnh gii hn tỡm mid+1 right Bưc 3: Nu left <= right. Quay li bưc 2 kim bưc k tip là na trờn hay na dưi Ngưc li: Dng. //ủó xột ht tt c cỏc phn t ca dóy hin hành.
5. c) Thao tỏc tỡm kim nh phõn L R N int BinarySearch (int a[],int n, int x) { 0 1 2 3 4 5 6 7 8 X= 4 int left = 0; 1 3 5 6 7 8 9 ~9 ~ int right = n1; while (left a[mid]) left = mid + 1; x a[mid] : left= mid +1 ; //tỡm tip trong dóy a mid+1 aright } Bưc 3: Nu left <= right. Quay li bưc 2 return 1; Ngưc li: Dng. //ủó xột ht tt c cỏc phn t } Bài tp Bài tp 1. Vit chương trỡnh tỡm phn t ln nht trong mt 5. ð sp xp dóy s nguyờn theo t t tăng dn ngưi ta dóy s nguyờn. ln lưt tỡm giỏ tr nh nht ủt vào ủu dóy, giỏ tr 2. Vit chương trỡnh tỡm tt c cỏc s nguyờn t trong nh th 2 ủt vào v trớ th 2, và tương t như th cho mt dóy s nguyờn dương nhp vào t bàn phớm. ủn ht dóy. Vit chương trỡnh sp xp dóy s nguyờn theo ý tưng trờn. 3. Vit chương trỡnh tỡm dóy con tăng dn dài nht trong dóy s nguyờn nhp vào t bàn phớm. 6. Vit chương trỡnh qun lý danh b ủin thoi vi cỏc thụng tin : S th t, h và tờn, s ủin thoi,ủa ch 4. Vit chương trỡnh nhp vào mt dóy ký t. In ra s email. Chương trỡnh ủm bo cỏc chc năng sau: ln xut hin ca cỏc ký t trong dóy. a. Nhp thụng tin vào danh b 5. Mt s t nhiờn ủưc gi là Palindrom khi cỏc ch b. Danh b phi ủưc sp tăng dn theo s th t s ca nú ủưc vit theo th t ngưc li s to c. Xut danh b thành s mi bng chớnh s ủú (vớ d: 4884, 321123, 15651). Hóy kim tra s t nhiờn nhp vào t bàn d. Tỡm kim thụng tin da vào “h và tờn” hoc “ủa ch email phớm cú phi là s Palindrom khụng? e. Xúa thụng tin da vào s th t cho trưc.
6. 3. Stack Vớ d v stack • Mt stack là mt cu trỳc • Stack rng: d liu mà vic thờm vào và loi b ủưc thc hin • ðy (push) Q vào: Q ti mt ủu (gi là ủnh – top ca stack). A • Là mt dng vào sau ra • ðy A vào: Q trưc – LIFO (Last In A First Out) • Ly (pop) ra mt => ủưc A: Q • Ly ra mt => ủưc Q và stack rng: Q ng dng: ðo ngưc danh sỏch Cỏc phộp toỏn trờn ngăn xp • Yờu cu: ðo ngưc mt danh sỏch nhp vào • empty (A): kim tra ngăn xp cú rng? • Gii thut: • length (A): Cho bit s phn t ngăn xp. 1. Lp li n ln • push (A, x ): Thờm phn t x vào ngăn xp A. 1.1. Nhp vào mt giỏ tr 1.2. ðy nú vào stack • pop (A): Loi phn t ủnh ngăn xp. 2. Lp khi stack chưa rng • getTop (A): Ly phn t ủnh ngăn xp. 2.1. Ly mt giỏ tr t stack 2.2. In ra
7. ðo ngưc danh sỏch – Vớ d ðo ngưc danh sỏch – Mó C++ Cn nhp 4 s vào #include s dng STL Ban ủu Nhp 1 Nhp 5 Nhp 7 Nhp 3 using namespace std; (Standard Template Library) 3 int main( ) { khai bỏo mt stack cú kiu d liu ca cỏc phõn t bờn trong là double 7 7 int n; double item; 5 5 5 stack numbers; 1 1 1 1 cout > n; ủy mt s vào trong stack Stack ủó rng for (int i = 0; i 3 Ly ra => 7 Ly ra => 5 Ly ra => 1 Ngng cin >> item; kim tra xem stack cú khỏc rng khụng numbers.push(item); 3 } ly giỏ tr trờn ủnh ca stack ra, stack khụng ủi 7 7 while (!numbers.empty( )) { cout =1): b th t (Sn1, t) • 4. B giỏ tr ủang cú trờn ủnh ca stack ( pop ) • Sn1: dóy cú chiu dài n1 thuc kiu T • 5. Ly giỏ tr trờn ủnh ca stack, stack khụng ủi (top ) • t là mt giỏ tr thuc kiu T.
8. Thit k stack Thit k cỏc phương thc template bool Stack ::empty() const ; enum Error_code {fail, success, overflow, underflow}; Pre : Khụng cú Post : Tr v giỏ tr true nu stack hin ti là rng, ngưc li thỡ tr v false template template class Stack { Error_code Stack ::push( const Entry &item); public : Pre : Khụng cú Stack(); //constructor Post : Nu stack hin ti khụng ủy, item s ủưc thờm vào ủnh ca stack. Ngưc li tr v giỏ tr overflow ca kiu Error_code và stack khụng ủi. bool empty() const ; //kim tra rng Error_code push( const Entry &item); //ủy item vào template Error_code pop(); //b phn t trờn ủnh Error_code Stack ::pop() const ; Pre : Khụng cú Error_code top(Entry &item); //ly giỏ tr trờn ủnh Post : Nu stack hin ti khụng rng, ủnh ca stack hin ti s b hy b. //khai bỏo mt s phương thc cn thit khỏc Ngưc li tr v giỏ tr underflow ca kiu Error_code và stack khụng ủi. private : template //khai bỏo d liu và hàm ph tr ch này Error_code Stack ::top(Entry &item) const ; }; Pre : Khụng cú Post : Nu stack hin ti khụng rng, ủnh ca stack hin ti s ủưc chộp vào tham bin item. Ngưc li tr v giỏ tr fail ca kiu Error_code. Hin thc stack liờn tc Khai bỏo stack liờn tc const int maxstack = 10; //small number for testing template class Stack { public : Stack( ); bool empty( ) const ; Error_code pop( ); Error_code top(Entry &item) const ; Error_code push(const Entry &item); private : int count; Entry entry[maxstack]; };
9. ðy mt phn t vào stack B phn t trờn ủnh stack • Gii thut: • Gii thut: 1. Nu cũn ch trng trong stack 1. Nu cũn phn t trong stack 1.1. Tăng v trớ ủnh lờn 1 1.1. Gim v trớ ủnh ủi 1 1.2. Cha giỏ tr vào v trớ ủnh ca stack 1.2. Gim s phn t ủi 1 1.3. Tăng s phn t lờn 1 top 7 7 5 top 5 1 count=2count=3 1 count=3count=2 Thờm/B phn t Mó C++ Ly giỏ tr trờn ủnh stack template Error_code Stack :: push( const Entry &item) { • Gii thut: if (count >= maxstack) 1. Nu cũn phn t trong stack return overflow; 1.1. Tr v giỏ tr ti v trớ ủnh else entry[count++] = item; • Mó C++: return success; } template Error_code Stack :: top(Entry &item) { template if (count == 0) Error_code Stack :: pop() { if (count == 0) return underflow; return underflow; else else item = entry[count 1]; count; return success; return success; } }
10. Ký phỏp Ba Lan ủo Ký phỏp Ba Lan ủo – Thit k chc năng • Mụ t bài toỏn: • Tp lnh: – Cỏc toỏn hng ủưc ủc vào trưc và ủy vào – ‘?’: ủc mt giỏ tr ri ủy vào stack stack – Toỏn t ‘+’, ‘’, ‘*’, ‘/’: ly 2 giỏ tr trong stack, – Khi ủc vào toỏn t, ly hai toỏn hng ra t stack, tớnh toỏn và ủy kt qu vào stack tớnh toỏn vi toỏn t này, ri ủy kt qu vào stack – Toỏn t ‘=’: in ủnh ca stack ra • Thit k phn mm: – ‘q’: kt thỳc chương trỡnh – Cn mt stack ủ cha toỏn hng – Cn hàm get_command ủ nhn lnh t ngưi dựng – Cn hàm do_command ủ thc hin lnh Ký phỏp Ba Lan ủo – Vớ d Ký phỏp Ba Lan ủo Hàm get_command char get command( ) { Tớnh toỏn biu thc: 3 5 + 2 * = char command ; bool waiting = true; cout :" ; 5 5 while (waiting) { cin >> command ; 3 3 3 8 command = tolower(command); Ban ủu Toỏn t ? Toỏn t ? Toỏn t + ðy 8 vào if (command == ‘?’ || command == ‘=‘ || command == ‘+’ || command == ‘−’|| command == ‘*’ || command == ‘/’ || Nhp vào 3 Nhp vào 5 Ly ra 5 và 3 command == ‘q’) waiting = false; Tớnh 3 + 5 => 8 else { cout 16 }
11. Ký phỏp Ba Lan ủo Gii thut tớnh toỏn Ký phỏp Ba Lan ủo Toỏn t cng Algorithm Op_process if (numbers.top(p) == underflow) Input : toỏn t op , stack cha cỏc toỏn hng cout > p ; char get_command( ); if (numbers .push(p) == overflow) bool do_command( char command, Stack &numbers); cout stored_numbers; else cout << p << endl ; break; introduction( ); instructions( ); // Add options for further user commands. while (do_command(get_command( ), stored_numbers)); case ‘q’: cout << "Calculation finished.\n" ; return false; } } //implementation return true; }
12. 4. Queue Queue tru tưng • Mt queue là mt cu trỳc d liu mà cỏc phộp toỏn • Mt queue kiu T: thc hin 2 ủnh , mt ủnh gi là ủu hàng, mt – Mt dóy hu hn kiu T ủnh gi là cui hàng. – Mt s tỏc v: • Phn t vào trưc s ra trưc – FIFO ( First In First • 1. Khi to queue rng (create ) Out) • 2. Kim tra rng (empty ) • 3. Thờm mt giỏ tr vào cui ca queue ( append ) • 4. B giỏ tr ủang cú ủu ca queue ( serve ) • 5. Ly giỏ tr ủu ca queue, queue khụng ủi (retrieve ) Thit k queue Thit k cỏc phương thc template bool Queue ::empty() const ; enum Error_code {fail, success, overflow, underflow}; Pre : Khụng cú Post : Tr v giỏ tr true nu queue hin ti là rng, ngưc li thỡ tr v false template template class Queue { Error_code Queue ::append( const Entry &item); public : Pre : Khụng cú Queue(); //constructor Post : Nu queue hin ti khụng ủy, item s ủưc thờm vào cui ca queue. bool empty() const ; //kim tra rng Ngưc li tr v giỏ tr overflow ca kiu Error_code và queue khụng ủi. Error_code append( const Entry &item); //ủy item vào template Error_code serve(); //b 1 phn t ủu Error_code Queue ::serve() const ; Pre : Khụng cú Error_code retrieve(Entry &item); //ly giỏ tr ủu Post : Nu queue hin ti khụng rng, ủu ca queue hin ti s b hy b. //khai bỏo mt s phương thc cn thit khỏc Ngưc li tr v giỏ tr underflow ca kiu Error_code và queue khụng ủi. private : template //khai bỏo d liu và hàm ph tr ch này Error_code Queue ::retrieve(Entry &item) const ; }; Pre : Khụng cú Post : Nu queue hin ti khụng rng, ủu ca queue hin ti s ủưc chộp vào tham bin item. Ngưc li tr v giỏ tr underflow ca kiu Error_code.
13. M rng queue Tớnh tha hưng • Cú thờm cỏc tỏc v: • Dựng tớnh tha hưng: – Kim tra ủy (full ) – Extended_queue cú ủy ủ cỏc thành phn ca Queue – Tớnh kớch thưc (size ) – Gii phúng queue ( clear ) – Thờm vào ủú cỏc thành phn riờng ca mỡnh – Ly giỏ tr ủu và b ra khi queue ( serve_and_retrieve ) • Mó C++: template class Extended_queue : public Queue { public : bool full( ) const ; Cú cỏc kh năng public , int size( ) const ; protected , private void clear( ); Error_code serve_and_retrieve(Entry &item); }; Queue liờn tc Queue là array vũng (circular array) • Dựng mt array: Cú xu hưng di v cui array • Hai cỏch hin thc ủu tiờn: – Khi ly mt phn t ra thỡ ủng thi di hàng lờn mt v trớ. A B C D B C D B C D E Ban ủu Ly ra 1 phn t: Thờm vào 1 phn t di tt c v trưc – Ch di hàng v ủu khi cui hàng khụng cũn ch A B C D B C D B C D E Ban ủu Ly ra 1 phn t Thờm vào 1 phn t: di tt c v trưc ủ trng ch thờm vào
14. Array vũng vi ngụn ng C++ ðiu kin biờn ca queue vũng • Xem array như là mt vũng: – phn t cui ca array ni vi phn t ủu ca array • Tớnh toỏn v trớ k: – i = ((i + 1) == max) ? 0 : (i + 1); – if ((i + 1) == max) i = 0; else i = i + 1; – i = (i + 1) % max; Mt s cỏch hin thc queue liờn tc Hin thc queue liờn tc • Mt array vi front là phn t ủu và tt c cỏc phn const int maxqueue = 10; // small value for testing t s ủưc di lờn khi ly ra mt phn t. • Mt array cú hai ch mc luụn tăng ch ủn phn t template class Queue { ủu và cui. public : • Mt array vũng cú ch mc front và rear và mt ụ Queue( ); bool empty( ) const ; luụn trng. Error_code serve( ); • Mt array vũng cú ch mc front và rear và mt c Error_code append( const Entry &item); (flag) cho bit queue là ủy (rng) chưa. Error_code retrieve(Entry &item) const ; protected : • Mt array vũng vi ch mc front và rear cú cỏc giỏ int count; tr ủc bit cho bit queue ủang rng. int front, rear; Entry entry[maxqueue]; • Mt array vũng vi ch mc front và rear và mt s cha }; s phn t ca queue.
15. Khi to và kim tra rng Thờm mt giỏ tr vào queue • Khi to: • Gii thut: template 1. Nu hàng ủy Queue ::Queue( ) { 1.1. Bỏo li overflow count = 0; 2. Tớnh toỏn v trớ cui mi theo array vũng rear = maxqueue − 1; 3. Gỏn giỏ tr vào v trớ cui mi này front = 0; 4. Tăng s phn t lờn 1 } 4. Bỏo success • Kim tra rng: Dựng bin count ủ front rear bit s phn t template trong queue bool Queue ::empty( ) const { A B C D return count == 0; } Loi mt giỏ tr khi queue Thờm/loi mt giỏ tr – Mó C++ • Gii thut: template 1. Nu hàng rng Error_code Queue ::append( const Entry &item) { if (count >= maxqueue) return overflow; 1.1. Bỏo li underflow count++; 2. Tớnh toỏn v trớ ủu mi theo array vũng rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1); 3. Gim s phn t ủi 1 entry[rear] = item; return success; 3. Bỏo success } template Error_code Queue ::serve() { front rear if (count <= 0) return underflow; count−−; A B C D front = ((front + 1) == maxqueue) ? 0 : (front + 1); return success; }
16. ng dng: Gi lp phi trưng Gi lp phi trưng – Hàng ủi • Mụ t: enum Runway_activity {idle, land, takeoff}; – 1. S dng hàng ủi runway cho vic ct và h cỏnh. class Runway { – 2. Mt mỏy bay cú th ct hoc h cỏnh trong mt ủơn v public : thi gian. Runway( int limit); Error_code can_land( const Plane ¤t); – 3. Ti mt thi ủim, s mỏy bay ủn là ngu nhiờn. Error_code can_depart( const Plane ¤t); – 4. Mỏy bay h cỏnh ủưc ưu tiờn trưc mỏy bay ct cỏnh. Runway_activity activity( int time, Plane &moving); void shut_down( int time) const ; – 5. Cỏc mỏy bay ch ct/h cỏnh ủưc cha vào cỏc hàng private : ủi tương ng và vi s lưng gii hn. Extended queue landing; Extended queue takeoff; int queue_limit; }; Gi lp phi trưng – H cỏnh Gi lp phi trưng – X lý Error_code Runway :: can_land( const Plane ¤t) { Runway_activity Runway::activity( int time, Plane &moving) { Error_code result; Runway_activity in_progress; if (landing.size( ) < queue_limit) if (!landing.empty( )) { result = landing.append(current); landing.retrieve(moving); else in_progress = land; result = fail; landing.serve( ); num_land_requests++; } else if (!takeoff.empty( )) { if (result != success) takeoff.retrieve(moving); num_land_refused++; in_progress = takeoff; else takeoff.serve( ); num_land_accepted++; } else return result; in_progress = idle; } return in_progress; }
17. Gi lp phi trưng – Gi lp Cõu hi và tho lun for (int current_time = 0; current_time < end_time; current_time++) { int number_arrivals = variable.poisson(arrival_rate); for (int i = 0; i < number_arrivals; i++) { Plane current_plane(flight_number++, current_time, arriving); if (small_airport.can_land(current_plane) != success) current_plane.refuse( ); } int number_departures = variable.poisson(departure_rate); for (int j = 0; j < number_departures; j++) { Plane current_plane(flight_number++, current_time, departing); if (small_airport.can_depart(current_plane) != success) current_plane.refuse( ); } Plane moving_plane; switch (small_airport.activity(current_time, moving_plane)) { case land: moving_plane.land(current_time); break ; case takeoff: moving_plane.fly(current_time); break ; case idle: run_idle(current_time); } } 66