Bài giảng Cấu trúc dữ liệu: Ngôn ngữ lập trình C++ - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

Chia sẻ: Conbongungoc09 | Ngày: | Loại File: PDF | Số trang:71

Thêm vào BST

Báo xấu

39
lượt xem 6
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: Chương 1 cung cấp cho người học những kiến thức như: Con trỏ (Pointer); Mảng một chiều, nhiều chiều; Cấp phát vùng nhớ động; Struct; Khuôn mẫu (template); Con trỏ hàm; Lớp và lập trình hướng đối tượng.

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: Ngôn ngữ lập trình C++ - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

TS. Lê Minh Trung Th.S Lương Trần Ngọc Khiết Khoa CNTT, Đại học Sư phạm TP. HCM
Lời nói đầu “Algorithms + Data Structures = Programs” N. Wirth “Computing is an art form. Some programs are elegant, some are exquisite, some are sparkling. My claim is it is possible to write grand programs, noble programs, truly magnificent programs” D.E.Knuth
Giải thuật (Thuật toán)  Chỉ ra làm thế nào để giải quyết bài toán.  Một dãy hữu hạn các thao tác mà cung cấp lời giải cho bài toán.  Input (đầu vào)  Output (đầu ra)  Mô tả thuật giải  Bằng lời  Lưu đồ thuật giải (flow chart)  Giả mã (pseudo code): Pascal like, C like, C++ like…
Tính chất của giải thuật  Tính chính xác (correctness)  Tính duy nhất (uniqueness)  Tính hữu hạn (finiteness)  Tính tổng quát (generality)
Cấu trúc dữ liệu  Cách tổ chức dữ liệu để thuận tiện cho các thao tác của thuật toán.
Cấu trúc dữ liệu  Một cấu trúc dữ liệu bao gồm  Một tập hợp các giá trị  Một tập hợp các thao tác (phép toán) trên các giá trị này Stack (ngăn xếp)  Thao tác:  Push, Pop, Peek
Cấu trúc dữ liệu tuyến tính 1. Đứng sau mỗi phần tử có tối đa một phần tử. 2. Mỗi phần tử có không quá 1 phần tử đứng trước.
Cấu trúc dữ liệu phi tuyến  Một trong hai điều kiện 1 hoặc 2 bị vi phạm.
Nội dung học  Giới thiệu và khái niệm cơ bản  Ôn tập lập trình C++  Các giải thuật tìm kiếm, sắp xếp  Ngăn xếp, hàng đợi và ứng dụng  Danh sách liên kết  Cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng  Bảng băm – Hash table
Điểm số - Đánh giá  Số tuần học: 10 buổi  Đánh giá giữa kì: 30% (thi thực hành)  Thi cuối kì: 70% (thi giấy)  Bài tập lớn miễn thi (nhóm 2- 3 sinh viên)
Tài liệu tham khảo  Data Structures and Problem Solving Using C++, Mark Allen Weiss, Pearson Education International Inc.  Data Structures and Algorithm Analysis, Clifford A. Shaffer, Dover Publications.  Algorithms, Robert Sedgewick and Kevin Wayne, Addison Wesley  Cấu trúc dữ liệu và Giải thuật, Đinh Mạnh Tường, Nhà xuất bản Giáo dục  Giải thuật và Lập trình, Lê Minh Hoàng, Đại học Sư phạm Hà Nội
TS. Lê Minh Trung – Lương Trần Ngọc Khiết Khoa CNTT, Đại học Sư phạm TP. HCM
Nội dung  Con trỏ (Pointer)  Mảng một chiều, nhiều chiều  Cấp phát vùng nhớ động  Struct  Khuôn mẫu (template)  Con trỏ hàm  Lớp và lập trình hướng đối tượng
Con trỏ  Con trỏ là biến chứa địa chỉ của một biến khác  Khai báo  type * name;  int * number;  char * character;  double * decimals;
Ví dụ int myvar=25; myvar và *foo giống nhau int *foo = &myvar; &myvar và foo giống nhau int bar=*foo; //bar=myvar
Ví dụ
Ví dụ
Phép toán với con trỏ char *mychar; ++mychar; mychar = mychar + 1; short *myshort; ++myshort; myshort = myshort + 1; long *mylong; ++mylong; mylong = mylong + 1;
Con trỏ tới con trỏ char a; char * b; char ** c; a = 'z'; b = &a; c = &b;
Con trỏ trống (void)  Rất linh động, có thể trỏ tới bất cứ kiểu dữ liệu nào như int, char, string …  Tuy nhiên, không thể lấy nội dung (dereference) của con trỏ trống một cách trực tiếp mà không ép kiểu thành kiểu con trỏ khác