1、<p>　　算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p>　　專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　學(xué)號(hào)： </p><p>　　姓名： </p><p>　　題目：1.用鏈表求解約瑟夫問題。</p><p>　　算法思路：由于約瑟夫問題是n個(gè)人圍坐

2、一圈，所以采用偱環(huán)鏈表實(shí)現(xiàn)，又由于報(bào)數(shù)時(shí)可能循環(huán)到開始，所以采用不帶頭結(jié)點(diǎn)的循環(huán)鏈表結(jié)構(gòu)。</p><p><b>　　算法步驟：</b></p><p>　　a在不帶頭結(jié)點(diǎn)的循環(huán)鏈表中查找第s個(gè)結(jié)點(diǎn)的指針。</p><p>　　b從p所指胡結(jié)點(diǎn)開始計(jì)數(shù)查找第m個(gè)結(jié)點(diǎn)，pre指向p的前驅(qū)。</p><p>　　c輸出該結(jié)

3、點(diǎn)元素值。</p><p>　　D刪除該結(jié)點(diǎn)，同時(shí)將該結(jié)點(diǎn)下一結(jié)點(diǎn)指針作為當(dāng)前指針即p指針，重復(fù)到步驟b,直到鏈表中所有結(jié)點(diǎn)都被刪除完為止。</p><p><b>　　算法分析：</b></p><p>　　int josephus_LinkList (LinkList josephus_Link,int s,int m)</p>

4、<p><b>　　{</b></p><p>　　LinkList p,pre;</p><p>　　int count;</p><p>　　if(!josephus_Link)</p><p>　　{ printf(“表中無元素”)}；</p><p>　　Return(0);

5、</p><p><b>　　}</b></p><p>　　P=josephus_Link;</p><p>　　For(count=1;count<s;count++)</p><p>　　p=p->next;</p><p>　　printf(“輸入約瑟夫序列：”);</p

6、><p>　　while(p!=p->next)</p><p>　　{for(count=1;count<m;count++)</p><p><b>　　{pre=p;</b></p><p>　　p=p->next;}</p><p>　　printf(“%d\t”,p->

7、;data);</p><p>　　pre->next=p->next;</p><p><b>　　free(p);</b></p><p>　　p=pre->next;</p><p>　　printf(“%d\t”,p->data);</p><p><b>

8、;　　free（p）;</b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>　　程序源代碼：</b></p><p>　　#include"stdlib.h"</p

9、><p>　　#include"stdio.h"</p><p>　　typedef struct node</p><p>　　{int data;</p><p>　　struct node *next;</p><p><b>　　} Lnode;</b></p>

10、<p>　　Lnode *create(int n)</p><p><b>　　{ int i;</b></p><p>　　Lnode*h,*p,*r=(Lnode*)malloc(sizeof(Lnode));</p><p>　　r->data=n;h=r;</p><p>　　for(i=n

11、-1;i>0;i--)</p><p>　　{p=(Lnode*)malloc(sizeof(Lnode));</p><p>　　p->data=i; </p><p>　　p->next=h; </p><p><b>　　h=p;</b></p><p><

12、b>　　} </b></p><p>　　r->next=h; </p><p><b>　　return h;</b></p><p><b>　　}</b></p><p>　　void jeseph(Lnode *p,int m)</p><p&

13、gt;　　{ Lnode *q; </p><p><b>　　int j=0;</b></p><p>　　printf("outqueue order:");</p><p><b>　　do {</b></p><p><b>　　j++;</b>&l

14、t;/p><p>　　if(j==m-1)</p><p>　　{q=p->next;</p><p>　　p->next=q->next;</p><p>　　printf("%d",q->data);</p><p>　　j=0;free(q);}</p>&l

15、t;p>　　p=p->next;</p><p>　　} while(p->next!=p);</p><p>　　printf("%d\n",p->data);</p><p><b>　　free(p);</b></p><p><b>　　} </b&g

16、t;</p><p>　　void main()</p><p>　　{ Lnode *h; </p><p><b>　　int m,n;</b></p><p>　　printf("\n input n,m=");</p><p>　　scanf("%d,%d&

17、quot;,&n,&m);</p><p>　　h=create(n);</p><p>　　jeseph(h,m);</p><p><b>　　}</b></p><p><b>　　運(yùn)行結(jié)果：</b></p><p><b>　　2.表達(dá)式求值

18、。</b></p><p>　　表達(dá)式求值是程序設(shè)計(jì)語言編譯中一個(gè)最基本的問題。它的實(shí)現(xiàn)也是棧的應(yīng)用中的一個(gè)典型的例子。</p><p>　　任何一個(gè)表達(dá)式都是由操作數(shù)，運(yùn)算符和界限符組成的有意義的式子。一般地，操作數(shù)既可以是常數(shù)，也可以是變量或常量。運(yùn)算符從運(yùn)算對(duì)象的個(gè)數(shù)上分，有單目運(yùn)算符、雙目運(yùn)算符和三目運(yùn)算符；從運(yùn)算類型上分，有算數(shù)運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符。界限符有

19、左右括號(hào)和表達(dá)式結(jié)束符等。運(yùn)算符、界限符統(tǒng)稱為算符。為簡單化，在這里，僅限于討論只含二目運(yùn)算符的加、減、乘、除算數(shù)表達(dá)式，并且操作數(shù)為一位字符表示的整數(shù)。</p><p><b>　　算法分析：</b></p><p>　　typedef double DataType;</p><p>　　int IsNum(char c)</p>

20、;<p><b>　　{</b></p><p>　　if(c>=’0’&&c<=’9’)return(1);</p><p>　　else return(0);</p><p><b>　　}</b></p><p>　　double postfix_ex

21、p(char*A)</p><p><b>　　{</b></p><p>　　PSeqStack S;</p><p>　　double Result,a,b,c;char ch;</p><p><b>　　ch=*A++;</b></p><p>　　S=Init_Se

22、qStack();</p><p>　　while (ch!=’#’)</p><p>　　{if (IsNum(ch)) Push_SeqStack(S,ch-‘0’);</p><p><b>　　Else</b></p><p>　　{Pop_SeqStack(S,&b);</p><p

23、>　　Pop_SeqStack(S,&a);</p><p>　　switch(ch)</p><p>　　{case ‘+’: c=a+b;break;</p><p>　　case ‘-’: c=a-b;break;</p><p>　　case ‘*’: c=a*b;break;</p><p>　

24、　case ‘/’: c=a/b;break;</p><p>　　case ‘%’: c=(int)a%(int)b;break;</p><p><b>　　}</b></p><p>　　Push_SeqStack(S,c);</p><p><b>　　}</b></p>&l

25、t;p><b>　　Ch=*A++</b></p><p><b>　　}</b></p><p>　　GetTop_SeqStack(S,&Result);</p><p>　　Destroy_SeqStack(&S);</p><p>　　Return Result;<

26、;/p><p><b>　　}</b></p><p><b>　　程序源代碼</b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#include<math.

27、h></p><p>　　#include<string.h></p><p>　　#define MAX_SIZE 256</p><p>　　enum BOOL{FALSE,TRUE};</p><p>　　typedef struct tagOPERATE{</p><p>　　double O

28、perand;</p><p>　　char Operator;</p><p>　　}OPERATE,*LPOPERATE;</p><p>　　void PostSrc(char *src,LPOPERATE lpOperator);</p><p>　　int IsDigit(char);</p><p>　　i

29、nt isp(char ch); </p><p>　　int icp(char ch);</p><p>　　int Locate(char ch);</p><p>　　int getOperand(char *s,int *len,double *oprd);</p><p>　　double Calculate(LPOPERATE l

30、pOperator,double x);</p><p>　　void SrcFunProc(char *src);</p><p>　　void _Proc(char*src);</p><p>　　static char Operator[]="#+-*/";</p><p>　　static int InPriori

31、ty[]={0,3,3,5,5};</p><p>　　static int OutPriority[]={0,2,2,4,4};</p><p>　　int Locate(char ch) </p><p><b>　　{</b></p><p><b>　　int i=0;</b><

32、/p><p>　　for(i=0;Operator[i]!='\0';i++)</p><p>　　if(Operator[i]==ch)</p><p><b>　　return i;</b></p><p>　　return -1;</p><p><b>　　}<

33、/b></p><p>　　int isp(char ch) </p><p><b>　　{</b></p><p>　　if('A'<=ch&&'Z'>=ch)</p><p><b>　　return 9;</b><

34、/p><p><b>　　else</b></p><p>　　return InPriority[Locate(ch)];</p><p><b>　　}</b></p><p>　　int icp(char ch) </p><p><b>　　{</b

35、></p><p>　　if('A'<=ch&&'Z'>=ch)</p><p><b>　　return 8;</b></p><p><b>　　else</b></p><p>　　return OutPriority[Loca

36、te(ch)];</p><p><b>　　}</b></p><p>　　void _Proc(char*src)</p><p><b>　　{</b></p><p>　　char Buffer[MAX_SIZE];</p><p>　　char*p=src,*q=B

37、uffer;</p><p>　　*q++=*p++;</p><p>　　while('\0'!=*p)</p><p><b>　　{</b></p><p>　　if('-'==*p&&'('==*(p-1))</p><p>

38、<b>　　{</b></p><p><b>　　*q++='0';</b></p><p><b>　　*q++='-';</b></p><p><b>　　p++;</b></p><p><b>　　}&

39、lt;/b></p><p><b>　　else</b></p><p>　　*q++=*p++;</p><p><b>　　}</b></p><p><b>　　*q='\0';</b></p><p>　　strcpy(s

40、rc,Buffer);</p><p><b>　　}</b></p><p>　　void SrcFunProc(char*src)</p><p><b>　　{</b></p><p>　　char Buffer[MAX_SIZE];</p><p>　　char*p=

41、src,*q=Buffer;</p><p>　　while(*p!='\0')</p><p><b>　　{</b></p><p>　　switch(*p)</p><p><b>　　{</b></p><p><b>　　case '

42、;s':</b></p><p><b>　　*q++='A';</b></p><p><b>　　p+=3;</b></p><p><b>　　break;</b></p><p>　　case 'c': <

43、;/p><p><b>　　*q++='B';</b></p><p><b>　　p+=3;</b></p><p><b>　　break;</b></p><p>　　case 'e': </p><p><

44、b>　　*q++='C';</b></p><p><b>　　p+=3;</b></p><p><b>　　break;</b></p><p>　　case 'l': </p><p>　　if('n'==*(p+1))

45、 </p><p><b>　　*q++='D';</b></p><p><b>　　else</b></p><p>　　*q++='E'; </p><p><b>　　p+=2;</b></p><p&g

46、t;<b>　　break;</b></p><p>　　case 't': </p><p><b>　　*q++='F';</b></p><p><b>　　p+=3;</b></p><p><b>　　break;&l

47、t;/b></p><p><b>　　default:</b></p><p>　　*q++=*p++;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</

48、b></p><p><b>　　*q='\0';</b></p><p>　　strcpy(src,Buffer);</p><p><b>　　}</b></p><p>　　void PostSrc(char*src,LPOPERATE lpOperator)</p

49、><p><b>　　{</b></p><p>　　char *p=src,y;</p><p>　　LPOPERATE lpOptr=lpOperator;</p><p>　　char stack[MAX_SIZE];</p><p>　　int top=-1; </p><

50、p>　　double Operand;</p><p>　　int offset=0;</p><p>　　stack[++top]='#';</p><p>　　while('\0'!=*p)</p><p><b>　　{</b></p><p>　　if

51、(IsDigit(*p))</p><p><b>　　{</b></p><p>　　getOperand(p,&offset,&Operand);</p><p>　　p+=offset;</p><p>　　lpOptr->Operand=Operand;</p><p&g

52、t;　　lpOptr->Operator=0;</p><p><b>　　lpOptr++;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if('x'==*p)</p>

53、<p><b>　　{</b></p><p>　　(lpOptr++)->Operator='x';</p><p><b>　　p++;</b></p><p><b>　　}</b></p><p><b>　　else</

54、b></p><p>　　if('p'==*p)</p><p><b>　　{</b></p><p>　　lpOptr->Operand=3.14159266;</p><p><b>　　p+=2;</b></p><p>　　lpOptr-

55、>Operator=0;</p><p><b>　　lpOptr++;</b></p><p><b>　　}</b></p><p><b>　　else{</b></p><p>　　for(y=stack[top--];isp(y)>icp(*p);y=st

56、ack[top--])</p><p>　　(lpOptr++)->Operator=y;</p><p>　　stack[++top]=y;</p><p>　　stack[++top]=*p++;</p><p><b>　　}</b></p><p><b>　　}</

57、b></p><p>　　while(top!=-1)</p><p>　　(lpOptr++)->Operator=stack[top--];</p><p><b>　　}</b></p><p>　　int IsDigit(char ch)</p><p><b>　　

58、{</b></p><p>　　if(('0'<=ch&&'9'>=ch)||'.'==ch)</p><p>　　return TRUE;</p><p>　　return FALSE;</p><p><b>　　}</b><

59、;/p><p>　　int getOperand(char *s,int *len,double *oprd){</p><p>　　char *p = s,ch = *s++;</p><p>　　double z = 0,x = 0;</p><p>　　int bits = 0;</p><p>　　int poin

60、t = FALSE;</p><p>　　while( IsDigit(ch) == TRUE){</p><p>　　if (ch == '.'){</p><p>　　if (point == TRUE) </p><p>　　return FALSE;</p><p>　　point = TRUE

61、;</p><p><b>　　}</b></p><p><b>　　else {</b></p><p>　　if (point == TRUE){</p><p><b>　　x *= 10;</b></p><p>　　x += ch - 

62、9;0';</p><p><b>　　bits++;</b></p><p><b>　　}</b></p><p><b>　　else {</b></p><p><b>　　z *= 10;</b></p><p>

63、　　z += ch - '0';</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　ch = *s++;</p><p><b>　　}</b></p><p>　　while(bits-

64、- > 0) x /= 10;</p><p><b>　　z += x;</b></p><p>　　*oprd = z;</p><p>　　*len = s - p - 1;</p><p>　　return TRUE;</p><p><b>　　}</b>&l

65、t;/p><p>　　double Calculate(LPOPERATE lpOperator,double x)</p><p><b>　　{</b></p><p>　　double stack[MAX_SIZE],y1,y2;</p><p>　　int top=-1;</p><p>　　

66、LPOPERATE lpOptr=lpOperator;</p><p>　　stack[++top]=0;</p><p>　　while(lpOptr->Operator!='#')</p><p><b>　　{</b></p><p>　　if(!lpOptr->Operator)&l

67、t;/p><p>　　stack[++top]=(lpOptr++)->Operand;</p><p><b>　　else</b></p><p>　　if('x'==lpOptr->Operator)</p><p><b>　　{</b></p><

68、;p>　　stack[++top]=x;</p><p><b>　　lpOptr++;</b></p><p><b>　　}</b></p><p><b>　　else </b></p><p>　　switch ((lpOptr++)->Operato

69、r)</p><p><b>　　{</b></p><p><b>　　case '+':</b></p><p>　　y1=stack[top--];</p><p>　　y2=stack[top--];</p><p>　　stack[++top]=y1

70、+y2;</p><p><b>　　break;</b></p><p><b>　　case '-':</b></p><p>　　y1=stack[top--];</p><p>　　y2=stack[top--];</p><p>　　stack[++

71、top]=y2-y1;</p><p><b>　　break;</b></p><p><b>　　case '*':</b></p><p>　　y1=stack[top--];</p><p>　　y2=stack[top--];</p><p>　　s

72、tack[++top]=y1*y2;</p><p><b>　　break;</b></p><p><b>　　case '/':</b></p><p>　　y1=stack[top--];</p><p>　　y2=stack[top--];</p><p

73、>　　stack[++top]=y2/y1;</p><p><b>　　break;</b></p><p><b>　　case 'A':</b></p><p>　　y1=stack[top--];</p><p>　　stack[++top]=sin(y1);</

74、p><p><b>　　break;</b></p><p><b>　　case 'B':</b></p><p>　　y1=stack[top--];</p><p>　　stack[++top]=cos(y1);</p><p><b>　　bre

75、ak;</b></p><p><b>　　case 'C':</b></p><p>　　y1=stack[top--];</p><p>　　stack[++top]=exp(y1);</p><p><b>　　break;</b></p><p

76、><b>　　case 'D':</b></p><p>　　y1=stack[top--];</p><p>　　stack[++top]=log(y1);</p><p><b>　　break;</b></p><p><b>　　default:</b&

77、gt;</p><p>　　break; } }</p><p>　　return stack[top];</p><p><b>　　}</b></p><p>　　void main()</p><p>　　{char src[MAX_SIZE];</p><p>&l

78、t;b>　　double d;</b></p><p>　　OPERATE postsrc[MAX_SIZE];</p><p>　　memset(src,0,MAX_SIZE);</p><p>　　printf("公式計(jì)算器 作者:吳琦n輸入任意表達(dá)式開始計(jì)算，輸入quit結(jié)束程序\n常量 pi=3.14159266\n&qu

79、ot;);</p><p>　　scanf("%s",src);</p><p>　　while(strcmp(src,"quit"))</p><p><b>　　{</b></p><p>　　_Proc(src);</p><p>　　SrcFunPr

80、oc(src);</p><p>　　PostSrc(src,postsrc);</p><p>　　d=Calculate(postsrc,3.1415926);</p><p>　　printf("計(jì)算結(jié)果是:%f\n",d);</p><p>　　memset(src,0,MAX_SIZE);</p>