Chủ đề : DANH SÁCH LIÊN KẾT
GVHD: Thầy TRẦN HỮU QUỐC THƯ
Thực hiện : VÕ MINH THÔNG
HỒ THỊ HỒNG VÂN
NGUYỄN TRẦN CẨM THÚY

?
Danh sách liên kết là tập hợp các phần tử được nối
kết với nhau theo trình tự tuyến tính và trên đó có
các thao tác tìm kiếm ,thêm bớt loại bỏ ,sắp xếp ….

():Các loại danh sách liên kết :
A B YX Z
Danh sách liên kết kép :
Mỗi phần tử liên kết với phần tử đứng trước và sau nó trong danh sách:
Danh sách liên kết đơn :
Mõi phần tử liên kết với một phần tử đứng trước nó trong danh sách:
A B X Y Z

Danh sách liên kết vòng:
Phần cuối danh sách liên kết với phần tử đầu danh sách :
A B C X Y
A B X Y Z
Vòng đơn
Vòng kép

Cấu trúc dữ liệu của một phần tử trong danh sách đơn
Mỗi phần tử trong danh sách đơn là một cấu trúc chứa hai thông tin
-Thành phần dữ liệu : lưu trữ các thông tin về bản thân phần tử
-Thành phần mối liên kết : lưu trữ địa chỉ của thành

thêm một con trỏ pTail giữ địa chỉ phần tử cuối xâu qua
khai báo sau :

NODE *pTail
khi đó ta được một danh sách đơn
A B YX Z
pTail
pHead

Các thao tác với danh sách:
//khoi tao danh sach
void init_list()
{
pHead = NULL;
}
//tao mot nut co gia tri la X
Node * GetNode(int x)
{
Node * pNew = new Node;
pNew->info=x;
pNew->pNext=NULL;
return pNew;
}

Thuật tóan :
Bước 1 :
Nếu danh sách rỗng thì
B1.1: pHead=pNew
B1.2:pTail=pHead;
Ngược lại :

pHead

//them mot phan tu vao cuoi danh sach
void add_last(int x)
{
if (pHead==NULL)
add_first (x);
else
{
Node * pNew=GetNode(x);
Node * pTail=pHead;
while(pTail->pNext!=NULL)
{
pTail=pTail->pNext;
}
pTail->pNext=pNew;
}
}

A B
Y
X
Z
phead
pTail
p

//them mot phan tu x vao sau phan tu y
void add(int x,int y)
{

Node *p=pHead;
pHead=pHead->pNext;
delete p;
return 0;
}
return -1;
}
Xoá phần tử đầu danh sách:

Thuật toán
Nếu q!=NULL thì
B1 p=q->pNext // p là phần tử cần hủy
B2 nếu (p!=NULL) thì // q không phải là phần tử cuối xâu
B2.1 q->pNext=p->pNext // tách p ra khỏi xâu
B2.2 delete p // hủy biến động do p trỏ đến

Xóa p sau một phần tử đứng sau phần tử q :
A B YX Z
pTail
p
q
pHead
//xoa sau phan tu x trong danh sach
int del(int x)
{
Node * p=find(x);
if(p!=NULL && p->pNext!=NULL)
{
Node * q=p->pNext;
p->pNext=q->pNext;

Bước 1
Tìm phần tử p có khóa x ( một cách hình thức
gọi info = x) và phần tử q đứng trước
p ( a->pNext =p)
Bước 2
Nếu (p!=NULL) thì hủy p ra khỏi xâu tương tự
hủy phần tử q // tìm thấy x
Ngược lại: thông báo không co phần tử khóa x

Xoá phần tử có giá trị x:
// xoa phan tu co gia tri la x
int del_X(int x)
{
Node * p=pHead;
Node * q=NULL;
while(p!=NULL && p->info==x)
{
q=p;
p=p->pNext;
}
if(p==NULL)
return -1;
else
if(p==pHead)
del_first();
else
{
q->pNext=p-
>pNext;
delete p;


Hủy toàn bộ danh sách ( và giải phóng bộ nhớ )

Để duyệt danh sách ( và sử lý từng phần tử ) thực hiện các
thao tác như sau

Thuật toán
Bước 1 p=pHead // cho p trỏ đến phần tử đầu danh sách
Bước 2 trong khi p!=NULL// chưa hết danh sách
B2.1 xử lý phần tử p
B2.2 p=p->pNext // cho p trỏ tới phần tử kế
Riêng hủy tòan bộ danh sách có sự thay đổi trong thủ tục duyệt
( xử lý ) danh sách trên do có một thao tác hủy phần tử và khi đó
phải cập nhật các liên kết liên quan
Bước 1 trong khi pHead!=NULL // chưa hết danh sách
B1.1 p=pHead
pHead=pHead->pNext // cho pHead trỏ tới phần tử kế
B 1. 2 hủy p
B 2 pTail =NULL // bảo đảm tính nhất quán khi xâu rỗng

void process ( Node & )
{
Node * p;
p=pHead;
while ( p!=NULL)
{
processNOde(p);// xu ly cu the tung ung dung
p=p->pNext;
}
}