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:
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
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:
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
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:
Tro p=First;
First=First->link;
delete(p);
* Xóa nút cuối danh sách:
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:
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