Cấp bậc tác giả:

JAVA

Danh sách liên kết kép

Được viết bởi QuangIT ngày 12/04/2014 lúc 10:57 PM
Quản lý danh sách: Dùng 2 con trỏ First và Last trỏ đến đầu và cuối danh sách
  • 0
  • 1915

Danh sách liên kết kép


Bài trước chia sẻ kiến thức về danh sách liên kết đơn

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

DS-kep.jpg

- 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:

DS-kep-chen-cuoi.jpg

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:

DS-kep-chen-q.jpg

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:

DS-kep-xoa-dau.jpg

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:

DS-kep-xoa-q.jpg

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);
}

Nguồn bài viết: DOTNET.VN

BÌNH LUẬN BÀI VIẾT

Bài viết mới nhất

LIKE BOX

Bài viết được xem nhiều nhất

HỌC HTML