1. Tổ chức dữ liệu:
Quản lý danh sách: Dùng 2 con trỏ First và Last trỏ đến đầu và cuối danh sách
- Khai báo:
struct nut
{
<type> Data;
nut *prev,*next;
};
typedef nut *Tro;
2. Các thao tác cơ bản:
a. Khởi tạo danh sách:
First=Last=NULL;
b. Bổ sung nút mới vào đầu/cuối hoặc vị trí bất kỳ
* Bổ sung cuối:
B1: Tạo nút mới chứa x
Tro p=new (nut);
p->Data=x;
p->prev=p->next=NULL;
B2: Bổ sung
if(First==NULL) First=Last=p;
else
{
p->prev=Last;//1
Last->next=p;//2
Last=p;//3
}
* Bổ sung sau nút q:
B1: Khởi tạo
Tro p=new(nut);
p->Data=x;
B2: Bổ sung
Tro r=q->next;
p->next=r;//1
q->next=p;//2
p->prev=q;//3
r->prev=p;//4
c. Xóa nút đầu/ giữa hoặc cuối
* Xóa đầu:
Tro p=First;
if(First==Last) First=Last=NULL;
else
{
First=p->next;
First->prev=NULL;
delete(p);
}
* Xóa nút đứng sau q:
Tro p=q->next;
Tro r=p->next;
q->next=r;//1
r->prev=q;//2
delete(p);
Viết hàm kiểm tra Danh sách liên kết kép có phải đối xứng không?
bool doiXung(Tro F, Tro L)
{
if(F==L) return true;
else
return doiXung(F->next, L->prev);
}