Xem mẫu
- ́ ́
Danh sach liên kêt đôi
(Doubly Linked List)
- • Là danh sach mà môi phân tử có 2 môi liên
́ ̃ ̀ ́
́
kêt:
– Next: để kêt nôi với phân tử kế tiêp
́ ́ ̀ ́
– Prev: để kêt nôi với phân tử trước nó
́ ́ ̀
pos
head
rear
- ̣̀
Cai đăt DSLK đôi
• Cai đăt: dựa trên con tro, bao gôm:
̀ ̣ ̉ ̀
• 3 con tro: head (đâu ds), pos (phân tử hiên hanh), và
̉ ̀ ̀ ̣ ̀
́
rear (cuôi ds)
• biên count: số phân tử cua danh sach
́ ̀ ̉ ́
typedef struct nodet { next
elem data;
data
struct nodet *next, *prev;
} node; prev
typedef node *nodeptr;
- pos
head
rear
typedef struct {
nodeptr head, pos, rear;
int count;
} list;
- ́ ́ ́ ́
Cac thao tac trên danh sach liên kêt đôi
• Tương tự như danh sach liên kêt đơn ngoai
́ ́ ̣
trừ 2 thao tac (cuc bô) lam thay đôi liên kêt:
́ ̣ ̣̀ ̉ ́
– Chen phân tử vao danh sach
̀ ̀ ̀ ́
– Xoa phân tử trong danh sach liên kêt
́ ̀ ́ ́
• Bổ sung thêm môt số thao tac như:
̣ ́
– Khởi đâu từ cuôi danh sach
̀ ́ ́
– Di chuyên qua phân tử trước phân tử hiên hanh
̉ ̀ ̀ ̣ ̀
- Chen phân tử x vao danh sach
̀ ̀ ̀ ́
q
p
head
rear
wp
• Chen đâu danh sach (xet theo chiêu xuôi):
̀ ̀ ́ ́ ̀
– q = head
– newp->next = q
– head = newp
- Chen phân tử x vao danh sach
̀ ̀ ̀ ́
q
p
head
rear
newp
• Chen sau p (xet theo chiêu xuôi):
̀ ́ ̀
– q = p->next
– newp->next=q
– p->next = newp
- ̉ ̣ ̀
Giai thuât chen
Câp phat bộ nhớ cho newp, gan dữ liêu
́ ́ ́ ̣
1.
Xac đinh con trỏ q=(p==NULL? head:p->next)
̣́
2.
́́
3. Kêt nôi xuôi
3.1 newp→next = q;
3.2 Nêu p=NULL thì
́
head = newp
3.3 Ngược lai
̣
p→next = newp
Kêt nôi ngược
́́
4.
4.1 newp→prev = p;
4.2 Nêu q=NULL thì
́
rear = newp
4.3 Ngược lai
̣
q→prev = newp
́
5. Tăng biên count
- Ham chen phân tử vao danh sach
̀ ̀ ̀ ̀ ́
void insertlist(list &l, elem &x, nodeptr p)
{ nodeptr newp, q;
newp = new node;
memcpy(&newp->data, &x, sizeof(elem));
q = (p==NULL? l.head: p->next);
newp->next = q;
if (p==NULL)
l.head = newp;
else
p->next = newp;
newp->prev = p;
if (q==NULL)
l.rear = newp;
else
q->prev = newp;
l.count++;
- Ham xoa phân tử trongdanh sach
̀ ́ ̀ ́
void deletelist(list &l, nodeptr p)
{
nodeptr t, q;
t = (p==NULL? l.head: p->next);
q = t->next;
if (p==NULL)
l.head = q;
else
p->next = q;
if (q==NULL)
l.rear = p;
else
q->prev = p;
delete t;
l.count--;
}
- Bổ sung 2 ham
̀
• Khởi đâu tử cuôi danh sach
̀ ́ ́
void startend(list &l)
{
l.pos = l.rear;
}
• Di chuyên đên phân tử trước phân tử hiên hanh
̉ ́ ̀ ̀ ̣ ̀
void skipbefore(list &l)
{
if (l.pos == NULL)
l.pos = l.rear;
else
l.pos = l.pos->prev;
}
- • Thiêt kế kiêu số nguyên lớn với cac phep
́ ̉ ́ ́
́ ̣ ́ ̣ ́
toan: công, nhân. Ap dung tinh 100!, 7100
• 349093429
• 675432
nguon tai.lieu . vn
