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)
