链表的应用

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

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

一、 问题分析与算法思路

     首先将问题分解为3个步骤：数据输入—>数据处理—>结果输出。
     题目给定使用链表来保存整型数据，并且只需要求某个节点及其后面k-1个节点的和，所以采用单向非循环链表实现。
     然后分为3个模块来实现：

1. 主函数main()：
   a. 实现数据的输入。数据可以从键盘输入也可以从.txt文件输入。从键盘输入时要检查结束符“#”，当遇到结束符时结束此次输入，然后进行数据处理。如果从文件输入则首先判断该文件是否是.txt格式，如果不是则输出错误提示，选择重新输入或者退出程序。如果是.txt文件则进行文件读取，文件中的整型数据以空格符隔开，遇到结束符“#”时结束读取，若在遇到结束符之前遇到了非整型数据则输出错误提示，然后选择重新输入或者退出程序。
   b. 调用数据处理模块进行数据处理。输入数据建立链表后让用户输入k的值然后进行求解。
   c. 实现数据输出。输出当前操作的结果之后继续输出提示，让用户选择是继续对当前链表数据求相邻k个节点data值之和为最大的第一节点还是重新输入数据求相邻k个节点data值之和为最大的第一节点，亦或者是结束当前程序。
   d. 结束程序。当输出数据之后，在用户选择结束程序后，退出当前程序。

2. 建表函数：Creatlist()：
   建立一个表头为空的单向非循环链表，然后将输入数据依次存入链表。

3. 求值函数：Adjmax(L, k)：
   求值函数将从链表的第一个元素开始，一直遍历到第（LisLength（L）- k + 1）个元素，每次遍历都求出从该元素起到其后第k-1个元素止的k个元素的和，然后比较每个和的大小，返回和最大时的第一节点。求值函数在进行遍历求和比较时，不是每次都把第一个数与其后共k个数依次相加，而是采用“滑动窗口”式求和。如下图所示：
   当k=3时，从第一个节点data=2开始，计算连续3个节点和，为2+6+4=12。然后“窗口”向右移动一个节点，这时计算“窗口”内数据和时不再是遍历相加得到6+4+7=17了，而是利用上一次的和12减去上一个“窗口”的第一个数2，然后再加上当前“窗口”的最后一个数7，即12-2+7=17。这样每次计算和时，只需要做3个数的加减运算，而不再需要将“窗口”内的k个数依次遍历一遍求和了。

   

二、程序实现

     该程序给出了完整的提示：包括选择数据输入方式（键盘输入或者txt文件输入）提示，还有对错误输入时的提醒，比如文件选择方式错误，选择的文件类型错误等。在程序运行结束后还提供了是否继续进行操作的选择。
（该程序在Visual Studio 2015环境下测试通过）

/*
求相邻k个节点数值之和最大的第一节点
输入数据（设为整型）建立单链表，并求相邻k个节点data值之和为最大的第一节点。
例如输入k = 2，数据为2 6 4 7 3 #（#为结束符），建立下面链表，运行结果输出（序号3，data值4）
*/
#include <stdio.h>
#include <string.h>
#define FILEDIR_SIZE 200  //定义要输入的文件的目录的长度


typedef struct node
{
    int data;
    struct node *next;
}linknode,*link;

void Creatlink(link L); //  链表创建函数
void addTolink(link L, int key); //  链表添加函数
void Adjmax(link L, int k);  //查找函数
char * right(char *dst, char *src);   //字符串截取函数，用于判断输入的文件是否是txt类型
void release(link L);
int length = 0;  //链表的长度，用于判断k是否合法
void main()
{
    int k = 0;
    link List ;
    int  sel=1;  //选择是否继续
    List = (link)malloc(sizeof(linknode));
    List->next = NULL;
    while (sel==1)
    {
        int repeat = 1;
        release(List);              //链表创建之前先释放
        Creatlink(List);
        while (repeat == 1)
        {
            printf_s("Please input k:");
            scanf_s("%d", &k);
            Adjmax(List, k);
            printf_s("Continue to input k(input 1) or Exit(input 0):\n");
            scanf_s("%d", &repeat);
        }
        printf_s("Continue to input the link data(input 1) or Exit(input 0):\n");
        scanf_s("%d", &sel);
    }

}
void  Creatlink(link L)  //创建链表函数，数据可选择从键盘输入或者从文件读入，可复用
{
    char in[10];    //定义一个字符数组来保存输入的值
    char fsuffix[4] = "";  //存放文件后缀，判断是否是txt类型
    printf("-----Input from the keyboard(input \"K\") or the file(input \"F\")-----\n");    //提示用户：输入K代表从键盘输入数据，输入F则是从文件读取数据
    scanf_s("%s", in, 10);
    while (in[0] != 'K' && in[0] != 'F')    //如果用户输入的既不是K也不是F则提示用户重新输入
    {
        printf("Illegal input !!! please choose again......\n");
        scanf_s("%s", in, 10);
    }
    if (in[0] == 'F')    //如果选择的是文件输入
    {
        printf("Please input the absolute path of a txt file:\n");
        FILE *fp = NULL;    //保存用户指定输入的文件
        char fileDir[FILEDIR_SIZE];
        scanf_s("%s", fileDir, FILEDIR_SIZE);
        errno_t err;
        while ((err = fopen_s(&fp, fileDir, "r")) != 0 || strcmp(right(fsuffix, fileDir), "txt") != 0)  //如果打开不成功,或者打开的不是txt格式文件
        {
            printf("The file can't be found or the file type can't be allowed, please input again:\n");
            scanf_s("%s", fileDir, FILEDIR_SIZE);
        }
        int y = 0;
        while (EOF != fscanf_s(fp, "%d", &y))
        {
            addTolink(L, y);
        }
    }
    else if (in[0] == 'K')
    {
        printf("please start to input the link data, end with '#':\n");
        int x=0;
        char c='!';
        while (c != '#')
        {
            if(!scanf_s("%d", &x))
            scanf_s("%c", &c);
            else
                addTolink(L, x);
        }
    }
}
void addTolink(link L, int key)
{
    link  p=L, r;
        r = (link)malloc(sizeof(linknode));
        r->data = key;
        r->next = NULL;
        while (p->next)
        {
            p = p->next;
        }
        p->next = r;
        length++;
}

void Adjmax(link L, int k)
{
    if (!(k < length+1 && k>0))
    {
        printf_s("The k is illegal, please try again\n");
        return;
    }
    link result=NULL,r,p = L, q = L->next;   //result用于存放和最大的第一节点，r用于遍历求和
    int sum = -1;            //初始值为-1，防止result为空指针引发异常
    int sumt = 0;       //存放临时的和
    int order = 0;
    int ordert=0;   //记录临时序号
    for (int i = 0; i < k; i++)   //使p指向以q开头的连续k个节点序列的最后一个节点。q、p分别为“窗口”开始和结束
    {
        if(p->next)
        p = p->next;
    }
    while (p)
    {
        ordert++;

        if (ordert > 1)
        {
            sumt = sumt + p->data - q->data;     //滑动窗口法计算和
            q = q->next;
        }

        else
        {
            r = q;
            for (int j = 0; j < k; j++)     //计算连续k个数的和
            {
                sumt += r->data;
                r = r->next;
            }
        }
        if (sumt > sum)
        {
            sum = sumt;
            result = q;
            order = ordert;
        }

        p = p->next;  //先只移动尾指针p
    }
    printf_s("序号%d，data值%d\n",order,result->data);
}

void release(link L)   //链表释放函数
{
    if (L->next)
    {
        link q = L->next, p = L->next;
        while (q)
        {
            p = q;
            q = q->next;
            free(p);
        }
    }
    L->next = NULL;
}
char * right(char *dst, char *src)   //截取src的最后3位赋值给dst，用于判断文件名
{
    int n = 3;
    char *p = src;
    char *q = dst;
    int len = strlen(src);
    if (n>len) n = len;
    p += (len - n);   //从右边第n个字符开始，到0结束
    while (*(q++) = *(p++));
    return dst;
}

/*
void Adjmax(link L, int k)      //该函数运行时需注释掉，这个为普通算法，上面的为滑动窗口法
{
    if (!(k < length + 1 && k>0))
    {
        printf_s("The k is illegal, please try again\n");
        return;
    }
    link result = NULL, r, p = L, q = L->next;   //result用于存放和最大的第一节点，r用于遍历求和
    int sum = 0;
    int sumt = 0;       //存放临时的和
    int order = 0;
    int ordert = 0;   //记录临时序号
    for (int i = 0; i < k; i++)   //使p指向以q开头的连续k个节点序列的最后一个节点。q、p分别为“窗口”开始和结束
    {
        if (p->next)
            p = p->next;
    }
    while (p)
    {
        ordert++;
        {
            r = q;
            sumt = 0;
            for (int j = 0; j < k; j++)     //计算连续k个数的和
            {
                sumt += r->data;
                r = r->next;
            }
        }
        if (sumt > sum)
        {
            sum = sumt;
            result = q;
            order = ordert;
        }

        p = p->next;  //向后移动尾指针p和q
        q = q->next;
    }
    printf_s("序号%d，data值%d\n", order, result->data);
}
*/

三、结果分析

1. 测试思路：先选用键盘输入方式，然后开始输入一串数据，#结束，然后输入k的值，正确输出结果。然后选择仍用改组数据，但是用新的k进行计算。
       当新的k小于（在此为0）或大于边界（该测试是6，数据长度为5）时，提示错误，然后选择重新输入，输入正确时正确输出。
       然后不退出程序，选择重新从键盘输入测试数据。这时链表会进行清空重置。接下来的测试数据只有一个数，k只能为1，结果正确。
   

若测试输入的数据为0个，则k无有效值。

2. 算法和结果的有效性分析
      由普通算法实现所用平均时间约为5秒（数据规模为50000+，测试文件为138kB的txt文件。）
      普通算法的计算函数代码如下：

void Adjmax(link L, int k)
{
    if (!(k < length + 1 && k>0))
    {
        printf_s("The k is illegal, please try again\n");
        return;
    }
    link result = NULL, r, p = L, q = L->next;   //result用于存放和最大的第一节点，r用于遍历求和
    int sum = 0;
    int sumt = 0;       //存放临时的和
    int order = 0;
    int ordert = 0;   //记录临时序号
    for (int i = 0; i < k; i++)   //使p指向以q开头的连续k个节点序列的最后一个节点。q、p分别为“窗口”开始和结束
    {
        if (p->next)
            p = p->next;
    }
    while (p)
    {
        ordert++;
        {
            r = q;
            sumt = 0;
            for (int j = 0; j < k; j++)     //计算连续k个数的和
            {
                sumt += r->data;
                r = r->next;
            }
        }
        if (sumt > sum)
        {
            sum = sumt;
            result = q;
            order = ordert;
        }

        p = p->next;  //向后移动尾指针p和q
        q = q->next;
    }
    printf_s("序号%d，data值%d\n", order, result->data);
}

该算法的时间复杂度为O（n2）

若使用“滑动窗口”算法实现，平均使用时间约为<0.1秒。（没有测试更大数据集，因为大数据集会导致建立链表时间过长从而无法实现。）该算法代码见程序实现部分的void Adjmax(link L, int k)函数。

该函数的时间复杂度为O（n）。