数据结构题目：链表

题目：求相邻k个节点数值之和最大的第一节点

输入数据（设为整型）建立单链表，并求相邻k个节点data值之和为最大的第一节点。例如输入k = 2，数据为2 6 4 7 3 #（#为结束符），建立下面链表，运行结果输出（序号3，data值4）：

image

c：

#include "stdio.h"
#include "malloc.h"
int sum;
int maxsum=0;
int count;
int k,k1;
int a1,a2;

typedef struct node
{
    int data,time;
    struct node *next;
}list,*List;
List Creatlist()
{
    List H,p,r;
    int a;
    H=(List)malloc(sizeof(list));
    r=H;
    printf("请输入整形数据，以空格隔开，#结束。\n");
    while((scanf("%d",&a))&&(a!='#')) 
    {
        p=(List)malloc(sizeof(list));
        p->data=a;
        p->time=count;
        count++;
        r->next=p;
        r=p;
    }
    r->next=NULL;
    return H;
}
List Adjmax(List H)
{
    List p,p1,q;
    p=H->next;
    if((p==NULL)||(count-1<k))
    {
        printf("输入错误！\n");
        return 0;
    }
    while (p)
    {
        k1 = k;
        sum = 0;
        p1 = p;
        while((k1--)&&(p1))
        {
            sum += p1->data;
            q = p1->next;
            p1 = q;
        }
        if(sum>maxsum)
        {
            a1=p->time;
            a2=p->data;
            maxsum=sum;
        }
        p=p->next;
    }
    printf("order:%d\ndata:%d\n",a1,a2);
    return 0;
}
int main()
{
    char ch;
    printf("求相邻k个节点数值之和最大的第一节点\nReady?Y/N   ");
    while(scanf("%c",&ch))
    {
        if(ch=='Y' || ch=='y')
        {
            count = 1;
            printf("请输入k值：   ");
            scanf("%d",&k);
            if(k==1 || k==2 || k==3 || k==4 || k==5 || k==6 || k==7 || k==8 || k==9)
                Adjmax(Creatlist());
            else
                printf("输入不合法\n");
            printf("Continue?Y/N   ");
            fflush(stdin);
        }
        else if(ch=='N' || ch=='n') break;
        else
            printf("输入不合法\n"); 
    }
    return 0;
}

java:

import java.util.Scanner;

/**
 *@author movis
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k;
        String data;
        String n;
        do {
            System.out.println("请输入k值：");
            data = in.next();
            while(!(data.equals("1")||data.equals("2")||data.equals("3")||data.equals("4")
                    ||data.equals("5")||data.equals("6")||data.equals("7")||data.equals("8")
                    ||data.equals("9"))) {
                System.out.println("输入k值不合法，请重新输入k值");
                data = in.next();
            }
            k = Integer.parseInt(data);
            
            System.out.println("请输入数据：");
            LinkedList list = new LinkedList();
            data = in.next();
            while(!data.equals("#")) {
                list.addNode(Integer.parseInt(data));
                data = in.next();
            }
            
            Adjmax(list, k);
            
            System.out.println("是否继续？请输入Y或N");
            n = in.next();
            while(!n.equals("Y") && !n.equals("N")) {
                System.out.println("输入值错误，请重新输入Y或N");
                n = in.next();
            }
        }while(n.equals("Y"));
        in.close();
    }
    
    public static void Adjmax(LinkedList list, int k) {
        int sum;
        int index;
        int data;
        int maxsum = 0;
        int finalindex = 0;
        int finaldata = 0;
        if(k > list.length()) {
            System.out.println("输入k值大于数据个数，错误！");
            return;
        }
        for(int i=0; i<=list.length()-k; i++) {
            sum = 0;
            index = 1;
            LinkedList.Node temp = list.head;
            data = temp.data;
            for(int n=i; n>0; n--) {
                temp = temp.next;
                data = temp.data;
                index++;
            }
            for(int j=k; j>0; j--) {
                sum += temp.data;
                temp = temp.next;
            }
            if(sum > maxsum) {
                maxsum = sum;
                finalindex = index;
                finaldata = data;
            }
        }
        System.out.println("序号为："+finalindex+"  data值为："+finaldata);
    }
}


/**
 *@author movis
 */
public class LinkedList {
    Node head = null;
    
    public class Node {
        int data;
        Node next = null;
        
        Node(int data) {
            this.data = data;
        }
    }
    
    public void addNode(int d) {
        Node newNode = new Node(d);
        if(head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while(temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
    
    public void printList() {
        Node tmp = head;
        while (tmp != null) {
            System.out.println(tmp.data);
            tmp = tmp.next;
        }
    }
    
    public int length() {
        int length = 0;
        Node tmp = head;
        while (tmp != null) {
            length++;
            tmp = tmp.next;
        }
        return length;
    }
    
}