Cơ sở dữ liệu - Chương 1: Tổng quan về cấu trúc dữ liệu

Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU ----o0o---- 1.1. Khái niệm về cấu trúc dữ liệu. Cấu trúc dữ liệu (CTDL) là một cách tổ chức dữ liệu của bài toán. CTDL có thể do ngôn ngữ lập trình định nghĩa trước hoặc có thể do người sử dụng định nghĩa. Cấu trúc dữ liệu tốt thì thuật toán xử lý bài toán mới tối ưu. Chính vì vậy, Niklaus wirth đã tổng kết: “Cấu trúc dữ liệu + thuật toán = Chương trình”. Cách biểu diễn tối ưu một cấu trúc dữ liệu trong bộ nhớ được gọi là cấu trúc lưu trữ (storage structure). Có thể có nhiều cấu trúc lưu trữ cho cùng một cấu trúc dữ liệu. Cấu trúc dữ liệu tương ứng với bộ nhớ gọi là lưu trữ trong hay tương ứng với bộ nhớ ngoài gọi là lưu trữ ngoài. Thông thường một kiểu dữ liệu được định nghĩa như sau: Một kiểu dữ liệu T là một cặp T = trong đó: - V (value) : Là một tập các trị mà một biến có kiểu T nhận được. - O (Operator) : Là tập hợp các thao tác trên V. Ví dụ: a. T º Integer = V={-32768,...,32767} ; O={+,-,*,/,mod,div,xor,,...} b. T º Boolean = V={True, False}; O = { And, Or, Xor, Not, , =,} Một cấu trúc dữ liệu là một kiểu dữ liệu được xây dựng từ những kiểu dữ liệu đã biết, trong trường hợp này cho ta một CTDL tương ứng với một kiểu dữ liệu đã cho. 1.2. Các cấu trúc dữ liệu căn bản. 1.2.1. Các kiểu dữ liệu căn bản. - Kiểu Integer (nguyên – 2 byte, -32768 .. 32767). Gồm tập hợp con các số nguyên. Tất cả các phép toán trên dữ liệu integer đều tuân thủ các qui tắc số học. Các toán tử chuẩn gồm bốn phép toán số học cơ bản: cộng (+), trừ (-), nhân (*), chia nguyên (div). - Kiểu Real (thực – 6 byte,2.9E-39 .. 1.7E38). Gồm tập hợp con của các số thực, các toán tử chuẩn gồm bốn phép toán số học cơ bản là: công (+), trừ (-), nhân (/). - Kiểu Boolean (luận lý – 1 bit). Gồm hai giá trị luân lý true (đúng) và false (sai). Các toán tử luận lý gồm ba phép toán cơ bản: not (phủ định), and (và) và or (hay). Các phép toán so sánh cho kết quả là một giá trị luận lý. Các phép toán so sánh gồm: = bằng khác bằng (khác) < nhỏ hơn <= nhỏ hơn hoặc bằng > lớn hơn >= lớn hơn hoặc bằng - Kiểu char ( kí tự – 1 byte): Gồm tập hợp các kí tự in được. Các kí tự thường dùng là: + Kiểu char gồm 26 chữ Latin ((‘A’<=x) and (x<=’Z’)), 10 ký số( 0 .. 9) và một số ký tự đặc biệt, ký tự trắng. - Kiểu liệt kê (Enuerated Types) Kiểu liệt kê gồm một tập hợp các giá trị bằng cách liệt kê các danh hiệu (identifier) chỉ định các giá trị này. Thứ tự của các kiểu liệt kê được định nghĩa như sau: Type T = (c1,c2,, cn) trong đó c1,c2,, cn là các danh hiệu chỉ định các giá trị của kiểu liệt kê. Ví dụ: Type shape = (rectange, square, ellipse, circle) - Kiểu miền con (Subrange Types) là trường hợp một biến có giá trị chỉ nằm trong một khoảng xác định nào đó của một kiểu. Điều này có thể được biểu diễn bằng cách định nghĩa biến thuộc kiểu miền con theo dạng: Type T= min max - Kiểu chuỗi (string). Gồm một tập hợp các kí tự. Các chuỗi kí tự này được ghi trong hai dấu nháy đơn (‘) và có tối đa 255 ký tự. Số ký tự của chuỗi được gọi là chiều dài của chuỗi, được khai báo như sau: Var s : string[10] ; 1.2.2. Các kiểu dữ liệu có cấu trúc. a. Kiểu mảng. Mảng là một bảng chứa dữ liệu có cùng kiểu, trên các hàng cột, giá trị của dữ liệu được xác định theo chỉ số hàng, cột. Có hai loại mảng: Một chiều, hai chiều. Bao gồm có tên của mảng và chỉ số tương ứng Ví dụ: Mảng một chiều a(n) với n là số nguyên nào đó, cho xác định số phần tử của mảng, phần tử của mảng được xác định theo chỉ số, chẳng hạn phần tử thứ 3 của mảng a ta ghi a[3] (dấu ngoặc vuông). Mảng hai chiều a(n,m) thường có nxm phần tử, gồm có n hàng, m cột, một phần tử thứ i,j nào đó có nghĩa là phần tử ở hàng thứ i, cột thứ j. * Mảng một chiều. - Cú pháp: + Khai báo gián tiếp: Kiểu TYPE = Array[ Chỉ số] OF ; VAR :; + Khai báo trực tiếp: VAR : ARRAY [chỉ số] OF ; Chú ý: Chỉ số trong khai báo đối với Pascal phải được xác định trước ở khai báo hằng hoặc ghi cụ thể. * Mảng hai chiều. - Cú pháp: + Khai báo gián tiếp: TYPE = ARRAY [chỉ số1, chỉ số 2] OF ; VAR :; + Khai báo trực tiếp: VAR : ARRAY [chỉ số1, chỉ số 2] OF ; Ví dụ: TYPE Mangnguyen = Array[1..100] of Integer; Matrix = Array[1..10,1..10] of Integer; MangKytu = Array[Byte] of Char; VAR A: Mangnguyen; M: Matrix; C: MangKytu; Hoặc: VAR A: Array[1..100] of Integer; C: Array[Byte] of Char; b. Kiểu xâu ký tự. Chúng ta gọi kiểu dữ liệu có giá trị là tập những kí tự là kiểu xâu kí tự hay nói một cách ngắn gọn là kiểu xâu. Pascal có từ khoá STRING để người dùng khai báo cho dữ liệu có giá trị là tập những kí tự. Ví dụ ta khai báo biến A có kiểu là tập những kí tự như sau: VAR   A : STRING ; máy dành cho biến A có thể lưu giữ được một tập có không quá 255 kí tự. Hằng văn bản phải để trong cặp dấu nháy cao (‘). * Khai báo. TYPE TênKiểu = STRING[Max]; VAR Tên biến : TênKiểu; hoặc khai báo biến trực tiếp: VAR Tên biến : STRING[Max]; Trong đó Max là số ký tự tối đa có thể chứa trong chuỗi (Max Î [0,255]). Nếu không có khai báo [Max] thì số ký tự mặ mặc định trong chuỗi là 255. Ví dụ: Type Hoten = String[30]; St80 = String[80]; Var Name : Hoten; Line : St80; St : String; {St có tối đa là 255 ký tự} * Truy xuất phần tử. - Có thể sử dụng các thủ tục xuất nhập Write, Writeln, Readln để truy xuất các biến kiểu String. - Để truy xuất đến ký tự thứ k của xâu ký tự, ta sử dụng cú pháp sau: Tênbiến[k]. * Các thủ tục và hàm trên xâu ký tự - Hàm lấy chiều dài của xây ký tự LENGTH(St : String):Integer; - Hàm COPY(St : String; Pos, Num: Byte): String; Lấy ra một xâu con từ trong xâu St có độ dài Num ký tự bắt đầu từ vị trí Pos . - Hàm POS(SubSt, St :String):Byte; Kiểm tra xâu con SubSt có nằm trong xâu St hay không? Nếu xâu SubSt nằm trong xâu St thì hàm trả về vị trí đầu tiên của xâu con SubSt trong xâu St, ngược lại hàm trả về giá trị 0. - Thủ tục DELETE(Var St:String; Pos, Num: Byte); Xoá trong xâu St Num ký tự bắt đầu từ vị trí Pos. - Thủ tục INSERT(SubSt: String; Var St: String; Pos: Byte); Chèn xâu SubSt vào xâu St bắt đầu tại vị trí Pos. - Thủ tục STR(Num; Var St:String); Đổi số nguyên hay thực Num thành dạng xâu ký tự, kết quả lưu vào biến St. - Thủ tục VAL(St:String; Var Num; Var Code:Integer); Đổi xâu số St thành số và gán kết quả lưu vào biến Num. Nếu việc chuyển đổi thành công thì biến Code có giá trị là 0, ngược lại biến Code có giá trị khác 0 (vị trí của lỗi). c. Kiểu bản ghi. Như ta đã biết các kiểu dữ liệu đã có, mỗi biến thuộc một loại kiểu nào đó thì giá trị của chúng chỉ thuộc một kiểu đó: Chẳng hạn kiểu số nguyên, kiểu mảngTrong khi đó kiểu bản ghi có thể coi như sự mở rộng các khái niệm biến và mảng, nó cho phép lưu trữ và xử lý các dạng thông tin phức tạp hơn. RECORD là một tập hợp các biến, các mảng và được hiển thị bằng một tên duy nhất. * Khai báo. TYPE TênKiểu = RECORD Field1 : Kiểu1; Field2 : Kiểu2; ... FieldN: KiểuN; END; VAR Biến : TênKiểu; Ví dụ: TYPE HocSinh = Record Hoten : String[20]; Tuoi : Integer; DiemTB : real; End; VAR HS : HocSinh; 1.2.3. Kiểu con trỏ. * Khai báo Type = ^ ; Var :; Ví dụ 1: Type TroNguyen = ^integer; Var p, q: TroNguyen; Sau khai báo này các biến p và q là các biến con trỏ có thể trỏ đến các biến động có kiểu integer. Chương trình sẽ cấp phát 4 byte cho mỗi biến con trỏ. Còn vùng nhớ của các biến động chưa được cấp phát. Ví dụ 2: Type TroSv = ^ Sinhvien; Sinhvien = Record Hoten: String[20]; Diem: real; Tiep: TroSv; End; Var p: TroSv; Trong ví dụ này, p là biến trỏ có thể trỏ đến các bản ghi có kiểu Sinhvien, trong bản ghi này lại có trường Tiep là một biến trỏ có thể trỏ đến biến động khác cũng có kiểu Sinhvien. * Làm việc với biến động - Cấp phát vùng nhớ Dùng thủ tục New theo cú pháp: New(); - Giải phóng vùng nhớ Dùng thủ tục Dispose(p); Trong đó p là một biến con trỏ. Thủ tục Dispose cho phép trả lại bộ nhớ động đã được cấp phát bởi thủ tục New. 1.3. Thuật toán và đánh giá độ phức tạp thuật toán . 1.3.1. Thuật toán. a. Khái niệm thuật toán (hay Giải thuật). Thuật toán hay giải thuật là một hệ thống chặc chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên những đối tượng, sao cho sau một số hữu hạn bước thực hiện các thao tác thì cho kết quả. b. Các đặc trưng của giải thuật. * Tính xác định Giải thuật bao gồm các bước rõ ràng. Trong cùng một điều kiện thì kết quả của mỗi bước là xác định. * Tính hữu hạn dừng Giải thuật sau một số hữu hạn bước thì cho kết quả. * Tính đúng đắn. Sau khi thực hiện các bước của giải thuật phải cho được kết quả mong muốn, kết quả đó được xác định theo định nghĩa có trước. * Tính phổ dụng Giải thuật phải giải quyết được cho một lớp bài toán. * Tính có đại lượng vào và ra Bắt đầu một giải thuật là việc nhận dữ liệu vào (Input) – kết thúc giải thuật là một số kết quả (dữ liệu ra Output). * Tính hiệu quả. Tính hiệu quả của một giải thuật được đánh giá dựa trên các tiêu chuẩn sau: - Dung lượng bộ cần thiết - Số lượng phép tính cần thực hiện. - Thời gian cần thiết để chạy. - Dễ hiểu và dễ cài đặt. c. Biểu diễn thuật toán Thường có hai cách biểu diễn một thuật toán, cách thứ nhất là mô tả các bước thực hiện của thuật toán, cách thứ hai là sử dụng sơ đồ giải thuật. - Mô tả các bước thực hiện. Để biểu diễn thuật toán người ta mô tả chính xác các bước thực hiện của thuật toán, ngôn ngữ dùng để mô tả thuật toán có thể là ngôn ngữ tự nhiên hoặc một ngôn ngữ lai ghép giữa ngôn ngữ tự nhiên với một ngôn ngữ lập trình nào đó gọi là các đoạn giả mã lệnh. Ví dụ 1: mô tả thuật toán tìm ước số chung lớn nhất của hai số nguyên. Input: Hai số nguyên a, b. Output: Ước số chung lớn nhất của a, b. Thuật toán: Bước 1: Nếu a=b th́ USCLN(a, b)=a. Bước 2: Nếu a > b th́ t́m USCLN của a-b và b, quay lại bước 1; Bước 3: Nếu a < b th́ t́m USCLN của a và b-a, quay lại bước 1; Ví dụ 2: Để giải phương trình bậc hai ax2 + bx +c = 0, ta có thể mô tả thuật toán bằng ngôn ngữ liệt kê như sau: Bước 1: Xác định các hệ số a,b,c. Bước 2 :Kiểm tra xem các hệ số a,b,c có khác 0 hay không ? Nếu a=0 quay lại thực hiện bước 1. Bước 3: Tính biểu thức = b2 – 4*a*c. Bước 4:Nếu D <0 thông báo phương trình vô nghiệm và chuyển sang bước 8. Bước 5:Nếu D=0,tính x1=x2=  và chuyển sang bước 7. Bước 6: Tính x1= , x2= và chuyển sang bước 7. Bước 7: Thông báo các nghiệm x1 , x2 . Bước 8: Kết thúc thuật toán. - Sử dụng lưu đồ giải thuật. Sử dụng các kư hiệu h́nh khối cơ bản để tạo thành một mô tả mang tính h́nh thức (cách này rơ ràng hơn so với việc mô tả các bước thực hiện thuật toán). Nhập, Xuất Bắt đầu Kết thúc Câu lệnh Điều kiện 1 2 3 4 5 Đúng Sai Khối 1: Khối bắt đầu thuật toán, chỉ có duy nhất một đường ra. Khối 2: Khối kết thúc thuật toán, có thể có nhiều đường vào. Khối 3: Thực hiện câu lệnh (có thể là một hoặc nhiều câu lệnh); gồm một đường vào và một đường ra. Khối 4: Rẽ nhánh, kiểm tra biểu thức điều kiện (biểu thức Boolean), nếu biểu thức đúng thuật toán sẽ đi theo nhánh Đúng (True), nếu biểu thức sai thuật toán sẽ đi theo nhánh Sai (False). Khối 5: Các câu lệnh nhập và xuất dữ liệu. d. Phân tích thời gian thực hiện giải thuật. Một giải thuật cho một lời giải thỏa đáng đối với một bài toán phải thỏa: - Đúng. - Hiệu quả. Thước đo về tính hiệu quả thường là thời gian mà máy sử dụng để giải quyết bài toán, khi các giá trị đầu vào có một kích thước xác định. Thước đo thứ hai là dung lượng bộ nhớ đòi hỏi để thực hiện giải thuật ứng với giá trị đầu vào có kích thước xác định. Sự phân tích thời gian cần thiết để giải một bài toán có kích thước nào đó, liên quan đến độ phức tạp thời gian của giải thuật. Sự phân tích bộ nhớ cần thiết của máy tính liên quan đến độ phức tạp không gian của giải thuật. Sự xem xét độ phức tạp không gian gắn với cấu trúc dữ liệu được dùng để thực hiện giải thuật. Trong phần này ta xét đến độ phức tạp thời gian. Độ phức tạp thời gian là một hàm tỷ lệ với kích thước dữ liệu, ký hiệu là T(n), trong đó n là kích thước dữ liệu vào. Tuy nhiên T(n) không thể biểu diễn thành đơn vị thời gian là giây, phút(do các máy tính có cấu hình khác nhau, hệ thống khác nhau). Mặc dù vậy, chúng ta hoàn toàn có thể so sánh được dựa vào các giá trị của hàm. Ví dụ: Giải thuật 1: - Độ phức tạp thời gian T1(n) = an2 Giải thuật : - Độ phức tạp thời gian T2(n) = kn Khi n lớn rõ ràng là T1(n) >=T2(n). Vậy giải thuật 1 chậm hơn giải thuật 2. 1.3.2. Đánh giá độ phức tạp của giải thuật. Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n 3(với tỷ suất tăng là n3). Giải thuật nào sẽ thực hiện nhanh hơn? Câu trả lời phụ thuộc vào kích thước dữ liệu vào. Với n 20 thì ngươc lại do số mũ của 100n2 nhỏ hơn số mũ của 5n3 (220 vì khi n<20 thì thời gian thực hiện của cả P1 và P2 đều không lớn và sự khác biệt giữa T1 và T2 là không đáng kể. Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiện. Cho một hàm T(n), T(n) gọi là có độ phức tạp f(n) nếu tồn tại các hằng C, N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là “ô của f(n)”) Ví dụ 1: T(n)= (n+1) 2có tỷ suất tăng là n2 nên T(n)= (n+1)2 là O(n2) Chú ý: O(C.f(n))=O(f(n)) với C là hằng số. Ðặc biệt O(C)=O(1) Nói cách khác độ phức tạp tính toán của giải thuật là một hàm chặn trên của hàm thời gian. Vì hằng nhân tử C trong hàm chặn trên không có ý nghĩa nên ta có thể bỏ qua vì vậy hàm thể hiện độ phức tạp có các dạng thường gặp sau: Độ phức tạp: O(1) O(logn) O(n) O(nlogn) O(nb) O(bn), b>1 O(n!) Thuật ngữ Độ phức tạp hằng số. Độ phức tạp logarit. Độ phức tạp tuyến tính. Độ phức tạp nlogn. Độ phức tạp đa thức. Độ phức tạp hàm mũ. Độ phức tạp n!. Xác định độ phức tạp tính toán. * Quy tắc cộng: Giả sử T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì thời gian thực hiện P1 rồi P2 tiếp theo sẽ là: T1(n) + T2(n) = O(Max(f(n),g(n)). Ví dụ 1 : Trong một chương trình có 3 bước thực hiện mà thời gian thực hiện từng bước lần lượt là O(n2), O(n3) và O(nlog2n) thì thời gian thực hiện 2 bước đầu là: O(max(n2,n3) = O(n3). Thời gian thực hiện chương trình sẽ là : O(n3,nlog2n) = O(n3). - Một ứng dụng khác của quy tắc này là nếu g(n) ≤ f(n) với mọi n≤ no thì O(f(n) = g(n)) cũng là O(f(n)). Chẳng hạn : O(n4 + n2) = O(n4) và O(n+Log2n) = O(n). Ví dụ 2: Lệnh gán x:=15 tốn một hằng thời gian hay O(1), Lệnh đọc dữ liệu READ(x) tốn một hằng thời gian hay O(1).Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1). * Quy tắc nhân : Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương trình đó lồng nhau là T(n) = O(f(n).g(n)). Qui tắc tổng quát để phân tích một chương trình: - Thời gian thực hiện của mỗi lệnh gán, READ, WRITE là O(1). - Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh. - Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1). - Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp. Ví dụ 3: 1. Câu lệnh gán: x:=x+1 có thời gian thực hiện bằng c (hằng số) nên được đánh giá là O(1). 2. Câu lệnh: For i:=1 to n do x:=x+1; Có thời gian thực hiện giải thuật là O(n.1) = O(n). 3. Câu lệnh: For i:=1 to n do For j:=1 to n do x:=x+1; Có thời gian thực hiện giải thuật được đánh giá là O(n.n) = O(n2) 4. Giả sử có hàm đệ qui: Function Vidu(n:integer):Real; Begin If n=1 then Vidu:=K {1} Else Vidu:=K/(2*n-3)+Vidu(n-1). {2} End ; Gọi thời gian thực hiện phép gán {1} là a, thời gian thực hiện phép chi {2} là b thì : T(n) = b+T(n-1) = b+b+T(n-2) = b+b+...+T(1) T(n) = b(n-1)+a. Lấy C = Max(a,b) Þ T(n) ≤ Cn, "n. Vậy T(n) là O(n). Chương 2: DANH SÁCH -----o0o----- 2.1. Định nghĩa danh sách. Danh sách là một tập hữu hạn các phần tử (element) a1, a2, , an, giữa các phần tử có mối quan hệ tương đối: Nếu biết phần tử ai thì sẽ định được vị trí phần tử ai+1. Nói cách khác hơn, các phần tử thuộc một danh sách có thể sắp xếp tuyến tính. Ví dụ 1: - Danh sách sinh viên là một danh sách. - Kiểu dữ liệu mảng trong pascal là một danh sách. 2.2. Danh sách đặc. 2.2.1. Định nghĩa. Danh sách đặc là một danh sách mà các phần tử được sắp xếp kế tiếp nhau trong bộ nhớ. 2.2.2. Tổ chức cấu trúc dữ liệu. Ta biểu diễn danh sách đặc là một dãy n phần tử a[1] a[2] ... a[n] Ta khai báo một danh sách đặc là một dãy số nguyên a[1], a[2],..., a[n] như sau: const elemno = 100; var a: aray [1..elemno] of integer; 2.2.3. Các phép toán trên danh sách: a. Khởi tạo danh sách: Khi khởi tạo danh sách, nếu danh sách là rỗng ta cho số phần tử bằng 0 * Thuật toán Procedure Initialize; Begin     n :=0; End; b. Thêm một phần tử vào danh sách:        Khi thêm một phần tử vào danh sách tại vị trí thứ i thì các phần tử cũ từ a[i] đến a[n] được di chuyển về phía sau 1 bước. Thuật toán: Procedure Insert_element(i : integer; Newinfo : integer); Var j : integer ; Begin For j:= n downto i do a[j+1] := a[j]; a[j] := Newinfo ; n:= n +1 ; end; c. Loại bỏ một phần tử của danh sách: Khi loại bỏ phần tử a[i] của danh sách, các phần tử còn lại từ a[i+1] đến a[n] được di chuyển về phía trước một bước. Thuật toán: Procedure Delete_element( i : integer); Var j: integer; Begin For j:= i to n do a[j] :=a[j+1]; n := n-1; end; d. Tìm kiếm một phần tử trong danh sách:        Khi tìm kiếm một phần tử trong danh sách đặc có khoá là k, ta có thể dùng thuật toán tìm kiếm tuần tự với danh sách chưa có thứ tự, hay thuật toán tìm kiếm nhị phân với danh sách đã có thứ tự. Ta sẽ nghiên cứu kĩ hơn trong bài 4. 2.2.4. Ưu nhược điểm và ứng dụng. - Ưu điểm: + Mật độ sử dụng là 100%. + Dễ dàng truy xuất đến phần tử a[i] nhờ địa chỉ. + Sử dụng các thuật toán hiệu năng để tìm kiếm (thuật toán tìm kiếm nhị phân). - Khuyết điểm: + Không gian nhớ cố định, vùng nhớ liên tục. + Việc thêm là loại bỏ một phần tử vào danh sách thời gian thực hiện tỷ lệ với số lượng phần tử của danh sách. T(n)max = O(n). + Lãng phí khi số lượng các phần tử có cùng giá trị cao. + Bộ nhớ được quản lý kém linh động. 2.3. Danh sách liên kết, các phép toán. 2.3.1. Định nghĩa. Danh sách liên kết là danh sách mà các phần tử được nối kết nhau nhờ vào vùng liên kết của chúng. Danh sách liên kết là một loại cấu trúc đơn giản và thích hợp với các phép thêm vào, phép loại bỏ, phép ghép nhiều danh sách mà các phép toán này lại không thích hợp cho danh sách đặc. 2.3.2. Danh sách liên kết đơn. 2.3.2.1. Tổ chức cấu trúc dữ liệu. Danh sách liên kết là danh sách mà mỗi phần tử của danh sách được lưu trữ trong một phần tử nhớ mà ta gọi là nút (node). Các nút này có thể nằm bất kỳ trong bộ nhớ. Trong mỗi nút, ngoài phần thông tin ứng với một phần tử còn có chứa địa chỉ của phần tử đứng sau nó trong danh sách. Qui cách của mỗi nút có thể hình dung như sau: INFO LINK Trường INFO chứa thông tin của phần tử. Trường LINK chứa địa chỉ của nút tiếp theo. Riêng nút cuối cùng trong danh sách thì không có nút đứng sau nó nên mối nối ở nút này phải là một “địa chỉ đặc biệt” đỉ dùng để đánh dấu nút kết thúc danh sách chứ không như các địa chỉ ở các nút khác ta gọi là “mối nối không” và ký hiệu là nill. Để có thể truy nhập vào mọi nút trong danh sách, tất nhiên là phải truy nhập được vào nút đầu tiên, nghĩa là cần có một con trỏ First trỏ tới nút đầu tiên này. Nếu dùng mũi tên để chỉ mối nối, ta sẽ có một hình ảnh danh sách móc nối đơn như sau: A B C D Fir