Cấu trúc dữ liệu - Chương 1 Các khái niệm cơ bản

Tài liệu "Cấu trúc dữ liệu - Chương 1 Các khái niệm cơ bản" giúp bạn nắm bắt thuật toán và cấu trúc dữ liệu, các kiểu dữ liệu cơ bản trong ngôn ngữ C, kiểu con trỏ, kiểu tham chiếu, đệ qui.
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu - Chương 1 Các khái niệm cơ bảnChương 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. Thuật toán và cấu trúc dữ liệu- Dữ liệu: nói chung là bất kỳ những gì mà máy tính xử lý- Kiểu dữ liệu: Mỗi kiểu dữ liệu gồm các giá trị có cùng chung các tính chất nào đó vàtrên đó xác định các phép toán- Cấu trúc dữ liệu: là cách tổ chức và lưu trữ dữ liệu trong máy tính- Thuật toán (hay giải thuật): là tập hợp các bước theo một trình tự nhất định để giải mộtbài toán- Giữa cấu trúc dữ liệu và thuật toán có quan hệ mật thiết. Nếu ta biết các tổ chức cấu trúcdữ liệu hợp lý thì thuật toán sẽ đơn giản hơn. Khi cấu trúc dữ liệu thay đổi thì thuật toánsẽ thay đổi theo 1.2. Các kiểu dữ liệu cơ bản trong ngôn ngữ C 1.2.1. Các kiểu dữ liệu đơn giản Có giá trị là đơn, - Kiểu ký tự: có giá trị là một ký tự bất kỳ đặt giữa hai dấu nháy đơn, có kíchthước 1 Byte và biểu diễn được một ký tự thông qua bảng mã ASCII, gồm 2 kiểu: Kiểu Phạm vi biểu diễn Kích thước char từ -128 đến 127 1 Byte unsigned char từ 0 đến 255 1 Byte - Kiểu số nguyên: có giá trị là một số nguyên, gồm các kiểu: Kiểu Phạm vi biểu diễn Kích thước int từ -32768 đến 32767 2 Byte unsigned int từ 0 đến 65535 2 Byte long từ -2147483648 đến 2147483647 4 Byte unsigned long từ 0 đến 4294967295 4 ByteNhận xét: Các kiểu ký tự cũng có thể xem là một dạng của kiểu số nguyên - Kiểu số thực: Có giá trị là một số thực, gồm các kiểu: Kiểu Phạm vi biểu diễn Kích thước float từ 3.4E-38 đến 3.4E+38 4 Byte double từ 1.7E-308 đến 1.7E+308 8 Byte long double từ 3.4E-4932 đến 1.1E4932 10 Byte 1.2.2. Các kiểu dữ liệu có cấu trúc 1.1.1.1. Kiểu mảng Các thành phần có cùng kiểu dữ liệu, mỗi thành phần gọi là một phần tử, các phầntử được đánh chỉ số từ 0 trở đi. Ví dụ với khai báo float A[5]Khai báo A là một mảng các số thực gồm 5 phần tử là A[0] , A[1] , A[2] , A[3] , A[4] 1.1.1.2. Kiểu bản ghi Các thành phần có thể có kiểu dữ liệu khác nhau, mỗi thành phần gọi là mộttrườngVí dụ: struct SVIEN { char ten[7]; int namsinh; float cao; }; CTDL - C – Trang 1 Khai báo SVIEN là kiểu bản ghi gồm 3 trường ten, namsinh, cao 1.3. Kiểu con trỏ 1.3.1. Định nghĩaCon trỏ là một biến mà nội dung của nó là địa chỉ của một đối tượng khác. Đối tượng ởđây có thể là một biến hoặc một hàm 1.3.2. Khai báo kiểu con trỏ kiểudữliệu *tênbiếncontrỏ ;Vd char c, *pc; // pc là con trỏ kiểu ký tự char int i, n, *p, *p2; float f, r, *pf; 1.3.3. Hàm địa chỉ &biến Trả về địa chỉ của một biến trong bộ nhớ, ví dụ &n 1.3.4. Các phép toán trên kiểu con trỏ- Phép gán: Ta có thể gán giá trị của hai biến con trỏ cùng kiểu cho nhau, hoặc gán địachỉ của một biến cho biến con trỏ cùng kiểu- Phép cộng thêm vào con trỏ một số nguyên (đối với con trỏ liên quan đến mảng)- Phép so sánh bằng nhau = = hoặc khác nhau !=- Hằng con trỏ NULL: cho biết con trỏ không chỉ đến đối tượng nào cả, giá trị này có thểđược gán cho mọi biến con trỏ kiểu bất kỳ- Phép cấp phát vùng nhớLệnh biếncontrỏ = NEW kiểudữliệu;Vd lệnh p = new int;- Phép thu hồi vùng nhớLệnh DELETE biếncontrỏ;Vd lệnh delete p; 1.4. Kiểu tham chiếu 1.4.1. Định nghĩaTrong C++ có 3 loại biếnBiến giá trị chứa một giá trị dữ liệu thuộc về một kiểu nào đó (nguyên, thực, ký tự . . . )Biến con trỏ chứa địa chỉ của một đối tượng. Hai loại biến này đều được cấp bộ nhớ vàcó địa chỉLoại thứ ba là biến tham chiếu, là biến không được cấp phát bộ nhớ, không có địa chỉriêng, được dùng làm bí danh cho một biến khác và dùng chung bộ nhớ của biến này 1.4.2. Khai báo kiểu tham chiếuCú pháp: kiểu dữ liệu &tên biến tham chiếu = tên biến;Tên biến là tên biến cùng kiểu với biến tham chiếu đang được khai báo, biến tham chiếusẽ tham chiếu đến biến cùng kiểu nàyVd float u, v; Float &x=u;Khai báo 2 biến thực u và vBiến tham chiếu x tham chiếu đến biến u cùng kiểu thực, dùng chung vùng nhớ với biếnu. Khi đó những thay đổi của biến u cũng là những thay đổi của biến x và ngược lạiVd int m; int &n=m; m=25; cout n=n+10; 1.4.3. Ứng dụng kiểu tham chiếu#include #include void doi(int x, int &y, int *z){ x=x+1; y=y+2; *z=*z+4;}void main(){ int i=1 ...