Cấu trúc dữ liệu và giải thuật

Mối quan hệ giữa cấu trúc dữ liệu và giải thuật

Cấu trúc dữ liệu + Giải thuật = Chương trình

Đánh giá cấu trúc dữ liệu và giải thuật

Các tiêu chuẩn đánh giá:

- Cấu trúc sữ liệu phải tiết kiệm bộ nhớ (bộ nhớ trong)

-Cấu trúc dữ liệu phải phản ảnh đúng thức tế của bài toán,

Cấu trúc dữ liệu phải dễ dàng trong thao tác dữ liệu.

Đánh giá độ phức tạp của thuật toán

-Dùng thời gian T(n) để đánh giá tương đối các thuật toán với nhau:

+ trường hợp tốt nhất :Tmin

+trường hợp xấu nhất :Tmax

Từ đó ước lượng được thời gian thực hiện trung bình của thuật toán Tavg.

Kiểu dữ liệu

-kiểu dữ liệu T có thể xem như là sự kết hợp của 2 thành phần:

-miền giá trị mà kiểu dữ liệu T có thể lưu trữ V,

-Tập hợp các phép toán để thao tác dữ liệu O.

T=<V,O>

Mỗi kiểu dữ liệu được đại diên bởi tên ( định danh),mỗi phần tử dữ liệu có kiểu T sẽ có giá trị trong miền Vvaf có thể được thực hiện trên các phép toán thuộc tập hợp các phép toán trong O.

Để lưu trữ phần tử dữ liệu này thường phải tốn một số Byte trong bộ nhớ ,số Byte này gọi là kích thước của dữ liệu.

Kỹ thuật tìm kiếm (Searching)

Các giải thuật tìm kiếm nội (Tìm kiếm trên dãy/mảng)

Giả sử chúng ta có một mảng M gồm N phần tử .vấn đề đặt ra là có hay không có phần tử có giá trị X trong mảng M ? nếu có thì nằm ở vị trí nào trong mảng M

Tìm kiếm tuyến tính(linear search)

Thuật toán tìm kiếm tuyến tính còn gọi là thuật toán tìm kiếm tuần tự (sequential Search)

a.tư tưởng :

lần lượt so sách các các phần tử của mảng M với giá trị X bắt đàu từ phần tử đầu tiên cho đến khi tìm thấy phần tử có giá trị X đã duyệt qua hết tất cả các phần tử cuả mảng M thì kết thúc.

b.thuật toán:

B1:k=1 //duyệt từ đầu mảng

B2:If M [k] ≠ X and k ≤ N //nếu chưa tìm thấy và cũng chưa duyệt hết mảng

B2.1 k++

B2.2 lập lại B2

B3 :If k ≤ N

Tìm thấy tại vị trí k

B4:Else

Không tìm thấy phần tử có giá trị X

B5 :kết thúc

c.Cài đạt thuật toán :

hàm LinearSearch có prototype:

int LinearSearch (T M[] , int N ,T X)

hàm thực hiện việc tìm kiếm phần tử có giá trị Xtreen mang M có N phần tử.Nếu tìm thấy , hàm trả về một số nguyên có giá trị từ 0 đến N-1 và vị trí tương ứng của phần tử tìm thấy .Trong trường hợp ngược lại hàm trả về giá trị -1 (không tìm thấy).Nội của hàm như sau:

int LinearSearch (T M[] , int N , T X)

{

Int k=0;

While (M[k])!= X && k < N

k++;

if(k<N)

return (k);

return (-1);

}

d. phân tích thuật toán :

-trường hợp tốt nhất khi phần tử đàu tiên của mảng có giá trị bằng X:

Số phép gán :Gmin =1

Số phép so sánh :Smin =2+1=3

-Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:

Số phép gán Gmax =1

Số phép so sánh Smax =2n+1

-Trung bình:

Số phép gán Gavg =1

Số phép so sánh Savg =(3 + 2N +1):2 =N +2

e. cải tiến thuật toán :

trong thuật toán trên ở mỗi bước lặp chúng ta phải thực hiên 2 phép so sánh để kiểm tra sự tìm thấy và soát sự hết mảng trong quá trình duyệt mảng .chúng ta có thể giảm bớt 1 phép toán so sánh nếu chúng ta thêm vào cuối mảng 1 phần tử cầm canh (sentinel / stand by) có giá trị bằng X đẻ nhận diện ra sự hết mảng khi f=duyệt mảng , khi đó thuậ toán này được cải tiến :

B1 :k=1

B2 :M[N+1] =X //phần tử cầm canh

B3 :If(M[k] ≠ X)

B3.1 k++;

B3.2 lặp lại B3

B4: If(k<N)

Tìm thấy tại vị trí k

B5 Else // k=N song nó chi là phần tử canh

Không tìm thấy phần tử có giá trị X

B6 :kết thúc

Hàm LinearSearch được viết lại như sau:

Int LinearSearch (T M[] ,ỉn N , T X)

{

Int k=0;

M[N]=X;

While (M[k]!= X)

K++;

If (k<N)

Return (k);

Return (-1);

}

f.phân tích thuật toán cải tiến:

-trường hợp tốt nhất phần tử đầu tiên của mảng có giá trị X:

Số phép gán :Gmin =2

Số phép so sánh :smin =1+1 =2

-trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:

Số phép gán Gmax =2

Số phép so sánh Savg =(2 + N + 2):2 =N/2 +2

- Như vậy nếu thời gian thực hiên phép gán không đáng kể thì thuật toan cải tiến sẽ chạy nhanh hơn thuật toán nguyên thủy.

Tìm kiếm nhị phân (Binary Search)

Thuật toán tìm tuyến tính chỉ áp dụng được nếu dữ liệu nhỏ còn đối với dữ liệu lớn nó tỏ ra không hiệu quả vì vậy ta phải dung thuật toán khác đối với khối dữ liệu lớn đó là thuật toán tìm kiếm nhị phân :

Trong thuật toán này chúng ta giả sử các phần tử trong dãy có giá trị đã có thứ tự tăng (không giảm dần ),tức là các phần tử đứng trước luôn có giá trị nhỏ hợn hoặc bằng (không lớn hơn) phần tử đừng sau nó .

Khi đó , nếu X nhỏ hơn giá trị phần tử đứng ở giữa dãy (M[Mid]) thì X chí có thể tìm thấy ở nửa đầu của dãy và ngược lại , nếu X lớn hơn phần tử M[Mid] thì X chỉ có thể ở nửa sau của dãy.

a.tư tưởng :

phạm vi tìm kiếm ban đầu của chúng ta là từ đầu tiên của dãy(First =1) cho đến phần tử cuối cùng của dãy (Last =N)

so sánh giá trị X với giá trị phần tử đứng ở giữa của dãy M là M[Mid].

Nếu X=M[Mid ]:tìm thấy

Nếu X<M[Mid ]:rút ngắn phạm vi tìm kiếm về nửa đầu của dãy M(Last =Mid -1)

Nếu X> M[mid ]:rút ngắn phạm vi tìm kiếm về nửa sau của dãy M (First =Mid +1)

Lặp lại quá trình này cho đến khi tìm thấy phần tử có giá trị X hoặc phạm vi tìm kiếm của chúng ta không còn nữa (First >Last)

b.Thuật toán đê quy (Recursion Algorithm)

B1: First =1

B2:Last =N

B3:if (First >Last) //hết phạm vi tìm kiếm

B3.1 không tìm thấy

B3.2 Thực hiện Bkt

B4: Mid = ( First +Last ) /2

B5 : if(X = M[Mid])

B5.1 :tìm thấy tai vị trí Mid

B5.2:thực hiện Bkt

B6 :if(X > M[Mid])

Tìm đệ quy từ First đến Last = Mid -1

B7: if(X < M[Mid ])

Tìm đệ quy từ First =Mid +1 đến Last

Bkt : Kết thúc

c.Cài đặt thuật toán đệ quy :

hàm BinarySearch có prototype:

int BinarySearch(T M[], int N ,T X)

hàm thực hiện việc tìm kiếm phần tử có giá trị X trong mảng M có N phần tử đã có thứ tự tăng .Nếu tìm thấy , hàm trả về một số nguyên có giá trị từ 0 đến N-1 là vị trí tương ứng của phần tử tìm thấy.Trong trường hợp ngược lại , hàm trả về giá trị -1(không tìm thấy ). Hàm BinarySearch có prototype:

int ReBinarySearch(T M[] ,int First ,int Last , T X);

hàm ReBinarySearch thực hiện việc tìm kiếm phần tử có giá tri X trên mảng M trong phạm vi phần tử thứ First đến phần tử thứ Last. Nếu tìm thấy , hàm trả về một trong số nguyên có giá trị từ First đến Last là vụ trí của phần tử tìm thấy.

Trong trường hợp ngược lại , hàm trả về giá trị -1(không tìm thấy ) .Nội dung cyar các hàm như sau:

Int ReBinarySearch(T M[] , int First, int Last ,T X)

{

If(First > Last)

Return (-1);

Int Mid =( First +Last)/2

If(X== M[Mid])

Return (Mid)

If(X < M[Mid])

Return (ReBinarysearch(M, First ,Mid -1 ,X));

Else

Return (ReBinarySearch(M. Mid+1 ,Last ,X));

}

//======================================================

Int BinarySearch(T M, int N ,T X)

{ Return (RebinarySearch(M,0,N-1,X));

}

d.Phân tích thuật toán đệ quy:

-Trường hợp tốt nhất khi phần tử ở giữa của mảng có giá trị bằng X:

Số phép gán :Gmin= 1

Số phép so sánh Smin =2

-Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:

Số phép gán :Gmax =log2N+1

Số phép so sánh Smax =3log2N + 1

-trung bình :

Số phép gán :Gavg = log2N + 1

Số phép so sánh :Savg = (3log2N + 3)

e. Thuật toán không đệ quy (Non-Recursion Algorithm):

B1: First =1

B2:Last =N

B3 if(First > Last)

B3.1 không tìm thấy

B3.2 thực hiện Bkt

B4: Mid = (First + Last)/2

B5:if(X = M[Mid])

B5.1 tìm thấy tại vị trí Mid

B5.2 thực hiện Bkt

B6:if(X < M[Mid])

B6.1:Last =mid -1

B6.2:lặp lại B3

B7: if(X > M[Mid])

B7.1Fist =Mid +1

B7.2 lặp lại B3

Bkt :kết thúc