Question

数据结构实习报告怎么做

Answer 1

　　其实书上就有的，清华大学严蔚敏编的那本，我这有不是很成熟的一个，仅供借鉴
　　题目:一元稀疏多项式计算器
　　班级:0307XX班
　　姓名:XXX
　　学号:0307XXXX
　　完成日期:2009-5-9

　　一、需求分析
　　(1) 输入的形式和输入值的范围
　　输入的形式: 先输入两个多项式的项数n;
　　然后从第1项开始,分别输入多项式各项的系数和指数;:
　　(先输入系数，后输入指数):
　　输入想要做的多项式运算类型:
　　输入值的范围:多项式各项的系数没有特殊要求,但是指数应该为正数

　　(2) 输出的形式
　　程序会自动输出两个一元稀疏多项式(序列按指数升序排列)
　　根据所选择的多项式运算类型,做出相应的数学运算,并且输出运算结果:一元稀疏多项式 (序列按指数降序排列)

　　(3) 程序功能
　　多项式的基本运算类型:加法、减法、乘法

　　(4) 测试数据
　　(见测试结果)

　　二、概要设计
　　抽象数据类型的定义

　　typedef struct LNode
　　{
　　float coef;
　　int expn;
　　LNode* next;
　　}term, *link;
　　typedef struct
　　{
　　link head,tail;
　　int len;
　　}polynomial,* Lpoly;

　　三、详细设计
　　建一个空的表
　　int InitList( polynomial &p) //建一个空的表
　　{

　　link h;
　　h=(link)malloc(sizeof(term));
　　if(!h)
　　return ERROR;
　　p.head=p.tail=h;
　　h->next=NULL;
　　p.len=0;
　　return 1;
　　}

　　判断是否有指数相同的节点
　　link LocateElem(polynomial p,term e) //判断是否有指数相同的节点
　　{
　　link ha;
　　ha=p.head->next;
　　int n=p.len;
　　while(n)
　　{
　　if(e.expn==ha->expn)
　　return ha;
　　ha=ha->next;
　　n--;
　　}
　　return 0;
　　}

　　判断第一个比e大的节点
　　link LocateElem2(polynomial p,term e) //判断第一个比e大的节点
　　{
　　link ha;
　　ha=p.head;
　　int n=p.len;
　　while(n)
　　{
　　if(e.expn<ha->next->expn)
　　return ha;
　　ha=ha->next;
　　n--;
　　}
　　return 0;
　　}

　　产生值为e的节点
　　int MakeNode(link& p,term e) //产生值为e的节点
　　{
　　p=(link)malloc(sizeof(term));
　　if(!p)
　　return ERROR;
　　p->coef=e.coef;
　　p->expn=e.expn;
　　return 1;
　　}

　　按照指数从小到大次序建立一个多项式链表
　　void CreatPolyn(polynomial& p,int m) //按照指数从小到大次序建立一个多项式链表
　　{
　　InitList(p);
　　link h=p.head,s,t1,t2; //h为中间的结点的位置指针
　　h->coef=0.0;
　　h->expn=-1;
　　term e;
　　cout<<"请输入p的系数和指数:"<<endl;
　　for(int i=1;i<=m;i++)
　　{
　　cin>>e.coef>>e.expn;
　　t1=LocateElem(p,e);
　　t2=LocateElem2(p,e);
　　if(!t1) //判断是否有指数相同的结点
　　{
　　if(MakeNode(s,e)) //是为产生结点的指针
　　{
　　if(!t2) //使新的节点按指数的顺序插入链表中
　　{
　　h->next=s;
　　h=h->next;
　　h->next=NULL;
　　p.len++;
　　}
　　else
　　{
　　s->next=t2->next;
　　t2->next=s;
　　p.len++;
　　}
　　}
　　}
　　else
　　{
　　t1->coef+=e.coef; //指数相同的话就直接在相同指数的节点上加上e的系数
　　}
　　}
　　p.tail=h;

　　}

　　输出一元稀疏多项式 (序列按指数升序排列)
　　void PrintPolyn(polynomial p)
　　{

　　cout<<"该一元稀疏多项式输出即为(序列按指数升序排列):"<<endl;
　　link q=p.head->next;

　　for (int i = 1;i <= p.len;i++,q = q->next)
　　{

　　if (q->coef == 0.0) //系数为 0,该项无需打印
　　continue;
　　if (q->coef > 0.0 && i != 1) // 系数为正数,且不是第一项时，打印" + "号
　　cout<<"+";
　　if (q->coef != 1.0) //系数非 1 时，需要打印出系数
　　cout<<q->coef;
　　if (q->expn !=0) //指数非 0 时，需要打印出指数
　　cout<<"X^"<<q->expn;
　　}

　　cout<<endl<<endl<<endl;
　　}

　　比较节点的指数大小
　　int CmpPolynExpn(link pa,link pb) //比较节点的指数大小
　　{
　　if(pa->expn>pb->expn)
　　return 1;
　　if(pa->expn==pb->expn)
　　return 0;
　　if(pa->expn<pb->expn)
　　return -1;
　　}

　　去掉h后面的节点q返回地址
　　int DelFirst(link h,link& q) //去掉h后面的节点q返回地址
　　{
　　q=h->next;
　　if(!q) //h为尾节点则报错
　　return ERROR;
　　h->next=h->next->next;
　　return 1;
　　}

　　多项式的长度计算
　　void LenPolyn(polynomial& p) //多项式的长度计算
　　{
　　link pa=p.head;
　　int i=0;
　　while(pa->next!=0)
　　{
　　i++;
　　pa=pa->next;
　　}
　　p.len=i;
　　}

　　多项式加法
　　polynomial AddPolyn(polynomial& pa,polynomial& pb) //多项式加法
　　{
　　polynomial c;
　　InitList(c);
　　link hc=c.head,ha=pa.head,hb=pb.head; //qa qb 为当前操作的结点的指针 ha hb为qa qb的上一个结点的指针
　　link qc=hc,qa=ha->next,qb=hb->next;

　　while(qa&&qb)
　　{
　　switch(CmpPolynExpn(qa,qb)) //-1 表示a中的小 0 表示一样大 1 表示b的小
　　{
　　case -1:
　　qc->next=qa;
　　qc=qa;
　　ha=qa;
　　qa=qa->next;
　　break;
　　case 0:
　　qa->coef+=qb->coef;
　　if(qa->coef==0) //当系数我0时候将节点free掉
　　{
　　DelFirst(ha,qa);
　　free(qa);
　　DelFirst(hb,qb);
　　free(qb);
　　qa=ha->next;qb=hb->next;
　　}
　　else
　　{
　　qc->next=qa;
　　qc=qa;
　　qa=qa->next;qb=qb->next;
　　}

　　break;
　　case 1:
　　qc->next=qb;
　　qc=qb;
　　hb=qb;
　　qb=qb->next;

　　break;
　　}
　　}

　　if(!qa) //将剩余的结点导入c中
　　{
　　qc->next=qb;
　　c.tail=pb.tail;

　　}
　　else
　　{
　　qc->next=qa;
　　c.tail=pa.tail;
　　}
　　LenPolyn(c);
　　return c;
　　}

　　多项式减法
　　polynomial SubPolyn(polynomial& pa,polynomial& pb) //多项式减法
　　{
　　polynomial c1;
　　InitList(c1);
　　link hc=c1.head,ha=pa.head,hb=pb.head;
　　link qc=hc,qa=ha->next,qb=hb->next;

　　while(qa&&qb)
　　{
　　switch(CmpPolynExpn(qa,qb))
　　{
　　case -1:
　　qc->next=qa;
　　qc=qa;
　　ha=qa;
　　qa=qa->next;
　　break;
　　case 0:
　　qa->coef=abs(qa->coef-qb->coef);
　　if(qa->coef==0)
　　{
　　DelFirst(ha,qa);
　　free(qa);
　　DelFirst(hb,qb);
　　free(qb);
　　qa=ha->next;qb=hb->next;
　　}
　　else
　　{
　　qc->next=qa;
　　qc=qa;
　　qa=qa->next;qb=qb->next;
　　}

　　break;
　　case 1:
　　qb->coef=-qb->coef;
　　qc->next=qb;
　　qc=qb;
　　hb=qb;
　　qb=qb->next;

　　break;
　　}
　　}

　　if(!qa)
　　{
　　qc->next=qb;
　　while(qb!=0)
　　{
　　qb->coef=-qb->coef;
　　qb=qb->next;
　　}
　　c1.tail=pb.tail;

　　}
　　else
　　{
　　qc->next=qa;
　　c1.tail=pa.tail;
　　}
　　LenPolyn(c1);
　　return c1;
　　}

　　四、调试分析
　　(1)调试过程中遇到的问题及其解决方法

　　A.问题:库函数 malloc 调用错误
　　解决方法:函数 malloc 的声明
　　void * malloc (unsigned size )
　　可以强制类型转换,前面为指针类型,后面为所分配的内存空间的大小
　　用于申请一段新的地址,参数 size 为需要内存空间的长度

　　B.问题:函数的指针类型的形式参数重复定义
　　解决方法:在函数定义的形式参数列表中, 指针类型的形式参数定义注意事项:
　　采用值传递,内存空间已经自动分配完毕;
　　采用引用传递,内存空间需要自动分配;

　　C.问题:在 for 循环语句中,循环变量使用控制错误
　　解决方法: 在 for 循环语句中,应该意识到:
　　循环变量的执行次数总是比循环体的执行次数多一次;
　　即最后一次的循环体执行完毕之后,循环变量又执行了一次,但是循环体却没有再执行了

　　D.问题: C++ 中编译出错信息: "cannot open Debug/*.exe for writing"
　　解决方法: 第一次编译运行后，没有关掉那个程序，所以更改后再次编译就提示不能写入;那么打开任务管理器看看那个进程在不在，可能关了窗口，但程序还没有结束;
　　记得编译前关闭程序，或者到任务管理器的看看进程是否存在，有的话结束掉

　　E.问题: AV(Access Violation) 错误
　　解决方法: 访问不再有效的内存,
　　大多数的情况下,出现这个错误要么是因为你试图访问一块已经被释放的内存,要么是想使用一个还未创建对象的指针。

　　F.问题: C++ 中编译出错信息: left operand must be l-value
　　解决方法: l-value应该是个left-value，也就是左值，只有变量和看作指针的内存空间可以被看作是左值

　　(2)经验与体会

　　A.在线性链表中进行遍历操作的两种常用控制手段:
　　a. 利用该线性链表的长度 L.length
　　b. 利用该线性链表的尾指针 NULL

　　B.在书写程序时,应该注意 return 语句在程序中的位置,因为在顺序结构中一旦使用到了 return 语句,return 语句后面的所有程序代码都无法再执行.

　　C.在对线性链表的操作中,
　　如果是加工型操作,则需要在形参列表中用引用传递的方式返回该线性链表 L;
　　如果是引用型操作,则不需要在形参列表中用引用传递的方式返回该线性链表 L;

　　D.在程序调试过程中,如果发现许多地方犯了同一类错误,则应该一次性将这一类错误全部调试好,这样可以提高程序调试的效率

　　E.返回链表类型的数据元素应该是链表结点,而不是该链表结点中的数据域 data

　　五、用户使用说明
　　本程序操作步骤：

　　(1) 初始化多项式P1
　　输入多项式 P1 的项数；
　　然后从第1项开始,分别输入多项式各项的系数和指数(先输入系数，后输入指数)；
　　程序会自动输出该一元稀疏多项式P1 (序列按指数升序排列)

　　(2) 初始化多项式P2
　　输入多项式 P2 的项数；
　　然后从第1项开始,分别输入多项式各项的系数和指数(先输入系数，后输入指数)；
　　程序会自动输出该一元稀疏多项式P2 (序列按指数升序排列)

　　(3) 输入想要做的多项式运算类型:
　　相加 1 相减 2:

　　(4)本程序会自动根据所选择的多项式运算类型,做出相应的数学运算,并且输出运算结果:一元稀疏多项式 (序列按指数升序排列)

　　六、测试结果
　　键盘输入与屏幕输出:

　　A
　　请输入p1的数目:3 (输入值)
　　请输入p的系数和指数:
　　1
　　3
　　4
　　6
　　7
　　9
　　该一元稀疏多项式输出即为(序列按指数升序排列):
　　X^3+4X^6+7X^9

　　请输入p2的数目:5 (输入值)
　　请输入p的系数和指数:
　　2
　　5
　　8
　　9
　　87
　　7
　　8
　　5
　　2
　　47
　　该一元稀疏多项式输出即为(序列按指数升序排列):
　　10X^5+87X^7+8X^9+2X^47

　　相加 1 相减 2:
　　1 (输入值)
　　多项式的和:
　　该一元稀疏多项式输出即为(序列按指数升序排列):
　　X^3+10X^5+4X^6+87X^7+15X^9+2X^47

　　Press any key to continue

　　B
　　请输入p1的数目:3
　　请输入p的系数和指数:
　　1
　　3
　　4
　　6
　　7
　　9
　　该一元稀疏多项式输出即为(序列按指数升序排列):
　　X^3+4X^6+7X^9

　　请输入p2的数目:4
　　请输入p的系数和指数:
　　6
　　5
　　6
　　5
　　8
　　9
　　5
　　526
　　该一元稀疏多项式输出即为(序列按指数升序排列):
　　12X^5+8X^9+5X^526

　　相加 1 相减 2:
　　2
　　多项式的差:
　　该一元稀疏多项式输出即为(序列按指数升序排列):
　　X^3-12X^5+4X^6+X^9-5X^526
　　Press any key to continue

　　七、附录
　　带有注释的源程序(见源程序文件)

　　那是相当麻烦啊。。。。这个还是比较不麻烦的，书上还有用伪代码的。。。

Answer 2

分多我就送你一个