CÁC THAO TÁC TRÊN DANH SÁCH LIÊN KẾT ĐƠN C++ potx
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (134.3 KB, 5 trang )
CÁC THAO TÁC TRÊN DANH
SÁCH LIÊN KẾT ĐƠN C++
3. Đếm
3.1. Đếm số phần tử
(SV tự vẽ hình minh họa)
- Đầu vào: DSLK đơn l
- Kết quả: Trả về số lượng các phần tử trong danh sách
- Giải thuật:
B1: d=0
p trỏ vào đầu danh sách
B2: Nếu p = NULL thì trả về d. Kết thúc
B3: d=d+1
B4: p trỏ đến phần tử kế tiếp, quay lại B2
- Cài đặt:
int SoLuongNode(LIST l)
{
int d=0;
NODE *p=l.pHead;
while(p)
{
d++;
p=p->pNext;
}
return d;
}
3.2. Đếm số phần tử thỏa điều kiện
(SV tự vẽ hình minh họa)
Đầu vào: DSLK đơn l, điều kiện bên ngoài (nếu có: ví dụ giá trị x để so
sánh)
- Kết quả: Trả về số lượng các phần tử thỏa điều kiện trong danh sách
- Giải thuật:
B1: d=0
p trỏ vào đầu danh sách
B2: Nếu p = NULL thì trả về d. Kết thúc
B3: Nếu giá trị p thỏa điều kiện thì
d=d+1
B4: p trỏ đến phần tử kế tiếp, quay lại B2
- Cài đặt (Giả sử đếm số lượng phần tử có giá trị chẵn trong danh sách
số nguyên):
int SoLuongNodeChan(LIST l)
{
int d=0;
NODE *p=l.pHead;
while(p)
{
if(p->Key%2==0)
d++;
p=p->pNext;
}
return d;
}
4. Kiểm tra
4.1. Kiểm tra tồn tại một phần tử thỏa mãn điều kiện cho trước
(SV tự vẽ hình minh họa)
- Đầu vào: DSLK đơn l, điều kiện bên ngoài (nếu có: ví dụ giá trị x để so
sánh)
- Kết quả: Trả về 1 nếu thỏa điều kiện, ngược lại trả về 0
- Giải thuật:
B1: p trỏ vào đầu danh sách
B2: Nếu p = NULL thì trả về 0. Kết thúc
B3: Nếu giá trị p thỏa điều kiện thì Trả về 1. Kết thúc
B4: p trỏ đến phần tử kế tiếp, quay lại B2
- Cài đặt (Giả sử kiểm tra xem danh sách có tồn tại phần tử có giá trị lẻ
trong danh
sách số nguyên):
int KiemTraTonTaiLe(LIST l)
{
NODE *p=l.pHead;
while(p)
{
if(p->Key%2!=0)
return 1;
p=p->pNext;
}
return 0;
}
4.2. Kiểm tra toàn bộ các phần tử thỏa mãn điều kiện cho trước
- Đầu vào: DSLK đơn l, điều kiện bên ngoài (nếu có: ví dụ giá trị x để so
sánh)
- Kết quả: Trả về 1 nếu thỏa điều kiện, ngược lại trả về 0
- Giải thuật:
B1: p trỏ vào đầu danh sách
B2: Nếu p = NULL thì trả về 1. Kết thúc
B3: Nếu giá trị p KHÔNG thỏa điều kiện thì
Trả về 0. Kết thúc
B4: p trỏ đến phần tử kế tiếp, quay lại B2
- Cài đặt (Giả sử kiểm tra xem toàn bộ các phần tử trong danh sách đều
có giá trị
chẵn trên danh sách số nguyên):
int KiemTraToanChan(LIST l)
{
NODE *p=l.pHead;
while(p)
{
if(p->Key%2!=0)
return 0;
p=p->pNext;
}
return 1;
}
Cài đặt (Giả sử kiểm tra xem danh sách số nguyên có tăng dần hay
không):
int KiemTraTang(LIST l)
{
NODE *p=l.pHead;
while(p!=l.pTail)
{
if(p->Key > (p->pNext)->Key)
return 0;
p=p->pNext;
}
return 1;
}
