数据结构实验(1)-线性表的应用

这是啥

《数据结构与数据库》这门课总是会布置一些实验和作业。老师说，我们的郭老师跟她说我们的C语言基础都非常好，所以老师就直接布置实验让我们做了。

这个基础对一部分同学也许是成立的，但是还是有很多同学根本没接触过C，所以很多同学在做实验的时候就很吃力，感觉无从下手。

我由于本身就比较喜欢编程，C语言学的也还行，所以想尽自己的力量帮助一下大家。为此我决定把我的代码都开源出来，让大家借鉴一下思路，并且欢迎大家找Bug，一起完善这个代码

目前不知道有多少次实验，先把这两次都给发出来吧。

先贴代码，过后会抽时间更新解题的思路，教会同学们如何设计一个程序。光看成品代码对大家的提升有限，授之以渔才是最好的。

题目描述

一元多项式在存储与运行的时候，一种常见的存储方法是根据最高项的幂次，按顺序生成数组。然而，当多项式比较稀疏的时候，大多数的存储空间被浪费在存储0系数的项中。因此，本实验采用链表的形式对多项式进行存储和运算，在节省空间的同时提高运算效率。

源代码

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <math.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1

typedef int status;

struct poly
{
    float coef;
    int expn;
    struct poly *next;
};

// 预定义函数
void intro();
status create(poly);
void show(struct poly);
int menu();
status add(poly, poly, poly);
status diff(poly, poly);
status integral(poly, poly);
status hasExpn(struct poly, int);
status insert(poly, poly);

int main()
{
    // 显示欢迎页面
    intro();

    // 定义变量
    struct poly polyns[5];
    int select;

    // 创建变量
    create(polyns);

    // 展示功能并获取选项
    select = menu();
    while(select!=4)
    {
        switch(select)
        {
        case 1:
            add(polyns, polyns+1, polyns+2);
            break;
        case 2:
            diff(polyns, polyns+3);
            break;
        case 3:
            integral(polyns, polyns+4);
            break;
        default:
            printf("谢谢使用，再见！\n");
            break;
        }
        select = menu();
    }

    return 0;
}

void intro()
{
    // 本函数用于展示程序一开始的页面，以及使用说明
    printf("**********************************\n");
    printf("*                                *\n");
    printf("*       一元多项式运算器         *\n");
    printf("*                                *\n");
    printf("**********************************\n\n");
    printf("本运算器可以实现一元多项式的创建、展示、求和、微分、不定积分\n");
    printf("在使用之前，请创建一元多项式：\n\n");
}

status create(struct poly *polyn)
{
    // 创建多项式，传入参数为头节点指针
    int num_poly;
    printf("********创建一元多项式************\n");
    printf("请依次输入每个多项式的系数和指数\n");
    printf("输入格式为：系数 指数。\n如想输入 2.5X^5,则输入 2.5 5 再按一下回车\n");
    printf("\n在输入之前，请问您想输入几个项？\n");
    scanf("%d", &num_poly);
    printf("您将输入%d个项目，已为您分配好空间\n", num_poly);
    printf("请开始您的输入：\n");

    // 初始化头节点
    polyn->coef = 0;
    polyn->expn = -1;
    polyn->next = NULL;

    // 开始正式输入
    float coef;
    int expn;
    for(int i=0; i<num_poly; i++)
    {
        scanf("%f %d", &coef, &expn);
        // 查找当前列表里是否有这一项，没有就插入
        if(!hasExpn(*polyn, expn))
        {
            // 分配空间
            struct poly *new_polyn = (struct poly *)malloc(sizeof(struct poly));
            new_polyn->coef = coef;
            new_polyn->expn = expn;
            // 按照递增顺序 插入到链表里
            insert(polyn, new_polyn);
            if(i!=num_poly-1)
            {
                printf("添加成功，请继续输入下一项：\n");
            }
        }
        else
        {
            printf("添加失败，可能是因为输入了重复的指数项，请继续输入下一项：\n");
        }
    }

    // 展示输入的结果
    printf("多项式创建成功！您创建的多项式为：\n");
    show(*polyn);
    printf("\n");
    return OK;
}

status hasExpn(struct poly polyn, int expn)
{
    // 查找当前链表里面有没有这一指数项
    struct poly *p = &polyn;

    while(p != NULL)
    {
        if(p->expn == expn)
        {
            // 如果找到了就返回TRUE
            return TRUE;
        }
        else
        {
            p = p->next;
        }
    }

    return FALSE;
}

status insert(struct poly *polyn, struct poly *new_poly)
{
    // 按照递减顺序插入新多项式
    struct poly *p = polyn;
    while(p->next != NULL)
    {
        if(new_poly->expn > p->next->expn)
        {
            // 可以插入了
            break;
        }
        else
        {
            p = p->next;
        }
    }
    // 插入
    new_poly->next = p->next;
    p->next = new_poly;

    return OK;
}


void show(struct poly polyn)
{
    // 用于展示多项式
    struct poly *p = &polyn;
    struct poly *p_diff = &polyn;

    // 上来就判断微分的时候是不是全部系数都为0
    int coef_all_zero = 1;
    p_diff = p_diff->next;
    while(p_diff != NULL)
    {
        if(!fabs(p_diff->coef)<0.000001)
        {
            // 如果有一个不是0，falg就取消
            coef_all_zero = 0;
        }
        p_diff = p_diff->next;
    }

    // 如果系数都为0，就输出0，否则再谈
    if(coef_all_zero)
    {
        printf("0.0");
    }
    else
    {
        p = p->next; //头节点不输出
        if(p == NULL)
        {
            // 当加起来为0的时候，就显示0
            printf("0.0");
        }
        while(p != NULL)
        {
            // 考虑到+号的问题
            if(p->next == NULL)
            {
                // 即最后一项
                if(fabs(p->coef)<0.000001)
                {
                    // 系数为0，直接不输出
                    break;
                }
                else if(p->expn == 0)
                {
                    // 指数为0，就不显示X项
                    printf("+ %.1f", p->coef);
                }
                else if(p == polyn.next)
                {
                    // 当只有一项的时候，既是最后一项又是第一项
                    printf("%.1fX^%d", p->coef, p->expn);
                }
                else
                {
                    printf("+ %.1fX^%d", p->coef, p->expn);
                }
            }
            else if (fabs(p->next->coef)<0.000001 || p->next->next == NULL)
            {
                // 如果下一项系数为0了，那后面应该都没有，所以就不写+了
                // 或者当是倒数第二个的时候也是
                if(fabs(p->coef)<0.000001)
                {
                    // 系数为0，直接不输出
                    break;
                }
                else if(p->expn == 0)
                {
                    // 指数为0，就不显示X项
                    printf("%.1f ", p->coef);
                }
                else
                {
                    printf("%.1fX^%d ", p->coef, p->expn);
                }
            }
            else
            {
                if(fabs(p->coef)<0.000001)
                {
                    // 系数为0，直接不输出
                    continue;
                }
                else if(p->expn == 0)
                {
                    // 指数为0，就不显示X项
                    printf("%.1f + ", p->coef);
                }
                else
                {
                    printf("%.1fX^%d + ", p->coef, p->expn);
                }
            }
            p = p->next;
        }
    }
}


int menu()
{
    // 用于展示菜单
    printf("\n现在您可以进行以下操作：\n");
    printf("1\t多项式加法\n");
    printf("2\t多项式微分\n");
    printf("3\t多项式不定积分\n");
    printf("4\t退出系统\n");
    printf("请输入您想做的功能的序号，并按回车键：\n");
    // 获取输入
    int select;
    scanf("%d", &select);

    return select;
}


status add(struct poly *add1, struct poly *add2, struct poly *sum)
{
    // 用于多项式的相加，如果使用相加功能，需要新输入一个多项式
    printf("\n********一元多项式的相加************\n\n");
    printf("欢迎使用多项式相加功能，在使用之前，需要前创建一个新的多项式：\n");
    create(add2);

    // 创建完毕，开始添加
    // 初始化sum的头节点
    sum->coef = 0;
    sum->expn = -1;
    sum->next = NULL;

    // 定义指针和变量
    struct poly *head_sum = sum;
    struct poly *p1 = add1->next;
    struct poly *p2 = add2->next;
    float coef_sum;

    // 开始比较并插入
    // 注意：由于就地合并会破坏原始多项式，但是后来还需要微分等操作
    // 所以我们采用新生成一个新的sum多项式，每次都生成一个新节点
    while(p1 && p2)
    {
        if(p1->expn > p2->expn)
        {
            struct poly *new_polyn = (struct poly *)malloc(sizeof(struct poly));
            new_polyn->coef = p1->coef;
            new_polyn->expn = p1->expn;
            sum->next = new_polyn;
            p1 = p1->next;
            sum = sum->next;
        }
        else if(p1->expn < p2->expn)
        {
            struct poly *new_polyn = (struct poly *)malloc(sizeof(struct poly));
            new_polyn->coef = p2->coef;
            new_polyn->expn = p2->expn;
            sum->next = new_polyn;
            p2 = p2->next;
            sum = sum->next;
        }
        else
        {
            coef_sum = p1->coef + p2->coef;
            if(!(fabs(coef_sum) < 0.000001))
            {
                // 因为是浮点数，所以不能直接==0
                // 生成一个新节点，给接上去
                struct poly *new_polyn = (struct poly *)malloc(sizeof(struct poly));
                new_polyn->coef = coef_sum;
                new_polyn->expn = p1->expn;
                new_polyn->next = p1->next;
                sum->next = new_polyn;
                sum = sum->next;
            }
            else
            {
                // 和为0,也不删节点，直接走一步
                printf("出现了相加之后系数为0的情况，系统将为您消去该项\n");
            }
            // p1 p2 各自往前走一步（因为p1待会还有用，所以不释放空间
            p1 = p1->next;
            p2 = p2->next;
        }

    }
    // 链接剩余节点
    struct poly *p_res = p1 ? p1 : p2;
    while(p_res)
    {
        struct poly *new_polyn = (struct poly *)malloc(sizeof(struct poly));
        new_polyn->coef = p_res->coef;
        new_polyn->expn = p_res->expn;
        sum->next = new_polyn;
        p_res = p_res->next;
        sum = sum->next;
    }
    // 定义一下尾节点
    sum->next = NULL;

    // 展示结果
    printf("\n计算完成！\n");
    show(*add1);
    printf(" 与 ");
    show(*add2);
    printf(" 的和为：\n\n");
    show(*head_sum);
    printf("\n");

    return OK;
}

status diff(struct poly *raw, struct poly *diff_res)
{
    // 用于实现微分
    // 微分就是直接对每一项开始操作就行了
    printf("\n********一元多项式的微分************\n\n");
    printf("本功能支持高阶微分，请问您需要微分几次？请输入一个整数并按回车\n");
    int num_diff;
    scanf("%d", &num_diff);

    // 初始化头节点
    diff_res->coef = 0;
    diff_res->expn = -1;
    diff_res->next = NULL;

    // 定义变量
    struct poly *head_diff = diff_res;
    struct poly *p = raw->next;

    for(int i=0; i<num_diff; i++)
    {
        while(p)
        {
            // 对每一个都进行操作
            if(p->expn == 0)
            {
                // 0阶的求导为0，直接不管就行
                struct poly *new_polyn = (struct poly *)malloc(sizeof(struct poly));
                new_polyn->coef = p->coef * p->expn;
                new_polyn->expn = p->expn;
                diff_res->next = new_polyn;
                diff_res = diff_res->next;
            }
            else
            {
                struct poly *new_polyn = (struct poly *)malloc(sizeof(struct poly));
                new_polyn->coef = p->coef * p->expn;
                new_polyn->expn = p->expn -1;
                diff_res->next = new_polyn;
                diff_res = diff_res->next;
            }
            p = p->next;
        }
        // 完善最后一项
        diff_res->next = NULL;
        // 把要微分的变成自己，实现高阶微分
        p = head_diff->next;
        diff_res = head_diff;
    }

    // 展示结果
    printf("\n计算完成！\n");
    show(*raw);
    printf(" 的 %d 阶微分为：\n\n", num_diff);
    show(*head_diff);
    printf("\n");

    return OK;
}

status integral(struct poly *raw, struct poly *int_res)
{
    // 用于实现不定积分
    // 微分就是直接对每一项开始操作就行了
    printf("\n********一元多项式的不定积分************\n\n");

    // 初始化头节点
    int_res->coef = 0;
    int_res->expn = -1;
    int_res->next = NULL;

    // 定义变量
    struct poly *head_int = int_res;
    struct poly *p = raw->next;

    while(p)
    {
        // 对每一个都进行操作
        struct poly *new_polyn = (struct poly *)malloc(sizeof(struct poly));
        new_polyn->coef = p->coef / (p->expn + 1.0);
        new_polyn->expn = p->expn + 1;
        int_res->next = new_polyn;
        int_res = int_res->next;
        p = p->next;
    }
    // 完善最后一项
    int_res->next = NULL;

    // 展示结果
    printf("\n计算完成！\n");
    show(*raw);
    printf(" 的不定积分为：\n\n");
    show(*head_int);
    printf(" + C");
    printf("\n");

    return OK;
}