Cấu trúc dữ liệu máy tính và giải thuật

Chia sẻ: Nguyen Ba Toan | Ngày: | Loại File: PDF | Số trang:67

0
346
lượt xem
174
download

Cấu trúc dữ liệu máy tính và giải thuật

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

Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả. Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn một cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ...

Chủ đề:
Lưu

Nội dung Text: Cấu trúc dữ liệu máy tính và giải thuật

  1. Kỹ thuật lập trình Giảng viên: Đỗ Tuấn Anh Địa chỉ: Bộ môn Khoa học Máy tính 323 C1 ĐHBK Hà Nội Email: anhdt@it-hut.edu.vn Điện thoại: 0989095167
  2. Mục tiêu • Nắm bắt được các loại ngôn ngữ lập trình • Kỹ thuật lập trình đệ qui • Tìm hiểu lập trình cấu trúc • Tìm hiểu lập trình hướng đối tượng • Tìm hiểu các thao tác vào ra
  3. Nội dung trình bày • Chương 1: Mở đầu – Giới thiệu về ngôn ngữ lập trình – Ngôn ngữ lập trình C • Chương 2: Đệ qui • Chương 3: Lập trình cấu trúc • Chương 4: Lập trình hướng đối tượng • Chương 5: Thao tác vào ra với tệp tin
  4. Tài liệu tham khảo • [1] Data Structures and Algorithm Analysis in C – Mark Allen Weiss • [2] Cấu trúc dữ liệu và giải thuật – Đỗ Auân Lôi • [3] Ngôn ngữ lập trình C – Nguyễn Thanh Thủy • [4] Lập trình với các cấu trúc dữ liệu trên Pascal – Lê Minh Trung
  5. Chương 1: Mở đầu • Giới thiệu ngôn ngữ lập trình 1. Lịch sử phát triển 2. Các mô hình ngôn ngữ lập trình
  6. 1. Lịch sử phát triển ngôn ngữ lập trình • Ngôn ngữ máy • Hợp ngữ (Assembly) • Ngôn ngữ bậc cao – Fortran, Pascal, C, Java, … – Prolog – Lisp – Occam • Ngôn ngữ truy vấn – SQL
  7. 2. Phân loại • Ngôn ngư lập trình được phân loại theo phương thức lập trình Phương thức lập trình Mệnh lệnh Khai báo Hướng đối Aử lý Thủ tục Logic Hàm CSDL tượng song song
  8. 2. Phân loại (tiếp) • Mệnh lệnh – Thủ tục: Fortran (1957), Pascal (1970), C(1971), … – Đối tượng: Smalltalk (1969), C++(1983), Java(1991), C#(2000),… – Song song: Ada, Occam(1982), C-Linda • Khai báo – Hàm: Lisp(1958), Caml(1987), Miranda(1982) – Logic: Prolog(1970) – CSDL: SQL(1980)
  9. 2. Phân loại (tiếp) • Đặc điểm của ngôn ngữ mệnh lệnh – Diễn đạt thuật toán sử dụng tập các trạng thái. – Aử lý lần lượt – Khai báo dữ liệu – Kiểu dữ liệu cơ bản, và kiểu dữ liệu mới – Hai kiểu dữ liệu có cùng tên thì tương đương – Thay đổi trạng thái thông qua lệnh gán – Cấu trúc điều khiển là tuần tự – Chương trình con: hàm, thủ tục với truyền tham số – Hiệu ứng phụ khi sử dụng chương trình con – Bốn mức: Khối, CT con, module, chương trình • Đặc điểm của ngôn ngữ khai báo – Sử dụng các hàm suy luận – Đánh giá một biểu thức
  10. 2.1 Lập trình cấu trúc • Chương trình được tổ chức theo các công việc cần thực hiện, phân chia chương trình theo chức năng. • Đặc điểm – Gồm các chương trình con – Thực hiện tuần tự – Các kiểu dữ liệu xây dựng dựa trên kiểu dữ liệu cơ bản • Ngôn ngữ – C, Pascal, …
  11. 2.2 Lập trình hướng đối tượng • Aây dựng dựa trên nền tảng khái niệm lập trình có cấu trúc • Phân chia bài toán thành các đối tượng và bài toán đi giải quyết mối quan hệ giữa các đối tượng • Các khái niệm – Class • Method • Properties – Object
  12. 3. Ngôn ngữ lập trình C • Trong môn học này dùng C để mô tả các bài toán • Yêu cầu: – Nắm chắc ngôn ngữ C – Cài đặt các bài toán cơ bản trên ngôn ngữ C – Bài tập: Viết một chương trình • Đọc dữ liệu từ file văn bản VB.TAT • Liệt kê các từ có trong văn bản và đếm xem có bao nhiêu lần từ đó xuất hiện và xem nó hiển thị ở trang bao nhiêu (mỗi trang 25 dòng)
  13. Khái niệm Software Program 2 Program 1 Commands Commands Commands
  14. Ngôn ngữ cấp trung Ngôn Ngôn ngữ cấp cao C Ngôn ngữ hợp ngữ
  15. Đặc điểm của C • C có 32 từ khóa • Những từ khóa này kết hợp với cú pháp của C hình thành ngôn ngữ C • Các quy tắc được áp dụng cho các chương trình C
  16. Cấu trúc chương trình C main() • Chương trình C được chia nhỏ thành những đơn vị gọi là hàm • Không kể có bao nhiêu hàm trong chương trình, Hệ điều hành luôn trao quyền điều khiển cho hàm main() khi một chương trình C được thực thi. • Theo sau tên hàm là dấu ngoặc đơn • Dấu ngoặc đơn có thể có chứa hay không chứa những tham số
  17. Cấu trúc chương trình C • Dấu phân cách {…} • Dấu kết thúc câu lệnh …; • /*Dòng chú thích*/
  18. Biên dịch và thi hành chương trình Biên
  19. Biến Bộ nhớ 15 15 Dữ liệu Dữ liệu trong bộ nhớ Mỗi vị trí trong bộ nhớ là duy nhất Biến cho phép cung cấp một tên có ý nghĩa cho mỗi vị trí nhớ
Đồng bộ tài khoản