BÁo cáo thực hành cấu trúc dữ liệu

Chia sẻ: Le Hengo | Ngày: | Loại File: DOC | Số trang:7

Thêm vào BST

Báo xấu

168
lượt xem 30
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nếu mảng có thứ tự phần tử a luôn là min. Ý tưởng của thuật toán chọn trực tiếp mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế: chọn phần tử nhỏ nhất trong N phần tử

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: BÁo cáo thực hành cấu trúc dữ liệu

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO: TH CẤU TRÚC DỮ LIỆU Thành viên nhóm: 1. Lê Hoàng Long 2. Nguyễn Trường Lưu Nhóm học phần: 07B Lớp: 09T4 Đà Nẵng, 04/2011
NỘI DUNG BÁO CÁO Yêu cầu bài toán: Đề 1: Viết chuơng trình thực hiện các công việc sau: 1. Sắp xếp mảng tăng dần theo phương pháp chọn trực tiếp 2. Hãy tìm phần tử d theo phương pháp tìm kiếm nhị phân 3. Tìm phần tử lớn nhất trong mảng theo phương pháp đệ qui Giải quyết yêu cầu: Mở đầu: Bài toán đưa ra yêu cầu cần giải quyết trong mảng, do đó, để không mất tính tổng quát, ta sẽ nhập vào một mảng ngẫu nhiên. Hàm nhập mảng ngẫu nhiên void nhap(int n) { srand(unsigned) time(0)); for(i=0;i
1. Sắp xếp mảng theo phương pháp chọn trực tiếp a. Thuật toán Phương pháp chọn trực tiếp: Giải thuật • Ta thấy rằng, nếu mảng có thứ tự, phần tử ai luôn là min(ai, ai+1, ., an-1). Ý tưởng của thuật toán chọn trực tiếp mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế: chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành; sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có N phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện N-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy. 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í. Sơ đồ khối •
Cài đặt • Cài đặt thuật toán sắp xếp chọn trực tiếp thành hàm sapxep() void sapxep() //bang phuong phap chon truc tiep { int j,tam,min; for (i=0;i ai thì x chỉ có thể xuất hiện trong đoạn [ai+1 ,aN] của dãy , ngược lại nếu x < ai thì x chỉ có thể xuất hiện trong đoạn [a1 ,ai- 1] của dãy . Giải thuật tìm nhị phân áp dụng nhận xét trên đây để tìm cách giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành.
Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử aleft .. aright , các bước tiến hành như sau : Bước 1: left = 1; right = N; // tìm kiếm trên tất cả các phần • tử Bước 2: • mid = (left+right)/2; // lấy mốc so sánh • So sánh a[mid] với x, có 3 khả năng : • a[mid] = x: Tìm thấy. Dừng o a[mid] > x: //tìm tiếp x trong dãy con aleft .. amid -1 : o right =midle - 1; a[mid] < x: //tìm tiếp x trong dãy con amid +1 .. aright : o left = mid + 1; Bước 3: • Nếu left ?right //còn phần tử chưa xét ?tìm tiếp. • Lặp lại Bước 2. Ngược lại: Dừng; //Ðã xét hết tất cả các phần tử. • • Cài đặt Thuật toán tìm nhị phân có thể được cài đặt thành hàm BinarySearch: int tim(int d, int dau, int cuoi) // ham tim kiem bang pp nhi phan { int giua; if (d>a[cuoi] ||d
• Cài đặt: int max(int b,int i) { if(i++==N) return b; else { if(a[i]>b) b=a[i]; return max(b,i); } } Kết quả chạy chương trình: