第一篇:数据结构课程设计 文章编辑 源代码
#include
gets(str);
if(strlen(str)>100)
{
printf(“每行最多输入100字符”);
break;
}
if(str[0]==64)
{
str[0]=' ';
p->ch[0]=str[0];
break;
}
p->next=(Lstring *)malloc(sizeof(Lstring));
strcpy(p->ch,str);
if(str[strlen(str)-1]==64)
{
p->ch[strlen(str)-1]=' ';
break;
}
p=p->next;} p->next=NULL;return head;} /****输出文章*****/ Lstring *OutPut(Lstring *head){ Lstring *p=head;do {
printf(“%sn”,p->ch);} while((p=p->next)!=NULL);return head;}
/****统计字母的个数*****/ int Alphabet(Lstring *head){
Lstring *p=head;int count=0;do { int Len;
Len=strlen(p->ch);
for(int i=0;i if((p->ch[i]>='a'&&p->ch[i]<='z')||(p->ch[i]>='A'&&p->ch[i]<='Z')) count++;}while((p=p->next)!=NULL);return count;} /****统计数字的字数*****/ int Num(Lstring *head){ Lstring *p=head;int count=0;do { int Len; Len=strlen(p->ch);for(int i=0;i if(p->ch[i]>='0' && p->ch[i]<='9') count++;}while((p=p->next)!=NULL);return count;} /****统计空格的字数*****/ int Space(Lstring *head){ Lstring *p=head;int count=0;do { int Len; Len=strlen(p->ch); for(int i=0;i if(p->ch[i]==32)count++;} while((p=p->next)!=NULL);return count;} /*统计文章的总字数*/ int All(Lstring *head){ Lstring *p=head;int count=0;do { count+=strlen(p->ch);} while((p=p->next)!=NULL);return count;} /****串的简单模式匹配*****/ int FindString(Lstring *head,char *str){ Lstring *p=head;int count=0;int h=0;int len1=0;int len2=strlen(str);int i,j,k;do { len1=strlen(p->ch); for(i=0;i { if(p->ch[i]==str[0]) { k=0; for(j=0;j if(p->ch[i+j]==str[j])k++; if(k==len2) { count++; i=i+k-1; } } } }while((p=p->next)!=NULL);return count;} void delstringword(char *s,char *str){ char *p;int count,len,i,j;char s1[80];p=strstr(s,str);len=strlen(s);i=len-strlen(p);j=i+strlen(str);count=0;for(int m=0;m s1[count++]=s[m]; for(int n=j;n s1[count++]=s[n]; s1[count]=' ';strcpy(s,s1);} Lstring *DelString(Lstring *head,char *str){ Lstring *p=head;do { while(strstr(p->ch,str)!=NULL) delstringword(p->ch,str);} while((p=p->next)!=NULL);return head;} void main(){ int i=0;int m;Lstring *head;char s1[20],s2[20];head=input();printf(“输入的文章为:n”);head=OutPut(head);printf(“n”);printf(“全部字母数:%d n”,Alphabet(head));printf(“数字个数:%d n”,Num(head));printf(“空格个数: %d n”,Space(head));printf(“文章总字数: %d n”,All(head));printf(“n”);printf(“**********************n”);printf(“* 菜 单 *n”);printf(“**********************n”);printf(“* 1---统计字符串 *n”);printf(“* 2---删除字符串 *n”);printf(“* 0---退出 *n”);printf(“**********************n”);do { printf(“请输入你要选择的操作(0~2):”); scanf(“%d”,&m); switch(m) { case 0: exit(0); break; case 1: printf(“请输入要统计的字符串:”); scanf(“%s”,&s1); printf(“%s在文章中出现的次数为:%d n”,s1,FindString(head,s1)); } printf(“n”); break; case 2: printf(“请输入要删除的某一字符串:”); scanf(“%s”,&s2); head=DelString(head,s2); printf(“删除%s后的文章为:n”,s2); OutPut(head); break; } }while(m!=0); #include eOperator = 1 //算子 }; int oper[7]={43,45,42,47,40,41,35}; char OPSET[OPSETSIZE]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'}; typedef struct sqlist{ int bol;//bol 是 0 时,num-ch是一个数字;bol 是 1 时 num_ch 运算符 int num_ch;struct sqlist *next;}sqlist;//线性表 typedef struct sqstack{ int *base;int *top;int stacksize;}sqstack;//栈的定义 unsigned char Prior[7][7] = {// 课本 表3.1 算符间的优先关系 '>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=',' ','>','>','>','>',' ','>','>','<','<','<','<','<',' ','=' }; int init_sq(sqlist *l){//初始化链表 l=(sqlist*)malloc(sizeof(sqlist));if(l==NULL){ exit(-2);} l->next=NULL;return 1;} int insert_sq(sqlist **p,int e,int bl){//链表插入操作 sqlist *q;q=(sqlist*)malloc(sizeof(sqlist));q->num_ch=e;q->bol=bl;q->next=NULL;(*p)->next=q;(*p)=(*p)->next;return 1;} int check(sqlist l)//保证输入的数字是给出的四个数字 { int right=1,find=0,i;sqlist *q=&l;q=q->next;for(;q->next!=NULL;q=q->next){ if(q->bol==1){ if(q->num_ch <=39||q->num_ch>57||q->num_ch==44||q->num_ch==46){ right=0; printf(“%c不是有效的运算符!n”); } } else { find=0; for(i=0;i<4;i++){ if(number[1][i]==0&&number[0][i]==q->num_ch){ number[1][i]=1; find=1; break; } } if(find==0){ printf(“%d 不在给出的四个数字中!n”,q->num_ch); right=0; } } }//end for for(i=0;i<4;i++){ if(number[1][i]==0){ printf(“%d没有用上!n”,number[0][i]); right=0; } } return right;} int chang(char *s,sqlist *l){//将用户的输入转化为单链表 int t=0;unsigned int i=0;int bl,ch;int a1,a2,a;sqlist *p=l;for(;i if(s[i]>47&&s[i]<58&&t==0){ a1=(int)s[i]-48; t++; } else if(s[i]>47&&s[i]<58&&t==1){ a2=(int)s[i]-48; a=a1*10+a2; t++; } else if(s[i]<48&&s[i]>39&&s[i]!=44&&s[i]!=46){ if(t==1){ bl=0; insert_sq(&p,a1,bl); t=0; } else if(t==2){ bl=0; insert_sq(&p,a,bl); t=0; } bl=1; ch=(int)s[i]; insert_sq(&p,ch,bl); t=0; } else { printf(“%c不是有效的运算符!n”,s[i]); } } //end for i=strlen(s)-1;if(s[i]>47&&s[i]<58){ if(s[i-1]>47&&s[i-1]<58){ bl=0; insert_sq(&p,a,bl); } else { bl=0; insert_sq(&p,a1,bl); } } bl=1;a=35;insert_sq(&p,a,bl);return(check(*l));} int Operate(int a,int theta, int b){//计算 switch(theta){ case 43: return a+b;case 45: return a-b;case 42: return a*b;case 47: { if(b==0){ return-2000; } if(a%b==0){ return a/b; } else {//printf(“不能为小数n”); return-10000; } } default : return 0;} } int ReturnOpOrd(char op,char* TestOp)// precede()函数调用求优先级 { int i;for(i=0;i< OPSETSIZE;i++){ if(op == TestOp[i])return i;} return 0;} char precede(char Aop, char Bop){ return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];} int initstack(sqstack *s){(s)->base =(int*)malloc(STACK_INIF_SIZE*sizeof(int));if((s)->base==NULL)exit(-2);(s)->top=(s)->base;(s)->stacksize = STACK_INIF_SIZE;return 1;} int gettop(sqstack *s){ //取得栈顶元素 int e;if(s->top==s->base){ printf(“栈空,无法取得栈顶元素!n”); return 0;} e=*(s->top-1);return e;} int push(sqstack *s,int e){ //压栈 if(s->top-s->base>=s->stacksize){ s->base=(int*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(int)); if(!s->base)exit(-2); s->stacksize+= STACKINCREMENT;} *(s->top++)=e;return 1;} int pop(sqstack *s,int *e){ //出栈 if(s->top==s->base){ printf(“栈空,出栈错误!n”); return 0;} *e=*(--s->top);return 1;} int EvaluateExpression(char* MyExpression){ // 算法3.4----计算表达式的值 // 算术表达式求值的算符优先算法。 // 设OPTR和&&OPND分别为运算符栈和运算数栈 int result;sqstack OPTR; // 运算符栈,字符元素 sqstack OPND; // 运算数栈,实数元素 int c,bl,a,b,theta,top;sqlist *q,l;char *s=MyExpression;init_sq(&l);if(chang(s,&l)!=0){ q=&l; initstack(&OPTR); push(&OPTR, 35); initstack(&OPND); q=q->next; c=q->num_ch; bl=q->bol; while((c!= 35 || gettop(&OPTR)!=35)){ if(bl!=1){ push(&OPND, c); q=q->next; c=q->num_ch; bl=q->bol; } // 不是运算符则进栈 else{ top=gettop(&OPTR); switch(precede((char)top,(char)c)){ case '<': // 栈顶元素优先权低 push(&OPTR, c); q=q->next; c=q->num_ch; bl=q->bol; break; case '=': // 脱括号并接收下一字符 pop(&OPTR, &c); q=q->next; c=q->num_ch; bl=q->bol; break; case '>': // 退栈并将运算结果入栈 pop(&OPTR, &theta); pop(&OPND, &b); pop(&OPND, &a); push(&OPND, Operate(a, theta, b)); break; default : printf(“没有这个运算符!n”); return 0; } // switch }//else } // while result=gettop(&OPND); return result;} else { printf(“你的输入有错误!n”); return 0;} } int randomm()//产生四个随机数 { int i=0;srand((unsigned)time(NULL));for(;i<4;i++){ number[0][i]=0; number[0][i]=rand(); number[0][i]%=13; number[0][i]++; number[1][i]=0;} return number[2][4];} int CalcOneExpress(int expression[][2])// 计算表达式 { // 算术表达式求值的算符优先算法。 // 设OPTR和&&OPND分别为运算符栈和运算数栈,OP为运算符集合。int index=0,result,c,theta,a,b;sqstack OPTR; // 运算符栈,字符元素 sqstack OPND; // 运算数栈,实数元素 initstack(&OPTR);push(&OPTR, 35);initstack(&OPND);c=expression[index][0];while(c!= 35 || gettop(&OPTR)!=35){ if(expression[index][1]!=1){ push(&OPND, c); index++; c=expression[index][0];} // 不是运算符则进栈 else { switch(precede((char)gettop(&OPTR),(char)c)) { case '<': // 栈顶元素优先权低 push(&OPTR, c); index++; c=expression[index][0]; break; case '=': // 脱括号并接收下一字符 pop(&OPTR, &c); index++; c=expression[index][0]; break; case '>': // 退栈并将运算结果入栈 pop(&OPTR, &theta); pop(&OPND, &b); pop(&OPND, &a); push(&OPND, Operate(a, theta, b)); break; default : printf(“没有这个运算符n”); return 0; } // switch }//else } // while result=gettop(&OPND);return result;} int Equal24(int n){ if(n==24){ return 1;} else return 0;} //括号的几种情况 //1 无括号 //2(a b)c d 同a b(c d), 下省略 //3(a b c)d //4(a b)(c d)//5((a b)c)d int CalcArray1(int iNumInput[2][4]){ // a * b * c * d 7 个字符 int expression[8][2],ii,jj,kk;int i,j,k,l,dRes;for(i=0;i<4;i++){ for(j=0;j<4;j++) { if(j==i) { continue; } for(k=0;k<4;k++) { if(k==i||k==j) { continue; } for(l=0;l<4;l++) { if(l==i||l==j||l==k) { continue; } expression[0][0]=iNumInput[0][i]; expression[2][0]=iNumInput[0][j]; expression[4][0]=iNumInput[0][k]; expression[6][0]=iNumInput[0][l]; expression[0][1]=eNumber; expression[2][1]=eNumber; expression[4][1]=eNumber; expression[6][1]=eNumber; for(ii=0;ii<4;ii++) { for(jj=0;jj<4;jj++) { for(kk=0;kk<4;kk++) { expression[1][0] = oper[ii]; expression[1][1] = eOperator; expression[3][0] = oper[jj]; expression[3][1] = eOperator; expression[5][0] = oper[kk]; expression[5][1] = eOperator; expression[7][0] = oper[6]; expression[7][1] = eOperator; dRes = CalcOneExpress(expression); if(Equal24(dRes)) { printf(“可以这样运算:%d%c%d%c%d%c%dn”,expression[0][0],oper[ii],expression[2][0],oper[jj],expression[4][0],oper[kk],expression[6][0]); return 1; } } } }//end of for oper } } } } return 0;} int CalcArray2(int iNumInput[2][4]){ //(a * b)* c * d //9 number int expression[10][2];int ii,jj,i,j,k,l,kk;int dRes;for(i=0;i<4;i++){ for(j=0;j<4;j++) { if(j==i) { continue; } for(k=0;k<4;k++) { if(k==i||k==j) { continue; } for(l=0;l<4;l++) { if(l==i||l==j||l==k) { continue; } expression[1][0]=iNumInput[0][i]; expression[3][0]=iNumInput[0][j]; expression[6][0]=iNumInput[0][k]; expression[8][0]=iNumInput[0][l]; expression[1][1]=eNumber; expression[3][1]=eNumber; expression[6][1]=eNumber; expression[8][1]=eNumber; for(ii=0;ii<4;ii++) { for(jj=0;jj<4;jj++) { for(kk=0;kk<4;kk++) { expression[0][0] = oper[4]; expression[0][1] = eOperator; expression[2][0] = oper[ii]; expression[2][1] = eOperator; expression[4][0] = oper[5]; expression[4][1] = eOperator; expression[5][0] = oper[jj]; expression[5][1] = eOperator; expression[7][0] = oper[kk]; expression[7][1] = eOperator; expression[9][0] = oper[6]; expression[9][1] = eOperator; dRes = CalcOneExpress(expression); if(Equal24(dRes)) { printf(“可以这样运算:%c%d%c%d%c%c%d%c%dn”,oper[4],expression[1][0],oper[ii],expression[3][0],oper[5],oper[jj],expression[6][0],oper[kk],expression[8][0]); return 1; } } } }//end of for oper } } } } return 0;} int CalcArray3(int iNumInput[2][4]){ //(a * b * c)* d //9 number int expression[10][2];int ii,jj,i,j,k,l,kk;int dRes;for(i=0;i<4;i++){ for(j=0;j<4;j++) { if(j==i) { continue; } for(k=0;k<4;k++) { if(k==i||k==j) { continue; } for(l=0;l<4;l++) { if(l==i||l==j||l==k) { continue; } expression[1][0]=iNumInput[0][i]; expression[3][0]=iNumInput[0][j]; expression[5][0]=iNumInput[0][k]; expression[8][0]=iNumInput[0][l]; expression[1][1]=eNumber; expression[3][1]=eNumber; expression[5][1]=eNumber; expression[8][1]=eNumber; for(ii=0;ii<4;ii++) { for(jj=0;jj<4;jj++) { for(kk=0;kk<4;kk++) { expression[0][0] = oper[4]; expression[0][1] = eOperator; expression[2][0] = oper[ii]; expression[2][1] = eOperator; expression[4][0] = oper[jj]; expression[4][1] = eOperator; expression[6][0] = oper[5]; expression[6][1] = eOperator; expression[7][0] = oper[kk]; expression[7][1] = eOperator; expression[9][0] = oper[6]; expression[9][1] = eOperator; dRes = CalcOneExpress(expression); if(Equal24(dRes)) { printf(“可以这样运算:%c%d%c%d%c%d%c%c%dn”,oper[4],expression[1][0],oper[ii],expression[3][0],oper[jj],expression[5][0],oper[5],oper[kk],expression[8][0]); return 1; } } } }//end of for oper } } } } return 0;} int CalcArray4(int iNumInput[2][4]){ //(a * b)*(c * d)//11 numbers int expression[12][2];int ii,jj,i,j,k,l,kk;int dRes;for(i=0;i<4;i++){ for(j=0;j<4;j++) { if(j==i) { continue; } for(k=0;k<4;k++) { if(k==i||k==j) { continue; } for(l=0;l<4;l++) { if(l==i||l==j||l==k) { continue; } expression[1][0]=iNumInput[0][i]; expression[3][0]=iNumInput[0][j]; expression[7][0]=iNumInput[0][k]; expression[9][0]=iNumInput[0][l]; expression[1][1]=eNumber; expression[3][1]=eNumber; expression[7][1]=eNumber; expression[9][1]=eNumber; for(ii=0;ii<4;ii++) { for(jj=0;jj<4;jj++) { for(kk=0;kk<4;kk++) { expression[0][0] = oper[4]; expression[0][1] = eOperator; expression[2][0] = oper[ii]; expression[2][1] = eOperator; expression[4][0] = oper[5]; expression[4][1] = eOperator; expression[5][0] = oper[jj]; expression[5][1] = eOperator; expression[6][0] = oper[4]; expression[6][1] = eOperator; expression[8][0] = oper[kk]; expression[8][1] = eOperator; expression[10][0] = oper[5]; expression[10][1] = eOperator; expression[11][0] = oper[6]; expression[11][1] = eOperator; dRes = CalcOneExpress(expression); if(Equal24(dRes)) { printf(“可以这样运算:%c%d%c%d%c%c%c%d%c%d%cn”,oper[4],expression[1][0],oper[ii],expression[3][0],oper[5],oper[jj],oper[4],expression[7][0],oper[kk],expression[9][0],oper[5]); return 1; } } } }//end of for oper } } } } return 0;} int CalcArray5(int iNumInput[2][4]){ //((a * b)* c)* d //11 numbers int expression[12][2];int ii,jj,i,j,k,l,kk;int dRes;for(i=0;i<4;i++){ for(j=0;j<4;j++) { if(j==i) { continue; } for(k=0;k<4;k++) { if(k==i||k==j) { continue; } for(l=0;l<4;l++) { if(l==i||l==j||l==k) { continue; } expression[2][0]=iNumInput[0][i]; expression[4][0]=iNumInput[0][j]; expression[7][0]=iNumInput[0][k]; expression[10][0]=iNumInput[0][l]; expression[2][1]=eNumber; expression[4][1]=eNumber; expression[7][1]=eNumber; expression[10][1]=eNumber; for(ii=0;ii<4;ii++) { for(jj=0;jj<4;jj++) { for(kk=0;kk<4;kk++) { expression[0][0] = oper[4]; expression[0][1] = eOperator; expression[1][0] = oper[4]; expression[1][1] = eOperator; expression[3][0] = oper[ii]; expression[3][1] = eOperator; expression[5][0] = oper[5]; expression[5][1] = eOperator; expression[6][0] = oper[jj]; expression[6][1] = eOperator; expression[8][0] = oper[5]; expression[8][1] = eOperator; expression[9][0] = oper[kk]; expression[9][1] = eOperator; expression[11][0] = oper[6]; expression[11][1] = eOperator; dRes = CalcOneExpress(expression); if(Equal24(dRes)) { printf(“可以这样运算:%c%c%d%c%d%c%c%d%c%c%dn”,oper[4],oper[4],expression[2][0],oper[ii],expression[4][0],oper[5],oper[jj],expression[7][0],oper[5],oper[kk],expression[10][0]); return 1; } } } }//end of for oper } } } } return 0;} int Calc24(int number[2][4]){ int find=0;//括号的 5 种情况 //1 a b c d //2(a b)c d 同 a b(c d)和 a(b c)d //3(a b c)d //4(a b)(c d)//5((a b)c)d 同(a(b c))d if(CalcArray1(number)){ find=1; return 1;} if(CalcArray2(number)){ find=1; return 1;} if(CalcArray3(number)){ find=1; return 1;} if(CalcArray4(number)){ find=1; return 1;} if(CalcArray5(number)){ find=1; return 1;} if(find==0){ printf(“这四个数字算不出24点.n”); return 0;} return 0;} void gameinformation(){ printf(“┌────────────────────────┐n”);printf(“│ 点 游 戏 │n”);printf(“│ 学号: │n”);printf(“│ 设计人:XXX │n”);printf(“│ 完成时间:2015年7月20日 │n”);printf(“└────────────────────────┘nn”);} void menu(){ char s[40],ch,mood;int result,t=1,t0=1,nall=0,nright=0,t1=1;double right;while(t==1){ printf(“本游戏有以下三种模式可选择↓n”); printf(“┌────────────────────────┐n”); printf(“│→ 0.开始游戏 │n”); printf(“│◇ 1.游戏规则 │n”); printf(“│→ 2.退出游戏 │n”); printf(“└────────────────────────┘nn”); printf(“请输入选项所对应的数字↑:”); scanf(“ %c”,&mood); if(mood=='0'){ //计算机成四个数字,游戏者求表达式 nall=0; nright=0; t0=1; while(t0==1) { number[2][4]=randomm(); printf(“这四个数是: %d %d %d %dn”,number[0][0],number[0][1],number[0][2],number[0][3]); printf(“请输入算式n”); printf(“如果你认为这四个数算不出24点,请输入'?'n”); printf(“计算机将会给出答案,算不出也是一种答案!n”); printf(“你的算式是:”); scanf(“%s”,s); if(s[0]=='?'){ if(Calc24(number)==0){ nright++; } nall++; } else { result=EvaluateExpression(s); printf(“你输入的算式的结果是: %d n”,result); if(result==24) { printf(“你赢了!n”); nright++; nall++; } else { 字 printf(“你输了!n”); nall++; } }//else right=(double)nright/nall; printf(“你共做了 %d 道,做对了 %d 道,正确率为:%.2f%%n”,nall,nright,right*100); printf(“继续这个模式吗?请选择: 'y':继续 'n':退出?n”); scanf(“ %c”,&ch); if(ch=='n'||ch=='N'){ t0=0; } else if(ch=='Y'||ch=='y')t0=1; else{ printf(“你的选择(输入)有误!n”); t0=0; } } }//end mood 0 else if(mood=='1'){ //游戏规则说明 printf(“ 规则其实很简单: n”); printf(“ 只能使用+,-,*,/,(,)这6种符号完成表达式 printf(” 当然也允许改变数字顺序n“); printf(” 下面请看示例:n“); printf(” 系统给出的数字为:1 5 5 5n“); printf(” 你只要输入(5-1/5)*5 即可n“); printf(”n“); printf(”n“); printf(”n“); }//end mood 1 else if(mood=='2'){//退出游戏 printf(”游戏结束!n“); t=0; } else { printf(”mood =%cn“,mood); printf(”您的输入有误,游戏结束!n“); t=0; } }//end big while n”);} void main(){ gameinformation();//输出作者信息 menu();//输出功能菜单,游戏开始 } 课 程 设 计 任 务 书 信息 学院 信息管理与信息系统 专业 09级1班 班 孙鹏一、二、课程设计题目: 迷宫求解、一元多项式 课程设计主要参考资料: 数据结构(C语言版)严蔚敏、吴伟民 编著 数据结构题集(C语言版)严蔚敏、吴伟民、米宁 编著 数据结构课件 三、设计应解决下列各主要问题: 1.实现迷宫的路径求解,并输出最终路径,标记走过却未选择的路径和最终选择的路径 2.对一元多项式实现加法,减法,乘法,求导的计算,并按指数由大到小排序输出 四、课程设计相关附件(如:图纸、软件等): 五、命题发出日期:2011-3-15 设计应完成日期: 2010-6-20 设计指导教师(签章): 系主任(签章): 指导教师对课程设计的评语 指导教师(签章): 年 月 日 山东科技大学学生课程设计 课程设计1 迷宫问题 一、需求分析: 1.2.3.4.以二维数组Maze[][]表示迷宫 用户输入迷宫的数据:构建迷宫,行数m,列数n 迷宫的入口位置和出口位置可由用户随时设定 若设定的迷宫存在通路,则以长方阵形式将迷宫及其通路输出到标准输出文件(即终端)上,其中,字符“#”表示障碍,字符“*”表示路径上的位置,字符“@”表示“死胡同”,即曾经途径然而不能到达出口的位置,余者用空格符印出。若设定的迷宫不存在通路,则报告相应信息。 5.本程序只求出一条成功的通路。然而,只需要对迷宫求解的函数做小量修改,便可求得全部路径。 二、概要设计: 抽象数据类型线性表的定义如下: ⒈ 设计栈的抽象数据类型定义: ADT Stack { 数据对象:D={ai:|ai∈PositionSet,i=1„n,n≥0} 数据关系:R1={ Push(&S,e)Pop(&S,e) 返回其值 }ADT Stack; ⒉ 迷宫的抽象数据类型定义: ADT Maze{ 数据对象:D:={aij,Start,end|aij,Start,end∈{} 0≤i≤m+2,0≤j≤n+2,m,n≥0} 数据关系:R={ROW.COL} Row={ 第1页 操作结果 构造一个空栈,完成栈用e返回栈S的栈顶元将新的元素e压入栈顶 删除栈顶元素,并用eInitStack(&S) 山东科技大学学生课程设计 Col={ 基本操作: masepath(int i,int j,int m,int n,sqstack &s)初始条件:已知目前迷宫状态, 传过起始位置,和终止位置 操作结果:搜索迷宫,用sqstack s返回搜索所得路径。如不存在,返回2 }ADT MAZE 三、详细设计: #include typedef int Status; typedef struct { int r;int c;}PostType;//坐标位置 迷宫的r行c列 typedef struct { int ord;//通道块在路径上的序号 PostType seat;//通道块的当前坐标位置 int di;//通道块指向下一通道块的方向 }SElemType;//栈元素的类型 typedef struct { SElemType *base;//栈底指针 SElemType *top;//栈顶指针 int stacksize;//栈的最大容量 }Stack;//栈的类型 第2页 山东科技大学学生课程设计 Status InitStack(Stack &S)//初始化栈 { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base) exit(OVERFLOW);//存储分配失败;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}//InitStack Status StackEmpty(Stack S)//判断栈是否为空,如果为空返回TRUE,否则返回FALSE { if(S.top==S.base) return TRUE; return FALSE;}//StackEmpty Status Push(Stack &S,SElemType e)//插入元素为e的栈顶元素 { if(S.top-S.base>=S.stacksize){ S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACK_INCREMENT;} *S.top++=e;return OK;}//Push Status Pop(Stack &S,SElemType &e)//删除栈顶元素存入e { if(S.top==S.base) return ERROR;e=*--S.top; 第3页 山东科技大学学生课程设计 return OK;}//Pop Status DestroyStack(Stack &S)//销毁栈 { free(S.base);S.top=S.base;return OK;}//DestroyStack //maze.cpp #define MAXLEN 20//迷宫包括外墙最大行列数目 typedef struct{ int r; int c; char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#' }MazeType; //迷宫类型 Status InitMaze(MazeType &maze){ //初始化迷宫若成功返回TRUE,否则返回FALSE int m,n,i,j,k=1; printf(“输入迷口的行数和列数: ”); scanf(“%d%d”,&maze.r,&maze.c);//迷宫行和列数 for(i=0;i<=maze.c+1;i++){//迷宫行外墙 maze.adr[0][i]='#'; maze.adr[maze.r+1][i]='#'; }//for for(i=0;i<=maze.r+1;i++){//迷宫列外墙 maze.adr[i][0]='#'; maze.adr[i][maze.c+1]='#'; } for(i=1;i<=maze.r;i++) for(j=1;j<=maze.c;j++) maze.adr[i][j]=' ';//初始化迷宫 printf(“输入障碍物%d的坐标(以坐标(0,0)结束输入): ”,k); scanf(“%d%d”,&m,&n); k++; while(m!=0) { if(m>maze.r || n>maze.c)//越界 第4页 山东科技大学学生课程设计 exit(ERROR); maze.adr[m][n]='#';//迷宫障碍用'#'标记 printf(“输入障碍物%d的坐标(以坐标(0,0)结束输入): ”,k); scanf(“%d%d”,&m,&n); k++; } return OK;}//InitMaze Status Pass(MazeType maze,PostType curpos){ //当前位置可通则返回TURE,否则返回FALSE if(maze.adr[curpos.r][curpos.c]==' ')//可通 return TRUE; else return FALSE;}//Pass Status FootPrint(MazeType &maze,PostType curpos){ //若走过并且可通返回TRUE,否则返回FALSE //在返回之前销毁栈S maze.adr[curpos.r][curpos.c]='*';//“*”表示可通 return OK;}//FootPrint PostType NextPos(PostType &curpos,int i){ //指示并返回下一位置的坐标 PostType cpos; cpos=curpos; switch(i){ //1.2.3.4分别表示东,南,西,北方向 case 1 : cpos.c+=1;break; case 2 : cpos.r+=1;break; case 3 : cpos.c-=1;break; case 4 : cpos.r-=1;break; default: exit(ERROR); } return cpos;}//Nextpos Status MarkPrint(MazeType &maze,PostType curpos){ //曾走过但不是通路标记并返回OK 第5页 山东科技大学学生课程设计 maze.adr[curpos.r][curpos.c]='@';//“@”表示曾走过但不通 return OK;}//MarkPrint void PrintMaze(MazeType &maze)//将最后标记好的迷宫输出 { int i,j;printf(“n输出迷宫的路径:n”);for(i=0;i<=maze.c+1;i++) printf(“%4d”,i);//输出列数 printf(“n”);for(i=0;i<=maze.r+1;i++){ printf(“%d”,i);//输出行数 for(j=0;j<=maze.c+1;j++) printf(“%4c”,maze.adr[i][j]);//输出迷宫 printf(“n”);} }//PrintMaze Status MazePath(MazeType &maze,PostType start,PostType end)//若迷宫从入口start到end的通道则求得一条存放在栈中 { Stack S;//初始化栈 PostType curpos;int curstep;SElemType e;InitStack(S);curpos=start;curstep=1;do { if(Pass(maze,curpos))//当前位置可通过而未曾走过留下足迹 { FootPrint(maze,curpos); e.ord=curstep;e.seat=curpos;e.di=1; Push(S,e);//加入栈路径中 if(curpos.r==end.r && curpos.c==end.c)//到达出口返回TRUE { 第6页 山东科技大学学生课程设计 if(!DestroyStack(S)) exit(OVERFLOW); else return TRUE; } else { curpos=NextPos(curpos,1);//下一位置是当前位置 curstep++;//探索下一步 } }//if else//当前位置不能通过 { if(!StackEmpty(S)) { Pop(S,e);//提取前一位置 while(e.di==4 &&!StackEmpty(S))//4个方向都不能通过则留下记号@ 提取前一个位置进行判断是否是能通过 { MarkPrint(maze,e.seat); Pop(S,e); } if(e.di<4)//换下一个方向探索 设定当前位置为该新方向上的邻位 { e.di++; Push(S,e); curpos=NextPos(e.seat,e.di); } }//if } }while(!StackEmpty(S));if(!DestroyStack(S)) exit(ERROR);else return FALSE;}//MazePath int main(){ MazeType maze;PostType start,end;char c; 第7页 山东科技大学学生课程设计 do { printf(“**********迷宫求解**********n”); if(!InitMaze(maze)) { printf(“n 初始化迷宫失败!!”); exit(ERROR); } do { printf(“n请输入入口的坐标:”); scanf(“%d%d”,&start.r,&start.c);//输入入口坐标 if(start.r>maze.r || start.c>maze.c) printf(“n输入错误,请重新输入入口的坐标!n”); continue; } while(start.r>maze.r || start.c>maze.c); do { printf(“n请输入出口的坐标:”);//输入出口的坐标 scanf(“%d%d”,&end.r,&end.c); if(end.r>maze.r || end.c>maze.c) printf(“n输入错误,请重新输入出口坐标!n”); continue; } while(end.r>maze.r || end.c>maze.c); if(!MazePath(maze,start,end)) printf(“n不能找到一条路径!!n”); else PrintMaze(maze);//输出迷宫 printf(“是否要继续?(y/n):”); scanf(“%s”,&c);} while(c=='y' || c=='Y');}。测试结果: 第8页 四、山东科技大学学生课程设计 课程设计2 一元多项式 一、需求分析: 第9页 山东科技大学学生课程设计 1.2.3.首先定义一个结构体,其中定义一元多项式中的两个参数:系数和指数和链表中结点的指针域; 然后一一罗列每个在主程序中用到的函数,并一一实现; 最后在主程序中主要完成用户的输入和相关函数的调用。 二、概要设计: void insert(PLOYList *head,PLOYList *input) //查找位置插入新链节的函数,且让输入的多项式呈降序排列 PLOYList *creat(char ch)//输入多项式 PLOYList *add(PLOYList *head,PLOYList *pre)//多项式相加,head为第一个多项式建立的链表表头,pre为第二个多项式建立的链表表头 PLOYList *sub(PLOYList *head,PLOYList *pre)//多项式相减 PLOYList *mul(PLOYList *head,PLOYList *pre)//多项式相乘 PLOYList *der(PLOYList *head)//多项式求导 void print(PLOYList *fun)//输出多项式,fun指要输出的多项式链表的表头 void start()//用户选择界面 三、详细设计: #include //定义节点类型 { float coef; //多项式的系数 int expn; //多项式的指数 struct node * next;//结点指针域 }PLOYList;void insert(PLOYList *head,PLOYList *input) //查找位置插入新链节的函数,且让输入的多项式呈降序排列 { PLOYList *pre,*now; int signal=0; pre=head; 第10页 山东科技大学学生课程设计 if(pre->next==NULL){pre->next=input;} //如果只有一个头结点,则把新结点直接连在后面 else { now=pre->next;//如果不是只有一个头结点,则设置now指针 while(signal==0) { if(input->expn < now->expn) { if(now->next==NULL) { now->next=input; signal=1; } else { pre=now; now=pre->next;//始终让新输入的数的指数与最后一个结点中的数的指数比较,小于则插在其后面 } } else if(input->expn > now->expn) { input->next=now; pre->next=input; signal=1; }//若新结点中指数比最后一个结点即now中的指数大,则插入now之前 else//若指数相等则需合并为一个结点,若相加后指数为0则释放该结点 { now->coef=now->coef+input->coef; signal=1; free(input); if(now->coef==0) { pre->next=now->next; free(now); } }//else } //while 第11页 山东科技大学学生课程设计 }//else }//void PLOYList *creat(char ch) //输入多项式 { PLOYList *head,*input; float x; int y; head=(PLOYList *)malloc(sizeof(PLOYList)); //创建链表头 head->next=NULL; scanf(“%f %d”,&x,&y);//实现用户输入的第一个项,包括其指数和系数 while(x!=0) { input=(PLOYList *)malloc(sizeof(PLOYList));//创建新链节 input->coef=x; input->expn=y; input->next=NULL; insert(head,input);//每输入一项就将其排序,是的链表中多项式呈降序排列 scanf(“%f %d”,&x,&y); } return head;} PLOYList *add(PLOYList *head,PLOYList *pre) //多项式相加,head为第一个多项式建立的链表表头,pre为第二个多项式建立的链表表头 { PLOYList *input; int flag=0; while(flag==0) { if(pre->next==NULL) flag=1;//若该链表为空,则无需进行加法运算,跳出循环 else { pre=pre->next; input=(PLOYList *)malloc(sizeof(PLOYList)); 第12页 山东科技大学学生课程设计 input->coef=pre->coef; input->expn=pre->expn; input->next=NULL; insert(head,input);// 把g(x)插入到f(x)中,相当于两者相加,结果保存于f(x) } } return head;} PLOYList *sub(PLOYList *head,PLOYList *pre)//多项式相减 { PLOYList *input; int flag=0; while(flag==0) { if(pre->next==NULL) flag=1; else { pre=pre->next; input=(PLOYList *)malloc(sizeof(PLOYList)); input->coef=0-pre->coef;//将第二个多项式里的数变为其相反数,再用和加法一样的方法实现减法 input->expn=pre->expn; input->next=NULL; insert(head,input); } } return head;} PLOYList *mul(PLOYList *head,PLOYList *pre)//多项式项乘 { PLOYList *hf,*pf,*qa,*qb; qa = head-> next; qb = pre-> next;//定义指针指向表头后一个元素,即链表中第一个元素 hf =(PLOYList *)malloc(sizeof(PLOYList));//新创建一个结点,当做表头 hf-> next = NULL;for(;qa;qa = qa-> next) 第13页 山东科技大学学生课程设计 { for(qb = pre-> next;qb;qb= qb-> next)//用两个循环,实现两个多项式之间每个项相乘,结果用insert函数进行排序与合并 { pf =(PLOYList *)malloc(sizeof(PLOYList)); pf-> coef = qa-> coef * qb-> coef;//系数相乘 pf-> expn = qa-> expn + qb-> expn;//指数相加 pf-> next = NULL; insert(hf,pf); } } return hf;} PLOYList *der(PLOYList *head)//多项式求导 { PLOYList *p;p = head-> next;while(p){ p-> coef = p-> coef * p-> expn; p-> expn = p-> expn--; p = p-> next;} return head;}//将多项式的每项系数和指数相乘得到新的系数,指数减一得到新的指数即完成求导 void print(PLOYList *fun)//输出多项式,fun指要输出的多项式链表的表头 { PLOYList *printing; int flag=0; printing=fun->next; if(fun->next==NULL)//若为空表,则无需输出 { printf(“0n”); return; } while(flag==0) { 第14页 山东科技大学学生课程设计 if(printing->coef>0&&fun->next!=printing) printf(“+”); if(printing->coef==1); else if(printing->coef==-1) printf(“-”); else printf(“%f”,printing->coef); if(printing->expn!=0)printf(“x^%d”,printing->expn); else if((printing->coef==1)||(printing->coef==-1)) printf(“1”); if(printing->next==NULL) flag=1; else printing=printing->next; } printf(“n”);} void start()//用户选择界面 { printf(“ #n”); printf(“ 用户选择界面 n”); printf(“ ************************************n”); printf(“ * *n”); printf(“ * 1.两个一元多项式相加 *n”); printf(“ * 2.两个一元多项式相减 *n”); printf(“ * 3.两个一元多项式相乘 *n”); printf(“ * 4.对一个一个一元多项式求导 *n”); printf(“ * 0.退出系统 *n”); printf(“ * *n”); printf(“ ************************************n”); printf(“ n”); printf(“ 注释:输入多项式格式(可无序):系数1 指数1 系数2 指数2 „„,并以0 0 结束:n”); printf(“ n”); printf(“ 请选择操作: ”);} int main(){ PLOYList *f,*g,*pf,*hf,*p; 第15页 山东科技大学学生课程设计 int sign=-1; start(); while(sign!=0) { scanf(“%d”,&sign); switch(sign) { case 0: break; case 1://多项式相加 { printf(“ 你选择的操作是多项式相加:n”); printf(“ 请输入第一个多项式f(x):”); f=creat('f'); printf(“ 第一个多项式为:f(x)=”); print(f); printf(“ 请输入第二个多项式g(x):”); g=creat('g'); printf(“ 第二个多项式为:g(x)=”); print(g); printf(“ 结果为:F(x)=f(x)+g(x)=”); f=add(f,g); print(f); printf(“nn”); printf(“ 继续请选择相应操作,退出请按0.break; } case 2://多项式相减 { printf(” 你选择的操作是多项式相减:n“); printf(” 请输入第一个多项式f(x):“); f=creat('f'); printf(” 第一个多项式为:f(x)=“); print(f); printf(” 请输入第二个多项式g(x):“); g=creat('g'); printf(” 第二个多项式为:g(x)=“); print(g); printf(” 结果为:F(x)=f(x)-g(x)=“); f=sub(f,g); print(f); ”);第16页 山东科技大学学生课程设计 printf(“nn”); printf(“ 继续请选择相应操作,退出请按0.”); break; } case 3://多项式相乘 { printf(“ 你选择的操作是多项式相乘:n”); printf(“ 请输入第一个多项式f(x):”); f=creat('f'); printf(“ 第一个多项式为:f(x)=”); print(f); printf(“ 请输入第二个多项式g(x):”); g=creat('g'); printf(“ 第二个多项式为:g(x)=”); print(g); printf(“ 结果为:F(x)=f(x)* g(x)=”); pf=mul(f,g); print(pf); printf(“nn”); printf(“ 继续请选择相应操作,退出请按0.”); break; } case 4://多项式求导 { printf(“您选择的是对一个一元多项式求导:n”); printf(“请输入一个一元多项式:”); f = creat('f'); printf(“这个多项式为:f(x)= ”); print(f); printf(“求导结果为:F(x)=f'(x)= ”); f=der(f); print(f); printf(“nn”); printf(“ 继续请选择相应操作,退出请按0.”); break; } }//swith }//while }//void 四、测试结果: 第17页 山东科技大学学生课程设计 第18页 南京航空航天大学金城学院 《数据结构》 课程设计报告 题目:一元多项式的加减乘法运算 班级: 20100232 学号: 2010023220 姓名: 祁博 成绩: 指导教师: 叶延风 完成日期: 2012年 2月18 日 课程设计的主要内容 需求分析 1.1课程设计题目 用线性表实现一元多项式的加法减法与乘法。 1.2课程设计的任务及要求 任务:利用所学线性表知识来完成计算器中一元多项式的加法减法与乘法的运算。要求:能自己创建线性表,能自主的进行线性表的有关插入删除操作,并且可以在此基础上实现线性表之间的加减乘除运算。 1.3课程设计思想 首先要定义一个结构体,其中定义一元多项式的两个参数,系数和指数和链表中的指针域,然后一一罗列每个在主程序中得到的函数,并一一实现,最后在主程序中主要完成用户的输入和相关程序的调用。 1.4软件开发的环境 VC++6.0。 2.程序源代码 #include typedef struct node{//定义节点类型 float coef;int expn; struct node * next;}Ployn; void menu()//用户选择界面 { printf(“************************************n”); printf(“ 两个一元多项式的相加/相减,相乘:n”); printf(“************************************n”); printf(“请选择操作:n”); printf(“0.退出n”); printf(“1.两个一元多项式相加n”); printf(“2.两个一元多项式相乘n”); printf(“3.两个一元多项式相减n”); } void insert(Ployn *head,Ployn *inpt)//查找位置插入新链节程序 { Ployn *pre,*now; int signal=0; pre=head;//pre定义为现在的前一个链节 if(pre->next==NULL){pre->next=inpt;} else {now=pre->next;while(signal==0){ if(inpt->expn>now->expn)//当新链节小于现在的连接时向后移一个链节 { if(now->next==NULL) { now->next=inpt; signal=1; } else { pre=now; now=pre->next; } } else if(inpt->expn { inpt->next=now; pre->next=inpt; signal=1; } else { now->coef=now->coef+inpt->coef; signal=1; free(inpt);//与当前链节相等指数 if(now->coef==0) { pre->next=now->next; free(now); } } } } } Ployn *creat(char ch)//输入多项式 { Ployn *head,*inpt; float x; int y; head=(Ployn *)malloc(sizeof(Ployn));//创建链表头 head->next=NULL; printf(“请输入一元多项式%c:(格式是:系数 指数;以0 0 结束!)n”,ch); scanf(“%f %d”,&x,&y); while(x!=0) { inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节 inpt->coef=x; inpt->expn=y; inpt->next=NULL; insert(head,inpt);//不然就查找位置并且插入新链节 printf(“请输入一元多项式%c的下一项:(以0 0 结束!)n”,ch); scanf(“%f %d”,&x,&y); } return head;} Ployn *addPloyn(Ployn *head,Ployn *pre)//多项式相加 { Ployn *inpt; int flag=0; while(flag==0) { if(pre->next==NULL) flag=1;//当现在指向空时跳出循环 else { pre=pre->next; inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节 inpt->coef=pre->coef; inpt->expn=pre->expn; inpt->next=NULL; insert(head,inpt); }//否则把当前“g(x)”的链节插入到“y(x)”中 } return head;} Ployn *minusPloyn(Ployn *head,Ployn *pre)//多项式相加 { Ployn *inpt; int flag=0; while(flag==0) { if(pre->next==NULL) flag=1;//当现在指向空时跳出循环 else { pre=pre->next; inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节 inpt->coef=0-pre->coef; inpt->expn=pre->expn; inpt->next=NULL; insert(head,inpt); }//否则把当前“g(x)”的链节插入到“y(x)”中 } return head;} Ployn *byPloyn(Ployn *head1,Ployn *head2)//多项式相乘 { Ployn *inpt,*res,*pre; int flag=0; res=(Ployn *)malloc(sizeof(Ployn));//创建链表头 res->next=NULL; head1=head1->next; pre=head2; while(flag==0) { if(pre->next==NULL) { pre=head2;//当现在指向空时跳出循环 head1=head1->next; continue; } if(head1==NULL) { flag=1;//当现在指向空时跳出循环 continue; } pre=pre->next; inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节 inpt->coef=pre->coef*head1->coef; inpt->expn=pre->expn+head1->expn; inpt->next=NULL; insert(res,inpt);//把当前“g(x)”的链节插入到“y(x)”中 } return res;} void print(Ployn *fun)//输出多项式 { Ployn *printing; int flag=0; printing=fun->next;//正在被打印的链节 if(fun->next==NULL)//如果函数为空打印0 { printf(“0n”); return;} while(flag==0) { if(printing->coef>0 && fun->next!=printing) printf(“+”);//为正数且不为第一项时打印“+”号 if(printing->coef==1);//如果为“1”就不用打印系数了 else if(printing->coef==-1) printf(“-”);//如果为“-1”就打印“-”号就行了 else printf(“%f”,printing->coef);//其余情况都得打印 if(printing->expn!=0)//如果指数为“0”不打印指数项 { if(printing->expn==1)printf(“x”); else printf(“x^%d”,printing->expn); } else if((printing->coef==1)||(printing->coef==-1)) printf(“1”); if(printing->next==NULL) flag=1;//如果现在的链节没有下一个就结束 else printing=printing->next; } printf(“n”);} void main(){ Ployn *f,*g; int sign=-1;//设置标志 menu(); while(sign!=0) { scanf(“%d”,&sign); switch(sign){ case 0: break;//退出 case 1: { printf(“你选择的操作是多项式相加:n”); f=creat('f');//输入多项式f(x) printf(“f(x)=”); print(f); g=creat('g');//输入多项式g(x) printf(“g(x)=”); print(g); printf(“F(x)=f(x)+g(x)=”); f=addPloyn(f,g);//两个多项式相加 print(f); sign=-1;//复位标志 menu();//回复用户选择界面 break; } case 2: { printf(“你选择的操作是多项式相乘:n”); f=creat('f');//输入多项式f(x) printf(“f(x)=”); print(f); g=creat('g');//输入多项式g(x) printf(“g(x)=”); print(g); printf(“F(x)=f(x)*g(x)=”); f=byPloyn(f,g);//两个多项式相加 print(f); sign=-1;//复位标志 menu();//回复用户选择界面 break; } case 3: { printf(“你选择的操作是多项式相减:n”); f=creat('f');//输入多项式f(x) printf(“f(x)=”); print(f); g=creat('g');//输入多项式g(x) printf(“g(x)=”); print(g); printf(“F(x)=f(x)-g(x)=”); f=minusPloyn(f,g);//两个多项式相加 print(f); sign=-1;//复位标志 menu();//回复用户选择界面 break; } default: { printf(“输入有误!请重新选择操作!n”);//选择错误,返回选择界面 menu(); break; } } } } 3.心得体会 每次做课设都有很大的收获。课设不仅是对课本知识的理论实践,更是对自我的一种挑战。 这次课设过程中,遇到很多的问题,让我有种无从下手的感觉,但是办法总比困难多,于是,在老师、同学的帮助下,以及自己在翻书、上网找资料的情况下,顺利解决问题。于是,我又上课的认识到,团队的重要性。 河海大学计算机与信息学院(常州) 数据结构课程设计 课程设计题目: 多 项 式 问 题 专业、年级:计算机科学与技术09级 学 号: 0962810226 姓 名: 王 超 目 录 一、问题描述-------------3 二、需求分析-------------4 三、概要设计-------------4 1.概要设计目的与要求--4 2.概要设计内容--------4 3.功能算法描述与数据结构说明-------------------------5 四、详细设计-------------5 五、系统测试-------------8 六、使用说明-------------9 七、总结及心得体会-----10 多项式问题 一.问题描述 给你九个整数,这九个整数分别是x的8次方至0次方的系数,请你按照多项式的一半形式合理地构造(去除不必要的)。例如九个系数分别是为0,0,0,1,22,-333,0,1,-1,你要构造并输出一行多项式:x^5 + 22x^4 – 333x^3 + x – 1。 它的格式规则如下: 1.多项式的项必须按其指数从高到低排列。2.指数必须跟在符号“^”后显示。3.有常数的只显示常数项(无需跟x^0)。 4.只显示系数不为0的项;若系数全为0,需显示常数项。 5.在多项式中唯一需要空格的地方是项与项之间的加号或减号的两边需加上空格。 6.如果首项的系数是正数,则系数前不加符号;如果首项的系数是负数,则符号与数字之间不加空格,就如:-3x^2 +-2x。 7.系数为1,指数为0时,系数的1才显示(推广到系数为-1)。 输入/输出说明 1.输入/输出方式为文件方式,输入文件有一行或多行的系数,系数之间有空格分隔。 2.每行共有九个系数,每个系数的绝对值为小于1000的整数。输出文件包含构造完地多项式,每行一个多项式。 输入范例 0 0 0 1 22-333 0 1-1 0 0 0 0 0 0-55 5 0 输出范例 x^5 + 22x^4 – 333x^3 + x – 1-55x^2 + 5x 二.需求分析 2.1可行性研究 该程序主要从技术的角度来分析可行性。技术上的可行性研究主要分析技术条件能否顺利完成开发工作,硬、软件能否满足开发者的需要等。该系统采用了Windows 7操作系统结合Visual C++ 6.0等软件开发平台已成熟可行。硬件方面,科技飞速发展的今天,硬件更新的速度越来越快,容量越来越大,可靠性越来越高,其硬件平台也比较能满足此系统的需要。 2.2结构与主要功能模块 从实现多项式输出过程的角度来分析,至少需要这样一些子功能模块。如: 1.多项式创建功能; 2.多项式输出功能; 3.释放多项式功能; 4.操作界面显示功能; 三.概要设计 1.概要设计目的与要求 通过多项式程序设计,使我们进一步掌握和利用C++语言进行结构化程序设计的能力;进一步理解和运用结构化程设计的思想和方法;初步掌握开发一个小型系统程序设计的基本方法;学会调试一个较长程序的基本方法;以及掌握书写课程设计开发文档的能力(书写课程设计报告)。总之,通过本课程设计加深对《C++语言》及《数据结构》课程所学知识的理解,进一步巩固C++语言语法规则,在程序中体现出算法的思想,提高程序的运行效率。学会编制结构清晰、风格良好、数据结构适当的C++语言程序,从而具备解决综合性实际问题的能力。 2.概要设计内容 多项式输出程序具有以下基本功能: 1.创建多项式。接收输入的数据,并保存到链表中。 2.Txt文档输入输出功能。 3. 清除内存内容,释放创建的链表,退出程序。 3.功能算法描述与数据结构说明 该多项式程序除了main()函数外,主要有以下函数: node *CreatePolyn() void firstnode(node *p) void othernode(node *p) void PrintPolyn(node *Pa) void deletechain(node *h) 下面对这些函数逐一介绍。①.main()函数 main函数主要调用其他函数,用来实现输入、显示功能。 在main()函数中,定义一维数组p[]用来保存多项式的系数,Pa定义程序所需链表的头指针。在程序开始要求输入多项式的系数,随后创建链表以保存多项式,再显示出构建的符合要求的多项式。②.node *CreatePolyn()该函数功能是创建新的多项式链表。使用for语句,控制输入多项式的每一项。 ③.void firstnode(node *p)该函数功能是判断输出多项式第一项。对于第一项的系数为1或-1,指数为0或-1等五种情况进行讨论。④.void othernode(node *p)该函数功能是判断输出多项式除第一项外的其它项。对于第一项的系数为1或-1,指数为0或-1等五种情况进行讨论。⑤.void PrintPolyn(node *Pa)该函数功能:显示构造的符合要求的多项式链表。在该函数中调用③、④函数,进行多项式的输出。⑥.void deletechain(node *h)该函数的功能是释放掉创建的链表,释放内存。 四.详细设计 下面讨论重要函数具体实现过程: 1.node *CreatePolyn()定义int i=9计数,当i>0时,for语句反复提示用户输入该多项式的每一项的指数。当i=1时,输入完毕,该链表也创建完毕。详细的实现过程如下: node *CreatePolyn(){ node *head,*pa,*s;int i; pa=head=new node;//创建一个新的结点 head->next=NULL; for(i = 9;i >0;i--)// 依次输入9项 { s=new node; s->next=NULL; s->coef = p[9-i]; s->exp=i-1;//x指数从8递减到0 if(s->coef!=0)//系数不为零时,结点p链接s { pa->next=s; pa=s; } } return head;} 2.void firstnode(node *p)对多项式第一项输出可能性进行多种分类讨论。 void firstnode(node *p)//输出多项式第一个结点 { //指数不为1且不为0,系数绝对值不为1(正常的输出)if(p->exp!=1&&p->exp&&fabs(p->coef)!=1) { if(p->coef>0) { outfile< coef<<“X^”< exp; } else { outfile< coef<<“X^”< exp; } } if(p->exp==0)//指数为0,即常数项 { if(p->coef>0) { outfile< coef; } else { outfile< coef; } } //指数大于0且不为1,系数绝对值为1 if(p->exp>0&&fabs(p->coef)==1&&p->exp!=1){ if(p->coef>0) { outfile<<“X^”< exp; } else { outfile<<“-X^”< exp; } } if(p->exp==1&&fabs(p->coef)!=1)//指数为1且系数绝对值不为1 { if(p->coef>0&&p->coef!=1) { outfile< coef<<“X”; } if(p->coef<0&&p->coef!=-1) { outfile< coef<<“X”; } } if(p->exp==1&&fabs(p->coef)==1)//指数为1且系数绝对值为1 { if(p->coef==1) outfile<<“X”; else outfile<<“-X”;} } 3.void PrintPolyn(node *Pa)该函数有一个参数,该指针指向多项式链表的头指针,以下是实现插入的关键代码: void PrintPolyn(node *Pa){ node *p;if(Pa->next==NULL)//首项判断,如果首项无,则显示“0” outfile<<“0”; return;else { firstnode(Pa->next);} p=Pa->next->next;//定义指针p指向Pa的下下个指针 while(p!=NULL){ othernode(p); p=p->next; //将p指向下个一个结点 } outfile< 五.系统测试 该程序在VC6.0中调试通过,没有错误和警告,运行结果经过检验为正确。以下图为该程序运行结果效果图: 图5-1 范例 图5-2 一行输出 图5-3 多行输出 六.使用说明 1.打开1.txt文件,在里面任意输入9个整数,每个数字间要有空格,可以输入一行或者多行,输入多行的时候需要换行。 2.编译运行后,打开2.txt文件,即可看到输出的符合要求的多项式。 七.总结及心得体会 通过这次课程设计练习,使我更深刻地理解了C++语言的精髓-----指针的使用。完成整个程序设计有很大的收获,对指针掌握的更加熟练。 同时通过直接对单链表的操作,加深了对数据结构的理解和认识。并在完成课程设计的过程作主动查阅了相关资料,学到了不少课本上没有的技术知识。 经过这次课程设计,我深刻认识到算法在程序设计中的重要性,如何让程序简单、易读是这个课程设计的难点。程序总是由若干个函数构成的,这些相应的函数体现了算法的基本思想。 编程是一件枯燥乏味工作,但是只要认真专研,我们会从中学到很多在课本上学不到或者无法在课堂上掌握的知识,同时也能从中感受到编程的乐趣。兴趣是可以培养的,只要坚持下去,面对困难我们总能够找到解决问题的方法。 计算多项式的输出-----该程序虽然不是很大,但是自己独立完成这一任务也遇到不少的困难。另外也需要提出的是,非常感谢老师对我们的耐心指导,尤其是上机的时候给了我很多锻炼的机会。所以这次课程设计我才能够顺利的完成。第二篇:数据结构24点游戏源代码
第三篇:数据结构课程设计
第四篇:数据结构课程设计
第五篇:数据结构课程设计