Cấu trúc dữ liệu động

Cấu trúc dữ liệu động
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
2
Mục tiêu
Giới thiệu khái niệm cấu trúc dữ liệu động.
Giới thiệu danh sách liên kết:
Các kiểu tổ chức dữ liệu theo DSLK.
Danh sách liên kết đơn: tổ chức, các thuật toán, ứng dụng.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
3
Kiểu dữ liệu tĩnh
Khái niệm: Một số đối tượng dữ liệu không thay thay đổi được kích thước, cấu trúc, . trong suốt qua trình sống. Các đối tượng dữ liệu thuộc những kiểu dữ liệu gọi là kiểu dữ liệu liệu tĩnh.
Một số kiểu dữ liệu tĩnh: 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 ...
? Các đối tượng dữ liệu được xác định thuộc những kiểu dữ liệu này thường cứng ngắt, gò bó ? khó diễn tả được thực tế vốn sinh động, phong phú.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
4
Ví dụ thực tế
Mô tả, quản lý một đối tượng `con người` cần thể hiện các thông tin tối thiểu như :
Họ tên
Số CMND
Thông tin về cha, mẹ
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
5
Ví dụ thực tế
Việc 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 bản ghi. 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 NGUOI, do vậy về nguyên tắc cần phải có định nghĩa như sau:
typedef struct NGUOI{
char Hoten[30];
int So_CMND ;
NGUOI Cha,Me;
};
Nhưng 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 ?
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
6
CTDL tĩnh - Một số hạn chế
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 ... Nếu dùng những cấu trúc dữ liệu tĩnh đã biết như mảng để biểu diễn ? Những thao tác phức tạp, kém tự nhiên ? chương trình khó đọc, khó bảo trì và nhất là khó có thể sử dụng bộ nhớ một cách có hiệu quả.
Dữ liệu tĩnh sẽ chiếm vùng nhớ đã dành cho chúng suốt quá trình hoạt động của chương trình ? sử dụng bộ nhớ kém hiệu quả.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
7
Hướng giải quyết
Cần xây dựng cấu trúc dữ liệu đáp ứng được các yêu cầu:
Linh động hơn.
Có thể thay đổi kích thước, cấu trúc trong suốt thời gian sống.
? Cấu trúc dữ liệu động.
Kiểu dữ liệu
Con trỏ
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
9
Biến không động
Biến không động (biến tĩnh, biến nửa tĩnh) là những biến thỏa:
Được khai báo tường minh,
Tồn tại khi vào phạm vi khai báo và chỉ mất khi ra khỏi phạm vi 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 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 không động
char b[10];
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
10
Kiểu dữ liệu Con trỏ
Cho trước kiểu dữ liệu T = .
Kiểu con trỏ - ký hiệu "Tp"- chỉ đến các phần tử có kiểu "T" được định nghĩa: Tp = , trong đó:
Vp = {{các điạ chỉ có thể lưu trữ những đối tượng có kiểu T}, NULL} (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 = {cá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 đó).
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
11
Kiểu dữ liệu Con trỏ
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á trị NULL.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
12
Kiểu dữ liệu Con trỏ
Kích thước của biến con trỏ tùy thuộc vào quy ướ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 bytes (2 bytes địa chỉ segment + 2 byte địa chỉ offset)
Biến con trỏ trong C có kích thước 2 hoặc 4 bytes tùy vào con trỏ near (chỉ lưu địa chỉ offset) hay far (lưu cả segment lẫn offset)

Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
13
Con trỏ - Khai báo
Cú pháp định nghĩa một kiểu con trỏ trong ngôn ngữ C :
typedef * < kiểu con trỏ>;
Ví dụ :
typedef int *intpointer;
intpointer p;
hoặc
int *p;
là những khai báo hợp lệ.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
14
Con trỏ - Thao tác căn bản
Các thao tác cơ bản trên kiểu con trỏ:(minh họa bằng C)
Khi 1 biến con trỏ p lưu địa chỉ của đối tượng x, ta nói `p trỏ đến x`.
Gán địa chỉ của một vùng nhớ con trỏ p:
p = <địa chỉ>;
p = <địa chỉ> + ;
Truy xuất nội dung của đối tượng do p trỏ đến (*p)
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
15
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 do 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 minh.
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.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
16
Biến độ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 trỏ đã biết định danh.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
17
Biến động
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ủy một biến động do p chỉ đến
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
18
Biến động
Tạo ra một biến động và cho con trỏ `p` chỉ đến nó
void* malloc(size); // trả về con trỏ chỉ đến vùng nhớ
// size byte vừa được cấp phát.
void* calloc(n,size);// trả về con trỏ chỉ đến vùng nhớ
// vừa được cấp phát gồm n phần tử,
// mỗi phần tử có kích thước size byte
new // toán tử cấp phát bộ nhớ trong C++
Hàm free(p) huỷ vùng nhớ cấp phát bởi hàm malloc hoặc calloc do p trỏ tới
Toán tử delete p huỷ vùng nhớ cấp phát bởi toán tử new do p trỏ tới
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
19
Biến động - Ví dụ
int *p1, *p2;
// caáp phaùt vuøng nhôù cho 1 bieán ñoäng kieåu int
p1 = (int*)malloc(sizeof(int));
*p1 = 5; // ñaët giaù trò 5 cho bieán ñoäng ñang ñöôïc p1 quaûn lyù
// caáp phaùt bieán ñoäng kieåu maûng goàm 10 phaàn töû kieåu int
p2 = (int*)calloc(10, sizeof(int));
*(p2+3) = 0; // ñaët giaù trò 0 cho phaàn töû thöù 4 cuûa maûng p2
free(p1);
free(p2);
Danh sách liên kết (List)
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
21
Danh sách liên kết (List)
Định nghĩa
Đị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 =
trong đó:
Vx = {Tập hợp có thứ tự các phần tử kiểu T được móc nối với nhau theo trình tự tuyến tính};
Ox = {Tạo danh sách; Tìm 1 phần tử trong danh sách; Chèn 1 phần tử vào danh sách; Huỷ 1 phần tử khỏi danh sách ; Liệt kê danh sách, Sắp xếp danh sách ...}
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
22
Danh sách liên kết (List)
Định nghĩa
Ví d?: 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ấu trúc Dữ liệu - Cấu trúc dữ liệu động
23
Danh sách liên kết (List)
Các hình thức tổ chức danh sách
Các hình thức tổ chức danh sách:
Mối liên hệ giữa các phần tử được thể hiện ngầm
Mối liên hệ giữa các phần tử được thể hiện tường minh
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
24
Danh sách liên kết (List)
Các hình thức tổ chức danh sách
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ử xi, xi+1 được xác định là kế cận trong danh sách nhờ vào quan hệ giữa cặp chỉ số i và (i+1).
Các phần tử của danh sách thường bắt buộc phải lưu trữ liên tiếp trong bộ nhớ để có thể xây dựng công thức xác định địa chỉ phần tử thứ i
address(i) = address(1) + (i-1)*sizeof(T)
Có thể xem mảng và tập tin là những danh sách đặc biệt được tổ chức theo hình thức liên kết "ngầm" giữa các phần tử.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
25
Danh sách liên kết (List)
Các hình thức tổ chức danh sách
Mối liên hệ giữa các phần tử được thể hiện ngầm:
Cho phép truy xuất ngẫu nhiên, đơn giản và nhanh chóng đến một phần tử bất kỳ trong danh sách
Hạn chế về mặt sử dụng bộ nhớ.
Đối với mảng, số phần tử được xác định trong thời gian biên dịch và cần cấp phát vùng nhớ liên tục.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
26
Danh sách liên kết (List)
Các hình thức tổ chức danh sách
Mối liên hệ giữa các phần tử được thể hiện ngầm:
Trong trường hợp tổng kích thước bộ nhớ trống còn đủ để chứa toàn bộ mảng nhưng các ô nhớ trống lại không nằm kế cận nhau thì cũng không cấp phát vùng nhớ cho mảng được.
Ngoài ra do kích thước mảng cố định mà số phần tử của danh sách lại khó dự trù chính xác nên có thể gây ra tình trạng thiếu hụt hay lãng phí bộ nhớ.
Các thao tác thêm, hủy một phần tử vào danh sách được thực hiện không tự nhiên trong hình thức tổ chức này.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
27
Danh sách liên kết (List)
Các hình thức tổ chức danh sách
Mối liên hệ giữa các phần tử được thể hiện tường minh
Mỗi phần tử ngoài các thông tin về bản thân còn chứa một liên kết (địa chỉ) đến phần tử kế trong danh sách nên còn được gọi là danh sách móc nối.
Do liên kết tường minh, với hình thức này các phần tử trong danh sách không cần phải lưu trữ kế cận trong bộ nhớ
Khắc phục được các khuyết điểm của hình thức tổ chức mảng
Việc truy xuất đến một phần tử đòi hỏi phải thực hiện truy xuất qua một số phần tử khác.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
28
Danh sách liên kết (List)
Các hình thức tổ chức danh sách
Mối liên hệ giữa các phần tử được thể hiện tường minh
Có nhiều kiểu tổ chức liên kết giữa các phần tử trong danh sách như :
Danh sách liên kết đơn
Danh sách liên kết kép
Danh sách liên kết vòng
.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
29
Danh sách liên kết (List)
Các hình thức tổ chức danh sách
Danh sách liên kết đơn: mỗi phần tử liên kết với phần tử đứng sau nó trong danh sách:


Danh sách liên kết kép: mỗi phần tử liên kết với các phần tử đứng trước và sau nó trong danh sách:
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
30
Danh sách liên kết (List)
Các hình thức tổ chức danh sách
Danh sách liên kết vòng : phần tử cuối danh sách liên kết với phần tử đầu danh sách:
Danh sách đơn - SList (xâu đơn)
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
32
Mỗi phần tử của danh sách đơn g?m 2 thành phần :
Thành phần dữ liệu: lưu trữ các thông tin về bản thân phần tử .
Thành phần mối liên kết: lưu trữ địa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu là phần tử cuối danh sách.
typedef struct NODE {
Data Info; // Data là kiểu đã định nghĩa trước
struct NODE * pNext; //con trỏ chỉ đến cấu trúc NODE
};
SList - Tổ chức 1 phần tử
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
33
Ví dụ : Định nghĩa một phần tử trong danh sách đơn lưu trữ hồ sơ sinh viên:
typedef struct SV {
char Ten[30];
int MaSV;
};
typedef struct SVNode {
SV Info;
struct SVNode * pNext;
};
SList - Tổ chức 1 phần tử
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
34
Một phần tử trong danh sách đơn là một biến động sẽ được yêu cầu cấp phát khi cần. Và danh sách đơn chính là sự liên kết các biến động này với nhau do vậy đạt được sự linh động khi thay đổi số lượng các phần tử
SList - Tổ chức, quản lý
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
35
SList - Tổ chức, quản lý
Để quản lý một xâu đơn chỉ cần biết địa chỉ phần tử đầu xâu.
Con trỏ Head sẽ được dùng để lưu trữ địa chỉ phần tử đầu xâu, ta gọi Head là đầu xâu. Ta có khai báo:
NODE* pHead;
Để tiện lợi, có thể sử dụng thêm một con trỏ pTail giữ địa chỉ phần tử cuối xâu. Khai báo pTail như sau :
NODE* pTail;
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
36
Khai báo kiểu của 1 phần tử và kiểu danh sách liên kết đơn:
// kiểu của một phần tử trong danh sách
typedef struct NODE {
Data Info;
struct NODE * pNext;
};

typedef struct SLIST // kiểu danh sách liên kết
{
NODE* pHead;
NODE* pTail;
};
SList - Tổ chức, quản lý
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
37
Thủ tục GetNode để tạo ra một phần tử cho danh sách với thông tin chứa trong x
NODE* GetNode(Data x)
{
NODE *p;
// Cấp phát vùng nhớ cho phần tử
p = new NODE;
if (p==NULL) {
printf("Không đủ bộ nhớ"); return NULL;
}
p->Info = x; // Gán thông tin cho phần tử p
p->pNext = NULL;
return p;
}
SList - Tạo một phần tử
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
38
Để tạo một phần tử mới cho danh sách, cần thực hiện câu lệnh:
new_ele = GetNode(x);
? new_ele sẽ quản lý địa chỉ của phần tử mới được tạo.
SList - Tạo một phần tử
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
39
Tạo danh sách rỗng
Thêm một phần tử vào danh sách
Tìm kiếm một giá trị trên danh sách
Trích một phần tử ra khỏi danh sách
Duyệt danh sách
S?p xếp danh sách
Hủy toàn bộ danh sách
SList - Các thao tác cơ sở
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
40
void Init(SLIST &l)
{
l.pHead = l.pTail = NULL;
}
SList - Khởi tạo danh sách rỗng
pHead
pTail
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
41
3 vị trí thêm phần tử mới vào danh sách:
Thêm vào đầu danh sách
Nối vào cuối danh sách
Chèn vào danh sách sau một phần tử q
SList - Thêm một phần tử
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
42
pHead
pTail
new_ele
SList - Thêm một phần tử
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
43
B
C
D
E
pHead
pTail
SList - Thêm một phần tử vào đầu
new_ele
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
44
//input: danh sách (head, tail), phần tử mới new_ele
//output: danh sách (head, tail) với new_ele ở đầu DS
Nếu Danh sách rỗng Thì
Head = new_ele;
Tail = Head;
Ngược lại
new_ele ->pNext = Head;
Head = new_ele ;
SList - Thêm một phần tử vào đầu
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
45
void AddFirst(SLIST &l, NODE* new_ele)
{
if (l.pHead == NULL) //Xaâu roãng
l.pHead = l.pTail = new_ele;
else {
new_ele->pNext = l.pHead;
l.pHead = new_ele;
}
}
SList - Thêm một phần tử vào đầu
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
46
//input: danh sách (head, tail), thành phần dữ liệu X
//output: danh sách (head, tail) với phần tử chứa X ở đầu DS
Tạo phần tử mới new_ele để chứa dữ liệu X
Nếu tạo được:
Thêm new_ele vào đầu danh sách
Ngược lại
Báo lỗi
SList
Thêm một thành phần dữ liệu vào đầu
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
47
NODE* InsertHead(SLIST &l, Data x)
{
NODE* new_ele = GetNode(x);
if (new_ele == NULL)
return NULL;
AddFirst(l, new_ele);
return new_ele;
}
SList
Thêm một thành phần dữ liệu vào đầu
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
48
B
C
D
E
pHead
pTail
SList - Thêm một phần tử vào cu?i
new_ele
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
49
//input: danh sách (head, tail), phần tử mới new_ele
//output: danh sách (head, tail) với new_ele ở cu?i DS
Nếu Danh sách rỗng Thì
Head = new_ele;
Tail = Head;
Ngược lại
Tail->pNext = new_ele ;
Tail = new_ele ;
SList - Thêm một phần tử vào cu?i
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
50
void AddTail(SLIST &l, NODE *new_ele)
{
if (l.pHead==NULL)
l.pHead = l.pTail = new_ele;
else
l.pTail = l.pTail->pNext = new_ele;
}
SList - Thêm một phần tử vào cu?i
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
51
//input: danh sách (head, tail), thành phần dữ liệu X
//output: danh sách (head, tail) với phần tử chứa X ở cuối DS
Tạo phần tử mới new_ele để chứa dữ liệu X
Nếu tạo được:
Thêm new_ele vào cuối danh sách
Ngược lại
Báo lỗi
SList
Thêm một thành phần dữ liệu vào cuối
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
52
NODE* InsertTail(SLIST &l, Data x)
{
NODE* new_ele = GetNode(x);

if (new_ele == NULL)
return NULL;
AddTail(l, new_ele);
return new_ele;
}
SList
Thêm một thành phần dữ liệu vào cuối
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
53
B
C
D
E
pHead
pTail
SList - Chèn một phần tử sau q
new_ele
q
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
54
//input: danh sách (head, tail), q, phần tử mới new_ele
//output: danh sách (head, tail) với new_ele ở sau q
Nếu ( q != NULL) thì
new_ele -> pNext = q -> pNext;
q -> pNext = new_ele ;
Nếu ( q == Tail) thì
Tail = new_ele;
Ngược lại
Thêm new_ele vào đầu danh sách
SList - Chèn một phần tử sau q
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
55
void AddAfter(SLIST &l,NODE *q, NODE* new_ele)
{
if (q!=NULL) {
new_ele->pNext = q->pNext;
q->pNext = new_ele;
if(q == l.pTail)
l.pTail = new_ele;
}
else // theâm vaøo ñaàu danh saùch
AddFirst(l, new_ele);
}
SList - Chèn một phần tử sau q
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
56
SList - Tìm một phần tử
D
A
B
C
E
pHead
pTail
C
p
X
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
57
SList - Tìm một phần tử
//input: danh sách (head, tail), dữ liệu cần tìm X
//output: địa chỉ phần tử chứa X
Bước 1:
p = Head; //Cho p trỏ đến phần tử đầu danh sách
Bước 2: Trong khi (p != NULL) và (p->Info != x ) thực hiện:
B21 : p:=p->Next;// Cho p trỏ tới phần tử kế
Bước 3:
Nếu p != NULL thì p trỏ tới phần tử cần tìm
Ngược lại: không có phần tử cần tìm.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
58
NODE *Search(SLIST l, Data X)
{
NODE *p;

for (p=l.pHead;(p)&&(p->Info!=X);p=p->pNext);
return p;
}
SList - Tìm một phần tử
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
59
3 trường hợp trích 1 phần tử ra khỏi danh sách:
Trích phần tử đầu
Trích phần tử sau một phần tử q
Trích phần tử có giá trị X

Lưu ý: Nếu muốn hủy phần tử vừa trích, cần gọi thêm toán tử delete để giải phóng bộ nhớ.
SList - Trích một phần tử
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
60
SList - Trích phần tử đầu xâu
A
B
C
D
E
pHead
pTail
p
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
61
//input: xâu (head, tail)
//output: xâu đã bị trích phần tử đầu xâu
Nếu (Head != NULL) thì
p = Head; // p là phần tử cần trích
Head = Head->pNext; // tách p ra khỏi xâu
p -> pNext = NULL;
Nếu Head=NULL thì Tail = NULL; //Xâu rỗng
SList - Trích phần tử đầu xâu
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
62
NODE* PickHead(SLIST &l)
{
NODE *p = NULL;
if (l.pHead != NULL) {
p = l.pHead;
l.pHead = l.pHead->pNext;
p->pNext = NULL;
if(l.pHead == NULL)
l.pTail = NULL;
}
return p;
}
SList - Trích phần tử đầu xâu
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
63
Data RemoveHead(SLIST &l)
{
if (l.pHead == NULL)
return NULLDATA;
NODE * p = PickHead(l);
Data x = p->Info;
delete p;
return x;
}
SList - Trích & hủy phần tử đầu xâu
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
64
SList - Trích phần tử sau q
A
B
C
D
E
pHead
pTail
p
q
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
65
//input: xâu (head, tail), con trỏ q
//output: xâu đã bị trích phần tử sau phần tử q
Nếu (q!= NULL)
p = q->pNext; // p là phần tử cần trích
Nếu (p != NULL) // q không phải là cuối xâu
q->pNext = p->pNext; // tách p ra khỏi xâu
p->pNext = NULL;
Nếu (p==Tail)
Tail = q;
Ngược lại:
Trích phần tử đầu xâu
SList - Trích phần tử sau q
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
66
NODE * PickAfter (SLIST &l, NODE *q)
{
NODE *p;
if ( q != NULL) {
p = q ->pNext ;
if ( p != NULL) {
if (p == l.pTail) l.pTail = q;
q->pNext = p->pNext;
p->pNext = NULL;
}
}
else p = PickHead(l);
return p;
}
SList - Trích phần tử sau q
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
67
SList - Trích phần tử có khóa K
D
A
B
C
E
pHead
pTail
C
p
K
q
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
68
//input: xâu (head, tail), khóa k
//output: xâu đã bị trích phần tử có khóa k
Bước 1:
Tìm phần tử p có khóa k và phần tử q đứng trước nó
Bước 2:
Nếu (p!= NULL) thì // tìm thấy k
Trích p ra khỏi xâu tương tự trích phần tử sau q;
Ngược lại
Báo không có k;
SList - Trích phần tử có khóa K
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
69
NODE * PickNode(SLIST &l, Data k)
{
NODE *p = l.pHead;
NODE *q = NULL;
while ((p != NULL) && (p->Info != k))
{
q = p;
p = p->pNext;
}
if(p == NULL) return NULL;
return PickAfter(l, q);
}
SList - Trích phần tử có khóa K
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
70
Duyệt danh sách là thao tác thường được thực hiện khi có nhu cầu xử lý các phần tử của danh sách theo cùng một cách thức hoặc khi cần lấy thông tin tổng hợp từ các phần tử của danh sách như:
Đếm các phần tử của danh sách,
Tìm tất cả các phần tử thoả điều kiện,
SList - Duyệt danh sách
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
71
Bước 1:p = Head; //Cho p trỏ đến phần tử đầu danh sách
Bước 2: Trong khi (Danh sách chưa hết) thực hiện
B21 : Xử lý phần tử p;
B22 : p:=p->pNext; // Cho p trỏ tới phần tử kế
void ProcessList (LIST &l)
{
NODE *p;
p = l.pHead;
while (p!= NULL)
{
ProcessNode(p); // xử lý cụ thể tùy ứng dụng
p = p->pNext;
}
}
SList - Duyệt danh sách
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
72
Để h?y toàn bộ danh sách, thao tác xử lý bao gồm hành động giải phóng một phần tử, do vậy phải cập nhật các liên kết liên quan:
Bước 1: Trong khi (Danh sách chưa hết) thực hiện
B11:
p = Head;
Head:=Head->pNext; // Cho p trỏ tới phần tử kế
B12:
Hủy p;
Bước 2:
Tail = NULL; //Bảo đảm tính nhất quán khi xâu rỗng
SList - Hủy toàn bộ danh sách
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
73
void RemoveList(LIST &l)
{
NODE *p;
while (l.pHead!= NULL) {
p = l.pHead;
l.pHead = p->pNext;
delete p;
}
l.pTail = NULL;
}
SList - Hủy toàn bộ danh sách
Sắp xếp danh sách
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
75
Sắp xếp danh sách
Cách tiếp cận:
Phương án 1: Hoán vị nội dung các phần tử trong danh sách (thao tác trên vùng Info).
Phương án 2: Thay đổi các mối liên kết (thao tác trên vùng Next)
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
76
Sắp xếp danh sách
Hoán vị nội dung các phần tử trong danh sách
Cài đặt lại trên xâu một trong những thuật toán sắp xếp đã biết trên mảng
Điểm khác biệt duy nhất là cách thức truy xuất đến các phần tử trên xâu thông qua liên kết thay vì chỉ số như trên mảng.
Do thực hiện hoán vị nội dung của các phần tử nên đòi hỏi sử dụng thêm vùng nhớ trung gian ? chỉ thích hợp với các xâu có các phần tử có thành phần Info kích thước nhỏ.
Khi kích thước của trường Info lớn, việc hoán vị giá trị của hai phân tử sẽ chiếm chi phí đáng kể.
Không tận dụng được các ưu điểm của xâu!
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
77
Slist - Sắp xếp
Hoán vị nội dung các phần tử trong danh sách
void ListSelectionSort (LIST &l)
{
NODE *min, *p,*q;
p = l.pHead;
while(p != l.pTail) {
q = p->pNext; min = p;
while(q != NULL) {
if(q->Info< min->Info )
min = q; // ghi nhaän vò trí phaàn töû min hieän haønh
q = q->pNext;
}
Hoanvi(min->Info, p->Info);
p = p->pNext;
}
}
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
78
Slist - Sắp xếp Thay đổi các mối liên kết
Thay vì hoán đổi giá trị, ta sẽ tìm cách thay đổi trình tự móc nối của các phần tử sao cho tạo lập nên được thứ tự mong muốn ? chỉ thao tác trên các móc nối (pNext).
Kích thước của trường pNext:
Không phụ thuộc vào bản chất dữ liệu lưu trong xâu
Bằng kích thước 1 con trỏ (2 hoặc 4 byte trong môi trường 16 bit, 4 hoặc 8 byte trong môi trường 32 bit.)
Thao tác trên các móc nối thường phức tạp hơn thao tác trực tiếp trên dữ liệu.
?Cần cân nhắc khi chọn cách tiếp cận: Nếu d? liệu không quá lớn thì nên chọn phương án 1 hoặc một thuật toán hiệu quả nào đó.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
79
Một trong những cách thay đổi móc nối đơn giản nhất là tạo một danh sách mới là danh sách có thứ tự gồm các phần tử trích từ danh sách cũ.
Giả sử danh sách mới sẽ được quản lý bằng con trỏ đầu xâu Result, ta có thuật toán chọn trực tiếp c?a phương án 2 như sau:
B1: Khởi tạo danh sách mới Result là rỗng;
B2: Tìm trong danh sách cũ l phần tử nhỏ nhất - min;
B3: Tách min khỏi danh sách cũ;
B4: Chèn min vào cuối danh sách Result;
B5: Lặp lại bước 2 khi chưa hết danh sách cũ;
Slist - Sắp xếp Thay đổi các mối liên kết
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
80
4
2
8
6
pHead
SList - Sắp xếp chọn trực tiếp
pHead2
pTail2
min
pTail
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
81
10
4
2
8
6
pHead
SList - Sắp xếp chọn trực tiếp
pHead2
min
pTail
pTail2
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
82
10
4
2
8
6
pHead
pTail
SList - Sắp xếp chọn trực tiếp
pHead2
min
pTail2
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
83
10
4
2
8
6
pHead
pTail
SList - Sắp xếp chọn trực tiếp
pHead2
min
pTail2
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
84
10
4
2
8
6
pHead
pTail
SList - Sắp xếp chọn trực tiếp
pHead2
min
pTail2
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
85
NODE* FindMinprev (LIST list)
{
NODE *min, *minprev, *p, *q;
minprev = q = NULL; min=p = list.pHead;
while(p != NULL) {
if (p->Info < min->Info) {
min = p; minprev = q;
}
q = p; p = p->pNext;
}
return minprev;
}
SList - Sắp xếp chọn trực tiếp
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
86
void ListSelectionSort2 (SLIST &list)
{
SLIST lRes;
NODE *min, *minprev;
lRes.pHead = lRes.pTail = NULL;
while(list.pHead != NULL) {
minprev = FindMinprev(list);
min = PickAfter(list, minprev);
AddTail(lRes, min);
}
list = lRes;
}
SList - Sắp xếp chọn trực tiếp
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
87
SList
Một số thuật toán sắp xếp hiệu quả
Thuật toán Quick Sort
Thuật toán Merge Sort
Thuật toán Radix Sort
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
88
SList -Quick Sort: Thuật toán
//input: xâu (head, tail)
//output: xâu đã được sắp tăng dần
Bước 1: Nếu xâu có ít hơn 2 phần tử
Dừng; //xâu đã có thứ tự
Bước 2: Chọn X là phần tử đầu xâu L làm ngưỡng. Trích X ra khỏi L.
Bước 3: Tách xâu L ra làm 2 xâu L1 (gồm các phần tử nhỏ hơn hay bằng X) và L2 (gồm các phần tử lớn hơn X).
Bước 4: Sắp xếp Quick Sort (L1).
Bước 5: Sắp xếp Quick Sort (L2).
Bước 6: Nối L1, X, và L2 lại theo trình tự ta có xâu L đã được sắp xếp.
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
89
SList - Sắp xếp quick sort
pHead
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
90
SList - quick sort: phân hoạch
pHead
X
Chọn phần tử đầu xâu làm ngưỡng
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
91
SList - quick sort: phân hoạch
pHead
6
8
2
4
5
1
X
Tách xâu hiện hành thành 2 xâu
pH1
pH2
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
92
SList - quick sort: phân hoạch
pHead
6
8
2
4
5
1
X
Tách xâu hiện hành thành 2 xâu
pH1
pH2
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
93
SList - quick sort: phân hoạch
pHead
6
8
2
4
5
1
X
Tách xâu hiện hành thành 2 xâu
pH1
pH2
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
94
SList - quick sort: phân hoạch
pHead
6
8
2
4
5
1
X
Tách xâu hiện hành thành 2 xâu
pH1
pH2
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
95
SList - quick sort
pHead
6
8
2
4
5
1
X
Sắp xếp các xâu pH1, pH2
pH1
pH2
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
96
SList - quick sort
pHead
6
8
2
4
5
1
X
Nối pH1, X, pH2
pH1
pH2
Đưa kết quả vào pHead
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
97
void SListAppend(SLIST &list, LIST &list2)
{
if (list2.pHead == NULL) return;
if (list.pHead == NULL)
list = list2;
else {
list.pTail->pNext = list2.pHead;
list.pTail = list2.pTail;
}
Init(list2);
}
SList - Nối 2 danh sách
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
98
void SListQSort(SLIST &list) {
NODE *X, *p;
SLIST list1, list2;
if (list.pHead == list.pTail) return;
Init(list1); Init(list2);
X = PickHead(list);
while (list.pHead != NULL) {
p = PickHead(list);
if (p->Info <= X->Info) AddTail(list1, p);
else AddTail(list2, p);
}
SListQSort(list1); SListQSort(list2);
SListAppend(list, list1);
AddTail(list, X);
SListAppend(list, list2);
}
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
99
MYLIST:
void QuickSort() {
NODE X, p;
MYLIST list1, list2;
if (Head == Tail) return;
X = PickHead();
while (Head != NULL) {
p = PickHead();
if (p.Info <= X.Info) list1.AddTail(p);
else list2.AddTail(p);
}
list1.QuickSort(); list2.QuickSort();
Append(list1);
AddTail(X);
Append(list2);
}
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
100
Nhận xét:
Quick sort trên xâu đơn đơn giản hơn phiên bản của nó trên mảng một chiều
Khi dùng quick sort sắp xếp một xâu đơn, chỉ có một chọn lựa phần tử cầm canh duy nhất hợp lý là phần tử đầu xâu. Chọn bất kỳ phần tử nào khác cũng làm tăng chi phí một cách không cần thiết do cấu trúc tự nhiên của xâu.
SList - Quick sort: nhận xét
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
101
//input: xâu L
//output: xâu L đã được sắp tăng dần
Bước 1: Nếu xâu có ít hơn 2 phần tử
Dừng; //Xâu đã có thứ tự
Bước 2: Phân phối luân phiên từng đường chạy của xâu L vào 2 xâu con L1 và L2.
Bước 3: Nếu L2 không rỗng
B31: Sắp xếp Merge Sort (L1).
B32: Sắp xếp Merge Sort (L2).
B33: Trộn L1 và L2 đã sắp xếp lại ta có xâu L đã được sắp xếp.
Bước 4: Ngược lại: L = L1;
SList - Merge sort: thuật toán
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
102




Phân phối các đường chạy của l vào l1, l2:
SList - Merge sort: Ví dụ
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
103
Sắp xếp l1:
Phân phối các đường chạy của l1 vào l11, l12:




Trộn l11, l12 lại thành l1:
SList - Merge sort: Ví dụ
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
104
Sắp xếp l2:
Phân phối các đường chạy của l2 vào l21, l22:




Trộn l21, l22 lại thành l2:
SList - Merge sort: Ví dụ
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
105
Trộn l1, l2 lại thành l:
SList - Merge sort: Ví dụ
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
106
void SListMergeSort(SLIST & list)
{
SLIST l1, l2;
if (list.pHead == list.pTail) //ñaõ coù thöù töï
return;
Init(l1); Init(l2);
//Phaân phoái list thaønh l1 vaø l2 theo töøng ñöoøng chaïy
SListDistribute(list, l1, l2);
if (l2.pHead) {
SListMergeSort(l1); //Goïi ñeä qui ñeå sort l1
SListMergeSort(l2); //Goïi ñeä qui ñeå sort l2
//Troän l1 vaø l2 ñaõ coù thöù töï thaønh list
SListMerge(list, l1, l2);
}
else SListAppend(list, l1);
}
SList - Merge sort: cài đặt
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
107
void SListDistribute(SLIST &list,
SLIST &l1, SLIST &l2)
{
NODE *p = PickHead(list);
AddTail(l1, p);
if (list.pHead)
if (p->Info <= list.pHead->Info)
SListDistribute(list, l1, l2);
else
SListDistribute(list, l2, l1);
}
SList - Merge sort: cài đặt
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
108
void SListMerge(SLIST& list,
SLIST& l1, SLIST& l2)
{
NODE *p;
while ((l1.pHead) && (l2.pHead))
{
if(l1.pHead->Info <= l2.pHead->Info)
p = PickHead(l1);
else
p = PickHead(l2);
AddTail(list, p);
}
SListAppend(list, l1);
SListAppend(list, l2);
}
SList - Merge sort: cài đặt
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
109
MYLIST:
void MergeSort()
{
MYLIST l1, l2;
if (Head == Tail) //ñaõ coù thöù töï
return;
//Phaân phoái list thaønh l1 vaø l2 theo töøng ñöoøng chaïy
Distribute(l1, l2);
if (l2.pHead) {
l1.MergeSort(); //Goïi ñeä qui ñeå sort l1
l2.MergeSort(); //Goïi ñeä qui ñeå sort l2
//Troän l1 vaø l2 ñaõ coù thöù töï thaønh list
Merge(l1, l2);
}
else Append(l1);
}
SList - Merge sort: cài đặt
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
110
MYLIST:
void Distribute(ref MYLIST l1, ref MYLIST l2)
{
NODE p = PickHead();
l1.AddTail(p);
if (Head)
if (p.Info <= Head.Info)
Distribute(l1, l2);
else
Distribute(l2, l1);
}
SList - Merge sort: cài đặt
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
111
MYLIST:
void Merge(ref MYLIST l1, ref MYLIST l2)
{
NODE p;
while ((l1.pHead) && (l2.pHead))
{
if(l1.pHead.Info <= l2.pHead.Info)
p = PickHead(l1);
else
p = PickHead(l2);
AddTail(p);
}
Append(l1);
Append(l2);
}
SList - Merge sort: cài đặt
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
112
Nhận xét:
Merge sort trên xâu đơn giản hơn phiên bản trên mảng một chiều.
Khi dùng Merge sort sắp xếp một xâu đơn, không cần dùng thêm vùng nhớ phụ như khi cài đặt trên mảng một chiều.
Thủ tục Merge trên xâu không phức tạp như trên mảng vì chỉ phải trộn hai xâu đã có thứ tự, trong khi trên mảng phải trộn hai mảng bất kỳ.
SList - Merge sort: nhận xét
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
113
//input: xâu L
//output: xâu L đã được sắp tăng dần
//dữ liệu trung gian: mười danh sách rỗng B0, B1, ., B9
B1: + Khởi tạo các danh sách (lô) rỗng B0, B1, ., B9;
+ k = 0;
B2: Trong khi L khác rỗng:
+ p ? phần tử đầu xâu của L;
+ Nối p vào cuối danh sách Bd với d là chữ số thứ k của p;
B3: Nối B0, B1, ., B9 lại thành L;
B4: + k = k+1;
+ Nếu k < m: quay lại Bước 2
SList - Radix sort: thuật toán
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
114
pHead
413
32
205
965
812
723
610
57
0
1
2
3
4
5
6
7
8
9
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
115
pHead
413
32
205
812
965
723
610
57
0
1
2
3
4
5
6
7
8
9
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
116
pHead
413
32
205
812
965
723
610
57
0
1
2
3
4
5
6
7
8
9
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
117
pHead
32
413
723
205
965
57
610
812
0
1
2
3
4
5
6
7
8
9
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
118
pHead
32
413
723
205
965
57
610
812
0
1
2
3
4
5
6
7
8
9
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
119
pHead
32
413
723
205
965
57
610
812
0
1
2
3
4
5
6
7
8
9
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
120
pHead
610
413
723
32
57
965
205
812
0
1
2
3
4
5
6
7
8
9
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
121
pHead
610
413
723
32
57
965
205
812
0
1
2
3
4
5
6
7
8
9
Cấu trúc Dữ liệu - Cấu trúc dữ liệu động
122
pHead
610
413
723
32
57
965
205
812
0
1
2
3
4
5
6
7
8