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

JAVA

Danh sách Liên kết Đơn

Được viết bởi QuangIT ngày 12/04/2014 lúc 12:16 AM
Mỗi nút gồm 2 trường: Data và Link
  • 0
  • 2417

Danh sách Liên kết Đơn


Bài trước chia sẻ kiến thức về các thuật toán tìm kiếm

1. Khai báo:
- Mỗi nút gồm 2 trường: Data và Link
- Danh sách phải có con trỏ đến phần tử đầu tiên của danh sách
- Tổ chức dữ liệu:
struct NODE
{
<Type> Data;
NODE *Link;
};
typedef NODE* Tro;

Tro First;

2. Thao tác cơ bản:
a. Khởi tạo danh sách:
- Dùng 1 con trỏ đầu FIRST = NULL;
- Dùng 2 con trỏ đầu và cuối FIRST=LAST=NULL;
b. Bổ sung 1 phần tử X vào danh sách(giả sử danh sách trỏ bởi First&Last)

* Bổ sung đầu:

chen-dau.jpg

B1: Tạo nút mới chứa X
Tro p=new (NODE);
p->Data=X;
p->Link=NULL;

B2: Bổ sung

if(First==NULL) First=Last=p;
else
{
p->Link=First;
First=p;
}

* Bổ sung cuối

chen-cuoi.jpg

B1: Tạo nút mới chứa X

Tro p=new (NODE);
p->Data=X;
p->Link=NULL;

B2: Bổ sung

if(First==NULL) First=Last=p;
else
{
Last->Link=p;
Last=p;
}

* Chèn vào sau q:

chen-giua.jpg

B1: Tạo nút mới chứa X

Tro p=new (NODE);
p->Data=X;

B2: Bổ sung

Tro r=new (NODE);
p->Link=r;
q->Link=p;

c. Duyệt danh sách:

Tro p=First;
while(p!=NULL)
{
<Xử lý danh p->Data>;
p=p->Link;
}

Bài tập:
Tổ chức DSLK Đơn chứa các số nguyên
1. Đếm DS đó có bao nhiêu nút
2. Kiểm tra DS này đã có thứ tự tăng dần chưa
3. Sắp xếp lại danh sách theo thứ tự tăng dần
4. Giả sử có 2 danh sách được trỏ bởi L1&L2. Biểu diễn 1 hàm để nối L2 vào sau DS L1
Bài làm:
struct nut
{
int x;
int *next;
};
typedef nut* Tro;

1. Đếm
int Dem(Tro L)
{
int dem=0;
Tro P=L;
while(P!=NULL)
{
dem++;
p=p->next;
}
return dem;
}

2. Kiểm tra DS tăng dần

kiem-tra-tang-dan.jpg
bool KiemTra(Tro L)
{
if((L==NULL)||(L->next==NULL) return true;
else{
Tro q=L, p=L->next;
while(p!=NULL)
{
if(q->x>p->x) return false;
q=p;
p=p->next;
}
return true;
}
}

3. Sắp xếp tăng dần

void Sort(Tro &L)
{
Tro p=L;
while(p!=NULL)
{
Tro q=p->next;
while(q!=NULL)
{
if(p->x>q->x) swap(p->x,q->x);
q=q->next;
}
p=p->next;
}
}

4. Nối L1 với L2:

void Noi(Tro &L1, Tro L2)
{
if(L1==NULL) L1=L2;
else
{
    Tro p=L1;
    while(p!=NULL)
    p=p->next;
    p->next=L2;
}
}

d. Xóa 1 nút trong danh sách:
* Xóa nút đầu danh sách:

xoa-dau.jpg
Tro p=First;
First=First->link;
delete(p);

* Xóa nút cuối danh sách:

xoa-cuoi.jpg
if(First->next==NULL) {delete(First);First=NULL;}
else
{
Tro p=First,q;
while(p->Link!=NULL)
{
q=p;
p=p->Link;
}
q->Link=NULL;
delete(p);
}

* Xóa nút đứng sau q:

xoa-sau-q.jpg
Tro p=q->Link;
q->Link=p->Link;
delete(p);

VD: Viết hàm xóa tất cả các nút trong danh sách liên kết
void Xoa(Tro &First)
{
While(First!=NULL)
{
Tro p=First;
First=First->Link;
delete(p);
}
}
Chương trình nhập danh sách liên kết và xuất danh sách liên kết:
#include <conio.h>
#include <stdio.h>
#include <malloc.h>

struct node
{
    int key;
    node *next;
};
typedef node *Tro;
void nhap(Tro &F)
{
    //Khoi tao
    F=NULL;
    Tro L=NULL;
    //Nhap so phan tu
    int n,x;
    printf("Nhap phan tu: ");scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        printf("Nhap so phan tu: ");scanf("%d",&x);
        //Tao nut moi
        Tro p;
        p =(Tro)malloc(sizeof(struct node));
        p->key=x;
        p->next=NULL;
        //Bo sung cuoi
        if(F==NULL) F=L=p;
        else
        {
            L->next=p;
            L=p;
        }
    }
}
void xuat(Tro F)
{
    Tro p;
    p=F;
    while(p!=NULL)
    {
        printf("%d ",p->key);
        p=p->next;
    }
}
main()
{
    clrscr();
    Tro F;
    nhap(F);
    xuat(F);
    getch();
}
Bài tiếp theo sẽ chia sẻ kiến thức về danh sách liên kết kép

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