BÀI TẬP MÔN THỰC HÀNH CẤU TRÚC DỮ LIỆU
*Thông tin sinh viên:
- Họ & Tên: Lê Thị Hồng Hà
- Mã sv: 102150218
- Số thứ tự: 06
- Lớp: 15TCLC1
- MSSV: 102150218
Bài làm:
Phần I: Mảng, con trỏ
1.

Sắp xếp mảng tăng dần theo phương pháp chọn trực tiếp
• Ý tưởng:
- Chọn phần tử nhỏ nhất trong n phần tử đầu, đưa phần tử này về vị trí
đầu của dãy. Tiếp tục quá trình với n-1 phần tử còn lại và bắt đầu từ vị
trí thứ 2, lặp lại quá trình trên cho dãy gồm n-1 phần tử còn lại.
- Thuật toán thực hiện n-1 lần để lần lượt đưa phần tử nhỏ nhất trong
dãy hiện hành về vị trí dẫn đầu.
• Các bước tiến hành như sau:
- Bước 1: i = 1;
- Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến
a[N]
- Bước 3 : Hoán vị a[min] và a[i]
- Bước 4 : Nếu i < N-1 thì i = i+1; Lặp lại Bước 2
- Ngược lại: Dừng. //N-1 phần tử đã nằm đúng vị trí.
Code:
#include<stdio.h>
#include<conio.h>
int a[100];
void main()
•



•

dãy, ngược lại nếu xx: // tìm tiếp x trong dãy con a(left)...a(mid-1):
right = mid-1;
+ a[mid]

tương tự sau một số hữu hạn bước thực hiện.
Ở mỗi bước thực hiện, dữ liệu đầu sẽ vào tiệm cận tới dữ liệu
dừng.
Là thuật giải trong đó có chứa thao tác gọi đến chính nó.
Có thể dẫn đến tiến trình gọi đệ qui không kết thúc, do không
thỏa điều kiện dừng (“phần mốc”).


4. Sắp xếp mảng giảm dần theo phương pháp nổi bọt:
• Ý tưởng:
- Cho vòng lặp Si chạy từ 1 tới (Sn-1):
- Lần lặp 1: Si = 1, lần lược so sánh với các vị trí khác bắt đầu từ
(Si + 1) tức là vị trí 2, nếu phần tử thứ 1 bé hơn các phần tử đứng sau
bắt đầu từ 2 thì hoán vị chúng.
- Lần lặp 2: Si = 2, lần lược so sánh với các vị trí khác bắt đầu từ
(Si + 1) tức là vị trí 3, nếu phần tử thứ 2 bé hơn các phần tử đứng sau
nó bắt đầu từ 3 thì hoán vụ chúng.
- Cứ như vậy cho đến khi ta lặp lần thứ (Sn – 1), lúc này biến Si = (Sn1), ta so sánh với phần tử cuối cùng (Sn) và hoán vị nếu không thỏa
mãn.
• Code:
for(i=0;ii;j--)


if(a[i]
else
return i; //tìm thấy x tại vị trí i
}

6. Tìm phần tử nhỏ nhất trong mảng (ko dùng đệ qui):
Ý tưởng:
- Gán min cho phần tử thứ nhất.
- Sau đó so sánh với các phần tử còn lại.
- Phần tử nào nhỏ hơn thì gán nó cho min;
• Code:
•

Int min(int *a,int n)
{
Int x;
x=a[0];
For(i=1;ia[i]) x=a[i];


}
Return a[i];