1、 算法与数据结构课程设计报告算法与数据结构课程设计报告 专业：专业： 计算机科学与技术计算机科学与技术 学号：学号： 姓名：姓名： 题目：题目：1.用链表求解约瑟夫问题。用链表求解约瑟夫问题。 算法思路：由于约瑟夫问题是 n个人围坐一圈，所以采用偱环链表实现，又由于 报数时可能循环到开始，所以采用不带头结点的循环链表结构。 算法步骤： a 在不带头结点的循环链表中查找第 s 个结点的指针。 b 从 p 所指胡结点开始计数查找第 m个结点，pre 指向 p 的前驱。 c 输出该结点元素值。 D 删除该结点，同时将该结点下一结点指针作为当前指针即 p 指针，重复到步骤 b,直到链表中所有结点都被删
2、除完为止。 算法分析：算法分析： int josephus_LinkList (LinkList josephus_Link,int s,int m) LinkList p,pre; int count; if(!josephus_Link) printf(“表中无元素”)； Return(0); P=josephus_Link; For(count=1;countnext; printf(“输入约瑟夫序列：”); while(p!=p-next) for(count=1;countnext; printf(“%dt”,p-data); pre-next=p-next; free(p); p=
3、pre-next; printf(“%dt”,p-data); free（p）; return 1; 程序源代码程序源代码： #include“stdlib.h“ #include“stdio.h“ typedef struct node int data; struct node *next; Lnode; Lnode *create(int n) int i; Lnode*h,*p,*r=(Lnode*)malloc(sizeof(Lnode) ; r-data=n;h=r; for(i=n-1;i0;i-) p=(Lnode*)malloc(sizeof(Lnode); p-data=i
4、; p-next=h; h=p; r-next=h; return h; void jeseph(Lnode *p,int m) Lnode *q; int j=0; printf(“outqueue order:“); do j+; if(j=m-1) q=p-next; p-next=q-next; printf(“%d“,q-data); j=0;free(q); p=p-next; while(p-next!=p); printf(“%dn“,p-data); free(p); void main() Lnode *h; int m,n; printf(“n input n,m=“);
5、 scanf(“%d,%d“, h=create(n); jeseph(h,m); 运行结果：运行结果： 2.表达式求值。 表达式求值是程序设计语言编译中一个最基本的问题。 它的实现也是栈的应用中 的一个典型的例子。 任何一个表达式都是由操作数，运算符和界限符组成的有意义的式子。一般地， 操作数既可以是常数，也可以是变量或常量。运算符从运算对象的个数上分，有 单目运算符、双目运算符和三目运算符；从运算类型上分，有算数运算符、关系 运算符、逻辑运算符。界限符有左右括号和表达式结束符等。运算符、界限符统 称为算符。为简单化，在这里，仅限于讨论只含二目运算符的加、减、乘、除算 数表达式，并且操作数为
6、一位字符表示的整数。 算法分析：算法分析： typedef double DataType; int IsNum(char c) if(c=0 else return(0); double postfix_exp(char*A) PSeqStack S; double Result,a,b,c;char ch; ch=*A+; S=Init_SeqStack(); while (ch!=#) if (IsNum(ch) Push_SeqStack(S,ch-0); Else Pop_SeqStack(S, Pop_SeqStack(S, switch(ch) case +: c=a+b;break; case -: c=a-b;break; case *: c=a*b;break; case /: c=a/b;break; case %: c=(int)a%(int)b;break;
