Bài giảng môn Cấu trúc dữ liệu - Chương 4: Danh sách (list)
5.2.3.d. Hủy ngăn xếp (dùng danh sách liên kết)
void SSDelete (SSTACK &SList)
{
while (SList != NULL)
{ SSTACK TempElement = SList;
SList = SList ->Next;
TempElement ->Next = NULL;
delete TempElement;
}
}
112 trang |
Chia sẻ: truongthinh92 | Lượt xem: 1576 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng môn Cấu trúc dữ liệu - Chương 4: Danh sách (list), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
77
Chương 4:
DANH SÁCH (LIST)
78
NỘI DUNG CHƯƠNG 4
1. Khái niệm danh sách
2. Các phép toán trên danh sách
3. Danh sách đặc
• Định nghĩa
• Biểu diễn danh sách đặc
• Các thao tác trên danh sách đặc
• Ưu nhược điểm và ứng dụng
4. Danh sách liên kết
• Định nghĩa
• Danh sách liên kết đơn
• Danh sách liên kết kép
• Ưu nhược điểm của danh sách liên kết
5. Danh sách hạn chế
• Hàng đợi
• Ngăn xếp
• Ứng dụng của danh sách hạn chế
79
1. Khái niệm danh sách
• Danh sách a1, a2, .aN là tập hợp các phần tử có kiểu
dữ liệu xác định và giữa chúng có 1 mối quan hệ nào đó.
Nếu biết phần tử ai vị trí của phần tử ai+1
• Số phần tử trong một danh sách là chiều dài của 1 danh
sách. Danh sách rỗng là danh sách có chiều dài = 0
• Cho T là một kiểu được định nghĩa 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ác thứ tự gồm một số biến động các phần tử kiểu
T }.
• 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.}.
80
2. Các phép toán trên danh sách
Tùy theo loại của từng danh sách sẽ có các phép toán khác
nhau, các phép toán thông thường như sau:
2.1. Tạo mới 1 danh sách
• Đưa vào danh sách nội dung các phần tử.
• Chiều dài của danh sách là xác định.
2.2. Thêm 1 phần tử vào danh sách
• Khi thêm 1 phần tử chiều dài danh sách tăng lên.
• Có thao tác thêm vào đầu, cuối hay tại 1 vị trí xác định của
danh sách.
2.3. Tìm kiếm 1 phần tử trong danh sách
• Tìm 1 phần tử trong danh sách thỏa mãn điều kiện nào đó
• Dùng các thuật toán tìm kiếm trong chương “Tìm kiếm”
81
2. Các phép toán trên danh sách
2.4. Loại bớt 1 phần tử trong danh sách
• Chiều dài danh sách giảm xuống 1 phần tử
• Công việc loại bớt cũng bao gồm thao tác tìm kiếm ra
phần tử cần hủy trong danh sách.
2.5. Sửa đổi giá trị 1 phần tử trong danh sách
• Thay đổi thông tin của 1 phần tử trong danh sách
• Công việc cập nhật phần tử cũng bao gồm thao tác tìm
kiếm ra phần tử cần hủy trong danh sách.
2.6. Sắp xếp danh sách
• Dùng các thuật toán trong chương sắp xếp.
82
2. Các phép toán trên danh sách
2.7. Tách danh sách thành nhiều danh sách con
• Tách danh sách thành các DS con theo 1 quy luật chia
nào đó
• Tổng chiều dài các danh sách được chia bằng chiều dài
danh sách ban đầu
2.8. Nhập nhiều danh sách thành 1 danh sách
• Nhập các danh sách thành 1 danh sách
• Tổng chiều dài danh sách bằng tổng chiều dài các danh
sách ban đầu
• Có thể ghép đuôi các danh sách hay trộn lẫn theo 1
phương pháp nhất định
2.9. Sao chép 1 danh sách: Sao chép toàn bộ nội dung
của danh sách thành 1 danh sách khác.
2.10. Hủy danh sách: Huỷ nội dung hay cả vùng nhớ chứa
DS
83
3. Danh sách đặc (Condensed List)
3.1. Định nghĩa
• Danh sách đặc là danh sách mà không gian bộ nhớ lưu
trữ các phần tử nằm kề cận nhau trong bộ nhớ.
3.2. Biểu diễn danh sách đặc
• Biểu diễn danh sách đặc dùng 1mảng các phần tử có
kiểu dử liệu là kiểu dữ liệu của các phần tử trong danh
sách
• Cần biết chiều dài tối đa của một danh sách đặc thông
qua 1 biến.
• Cần biết chiều dài thực của một danh sách đặc thông qua
1 biến.
VD:#define MaxLength 1000
int RealLength;
T CD_List[MaxLength]
Hay: T * CD_List = new T[MaxLength]
84
3. Danh sách đặc (tt)
3.3. Các thao tác trên danh sách đặc
Một số thao tác trên danh sách đặc được thống kê tóm tắt:
3.3.1. Khởi tạo danh sách
Khởi tạo danh sách cho chiều dài danh sách trở về 0.
void CD_Initialize(int &Len)
{
Len = 0;
return;
}
85
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.2. Tạo danh sách mới & nhập danh sách
Tạo danh sách mới có chiều dài tối đa MaxLen, hàm trả về
giá trị thực của danh sách mới được tạo.
int CD_Create_List(T M[], int &Len)
{
if (Len > MaxLen)
Len = MaxLen;
for (int I = 0; i< Len;I++)
M[I] = InputOneElement();
return (Len);
}
T InputOneElement()
{ }
86
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.3. Thêm 1 phần tử vào danh sách
Thêm 1 phần tử có giá trị NewValue vào trong danh sách có chiều dài
Length tại vị trí InsPos
B1: IF (Length = MaxLen)
Thực hiện BKT
B2: Pos = Length+1
B3: IF(Pos = InsPos)
Thực hiện B7
B4: M[Pos] = M[Pos -1]
B5: Pos--
B6: Lặp lại B3
B7:M[InsPos] = NewValue
B8: Length++
BKT: Kết thúc
87
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.3. Thêm 1 phần tử vào danh sách (tt)
int CD_InsertElement(T M[], int &Len, T NewValue, int
InsPos)
{
if (Len == MaxLen)
return (-1);
for (int I = Len; I >InsPos; I++)
M[I] = M[I-1];
M[InsPos] = NewValue;
Len++;
return (Len);
}
88
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.4. Tìm kiếm 1 phần tử trong danh sách
Dùng các thuật toán tìm kiếm tìm phần tử thỏa mãn điều
kiện trong danh sách
• Tìm kiếm tuyến tính
• Tìm nhị phân
89
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.5. Hủy 1 phần tử trong danh sách
• Loại bỏ phần tử có vị trí DelPosition trong danh sách M
có chiều dài Length (có thể có thao tác tìm kiếm xác
định vị trí xóa phần tử)
Thuật toán:
B1: IF(Length =0 OR DelPos > Len) Thực hiện BKT
B2: Pos = DelPos
B3: IF(Pos = Length)
Thực hiện B7
B4: M[Pos] = M[Pos+1]
B5: Pos++
B6: Lặp lại B3
B7: Length--
BKT: Kết thúc
90
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.5. Hủy 1 phần tử trong danh sách (tt)
int CD_Delete_Element(T M[], int &Len, int DelPos)
{
int (Len ==0 || DelPos >=Len)
return (-1);
for (int I =DelPos; i<Len; i++)
M[i] = M[i+1];
Len --;
return (Len);
}
91
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.6. Sửa đổi giá trị cho 1 phần tử trong danh sách
• Giả sử phần tử trong danh sách được thay đổi ở tại vị
trí Position trong danh sách M có chiều dài Length.
• Thao tác sửa đổi là thao tác tìm kiếm phần tử cần có vị
trí (hay giá trị) và gán giá trị mới
• M[Pos] = NewValue;
92
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.7. Sắp xếp thứ tự phần tử trong danh sách
Dùng các thuật toán sắp xếp nội
• Giải thuật sắp xếp nổi bọt (Bubble Sort)
• Giải thuật sắp xếp dựa trên phân hoạch (Quick Sort)
• Giải thuật sắp xếp chọn trực tiếp (Straight Selection
Sort)
• Giải thuật sắp xếp chèn trực tiếp (Straight Insertion
Sort)
• Giải thuật sắp xếp trộn trực tiếp (Straight Merge Sort)
• Giải thuật sắp xếp trộn tự nhiên (Natural Merge Sort)
93
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.8. Tách 1 danh sách thành nhiều danh sách
Có nhiều thao tác tách 1 danh sách thành nhiều danh
sách:
• Phân phối luân phiên theo đường chạy (distribute)
• Phân phối từng phần của danh sách thành các danh
sách con
• Tách các phần tử thỏa mãn điều kiện cho trước thành
các danh sách con.
Giả sử cần tách danh sách M có chiều dài Length thành
các danh sách con SM1, SM2 có chiều dài tương ứng
là Slen1 và SLen2
94
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.8. Tách 1 danh sách thành nhiều danh sách (tt)
B1: IF(SLen1 >= Len)
SLen1 = Len
SLen2 = 0
B2:IF(SLen2 >= Len)
SLen2 = Len
SLen1 = 0
B3: IF(SLen1 + SLen2 Len) SLen2 = Len – SLen1
B4: IF (SLen1 < 0) SLen1 = 0
B5: IF (SLen2 < 0) SLen2 = 0
B6: I =1, SI = 1
B7: IF (I > SLen1)Thực hiện B11
B8: SM[SI] = M[I]
B9: I++, SI++
B10: Lặp lại B7
B11: SI = 1
B12: IF(I > Len) Thực hiện BKT
B13: SM2[SI] = M[I]
B14: I++, SI++
B15: Lặp lại B12
BKT: Kết thúc
95
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.8. Tách 1 danh sách thành nhiều danh sách (tt)
void CS_Split(T M[], int Len, T SM1[], int &SLen1, T SM2[], int &SLen2)
{ int (Slen1 >=Len)
{ SLen1 = Len;
Slen2 = 0;
}
int (Slen2 >=Len)
{ SLen2 = Len;
SLen1 = 0;
}
if (SLen1 < 0) SLen1 = 0;
if (SLen2 < 0) SLen2 = 0;
if (SLen1 + SLen2 != Len) SLen2 = Len - SLen1;
for (int i=0; i<SLen1; i++) SM1[i] = M[i];
for (int j=0; j<SLen1; i++, j++) SM1[j] = M[i];
return;
}
96
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.9. Nhập nhiều danh sách thành 1 danh sách
Các cách nhập danh sách:
• Ghép nối đuôi các danh sách thành danh sách mới có
chiều dài là tổng chiều dài các danh sách.
• Trộn xen kẽ các phần tử trong danh sách con theo 1
quy luật nào đó thành 1 danh sách mới (dùng thuật
toán merge trong merge sort)
Giả sử cần ghép danh sách SM1, SM2 có chiều dài SLen1,
SLen2 thành danh sách M có chiều dài Len =
SLen1+SLen2 theo thứ tự từ SM1 đến hết SM2
97
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.9. Nhập nhiều danh sách thành 1 danh sách(tt)
Thuật toán:
B1: IF (Slen1+SLen2 > MaxLen) // M không đủ khả năng chứa
Thực hiện BKT
B2: I = 1 // Chép từ SM1[] vào M[]
B3: IF (I > SLen1)
Thực hiện B7
B4: M[I] = SM[I]
B5: I++
B6: Lặp lại B3
B7: SI = 1 // Chép từ SM2[] vào M[]
B8: IF (SI > SLen2)
Thực hiện BKT
B9: M[I] = SM[SI]
B10: I++; SI++
B11: Lặp lại B8
BKT: Kết thúc
98
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.9. Nhập nhiều danh sách thành 1 danh sách(tt)
int CD_Concat(T SM1[], int SLen1, T SM2[], int SLen2, T M
[], int &Len)
{
if (SLen1+SLen2 > MaxLen)
return (-1);
for (int I = 0; I < SLen1; I++)
M[I] = SM1[I];
for (int J = 0; J < SLen2; I++, J++)
M[I] = SM1[J];
Len = SLen1+ SLen2;
return (Len);
}
99
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.10. Sao chép 1 danh sách: Sao chép nội dung danh sách thành
1 danh sách khác có cùng chiều dài
Thuật toán
B1: I = 1
B2: IF (I > Length) // Length là chiều dài của dãy
B3: CM[I] = M[I]
B4: I++
B5: Lặp lại B2
BKT: Kết thúc
int CD_Copy(T M[], int Len, T CM[]) // Hàm trả về chiều dài của DS
{ for (int i=0; i< Len; i++)
CM[i] = M[i];
return (Len)
}
100
3. Danh sách đặc
3.3. Các thao tác trên danh sách đặc (tt)
3.3.11. Hủy danh sách
• Nếu danh sách được cấp phát động dùng toán tử
delete để hủy.
• Nếu danh sách được cấp phát tĩnh, việc hủy bỏ chỉ có
tác dụng đưa chiều dài danh sách về 0, việc thu hồi bộ
nhớ sẽ do ngôn ngữ lập trình thực hiện
101
3. Danh sách đặc
3.4. Ưu nhược điểm và ứng dụng
• Do phần tử được lưu trữ kề cập với nhau trong bộ nhớ,
danh sách đặc có các ưu điểm:
• Mật độ sử dụng danh sách là tối ưu tuyệt đối.
• Truy cập, tìm kiếm các phần tử là dễ dàng vì vị trí các phần tử
liền kề với nhau trong bộ nhớ.
• Nhược điểm của danh sách là khi thêm hay hủy 1 phần
tử trong danh sách cần dịch chuyển các phần tử còn lại
qua vị trí khác.
• Được ứng dụng nhiều trong cấu trúc dữ liệu mảng
(mảng 1 chiều, mảng nhiều chiều, mảng cấp phát tĩnh,
mảng cấp phát động).
102
4. Danh sách liên kết (Linked List)
4.1. Định nghĩa
4.2. Danh sách liên kết đơn (Simply Linked List)
4.3. Danh sách liên kết kép (Doubly Linked List)
4.4. Ưu nhược điểm của danh sách liên kết
103
4. Danh sách liên kết
4.1. Định nghĩa
• Danh sách liên kết là tập hợp các phần tử mà giữa
chúng có một sự nối kết với nhau thông qua vùng liên
kết của chúng.
• Tùy cách kết nối ràng buộc giữa những phần tử này và
phần tử khác, danh sách liên kết chia thành các loại
khác nhau:
• Danh sách liên kết đơn
• Danh sách liên kết đôi/kép
• Danh sách đa liên kết
• Danh sách liên kết vòng (vòng đơn, vòng đôi)
• Mỗi loại danh sách có cách biểu diễn theo các cấu trúc
dữ liệu và thao tác trên dữ liệu khác nhau.
104
4.2. Danh sách liên kết đơn (SLL)
4.2.1. Cấu trúc dữ liệu
• Nội dung mỗi phần tử (nút) trong danh sách liên kết gồm 2
vùng Vùng dữ liệu và Vùng liên kết
typedef struct SLLNode
{ T Key;
InfoType Info;
SLLNode *NextNode; // liên kết đến vùng của phần tử kế tiếp
} SLLOneNode;
typedef struct SLLNode
{ T Key;
SLLNode *NextNode;
} SLLOneNode;
typedef SLLOneNode * SLLType;
105
4.2. Danh sách liên kết đơn
4.2.1. Cấu trúc dữ liệu (tt)
• Để quản lý danh sách liên kết có thể dùng nhiều phương
pháp khác nhau, mỗi phương pháp sẽ có cấu trúc dữ liệu
cụ thể.
• Quản lý địa chỉ phần đầu danh sách
SLLType SLList1;
• Quản lý địa chỉ phần đầu và cuối danh sách
typedef struct SLL_PairNode
{ SLLType SLLFirst;
SLLType SLLLase;
} SLLPType;
SLLPType SLLList2;
106
4.2. Danh sách liên kết đơn
4.2.1. Cấu trúc dữ liệu (tt)
• Quản lý địa chỉ phần đầu, cuối và số phần tử của danh sách
typedef struct SLL_PairNNode
{ SLLType SLLFirst;
SLLType SLLLase;
unsigned NumNode;
} SLLPNType;
SLLPNType SLLList3;
107
4.2. Danh sách liên kết đơn
4.2.2. Các thao tác trên danh sách liên kết đơn
a. Khởi tạo danh sách SLL
b. Tạo mới 1 phần tử (nút) trong danh sách SLL
c. Thêm 1 phần tử vào danh sách SLL
• Thêm vào đầu | cuối | giữa danh sách liên kết đơn
d. Duyệt qua các nút trong danh sách
e. Tìm kiếm phần tử trong danh sách
f. Hủy bỏ 1 phần tử trong danh sách
g. Hủy danh sách
h. Tạo mới danh sách/Nhập danh sách
i. Tách 1 danh sách thành nhiều danh sách
j. Nhập nhiều danh sách thành 1 danh sách
k. Sắp xếp thứ tự các phần tử trong danh sách
h. Sao chép 1 danh sách
108
4.2. Danh sách liên kết đơn
4.2.2.a. Khởi tạo danh sách SLL
• Thao tác khởi tạo danh sách liên kết đơn là cho
giá trị con trỏ quản lý địa chỉ đầu của danh sách
về con trỏ NULL.
• Hàm khởi tạo danh sách liên kết đơn:
void SLLInitialize(SLLType &First)
{
First = NULL;
return;
}
109
4.2. Danh sách liên kết đơn
4.2.2. b. Tạo mới 1 phần tử (nút) trong danh sách SLL
Giả sử tạo mới 1 phần tử có thành phần dữ liệu = NewData
Thuật toán
B1: First = new SLLOneNode
B2: IF(First == NULL)
Thực hiện BKT
B3: First->NextNode = NULL;
B4: First ->Key = NewData
BKT: Kết thúc
110
4.2. Danh sách liên kết đơn
4.2.2. b. Tạo mới 1 phần tử (nút) trong danh sách SLL (tt)
Cài đặt
Prototype: SLLType SLLCreateNode(T NewData)
SLLType SLLCreateNode(T NewData)
{
SLLType Pnode = New SLLOneNode;
if (Pnode != NULL)
{
Pnode ->NextNode = NULL;
Pnode ->Key = NewData;
}
return Pnode;
}
111
4.2. Danh sách liên kết đơn
4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm đầu
DS)
Thuật toán
B1: NewNode = SLLCreateNode(NewData)
B2: If (NewNode == NULL)
Thực hiện BKT
B3: NewNode->NextNode = SSList
B4: SLList = NewNode
BKT: Kết thúc
112
4.2. Danh sách liên kết đơn
4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm
đầu DS) (tt)
Cài đặt
SLLType SLLAddFirst (SLLType &SList, T NewData)
{
SLLType NewNode = SLLCreateNode(NewData);
if (NewNode == NULL)
return (NULL);
NewNode->NextNode = SList;
SList = NewNode;
return (SList);
}
113
4.2. Danh sách liên kết đơn
4.2.2.c. Thêm 1 phần tử vào danh sách SLL (tt) (Thêm giữa
DS)
• Thêm phần tử mới vào ngay sau nút có địa chỉ InsNode.
Thuật toán
B1: NewNode = SLLCreateOneNode(NewData)
B2: IF (NewNode == NULL)
Thực hiện BKT
B3: IF(InsNode ->NextNode == NULL)
B3.1: InsNode->NextNode = NewNode
B3.2: Thực hiện BKT
B4: NewNode->NextNode = InsNode->NextNode
B5: InsNode->NextNode = NewNode
BKT: Kết thúc
114
4.2. Danh sách liên kết đơn
4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm giữa DS) (tt)
SLLType SLLAddLast (SLLType &SList, T NewData)
{ SLLType NewNode = SLLCreateNode(NewData);
if (NewNode == NULL)
return (NULL);
if (SList == NULL)
{ SList = NewNode;
return (SList);
}
SLLType CurrNode = SList;
while (CurrNode->NextNode != NULL)
CurrNode = CurrNode-> NextNode;
CurrNode-> NextNode = NewNode;
return (SList);
}
115
4.2. Danh sách liên kết đơn
4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm cuối DS)
B1: NewNode = SLLCreateNode(NewData)
B2: IF(NewNode == NULL)
Thực hiện BKT
B3:IF (SLList == NULL)
B3.1: SLList = NewNode
B3.2: Thực hiện BKT
B4: CurrNode = SLList
B5: IF(CurrNode->NextNode == NULL)
Thực hiện B8
B6: CurrNode = CurrNode -> NextNode
B7: Lặp lại B5
B8: CurrNode->NextNode = NewNode
BKT: Kết thúc
116
4.2. Danh sách liên kết đơn
4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm cuối DS) (tt)
Cài đặt
SLLType SLLAddMid (SLLType &SList, T NewData, SLLType
&InsNode)
{ SLLType NewNode = SLLCreateNode(NewData);
if (NewNode == NULL) return (NULL);
if (InsNode->NextNode == NULL)
{ InsNode->NextNode = NewNode;
return (SList);
}
NewNode-> NextNode = InsNode->NextNode;
InsNode-> NextNode = NewNode;
return (SList);
}
117
4.2. Danh sách liên kết đơn
4.2.2.d. Duyệt qua các nút trong danh sách liên kết đơn
• Là thao tác thường dùng trong các loại danh sách.
• Tùy theo từng trường hợp cụ thể để xử lý trong khi
duyệt DS.
Thuật toán:
B1: CurrNode = SLList
B2: IF (CurrNode == NULL)
Thực hiện BKT
B3: OutputData(CurrNode->Key)
B4: CurrNode = CurrNode->NextNode
B5: Lặp lại B2
BKT: Kết thúc
118
4.2. Danh sách liên kết đơn
4.2.2.d. Duyệt qua các nút trong danh sách liên kết đơn (tt)
Cài đặt:
void SLLTravelling(SLLType SList)
{
SLLType CurrNode = SList;
while (CurrNode != NULL)
{
OutputData(CurrNode->Key);
CurrNode = CurrNode->NextNode;
}
return;
}
// Tùy theo từng trường hợp cụ thể, hàm OutputData được
xử lý khác nhau
119
4.2. Danh sách liên kết đơn
4.2.2.e. Tìm kiếm phần tử trong danh sách
• Giả sử cần tìm kiếm trong danh sách liên kết đơn
phần tử có phần dữ liệu SearchData.
• Dùng thuật toán tìm tuyến tính.
Thuật toán
B1: CurrNode = SLList
B2: IF(CurrNode == NULL OR CurrNode->Key ==
SearchData)
Thực hiện BKT
B3: CurrNode = CurrNode->NextNode
B4: Lặp lại B2
BKT: Kết thúc
120
4.2. Danh sách liên kết đơn
4.2.2.e. Tìm kiếm phần tử trong danh sách (tt)
Cài đặt
SLLType SLLSearching (SLLType &SList, T SearchData)
{
SLLType CurrNode = SList;
while (CurrNode != NULL)
{
if (CurrNode->Key == SearchData)
break;
CurrNode = CurrNode-> NextNode;
}
return (CurrNode);
}
121
4.2. Danh sách liên kết đơn
4.2.2.f. Hủy bỏ 1 phần tử trong danh sách
• Loại bỏ phần tử (nút) có thành phần dữ liệu là DelData trong danh sách liên kết
đơn. Gồm 2 thao tác: tìm phần tử có thành phần dữ liệu là DelData và loại bỏ phần
tử này. (Trong quá trình tìm kiếm cần lưu trữ thành phần trước đó PreDelData)
B1: DelNode = SLList // Tìm kiếm phần tử có Key = DelData
B2: PreDelNode = NULL
B3: IF (DelNode == NULL) Thực hiện BKT
B4: IF (DelNode->Key == DelData) Thực hiện B8
B5: PreDelNode = DelNode
B6: DelNode = DelNode->NextNode
B7: Lặp lại B3
B8: IF (PreDelNode == NULL) // Loại bỏ phần tử đầu tiên trong DS
B8.1: SLList = SLList->NextNode
B8.2: Thực hiện B10
B9: PreDelNode->NextNode = DelNode->NextNode // Liên kết các nút sau DelNode về
PreDelNode
B10: DelNode->NextNode = NULL // Cắt mối liên kết của DelNode với các nút còn lại
B11: delete DelNode // Hủy DelNode
BKT: Kết thúc
122
4.2. Danh sách liên kết đơn
4.2.2.f. Hủy bỏ 1 phần tử trong danh sách (tt)
Cài đặt thuật toán trong C++ (Hàm trả về giá trị 1 nếu hủy thành công)
int SLLDeleteNode(SLLType &SList, T DelData)
{ SLLType DelNode = SList;
SLLType PreDelNode = NULL;
while (DelNode != NULL)
{ if (DelNode->Key = DelData)
break;
PreDelNode = DelNode;
DelNode = DelNode->NextNode;
}
if (DelNode == NULL) return (-1);
if (PreDelNode == NULL)
SList = SList->NextNode;
else PreDelNode->NextNode = DelNode->NextNode;
DelNode->NextNode = NULL;
delete DelNode;
return (1);
}
123
4.2. Danh sách liên kết đơn
4.2.2.g. Hủy danh sách
• Việc hủy danh sách thực chất là thực hiện nhiều lần
hủy 1 nút
Thuật toán:
B1: IF (SLList = NULL)
Thực hiện BKT;
B2: TempNode = SLList
B3: SLList = SLList->NextNode
B4: TempNode->NextNode = NULL;
B5: delete TempNode
B6: Lặp lại B1;
BKT: Kết thúc
124
4.2. Danh sách liên kết đơn
4.2.2.g. Hủy danh sách (tt)
Cài đặt thuật toán:
void SLLDelete (SLLType &SList)
{
SLLType TempNode = SList;
while (SList != NULL)
{
SList = SList ->NextNode;
TempNode ->NextNode = NULL;
delete TempNode;
TempNode = Slist;
}
return;
}
125
4.2. Danh sách liên kết đơn
4.2.2.h. Tạo mới danh sách/Nhập danh sách
• Tạo mới 1 danh sách thực chất là liên tục thêm 1 phần tử
vào danh sách mà danh sách ban đầu là rỗng.
• Có thể dùng lại các hàm SLLAddFirst, SLLAddMid,
SLLAddLast
B1: SLLInitialize (SLList)
B2: I = 1
B3: IF (I > N)
Thực hiện BKT;
B4: NewData = InputNewData();
B5: SLLAddFirst(SLList, NewData)
B6: I++
B7: Lặp lại B3
BKT: Kết thúc
126
4.2. Danh sách liên kết đơn
4.2.2.h. Tạo mới danh sách/Nhập danh sách (tt)
Cài đặt
SLLType SLLCreate(SLLType &SList, int N)
{
SLLInitialize(SList);
T NewData;
for (int I = 0; I<N; I++)
{ NewData = InputNewData();
if (SLLAddFirst(SList, NewData) == NULL)
{ SLLDelete(SList);
break;
}
}
return (SList);
}
127
4.2. Danh sách liên kết đơn
4.2.2.k. Sắp xếp thứ tự các phần tử trong danh sách
Thuật toán sắp xếp trộn tự nhiên:
B1: IF (SLLSplit(SLList, TempList) == NULL) Thực hiện BKT
B2: SLLMerge(SLList, TempList, SLList)
B3: Lặp lại B1
BKT: Kết thúc
void SLLNaturalMergeSort(SLLType &SList)
{ SLLType TempList = NULL, List = NULL;
while (SLLSplit(SList,TempList) != NULL)
{ SLLMerge(SList, TempList, List);
SList = List;
}
return;
}
128
4.2. Danh sách liên kết đơn
4.2.2.h. Sao chép 1 danh sách
• Sao chép 1 danh sách thực chất là tạo mới danh sách
NewList bằng cách duyệt qua các nút của SLList để lấy
thành phần dữ liệu để tạo thành 1 nút mới & bổ sung nút
mới này vào danh sách NewList.
Thuật toán
B1: NewList = NULL
B2: CurrNode = SLList
B3: IF (CurNode = NULL) Thực hiện BKT
B4: SLLAddLast(NewList, CurrNode->Key)
B5: CurrNode = CurrNode->NextNode
B6: Lặp lại B3
BKT: Kết thúc
129
4.2. Danh sách liên kết đơn
4.2.2.h. Sao chép 1 danh sách (tt)
Cài đặt thuật toán:
SLLType SLLCopy(SLLType SList, SLLType &NewList)
{ NewList = NULL;
SLLType CurrNode = SList;
while (CurrNode != NULL)
{ SLLType NewNode=SLLAddLast(NewList,CurrNode->Key);
if (NewNode == NULL)
{ SLLDelete(NewList);
break;
}
}
return (NewList);
}
130
4.3. Danh sách liên kết đôi (DLL)
• Các phần tử của danh sách liên kết đôi có 2 mối liên kết với
các phần tử khác trong danh sách.
• Cấu trúc dữ liệu của danh sách liên kết đôi:
typedef struct DLLNode
{ T Key;
InfoType Info;
DLLNode * NextNode;
DLLNode * PreNode;
} DLLOneNode;
typedef struct DLLNode
{ T Key;
DLLNode * NextNode;
DLLNode * PreNode;
} DLLOneNode;
typedef DLLOneNode * DLLType;
131
4.3. Danh sách liên kết đôi
4.3.1. Quản lý danh sách liên kết liên kết đôi:
• Quản lý địa chỉ phần tử đầu của danh sách
DLLType DLList1
• Quản lý địa chỉ phần tử đầu và phần tử cuối của danh sách
typedef struct DLLPairNode
{ DLLType DLLFirst;
DLLType DLLLast;
} DLLPType;
DLLPType DLList2;
• Quản lý địa chỉ phần tử đầu, phần tử cuối và số phần tử của
danh sách
typedef struct DLLPairNode
{ DLLType DLLFirst;
DLLType DLLLast;
unsigned NumNode;
} DLLPNType;
DLLPNType DLList3;
132
4.3. Danh sách liên kết đôi
4.3.2. Thao tác trên danh sách liên kết đôi
a. Khởi tạo danh sách liên kết đôi
b. Tạo mới 1 phần tử
c. Thêm 1 phần tử vào danh sách
d. Duyệt qua các nút trong 1 danh sách
e. Tìm kiếm 1 phần tử trong danh sách
f. Loại bỏ 1 phần tử trong danh sách
g. Hủy toàn bộ danh sách
h. Tạo 1 danh sách mới/Nhập danh sách
i. Tách 1 danh sách thành nhiều danh sách
j. Nhập nhiều danh sách thành 1 danh sách
k. Sắp xếp thứ tự thành phần dữ liệu trong danh sách
l. Sao chép 1 danh sách thành 1 danh sách mới
133
4.3. Danh sách liên kết đôi
4.3.2.a. Khởi tạo danh sách liên kết đôi
Cho giá trị các con trỏ quản lý địa chỉ 2 nút đầu và cuối danh
sách liên kết đôi về NULL
DLLPType DLLInitialize(DLLPType &DList)
{
DList.DLLFirst = NULL;
DList.DLLast = NULL;
return (DList);
}
134
4.3. Danh sách liên kết đôi
4.3.2.b. Tạo mới 1 phần tử
Tạo nút mới có thành phần dữ liệu là NewData
Thuật toán
B1: Dnode = New DLLOneNode
B2: IF (Dnode == NULL)
Thực hiện BKT
B3: DNode ->NextNode = NULL
B4: DNode ->Key = NewData
B5: DNode ->PreNode = NULL
BKT: Kết thúc
DLLType DLLCreateNode(T NewData)
{ DLLType Pnode = new DLLOneNode;
if (Pnode != NULL)
{ Pnode ->NextNode = NULL;
Pnode ->Key = NewData
Pnode ->PreNode = NULL;
}
return (Pnode);
}
135
4.3. Danh sách liên kết đôi
4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm đầu)
B1: NewNode = DLLCreateNode(NewData)
B2: IF (NewNode == NULL)
Thực hiện BKT
B3: IF(DLLList.DLLFirst == NULL)
B3.1: DLLList.DLLFirst = NewNode
B3.2: DLLList.DLLLast = NewNode
B3.3: Thực hiện BKT
B4: NewNode ->NextNode = DLLList.DLLFirst
B5: DLLList.DLLFirst ->PreNode = NewNode
// chuyển vai trò đứng đầu của NewNode cho DLLFirst
B6: DLLList.DLLFirst = NewNode
BKT: Kết thúc
136
4.3. Danh sách liên kết đôi
4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm đầu)
DLLType DLLAddFirst(DLLPType &DList, T NewData)
{
DLLType NewNode = DLLCreateNode(NewData);
if (NewNode == NULL)
return (NULL);
if (DList.DLLFirst == NULL)
DList.DLLFirst = DList.DLLLast = NewNode;
else
{
NewNode ->NextNode = DList.DLLFirst;
DList.DLLFirst ->PreNode = NewNode;
DList.DLLFirst = NewNode;
}
return (NewNode);
}
137
4.3. Danh sách liên kết đôi
4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm cuối)
B1: NewNode = DLLCreateNode(NewData)
B2: IF (NewNode == NULL)
Thực hiện BKT
B3: IF(DLLList.DLLFirst == NULL)
B3.1: DLLList.DLLFirst = NewNode
B3.2: DLLList.DLLLast = NewNode
B3.3: Thực hiện BKT
B4: DLLList.DLLLast ->NextNode = NewNode
B5: NewNode ->PreNode = DLLList.DLLLast
// chuyển vai trò đứng đầu của NewNode cho DLLFirst
B6: DLLList.DLLLast = NewNode
BKT: Kết thúc
138
4.3. Danh sách liên kết đôi
4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm cuối)
DLLType DLLAddLast(DLLPType &DList, T NewData)
{
DLLType NewNode = DLLCreateNode(NewData);
if (NewNode == NULL)
return (NULL);
if (DList.DLLLast == NULL)
DList.DLLFirst = DList.DLLLast = NewNode;
else
{
DList.DLLLast ->NextNode = NewNode;
NewNode ->PreNode = DList.DLLLast;
DList.DLLLast = NewNode;
}
return (NewNode);
}
139
4.3. Danh sách liên kết đôi
4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm giữa)
B1: IF (InsNode ->NextNode == NULL)
B1.1: DLLAddLast(DLLList, NewData)
B1.2: Thực hiện BKT
B2: NewNode = DLLCreateNode(NewData)
B3: IF (NewNode == NULL)
Thực hiện BKT
B4: NewNode ->NextNode = InsNode ->NextNode
B5: InsNode ->NextNode ->PreNode = NewNode
B6: InsNode ->NextNode = NewNode
B7: NewNode ->PreNode = InsNode
BKT: Kết thúc
140
4.3. Danh sách liên kết đôi
4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm giữa)
DLLType DLLAddMid(DLLPType &DList, T NewData, DLLType &InsNode)
{ DLLType NewNode = DLLCreateNode(NewData);
if (NewNode == NULL)
return (NULL);
if (InsNode ->NextNode == NULL)
{ InsNode ->NextNode = NewNode;
NewNode ->PreNode = InsNode;
DList.DLLLast = NewNode;
}
else
{ NewNode ->NextNode = InsNode ->NextNode;
InsNode ->NextNode ->PreNode = NewNode;
InsNode ->NextNode = NewNode;
NewNode ->PreNode = InsNode;
}
return (NewNode);
}
141
4.3. Danh sách liên kết đôi
4.3.2.d. Duyệt qua các nút trong 1 danh sách
Thuật toán
B1: CurrNode = DLLList.First
B2: IF (CurrNode == NULL)
Thực hiện BKT
B3: OutputData(CurrNode->Key)
B4: CurrNode = CurrNode ->NextNode
B5: Lặp lại B2
BKT: Kết thúc
Cài đặt thuật toán
void DLLTravelling (DLLPType DList)
{ DLLType CurrNode = DList.DLLFirst;
while (CurrNode != NULL)
{ OutputData(CurrNode->Key);
CurrNode = CurrNode ->NextNode ;
}
return;
}
142
4.3. Danh sách liên kết đôi
4.3.2.e. Tìm kiếm 1 phần tử trong danh sách
Thuật toán
B1: CurrNode = DLLList.First
B2: IF (CurrNode == NULL OR CurrNode->Key = SearchData)
Thực hiện BKT
B3: CurrNode = CurrNode ->NextNode
B4: Lặp lại B2
BKT: Kết thúc
Cài đặt thuật toán
DLLType DLLSearching(DLLPType Dlist, T SearchData)
{ DLLType CurrNode = DList.DLLFirst;
while (CurrNode != NULL)
{ if (CurrNode->Key == SearchData)
break;
CurrNode = CurrNode ->NextNode
}
return (CurrNode);
}
143
4.3. Danh sách liên kết đôi
4.3.2.f. Loại bỏ 1 phần tử trong danh sách
Thuật toán
B1: DelNode = DLLSearching(DLLList. DelData) // Tìm kiếm nút DelData
B2: IF(DelNode == NULL)
Thực hiện BKT
B3: IF(DelNode->PreNode=NULL AND DelNode->NextNode=NULL)
B3.1: DLLList.DLLFirst = DLLList.DLLLast = NULL
B3.2: Thực hiện B8
B4: IF (DelNode ->PreNode = NULL) // Loại nút đầu tiên trong DS
B4.1: DLLList.DLLFirst = DLLList.DLLFirst ->NextNode
B4.2: DLLList.DLLFirst ->PreNode = NULL
B4.3: Thực hiện B8
B5: IF (DelNode ->NextNode = NULL) // Loại nút cuối trong DS
B4.1: DLLList.DLLLast = DLLList.DLLLast ->PreNode
B4.2: DLLList.DLLLast ->NextNode = NULL
B4.3: Thực hiện B8
// Liên kết giữa nút trước và sau nút bị xóa
B6: DelNode ->PreNode ->NextNode = DelNode ->NextNode
B7: DelNode ->NextNode ->PreNode = DelNode ->PreNode
// Bỏ mối liên kết giữa DelNode giữa 2 nút trước & sau
B8: DelNode ->NextNode = DelNode ->PreNode = NULL
B9: delete DelNode
BKT: Kết thúc
144
4.3. Danh sách liên kết đôi
4.3.2.f. Loại bỏ 1 phần tử trong danh sách
Cài đặt thuật toán
Int DLLDeleteNode (DLLPType &DList, T DelData)
{ DLLType DelNode = DLLSearching(DList, DelData)
if (DelNode == NULL)
return (-1);
if (DelNode ->NextNode == NULL && DelNode ->PreNode == NULL)
DList.DLLFirst = DList.DLLLast = NULL;
else
if (DelNode ->PreNode ==NULL)
{ DList.DLLFirst = Dist.DLLFirst ->NextNode ;
Dist.DLLFirst ->PreNode = NULL;
}
else
if (DelNode ->NextNode ==NULL)
{ DList.DLLLast = Dist.DLLLast ->PreNode ;
Dist.DLLLast ->NextNode = NULL;
}
else
{ DelNode ->PreNode ->NextNode = DelNode ->NextNode;
DelNode ->NextNode ->PreNode = DelNode ->PreNode ;
}
}
145
4.3. Danh sách liên kết đôi
4.3.2.g. Hủy toàn bộ danh sách
Thực hiện nhiều lần thao tác hủy một nút
Thuật toán
B1: IF (DLLList.DLLFirst == NULL)
Thực hiện BKT
B2: TempNode = DLLList.DLLFirst
B3: DLLList.DLLFirst = DLLList.DLLFirst ->NextNode
B4: IF (DLLList.DLLFirst == NULL)
B4.1: DLLList.DLLLast = NULL
B4.2: Thực hiện B7
B5: DLLList.DLLFirst ->PreNode = NULL
B6: TempNode ->NextNode = NULL
B7: delete TempNode
B8: Lặp lại B1
BKT: Kết thúc
146
4.3. Danh sách liên kết đôi
4.3.2.g. Hủy toàn bộ danh sách (tt)
Cài đặt thuật toán
void DLLDelete (DLLPType &DList)
{
DLLType TempNode = DList.DLLFirst;
while (TempNode != NULL)
{
DList.DLLFirst = DList.DLLFirst ->NextNode;
TempNode ->NextNode = NULL;
if (DList.DLLFirst != NULL)
DList.DLLFirst ->PreNode = NULL;
delete TempNode;
TempNode = DList.DLLFirst;
}
return;
}
147
4.3. Danh sách liên kết đôi
4.3.2.h. Tạo 1 danh sách mới/Nhập danh sách
Thuật toán
B1: DLLInitialize(DLLList)
B2: I = 1
B3: IF (I >N)
Thực hiện BKT
B4: NewData = InputNewData();
B5: DLLAddLast(DLLList, NewData)
B6: I++
B7: Lặp lại B3
BKT: Kết thúc
148
4.3. Danh sách liên kết đôi
4.3.2.h. Tạo 1 danh sách mới/Nhập danh sách
Cài đặt thuật toán
DLLPType DLLCreate (DLLPType &DList, int N)
{
DLLInitialize(DList);
T NewData;
for (int i=0; i <N; i++)
{
NewData = InputNewData();
if (DLLAddLast(DList, NewData) == NULL)
{ DLLDelete(DList);
break;
}
}
return (DList);
}
149
4.3. Danh sách liên kết đôi
4.3.2.k. Sắp xếp thứ tự thành phần dữ liệu trong danh sách
B1: Inode = DLLList.DLLFirst
B2: IF(Inode == NULL)
Thực hiện BKT
B3: IF (Inode == DLLList.DLLLast)
Thực hiện BKT
B4: Jnode = DLLList.DLLLast
B5: IF (Jnode = Inode)
Thực hiện B7
B6: ELSE
B6.1: If (Jnode->Key PreNode ->Key)
Swap (Jnode ->Key, Jnode ->PreNode ->Key)
B6.2: Jnode = Jnode ->NextNode
B6.3: Lặp lại B5
B7: Inode = Inode ->NextNode
B8: Lặp lại B3
BKT: Kết thúc
150
4.3. Danh sách liên kết đôi
4.3.2.k. Sắp xếp thứ tự thành phần dữ liệu trong danh sách (tt)
Cài đặt thuật toán
void DLLBubbleSort (DLLPType &DList)
{ DLLType Inode = DList.DLLFirst;
if (Inode == NULL)
return;
while (Inode != DList.DLLLast)
{ DLLType Jnode = DList.DLLLast;
while (Jnode != Inode)
{ if (Jnode->Key PreNode ->Key)
Swap(Jnode->Key,Jnode->PreNode->Key)
Jnode = Jnode ->PreNode ;
}
Inode = Inode ->NextNode ;
}
return;
}
151
4.3. Danh sách liên kết đôi
4.3.2.l. Sao chép 1 danh sách thành 1 danh sách mới
Thuật toán
B1: DLLInitialize(NewList)
B2: CurrNode = DLLList.DLLFirst
B3: IF (CurrNode == NULL)
Thực hiện BKT
B4: DLLAddLast(NewList, CurrNode->Key)
B5: CurrNode = CurrNode ->NextNode
B6: Lặp lại B3
BKT: Kết thúc
152
4.3. Danh sách liên kết đôi
4.3.2.l. Sao chép 1 danh sách thành 1 danh sách mới
Cài đặt thuật toán
DLLPType DLLCopy(DLLPType &DList, DLLPType &NewList)
{
DLLInitialize(NewList);
DLLType CurrNode = DList.DLLFirst;
while (CurrNode != NULL)
{
if (DLLAddLast(NewList, CurrNode->Key) == NULL)
{ DLLDelete(NewList);
break;
}
CurrNode = CurrNode ->NextNode ;
}
return (NewList);
}
153
4. Danh sách liên kết
4.4. Ưu nhược điểm của danh sách liên kết
• Nhược điểm
• Mật độ sử dụng bộ nhớ của danh sách liên kết không tối ưu
tuyệt đối (<100%)
• Việc truy xuất và tìm kiếm các phần tử trong danh sách liên kết
mất nhiều thời gian vì phải duyệt tuần tự qua các phần tử trong
danh sách.
• Bộ nhớ cần nhiều vì phải lưu thêm phần tử liên kết, nếu vùng
dữ liệu là lớn thì tỷ lệ mức sử dụng bộ nhớ là cao.
• Ưu điểm
• Tận dụng được không gian bộ nhớ nhỏ để lưu trữ từng nút.
• Việc thêm, xóa phần tử trong danh sách liên kết là dễ dàng, chỉ
cần thay đổi mối liên kết của các phần tử với nhau.
154
5. Danh sách hạn chế
5.1. Hàng đợi (Queue)
5.2. Ngăn xếp (Stack)
5.3. Ứng dụng của danh sách hạn chế
155
5. Danh sách hạn chế
5.1. Hàng đợi (Queue)
• Hàng đợi là một danh sách mà trong đó thao tác thêm 1
phần tử vào trong danh sách được thực hiện 1 đầu này
và lấy 1 phần tử trong danh sách lại thực hiện bởi đầu kia.
• Các phần tử đưa vào trong hàng đợi trước sẽ được lấy ra
trước, phần tử đưa vào trong hàng đợi sau sẽ được lấy ra
sau.
• Hàng đợi còn được gọi là danh sách FIFO List và cấu trúc
dữ liệu này còn được gọi cấu trúc FIFO (First In First Out)
• Có nhiều cách biểu diễn hàng đợi: dùng danh sách đặc
hoặc dùng danh sách liên kết
• Quản lý vị trí 2 đầu của hàng đợi thông qua 2 biến:
• Biến trước (Font)
• Biến sau (Rear)
156
5.1. Hàng đợi
5.1.1. Cấu trúc dữ liệu biểu diễn cho hàng đợi
• Biểu diễn và tổ chức hàng đợi bằng danh sách đặc và
danh sách liên kết đơn được quản lý bởi 2 phần tử đầu
và cuối
• Cấu trúc dữ liệu biểu diễn hàng đợi bằng danh sách
đặc
typedef struct QC
{ int Len;
int Front, Rear;
T * List;
} CQUEUE;
CQUEUE CQList;
157
5.1. Hàng đợi
5.1.1. Cấu trúc dữ liệu biểu diễn cho hàng đợi (tt)
Cấu trúc dữ liệu biểu diễn hàng đợi bằng danh sách liên
kết
typedef struct QElement
{ T Key;
QElement *Next;
} QOneElement;
typedef QElement *QType;
typedef struct QPElement
{ QType Font;
QType Rear;
} SQUEUE;
SQUEUE SQList;
158
5.1. Hàng đợi
5.1.2. Các thao tác trên hàng đợi tổ chức bằng danh
sách đặc
a. Khởi tạo hàng đợi (Initialize)
b. Thêm 1 phần tử vào hàng đợi (Add)
c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý (Get)
d. Hủy hàng đợi
159
5.1. Hàng đợi
5.1.2.a. Khởi tạo hàng đợi (tổ chức bằng danh sách
đặc)
B1: CQList.Len = Length
B2: CQList.List = new T[Length]
B3: IF(CQList.List == NULL)
Thực hiện BKT
B4: CQList.Front = CQList.Rear = 0
BKT: Kết thúc
160
5.1. Hàng đợi
5.1.2.a. Khởi tạo hàng đợi (tổ chức bằng danh sách
đặc)
Cài đặt thuật toán
T * CQInitialize (CQUEUE & QList, int Length)
{
QList.Len = Length;
QList.List = new T[Length];
if (QList.List == NULL)
return (NULL);
QList.Front = QList.Rear =-1;
return (QList.List);
}
161
5.1. Hàng đợi
5.1.2.b. Thêm 1 phần tử vào hàng đợi (tổ chức bằng danh sách đặc)
Thuật toán
// nếu hàng đợi đã bị đầy
B1: IF(CQList.Front ==1 AND CQList.Rear == CQList.Len)
Thực hiện BKT
B2: IF(CQList.Rear+1 == CQList.Front)
Thực hiện BKT
B3: IF(CQList.Front = 0) // nếu hàng đợi rỗng
CQList.Front = 1
B4: IF(CQList.Rear = CQList.Len)
CQList.Rear = 1
B5: ELSE
CQList.Rear ++
B6: CQList.List[CQList.Rear] = NewData
BKT: Kết thúc
162
5.1. Hàng đợi
5.1.2.b. Thêm 1 phần tử vào hàng đợi (tổ chức bằng danh sách đặc)
Cài đặt thuật toán
int CQAdd(CQUEUE & QList, T NewData)
{ if (QList.Front == 0 && QList.Rear == QList.Len -1)
return (-1);
if (QList.Rear +1 == QList.Front)
return (-1);
if (QList.Front == -1)
QList.Front =0
if (QList.Rear == QList.Len)
QList.Rear = 0;
else
QList.Rear += 1;
QList.List[QList.Rear] = NewData
return (QList.Rear );
}
163
5.1. Hàng đợi
5.1.2.c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý
(tổ chức bằng danh sách đặc)
B1: IF (CQList.Front = 0)
Thực hiện BKT
B2: Data = CQList.List[CQList.Front]
B3: IF(CQList.Rear == CQList.Front)
B3.1: CQList.Rear = CQList.Front = 0
B3.2: Thực hiện BKT
B4: IF (CQList.Front = CQList.Len)
CQList.Front = 1
B5: ELSE
CQList.Front++
BKT: Kết thúc
164
5.1. Hàng đợi
5.1.2.c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý (tổ chức
bằng danh sách đặc)
Cài đặt thuật toán
int CQGet(CQUEUE & QList, T &Data)
{ if (QList.Front == -1)
return (-1);
Data = QList.List[QList.Front];
if (QList.Front == QList.Rear)
{ QList.Front = QList.Rear = -1;
return (1);
}
if (QList.Front == QList.Len -1)
QList.Front = 0;
else
QList.Front += 1;
return (1);
}
165
5.1. Hàng đợi
5.1.2.d. Hủy hàng đợi (tổ chức bằng danh sách đặc)
Hủy bộ nhớ cấp phát cho hàng đợi
void CQDelete(CQUEUE & QList)
{
delete QList.List;
return;
}
166
5.1. Hàng đợi
5.1.3. Các thao tác trên hàng đợi tổ chức bằng danh
sách liên kết đơn
a. Khởi tạo hàng đợi (Initialize)
b. Thêm 1 phần tử vào hàng đợi (Add)
c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý (Get)
d. Hủy hàng đợi
167
5.1. Hàng đợi
5.1.3.a. Khởi tạo hàng đợi (dùng danh sách liên kết
đơn)
Tương tự với danh sách liên kết đơn, hàm khởi tạo thực
hiện gán con trỏ Front và Rear về NULL
SQUEUE SQInitialize (SQUEUE &QList)
{
QList.Front = QList.Rear = NULL;
return (QList);
}
168
5.1. Hàng đợi
5.1.3.b. Thêm 1 phần tử vào hàng đợi (dùng danh sách
liên kết đơn)
Thêm phần tử vào sau phần tử Rear (Thêm vào cuối danh
sách liên kết)
Giả sử dữ liệu đưa vào hàng đợi là NewData
B1: NewElement = SLLCreateNode(NewData)
B2: IF (NewElement == NULL)
Thực hiện BKT
B3: IF (SQList.Front == NULL) // hàng đợi dang rỗng
B3.1: SQList.Front = SQList.Rear = NewElement
B3.2: Thực hiện BKT
B4: SQList.Rear->Next = NewElement
B5: SQList.Rear = NewElement
BKT: Kết thúc
169
5.1. Hàng đợi
5.1.3.b. Thêm 1 phần tử vào hàng đợi (dùng danh sách liên kết
đơn)
Cài đặt thuật toán:
QType SQAdd(SQUEUE &Qlist, T NewData)
{ QType NewElement = SLLCreateNode(NewData)
if (NewElement == NULL)
return (NULL);
if (QList.Front == NULL)
QList.Front = QList.Rear = NewElement;
else
{ QList.Rear->Next = NewElement;
QList.Rear = NewElement;
}
return(NewElement);
}
170
5.1. Hàng đợi
5.1.3.c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý
(dùng danh sách liên kết đơn)
Lấy nội dung thành phần dữ liệu của phần tử ở địa chỉ
Front ra biến Data và tiến hành hủy phần tử này
B1: IF (SQList.Front == NULL) // nếu hàng đợi bị rỗng
Thực hiện BKT
B2: TempElement = SQList.Front;
B3: SQList.Front = SQList.Front ->Next
B4: TempElement ->Next = NULL
B5: Data = TempElement ->Key
B6: IF (SQList.Front == NULL)
SQList.Rear == NULL
B7: delete TempElement
BKT: Kết thúc
171
5.1. Hàng đợi
5.1.3.c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý (dùng danh
sách liên kết đơn) Cài đặt thuật toán
int SQGet (SQUEUE &QList, T &Data)
{ if (QList.Front = NULL)
return (-1);
QType TempElement = QList.Front;
QList.Front = QList.Front ->Next;
TempElement ->Next = NULL;
Data = TempElement ->Next ;
if (QList.Front = NULL)
QList.Rear = NULL;
delete TempElement;
return(1);
}
172
5.1. Hàng đợi
5.1.3.d. Hủy hàng đợi (dùng danh sách liên kết đơn)
void SQQueue (SQUEUE &QList)
{
QList.Rear = NULL;
while (QList.Front != NULL)
{
QType TempElement = QList.Front;
TempElement ->Next = NULL;
delete TempElement;
}
return;
}
173
5.2. Ngăn xếp (Stack)
Ngăn xếp là một danh sách mà trong đó thao tác trên 1
phần tử vào trong ngăn xếp và thao tác lấy ra một phần
tử được thực hiện 1 đầu.
Các phần tử được đưa vào ngăn xếp sau cùng sẽ được
lấy ra trước tiên, phần tử được đưa vào trước tiên sẽ
được lấy ra sau cùng.
Ngăn xếp được gọi là danh sách vào sau ra trước LIFO,
cấu trúc dữ liệu này được gọi là cấu trúc LIFO.
5.2.1. Cấu trúc dữ liệu
5.2.2. Các thao tác trên ngăn xếp tổ chức bằng danh sách
đặc
5.2.2. Các thao tác trên ngăn xếp tổ chức bằng danh sách
liên kết
174
5.2. Ngăn xếp
5.2.1. Cấu trúc dữ liệu
Biểu diễn và tổ chức bằng danh sách đặc
typedef struct SC
{ int Size;
int SP;
T * List;
} CSTACK;
CSTACK CSList;
Biểu diễn và tổ chức bằng danh sách liên kết
typedef struct SElement
{ T Key;
SElement *Next;
} SOneElement;
typedef struct SOneElement *SSTACK;
SSTACK SSP;
175
5.2. Ngăn xếp
5.2.2. Các thao tác trên ngăn xếp tổ chức bằng danh sách
đặc
5.2.2.a. Khởi tạo ngăn xếp (Initialize)
5.2.2.b. Thêm 1 phần tử vào ngăn xếp (Push)
5.2.2.c. Lấy nội dung 1 phần tử trong ngăn xếp ra xử lý
(Pop)
5.2.2.d. Hủy ngăn xếp
176
5.2. Ngăn xếp
5.2.2.a. Khởi tạo ngăn xếp (dùng danh sách đặc)
B1: CSList.Size = MaxSize
B2: CSList.List = new T[MaxSize]
B3: IF (CSList.List == NULL)
Thực hiện BKT
B4: CSList.SP = CSList.Size +1
BKT: Kết thúc
T * CSInitialize(CSTACK &SList, int MaxSize)
{ SList.Size = MaxSize;
SList.List = new T[MaxSize];
if (SList.List == NULL)
return (NULL);
SList.SP = SList.Size ;
return (SList.List);
}
177
5.2. Ngăn xếp
5.2.2.b. Thêm 1 phần tử vào ngăn xếp (dùng danh sách
đặc)
B1: IF (CSList.SP == 1)
Thực hiện BKT
B2: CSList.SP --
B3: CSList.List[CSList.SP] = NewData
BKT: Kết thúc
int CSPush(CSTACK &SList, T NewData)
{ if (SList.SP == 0)
return (-1);
SList.SP -= 1;
SList.List[SList.SP] = NewData;
return (SList.SP);
}
178
5.2. Ngăn xếp
5.2.2.c. Lấy nội dung 1 phần tử trong ngăn xếp ra xử lý (dùng danh sách
đặc)
B1: IF (CSList.SP == CSList.Size +!)
Thực hiện BKT
B2: Data = CSList.List[CSList.SP]
B3: CSList.SP++
BKT: Kết thúc
int CSPop(CSTACK &SList, T &Data)
{ if (SList.SP == SList.Size)
return (-1);
Data = SList.List[SList.SP];
SList.SP += 1;
return (1);
}
179
5.2. Ngăn xếp
5.2.2.d. Hủy ngăn xếp (dùng danh sách đặc)
int CSDelete(CSTACK &SList)
{
delete SList.SList;
return;
}
180
5.2. Ngăn xếp
5.2.2. Các thao tác trên ngăn xếp tổ chức bằng danh sách
liên kết
5.2.3.a. Khởi tạo ngăn xếp (Initialize)
5.2.3.b. Thêm 1 phần tử vào ngăn xếp (Push)
5.2.3.c. Lấy nội dung 1 phần tử trong ngăn xếp ra xử lý
(Pop)
5.2.3.d. Hủy ngăn xếp
181
5.2. Ngăn xếp
5.2.3.a. Khởi tạo ngăn xếp (dùng danh sách liên kết)
SSTACK SSInitialize (SSTACK &SList)
{ SList = NULL;
return (SList);
}
182
5.2. Ngăn xếp
5.2.3.b. Thêm 1 phần tử vào ngăn xếp (dùng danh sách
liên kết)
B1: NewElement = SLLCreateNode(NewData)
B2: if (NewElement == NULL)
Thực hiện BKT
B3: if (SSP == NULL)
B3.1: SSP = NewElement
B3.2: Thực hiện BKT
B4: NewElement ->Next = SSP
B5: SSP = NewElement
BKT: Kết thúc
183
5.2. Ngăn xếp
5.2.3.b. Thêm 1 phần tử vào ngăn xếp (dùng danh sách
liên kết)
SSTACK SSPush (SSTACK &SList, T NewData)
{ SSTACK NewElement = SLLCreateNode(NewData);
if (NewElement == NULL)
return (NULL);
NewElement ->Next = SList;
SList = NewElement;
return (NewElement);
}
184
5.2. Ngăn xếp
5.2.3.c. Lấy nội dung 1 phần tử trong ngăn xếp ra xử lý
(dùng danh sách liên kết)
B1: if (SSP == NULL)
Thực hiện BKT
B2: TempElement = SSP
B3: SSP = SSP ->Next
B4: TempElement ->Next = NULL
B5: Data = TempElement->Key
B6: delete TempElement-
BKT: Kết thúc
185
5.2. Ngăn xếp
5.2.3.c. Lấy nội dung 1 phần tử trong ngăn xếp ra xử lý
(dùng danh sách liên kết)
int SSPop (SSTACK &SList, T &Data)
{
if (SList == NULL)
return (-1);
SSTACK TempElement = SList;
SList = SList ->Next;
TempElement ->Next = NULL;
Data = TempElement->Key;
delete TempElement;
return (1);
}
186
5.2. Ngăn xếp
5.2.3.d. Hủy ngăn xếp (dùng danh sách liên kết)
void SSDelete (SSTACK &SList)
{
while (SList != NULL)
{ SSTACK TempElement = SList;
SList = SList ->Next;
TempElement ->Next = NULL;
delete TempElement;
}
}
187
5.2. Ngăn xếp
5.3. Ứng dụng của danh sách hạn chế
• Hàng đợi dùng trong nhiều trường hợp lưu trữ dữ liệu
cần xử lý tuần tự.
• Ngăn xếp dùng trong việc xử lý dữ liệu truy hồi, đặc
biệt trong việc xử lý đệ quy của các thuật giải.
188
BÀI TẬP CHƯƠNG 4
• Bài tập chương 4, giáo trình Cấu trúc dữ liệu và giải
thuật (Trang 156 -157)
Các file đính kèm theo tài liệu này:
- cau_truc_du_lieu_c4_9759.pdf