CHƯƠNG 3 CẤU TRÚC DỮ LIỆU ĐỘNG Mục tiêu *“#” Giới thiệu khái niệm cấu trúc dữ liệu động. *®” Danh sách liên kết: tổ chức, các thuật toán, ứr:g dụng. DAT VAN DE Với các cấu trúc dữ liệu được xây dựng từ các kiểu cơ sở như: kiếu thực, kiểu nguyên, kiểu ký tự. hoặc từ các cấu trúc đơn giản như mẩu tin, tập hợp, mảng.
lập trình viên có thể giải quyết hầu. hết các bài toán đặt ra. Các đối tượng dữ liệu được xác định thuộc những kiểu dữ liệu này có đặc điểm chung là không thay đổi được kích thước, cấu trúc trong quá trình sống, do vậy thường cứng nhắc, gò bó khiến đôi khi khó diễn tả được thực tế vốn. sinh động, phong phú.
Các kiểu dữ liệu kể trên được gọi là các kiểu dữ liệu tĩnh. Trong thực tế, một số đối tượng có thể được định nghĩa đệ qui, ví dy để mô tả đối tugng ‘con người' cắn thể hiện các thông tin tối thiểu như : = Họ tên * SốCMND 97 » _ Thông tin về cha, mẹ Để biểu diễn một đối tượng có nhiều thành phần thông tin như trên có thể sử dụng kiểu mẫu tin. Tuy nhiên, cần lưu ý cha, mẹ của một người cũng là các đối tượng kiểu NGƯỜI, do vậy vẻ nguyên tắc cẩn phải có định nghĩa như sau: typedef struct NGUOI( char ñoten(30]; intSo_CMND ; NGUOI Cha,Me; H 'Tuy nhiên với khai báo trên, các ngôn ngữ lập trình gặp khó khăn trong việc cài đặt không vượt qua được như xác định kích thước của đối tượng kiểu NGUOI ? 2. Một số đối tượng dữ liệu trong chu kỳ sống của nó có thể thay đổi vẻ cấu trúc, độ lớn, như danh sách các học viên trong một lớp học có thể tăng thêm, giảm đi.
Khi đó nếu cố tình dùng những cấu trúc dữ liệu tĩnh đã biết như mảng. để biểu diễn những đối tượng đơ, lập trình viên phải sử dụng những thao tác phức tạp, kém tự nhiên khiến chương „ trình trở nên khó đọc, do đó khó bảo trì và nhất là khó có thể sử dụng bộ nhớ một cách có hiệu quả. Một lý do nữa làm cho các kiểu đữ liệu tĩnh không thể đáp ứng được nhu cầu của thực tế là tổng kích thước vùng nhớ dành cho tất cả các biến tĩnh chỉ là 64kb (1 Segment bộ nhớ). Khi có nhu cẩu dùng nhiễu bộ nhớ hơn ta phải sử dụng các cấu trúc dữ liệu động.
Cuối cùng, do bản chất của các dữ liệu tĩnh, chúng sẽ chiếm. 98 vùng nhớ đã dành cho chúng suốt quá trình hoạt động của chương trình. Tuy nhiên, trong thực tế, có thể xảy ra trường hợp một dữ liệu nào đó chỉ tổn tại nhất thời hay không thường xuyên trong quá trình hoạt động của chương trình. Vì vậy việc dùng các CTDL tĩnh sẽ không cho phép sử dụng hiệu quả bộ nhớ.
Do vậy, nhằm đáp ứng nhu câu thể hiện sát thực bản chất của dữ liệu cũng như xây dựng các thao tác hiệu quả trên dữ liệu, cần phải tìm cách tổ chức kết hợp dữ liệu với những hình thức mới linh động hơn, có thể thay đổi kích thước, cấu trúc trong; suốt thời gian. Các hình thức tổ chức dữ liệu như vậy được gọi là cấu £rúc diz ligu động. Chương này sẽ giới thiệu về các cấu trúc dữ liệu động và tập trung khảo sát cấu trúc đơn giản nhất thuộc loại này là “danh sách liên kết. KIỂU DỮ LIỆU CON TRỎ 1.
Biến không động (biến tĩnh, biến nửa tĩnh) Khi xây dựng chương trình, lập trình viên có thể xác định được ngay những đối tượng dữ liệu luôn cần được sử dụng, không có nhu cẩu thay đổi về số lượng kích thước. do đó có thể xác định cách thức lưu trữ chúng ngay từ đâu. Các đối tượng dữ liệu này sẽ được khai báo như các biến không động. Biến không động là những biến thỏa: « _ Được khai báo tường mình, + Tén tai khi vào phạm vi khai báo và chỉ: mất khi ra khỏi phạm vỉ này, « Được cấp phát vùng nhớ trong vùng dữ liệu (Data segment) hoặc là Stack (đối với biến nửa tĩnh - các biến 99 cục bộ).
« _ Kích thước không thay đổi trong suốt quá trình sống. Do được khai báo tường minh, các biến không động có một định danh đã được kết nối với địa chỉ vùng nhớ lưu trữ biến và được truy xuất trực tiếp thông qua định danh đó. Ví dụ : int a //a, b là các biến khong dong char (10); 2. Kiểu con trỏ « Cho trước kiểu T = <V,O>.
Kiểu con trỏ - ký hiệu “Tp”- chỉ đến các phần tử có kiểu “T” được định nghĩa: Tp = <Vp, Op> trong đó ~ Vp = lleác đia chỉ có thể lưu trữ những đối tượng có kiểu TỊ, NULLI (với NULL là một giá trị đặc biệt tượng. trưng cho một giá trị không biết hoặc không quan tâm) ~ Op= lcác thao tác định địa chỉ của một đối tượng thuộc kiểu T khi biết con trỏ chỉ đến đối tượng đó] (thường gồm các thao tác tạo một con trỏ chỉ đến một đối tượng. thuộc kiểu T; hủy một đối tượng dữ liệu thuộc kiểu T khi biét con trỏ chỉ đến đối tượng đó) © Nói một cách dễ hiểu, kiểu con trỏ là kiểu cơ sở dùng lưu địa chỉ của một đối tượng dữ liệu khác. « _ Biến thuộc kiểu con trỏ Tp là biến mà giá trị của nó là địa chỉ cuả một vùng nhớ ứng với một biến kiểu T, hoặc là giá 100 tri NULL.
l ưuý “#” Kích thước của biến con trỏ tùy thuộc vào qui ước số byte địa chỉ trong từng mô hình bộ nhớ của từng ngôn ngữ lập trình cụ thé. Ví dụ: -_ biến con tré trong Pascal có kích thước 4 byte (2 byte địa chi segment + 2 byte dja chi offset) - _ biến con trổ trong C có kích thước 2 hoặc 4 byte tùy vào con trỏ near (chỉ lưu địa chỉ offset) hay far (lưu cả segment lẫn offset) “# Cú pháp định nghĩa một kiểu con trỏ trong ngôn ngữ C : typedef «<kiểuconưỏ> *<kiéucd sd>; Ví dụ typedef int *intpointer; intpointer p; hoặc int*pz là những khai báo hợp lệ. Các thao tác cơ bản trên kiểu con trỏ(minh họa bằng C) 101 - _ Khi một biến con trỏ p lưu địa chỉ của đối tượng x, ta nói íp tré dén x’. - __ Gán địa chỉ của một vùng nhớ con trỏ p: p = <địa chỉ»; P= <dia chỉ» + <giá trị nguyén>; ~ __ Truy xuất nội dung của đối tượng do p trỏ đến (*p) 3.
Biến động Trong nhiễu trường hợp, tại thời điểm biên dịch không thể xác định trước kích thước chính xác của một số đối tượng dữ liệu đo sự tổn tại và tăng trưởng của chúng phụ thuộc vào ngữ cảnh của việc thực hiện chương trình. Các đối tượng dữ liệu có đặc điểm kể trên nên được khai báo như biến động. Biến động là những biến thỏa: - _ Biến không được khai báo tưởng mình. ~_ Có thể được cấp phát hoặc giải phóng bộ nhớ khi người sử dụng yêu cầu.
-_ Các biến này không theo qui tắc phạm vi (tĩnh). 'Vùng nhớ của biến được cấp phát trong Heap. Kích thước có thể thay đổi trong quá trình sống. Do không được khai báo tường minh nên các biến động không có một định danh được kết buộc với địa chỉ vùng nhớ cấp phát cho nó, do đó gặp khó khăn khi truy xuất đến một biến động.
Để giải quyết vấn đề, biến con trỏ (là biến không động) được sử dụng để trỏ đến biến động. Khi tạo ra một biến động, phải dùng một con trỏ để lưu địa chỉ của biến này và sau đó, truy xuất đến biến động thông qua biến con 102 trỏ đã biết định danh. Hai thao tác cơ bản trên biến động là tạo và hủy một biến. động do biến con trỏ 'p' trỏ đến: Tạo ra một biến động và cho con trỏ “p' chỉ đến nó Hầu hết các ngôn ngữ lập trình cấp cao đều cung cấp những thủ tục cấp phát vùng nhớ cho một biến động và cho một con trỏ giữ địa chỉ vùng nhớ đó.
Một số hàm cấp phát bộ nhớ của C : void* malloe(size) ; _ // trả vể con trỏ chỉ đến một vùng nhớ. 1í size byte vừa được cấp phát. void* ca1loe(n„ size) ;// trả về con trỏ chỉ đến một vùng nhớ. 4 vừa được cấp phát gồm n phẫn tử, 1 mỗi phân tử có kích thước size byte new //hàm cấp phát bộ nhớ trong C++ Hủy một biến động do p chỉ đến Ham free(p) huỷ vùng nhớ cấp phát bởi hàm malloe hoặc calloe do p trở tới Hàm delete p huỷ vùng nhớ cấp phát bởi hàm new do p trỏ tới Ví dụ: int* pì, P2; 4ƒ cấp phát vùng nhớ cho một biến động kiểu int pl = (int*)malloc(sizeof(int)); 108 pl? = 5; // đất giá trị năm cho biến dong pl // cấp phát biến động kiểu mảng gồm 10 phẩn tử kiểu int p2 = (int*)calloc(10, sizeof|int)); (p2+3)* = 0; / đặt giá trị 0 cho phẩn tử thứ 4 của mảng p2 free(pl); £free(p2); : Il.
DANH SÁCH LIÊN KET (LINK LIST) 1. Định nghĩa : Cho T là một kiểu được định nghiã trước, kiểu danh sách. Tx gồm các phần tử thuộc kiểu T được định nghĩa là: ‘Tx = <Vx, Ox> trong đó: Vx = (tap hợp có thứ tự các phần tử kiểu T được móc nối với nhau tieo trình tự tuyến tính]; * Ox = (Tao danh sách; Tìm một phẩn tử trong danh sách; Chèn một phản tử vào danh sách; Huỳ một phần tử khỏi danh sách ; Liệt kê danh sách, Sấp xếp danh sách .] Ví du: Hồ sơ các học sinh của một trường được tổ chức thành. danh sách gồm nhiều hồ sơ của từng học sinh; số lượng học sinh trong trường có thể thay đổi do vậy cản có các thao tác thêm, hủy một hổ sơ; để phục vụ công tác giáo.
vụ cẩn thực hiện các thao tác tìm hỗ sơ của một học sinh, in danh sách hỗ sơ. Các hình thức tổ chức danh sách. Có nhiễu hình thức tổ chức mối liên hệ tuần tự giữa các phần tử trong cùng một danh sách: 104 « Mối liên hệ giữa các phần tử được thể hiện ngắm: mỗi phần tử. trong danh sách được đặc trưng bằng chỉ số.
Cặp phần tử x„, Xiq1 được xác định là kế cận trong danh sách nhờ vào quan hệ giữa cặp chỉ số¡ và (i+1). Với hình thức tổ chức này, các phần.