Tìm max trong danh sách liên kết đơn C

CÁC THAO TÁC TRÊN DANH
SÁCH LIÊN KẾT ĐƠN C++



struct tNODE
{
Key;
struct tNODE *pNext;
};
typedef struct tNODE NODE;
struct tList
{
NODE *pHead, *pTail;
};
typedef struct tList LIST;

***yêu cầu:
1. Tìm kiếm
2. Duyệt
3. Đếm
4. Kiểm tra
5. Thêm
6. Xóa
7. Sắp xếp
1. Tìm kiếm
1.1. Tìm phần tử có giá trị x
(SV tự vẽ hình minh họa)

Đầu vào: DSLK đơn l, giá trị x
- Kết quả: Trả về con trỏ tìm được (hoặc NULL: Nếu không có x)
- Giải thuật:
B1: p trỏ vào đầu danh sách
B2: Nếu p = NULL thì trả về NULL. Kết thúc
Ngược lại sang B3
B3: Nếu giá trị p = x thì trả về p. Kết thúc
B4: p trỏ đến phần tử kế tiếp, quay lại B2
- Cài đặt (Giả sử tìm phần tử có giá trị x trên danh sách số nguyên):

NODE *TimX(LIST l, int x)
{
NODE *p=l.pHead;
while(p)
{
if(p->Key==x)
return p;
p=p->pNext;
}
return NULL;
}

1.2. Tìm phần tử có giá trị max / min
(SV tự vẽ hình minh họa)











Đầu vào: DSLK đơn l
- Kết quả: Trả về con trỏ max tìm được
- Giải thuật:
B1: pMax trỏ vào đầu danh sách
p trỏ vào sau pMax
B2: Nếu p = NULL thì trả về pMax. Kết thúc
Trang
3
GV: Trần Minh Thái
Ngược lại sang B3
B3: Nếu giá trị p > giá trị pMax thì gán pMax = p
B4: p trỏ đến phần tử kế tiếp quay lại B2
- Cài đặt (Giả sử tìm max trên danh sách số nguyên):

NODE *TimMax(LIST l)
{
NODE *pMax=l.pHead, *p=pMax->pNext;

while(p)
{
if(p->Key>pMax->Key)
pMax = p;
p=p->pNext;
}
return pMax;
}

1.3. Tìm phần tử có giá trị thỏa điều kiện xuất hiện đầu tiên
(Giả sử phần tử có giá trị chẵn xuất hiện đầu tiên trên danh sách số
nguyên)
(SV tự vẽ hình minh họa)











- Đầu vào: DSLK đơn l
- Kết quả: Trả về con trỏ chứa giá trị chẵn đầu tiên tìm được (hoặc
NULL: Nếu
không có chẵn)
- Giải thuật:
B1: p trỏ vào đầu danh sách

B2: Nếu p = NULL thì trả về NULL. Kết thúc
Ngược lại sang B3
B3: Nếu giá trị p là chẵn thì trả về p. Kết thúc
B4: p trỏ đến phần tử kế tiếp, quay lại B2
-Cài đặt:

NODE *TimChanDau(LIST l)
{
NODE *p=l.pHead;
while(p)
{
if(p->Key%2==0)
return p;
p=p->pNext;
}
return NULL;
}

1.4. Tìm phần tử có giá trị thỏa điều kiện xuất hiện cuối cùng
(Giả sử phần tử có giá trị chẵn xuất hiện cuối cùng trên danh sách số
nguyên)
(SV tự vẽ hình minh họa)







Đầu vào: DSLK đơn l

- Kết quả: Trả về con trỏ chứa giá trị chẵn xuất hiện cuối cùng (hoặc
NULL: Nếu
không có chẵn)
- Giải thuật:
B1: p trỏ vào đầu danh sách
pChanCuoi=NULL;
B2: Nếu p = NULL thì trả về pChanCuoi. Kết thúc
Ngược lại sang B3
B3: Nếu giá trị p là chẵn thì gán pChanCuoi = p
B4: p trỏ đến phần tử kế tiếp, quay lại B2