数据结构课程设计___一元稀疏多项式计算器(报告+代码)__完整版

时间:2024.3.23

 

数据结构课程设计

20##年 7  月 14  日


目录

一、   课程题目………………………………………………………1

二、   需求分析………………………………………………………1

三、   测试数据………………………………………………………2

四、   概要设计………………………………………………………2

五、   调用关系图……………………………………………………3

六、   程序代码………………………………………………………3

七、   心得体会及总结………………………………………………12

数据结构课程设计

一、课程题目

      一元稀疏多项式计算器

二、需求分析

1、一元稀疏多项式简单计算器的功能是:

1.1 输入并建立多项式;

1.2 输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,………cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列;

1.3 求多项式a、b的导函数;

1.4 计算多项式在x处的值;

1.5多项式a和b相加,建立多项式a+b;

1.6 多项式a和b相减,建立多项式a-b。

2、设计思路:

2.1 定义线性表的动态分配顺序存储结构;

2.2 建立多项式存储结构,定义指针*next

2.3利用链表实现队列的构造。每次输入一项的系数和指数,可以输出构造的一元多项式

2.4演示程序以用户和计算机的对话方式执行,即在计算机终站上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运行命令;最后根据相应的输入数据(滤去输入中的非法字符)建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为:c1x^e1+c2x^e2+…+cnx^en

3、设计思路分析

要解决多项式相加,必须要有多项式,所以必须首先建立两个多项式,在这里采用链表的方式存储链表,所以我将结点结构体定义为

运用尾插法建立两条单链表,以单链表polyn p和polyn h分别表示两个一元多项式a和b,a+b的求和运算等同于单链表的插入问题(将单链表polyn p中的结点插入到单链表polyn h中),因此“和多项式”中的结点无须另生成。

为了实现处理,设p、q分别指向单链表polya和polyb的当前项,比较p、q结点的指数项,由此得到下列运算规则:

① 若p->expn<q->expn,则结点p所指的结点应是“和多项式”中的一项,令指针p后移。

② 若p->expn=q->expn,则将两个结点中的系数相加,当和不为0时修改结点p的系数。

③ 若p->expn>q->expn,则结点q所指的结点应是“和多项式”中的一项,将结点q插入在结点p之前,且令指针q在原来的链表上后移。

三、测试数据:

1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);

2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15

)=(-7.8x^15-1.2x^9+12x^-3-x);

3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);

4、(x+x^3)+(-x-x^3)=0;

5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);

6、(x+x^2+x^3)+0=x+x^2+x^3.

四、概要设计

   1、元素类型、结点类型和指针类型:

typedef struct Polynomial{

           float               coef;     //系数

           int                 expn;     //指数

       struct Polynomial  *next;

}*Polyn,Polynomial;

2、建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点:

 Polyn CreatePolyn(Polyn head,int m){

          int     i;

          Polyn   p;

    p=head=(Polyn)malloc(sizeof(struct Polynomial));

    head->next=NULL;

    for(i=0;i<m;i++)

    {

        p=(Polyn)malloc(sizeof(struct Polynomial)); 

        printf("请输入第%d项的系数与指数:",i+1);

        scanf("%f %d",&p->coef,&p->expn);

        Insert(p,head);                             

    }

    return head;

}

3、主函数和其他函数:

void main()

{

            int   m,n,a,x;

            char  flag;

            Polyn pa=0,pb=0,pc;

}

float ValuePolyn(Polyn head,int x) //输入x值,计算并返回多项式的值

五、调用关系图(图1)

六、程序代码:

#include<stdio.h>

#include<stdlib.h>                //定义多项式的项

typedef struct Polynomial{

    float               coef;     //系数

    int                 expn;     //指数

    struct Polynomial  *next;

}*Polyn,Polynomial;

void Insert(Polyn p,Polyn h){    

    if(p->coef==0) free(p);       //系数为0的话释放结点

    else

    {

        Polyn q1,q2;

        q1=h;

       q2=h->next;

        while(q2&& p->expn < q2->expn)

       {                        //查找插入位置

            q1=q2;

            q2=q2->next;

       }

        if(q2&& p->expn == q2->expn)

       {                        //将指数相同相合并

            q2->coef += p->coef;

            free(p);

            if(!q2->coef)

           {                    //系数为0的话释放结点

                q1->next=q2->next;

                free(q2);

           }

       }

        else

       {                       //指数为新时将结点插入

            p->next=q2;

            q1->next=p;

       }

    }

}

Polyn CreatePolyn(Polyn head,int m){                 //建立一个头指针为head、项数为m的一元多项式

    int     i;

    Polyn   p;

    p=head=(Polyn)malloc(sizeof(struct Polynomial));

    head->next=NULL;

    for(i=0;i<m;i++)

    {

        p=(Polyn)malloc(sizeof(struct Polynomial));  //建立新结点以接收数据

        printf("请输入第%d项的系数与指数:",i+1);

        scanf("%f %d",&p->coef,&p->expn);

        Insert(p,head);                              //调用Insert函数插入结点

    }

    return head;

}

void DestroyPolyn(Polyn p){                          //销毁多项式p

    Polyn q1,q2;

    q1=p->next;

    q2=q1->next;

    while(q1->next)

    {

        free(q1);

        q1=q2;

        q2=q2->next;

    }

}

void PrintPolyn(Polyn P){

    Polyn q=P->next;

    int flag=1;                  //项数计数器

    if(!q)

    {                            //若多项式为空,输出0

        putchar('0');

        printf("\n");

        return;

    }  

    while(q)

    {

        if(q->coef>0&& flag!=1) putchar('+');    //系数大于0且不是第一项

        if(q->coef!=1&&q->coef!=-1)

       {                                       //系数非1或-1的普通情况

            printf("%g",q->coef);

            if(q->expn==1) putchar('X');

            else if(q->expn) printf("X^%d",q->expn);

       }

        else

       {

            if(q->coef==1)

           {

                if(!q->expn) putchar('1');

                else if(q->expn==1) putchar('X');

                else printf("X^%d",q->expn);

           }

            if(q->coef==-1)

           {

                if(!q->expn) printf("-1");

                else if(q->expn==1) printf("-X");

                else printf("-X^%d",q->expn);

           }

       }

        q=q->next;

        flag++;

    }

    printf("\n");

}

int compare(Polyn a,Polyn b){

    if(a&&b)

    {

        if(!b||a->expn>b->expn) return 1;

        else if(!a||a->expn<b->expn) return -1;

        else return 0;

    }

    else if(!a&&b) return -1;                    //a多项式已空,但b多项式非空

    else return 1;                               //b多项式已空,但a多项式非空

}

Polyn AddPolyn(Polyn pa,Polyn pb){               //求解并建立多项式a+b,返回其头指针

    Polyn qa=pa->next;

    Polyn qb=pb->next;

    Polyn headc,hc,qc;

    hc=(Polyn)malloc(sizeof(struct Polynomial)); //建立头结点

    hc->next=NULL;

    headc=hc;

    while(qa||qb)

    {

        qc=(Polyn)malloc(sizeof(struct Polynomial));

        switch(compare(qa,qb)){

        case 1:

           {

                qc->coef=qa->coef;

                qc->expn=qa->expn;

                qa=qa->next;

                break;

           }

        case 0:

           {

                qc->coef=qa->coef+qb->coef;

                qc->expn=qa->expn;

                qa=qa->next;

                qb=qb->next;

                break;

           }

        case -1:

           {

                qc->coef=qb->coef;

                qc->expn=qb->expn;

                qb=qb->next;

                break;

           }

       }

        if(qc->coef!=0)

       {

            qc->next=hc->next;

            hc->next=qc;

            hc=qc;

       }

    else free(qc);                               //当相加系数为0时,释放该结点

    }

    return headc;

}

Polyn SubtractPolyn(Polyn pa,Polyn pb){         //求解并建立多项式a-b,返回其头指针

    Polyn h=pb;

    Polyn p=pb->next;

    Polyn pd;

    while(p)

    {                                           //将pb的系数取反

        p->coef*=-1;

        p=p->next;

    }

    pd=AddPolyn(pa,h);

    for(p=h->next;p;p=p->next)                   //恢复pb的系数

        p->coef*=-1;

    return pd;

}

float ValuePolyn(Polyn head,int x){                //输入x值,计算并返回多项式的值

    Polyn p;

    int i,t;

    float sum=0;

    for(p=head->next;p;p=p->next)

    {

        t=1;

        for(i=p->expn;i!=0;)

       {

            if(i<0){t/=x;i++;}              //指数小于0,进行除法

            else{t*=x;i--;}                 //指数大于0,进行乘法

       }

        sum+=p->coef*t;

    }

    return sum;

}

Polyn Derivative(Polyn head){               //求解并建立导函数多项式,并返回其头指针

    Polyn q=head->next,p1,p2,hd;

    hd=p1=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点

    hd->next=NULL;

    while(q)

    {

        if(q->expn!=0)

       {                                  //该项不是常数项时

            p2=(Polyn)malloc(sizeof(struct Polynomial));

            p2->coef=q->coef*q->expn;

            p2->expn=q->expn-1;

            p2->next=p1->next;            //连接结点

            p1->next=p2;

            p1=p2;

       }

        q=q->next;

    }

    return hd;

}

Polyn MultiplyPolyn(Polyn pa,Polyn pb){   //求解并建立多项式a*b,返回其头指针

    Polyn hf,pf;

    Polyn qa=pa->next;

    Polyn qb=pb->next;

    hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点

    hf->next=NULL;

    for(;qa;qa=qa->next)

    {

        for(qb=pb->next;qb;qb=qb->next)

       {

            pf=(Polyn)malloc(sizeof(struct Polynomial));

            pf->coef=qa->coef*qb->coef;

            pf->expn=qa->expn+qb->expn;

            Insert(pf,hf);                    //调用Insert函数以合并指数相同的项

       }

    }

    return hf;

}

void main()

{

    int   m,n,a,x;

    char  flag;

    Polyn pa=0,pb=0,pc;

    printf("      --------------------------------------------------\n");

    printf("    |  ***班      ***       ********          |\n");

    printf("      --------------------------------------------------\n");

    printf("                 欢迎使用多项式操作程序\n");

    printf("请输入a的项数:");

    scanf("%d",&m);

    pa=CreatePolyn(pa,m);                      //建立多项式a

    printf("请输入b的项数:");

    scanf("%d",&n);

    pb=CreatePolyn(pb,n);                     //建立多项式b

    //输出菜单

printf("    **************************************************\n");

  printf("    *              多项式操作程序                    *\n");

printf("    *                                                *\n");

    printf("   *     A:输出多项式a        B:输出多项式b        *\n");

    printf("   *                                                *\n");

    printf("   *     C:输出a的导数        D:输出b的导数       *\n");

    printf("   *                                                *\n");

    printf("   *     E:代入x的值计算a     F:代入x的值计算b   *\n");

    printf("   *                                                *\n");

    printf("   *     G:输出a+b             H:输出a-b           *\n");

    printf("   *                                                *\n");

    printf("   *     I:输出a*b             J:退出程序          *\n");

    printf("   *                                                *\n");

    printf("   *************************************************\n");

    while(a)

    {

        printf("\n请选择操作:");

        scanf(" %c",&flag);       

       switch(flag)

       {

           case'A':

           case'a':

              {

                   printf("\n       多项式a=");

                   PrintPolyn(pa);

                  break;

              }

           case'B':

           case'b':

              {

                  printf("\n       多项式b=");

                  PrintPolyn(pb);

                  break;

              }

            case'C':

            case'c':

              {

                 pc=Derivative(pa);

                 printf("\n       多项式a的导函数为:a'=");

                  PrintPolyn(pc);

                  break;

              }

            case'D':

           case'd':

              {

                  pc=Derivative(pb);

                  printf("\n       多项式b的导函数为:b'=");

                  PrintPolyn(pc);

                  break;

              }

            case'E':

           case'e':

              {

                  printf("输入x的值:x=");

                  scanf("%d",&x);

                  printf("\n       x=%d时,a=%.3f\n",x,ValuePolyn(pa,x));

                  break;

              }

            case'F':

           case'f':

              {

                  printf("输入x的值:x=");

                  scanf("%d",&x);

                  printf("\n       x=%d时,b=%.3f\n",x,ValuePolyn(pb,x));

                  break;

              }

           case'G':

           case'g':

              {

                  pc=AddPolyn(pa,pb);

                    printf("\n       a+b=");

                  PrintPolyn(pc);

                  break;

              }

            case'H':

           case'h':

              {

                  pc=SubtractPolyn(pa,pb);

                    printf("\n       a-b=");

                  PrintPolyn(pc);

                  break;

              }

            case'I':

           case'i':

              {

                  pc=MultiplyPolyn(pa,pb);

                    printf("\n      a*b=");

                  PrintPolyn(pc);

                  break;

              }

           case'J':

           case'j':

              {

                  printf("\n       感谢使用此程序!\n");

                  DestroyPolyn(pa);

                  DestroyPolyn(pb);

                   a=0;

                  break;

              }

            default:

              printf("\n       您的选择错误,请重新选择!\n");

       }

    }

}

七、心得体会及总结

    通过这次课程设计,我感觉到要真正做出一个程序并不很容易,但只要用心去做,总会有收获,特别是当我遇到问题,与同学互相探讨,想尽办法去解决,最后终于找到方法时,心里的那份喜悦之情真是难以形容.编写程序中遇到问题再所难免,应耐心探究其中的原因,从出现问题的地方起,并联系前后程序,仔细推敲,逐个排查.直到最终搞清为止。
    对于数据结构有了更深层次的理解,循环队列中对边界条件的处理,满足什么条件为队满,满足什么条件为队空。

更多相关推荐:
数据结构课程设计报告模板

课程设计说明书课程名称:数据结构与算法专业:计算机科学与技术班级:103013姓名:XXX学号:03指导教师:XXX完成日期:20XX年1月12日任务书题目:黑白棋系统设计内容及要求:1.课程设计任务内容通过玩…

数据结构课程设计报告(含代码)

西安郵電學院数据结构课程设计报告题目校园导航系统院系名称计算机学院专业名称计算机科学与技术班级学生姓名学号8位指导教师设计起止时间20xx年12月11日20xx年12月15日一设计目的1通过本次课程设计巩固数据...

《数据结构课程设计报告》

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称课题名称用三元组实现稀疏矩阵的转置相加相乘专业计算机科学与技术班级学号AA姓名AAA联系方式136XXXXXXXX指导教师武彬20年月日目录1数据结构课程设...

数据结构课程设计报告

扬州大学信息工程学院数据结构课程设计报告题目井字棋小游戏班级学号姓名指导教师一课程题目井字棋小游戏二需求分析计算机和人对弈问题计算机之所以能和人对弈是因为有人将对弈的策略事先已存入计算机由于对弈的过程是在一定规...

数据结构课程设计报告(模版)

攀枝花学院学生课程设计论文题目学生姓名学号20xx108010所在院系数学与计算机学院专业计算机科学与技术专业班级20xx级计算机科学与技术1班指导教师蒋斌职称讲师20xx年12月19日数据结构课程设计任务书攀...

数据结构课程设计报告

数据结构课程设计报告撰写要求一纸张与页面要求1采用国际标准A4型打印纸或复印纸纵向打印2封页和页面按照下面模板书写正文为小四宋体15倍行距3图表及图表标题按照模板中的表示书写二课设报告书的内容应包括以下各个部分...

数据结构课程设计报告

CENTRALSOUTHUNIVERSITY数据结构课程设计报告题目学生姓名指导教师学院专业班级完成时间交通旅游图的最短路径问题摘要数据结构主要是一门研究非数值计算的程序设计问题中的计算机操作对象以及它们之间的...

20xx数据结构课程设计报告

沈阳航空航天大学课程设计报告课程设计名称:数据结构课程设计课程设计题目:树与二叉树转换院(系):专业:班级:学号:姓名:指导教师:完成日期:目录第1章题目内容与要求...11基本功能...12功能分解...1第…

数据结构课程设计报告(盐城工学院)

数据结构课程设计深度与广度优先搜索迷宫问题专班学业级号软件工程B软件1211210701128学生姓名数据结构课程设计深度与广度优先搜索迷宫问题目录1设计题目12设计分析13设计实现34测试方法341测试目的8...

数据结构课程设计报告 二叉树

淮阴工学院Project1课程设计报告选题名称二叉排序树用顺序表结构存储系院计算机工程学院专业软件工程班级软件1092姓名单重阳学号指导教师殷路张亚红张勇军冯万利学年学期20xx20xx学年第1学期设计任务书摘...

数据结构课程设计报告

一题目奇数阶幻方求解问题描述幻方是一种很有意思的数字矩阵在很早著名的九宫八卦阵就与幻方有关幻方的定义为1到NN的整数填入NN的方格中每行和每列以及对角线的数字之和必须是相等的你作为八卦公司的顶级程序员现在需要你...

数据结构课程设计报告(c++)

数据结构课程设计报告题目2用无序的顺序表实现一个城市数据库专业班级112学号20xx41404207姓名符日富同组人员吴为密周金驰邱李棚一课程设计的内容要求2用无序的顺序表实现一个城市数据库每条数据库记录包括城...

数据结构课程设计报告(34篇)