算法与数据结构 课程设计报告书.doc

* 实践教学实践教学 * 兰州理工大学兰州理工大学 计算机与通信学院 2013 年春季学期 算法与数据结构算法与数据结构 课程设计课程设计 题 目：1 求解素数问题；2 构造 可以使 n 个城市连接的最 小生成树；3 病人就医管 理模拟问题； 专业班级：计算机科学与技术 姓 名： 学 号： 指导教师： 成 绩：_ 0 目目 录录 摘摘 要要.2 一求素数问题一求素数问题.3 1.采用类语言定义相关的数据类型3 2.算法设计3 3.函数的调用关系图3 4.调试分析4 5.测试结果5 6.源程序（带注释）5 二二构造可以使构造可以使 N N 个城市连接的最小生成树个城市连接的最小生成树.8 1.采用类语言定义相关的数据类型8 2.算法设计8 3函数的调用关系图.9 4.调试分析10 5.测试结果11 6.源程序（带注释）14 三病人就医管理模拟问题三病人就医管理模拟问题.19 1.采用类语言定义相关的数据类型19 2.算法设计20 3函数的调用关系图.21 4.调试分析22 5.测试结果23 6.源程序（带注释）28 总总 结结.33 参考文献参考文献.34 致致 谢谢.34 1 摘摘 要要 1. 病人就医管理系统设计是关于对患者排队、就诊，查看排队、下班退出的 管理来设计的一个系统。整个系统从符合操作简便、界面友好、灵活、实用、 安全的要求出发，完成病人就医管理的全过程，包括创建一个链式队列、患者 排队、患者就诊、查看排队患者、下班退出等工作。 2.选择一颗生成树，使之总的消费最少，也就是要连通网的最小代价生成树 （简称为最小生成树）的问题，一颗生成树的代价就是树上各边的代价之和， 构造最小生成树可以有多种算法。 3.素数问题的求解是一种利用埃拉托色尼筛法（Sieve of Eratosthenes）来 查找小于 N 的素数的求解方法，它能够实现对数据 N 的输入，判断 N 是否越界， 查找小于 N 的素数，判断是否继续输入 N 等操作。 1.1.关键词：关键词：病人就医管理系统，C 语言，数据结构 2.2.关键词：关键词：最小生成树 连通图 克鲁斯卡尔算法 3.3.关键词关键词: : 素数问题 C 语言 数据结构 2 一求素数问题求素数问题 埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于 N 的素 数的方法。从建立一个整数 2N 的表着手，寻找 i的整数，编程实现此算法， 并讨论运算时间。(1) 1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型 定义一个线性表顺序存储结构，用来求所有小于 N 的素数 typedef int DataType;/数据类型 typedef struct DataType datamaxsize; 定义一个一维数组 int length;/线性表中实际元素的个数 Seqlist; 2.算法设计算法设计 用一个循环结构判断是否为素数，如果是素数则返回 1，负责返回 0。 int sushu(DataType if(i=1) return 0; for(m=2;m #include #define maxsize 200 #define FALSE 0 typedef int DataType; typedef struct DataType datamaxsize; int length; Seqlist;/结点结构 int sushu(DataType if(i=1) return 0; for(m=2;mL.length ) return FALSE; printf(“1 至 m 之间的素数从小到大分别为:n“); int i,k=0; for(i=1;in);i +) /*初始化数组 prex,rankx*/ set(i); for(i = 0;in);i +) for(j = i + 1;j n);j +) p+k.str = i; pk.end = j; pk.dis = g-adjij; /*先把所有城市之间的路段看成一个 边*/ for(i=0;i #include #include #define max 20/城市间边数 #define MAX_LNT 10 /城市数 # define INF 32627 /两个城市间无直接路径，用大数 32627 表示 typedef struct node /*构造一个结构体，两个城市可以看成起点和终点，之 间的道路可以看成一个边 */ int str; /*起点*/ int end; /*终点*/ int dis;/*距离*/ node; node pmax,temp;/*p 记录城市信息*/ typedef struct/邻接矩阵存储图结构 int vexsMAX_LNT;/数组用于存储城市数 int adjmax+1max+1;/图的邻接矩阵表示 int n,e; /n 代表城市数，e 代表城市间边 数 graph; int pre100,rank100;/*用于判断是否构成回路 */ /int arcsMAX_LNTMAX_LNT;/*n 表示城市个数， arcs记录城市间权 值*/ int menu( ) /*菜单函数*/ int m; 14 printf(“ 求最小生成树n“); printf(“ _nn“); printf(“ 1 输入城市之间的信息 n“); printf(“ 2 遍历所有城市生成最小生成树 n“); printf(“ 3 退出n“); printf(“ _nn“); printf(“ 请输入所选功能 1-3:n“); system(“color E“);/*改变界面颜色的*/ scanf(“%d“, return m; void create(graph *g)/*输入城市信息*/ int i,j,k; printf(“输入城市数为:“); scanf(“%d“, printf(“n“); printf(“输入个城市间边数为 :“); scanf(“%d“, printf(“输入城市的各个顶点为 :“); for(i=0;in);i+) scanf(“%d“, /顶点存入数组 vexs printf(“输入%d 条边，建立邻接矩阵 “,(g-e); printf(“n“); for(i=0;in);i+) /初始化邻接矩阵 for(j=0;jn);j+) if(i=j) g-adjij=0; else g-adjij=INF; printf(“请输入具有邻接关系的两个顶点在矩阵中所在的行与列及权值 : n“); for(k=0;ke);k+) /有 g-e 条边，即有 g-e 个权值 scanf(“%d,%d“, 15 scanf(“%d“, for(i=0;in);i+) for(j=0;jn);j+) g-adjji=g-adjij; printf(“ 图的邻接矩阵如下 n“); for(i=0;in);i+) /输出邻接矩阵 g for(j=0;jn);j+) if(g-adjij=INF) printf(“t%3s“,“); else printf(“t%3d“,g-adjij); printf(“n“); /*下面三个函数作用是检验当一条边添加进去，是否会产生回路 */ void set(int x)/*初始化*/ prex = x; rankx = 0; int find(int x)/*找到这个点的祖先 */ if(x != prex) prex = find(prex); return prex; void Union(int x,int y)/*将这两个添加到一个集合里去 */ x = find(x); y = find(y); if(rankx = ranky) prey = x; rankx +; else prey = x; 16 void Kruskal(graph *g ) int ans = 0,i,j,k = 0;/*ans 用来记录生成最小树的权总值 */ int index; int count = 0;/*记录打印边的条数 */ for(i = 0;in);i +) /*初始化数组 prex,rankx*/ set(i); for(i = 0;in);i +) for(j = i + 1;j n);j +) p+k.str = i; pk.end = j; pk.dis = g-adjij; /*先把所有城市之间的路段看成一个 边*/ for(i=0;in)=0) printf(“这里没有城市之间的信息 n“); return; printf(“遍历所有城市得到最小生成树为： nnn“); Kruskal(g); int main( ) /*主函数*/ graph *g=(graph*)malloc(sizeof(graph);/这是给 graph 类变量*g 分配一定 的内存空间， 分配的空间大小等于结构体 graph 的大小 while(1) switch( menu( ) ) case 1:create(g);break;/*输入城市信息*/ case 2:display(g);break; /*显示生成的最小生成树 */ case 3:exit(0); return 0; 18 三病人就医管理模拟问题病人就医管理模拟问题 编写一个程序定义行医类，反映病人到医院看病，排队看医生的情况，在 病人排队过程中，主要发生两件事： （1） 病人到达诊室，将病历本交给护士，排到等待队列中候诊。 （2） 护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。 要求程序采用菜单方式，其选项及功能说明如下： （1） 排队-输入病人的病历号，加入到病人排队队列中 （2） 就诊-病人排队队列中最前面的病人就诊，并将其从队列中删 除。 （3） 查看排队-从队首到队尾列出所有的排队病人的病历号。 （4） 下班-退出运行。 （5） 1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型 队列是一种特殊的线性表，是限制在表的一端进行插入和在另一端进行删除 的线性表。表中允许插入的一端称为队尾（rear） ，允许删除的一端称为对头 （front） 。队列可以采取顺序存储和链式存储两种方式，依据本课题要求采用链 式存储操作更为方便，故采用队列的链式存储这一数据结构来处理各种操作。具 体的结构定义如下： 1、链队节点元素（抽象出的病人数据结构）类型定义 typedef struct QNode char name25; status age; char sex3; struct QNode *next; QNode, *QueuePtr;/结点结构定义 2、将头尾指针封装在一起的链队（排队队列） typedef struct QueuePtr front; QueuePtr rear; 19 LinkQueue; 2.算法设计算法设计 该项目需要模拟病人看病的步骤，由于病人排队看病的一般规则是先到先排， 排在队前的先就诊。根据这个特点可以采取队列（先进先出）的形式来存储数据 元素构建数据结构。 依据该项目要求实现的排队、就诊、查看排队人数等功能，可以抽象出需要 设计的算法有：队列数据结构的定义、队列的初始化、队列的插入操作、队列的 删除操作、求队列长度以及销毁队列等基本操作。 InitQueue( typedef int status; char menubar()/菜单函数 int c=0; printf(“n*n“); printf(“n*欢迎进入就诊模拟系统 *nn“); printf(“ 1:排队n“); printf(“ 2:就诊n“); printf(“ 3:查看队列n“); printf(“ 4:不再排队n“); printf(“ 5:查询今天已有人数n“); printf(“ 6:正在候诊的人数n“); printf(“ 7:下班n“); printf(“n*n“); printf(“n 特注： 请输入数字选项(1-7):n“); do scanf(“%d“, getchar(); if(!(c=1 return OK; int i=0; status EnQueue(LinkQueue printf(“请输入年龄：“); scanf(“%d“, printf(“请输入性别(男性请输入 Mm，女性请输入 Ff): “); scanf(“%s“,p-sex); p-next=NULL; Q.rear-next=p; Q.rear=p; +i; return OK; else printf(“今日就诊人数已达上限!n“); return FALSE; status DeQueue(LinkQueue if(Q.front=Q.rear) printf(“此时无候诊病人“); 29 return ERROR; p=Q.front-next; if(p!=Q.rear) Q.front-next=p-next; else Q.rear=Q.front; printf(“请%s 就诊“,p-name); free(p); return OK; status QueueEmpty(LinkQueue Q)/判断队是否为空 if(Q.front=Q.rear) return TRUE; else return FALSE; status show(LinkQueue Q)/查看队列 if(Q.front=Q.rear) printf(“无候诊病人“); return 0; QueuePtr a; QueuePtr b; a=Q.front; Q.front=Q.front-next; b=Q.rear; printf(“ 姓名 年龄 性别n“); printf(“-n“); do printf(“%s %-4d %sn“,Q.front-name,Q.front- age,Q.front-sex); if(Q.front=Q.rear)return ERROR; Q.front=Q.front-next; while( Q.front!=Q.rear); printf(“%s %-4d %sn“,Q.front-name,Q.front-age,Q.front- sex); Q.front=a; Q.rear=b; 30 return 0; void Reshu(status a) printf(“今天已有人数n“); printf(“%d 人“,a); void pdrenshu(LinkQueue Q) int c=0; if(Q.front=Q.rear) printf(“无候诊病人“); printf(“%d 人“,c); else QueuePtr a; QueuePtr b; a=Q.front; Q.front=Q.front-next; b=Q.rear; while(Q.front!=Q.rear) +c; Q.front=Q.front-next; +c; printf(“%d“,c); Q.front=a; Q.rear=b; status DestroyQueue(LinkQueue Q)/队列销毁，释放队列的空间 QueuePtr p; if(Q.front=Q.rear) i=max; return OK; else do 31 p=Q.front-next; if(p!=Q.rear) Q.front-next=p-next; else Q.rear=Q.front; free(p); while(Q.rear!=Q.front); free(Q.rear); Q.rear=Q.front; i=max; return OK; void workoff(LinkQueue Q) DestroyQueue(Q); printf(“现在已下班，后续病人无法继续就诊！nn“); void bzpd(LinkQueue Q) printf(“临近下班，停止排队，请明日再来，如给您带来不便，敬请谅解！ n“); i=max; void main() LinkQueue x; InitQueue(x); int m=1; while(m=!0) switch(menubar() case 1:EnQueue(x);break; case 2:DeQueue(x);break; case 3:show(x);break; case 4:bzpd(x);break; case 5:Re