线性表算法设计题（六）

题目

设计一个算法，通过一趟遍历确定长度为n的单链表中值最大的结点。

算法思想

在遍历的时候利用指针pmax记录值最大的结点的位置。

完整代码

#include <iostream>
using namespace std;

//设计一个算法，通过一趟遍历确定长度为n的单链表中值最大的结点 

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode, *LinkList;

//创建链表
int CreateList(LinkList &L,int n){
    LNode *p,*r;
    int i;
    L = new LNode;
    L -> next = NULL;
    r = L;
    for(i = 0;i < n;i ++)
    {
        p = new LNode;
        cin >> p -> data;
        p -> next = NULL;
        r -> next = p;
        r = p;
    }
    return 0;
}

ElemType Max(LinkList L){
    //确定单链表中值最大的结点 
    LinkList pmax, p;
    if(L -> next == NULL){
        return NULL;
    }
    pmax = L -> next;                    //pmax指向首元结点 
    p = L -> next -> next;               //p指向第二个结点 
    while(p != NULL){                    //遍历链表，如果下一个结点存在 
        if(p -> data > pmax -> data){
            pmax = p;                    //pmax指向数值大的结点 
        }
        p = p -> next;                   //p指向下一个结点，继续遍历 
    }
    return pmax -> data;
}

int main(){
    LinkList L;
    int n;
    cout << "请输入链表的长度：";
    cin >> n;
    cout << "请依次输入要存入的数据：" << endl;
    CreateList(L, n);
    int max = Max(L);
    cout << "该链表的最大值为：" << max << endl;
    return 0;
} 

结果显示

TIM图片20191026124952.png