Danh sách nối vòng và nối kép~
Định nghĩa và nguyên tắc Danh sách liên kết vòng (xâu vòng) là một danh sách đơn (hoặc kép) mà phần tử cuối danh sách thay vì mang giá trị NULL, trỏ tới phần tử đầu danh sách. Ðể biểu diễn, ta có thể xử dụng các kỹ thuật biểu diễn như ...
Định nghĩa và nguyên tắc
Danh sách liên kết vòng (xâu vòng) là một danh sách đơn (hoặc kép) mà phần tử cuối danh sách thay vì mang giá trị NULL, trỏ tới phần tử đầu danh sách. Ðể biểu diễn, ta có thể xử dụng các kỹ thuật biểu diễn như danh sách đơn (hoặc kép).
Ta có thể khai báo xâu vòng như khai báo xâu đơn (hoặc kép). Trên danh sách vòng ta có các thao tác thường gặp sau:
Tìm phần tử trên danh sách vòng
Danh sách vòng không có phần tử đầu danh sách rõ rệt, nhưng ta có thể đánh dấu một phần tử bất kỳ trên danh sách xem như phân tử đầu xâu để kiểm tra việc duyệt đã qua hết các phần tử của danh sách hay chưa.
NODE* Search(LIST &l, Data x)
{
NODE *p;
p = l.pHead;
do
{
if ( p->Info == x)
return p;
p = p->pNext;
}while (p != l.pHead); // chưa đi giáp vòng
return p;
}
Thêm phần tử đầu xâu
void AddHead(LIST &l, NODE *new_ele)
{
if(l.pHead == NULL) //Xâu rỗng
{
l.pHead = l.pTail = new_ele;
l.pTail->pNext = l.pHead;
}
else
{
new_ele->pNext = l.pHead;
l.pTail->pNext = new_ele;
l.pHead = new_ele;
}
}
Thêm phần tử cuối xâu
void AddTail(LIST &l, NODE *new_ele)
{
if(l.pHead == NULL) //Xâu rỗng
{
l.pHead = l.pTail = new_ele;
l.pTail->pNext = l.pHead;
}
else
{
new_ele->pNext = l.pHead;
l.pTail->pNext = new_ele;
l.pTail = new_ele;
}
}
Thêm phần tử sau nút q
void AddAfter(LIST &l, NODE *q, NODE *new_ele)
{
if(l.pHead == NULL) //Xâu rỗng
{
l.pHead = l.pTail = new_ele;
l.pTail->pNext = l.pHead;
}
else
{
new_ele->pNext = q->pNext;
q->pNext = new_ele;
if(q == l.pTail)
l.pTail = new_ele;
}
}
Hủy phần tử đầu xâu
void RemoveHead(LIST &l)
{ NODE *p = l.pHead;
if(p == NULL) return;
if (l.pHead = l.pTail) l.pHead = l.pTail = NULL;
else
{
l.pHead = p->Next;
if(p == l.pTail)
l.pTail->pNext = l.pHead;
}
delete p;
}
Hủy phần tử đứng sau nút q
void RemoveAfter(LIST &l, NODE *q)
{ NODE *p;
if(q != NULL)
{
p = q ->Next ;
if ( p == q) l.pHead = l.pTail = NULL;
else
{
q->Next = p->Next;
if(p == l.pTail)
l.pTail = q;
}
delete p;
}
}
NHẬN XÉT
Ðối với danh sách vòng, có thể xuất phát từ một phần tử bất kỳ để duyệt toàn bộ danh sách
Danh sách liên kết kép là danh sách mà mỗi phần tử trong danh sách có kết nối với 1 phần tử đứng trước và 1 phần tử đứng sau nó.
Các khai báo sau định nghĩa một danh sách liên kết kép đơn giản trong đó ta dùng hai con trỏ: pPrev liên kết với phần tử đứng trước và pNext như thường lệ, liên kết với phần tử đứng sau:
typedef struct tagDNode
{
Data Info;
struct tagDNode* pPre; // trỏ đến phần tử đứng trước
struct tagDNode* pNext; // trỏ đến phần tử đứng sau
}DNODE;
typedef struct tagDList
{
DNODE* pHead; // trỏ đến phần tử đầu danh sách
DNODE* pTail; // trỏ đến phần tử cuối danh sách
}DLIST;
khi đó, thủ tục khởi tạo một phần tử cho danh sách liên kết kép được viết lại như sau :
DNODE* GetNode(Data x)
{ DNODE *p;
// Cấp phát vùng nhớ cho phần tử
p = new DNODE;
if ( p==NULL) {
printf("Không đủ bộ nhớ");
exit(1);
}
// Gán thông tin cho phần tử p
p ->Info = x;
p->pPrev = NULL;
p->pNext = NULL;
return p;
}
Tương tự danh sách liên kết đơn, ta có thể xây dựng các thao tác cơ bản trên danh sách liên kết kép (xâu kép). Một số thao tác không khác gì trên xâu đơn. Dưới đây là một số thao tác đặc trưng của xâu kép:
Chèn một phần tử vào danh sách:
Có 4 loại thao tác chèn new_ele vào danh sách:
Cách 1: Chèn vào đầu danh sách
Cài đặt :
void AddFirst(DLIST &l, DNODE* new_ele)
{
if (l.pHead==NULL) //Xâu rỗng
{
l.pHead = new_ele; l.pTail = l.pHead;
}
else
{
new_ele->pNext = l.pHead; // (1)
l.pHead ->pPrev = new_ele; // (2)
l.pHead = new_ele; // (3)
}
}
NODE* InsertHead(DLIST &l, Data x)
{ NODE* new_ele = GetNode(x);
if (new_ele ==NULL) return NULL;
if (l.pHead==NULL)
{
l.pHead = new_ele; l.pTail = l.pHead;
}
else
{
new_ele->pNext = l.pHead; // (1)
l.pHead ->pPrev = new_ele; // (2)
l.pHead = new_ele; // (3)
}
return new_ele;
}
Cách 2: Chèn vào cuối danh sách
Cài đặt :
void AddTail(DLIST &l, DNODE *new_ele)
{
if (l.pHead==NULL)
{
l.pHead = new_ele; l.pTail = l.pHead;
}
else
{
l.pTail->Next = new_ele; // (1)
new_ele ->pPrev = l.pTail; // (2)
l.pTail = new_ele; // (3)
}
}
NODE* InsertTail(DLIST &l, Data x)
{ NODE* new_ele = GetNode(x);
if (new_ele ==NULL) return NULL;
if (l.pHead==NULL)
{
l.pHead = new_ele; l.pTail = l.pHead;
}
else
{
l.pTail->Next = new_ele; // (1)
new_ele ->pPrev = l.pTail; // (2)
l.pTail = new_ele; // (3)
}
return new_ele;
}
Cách 3 : Chèn vào danh sách sau một phần tử q
Cài đặt :
void AddAfter(DLIST &l, DNODE* q,DNODE* new_ele)
{ DNODE* p = q->pNext;
if ( q!=NULL)
{
new_ele->pNext = p; //(1)
new_ele->pPrev = q; //(2)
q->pNext = new_ele; //(3)
if(p != NULL)
p->pPrev = new_ele; //(4)
if(q == l.pTail)
l.pTail = new_ele;
}
else //chèn vào đầu danh sách
AddFirst(l, new_ele);
}
void InsertAfter(DLIST &l, DNODE *q, Data x)
{
DNODE* p = q->pNext;
NODE* new_ele = GetNode(x);
if (new_ele ==NULL) return NULL;
if ( q!=NULL)
{
new_ele->pNext = p; //(1)
new_ele->pPrev = q; //(2)
q->pNext = new_ele; //(3)
if(p != NULL)
p->pPrev = new_ele; //(4)
if(q == l.pTail)
l.pTail = new_ele;
}
else //chèn vào đầu danh sách
AddFirst(l, new_ele);
}
Cách 4 : Chèn vào danh sách trước một phần tử q
Cài đặt :
void AddBefore(DLIST &l, DNODE q, DNODE* new_ele)
{ DNODE* p = q->pPrev;
if ( q!=NULL)
{
new_ele->pNext = q; //(1)
new_ele->pPrev = p; //(2)
q->pPrev = new_ele; //(3)
if(p != NULL)
p->pNext = new_ele; //(4)
if(q == l.pHead)
l.pHead = new_ele;
}
else //chèn vào đầu danh sách
AddTail(l, new_ele);
}
void InsertBefore(DLIST &l, DNODE q, Data x)
{ DNODE* p = q->pPrev;
NODE* new_ele = GetNode(x);
if (new_ele ==NULL) return NULL;
if ( q!=NULL)
{
new_ele->pNext = q; //(1)
new_ele->pPrev = p; //(2)
q->pPrev = new_ele; //(3)
if(p != NULL)
p->pNext = new_ele; //(4)
if(q == l.pHead)
l.pHead = new_ele;
}
else //chèn vào đầu danh sách
AddTail(l, new_ele);
}
Hủy một phần tử khỏi danh sách
Có 5 loại thao tác thông dụng hủy một phần tử ra khỏi xâu. Chúng ta sẽ lần lượt khảo sát chúng.
Hủy phần tử đầu xâu:
Data RemoveHead(DLIST &l)
{ DNODE *p;
Data x = NULLDATA;
if ( l.pHead != NULL)
{
p = l.pHead; x = p->Info;
l.pHead = l.pHead->pNext;
l.pHead->pPrev = NULL;
delete p;
if(l.pHead == NULL) l.pTail = NULL;
else l.pHead->pPrev = NULL;
}
return x; }
Hủy phần tử cuối xâu:
Data RemoveTail(DLIST &l)
{
DNODE *p;
Data x = NULLDATA;
if ( l.pTail != NULL)
{
p = l.pTail; x = p->Info;
l.pTail = l.pTail->pPrev;
l.pTail->pNext = NULL;
delete p;
if(l.pHead == NULL) l.pTail = NULL;
else l.pHead->pPrev = NULL;
}
return x;
}
Hủy một phần tử đứng sau phần tử q
void RemoveAfter (DLIST &l, DNODE *q)
{ DNODE *p;
if ( q != NULL)
{
p = q ->pNext ;
if ( p != NULL)
{
q->pNext = p->pNext;
if(p == l.pTail) l.pTail = q;
else p->pNext->pPrev = q;
delete p;
}
}
else
RemoveHead(l);
}
Hủy một phần tửđứng trước phần tử q
void RemoveAfter (DLIST &l, DNODE *q)
{ DNODE *p;
if ( q != NULL)
{
p = q ->pPrev;
if ( p != NULL)
{
q->pPrev = p->pPrev;
if(p == l.pHead) l.pHead = q;
else p->pPrev->pNext = q;
delete p;
}
}
else
RemoveTail(l);
}
Hủy 1 phần tử có khoá k
int RemoveNode(DLIST &l, Data k)
{
DNODE *p = l.pHead;
NODE *q;
while( p != NULL)
{
if(p->Info == k) break;
p = p->pNext;
}
if(p == NULL) return 0; //Không tìm thấy k
q = p->pPrev;
if ( q != NULL)
{
p = q ->pNext ;
if ( p != NULL)
{
q->pNext = p->pNext;
if(p == l.pTail)
l.pTail = q;
else p->pNext->pPrev = q;
}
}
else //p là phần tử đầu xâu
{
l.pHead = p->pNext;
if(l.pHead == NULL)
l.pTail = NULL;
else
l.pHead->pPrev = NULL;
}
delete p;
return 1;
}
NHẬN XÉT:
Xâu kép về mặt cơ bản có tính chất giống như xâu đơn. Tuy nhiên nó có một số tính chất khác xâu đơn như sau:
- Xâu kép có mối liên kết hai chiều nên từ một phần tử bất kỳ có thể truy xuất một phần tử bất kỳ khác. Trong khi trên xâu đơn ta chỉ có thể truy xuất đến các phần tử đứng sau một phần tử cho trước. Ðiều này dẫn đến việc ta có thể dễ dàng hủy phần tử cuối xâu kép, còn trên xâu đơn thao tác này tồn chi phí O(n).
Bù lại, xâu kép tốn chi phí gấp đôi so với xâu đơn cho việc lưu trữ các mối liên kết. Ðiều này khiến việc cập nhật cũng nặng nề hơn trong một số trường hợp. Như vậy ta cần cân nhắc lựa chọn CTDL hợp lý khi cài đặt cho một ứng dụng cụ thể.
