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

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.
Nội dung trích xuất từ tài liệu:
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ếtKhoa CNTT, Đại học Sư phạm TP. HCMLời nói đầu“Algorithms + Data Structures = Programs” N. Wirth“Computing is an art form. Some programs areelegant, some are exquisite, some are sparkling.My claim is it is possible to write grand programs,noble programs, truly magnificent programs” D.E.KnuthGiả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, PeekCấu trúc dữ liệu tuyến tính1. Đứ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ộiTS. Lê Minh Trung – Lương Trần Ngọc Khiết Khoa CNTT, Đại học Sư phạm TP. HCMNộ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ượngCon 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 nhauint *foo = &myvar; &myvar và foo giống nhauint bar=*foo; //bar=myvarVí 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