Võ Văn Hải's blog

Chỉ có một điều tuyệt đối đó là mọi thứ đều tương đối…

Một số thao tác trên danh sách liên kết đơn

Trong bài này là một số thao tác cơ bản trên dslk đơn có trường dữ liệu kiểu nguyên


#include<iostream.h>
#include<fstream.h>

//khai báo 1 node
struct node{
int data;
node*next;
};

struct dslk{
node* head;
node* tail;
};
//Thu tuc cho phep tao 1 node khi có gia tri x
//@param x la gia tri cua nut
//@return con tro tro den nut chua gia tri x
node* createNode(int x){
node *p; p=new node;
if(p==NULL)return NULL;
p->data=x;
p->next=NULL;
return p;
}
///Ham khoi tao 1 dslk
//@param l la danh sach can khoi tao
void init( dslk &l){
l.head=NULL;
l.tail=NULL;
}
//ham them 1 nut vao dau dslk
//param p la nut can them
void addFirst(dslk &l,node*p){
if(l.head==NULL)
l.head=l.tail=p;
else{
p->next=l.head;
l.head=p;
}
}

void addLast(dslk &l,node*p){
if(l.head==NULL)
l.head=l.tail=p;
else{
l.tail->next=p;
l.tail=p;
}
}
//chen node n vao sau node p trong danh sach
void addAfter(dslk&l,node *q,node*new_node){
if(l.head==NULL&&q==NULL)
l.head=l.tail=new_node;
if (q!=NULL){
new_node->next = q->next;
q->next = new_node;
if(q == l.tail)
l.tail = new_node;
}

}

void addBefore(dslk&l,node *q,node*new_node){
node*p=NULL;
node*t=l.head;
while(t->data!=q->data&&t!=NULL){
p=t;
t=t->next;
}
addAfter(l,p,new_node);
}
//add phan tu vao sao cho danh sach luon tang dan
void addSort(dslk&l,node*n){
if(l.head==NULL)
l.head=l.tail=n;
else{
if(n->data<=l.head->data)
addFirst(l,n);
else if(n->data>=l.tail->data)
addLast(l,n);
else{
node*t=l.head;
while(t!=NULL){
if(t->data>n->data)
break;
t=t->next;
}
addBefore(l,t,n);
}
}
}

//Ham nay dung de duyet qua danh sach va in gia tri data
//param l la danh sach can duyet
void traverse(dslk l){
node*t=l.head;
while(t!=NULL){
cout<<t->data<<" ";
t=t->next;
}
cout<<endl;
}

int nodesCounter(dslk l){
node*t=l.head;
int dem=0;
while(t!=NULL){
dem++;
t=t->next;
}
return dem;
}

node*searchByKey(dslk l,int data){
node*t=l.head;
while(t!=NULL){
if(t->data==data)
return t;
t=t->next;
}
return NULL;
}
//xoa 1 phan tu dau danh sach
int deleteFirst(dslk&l){
if(l.head==NULL)
return -1;
node*p=l.head;//phan tu can xoa
l.head=p->next;
if(l.head==NULL)
l.tail=NULL;
delete p;
return 1;
}
//Xoa 1 node sau node q
//tra ve 1 neu xoa thanh cong
int deleteAfter(dslk&l,node*q){
if(q==NULL || q->next==NULL)
return -1;
node*p=q->next;
q->next=p->next;
if(p==l.tail)
l.tail=q;
delete p;
return 1;
}
//xoa 1 nút có khóa là key
//tra ve -1 neu ds rong, 0 neu khong tim thay, 1 neu OK
int deleteByKey(dslk&l,int key){
if(l.head==NULL) return -1;
node*sau=l.head;
node*truoc=NULL;
while(sau!=NULL){
if(sau->data==key) break;
truoc=sau;
sau=sau->next;
}
if(sau==NULL)
return 0;
if(truoc==NULL)
return deleteFirst(l);
return deleteAfter(l,truoc);
}
//xoa tat ca cac nut trong dslk l co data=key
void deleteByKeyAll(dslk&l,int key){
if(l.head==NULL) return;
node*sau=l.head;
node*truoc=NULL;int x=-1;
while(sau!=NULL){
x=-1;
if(sau->data==key){
if(truoc==NULL)
deleteFirst(l);
else
deleteAfter(l,truoc);
sau=l.head;
truoc=NULL;
x=1;
}
if(x!=1){
truoc=sau;
sau=sau->next;
}
}
}
//huy toan bo danh sach
void removeAll(dslk&l){
node*p;
while(l.head!=NULL){
p=l.head;
l.head=p->next;
delete p;
}
l.tail=NULL;
}
//ham ghi du lieu xuong file
void write2file(char * filename, dslk ds){
ofstream fs(filename, ios::binary | ios::out );//| ios::app
node*t=ds.head;
while(t!=NULL){
fs.write((char*)&t->data,sizeof(int));
t=t->next;
}
fs.close();
}
///hàm doc du lieu tu file
void readfromfile(char * filename, dslk &ds){
init(ds);
ifstream infile(filename,ios::in|ios::binary);
if(infile!=NULL){
int data;
infile.read((char*)&data,sizeof(int));
while(!infile.eof()){
node*n=createNode(data);
addLast(ds,n);
infile.read((char*)&data,sizeof(int));
}
}
infile.close();
}

2 Responses to “Một số thao tác trên danh sách liên kết đơn”

  1. Huy said

    thầy ạ !
    đối với Java thì em phải tạo danh sách liên kết như thế nào ạ ???

  2. minh thư said

    Em đang gặp vướng mắc về chương trình đồ họa mô phỏng ứng dụng của danh sách liên kết đơn. Em mong thầy giúp đỡ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: