Một số hàm căn bản trong danh sách liên kết đơn

Dưới đây là một số hàm căn bản cần thiết khi đụng chạm tới bài tập danh sách liên kết đơn.

// hàm tạo list rỗng

Mã:

void Init(LIST &l)

{

l.pHead=l.pTail=NULL;

}

// Hàm tạo NODE

Mã:

NODE* GetNode(int x)

{

NODE* p;

p=new NODE;

if(p==NULL)

{

cout<<"cap phat bo nho khong du.";

exit(0);

}

p->data=x;

p->pNext=NULL;

return p;

}

// hàm Thêm Node đầu

Mã:

void AddHead(LIST &l,NODE* new_ele)

{

if(l.pHead==NULL)

l.pHead=l.pTail=new_ele;

else

{

new_ele->pNext=l.pHead;

l.pHead=new_ele;

}

}

// Hàm thêm node cuối

Mã:

void AddTail(LIST &l,NODE* new_ele)

{

if(l.pTail==NULL)

l.pHead=l.pTail=new_ele;

else

{

l.pTail->pNext=new_ele;

l.pTail=new_ele;

}

}

//Hàm nhập danh sách:

Mã:

void InPut(LIST &l)

{

int x;

NODE *pnew;

Init(l);

do{

cout<<"Nhap gia tri: (nhan 0 de ket thuc) ";

cin>> x;

if ( x==0)

break;

pnew = GetNode(x);

AddHead(l, pnew);

}while (true);

}

// Hàm xuất danh sách

Mã:

OutPut(LIST l)

{

NODE *p =l.pHead;

while (p)

{

cout<< p ->data<<" ";

p = p->pNext;

}

}

//Hàm tìm NODE nhỏ nhất

Mã:

*TimMin( LIST l , NODE * vtmin)

{

vtmin = l.pHead;

for ( NODE *p = l.pHead->pNext; p; p = p->pNext)

{

if ( p ->data < vtmin ->data)

vtmin = p;

}

return vtmin;

}

// Hàm xóa NODE đầu

Mã:

void Xoadau( LIST &l)

{

NODE *p =l.pHead;

l.pHead = l.pHead ->pNext;

delete p;

}

// Hàm chèn node vào sau node p

Mã:

void ChenNodeSaup (LIST &l, NODE *p, NODE *pnew)

{

pnew ->pNext = p ->pNext;

p ->pNext = pnew;

}

// Hàm chèn node vào trước node p

Mã:

void ChenNodeTruocp (LIST &l, NODE *p, NODE *pnew)

{

ChenNodeSaup(l,p,pnew);

HoanVi(p->data,pnew->data);

}

// Hàm tìm NODE trước NODE p

Mã:

NODE *NodePrv(LIST l, NODE *p)

{

if( p == l.pHead || p == NULL )

return NULL;

for( NODE *prv =l.pHead; prv; prv=prv ->pNext)

if(prv->pNext ->data = p->data)

return prv;

}

// Hàm huy danh sach

Mã:

void destroylist (LIST l)

{

if( l.pHead == l.pTail)

Init(l);

NODE *p =l.pHead;

while (p)

{

delete p;

p =p ->pNext;

}

}

// Hàm sắp xếp danh sách

Mã:

void Doichotructiep(LIST l)

{

for(NODE* p=l.pHead;p;p=p->pNext)

for(NODE*q=p->pNext;q;q=q->pNext)

if(p->data>q->data)

HoanVi(p->data,q->data);

}

Hoặc

Mã:

void Chontructiep(LIST l)

{

NODE *pmin;

for( NODE *p =l.pHead;p!= l.pTail;p = p->pNext)

{

pmin =p;

for ( NODE *q = p->pNext;q; q = q->pNext)

if (q->data < pmin ->data)

pmin = q;

HoanVi(pmin ->data,p->data);

}

}