Kỹ Thuật Lập Trình Dùng Mảng - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.docx) (23 trang)

Trang chủ

Công Nghệ Thông Tin

Kỹ thuật lập trình

Kỹ thuật lập trình dùng mảng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (173.13 KB, 23 trang )

Kỹ thuật lập trình dùng mảngI. Mảng một chiềuI.1. Khai niệm và cách khai báoBài toán: hãy lưu trữ một dãy số gồm 5 phần tử: {2, 5, 3, 6, 7}Cách 1: Sử dụng 5 ô nhớ (5 biến) cùng kiểu. Các biến được đặt tên lần lượt là: a, b, c, d, e. Khi đó, các phần tử được chứa trong 5 ô nhớ này như sau:25367a b c d eVì cần lưu trữ 5 giá trị khác nhau nên việc dùng 5 ô nhớ khác nhau là cần thiết. Tuy nhiên, phương pháp này tỏ không khả thi do sử dụng quá nhiều tên biến, dẫn tới khó kiểm soát các biến, đặc biệt trong trường hợp số phần tử của dãy quá lớn.Cách 2: Vẫn sử dụng 5 ô nhớ cùng kiểu nhưng tất cả các ô được đặt chung một tên (a chẳng hạn). Để phân biệt các ô với nhau, người ta đánh chỉ số cho từng ô. Chỉ số là các số nguyên liên tiếp, tính từ 0. Như vậy ta thu được:25367 a[0] a[1] a[2] a[3] a[4]Kết quả ta có được một cấu trúc dữ liệu khắc phục được nhược điểm của cách 1. Cấu trúc dữ liệu này gọi là mảng một chiều.Mảng là một cấu trúc bộ nhớ bao gồm một dãy liên tiếp các ô nhớ cùng tên, cùng kiểu nhưng khác nhau về chỉ số, dùng để lưu trữ một dãy các phần tử cùng kiểu.Cú pháp khai báo mảng:<Kiểu mảng> <Tên mảng> [<Số phần tử tối đa>];Trong đó:<Kiểu mảng>: Là kiểu dữ liệu của mỗi phần tử trong mảng, có thể là một kiểu dữ liệu chuẩn hoặc kiểu dữ liệu tự định nghĩa.<Tên mảng>: Được đặt tuỳ ý tuân theo quy ước đặt tên biến trong C++.<Số phần tử tối đa>: Là một hằng số chỉ ra số ô nhớ tối đa được dành cho mảng cũng như số phần tử tối đa mà mảng có thể chứa được.Ví dụ: Khai báo int a[3]; sẽ cấp phát 3 ô nhớ liên tiếp cùng kiểu nguyên (2 byte) dành cho mảng a. Mảng này có thể chứa được tối đa 3 số nguyên.I.2. Các thao tác cơ bản trên mảng một chiều- Nhập mảng: Giả sử ta cần nhập mảng a gồm n phần tử. Cách duy nhất là nhập từng phần tử cho mảng. Do vậy, ta cần sử dụng một vòng lặp for duyệt qua từng phần tử và nhập dữ liệu cho chúng. Nhưng trước tiên, cần nhập số phần tử thực tế của mảng (n).for(int i=0; i<n; i++){ cout<< “a[“<<i<< “]=”; cin>>a[i];}- Xuất mảng: tương tự như nhập mảng, ta cũng cần sử dụng vòng lặp for để xuất từng phần tử của mảng lên màn hình.for(i = 0; i<n; i++)cout<<a[i];cout<<a[i]<< “ ”;cout<<a[i]<<endl;- Duyệt mảng: là thao tác thăm lần lượt từng phần tử của mảng. Thao tác duyệt mảng có trong hầu hết các bài toán sử dụng mảng. for(i = 0; i<n; i++) {thăm phần tử a[i]}I.3. Các bài toán cơ bảna. Bài toán sắp xếp mảngBài toán: cho một dãy gồm n phần tử. Hãy sắp xếp dãy theo chiều tăng dần.Để giải quyết bài toán này, trước tiên ta cần lưu trữ dãy các phần tử đã cho vào bộ nhớ, như vậy ta cần sử dụng một mảng một chiều. Sau đó, có rất nhiều phương pháp để sắp một mảng theo chiều tăng dần. Sau đây ta xem xét một số cách phổ biến:• Phương pháp 1: Sắp xếp nổi bọt – bubble sortý tưởng của phương pháp như sau:- Sắp lần lượt từng phần tử của dãy, bắt đầy từ phần tử đầu tiên.- Giả sử cần sắp phần tử thứ i, ta tiến hành duyệt lần lượt qua tất cả các phần tử đứng sau nó trong dãy, nếu gặp phần tử nào nhỏ hơn phần tử đang sắp thì đổi chỗ.Giả sử ta sắp mảng a gồm n phần tử, giải thuật được mô tả chi tiết như sau:for(i = 0; i < n; i++)// với mỗi phần tử a[i]for(j = i+1; j<n; j++) if(a[j] < a[i]) Đổi chỗ a[i] cho a[j]Để đổi chỗ a[i] cho a[j], ta sử dụng một biến tg có cùng kiểu và gán một trong 2 giá trị (a[i] hoặc a[j]) vào đó. Sau đó gán giá trị còn lại sang giá ô nhớ vừa gán vào tg. Cuối cùng ta gán giá trị đang chứa trong tg vào ô nhớ này.for(i = 0; i < n; i++)for(j = i+1; j<n; j++)if(a[j] < a[i]){ tg = a[i]; a[i] = a[j]; a[j] = tg;}Sắp xếp bằng phương pháp này trung bình cần n2/ 2 lần so sánh và n2/2 lần hoán vị. Trong trường hợp tồi nhất ta cũng cần số lần so sánh và hoán vị như vậy.Giả sử ta có mảng a = {3, 5, 2, 7, 4, 8}. Hình ảnh của a sau các lần lặp sắp xếp nổi bọt như sau:Bắt đầu sắp i = 03 5 2 7 4 8Hết 1 vòng lặp j; i = 1;2 5 3 7 4 8Hết một vòng j; i=2;2 3 5 7 4 8Hết một vòng j; i=3;2 3 4 7 5 8Hết một vòng j; i=4;2 3 4 5 7 8• Phương pháp sắp xếp chọn – Selection sortTrong phương pháp sắp sếp nổi bọt, để sắp một phần tử nhiều khi ta phải đổi chỗ nhiều lần phần tử đang sắp với các phần tử đứng sau nó. Một ý tưởng rất hay là làm sao chỉ đổi chỗ 1 lần duy nhất khi sắp một phần tử trong dãy. Đây chính là ý tưởng của phương pháp sắp xếp chọn.Để làm được điều này, khi sắp phần tử thứ i, người ta tiến hành tìm phần tử nhỏ nhất trong số các phần tử đứng sau nó kể cả phần tử đang sắp rồi tiến hành đổi chỗ phần tử nhỏ nhất tìm được với phần tử đang sắp.Ví dụ: Với dãy a = {1, 6, 4, 2, 5, 7}, để sắp phần tử thứ 2 (6) người ta tiến hành tìm phần tử nhỏ nhất trong số các phần tử {6, 4, 2, 5, 7}. Khi đó Min(6, 4, 2, 5, 7) = 2 và phần tử 2 được đảo chỗ cho phần tử 6. Kết quả thu được:Trước tiên ta xem xét bài toán tìm phần tử nhỏ nhất của một dãy các phần tử:- Lấy một phần tử ngẫu nhiên trong dãy làm phần tử nhỏ nhất (Min) (thường lấy phần tử đầu tiên). - Duyệt qua tất cả các phần tử của dãy, nếu gặp phần tử nào nhỏ hơn Min thì gán Min bằng phần tử đó.Ví dụ: Tìm số nhỏ nhất trong mảng a gồm n phần tử:Min = a[0];for(i = 0; i<n; i++)if (a[i] < Min) Min = a[i];Khi kết thúc vòng lặp, ta thu được giá trị nhỏ nhất của dãy đang chứa trong biến Min.Tuy nhiên, áp dụng giải thuật này vào phương pháp sắp xếp chọn ta cần phải lưu ý một số điểm. Chẳng hạn ta cần biết chính xác vị trí của phần tử Min nằm ở đâu để tiến hành đổi chỗ chứ không quan tâm tới giá trị Min là bao nhiêu. Tuy nhiên giải thuật tìm Min lại chỉ cho biết giá trị Min mà không cho biết vị trí. Nếu muốn biết, ta lại phải sử dụng 1 vòng lặp duyệt lại từ đầu để tìm 1vị trí Min. Do vậy, khi cài đặt phương pháp sắp xếp chọn, để tránh trường hợp sử dụng nhiều vòng lặp sẽ làm tăng độ phức tạp của giải thuật, ta chỉ chú ý tới việc tìm vị trí phần tử Min.- Sắp xếp từng phần tử của dãy, bắt đầu từ phần tử đầu tiên.- Giả sử sắp phần tử a[i], ta gán Min = i rồi duyệt qua các phần tử đứng sau nó (i+1 trở đi). Nếu phần tử a[j] nào nhỏ hơn phần tử a[Min] thì gán Min bằng vị trí của a[j] (tức Min=j). Cuối cùng ta đổi chỗ a[i] cho a[Min].for(i = 0; i < n; i++){ Min = i; for(j = i+1; j<n; j++) if(a[j] < a[Min]) Min = j; tg = a[i];a[i] = a[Min];a[Min] = tg;}Sắp xếp bằng phương pháp chọn cần n2/2 lần so sánh và n lần hoán vị.Giả sử ta có mảng a = {3, 5, 2, 7, 4, 8}. Hình ảnh của a qua các lần lặp sắp xếp chọn như sau:3 5 2 7 4 8Min = 22 5 3 7 4 8Min = 32 3 5 7 4 8Min = 42 3 4 7 5 8Min = 52 3 4 5 7 8Min = 72 3 4 5 7 8Min = 8Sau đây là hàm sắp xếp chọn với đối vào là mảng a gồm n phẩn tử:void SapChon(int a[100], int n){for (int i=0; i<n-1; i++){int min = i;for (int j = i+1; j<n; j++)if (a[j] < a[min]) min = j;int tg = a[i];a[i] = a[min];a[min]=tg;}}• Phương pháp sắp xếp chènMột thuật toán gần như đơn giản ngang với thuật toán sắp xếp chọn nhưng có lẽ mềm dẻo hơn, đó là sắp xếp chèn. Đây là phương pháp người ta dùng để sắp xếp các thanh ngang cho một chiếc thang.Đầu tiên, người ta rút ngẫu nhiên 1 thanh ngang và đặt vào 2 thanh dọc để làm thang. Tiếp đó, người ta lần lượt chèn từng thanh ngang vào sao cho không phá vỡ tính được sắp của các thanh đã được đặt trên 2 thanh dọc.Giả sử với mảng a = {3, 5, 2, 7, 4, 8}. Giả sử các phần tử 3 và 5 đã được chèn vào đúng vị trí (đã được sắp):3 5 2 7 4 83 5 7 4 83 5 7 4 82 3 5 7 4 82TgTa xem xét quá trình chèn phần tử tiếp theo vào mảng (giả sử chèn 2 vào). Khi đó, quá trình diễn ra như sau:- Đặt phần tử 2 vào biến tg.- Duyệt qua các phần tử đứng trước phần tử 2 (các phần tử đã được sắp). Nếu gặp phần tử nào lớn hơn 2 thì đẩy phần tử đó sang phải 1 vị trí. Ngược lại, nếu gặp phần tử nhỏ hơn 2 thì chèn 2 vào ngay sau phần tử nhỏ hơn này. Nếu đã duyệt hết các phần tử đứng trước mà vẫn chưa tìm thấy phần tử nhỏ hơn 2 thì chèn 2 vào đầu mảng.Kết thúc quá trình này, phần tử 2 đã được chèn đúng vị trí và 3 phần tử đã được sắp là:32Toàn bộ quá trình sắp mảng a được biểu diễn trong bảng sau:3 5 2 7 4 833 52 3 52 3 5 72 3 4 5 72 3 4 5 7 8Như vậy trong quá trình thực hiện, để chèn 1 phần tử vào đúng vị trí của nó, ta luôn thực hiện 2 công việc: Đẩy một phần tử sang phải 1 vị trí hoặc chèn phần tử cần chèn vào vị trí của nó. Nếu gọi phần tử cần chèn là a[i] đang chứa trong biến tg và j là biến duyệt qua các phần tử đứng trước a[i] thì:- Khi chưa hết mảng và gặp một phần tử lớn hơn phần tử cần chèn thì đẩy nó sang phải 1 vị trí: while ( j >= 0 && a[j] > tg) a[j+1] = a[j]; - Ngược lại thì chèn tg vào sau j: a[j+1] = tg; void SapChen(int a[100], int n){for (int i=1; i< n; i++){int Tg = a[i]; int j = i-1;while (j > = 0 && a[j] > Tg) { a[j+1] = a[j];j--; }a[j+1]=Tg;}}Sắp xếp bằng phương pháp chèn trong trường hợp trung bình cần n2/ 4 lần so sánh và n2/ 8 lần hoán vị. Trường hợp tồi nhất gấp đôi số lần này.• Phương pháp sắp xếp trộn: Merge sortBài toán trộn: Cho mảng a gồm n phần tử và mảng b gồm m phần tử đã sắp tăng. Hãy trộn hai mảng để thu được một mảng thứ 3 cũng được sắp tăng.Trước tiên, ta xét hai mảng a và b như ví dụ như sau:Mảng c sau thu được sau khi trộn a và b là:Để có được mảng c, ta làm như sau:B1. Cho biến i xuất phát từ đầu mảng a (i=0) và biến j xuất phát từ đầu mảng b (j=0). B2. Ta so sánh a[i] và a[j] rồi lấy phần tử nhỏ hơn trong hai phần tử đó đặt vào mảng c. Nếu lấy a[i], ta phải tăng i lên 1 đơn vị (i++) và tương tự, nếu lấy b[j], ta tăng j lên 1 đơn vị (j++). Lặp lại B2 cho tới khi 1 trong 2 mảng đã được lấy hết.Với mảng a,b ở trên, dễ thấy giải thuật trên sẽ dừng lại khi mảng a đã được lấy hết. Tuy nhiên, khi đó, mảng b vẫn còn các phần tử 6, 7, 9, 10 chưa được lấy. Công việc tiếp theo là chuyển toàn bộ các phần tử “còn thừa” này từ b sang c.Hàm sau thực hiện trộn 2 mảng a, b theo thuật toán trên.int c[100];void Tron(int a[50],int n, int b[50], int m){int i=0, j=0, k=0;while(i<n&&j<m)if(a[i]<b[j]) {c[k]=a[i]; i++; k++;}else {c[k]=b[j]; j++; k++;}// Gắn đuôi------------------------------if(i<n) for(int t=i; t<n; t++) {c[k]=a[t]; k++;}else for(int t=j; t<m; t++) {c[k]=b[t]; k++;}}Dễ thấy quá trình cho i chạy trên a và j chạy trên b sẽ buộc phải dừng lại khi 1 trong 2 mảng đã được duyệt hết. Nếu không, biến i hoặc j sẽ chạy quá giới hạn của mảng a hoặc b. Khi dừng lại, một trong 2 mảng có thể chưa được duyệt hết và còn thừa một số phần tử và quá trình chuyển các phần tử này sang c được diễn ra.bacMột cải tiến nhỏ giúp cho i và j không bao giờ chạy vượt quá giới hạn của 2 mảng a và b cho tới khi ta lấy xong tất cả các phần tử của a và b đặt sang c. Muốn vậy, trước khi thực hiện giải thuật trên, ta làm như sau:- Gọi Max là phần tử lớn nhất trong số các phần tử của cả a và b.- Chèn giá trị Max + 1 vào vị trí cuối cùng của mảng a và mảng b.Với mảng trên, giá trị Max = 10 và hai mảng sau khi chèn Max+1 vào cuối sẽ có dạng:Khi i hoặc j chạy tới cuối mảng, ta gặp phải giá trị 11 là giá trị lớn hơn bất kỳ giá trị mào của hai mảng a và b ban đầu, do đó, theo giải thuật thì i và j sẽ bị dừng lại tại đó và không thể chạy vượt ra khỏi giới hạn của mảng.int c[100];void Tron2(int a[50],int n, int b[50], int m){int Max=a[n-1];if(Max<b[m-1]) Max=b[m-1];a[n]=b[m]=Max+1;//------------------------int i=0, j=0;for(int k=0; k<n+m; k++)if(a[i]<b[j]) {c[k]=a[i]; i++;}else {c[k]=b[j]; j++;}}ý tưởng của giải thuật sắp xếp trộn như sau:- Giả sử có mảng a chưa sắp:- Chia mảng a làm hai phần bằng nhau và sắp trên 2 nửa của a.- Trộn 2 nửa đã sắp để thu được mảng a cũng được sắp:ba

Tài liệu liên quan

Kỹ thuật lập trình C
- 134
- 1
- 11
Chương 4 Kỹ thuật lập trình dùng mảnh
- 17
- 418
- 1
Chương 5 Kỹ thuật lập trình dùng con trỏ
- 8
- 562
- 2
Kỹ thuật lập trình dùng con trỏ
- 10
- 1
- 28
Kỹ thuật lập trình dùng mảng
- 23
- 414
- 2
Kỹ thuật lập trình C/C++-Chương: Con trỏ, mảng và quản lý bộ nhớ pptx
- 17
- 595
- 5
Tài liệu Kỹ thuật lập trình - Chương 3: Kiểm tra và xây dựng số nguyên tố
- 19
- 631
- 0
Tài liệu Kỹ thuật lập trình - Chương 7 Kiểm tra và xây dựng số nguyên tố
- 81
- 538
- 0
Kỹ thuật lập trình - Ngôn ngữ lập trình C - Mảng docx
- 14
- 510
- 0
Kỹ thuật lập trình - Ngôn ngữ lập trình C - Mảng (tt) pot
- 10
- 347
- 1