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