Ktl-icon-tai-lieu

Tài liệu môn Cấu trúc Dữ Liệu

Được đăng lên bởi myvan
Số trang: 193 trang   |   Lượt xem: 5931 lần   |   Lượt tải: 0 lần
GIỚI THIỆU MÔN HỌC
Trong ngôn ngữ lập trình, dữ liệu bao gồm hai kiểu chính là :
- Kiểu dữ liệu đơn giản : char, int, long, float, enumeration, subrange.
- Kiểu dữ liệu có cấu trúc : struct, array, file (kiểu dữ liệu có kích thước
không đổi)...
Giáo trình này tập trung vào việc nghiên cứu các kiểu dữ liệu có cấu trúc
có kích thước không đổi hoặc thay đổi trong ngôn ngữ lập trình, mô tả thông qua
ngôn ngữ C. Ngoài ra còn giới thiệu các giải thuật chung quanh các cấu trúc dữ
liệu này như cách tổ chức, thực hiện các phép toán tìm kiếm, sắp thứ tự nội, sắp
thứ tự ngoại...
Điều kiện để có thể tìm hiểu rõ ràng về môn học này là học viên đã biết
các khái niệm về kỹ thuật lập trình trên ngôn ngữ C. Trong phần mở đầu, bài
giảng này sẽ giới thiệu cách thức phân tích & thiết kế một giải thuật trước khi
tìm hiểu về các cấu trúc dữ liệu cụ thể.
Vào cuối khóa học, sinh viên có thể:
- Phân tích độ phức tạp của các chương trình có kích thước nhỏ và trung
bình.
- Nhận thức được sự cần thiết của việc thiết kế cấu trúc dữ liệu.
- Làm quen với các khái niệm stacks, queues, danh sách đặc, danh sách
liên kết, cây nhị phân, cây nhị phân tìm kiếm, ....
- Hiểu được nguyên lý của việc xây dựng một chương trình máy tính.
- Có thể chọn lựa việc tổ chức dữ liệu phù hợp và các giải thuật xử lý dữ
liệu có hiệu quả trong khi xây dựng chương trình. Sinh viên cần lưu ý rằng, tùy
vào công việc cụ thể mà ta nên chọn cấu trúc dữ liệu nào là thích hợp theo
hướng tối ưu về thời gian thực hiện hay tối ưu về bộ nhớ.

1

CHƯƠNG I
PHÂN TÍCH & THIẾT KẾ
GIẢI THUẬT
I. MỞ ĐẦU
Hầu hết các bài toán đều có nhiều giải thuật khác nhau để giải quyết chúng.
Vậy làm thế nào chọn được một giải thuật tốt nhất ?
Việc chọn lựa phụ thuộc vào nhiều yếu tố như : Độ phức tạp tính toán của
giải thuật, chiếm dung lượng bộ nhớ, tần suất sử dụng, tính đơn giản, tốc độ thực
hiện...
Thông thường mục tiêu chọn lựa là :
1. Giải thuật rõ ràng, dễ hiểu, dễ mã hóa và hiệu chỉnh.
2. Giải thuật sử dụng có hiệu quả tài nguyên của máy tính và đặc biệt
chạy càng nhanh càng tốt.
Do đó khi viết chương trình để chạy một lần hoặc ít chạy thì mục tiêu 1 là
quan trọng hơn cả.
Ngược lại khi viết chương trình để chạy nhiều lần thì phí tổn chạy chương
trình có thể vượt quá phí tổn lập chương trình, nhất là khi phải nhập nhiều số
liệu. Nói chung, người lập trình phải biết chọn lựa, viết, đánh giá các giải thuật
để có được giải thuật tối ưu cho bài toán của mình.
II. ĐÁNH GIÁ THỜI GIAN CHẠY CỦA CHƯƠNG TRÌNH
Thời gian chạy của chưong trình phụ ...
GII THIU MÔN HC
Trong ngôn ng lp trình, d liu bao gm hai kiu chính là :
- Kiu d liu đơn gin : char, int, long, float, enumeration, subrange.
- Kiu d liu có cu trúc : struct, array, file (kiu d liu có kích thước
không đổi)...
Giáo trình này tp trung vào vic nghiên cu các kiu d liu có cu trúc
có kích thước không đổi hoc thay đổi trong ngôn ng lp trình, mô t thông qua
ngôn ng C. Ngoài ra còn gii thiu các gii thut chung quanh các cu trúc d
liu này như cách t chc, thc hi
n các phép toán tìm kiếm, sp th t ni, sp
th t ngoi...
Điu kin để có th tìm hiu rõ ràng v môn hc này là hc viên đã biết
các khái nim v k thut lp trình trên ngôn ng C. Trong phn m đầu, bài
ging này s gii thiu cách thc phân tích & thiết kế mt gii thut trước khi
tìm hiu v các cu trúc d liu c th.
Vào cu
i khóa hc, sinh viên có th:
- Phân tích độ phc tp ca các chương trình có kích thước nh và trung
bình.
- Nhn thc được s cn thiết ca vic thiết kế cu trúc d liu.
- Làm quen vi các khái nim stacks, queues, danh sách đặc, danh sách
liên kết, cây nh phân, cây nh phân tìm kiếm, ....
- Hiu được nguyên lý ca vic xây dng mt chương trình máy tính.
- Có th chn la vic t chc d liu phù hp và các gi
i thut x lý d
liu có hiu qu trong khi xây dng chương trình. Sinh viên cn lưu ý rng, tùy
vào công vic c th mà ta nên chn cu trúc d liu nào là thích hp theo
hướng ti ưu v thi gian thc hin hay ti ưu v b nh.
1
Tài liệu môn Cấu trúc Dữ Liệu - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Tài liệu môn Cấu trúc Dữ Liệu - Người đăng: myvan
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
193 Vietnamese
Tài liệu môn Cấu trúc Dữ Liệu 9 10 830