单链表算法实现：找最大值节点与统计不及格人数

实验一（2）单链表 在这个实验中，我们将探讨两个关于单链表的问题，分别是找到链表中最大元素所在的结点以及统计成绩不及格的学生人数。这两个问题都是基于链表的基本操作，如插入、遍历和查找。 首先，我们定义了链表节点的数据结构，如下： ```cpp typedef int ElemType; typedef struct LNode { ElemType data; // 节点存储的数据 struct LNode* next; // 指向下一个节点的指针 } LNode, *LinkList; ``` 这里，`LNode` 是一个结构体，包含一个整型数据 `data` 和一个指向下一个节点的指针 `next`。`LinkList` 是一个指向 `LNode` 结构体的指针，通常用于表示链表的头结点。 第一个问题是在单链表中找出最大元素的结点。为此，我们编写了一个名为 `MaxNode` 的函数： ```cpp int MaxNode(LinkList h) { int j, k; LNode *p, *q; if (h->next == NULL) return 0; q = h->next; p = q->next; k = 1; j = 2; while (p != NULL) { if (p->data > q->data) { q = p; k = j; } p = p->next; j++; } return k; } ``` 这个函数接收链表的头结点作为参数，通过遍历链表，比较当前结点和前一个结点的值来找到最大值的结点。返回的是最大值结点在链表中的位置（从1开始计数）。 第二个问题是根据输入的学生人数和成绩建立链表并统计不及格人数。这可以通过以下步骤实现： 1. 从键盘读取学生人数和成绩。 2. 使用 `CreateLink` 函数创建链表，将成绩作为节点数据插入链表。 3. 遍历链表，统计不及格（假设不及格为60分以下）的人数。 创建链表的函数 `CreateLink` 定义如下： ```cpp void CreateLink(LinkList& h, ElemType a[], int n) { LNode *s, *r; int i; h = (LNode*)malloc(sizeof(LNode)); // 创建头结点 r = h; for (i = 0; i < n; i++) { s = (LNode*)malloc(sizeof(LNode)); // 为每个元素创建新节点 s->data = a[i]; // 设置节点数据 r->next = s; // 将新节点连接到链表 r = s; } r->next = NULL; // 设置尾部指针为 NULL } ``` 最后，在主函数 `main` 中，我们可以将上述功能结合起来，实现完整的程序： ```cpp int main() { LinkList head; ElemType a[N]; int i, k; cout << "请输入一组数：" << endl; for (i = 0; i < N; i++) scanf_s("%d", &a[i]); CreateLink(head, a, N); // 输出链表所有结点的数据 output(head); // 输出最大值结点序号 k = MaxNode(head); cout << "最大值结点序号：" << k << endl; // 统计不及格人数的代码... } ``` 以上就是关于单链表实验的详细解释，涵盖了链表的基本操作和查找算法。在这个过程中，我们学习了如何建立链表、遍历链表以及在链表中查找特定值。这些是数据结构和算法学习的基础，对于理解和解决更复杂的问题至关重要。