Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 3: Mảng và danh sách - Đỗ Tuấn Anh

ode* InsertNode(Node* head, int index, int x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode = head;
while (currNode && index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode == NULL) return NULL;
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = x;
if (index == 0) {
newNode->next = head;
head = newNode;
}
else {
newNode->next = currNode->next;
currNode->next = newNode;
}
return newNode;
}
Tìm nút thứ
index. Nếu không 
tìm thấy, trả lại
NULL.
Thêm một nút mới
Node* InsertNode(Node* head, int index, int x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode = head;
while (currNode && index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode == NULL) return NULL;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = x;
if (index == 0) {
newNode->next = head;
head = newNode;
}
else {
newNode->next = currNode->next;
currNode->next = newNode;
}
return newNode;
}
Tạo nút mới
Thêm một nút mới
Node* InsertNode(Node* head, int index, int x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode = head;
while (currNode && index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode == NULL) return NULL;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = x;
if (index == 0) {
newNode->next = head;
head = newNode;
}
else {
newNode->next = currNode->next;
currNode->next = newNode;
}
return newNode;
}
Thêm vào đầu danh sách
head
newNode
Thêm một nút mới
Node* InsertNode(Node* head, int index, int x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode = head;
while (currNode && index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode == NULL) return NULL;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = x;
if (index == 0) {
newNode->next = head;
head = newNode;
}
else {
newNode->next = currNode->next;
currNode->next = newNode;
}
return newNode;
}
Thêm vào sau currNode
newNode
currNode
Tìm nút
zint FindNode(int x)
{Tìm nút có giá trị x trong danh sách.
{Nếu tìm được trả lại vị trí của nút. Nếu không,
trả lại 0.
int FindNode(Node* head, int x) {
Node* currNode = head;
int currIndex = 1;
while (currNode && currNode->data != x) {
currNode = currNode->next;
currIndex++;
}
if (currNode) return currIndex;
return 0;
}
Xóa nút
z int DeleteNode(int x)
{Xóa nút có giá trị bằng x trong danh sách.
{Nếu tìm thấy nút, trả lại vị trí của nó. Nếu không, trả
lại 0.
zGiải thuật
{Tìm nút có giá trị x (tương tự như FindNode)
{Thiết lập nút trước của nút cần xóa nối đến nút sau 
của nút cần xóa
{Giải phóng bộ nhớ cấp phát cho nút cần xóa
zGiống như InsertNode, có 2 trường 
hợp
{Nút cần xóa là nút đầu tiên của danh sách
{Nút cần xóa nằm ở giữa hoặc cuối danh sách
Xóa nút đầu danh sách
head = currNode->next;
free(currNode);
(nút xóa)Head
currNode
20 45 75 85 ...
Xóa nút giữa/cuối danh sách
prevNode->next = currNode-
>next;
free(currNode);
(nút xóa)Head
currNode
20 45 75 85
prevNode
...
Xóa một nút
int DeleteNode(Node*& head, int x) {
Node* prevNode = NULL;
Node* currNode = head;
int currIndex = 1;
while (currNode && currNode->data != x) {
prevNode = currNode;
currNode = currNode->next;
currIndex++;
}
if (currNode) {
if (prevNode) {
prevNode->next = currNode->next;
free (currNode);
}
else {
head = currNode->next;
free (currNode);
}
return currIndex;
}
return 0;
}
Tìm nút có giá trị bằng x
Xóa một nút
int DeleteNode(Node* head, int x) {
Node* prevNode = NULL;
Node* currNode = head;
int currIndex = 1;
while (currNode && currNode->data != x) {
prevNode = currNode;
currNode = currNode->next;
currIndex++;
}
if (currNode) {
if (prevNode) {
prevNode->next = currNode->next;
free (currNode);
}
else {
head = currNode->next;
free (currNode);
}
return currIndex;
}
return 0;
}
currNodeprevNode
Xóa một nút
int DeleteNode(Node* head, int x) {
Node* prevNode = NULL;
Node* currNode = head;
int currIndex = 1;
while (currNode && currNode->data != x) {
prevNode = currNode;
currNode = currNode->next;
currIndex++;
}
if (currNode) {
if (prevNode) {
prevNode->next = currNode->next;
free (currNode);
}
else {
head = currNode->next;
free (currNode);
}
return currIndex;
}
return 0;
}
currNodehead
Hủy danh sách
zvoid DestroyList(Node* head)
{Sử dụng hàm hủy để giải phóng bộ nhớ được cấp 
phát cho danh sách.
{Duyệt toàn bộ danh sách và xóa lần lượt từng nút.
void DestroyList(Node* head)
{
Node* currNode = head, *nextNode = NULL;
while (currNode != NULL)
{
nextNode = currNode->next;
// giải phóng nút vừa duyệt
free (currNode);
currNode = nextNode;
}
}
In toàn bộ danh sách
zvoid DisplayList(Node* head)
{In dữ liệu của tất cả các phần tử
void DisplayList(Node* head)
{
int num = 0;
Node* currNode = head;
while (currNode != NULL){
printf(“%d \n”, currNode->data);
currNode = currNode->next;
num++;
}
}
Sử dụng danh sách
int main(void)
{
Node* head = NULL;
InsertNode(head, 0, 7); // thêm vào đầu danh sách
InsertNode(head, 1, 5); // thêm vào sau phần tử đầu
InsertNode(head, -1, 5); // không thêm được
InsertNode(head, 0, 6); // thêm vào đầu danh sách
InsertNode(head, 8, 4); // không thêm được
DisplayList(head); // in danh sách
DeleteNode(head, 7); // xóa nút có giá trị = 7
DisplayList(head); // in danh sách
DestroyList(head); // hủy toàn bộ danh sách
return 0;
}
6
7
5
6
5
kết quả
So sánh mảng và danh sách liên kết
zViệc lập trình và quản lý danh sách liên 
kết khó hơn mảng, nhưng nó có những 
ưu điểm:
{Linh động: danh sách liên kết có kích thước tăng 
hoặc giảm rất linh động.
zKhông cần biết trước có bao nhiêu nút trong danh 
sách. Tạo nút mới khi cần.
zNgược lại, kích thước của mảng là cố định tại thời gian 
biên dịch chương trình.
{Thao tác thêm và xóa dễ dàng
zĐể thêm và xóa một phần tử mảng, cần phải copy dịch 
chuyển phần tử.
zVới danh sách móc nối, không cần dịch chuyển mà chỉ
cần thay đổi các móc nối
Các dạng khác của DSLK
zDanh sách nối vòng
{Nút cuối cùng nối đến nút đầu tiên của danh 
sách
{Khi nào thì kết thúc duyệt? (kiểm tra 
currNode == head?)
A
Head
B C
Các dạng khác của DSLK
zDanh sách nối kép
{Mỗi nút không chỉ nối đến nút tiếp theo mà còn 
nối đến nút trước nó
{Có 2 mối nối NULL: tại nút đầu và nút cuối 
của danh sách
{Ưu điểm: tại một nút có thể thăm nút trước nó
một cách dễ dàng. Cho phép duyệt danh sách 
theo chiều ngược lại
A
Head
B∅ C ∅
Danh sách nối kép
zMỗi nút có 2 mối nối
{prev nối đến phần tử trước
{next nối đến phần tử sau
10 7020 5540
Head
currNode currNode->nextcurrNode->prev
Định nghĩa danh sách nối kép
typedef struct Node{
int data;
struct Node* next;
struct Node* prev;
}Node;
Thêm nút
zThêm nút New nằm ngay trước Cur
(không phải nút đầu hoặc cuối danh sách)
New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New;
10 7020 55
40Head
New
Cur
Xóa nút
zXóa nút Cur (không phải nút đầu hoặc 
cuối danh sách)
(Cur->prev)->next = Cur->next;
(Cur->next)->prev = Cur->prev; 
free (Cur);
10 7020 5540
Head
Cur
Danh sách nối kép với nút đầu giả
{Danh sách không rỗng
{Danh sách rỗng
7020 5540
Head
10
Nút đầu giả
Head
Nút đầu giả
Tạo danh sách nối kép rỗng
Node* Head = malloc 
(sizeof(Node));
Head->next = Head;
Head->prev = Head;
Head
Nút đầu giả
Xóa nút
zNút Cur cần xóa nằm tại đầu danh sách
7020 5540
Head
10
Nút đầu giả
Cur
(Cur->prev)->next = Cur->next;
(Cur->next)->prev = Cur->prev; 
free (Cur);
zNút cần xóa nằm ởgiữa danh sách
(Cur->prev)->next = Cur->next;
(Cur->next)->prev = Cur->prev; 
free (Cur); // giống như xóa ở đầu DS!
70
Head
10
Nút đầu giả
20 5540
Cur
zNút cần xóa nằm tại cuối danh sách
(Cur->prev)->next = Cur->next;
(Cur->next)->prev = Cur->prev; 
free (Cur); // tương tự như xóa ở giữa DS!
7020 5540
Head
10
Nút đầu giả
Cur
void deleteNode(Node* Head, int
x){
Node* Cur;
Cur = FindNode(Head, x);
if (Cur != NULL){
Cur->prev->next = Cur->next;
Cur->next->prev = Cur->prev;
free (Cur);
}
} 
Thêm nút
zThêm nút New vào sau nút giả (đầu danh 
sách) và trước nút Cur
Head
Nút giả
Cur
20
New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New;
10
New
zThêm nút New vào trước nút CurNew->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New; // giống như thêm vào đầu!
55
Head
10
Nút giả
20
Cur
40
New
Thêm vào giữa DS
zThêm nút New vào cuối DS (lúc này Cur
trỏ vào nút giả)New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New; // giống như thêm vào đầu
7020 5540
Head
10
Nút giả
Cur New
Thêm vào cuối DS
zThêm New vào danh sách rỗng (Cur trỏ
vào nút giả)
Head
Nút giả
New
20
New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New;
Cur
Thêm vào DS rỗng
void insertNode(Node* Head, int item){ 
Node *New, *Cur; 
New = malloc (sizeof(Node));
New->data = item;
Cur = Head->next;
while (Cur != Head){ 
if (Cur->data < item)
Cur = Cur->next;
else 
break;
}
New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New;
}
5. Sử dụng danh sách móc nối
zBài toán cộng 2 đa thức:
5x4 + 6x3 + 7
+ 2x3 – 7x2 + 3x
= 5x4 + 8x3 – 7x2 + 3x + 7
zMỗi nút của danh sách:
4
exponent next
nút
5
coef
Figure 3-38
Biểu diễn đa thức
z typedef struct poly{
float hs;
float sm;
struct poly *nextNode;
}