多叉路口交通灯管理 一、
需求分析 1. 设计背景 通常，在十字路口只需设红、绿两色的交通灯便可以保证正常的交通秩序，而在多叉路口需设计几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流量。该程序就是在多叉路口情况下，判断各个路口交通灯颜色，以便人们进行管理。对于用户任意输入的多叉路口（实际输入所有的可以通行的方向及数量，从而构建出图），输出需要的交通灯的数量。
2. 任务概述 假设有一个如图 1 所示的五叉路口，其中 C 和 E 为单行道。在路口有 13 条可行的道路，其中有的可以同时通行，如 A—>B 和 E—>C，而有的不能同事通行，如 E—>B，A—>D，那么，如何设置交通灯呢？
每个圆圈表示五叉路口上的一条通路，两个圆圈之间的连线表示这两个圆圈表示的两条道路不能同事通行。设置交通灯的问题等价为对图的顶点进行染色问题。要求对图上的每个顶点染一种颜色，并且要求有限相连的两个顶点不能具有相同颜色，而且总的颜色种类尽可能少。所以，我准备把每个顶点用字母“a、b、c、……”表示，而染色的颜色用数字表示。
可以同时通行的道路交通灯的颜色相同，不能同时通行的颜色不同。顶点 AB 为 a，AC 为 b，AD 为 c，BA 为 d，BC 为 e，BD 为 f，DA 为 g，DB 为 h，DC 为 i，EA 为 j，EB 为 k，EC为 l，ED 为 m，顶点之间的边全都用“1”表示。
二、 详细设计 在动手编制程序之前，先要做好程序的规划，包括程序储存数据所用的结构，数据类型等等，只有确定了数据类型和数据结构，才能在此基础上进行各种算法的设计和程序的编写。
1. 数据结构 首先，是考虑数据类型。在多叉路口中，每条通路是最基本的组成部分，对于交通灯管理已经不可能在细分了，所以选定通路作为数据的基本类型，并在程序中定义图的数据结构,其中包含存放图的顶点和图的边，以及顶点数和边数。用邻接矩阵表示图的结构。其形式描述如下：
int color[30]={0};//来存储对应块的对应颜色 typedef char vextype; typedef int adjtype; typedef struct
//定义图 {
vextype vexs[MAXedg];
//存放边的矩阵
adjtype arcs[MAXedg][MAXedg];
//图的邻接矩阵
int vnum,arcnum;
//图的顶点数和边数 }Graph;
在选择数据结构方面，直接用数组来存储数据，即使是在内存中也用数组来处理数据间的联系。运用顺序表这个结构虽然不是那么直观，但在查找数据时的算法设计比较简单容易实现，效率高，而且在内存中的数据可以直接读入到文件中，文件中的数据也可以直接读入内存，不需要进行转换。所以在衡量的各个方面之后，我决定用数组来处理数据间的联系。
2. 算法流程图 2.1 建立邻接矩阵的流程图
2.2 交通灯颜色模块的流程图
3 ．函数之间的调用关系图 图 构想好总体规划之后，便开始设计程序中需要用到的各个功能函数，输入图函数、染色函数、输出函数等。
3.1 输入图函数 void Create(Graph &G) 考虑到输入的问题，就是在输入界面以何种形式输入，输入顶点和边数以及边的权值在计算机内部建立数组存储。部分代码如下：
printf("输入多叉路口的顶点数和边数:\n");
scanf("%d%d",&G.vnum,&G.arcnum);
getchar();
printf("输入多叉路口的各顶点：\n");
for(i=1;i<=G.vnum;i++)
{
scanf("%c",&G.vexs[i]);
getchar();
}
printf("输入边的两个顶点和权值:\n");
for(k=0;k<G.arcnum;k++)
{
scanf("%c", &v1);getchar();
scanf("%c", &v2);getchar();
scanf("%d", &w); getchar();
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=w;
G.arcs[j][i]=w; } 3.2 染色函数 void trycolor(int s,Graph G) 给各个顶点染色，然后输出染色结果，并调用判断颜色是否满足要求函数。从第一个顶点开始染色，而后判断和其相邻的顶点的颜色是够与第一个顶点相同。部分代码如下：
if(s>G.vnum)
{
output(G);
exit(1);
}
else
{
for(i=1;i<=N;i++)//对每一种色彩逐个测试
{
color[s]=i;
if(colorsame(s,G)==0)
trycolor(s+1,G);//进行下一块的着色
}
} 3.3 定位函数 int LocateVex(Graph G,char u) 在已经输入的图中，找到与要记录的顶点在图中的位置，返回值是在数组中的位置。部分代码如下：
for(i=1;i<=G.vnum;i++)
{
if(u==G.vexs[i])
return i;
}
if(i==G.vnum)
{
printf("Error u!\n");
exit(1);
}
return 0; 3.4 主程序 int main() {
int i,j;
Graph G;
Create(G);
printf("多叉路口的各顶点：\n");
for(i=1;i<=G.vnum;i++)
printf("%c ",G.vexs[i]);
printf("\n");
printf("相应的亮灯方案:\n");
trycolor(1,G);
return 0;
} 三、 调试分析 1 经验体会 通过这次课设，体会很深刻，将一直以来学到的东西都运用到实际上来，学以致用，对
所学知识有了更深刻的理解，同时还发现了许多平时在书本上没有遇见过的问题，促进了自己对知识的渴望，遇见了问题，就希望能够通过查找课外书来解决它们。刚接触题目的时候，自己就有了一定的想法，觉得这个程序做起来是问题不大的，但到了自己真正开始编程的时候却发现远远没有想象中那么简单，很多细节的问题没有预想到，很多关系的处理想得过于简单，以至于实施起来遇到了很大的困难，花了大量的时间。
2 算法改进 关于这个程序的缺点方面，由于自己花的时间不是很多，再加上知识有限，并不会运用可视化编程工具来辅助自己编程，所以弄得这个程序的不足之处还是挺多的，首当其冲的是程序界面，一开始的时候是注重功能的实现，并没有怎么理会运用界面，而到了后期，当辛辛苦苦搞好了功能之后，界面就没有动力再去弄了，所以程序的界面很粗糙。
四、 用户手册 在 VC++环境下，运行该程序。根据提示输入多叉路口的顶点数和边数，例如五叉路口的情况，顶点 13 个，20 条边，就输入 13 20 然后回车，根据提示输入顶点 a b c d e f g h i j k l m 回车，根据提示输入两个顶点和权值 a j 1 a e 1…回车，程序结果就出现在屏幕上了“亮灯方案：1 1 1 1 2 2 3 3 1 2 4 4 1” 五、 测试结果 正确输入时结果如下图 第一组：
第二组：
第三组：
第四组：错误输入后，如果不按照要求输入， 测试结果：系统没能作出良好提示，突然退出
六、 附录 #include <stdio.h> #include <stdlib.h> #define MAXedg 30 #define MAX 0 #define N 4
//亮灯的颜色数 int color[30]={0};//来存储对应块的对应颜色 typedef char vextype; typedef int adjtype; typedef struct
//定义图 {
vextype vexs[MAXedg];
//存放边的矩阵
adjtype arcs[MAXedg][MAXedg];
//图的邻接矩阵
int vnum,arcnum;
//图的顶点数和边数 }Graph;
int LocateVex(Graph G,char u) {
int i;
for(i=1;i<=G.vnum;i++)
{
if(u==G.vexs[i])
return i;
}
if(i==G.vnum)
{
printf("Error u!\n");
exit(1);
}
return 0; }
void Create(Graph &G)
//输入图 {
int i,j,k,w;
vextype v1,v2;
printf("输入多叉路口的顶点数和边数:\n");
scanf("%d%d",&G.vnum,&G.arcnum);
getchar();
printf("输入多叉路口的各顶点：\n");
for(i=1;i<=G.vnum;i++)
{
scanf("%c",&G.vexs[i]);
getchar();
}
printf("输入边的两个顶点和权值:\n");
for(k=0;k<G.arcnum;k++)
{
scanf("%c", &v1);getchar();
scanf("%c", &v2);getchar();
scanf("%d", &w); getchar();
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=w;
G.arcs[j][i]=w;
} }
int colorsame(int s,Graph G)//判断这个颜色能不能满足要求 {
int i,flag=0;
for(i=1;i<=s-1;i++)//分别于前面已经着色的几块比较
if(G.arcs[i][s]==1&&color[i]==color[s])
{flag=1;break;}
return flag; }
void output(Graph G) {
int i;
for(i=1;i<=G.vnum;i++)
printf("%d ",color[i]);
printf("\n"); }
void trycolor(int s,Graph G)//s 为开始图色的顶点，从 1 开始 {
int i;
if(s>G.vnum)
{
output(G);
exit(1);
}
else
{
for(i=1;i<=N;i++)//对每一种色彩逐个测试
{
color[s]=i;
if(colorsame(s,G)==0)
trycolor(s+1,G);//进行下一块的着色
}
} }
int main() {
int i,j;
Graph G;
Create(G);
printf("多叉路口的各顶点：\n");
for(i=1;i<=G.vnum;i++)
printf("%c ",G.vexs[i]);
printf("\n");
printf("相应的亮灯方案:\n");
trycolor(1,G);
return 0;
}
家庭成员的管理问题 一、
需求分析 1. 设计背景 例如有这样的一对老夫妻（A、B），他们生有 n 男 m 女，其中，某个儿子（D）娶妻（C）生有 x 男 y 女，某个女儿（E）嫁夫（F）生有 i 男 j 女，其余的子女有可能婚嫁，也有可能单身，已婚的可能生有孩子若干，其孩子相继婚嫁…… 数据对象是以上所有的家庭成员，要求建立他们之间的夫妻、子女等关系并方便查询。
2. 任务概述 家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理程序，实现对一个家族所有的资料进行收集整理。构建数据模型，按时间关系建立他们之间的夫妻，子女等关系。按姓名查询某个家庭成员及其配偶和孩子 二、
详细设计 在动手编制程序之前，先要做好程序的规划，包括程序储存数据所用的结构，数据类型等等，只有确定了数据类型和数据结构，才能在此基础上进行各种算法的设计和程序的编写。
1. 数据结构 首先是考虑数据类型。在家谱中，家族成员是最基本的组成部分，对于家族管理中，已经不能再进行细分了，所以选定家族成员作为数据的基本类型。定义每个成员为一个结点，结点属性包括成员的姓名和左右子树的指针，为了查找方便，我设计父亲结点的左孩子根结点是该父亲结点的配偶，而父亲结点的右孩子根结点是其父亲结点的孩子。性别的辨别是通过用户输入“m”或“f”来辨别，并没有定义其属性。
struct treenode{
char name[10];
struct treenode *left,*right;
}; 2. 算法流程图
2.1. 建树的流程图
2.2 查找父亲节点流程图
2.3 查找孩子结点流程图
2.4 插入妻子和孩子函数的流程图
3 ．函数之间的调用关系图 构想好总体规划之后，便开始设计程序中需要用到的各个功能函数，输入图函数、染色函数、输出函数等。
重要函数的大体思想看下面：
3.1 建树函数
struct treenode *creatree()
由屏幕输入结点姓名和其配偶，再添加孩子结点，逐步建立树。
while(contin)
{ if(frist==1)
{
btree=new treenode;
printf("姓名:");
scanf("%s",btree->name);
btree->right=NULL;
s=new treenode;
printf("配偶:");
scanf("%s",s->name);
s->right=s->left=NULL;
btree->left=s; frist=0;
}
else{
printf("父亲结点:");
scanf("%s",xm);
if(strcmp(xm,"#")==0)contin=0;
else
{ p=findfather(btree,xm);
if(p!=NULL)
{ p=p->left;
if(p==NULL)
printf("不能有孩子,因为没有配偶\n");
else
{
while(p->right!=NULL)
p=p->right;
s=new treenode;
s->right=NULL;
p->right=s;
printf("孩子:");
scanf("%s",s->name);
printf("配偶:");
scanf("%s",xm);
if(strcmp(xm,"#")!=0)
{
t=new treenode;
strcpy(t->name,xm);
t->left=t->right=NULL;
s->left=t;
}
else s->left=NULL;
}
}
else printf("不存在这样的父亲结点!\n");
}
3.2 插入函数
void
insert(struct treenode**p)
插入函数是插入配偶或插入孩子的函数，先从父亲结点进行查找，如果不存在则结束，倘若存在则遍历其左子树，为空则插入其配偶结点，不空则在其配偶结点右子树插入孩子结点。部分代码如下：
if(!t->left)
{
t->left=q;
q->right=NULL;
q->left=NULL;
}
else
{
t=t->left;
while(t->right)
{
t=t->right;
}
t->right=q;
q->right=NULL;
q->left=NULL;
} 3.3 查找父亲结点函数
struct treenode *findfather(struct treenode *p,char xm[])
对二叉树进行查找，先进行根结点查找，而后左子树再右子树查找。部分代码如下：
if(p==NULL)return(NULL);
else
{ if(strcmp(p->name,xm)==0)return(p);
else
{ bt=findfather(p->left,xm);
if(bt!=NULL)return(bt);
else return(findfather(p->right,xm));
}
}
3.4 查找孩子结点函数
void findson(struct treenode *bt)
查找孩子结点，是先findfather （）找出这样的父亲结点p是否存在，若存在则p=p->left,再查找 p 是否为空，即是够有配偶，若配偶存在再查找配偶结点的右子树，返回孩子的信息。
p=findfather(bt,xm);
if(p==NULL)
printf("不存在这样的父亲结点\n");
else {
p=p->left;
//p=p->right;
if((!p)||(!(p->right)))
{
printf("配偶:");
printf("%s\n",p->name);
printf("没有孩子\n");
}
else
{ printf("配偶:");
printf("%s\n",p->name);
printf("有以下孩子:\n");
p=p->right;
while(p!=NULL)
{
printf("%s\n",p->name);
p=p->right;}
}
} 3.5 主函数
void main()
void main()
{
struct treenode *bt,*p;
int i,j,flag=1;
char ch[10];
bt=creatree();
while(flag)
{
printf("1,查找 2,加孩子 3,结婚 0,结束\n");
scanf("%d",&j);
switch(j)
{
case 1:printf("查找\n");
findson(bt);
break;
case 2:printf("\n 请输入要加孩子的人的姓名\n");
scanf("%s",ch);
p=findfather(bt,ch);
if(!(p->left))
printf("该人未婚");
else
insert(&p);
break;
case 3:printf("\n 请输入要结婚的人的姓名\n");
scanf("%s",ch);
p=findfather(bt,ch);
if(p->left)
printf("该人已婚");
else
insert(&p);
break;
case 0: flag=0;
break;
}
}
} 三、
调试分析 1. 经验总结 好的数据结构有时比好的算法更能给程序带来便捷 2. 时空分析 时间效率：O(n)； 空间效率:O(n+e)。
3. 算法改进分析 家庭成员的以什么数据结构来存储对本题来说是非常重要。除了我给出来的这种程序结构外，还可以尝试建立二叉树，但是鉴于二叉树不能不易向上回溯查找父母结点。
4．经验和体会 先思而后行可以减少无谓的时间，心细与不孜可以减少无谓的错误。
四、
用户手册 在 VC++环境下，运行该程序。系统提供了良好的提示，根据提示输入父亲、配偶。用户可以先自己在草稿纸上建立家庭关系，然后依照提示严格输入。具体操作可以参考测试结果中用例，这里不再赘述。
五、
测试结果
第一组：
第二组：
第三组：
第四组，查找无父亲结点时，仍可继续输入：
六、
附录 #include<stdio.h> #include<stdlib.h>
#include<string.h>
struct treenode{
char name[10];
struct treenode *left,*right;
};
struct treenode *findfather(struct treenode *p,char xm[])
{ struct treenode*bt;
if(p==NULL)return(NULL);
else
{ if(strcmp(p->name,xm)==0)return(p);
else
{ bt=findfather(p->left,xm);
if(bt!=NULL)return(bt);
else return(findfather(p->right,xm));
}
}
}
struct treenode *creatree()
{
int contin=1;int frist=1;
char xm[10];
struct treenode *btree,*s,*t,*p;
printf("输入"m"是儿子,f"是女儿:\n");
printf("建立一个家谱二叉树(以#结尾):\n");
while(contin)
{ if(frist==1)
{
btree=new treenode;
printf("姓名:");
scanf("%s",btree->name);
btree->right=NULL;
s=new treenode;
printf("配偶:");
scanf("%s",s->name);
s->right=s->left=NULL;
btree->left=s; frist=0;
}
else{
printf("父亲结点:");
scanf("%s",xm);
if(strcmp(xm,"#")==0)contin=0;
else
{ p=findfather(btree,xm);
if(p!=NULL)
{ p=p->left;
if(p==NULL)
printf("不能有孩子,因为没有配偶\n");
else
{
while(p->right!=NULL)
p=p->right;
s=new treenode;
s->right=NULL;
p->right=s;
printf("孩子:");
scanf("%s",s->name);
printf("配偶:");
scanf("%s",xm);
if(strcmp(xm,"#")!=0)
{
t=new treenode;
strcpy(t->name,xm);
t->left=t->right=NULL;
s->left=t;
}
else s->left=NULL;
}
}
else printf("不存在这样的父亲结点!\n");
}
}
}
return(btree);
}
void findson(struct treenode *bt)
{
char xm[10];
struct treenode *p;
printf("查找指定父亲的所有孩子\n");
printf("父亲结点：");
scanf("%s",xm);
p=findfather(bt,xm);
if(p==NULL)
printf("不存在这样的父亲结点\n");
else {
p=p->left;
//p=p->right;
if((!p)||(!(p->right)))
{
printf("配偶:");
printf("%s\n",p->name);
printf("没有孩子\n");
}
else
{ printf("配偶:");
printf("%s\n",p->name);
printf("有以下孩子:\n");
p=p->right;
while(p!=NULL)
{
printf("%s\n",p->name);
p=p->right;}
}
}
} void insert(struct treenode**p) {
struct treenode*t,*q;
t=*p;
q=(struct treenode*)malloc(sizeof(treenode));
printf("请输入添加人的姓名\n");
scanf("%s",q->name);
if(!t->left)
{
t->left=q;
q->right=NULL;
q->left=NULL;
}
else
{
t=t->left;
while(t->right)
{
t=t->right;
}
t->right=q;
q->right=NULL;
q->left=NULL;
} }
void main()
{
struct treenode *bt,*p;
int i,j,flag=1;
char ch[10];
bt=creatree();
while(flag)
{
printf("1,查找 2,加孩子 3,结婚 0,结束\n");
scanf("%d",&j);
switch(j)
{
case 1:printf("查找\n");
findson(bt);
break;
case 2:printf("\n 请输入要加孩子的人的姓名\n");
scanf("%s",ch);
p=findfather(bt,ch);
if(!(p->left))
printf("该人未婚");
else
insert(&p);
break;
case 3:printf("\n 请输入要结婚的人的姓名\n");
scanf("%s",ch);
p=findfather(bt,ch);
if(p->left)
printf("该人已婚");
else
insert(&p);
break;
case 0: flag=0;
break;
}
}
}
