数据结构实习报告

1、 数据结构实习报告 姓 名： 学 号： 班 级： 14 / 16文档可自由编辑打印 一、一元多项式计算1、题目要求： 能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减和相乘，并将结果输出。 2、程序代码：#include#includetypedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial; /Polyn为结点指针类型 void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系数为0的话释放结点elseP

2、olyn q1,q2;q1=h;q2=h-next;while(q2&p-expnexpn) /查找插入位置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; /InsertPolyn CreatePolyn(Polyn head,int m) /建立一个头指针为head、项数为m的一元多项式int i;Polyn p;p=hea

3、d=(Polyn)malloc(sizeof(struct Polynomial);head-next=NULL;for(i=0;icoef,&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;

4、/项数计数器if(!q) /若多项式为空，输出0putchar(0); printf(n);return; while (q)if(q-coef0&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);elseif(q-coef=1)if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else pr

5、intf(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+;/whileprintf(n); /PrintPolynint compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else if(!a&b) return -1; /a多项式已

6、空，但b多项式非空 else return 1; /b多项式已空，但a多项式非空 /comparePolyn 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(compa

7、re(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; /switchif(qc-coef!=0)qc-next=hc-next;hc-next=qc;hc=qc;else free(qc); /当相加系数为0时，释放该结点 /whilereturn hea

8、dc; /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; /SubtractPolynint main()int m,n,flag=0;float x;Polyn pa=0,pb=0,pc,pd,pe,pf;/定义各式的头指

9、针，pa与pb在使用前付初值NULLprintf(请输入a的项数:);scanf(%d,&m);pa=CreatePolyn(pa,m);/建立多项式aprintf(请输入b的项数:);scanf(%d,&n);pb=CreatePolyn(pb,n);/建立多项式a/输出菜单printf(*n);printf(操作提示：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);p

10、rintf(多项式b：);PrintPolyn(pb);continue; if(flag=2)pc=AddPolyn(pa,pb);printf(多项式a+b：);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(flag4) printf(Error!n);continue;/forDestroyPolyn(pa);DestroyPo

11、lyn(pb);return 0;3、运行结果： 二、设计一个模拟计算器的程序1、题目要求： 设计一个模拟计算器的程序 要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。2、 程序代码：#include #include #include using namespace std;class calculator public:void cal(string s);void express();int legal(string w);private:void push();void pop();bool can();int StringToNumber(string aStr);in

12、t 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 /:numberp=numberp/numberp+1;break;bool calculator:ca

13、n()if (si=+)|(si=-)&(symboltp!=() return true;if (si=*)|(si=/)&(symboltp=*)|(symboltp=/) return true;return false;int calculator:StringToNumber(string aStr) int number = 0;for (int i=0;iaStr.length();i+)number = number*10 + aStri-48; return number;void calculator:cal(string w) s=(+w+);i=0;p=0;while

14、(i=0)&(si=9);int m;t=;int h=0;for(m=j;mi;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()coutnumber0endl; int calculator:legal(string w)int k=0;for(i=0;i=0&wi=9)k+;i

15、f(k)couterror:含有非法字符endl;return k;int main(int argc, char* argv)while(1)string w; coutw;calculator MyCal;if(!MyCal.legal(w)MyCal.cal(w);MyCal.express(); char chose; cout是否继续Y/Nchose;if (chose=n|chose=N) break; return 0;3、 运行结果： 三、Josephus问题1、 题目要求： 设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数

16、，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。2、 程序代码：#include #include malloc.h#define False 0#define TRUE 1typedef int DataType;struct SeqListint MAXNUM;int n;DataType *element;typedef struct SeqList *PSeqList;PSeqList createNullList_seq(int m)PSeqList palist=(PSeqList)ma

17、lloc(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);return NULL;int insertPre_seq(PSeqList palist,int p,DataType x)/*在palist所指顺序表中下标为P的元素之前插入元素x*/int q;if

18、(palist-n=palist-MAXNUM)/溢出printf(Overflow! n);return 0;if (ppalist-n)printf(Not exist! n);return 0;for(q=palist-n-1;q=p;q-)palist-elementq+1=palist-elementq;palist-elementp=x;palist-n=palist-n+1;return 1;int deleteP_seq(PSeqList palist,int p)/删除下标为p的元素int q;if (ppalist-n-1)printf(Not exist! n);return 0;for(q=p;qn-1;q+)palist-elementq=palist-elementq+1;palist-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;i0;i-)s1=(s1+m-1)%i;w=palist-elements1;printf(Out element %d n,w);deleteP_seq(palist,s1);main()PSeqLis