数据结构课程设计-约瑟夫环,广义表,栈和队列,floyed算法.doc

山东科技大学学生课程设计设计1 约瑟夫环问题 1、 需求分析一、具体目标包括： 1、实现单循环链表的初始化以及节点的创建和赋值2、理解约瑟夫环的定义，通过循环找到每次要出列的人的位置3、从单循环链表中删除结点，对头节点和一般结点分情况讨论二、单循环链表的抽象数据类型定义为： ADT CLink 数据对象：Dai | aiElemset,i=1,2,n,n0 数据关系：R=, | ai-1,aiD,i=2,n 基本操作： Status CreateList(CLink &head,int length)操作结果：构造一个含有n个元素的单向循环链表。 void Selectqueue(CLink head,int n,int m)操作结果：输出符合上限应该出列的结点。三、问题描述设编号为1，2，n(n0)个人按顺时针方向围坐一圈，每人持有一个 正整数密码。开始时任意给出一个报数上限值m，从第一人开始顺时针方向自1 起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺指针方向上的下一个人起重新自1起顺序报数；下去，直到所有人全部出列为止。要求设计一个程序模拟此过程。四、基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序输出个人的编号以及持有的密码。 二、概要设计一、本程序主要分为三个模块1、主模块 void main() 单循环链表的初始化； 输入总人数和第一个上限值； 调用另外两个模块，实现出列人的顺序；2、 单向循环链表抽象数据类型模块：CreateList(CLink &head,int length)实现单向循环链表的抽象数据类型功能；3、出列节点的顺序模块：Selectqueue(CLink head,int n,int m),实现出列结点的顺序功能；三、详细设计1、主模块的实现算法 基本思想：对单链表进行初始化，并设置总人数和第一个报数的上限值。若总人数或者上限不符合要求时则重新输入。2、构建一个单循环链表算法基本思想 ：先创建单链表的一个结点，再依次循环创建直至达到总结点数，并且让最后一个创建的结点的指针域为头结点的地址。Status CreateList(CLink &head,int length) CLink before; CLink new_node; int i; printf(Please Input Password 1 : ); scanf(%d,&head-password); head-number=1; head-next=NULL; before=head; for(i=1;inumber = i+1; printf(Please Input Password %d : , new_node-number); scanf(%d,&new_node-password); new_node-next = NULL; before-next=new_node; before=new_node; new_node-next =head; return TRUE; 流程图13、构建一个实现出列顺序的算法 基本思想：用ptr只向当前出列的结点，若为头结点时则找到指向头结点的指针，并做结点的删除，若不是头结点，则用back指针作为指向ptr的指针，进行结点的删除。void selectqueue(CLink head,int n,int m) CLink ptr,back,last; int i,j; ptr=head; for(i=0;in;i+) for(j=0;jnext; m=ptr-password；printf(第%d个出列的编号以及密码为:%d,%dn,i+1,ptr-number,m); if(ptr=head) last=head; while(last-next!=head) last=last-next; last-next=head-next; free(ptr); ptr=last-next; head=ptr; else back-next=ptr-next; free(ptr); ptr=back-next; 流程图2四、运行结果及分析 测试用例1：（一般数据） 测试用例2：（边界数据）测试用例3：（错误数据）运行结果分析：（1）对一般数据能否输出正确结果？ 能输出正确结果（2）对边界数据能否给出合适的反应？ 对于头结点要出列或者第一个上限数很大时也可以给出结果（3）对错数据能否给出必要的提示？提示重新输入的语句（4）算法的复杂度多少？ CreateList是O(n), Selectqueue是O()五、总结本次实验主要考察了对单循环链表的灵活应用附：主要源代码#include #include#define OVERFLOW -1#define TRUE 1typedef int Status;typedef struct CNode int password; int number; struct CNode *next;CNode,*CLink;Status CreateList(CLink &head,int length) CLink before; CLink new_node; int i; printf(Please Input Password 1 : ); scanf(%d,&head-password); head-number=1; head-next=NULL; before=head; for(i=1;inumber = i+1; printf(Please Input Password %d : , new_node-number); scanf(%d,&new_node-password); new_node-next = NULL; before-next=new_node; before=new_node; new_node-next =head; return TRUE; void selectqueue(CLink head,int n,int m) CLink ptr,back,last; int i,j; ptr=head; for(i=0;in;i+) for(j=0;jnext; m=ptr-password; printf(第%d个出列的编号以及密码为:%d,%dn,i+1,ptr-number,m); if(ptr=head) last=head; while(last-next!=head) last=last-next; last-next=head-next; free(ptr); ptr=last-next; head=ptr; else back-next=ptr-next; free(ptr); ptr=back-next;int main() CLink head; CLink ptr,back,last; int i,j,m,n; printf(Please Input the Number of Persons: ); scanf(%d,&n); while(n1) printf(Please Input the Number of Persons again: ); scanf(%d,&n); printf(Please Input the frist m: ); scanf(%d,&m); while(m=0数据关系： R1=| ai-1,aiD,i=2,n基本操作：InitStack(& S)操作结果：构造一个空栈S；StackEmpty(S)初始条件：栈S已存在；操作结果：若S为空栈，则返回0，否则返回1；GetTop(S,&e)初始条件：栈S已存在；操作结果：若栈S不空，则以e返回栈顶元素；Push(&S,e)；操作结果：在栈S的栈顶插入新的栈顶元素e；Pop(&S,&e) 操作结果：删除S的栈顶元素，并以e返回其值；Status Match(char *str) /括弧、字符范围匹配初始条件：栈S已经存在；操作结果：/括弧、字符范围匹配。Status Involution(int a,int b)初始条件：需要幂运算；操作结果：乘方（幂）运算函数。Status Precede(int a,int b)初始条件：当前量有两个；操作结果：优先级判段函数 。void assort(char *str,char *str2)操作结果：将表达式转化为后缀表达式StatusCallast(char *str)初始条件：输入合理操作结果：表达式求解,操作数栈OPND，操作码栈OPTR，最初压入“#”2、定义树的抽象数据类型定义：ADT Stack 数据对象： D是具有相同特性的数据元素的集合。 数据关系：若D为空集，则称为空树 。否则: (1) 在D中存在唯一的称为根的数据元素root；(2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, , Tm，其中每一个子集本身又是一棵符合本定义的树， 称为根root的子树。 基本操作：InitBiTree(T) 对于前缀表达式实现树的初始化 PreorderT(T-lchild)：后序遍历树并输出，二、概要设计我想把本设计题目的实现划分成成如下几个模块实现，包括:1、主模块 Void main() 输入表达式，包括对表达式的检查，当输入有误时则重新输入 调用将表达式转化为后缀表达式的模块 调用利用栈实现后缀表达式求值的模块 调用将二叉树的模块 2、assort(str,str2)：将输入的表达式转化为后缀表达式的模块3、Callast(str2)：后缀表达式求值的模块4、InitBiTree(T)以及PreorderT(T-lchild)：将输入的前缀表达式转化成树并输出的模块三、详细设计模块1的实现算法基本算法：表达式的输入并进行检查，当输入有误则重新输入模块2的实现算法void assort(char *str,char *str2)SqStack OPTR;InitSqStack(OPTR);Push(OPTR,#);char ch;int n,i=0;int theta,x, a,b;while(*(str+i) != # | GetTop(OPTR) != #)n=0;ch=*(str+i);if(ch-0) 9 )switch(Precede(GetTop(OPTR),ch)/比较栈顶运算符与c的优先级case :Pop(OPTR,theta);if(theta!=() *str2+=char(theta); / printf(%c,char(theta); *str2+= ;break;elsewhile(ch-0) = 0 & (ch-0) =0&(ch-0)= 0 & (ch-0) = 9)n=10*n+ch-0;+i;ch=*(str2+i);/实现两位数以上的数值计算Push(OPND,n);if(ch= ) i+;else if(ch= ) i+; else Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,int(ch),b); i+ ; return GetTop(OPND);流程图2模块4的实现算法 基本思想将输入的前缀表达式运用递归算法转化成树，先建立根节点再依次建立左子树和右子树，并后序遍历输出树。四、运行结果及分析测试用例1：（一般数据）测试用例2：（错误数据）运行结果分析：（1）对一般数据能否输出正确结果？ 能输出正确结果（2） 对边界数据能否给出合适的反应？ 只要输入正确都可以给出合适的反应（3）对错输入能否给出必要的提示？ 提示出错的原因以及重新输入的提示（1） 算法的复杂度多少？每个模块都是Strlen（str）5、 总结 本实验主要考察了对栈和树的操作，以及对表达式转化的应用。附：主要源代码#include#include#include#include #define OK 1#define ERROR 0#define OVERFLOW -1#define TRUE 1#define FALSE 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef int SElemType;typedef struct/栈的定义SElemType *base;SElemType *top;int stacksize;SqStack;typedef struct BiTNode char data; struct BiTNode *lchild, *rchild;BiTNode, *BiTree;Status InitSqStack(SqStack &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;Status Push(SqStack &S,SElemType e)/插入一元素if(S.top-S.base=S.stacksize)S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e)/删除一元素if(S.top = S.base)return ERROR;elsee=*-S.top;return OK;Status GetTop(SqStack S)/取栈顶元素，用e带回if(S.top = S.base)return ERROR;elsereturn *(S.top-1);Status Match(char *str)/括弧、字符范围匹配SqStack S;int hasErr=0,i=0;SElemType e;InitSqStack(S);char ch; for(i=0;*(str+i)!=#;+i) if(*(str+i)=/&(*(str+i+1)=0) printf(n警告：0不能做分母出错n);return FALSE; else continue; i=0;while(ch=*(str+i)!=# & hasErr=0)switch(ch)case (:Push(S,ch);break;case ):if(S.top=S.base)hasErr=1;break;elsePop(S,e);if(e!=()hasErr=1;break;break;+i;if(!(hasErr=0 & S.top=S.base)printf(n警告：括号不匹配n);return FALSE;for(i=0;(ch=*(str+i)!=#;+i)if(ch=(|ch=)|ch=+|ch=-|ch=*|ch=/|ch=%|ch=|ch=#|(ch-0)=0&(ch-0)=9) continue; else printf(n警告：字符匹配出错n);return FALSE; return TRUE;Status Involution(int a,int b)/乘方（幂）运算函数if(0=b)return 1;if(1=b)return a;int num=a;for(int i=2;i=b;+i)num*=a;return num;Status Operate(int a,int theta,int b)switch(theta)case +:return a+b;case -:return a-b;case *:return a*b;case /:return a/b;case %:return a%b;case :return Involution(a,b);default:return ERROR;Status Precede(char a,char b)/优先级判段函数switch(a)case #:if(#=b)return =;else return ;else return ;case *:case /:case %:if(=b|=b)return ;case :if(=b)return ;case (:if()=b)return =;else return ;default:return ERROR;void assort(char *str,char *str2)SqStack OPTR;InitSqStack(OPTR);Push(OPTR,#);char ch;int n,i=0;int theta,x, a,b;while(*(str+i) != # | GetTop(OPTR) != #)n=0;ch=*(str+i);if(ch-0) 9 )switch(Precede(GetTop(OPTR),ch)/比较栈顶运算符与c的优先级case :Pop(OPTR,theta);if(theta!=() *str2+=char(theta); / printf(%c,char(theta); *str2+= ;break;elsewhile(ch-0) = 0 & (ch-0) =0&(ch-0)= 0 & (ch-0) lchild=NULL; T-rchild=NULL; return T; BiTree CreateBiTree(BiTree T) char ch; scanf(%c,&ch);/按前序次序输入节点信息 if (ch= ) T = NULL; else if (!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(0); T-data = ch; / 生成根结点 T-lchild =CreateBiTree(T-lchild); / 构造左子树 T-rchild =CreateBiTree(T-rchild); / 构造右子树 return T; / CreateBiTree ,无头节点void PreorderT(BiTree T)if (T) PreorderT(T-lchild ); PreorderT(T-rchild ); printf(%c, T-data );int main()char str200,str2400;BiTree T;printf(请输入表达式，以#结束：n);scanf(%s,str);strstrlen(str)+1=0;while(FALSE = Match(str)printf(重新输入表达式：n); scanf(%s,str); strstrlen(str)+1=0;printf(后缀表达式：);assort(str,str2); puts(str2);putchar(n);printf(表达式的值为：%dn,Callast(str2); printf(input the string: ); T= InitBiTree(T); getchar(); T-lchild =CreateBiTree(T-lchild ); printf(The Tree is: ); PreorderT(T-lchild); 设计3 数组和广义表一、需求分析一、抽象数据类型ADT SMatrix 数据对象： Daj1,j2, .,ji, .,jn| ji =0,.,bi -1, i=1,2,.,n 数据关系： Row|1=i=m,1=j=n-1 Col|1=i=m-1,1=j=n 2、基本操作：（1）status LogicMatrix(SMatrix M,SMatrix N,SMatrix *Q)操作结果：求矩阵逻辑乘积Q=M*N （2）status SumMatrix(SMatrix M,SMatrix N,SMatrix *Q)操作结果：M+N=Q二、概要设计1、用三元组顺序表存储表示2、通过求两个矩阵的和及乘积来求的关系的传递闭包3、 详细设计四、运行结果及分析运行结果分析1） 能给出正确结果2） 算法复杂度：SumMatrix(At1,N,&At2) O(n) LogicMatrix(M,Temp,&N) O()五、总结主要应用三元组处理矩阵，利用矩阵的加法和乘法求自反闭包、对称闭包和传递闭包附：主要源代码#include#include#define MAXSIZE 1250#define OK 1#define ERROR 0#include#includetypedef int status;typedef int ElemType;typedef structint i,j; /该非零元的行下标和列下表 ElemType e;Triple;typedef structTriple dataMAXSIZE+1; /非零元三元组int rposMAXSIZE+1; /各行第一个非零元的位置表int mu,nu,tu;/矩阵的行数列数和非零元个数SMatrix;status SumMatrix(SMatrix M,SMatrix N,SMatrix *Q) /M+N=Qint p,q,k=1;if(!(M.nu=N.nu & M.mu=N.mu)return ERROR;Q-mu=M.mu;Q-nu=M.nu;for(p=1,q=1;p=M.tu & qdatak.i=M.datap.i; Q-datak.j=M.datap.j; Q-datak.e=1; p+; q+; k+;else if(M.datap.jdatak.i=M.datap.i; Q-datak.j=M.datap.j; Q-datak.e=1;p+; k+;else if(M.datap.jN.dataq.j) Q-datak.i=N.dataq.i; Q-datak.j=N.dataq.j; Q-datak.e=1; q+;k+; else if(M.datap.iN.dataq.i) Q-datak.i=N.dataq.i; Q-datak.j=N.dataq.j; Q-datak.e=1; q+; k+; else if(M.datap.idatak.i=M.datap.i; Q-datak.j=M.datap.j; Q-datak.e=1; p+;k+;for(p;pdatak.i=M.datap.i; Q-datak.j=M.datap.j; Q-datak.e=1; k+;for(q;qdatak.i=N.dataq.i; Q-datak.j=N.dataq.j; Q-datak.e=1; k+; Q-tu=-k; return OK;status LogicMatrix(SMatrix M,SMatrix N,SMatrix *Q)/求矩阵逻辑乘积Q=M*N,采用行逻辑链接存储表示int i,t,ccol,arow,tp,p,q,ctempMAXSIZE=0,brow;if(M.nu!=N.mu)return ERROR;Q-mu=M.mu;Q-nu=N.nu;Q-tu=0;/Q初始化if(M.tu*N.tu!=0) /Q是非零矩阵for(arow=1;arow=M.mu;+arow) /处理M的每一行for(i=1;irposarow=Q-tu+1;if(arowM.mu)tp=M.rposarow+1;elsetp=M.tu+1;for(p=M.rposarow;ptp;+p)/对当前行中每一个非零元找到对应元在N中的行号brow=M.datap.j;if(browM.mu) t=N.rposbrow+1;elset=N.tu+1; for(q=N.rposbrow;qt;+q) ccol=N.dataq.j;/乘积元素在Q中的列号ctempccol=1; /求得Q中第crow行非零元 for(ccol=1;ccolnu;+ccol)/压缩存储该行非零元if(ctempccol) if(+Q-tuMAXSIZE)return ERROR;Q-dataQ-tu.i=arow; Q-dataQ-tu.j=ccol; Q-dataQ-tu.e=ctempccol; return OK;status Moutput(SMatrix *N) int i,k=1,j; for(i=1;imu;+i) for(j=1;jnu;j+) if(ktu) if(N-datak.i=i & N-datak.j=j) printf( %d ,N-datak.e); if(k=N-tu) k=k+2; else k+; else printf( 0 ); else if(kN-tu+1)printf( 0 );printf(n);return OK;status Creatrops(SMatrix *N) int t,r,numMAXSIZE=0;if(N-tu) for(r=1;rmu;+r)numr=0;for(t=1;ttu;+t)+numN-datat.i; N-rpos1=1;for(r=2;rmu;+r) N-rposr=N-rposr-1+numr-1; return OK;int main() int i;SMatrix M,N,*At,At2,At1,As,Ar,Ix,Temp;printf(输入矩阵的行数，列数以及非零元的个数：n);scanf(%d%d%d,&M.mu,&M.nu,&M.tu);printf(输入三元组：n);for(i=1;i=M.tu;i