《数据结构实习报告.docx》由会员分享，可在线阅读，更多相关《数据结构实习报告.docx（16页珍藏版）》请在三一文库上搜索。
1、. 数据结构实习报告 姓 名： 学 号： 班 级： ; 一、一元多项式计算 1、题目要求： 能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减和相乘，并将结果输出。 2、程序代码：#include<stdio.h>#include<malloc.h>typedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial; /Polyn为结点指针类型 void Insert(Polyn p,Polyn h) if(p->coef=0
2、) free(p); /系数为0的话释放结点elsePolyn 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=q
3、2; q1->next=p; /InsertPolyn 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",
4、&p->coef,&p->expn);Insert(p,head); /调用Insert函数插入结点return head;/CreatePolynvoid DestroyPolyn(Polyn p)/销毁多项式pPolyn 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) /若多项式为空，输出0put
5、char('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",
6、q->expn);elseif(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=
7、q->next; flag+;/whileprintf("n"); /PrintPolynint 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多项式非空 /comparePo
8、lyn 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
9、;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; /switchif(qc->coef!=0)qc->next=hc->next;hc->next=qc;hc=qc;el
10、se free(qc); /当相加系数为0时，释放该结点 /whilereturn headc; /AddPolynPolyn 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; /SubtractPolyn
11、int main()int m,n,flag=0;float x;Polyn pa=0,pb=0,pc,pd,pe,pf;/定义各式的头指针，pa与pb在使用前付初值NULLprintf("请输入a的项数:");scanf("%d",&m);pa=CreatePolyn(pa,m);/建立多项式aprintf("请输入b的项数:");scanf("%d",&n);pb=CreatePolyn(pb,n);/建立多项式a/输出菜单printf("*n");printf("
12、操作提示：nt1.输出多项式a和bnt2.建立多项式a+bnt3.建立多项式a-bn");printf("t4.退出n*n");for(;flag=0)printf("执行操作：");scanf("%d",&flag);if(flag=1)printf("多项式a：");PrintPolyn(pa);printf("多项式b：");PrintPolyn(pb);continue; if(flag=2)pc=AddPolyn(pa,pb);printf("多项式a+b：
13、");PrintPolyn(pc);DestroyPolyn(pc);continue; if(flag=3)pd=SubtractPolyn(pa,pb);printf("多项式a-b：");PrintPolyn(pd);DestroyPolyn(pd);continue; if(flag=4) break; if(flag<1|flag>4) printf("Error!n");continue;/forDestroyPolyn(pa);DestroyPolyn(pb);return 0;3、运行结果： 二、设计一个模拟计算器的
14、程序 1、题目要求： 设计一个模拟计算器的程序 要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。2、 程序代码：#include <iostream>#include <string>#include <stdlib.h>using namespace std;class calculator public:void cal(string s);void express();int legal(string w);private:void push();void pop();bool can();int StringToN
15、umber(string aStr);int number1000;char symbolt1000;string s,t;int i,j,p;void calculator:push() p+;symboltp=si;void calculator:pop() p-;switch (symboltp+1)case '+':numberp+=numberp+1;break;case '-':numberp=numberp-numberp+1;break;case '*':numberp=numberp*numberp+1;break;case &
16、#39;/':numberp=numberp/numberp+1;break;bool calculator:can()if (si='+')|(si='-')&&(symboltp!='(') return true;if (si='*')|(si='/')&&(symboltp='*')|(symboltp='/') return true;return false;int calculator:StringToNumber(string
17、aStr) int number = 0;for (int i=0;i<aStr.length();i+)number = number*10 + aStri-48; return number;void calculator:cal(string w) s='('+w+')'i=0;p=0;while (i<=s.length()-1) while (si='(') push();i+;j=i;do i+;while (si>='0')&&(si<='9');int m;t
18、=""int h=0;for(m=j;m<i;m+) t=t+sm;numberp = StringToNumber(t);do if (si=')')while (symboltp!='(') pop();p-;numberp=numberp+1;elsewhile (can() pop();push();i+;while (i<=s.length()&&(si-1=')');void calculator:express()cout<<number0<<endl; int
19、 calculator:legal(string w)int k=0;for(i=0;i<w.length();i+)if(!(wi='+'|wi='-'|wi='*'|wi='/'|wi='('|wi=')'|(wi>='0'&&wi<='9')k+;if(k)cout<<"error:含有非法字符"<<endl;return k;int main(int argc, char* argv
20、)while(1)string w; cout<<"input your string:"cin>>w;calculator MyCal;if(!MyCal.legal(w)MyCal.cal(w);MyCal.express(); char chose; cout<<"是否继续Y/N"<<endl;cin>>chose;if (chose='n'|chose='N') break; return 0;3、 运行结果： 三、Josephus问题1、 题目要求： 设
21、有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。2、 程序代码：#include <stdio.h>#include "malloc.h"#define False 0#define TRUE 1typedef int DataType;struct SeqListint MAXNUM;int n;DataType *element;typedef struct Seq
22、List *PSeqList;PSeqList createNullList_seq(int m)PSeqList palist=(PSeqList)malloc(sizeof(struct SeqList);if(palist!=NULL)palist->element=(DataType*)malloc(sizeof(DataType)*m);if(palist->element)palist->MAXNUM=m;palist->n=0;return palist;else free(palist);printf("Out of space!n"
23、);return NULL;int insertPre_seq(PSeqList palist,int p,DataType x)/*在palist所指顺序表中下标为P的元素之前插入元素x*/int q;if (palist->n>=palist->MAXNUM)/溢出printf("Overflow! n");return 0;if (p<0|p>palist->n)printf("Not exist! n");return 0;for(q=palist->n-1;q>=p;q-)palist->e
24、lementq+1=palist->elementq;palist->elementp=x;palist->n=palist->n+1;return 1;int deleteP_seq(PSeqList palist,int p)/删除下标为p的元素int q;if (p<0|p>palist->n-1)printf("Not exist! n");return 0;for(q=p;q<palist->n-1;q+)palist->elementq=palist->elementq+1;palist->
25、n=palist->n-1;return 1;void josephus_seq(PSeqList palist,int s,int m)int s1,i,w;s1=s-1;for(i=palist->n;i>0;i-)s1=(s1+m-1)%i;w=palist->elements1;printf("Out element %d n",w);deleteP_seq(palist,s1);main()PSeqList jos_alist;int i;int n,s,m;printf("nplease input the values(<
26、;100) of n=");scanf("%d",&n);printf("please input the values of s=");scanf("%d",&s);printf("please input the values of m=");scanf("%d",&m);jos_alist=createNullList_seq(n);if(jos_alist!=NULL)for(i=0;i<n;i+)insertPre_seq(jos_alist,i,i+1);josephus_seq(jos_alist,s,m);free(jos_alist->element);free(jos_alist);3、 运行结果：例如输入n8，s1，m4；结果如下：14