数据结构的c语言算法(doc63)-经营管理(编辑修改稿)

数据结构的c语言算法(doc63)-经营管理(编辑修改稿)内容摘要：

后退出循环 */ { prelink=xor(r,NULL)。 /*将 slink 置为前后节 点地址之异或 */ *e=pre。 break。 } s=(dlist *)malloc(sizeof(dlist))。 /*创建一个节点 */ sdata=x。 if(i==1)/*是第一个节点的情况 */ { pre=head=s。 r=NULL。 /*r 为当前节点的前一个节点 */ } else { prelink=xor(r,s)。 /*将 slink 置为前后节点地址之异或 */ r=pre。 pre=s。 } i++。 } return head。 } void order(dlist *h,dlist *e) { dlist *pre=NULL,*pre1,*p=h。 printf(遍历节点序列 : )。 if(h==NULL) printf(空表 \n)。 else { while(p!=e)/*遍历最后一节点前的所有节点 */ { printf(%d ,pdata)。 pre1=p。 p=xor(pre,plink)。 /*为下一个节点的地址 */ pre=pre1。 17 } printf(%d ,edata)。 printf(\n)。 } } void main() { dlist *h,*e。 int i。 h=create(amp。 e)。 printf(从左向右 )。 order(h,e)。 printf(从右向左 )。 order(e,h)。 } /*运行结果 : 创建一个双链表 (以 0 结束 ) 输入第 1 节点值 :3 输入第 1 节点值 :5 输入第 1 节点值 :8 输入第 1 节点值 :2 输入第 1 节点值 :6 输入第 1 节点值 :0 从左向右遍 历节点序列 : 3 5 8 2 6 从右向左遍历节点序列 : 6 2 8 5 3 */ 第三章 栈和队列 实现栈基本算法的头文件 为： include define MaxLen 20/*顺序栈存放的最多元素个数为 Maxlen1*/ typedef char elemtype。 typedef struct sqstack { elemtype data[MaxLen]。 int top。 }stack。 void init(stack *st)/*初始化栈 st*/ { sttop=0。 } int push(stack *st,elemtype x)/*入栈 */ { if(sttop==MaxLen1) { printf(栈溢出 \n)。 18 return 0。 } else { sttop++。 stdata[sttop]=x。 return 1。 } } int pop(stack *st,elemtype *x)/*退栈 */ { if(sttop==0) { printf(栈下溢出 \n)。 return 0。 } else { *x=stdata[sttop]。 sttop。 return 1。 } } int empty(stack *st)/*判断栈空 */ { if(sttop==0) return 1。 else return 0。 } int gettop(stack *st,elemtype *x)/*获取栈顶元素 */ { if(sttop==0) { printf(栈下溢出 \n)。 return 0。 } else { *x=stdata[sttop]。 return 1。 } } void disp(stack *st)/*输出栈的所有元素 */ 19 { int i。 for(i=sttop。 i0。 i) printf(%d ,stdata[i])。 printf(\n)。 } /*练习 */ /*假设一个算术表达式中可以包含三种括号，圆括号 (和 )、方括号 [和 ]和花括号 {和 },且这三种括号可按任意的次序嵌套使用 (如 :..[..{..}..[..]..]..[..]..(..)..).编写判别给定表达式中所含括号是否正确配对出现的算法 (已知表达式已存入数据元素为字符的顺序表中 */ /*输入： {a+[b+(c+d)+e]+f}*/ include include int correct(char *str) { stack st。 char x。 int i,ok=1。 init(amp。 st)。 for(i=0。 str[i]!=39。 \039。 i++) { switch(str[i]) { case39。 (39。 :push(amp。 st,39。 (39。 )。 break。 case39。 [39。 :push(amp。 st,39。 [39。 )。 break。 case39。 {39。 :push(amp。 st,39。 {39。 )。 break。 case39。 )39。 :if(!(pop(amp。 st,amp。 x)amp。 amp。 x==39。 (39。 )) ok=0。 break。 case39。 ]39。 :if(!(pop(amp。 st,amp。 x)amp。 amp。 x==39。 [39。 )) ok=0。 break。 case39。 }39。 :if(!(pop(amp。 st,amp。 x)amp。 amp。 x==39。 {39。 )) ok=0。 break。 } if(!ok) break。 } if(empty(amp。 st)amp。 amp。 ok) return 1。 else return 0。 } void main() { 20 char *str。 str=(char*)malloc(100*sizeof(char))。 printf(str: )。 scanf(%s,str)。 if(correct(str)) printf(表达式括号匹配 \n)。 else printf(表达式括号不匹配 \n)。 getch()。 }练习 include define MaxLen 100 int trans(char str[],char exp[]) { int st[MaxLen]。 /*作为栈使用 */ char ch。 int i=0,t=0,top=1。 /*t 作为 exp 的下标， top 作为 st的下标， i 作为 str 的下标 */ while((ch=str[i++])!=39。 \039。 ) { if(ch=39。 039。 amp。 amp。 ch=39。 939。 )/*判断为数字 */ { exp[t]=ch。 t++。 while ((ch=str[i++])!=39。 \039。 amp。 amp。 ch=39。 039。 amp。 amp。 ch=39。 939。 ) { exp[t]=ch。 t++。 } i。 exp[t]=39。 39。 t++。 } else if(ch==39。 (39。 )/*判断为左括号 */ { top++。 st[top]=ch。 } else if(ch==39。 )39。 )/*判断为右括号 */ { while(st[top]!=39。 (39。 ) { exp[t]=st[top]。 top。 t++。 } top。 } else if(ch==39。 +39。 ||ch==39。 39。 )/*判断为加减号 */ 21 { while(top=0 amp。 amp。 st[top]!=39。 (39。 ) { exp[t]=st[top]。 top。 t++。 } top++。 st[top]=ch。 } else if(ch==39。 *39。 ||ch==39。 /39。 ) { while (st[top]==39。 *39。 || st[top]==39。 /39。 ) { exp[t]=st[top]。 top。 t++。 } top++。 st[top]=ch。 } } while(top=0) { exp[t]=st[top]。 t++。 top。 } exp[t]=39。 \039。 return 1。 } int pvalue(char exp[],int *n) { int st[MaxLen],d。 /*作为栈使用 */ char ch。 int t=0,top=1。 /*t 作为 exp 的下标， top 作为 st 的下标 */ while ((ch=exp[t+1])!=39。 \039。 ) { if(ch=39。 039。 amp。 amp。 ch=39。 939。 )/*为数字字符时转换为数字 */ { d=0。 do { d=10*d+ch39。 039。 }while((ch=exp[t++])!=39。 39。 )。 top++。 st[top]=d。 /*数字进栈 */ } else /*为运算符时，计算并退栈 */ { switch(ch) { case39。 +39。 :st[top1]=st[top1]+st[top]。 break。 22 case39。 39。 :st[top1]=st[top1]st[top]。 break。 case39。 *39。 :st[top1]=st[top1]*st[top]。 break。 case39。 /39。 :if(st[top]!=0) st[top1]=st[top1]/st[top]。 else return 0。 /*除 0 错误 */ break。 } top。 } } (*n)=st[top]。 return 1。 } void main() { char str[MaxLen]。 /*存储原算术表达式 */ char exp[MaxLen]。 /*存储转换成的波兰表达式 */ int n。 printf(算术表达式 : )。 scanf(%s,amp。 str)。 if(trans(str,exp)==0) printf(原算术表达式不正确 \n)。 else { printf(波兰表达式 : %d\n,exp)。 if(pvalue(exp,amp。 n)==1) printf(计算结果 : %d\n,n)。 else printf(计算错误 \n)。 } } 练习 /*已知 Ackerman 函数的定义如下： Akm(m,n)=n+1(m=0),akm(m1,1)(m!=0,n=0) akm(m1),akm(m,n1))(m!=0,n!=0) ； 2。 写出非递归算法； 3。 根据非递归算法，画出求 akm(2,1)时栈的变化过程 */ include define MaxLen 5000/*此数应足够大，因为 m和 n值的较小增长会引起函数值的极快增长，用的栈的空间也很大 */ int f1(int m,int n) { if(m==0) return n+1。 else if(n==0) return f1(m1,1)。 23 else return f1(m1,f1(m,n1))。 } int no(int m,int n) { if(m==0) return 1。 else if(n==0) return 2。 else return 3。 } int f2(int m,int n) { int st[MaxLen][4],top=1,m1,n1。 st[top][0]=no(m,n)。 st[top][1]=0。 /*初值 0 进栈 */ st[top][2]=m。 /*初值 m 进栈 */ st[top][3]=n。 /*初值 n 进栈 */ do /*开始循环 */ { if(st[top][1]==0)。