Bài giảng Cấu trúc dữ liệu và giải thuật (501040)

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:129

Thêm vào BST

Báo xấu

81
lượt xem 15
download

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

Bài giảng Cấu trúc dữ liệu và giải thuật (501040) được biên soạn nhằm trang bị cho các bạn những kiến thức về tổng quan, Stack, Queue, đệ qui, List và String, cây nhị phân, tìm kiếm, sắp xếp. Bài giảng phục vụ cho các bạn chuyên ngành Công nghệ thông tin và những ngành có liên quan.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật (501040)

A C CẤU TRÚC DỮ LIỆU VÀ B F GIẢI THUẬT (501040) D E G K H
Giới thiệu Môn học giới thiệu: Các cấu trúc dữ liệu cơ bản Các giải thuật điển hình trên các cấu trúc dữ liệu đó Dùng phương pháp hướng đối tượng. Ngôn ngữ lập trình minh hoạ: Mã giả (pseudocode) C++ (không được giảng dạy chính thức trong môn học) ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Giới thiệu môn học 2
Nội dung Chương 1. Tổng quan Chương 2. Stack Chương 3. Queue Chương 4. Đệ qui Chương 5. List và String Chương 6. Cây nhị phân Chương 7. Tìm kiếm Chương 8. Sắp xếp ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Giới thiệu môn học 3
Một số thuật ngữ căn bản Một chương trình máy tính (computer program) là tập các câu lệnh để điều khiển một máy tính sinh ra một kết quả cụ thể Viết các chương trình máy tính gọi là lập trình máy tính (computer programming) Ngôn ngữ để tạo các chương trình máy tính gọi là ngôn ngữ lập trình Software là một chương trình hay tập hợp các chương trình Programming 4 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 4
Ngôn ngữ máy Cấp thấp nhất. Các chương trình bao gồm 0, 1. Lập trình bằng ngôn ngữ máy có thể điều khiển trực tiếp đến phần cứng máy tính Ví dụ 00101010 000000000001 000000000010 10011001 000000000010 000000000011 Instruction part address parts (địa chỉ bộ nhớ (opcode – tác vụ của dữ liệu được thực hiện) Programming 5 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 5
Assembly languages Thực hiện cùng nhiệm vụ ngôn ngữ máy nhưng sử dụng tên tượng trưng cho opcode và các toán tử thay vì 1, 0 LOAD BASEPAY ADD OVERPAY STORE GROSSPAY Chương trình ngôn ngữ assembly phải được dịch sang ngôn ngữ máy trước khi có thể thực thi bởi máy tính Programming 6 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 6
Assembler Translation Assembly Machine program language language (assembler) program program Programming 7 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 7
Ngôn ngữ lập trình cấp cao Sử dụng các câu lệnh dễ hiểu hơn. Các chương trình sử dụng ngônn ngữ cấp cao phải được dịch sang ngôn ngữ cấp thấp bằng cách sử dụng một chương trình gọi là compiler Programming 8 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 8
High-level Programming Languages (cont.) Cho phép người lập trình viết các câu lệnh như câu tiếng Anh và các kí hiệu toán học thông dụng Mỗi dòng trong chương trình ngôn ngữ mức cao gọi là câu lệnh Example: Result = (First + Second)*Third Programming 9 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 9
Phần mềm ứng dụng và phần mềm hệ thống 2 loại chương trình máy tính Application software bao gồm những chương trình được viết để thực thi các nhiệm vụ cụ thể được yêu cầu bởi user • System software là tập các chươg trình phải luôn được sẵn sàng đến bất kì hệ thống máy tính cho nó vận hành (hệ điều hành, bộ chuyển đổi ngôn ngữ) Programming 10 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 10
PROGRAMMING LANGUAGES Một số ngôn ngữ thông dụng FORTRAN 1957 COBOL 1960s BASIC 1960s PASCAL 1971 Structure programming C C++ Object-oriented programming Java Cú pháp (syntax) Cú pháp của một ngôn ngữ lập trình là tập các luật để viết các câu lệnh chính xác Programming 11 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 11
The C Programming Language In the 1970s, at Bell Laboratories, Dennis Ritchie and Brian Kernighan designed the C programming language. C was used exclusively on UNIX and on mini-computers. During the 1980s, C compilers were written for other flatforms, including PCs. To provide a level of standardization for C language, in 1989, ANSI created a standard version of C, called ANSI C. One main benefit of C : it is much closer to assembly language other than other high-level programming languages. The programs written in C often run faster and more efficiently than programs written in other high-level programming language. Programming 12 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 12
The C++ Programming Language In 1985, at Bell Laboratories, Bjarne Stroutrup created C++ based on the C language. C++ is an extension of C that adds object- oriented programming capabilities. C++ is now the most popular programming language for writing programs that run on Windows and Macintosh. The standardized version of C++ is referred to as ANSI C++. The ANSI standards also define run-time libraries, which contains useful functions, variables, constants, and other programming items that you can add to your programs. The ANSI C++ run-time library is called Standard Template Library or Standard C++ Library Programming 13 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 13
Giải thuật Dùng C++ để diễn tả?  có vấn đề Có thể diễn tả giải thuật bằng cách sử dụng flowchart Flow chart thể hiện nét phát thảo cấu trúc căn bản và tính logic của chương trình Một cách khác để diễn tả giải thuật là sử dụng mã giả pseudocode Giả lập, thường là dễ hiểu, không chi tiết đến các kỹ thuật lập trình Ở cấp độ hết sức tổng quát: gần ngôn ngữ tự nhiên Hoặc rất chi tiết: như dùng ngôn ngữ tựa Pascal, tựa C++ Programming 14 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 14
Giải thuật (Algorithm) 15 Các tính chất quan trọng của giải thuật là: 􀂾 Hữu hạn (finiteness): giải thuật phải luôn luôn kết thúc sau một số hữu hạn bước. 􀂾 Xác định (definiteness): mỗi bước của giải thuật phải được xác định rõ ràng và phải được thực hiện chính xác, nhất quán. 􀂾 Hiệu quả (effectiveness): các thao tác trong giải thuật phải được thực hiện trong một lượng thời gian hữu hạn. – Ngoài ra một giải thuật còn phải có đầu vào (input) và đầu ra (output). ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Giới thiệu môn học 15
Flowchart symbols Terminal Input/output Process Connector Flowlines Predefined process Decision Programming 16 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 16
Example Start Input Name, Hours, Rate Calculate Note: Name, Hours Pay Hours Rate and Pay are variables in the program. Dislay Name, Pay End Programming 17 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 17
Algorithms in pseudo-code Sử dụng các cụm từ như tiếng Anh để mô tả pseudocode. Example: Input the three values into the variables Name, Hours, Rate. Calculate Pay = Hours Rate. Display Name and Pay. Programming 18 ĐH Bách Khoa Tp.HCM Khoa Công Fundamentals nghệ Thông tin Giới thiệu môn học 18
Loops Note: 1. Loop is a very important Start concept in programming. NUM 4 2. NUM NUM + 1 means old value of NUM + 1 SQNUM NUM2 becomes new value of NUM. The algorithm can be described Print NUM, SQNUM in pseudocode as follows: NUM 4 NUM NUM + 1 do No SQNUM NUM2 NUM> 9? Print NUM, SQNUM Yes NUM NUM + 1 STOP while (NUM
Giải thuật bằng mã giả Ví dụ: Mã giả của bubble sort Giải thuật 1 Giải thuật 2 Algorithm Bubble sort Algorithm Bubble sort Input: The list A of n elements is Input: The list A of n elements is given given Output: The list A is sorted Output: The list A is sorted 1. loop for n time 1. for outter in 0..(n-2) 1.1. for inner in 0..(n-2- outter) 1.1. for each pair in the list 1.1.1. if Ainner+1 < Ainner 1.1.1. if it is not in ordered 1.1.1.1. swap Ainner, Ainner+1 1.1.1.1. exchange them End Bubble sort End Bubble sort ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Giới thiệu môn học 20