885191311数据结构课程设计报告—迷宫求解问题.doc
课题设计1：迷宫求解一. 需求分析：本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。二、 概要设计：1.抽象数据类型定义：ADT Find数据对象：D=ai?ai ElemSet,i=1,2,n,n0数据关系：R1=<ai-1,ai>?ai-1, aiD 基本操作： find (&S)初始条件：已初始化栈S，且栈为空操作结果：从栈中找出相对应的数据关系，并输出结果ADT Find2. 主程序的流程以及各程序模块之间的调用关系：(1).定义变量i、j、w、z为整形变量(2).输入迷宫二维数组maze(0:m,0:n)(3).调用子程序find ()(4).结束程序三、相应的源程序如下：#include<stdio.h>#include<stdlib.h>typedef enum ERROR, OK Status;typedef struct int row, line; PosType; typedef struct int di, ord; PosType seat; SElemType; typedef structSElemType * base;SElemType * top;int stacksize;SqStack;Status InitStack(SqStack &S); Status Push(SqStack &S,SElemType &a); Status Pop(SqStack &S,SElemType &a); Status StackEmpty(SqStack S); Status MazePath(int maze1212,SqStack &S, PosType start, PosType end); void Initmaze(int maze1212,int size); void printmaze(int maze1212,int size); Status Pass(int maze1212,PosType CurPos); void Markfoot(int maze1212, PosType CurPos); PosType NextPos(PosType CurPos, int Dir); void printpath(int maze1212,SqStack S,int size);void main (void) SqStack S;int size,maze1212; for(int n=0;n<10;n+) printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于50):n"); scanf("%d",&size);if(size<1 | size>10)printf("输入错误!");return; Initmaze(maze,size); printmaze(maze,size); PosType start,end; printf("输入入口行坐标和列坐标:");scanf("%d",&start.row);scanf("%d",&start.line); printf("输入出口行坐标和列坐标:");scanf("%d",&end.row);scanf("%d",&end.line); if(MazePath(maze,S,start,end) printpath(maze,S,size); else printf("找不到通路!nn");Status MazePath(int maze1212,SqStack &S, PosType start, PosType end) PosType curpos;int curstep;SElemType e;InitStack(S);curpos = start; curstep = 1; do if (Pass(maze,curpos) Markfoot(maze,curpos); e.di =1; e.ord = curstep; e.seat= curpos; Push(S,e); if (curpos.row=end.row && curpos.line=end.line) return OK; curpos = NextPos(curpos, 1); curstep+; else if (!StackEmpty(S) Pop(S,e); while (e.di=4 && !StackEmpty(S) Markfoot(maze,e.seat); Pop(S,e); if (e.di<4) e.di+; Push(S, e); curpos = NextPos(e.seat, e.di); while (!StackEmpty(S);return ERROR; void Initmaze(int maze1212,int size) char select; printf("选择创建方式 A:自动生成 B:手动创建n"); label:scanf("%c",&select); if(select='a'|select='A') for(int i=0;i<size+2;i+)maze0i=1; for( i=1;i<size+1;i+) mazei0=1; for(int j=1;j<size+1;j+) mazeij=rand()%2; mazeisize+1=1; for(i=0;i<size+2;i+)mazesize+1i=1; else if(select='b'|select='B') printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):n",size,size); for(int i=0;i<size+2;i+)maze0i=1; for( i=1;i<size+1;i+) mazei0=1; for(int j=1;j<size+1;j+) scanf("%d",&mazeij); mazeisize+1=1; for(i=0;i<size+2;i+)mazesize+1i=1; else if(select='n')goto label; else printf("输入错误!");void printmaze(int maze1212,int size)printf("nn");printf("显示所建的迷宫(#表示外面的墙):n"); for(int i=0;i<size+2;i+)printf("%c ",'#');printf("n");for(i=1;i<size+1;i+) printf("%c ",'#'); for(int j=1;j<size+1;j+) printf("%d ",mazeij); printf("%c",'#'); printf("n"); for(i=0;i<size+2;i+)printf("%c ",'#');printf("n");void printpath(int maze1212,SqStack S,int size) printf("nn通路路径为:n");SElemType * p=S.base;while(p!=S.top) mazep->seat.rowp->seat.line=2; p+; for(int i=0;i<size+2;i+)printf("%c ",'#');printf("n");for(i=1;i<size+1;i+) printf("%c ",'#'); for(int j=1;j<size+1;j+) if(mazeij=2) printf("%c ",'0'); else printf(" "); printf("%c",'#'); printf("n"); for(i=0;i<size+2;i+)printf("%c ",'#');printf("nn");Status Pass(int maze1212,PosType CurPos)if (mazeCurPos.rowCurPos.line=0) return OK; else return ERROR; void Markfoot(int maze1212,PosType CurPos)mazeCurPos.rowCurPos.line=1;PosType NextPos(PosType CurPos, int Dir) PosType ReturnPos; switch (Dir) case 1: ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line+1; break; case 2: ReturnPos.row=CurPos.row+1; ReturnPos.line=CurPos.line; break; case 3: ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line-1; break; case 4: ReturnPos.row=CurPos.row-1; ReturnPos.line=CurPos.line; break;return ReturnPos;Status InitStack(SqStack &S)S.base=(SElemType *)malloc(100*sizeof(SElemType);if(!S.base)return ERROR;S.top=S.base;S.stacksize=100;return OK;Status Push(SqStack &S,SElemType &a) *S.top+=a;return OK;Status Pop(SqStack &S,SElemType &a)if(S.top=S.base)return ERROR;a=*-S.top;return OK;Status StackEmpty(SqStack S)if(S.top=S.base)return OK;return ERROR;以下为测试数据：输入一个矩阵，例如：1 0 0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 输入入口行坐标和列坐标：1 2输入出口行坐标和列坐标：5 5通路路径为：课题设计3：joseph环一. 需求分析：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。首先创建一个空链表，初始化链表，构造出一个只有头结点的空链表，建立好一个约瑟夫环。1. 输入的形式和输入值的范围 本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。2. 输出的形式 从屏幕显示出列顺序。3. 程序功能 提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。二、 概要设计以单向循环链表实现该结构。1. 抽象数据类型的定义为：ADT LNode 数据对象：D=ai | aiCharSet，i= 1，2，n，n0 数据关系：R1=< ai-1 ，ai > | ai D， I=2，n三源程序：#include<stdio.h> #include<stdlib.h> typedef struct Node int key;/每个人持有的密码 int num;/这个人的编号 struct Node *next;/指向下一个节点 Node,*Link; void InitList(Link &L) /创建一个空的链表 L=(Node *)malloc(sizeof(Node); if(!L) exit(1); L->key=0; L->num=0; L->next=L; void Creater(int n,Link &L) /初始化链表 Link p,q; q=L; for(int i=1;i<=n;i+) p=(Node *)malloc(sizeof(Node); if(!p) exit(1); printf("the key_%d is:",i); scanf("%d",&p->key); p->num=i; L->next=p; L=p; L->next=q->next; free(q); void main() Link L,p,q; int n,x; L=NULL; InitList(L);/构造出一个只有头结点的空链表 printf("please input the totle number of people:"); scanf("%d",&n);/总共的人数n printf("the start key is:"); scanf("%d",&x);/初始密码为x Creater(n,L);/建立好一个约瑟夫环 p=L; for(int i=1;i<=n;i+) for(int j=1;j<x;j+) p=p->next; q=p->next; x=q->key; printf("%d ",q->num); p->next=q->next; free(q); 四、测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4输出：6 7 4 1 5 3 2课题设计4：商品货架管理1、需求分析：设计一个算法，每一次上货后始终保持生产日期越近的商品越靠近栈底。求货架上剩余货物M、每天销售件数N、员工每天上货工作时间T，三者之间有何关系及T的最小值。2、源程序：#include<iostream.h>#include"string.h"#include"stdio.h"const int maxsize=100; const int k=10; #define elemtype chartypedef structint Month;int Day;int Year;DATE;typedef struct int num; DATE date; Node;class seqstackpublic:Node stackmaxsize;int top;void inistack()top=0;void push(int x,int day,int month,int year)if(top=maxsize)cout<<"货架已满"<<endl;else top+;stacktop.num=x;stacktop.date.Day=day;stacktop.date.Month=month;stacktop.date.Year=year;void pop()if(top=0)cout<<"货架已空"<<endl;elsetop-;elemtype gettop()if(top=0)cout<<"货架已空"<<endl;elsereturn top;bool empty()return top=0;void main()seqstack ck+1; /存放k种商品的数组,用c0来做中介货架int Txqk+1; /第i种取货用的时间int Txsk+1; /第i种上货用的时间int Nxk+1; /第i种每天的销售数量int N=0; /每天销售总量int Txk+1; /第i种每天上货的总时间int T=0; /每天上货用的总时间char yn='Y'for(int i=1;i<=k;i+)cout<<" *"<<endl;cout<<" 商品货架管理系统"<<endl;cout<<" *"<<endl;Node store20;char year,month;int count; /货架上第i种商品的数目 int x,d,m,y; /x为第i种商品的序号cout<<"请输入货架上第"<<i<<"种货物的详细信息:"<<endl;cout<<"(序号,生产日期(年、月、日如2006.2.13)，现在货架上的存货数目,上货用时和取货用时)"<<endl;cin>>x>>y>>year>>m>>month>>d>>count>>Txsi>>Txqi;Nxi=maxsize-count;cout<<"货架上还需上"<<i<<"货物"<<Nxi<<"件"<<endl;Txk=Txsi*(maxsize+count)+2*Txqi*count;cout<<"该货架满货需要用时"<<Txk<<endl;cout<<"是否要上货?(Y/N)"<<endl;cin>>yn;if(yn='Y'|yn='y')int numbers,nian,yue,ri;cout<<"请输入要上货物的数目及生产日期(年、月、日)"<<endl; /上的是同一日期生产的货物cin>>numbers>>nian>>yue>>ri;if(numbers>maxsize-count)cout<<"要上的货物数目超出了货架的最大容量，请重新输入"<<endl;cin>>numbers>>nian>>yue>>ri;for(int j=1;j<=numbers;j+)N+=Nxi;T+=Txi;cout<<"每天销售总量为:"<<N<<endl;cout<<"每天上货用的总时间为:"<<T<<endl;3、测试结果：五、课程设计5：航空客运订票系统1、需求分析：对于本设计，可采用基数排序法对于一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快递查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因为它们用的较少。2、源程序：#include <stdio.h>#include <string.h>#define maxspace 100#define keylen 7#define radix_n 10#define radix_c 26typedef char keytype;typedef struct char start6;char end6;char sche10;char time15;char time25;char model4;int price;infotype;typedef structkeytype keyskeylen;infotype others;int next;slnode;typedef structslnode slmaxspace;int keynum;int length;sllist;typedef int arrtype_nradix_n;typedef int arrtype_cradix_c;void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e)int j,p;for(j=0;j<radix_n;j+)fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%48;if(!fj)fj=p;elseslej.next=p;ej=p;void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)int j,t;for(j=0;!fj;j+);sl0.next=fj;t=ej;while(j<radix_n-1)for(j=j+1;j<radix_n-1&&!fj;j+);if(fj)slt.next=fj;t=ej; slt.next=0;void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e)int j,p;for(j=0;j<radix_c;j+)fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%65;if(!fj)fj=p;elseslej.next=p;ej=p;void collect_c(slnode *sl,int i,arrtype_c f,arrtype_c e)int j,t;for(j=0;!fj;j+);sl0.next=fj;t=ej;while(j<radix_c-1)for(j=j+1;j<radix_c-1&&!fj;j+);if(fj)slt.next=fj;t=ej; slt.next=0;void radixsort(sllist &l)/链式int i;arrtype_n fn,en;arrtype_c fc,ec;for(i=0;i<l.length;i+)l.sli.next=i+1;l.sll.length.next=0;for(i=l.keynum-1;i>=2;i-)distribute(l.sl,i,fn,en);collect(l.sl,i,fn,en);for(i=1;i>=0;i-)distribute_c(l.sl,i,fc,ec);collect_c(l.sl,i,fc,ec);void arrange(sllist &l)/重新整理int p,q,i;slnode temp;p=l.sl0.next;for(i=1;i<l.length;i+)while(p<i)p=l.slp.next;q=l.slp.next;if(p!=i)temp=l.slp;l.slp=l.sli;l.sli=temp;l.sli.next=p;p=q;int binsearch(sllist l,keytype key)int low,high,mid;low=1;high=l.length;while(low<=high)mid=(low+high)/2;if(strcmp(key,l.slmid.keys)=0)return mid;else if(strcmp(key,l.slmid.keys)<0)high=mid-1;elselow=mid+1;return 0;void seqsearch(sllist l,keytype key,int i)int j,k,m=0;printf("*n");printf("* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *n");for(j=1;j<=l.length;j+)switch(i)case 2:k=strcmp(key,l.slj.others.start);break;case 3:k=strcmp(key,l.slj.others.end);break;case 4:k=strcmp(key,l.slj.others.time1);break;case 5:k=strcmp(key,l.slj.others.time2);break;if(k=0)m=1;printf("* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *n",l.slj.keys,l.slj.others.start,l.slj.others.end,l.slj.others.sche,l.slj.others.time1,l.slj.others.time2,l.slj.others.model,l.slj.others.price);if(m=0)printf("* 无此航班信息，可能是输入错误！ *n");printf("*n");void searchcon(sllist l)keytype keykeylen;int i=1,k;while(i>=1&&i<=5)printf("n *n");printf(" * 航班信息查询系统 *n");printf(" *n");printf(" * 1.航 班 号 *n");printf(" * 2.起 点 站 *n");printf(" * 3.终 点 站 *n");printf(" * 4.起飞时间 *n");printf(" * 5.到达时间 *n");printf(" * 0.退出系统 *n");printf(" *n");printf(" 请选择(0-5):");scanf("%d",&i);printf("n");switch(i)case 1:printf("输入要查询的航班号(字母要大写):");scanf("%s",key);k=binsearch(l,key);printf("*n");if(k=0)printf("* 无此航班信息，可能是输入错误！ *n");elseprintf("* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *n");printf("* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *n",l.slk.keys,l.slk.others.start,l.slk.others.end,l.slk.others.sche,l.slk.others.time1,l.slk.others.time2,l.slk.others.model,l.slk.others.price);printf("*n");break;case 2:printf("输入要查询的航班起点站名:");scanf("%s",key);seqsearch(l,key,i);break;case 3:printf("输入要查询的航班终点站名:");scanf("%s",key);seqsearch(l,key,i);break;case 4:printf("输入要查询的航班起飞时间:");scanf("%s",key);seqsearch(l,key,i);break;case 5:printf("输入要查询的航班到达时间:");scanf("%s",key);seqsearch(l,key,i);break;case 0:printf("nnn 再 见nnn");void inputdata(sllist &l)int i=+l.length;char yn='y'while(yn='y'|yn='Y')printf("航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价n");scanf("%s%s%s%s%s%s%s%d",l.sli.keys,l.sli.others.start,l.sli.others.end,l.sli.others.sche,l.sli.others.time1,l.sli.others.time2,l.sli.others.model,&l.sli.others.price);+i; getchar(); radixsort(l);arrange(l);printf("继续输入吗?y/n:");scanf("%c",&yn);l.length=i-1;void main()sllist l;l.keynum=6;l.length=0;inputdata(l);searchcon(l);3、
