《数据结构》上机题（C语言程序）北京科技大学数据结构上机实验ivince上机题1．输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。

例如输入：2 6 4 7 3 0（0为结束符），建立：所求结果=4程序结构：类型说明；建表函数：Creatlist(L); 求值函数：Adjmax(L);main( ){ 变量说明；调用Creatlist(L)建表；调用Adjmax(L)求值；打印数据；释放链表空间；Y 继续？N停止}//ivince//启动程序后输入字符（每输入一个字符，都要回车结束），如果字符不是"@"和"0"，字符就会进队。

输入"0",则队头元素出队；输入"@",所有元素出队。

//特殊情况：直接输入"0"，或直接输入"@"都已经做了相应处理#include<stdio.h>#include<malloc.h>typedefstruct node{charch;struct node* next;}Qnode,*Qlink;typedefstruct{Qnode *front,*rear;}linkqueue;voidCreatqueue(linkqueue *q){q->front=(Qlink)malloc(sizeof(Qnode));q->front->next=NULL;q->rear=q->front;}intEmptyqueue (linkqueue *q) //判队空{if(q->front==q->rear)return(1);elsereturn (0);}void Enqueue(linkqueue *q,char e) //元素e进队{Qlink p=(Qlink)malloc(sizeof(Qnode)); //申请进队节点p->ch=e;p->next=NULL;q->rear->next=p;q->rear=p;}intDequeue(linkqueue *q) //出队{Qlink p;if (Emptyqueue(q))return(NULL); //队空处理else{p=q->front ;q->front=p->next ;free(p);return(q->front->ch);}}void main(void) //主函数{linkqueue q;charch='0',ch2;Creatqueue(&q);printf("请输入字符，字符0出队字符@全部出队：\n");while(ch!='@'){scanf("%c",&ch);fflush(stdin); //清除缓存字符if(ch=='0'){ch2=Dequeue(&q);if(ch2!=NULL)printf("%c\n",ch2);elseprintf("目前队列中不存在任何元素!,请您先存入!!\n");}else if(ch=='@'){while(!Emptyqueue(&q)){printf("%c\n",Dequeue(&q));}}elseEnqueue(&q,ch);}}上机题2.实现算术表达式求值程序（栈的运用）。

设操作数：0，1，2，……，8，9（可扩充）；运算符：+，－，*，/，（，），#（#号为结束）。

输入中缀表达式，如：5+(4－2)*3 #，将其转换成后缀表达式：542－3*+#，然后计算，本例结果为11。

程序结构：类型说明；函数：Clearstack(S)、Emptystack(S)、Getstop(S)、Push(S)、Pop(S)；中缀到后缀转换的函数：Mid-post(E[n]，B[n])；后缀表达式求值的函数：Postcount(B[n])；main（）{ 变量说明；输入中缀表达式，存入E[n]；调用Mid-post(E，B)；调用Postcount(B)；打印表达式结果；Y 继续？N停止}//ivince//该程序用于计算正整数的+ - * / () 运算，输入正确的表达式并以#结尾，//只输入#将输出-1，运算过程出现分母为0的情况将终止程序//按要求输入数据后，程序自动将中缀表达式转换为后缀表达式，并将其输出出来，计算结果下一行输出//该程序用了一个栈存数据，一个栈存运算符，所以可以实现int范围内的正整数的和差积商的计算#include<stdio.h>#include<malloc.h>#include<math.h>#include<windows.h>//数据栈typedefstruct node1{int date1;struct node1* next1;}snode1,*slink1;int Emptystack1(slink1 S){if(S==NULL)return(1);else return(0);}int Pop1(slink1* top){int e;slink1 p;if(Emptystack1(*top))return(-1);else{e=(*top)->date1;p=*top;*top=(*top)->next1;free(p);return(e);}}void Push1(slink1* top,int e){slink1 p;p=(slink1)malloc(sizeof(snode1));p->date1=e;p->next1=*top;*top=p;}int Getstop1(slink1 S){if(S!=NULL)return(S->date1);return 0;}void Clearstack1(slink1* top){ slink1 p;while(*top!=NULL){p=(*top)->next1;Pop1(top);*top=p;}}//字符栈typedefstruct node{char date;struct node* next;}snode,*slink;intEmptystack(slink S){if(S==NULL)return(1);else return(0);}char Pop(slink* top){char e;slink p;if(Emptystack(*top))return(0);else{e=(*top)->date;p=*top;*top=(*top)->next;free(p);return(e);}}void Push(slink* top,char e){slink p;p=(slink)malloc(sizeof(snode));p->date=e;p->next=*top;*top=p;}voidClearstack(slink* top){ slink p;while(*top!=NULL){p=(*top)->next;Pop(top);*top=p;}*top=NULL;}charGetstop(slink S){if(S!=NULL)return(S->date);return 0;}int Precede(char x,char y){switch(x){case '#':x=0;break;case '(':x=1;break;case '+':case '-':x=2;break;case '*':case '/':x=3;break;}switch(y){case '+':case '-':y=2;break;case '*':case '/':y=3;break;case '(':y=4;break;}if(x>=y)return 1;else return 0;}voidmid_post(char post[],char mid[]){inti=0,j=0;char x;slink S=NULL;Push(&S,'#');do{x=mid[i++];switch(x){case '#':{while(!Emptystack(S)){if(post[j-1]<='9'&&post[j-1]>='0')post[j++]=' ';post[j++]=Pop(&S);}}break;case ')':{while(Getstop(S)!='('){if(post[j-1]<='9'&&post[j-1]>='0')post[j++]=' ';post[j++]=Pop(&S);}if(post[j-1]<='9'&&post[j-1]>='0')post[j++]=' ';Pop(&S);}break;case '+':case '-':case '*':case '/':case '(':{while(Precede(Getstop(S),x)){if(post[j-1]<='9'&&post[j-1]>='0')post[j++]=' ';post[j++]=Pop(&S);}if(post[j-1]<='9'&&post[j-1]>='0')post[j++]=' ';Push(&S,x);}break;default:post[j++]=x;}}while(x!='#');post[j]='\0';Clearstack(&S);}intpostcount(char post[]){inti=0,m=0,sum=0,j=0;char x;intz,a,b;slink S=NULL;slink1 S1=NULL;while(post[i]!='#'){x=post[i];switch(x){case '+':b=Pop1(&S1);a=Pop1(&S1);z=a+b;Push1(&S1,z);sum=0;m=0;j=0;break;case '-':b=Pop1(&S1);a=Pop1(&S1);z=a-b;Push1(&S1,z);sum=0;m=0;j=0;break;case '*':b=Pop1(&S1);a=Pop1(&S1);z=a*b;Push1(&S1,z);sum=0;m=0;j=0;break;case '/':b=Pop1(&S1);if(b==0){printf("运算过程中出现分母为0的状况\n");exit(0);}a=Pop1(&S1);z=a/b;Push1(&S1,z);sum=0;m=0;j=0;break;case ' ':while(j!=m){sum=sum+Pop1(&S1)*pow(10,j);j++;}Push1(&S1,sum);sum=0;m=0;j=0;break;default :x=post[i]-'0';Push1(&S1,x);m++;}i++;}sum=Pop1(&S1);Clearstack1(&S1);return sum;}void main(){int sum=0;char post[255],mid[255];char x='Y';printf("注意: 该程序无法检查表达式的正确性,输入不合法表达式将出现错误的结果!!!\n");while(x=='Y'||x=='y'){printf("请输入要处理的中缀表达式：\n");scanf("%s",mid);printf("相应的后缀表达式为：\n");mid_post(post,mid);printf("%s\n",post);sum=postcount(post);printf("表达式的值为：%d\n",postcount(post));printf("继续？y/n\n");scanf("%c",&x);scanf("%c",&x);}}上机题3.实现链式队列运算程序（队列的运用）。