多叉路口交通燈管理 一、
需求分析 1. 設計背景 通常，在十字路口只需設紅、綠兩色的交通燈便可以保證正常的交通秩序，而在多叉路口需設計幾種顏色的交通燈才能既使車(chē)輛相互之間不碰撞，又能達到車(chē)輛的最大流量。該程序就是在多叉路口情況下，判斷各個(gè)路口交通燈顏色，以便人們進(jìn)行管理。對于用戶(hù)任意輸入的多叉路口（實(shí)際輸入所有的可以通行的方向及數量，從而構建出圖），輸出需要的交通燈的數量。
2. 任務(wù)概述 假設有一個(gè)如圖 1 所示的五叉路口，其中 C 和 E 為單行道。在路口有 13 條可行的道路，其中有的可以同時(shí)通行，如 A—>B 和 E—>C，而有的不能同事通行，如 E—>B，A—>D，那么，如何設置交通燈呢？
每個(gè)圓圈表示五叉路口上的一條通路，兩個(gè)圓圈之間的連線(xiàn)表示這兩個(gè)圓圈表示的兩條道路不能同事通行。設置交通燈的問(wèn)題等價(jià)為對圖的頂點(diǎn)進(jìn)行染色問(wèn)題。要求對圖上的每個(gè)頂點(diǎn)染一種顏色，并且要求有限相連的兩個(gè)頂點(diǎn)不能具有相同顏色，而且總的顏色種類(lèi)盡可能少。所以，我準備把每個(gè)頂點(diǎn)用字母“a、b、c、……”表示，而染色的顏色用數字表示。
可以同時(shí)通行的道路交通燈的顏色相同，不能同時(shí)通行的顏色不同。頂點(diǎn) 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，頂點(diǎn)之間的邊全都用“1”表示。
二、 詳細設計 在動(dòng)手編制程序之前，先要做好程序的規劃，包括程序儲存數據所用的結構，數據類(lèi)型等等，只有確定了數據類(lèi)型和數據結構，才能在此基礎上進(jìn)行各種算法的設計和程序的編寫(xiě)。
1. 數據結構 首先，是考慮數據類(lèi)型。在多叉路口中，每條通路是最基本的組成部分，對于交通燈管理已經(jīng)不可能在細分了，所以選定通路作為數據的基本類(lèi)型，并在程序中定義圖的數據結構,其中包含存放圖的頂點(diǎn)和圖的邊，以及頂點(diǎn)數和邊數。用鄰接矩陣表示圖的結構。其形式描述如下：
int color[30]={0};//來(lái)存儲對應塊的對應顏色 typedef char vextype; typedef int adjtype; typedef struct
//定義圖 {
vextype vexs[MAXedg];
//存放邊的矩陣
adjtype arcs[MAXedg][MAXedg];
//圖的鄰接矩陣
int vnum,arcnum;
//圖的頂點(diǎn)數和邊數 }Graph;
在選擇數據結構方面，直接用數組來(lái)存儲數據，即使是在內存中也用數組來(lái)處理數據間的聯(lián)系。運用順序表這個(gè)結構雖然不是那么直觀(guān)，但在查找數據時(shí)的算法設計比較簡(jiǎn)單容易實(shí)現，效率高，而且在內存中的數據可以直接讀入到文件中，文件中的數據也可以直接讀入內存，不需要進(jìn)行轉換。所以在衡量的各個(gè)方面之后，我決定用數組來(lái)處理數據間的聯(lián)系。
2. 算法流程圖 2.1 建立鄰接矩陣的流程圖
2.2 交通燈顏色模塊的流程圖
3 ．函數之間的調用關(guān)系圖 圖 構想好總體規劃之后，便開(kāi)始設計程序中需要用到的各個(gè)功能函數，輸入圖函數、染色函數、輸出函數等。
3.1 輸入圖函數 void Create(Graph &G) 考慮到輸入的問(wèn)題，就是在輸入界面以何種形式輸入，輸入頂點(diǎn)和邊數以及邊的權值在計算機內部建立數組存儲。部分代碼如下：
printf("輸入多叉路口的頂點(diǎn)數和邊數:\n");
scanf("%d%d",&G.vnum,&G.arcnum);
getchar();
printf("輸入多叉路口的各頂點(diǎn)：\n");
for(i=1;i<=G.vnum;i++)
{
scanf("%c",&G.vexs[i]);
getchar();
}
printf("輸入邊的兩個(gè)頂點(diǎn)和權值:\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) 給各個(gè)頂點(diǎn)染色，然后輸出染色結果，并調用判斷顏色是否滿(mǎn)足要求函數。從第一個(gè)頂點(diǎn)開(kāi)始染色，而后判斷和其相鄰的頂點(diǎn)的顏色是夠與第一個(gè)頂點(diǎn)相同。部分代碼如下：
if(s>G.vnum)
{
output(G);
exit(1);
}
else
{
for(i=1;i<=N;i++)//對每一種色彩逐個(gè)測試
{
color[s]=i;
if(colorsame(s,G)==0)
trycolor(s+1,G);//進(jìn)行下一塊的著(zhù)色
}
} 3.3 定位函數 int LocateVex(Graph G,char u) 在已經(jīng)輸入的圖中，找到與要記錄的頂點(diǎn)在圖中的位置，返回值是在數組中的位置。部分代碼如下：
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("多叉路口的各頂點(diǎn)：\n");
for(i=1;i<=G.vnum;i++)
printf("%c ",G.vexs[i]);
printf("\n");
printf("相應的亮燈方案:\n");
trycolor(1,G);
return 0;
} 三、 調試分析 1 經(jīng)驗體會(huì ) 通過(guò)這次課設，體會(huì )很深刻，將一直以來(lái)學(xué)到的東西都運用到實(shí)際上來(lái)，學(xué)以致用，對
所學(xué)知識有了更深刻的理解，同時(shí)還發(fā)現了許多平時(shí)在書(shū)本上沒(méi)有遇見(jiàn)過(guò)的問(wèn)題，促進(jìn)了自己對知識的渴望，遇見(jiàn)了問(wèn)題，就希望能夠通過(guò)查找課外書(shū)來(lái)解決它們。剛接觸題目的時(shí)候，自己就有了一定的想法，覺(jué)得這個(gè)程序做起來(lái)是問(wèn)題不大的，但到了自己真正開(kāi)始編程的時(shí)候卻發(fā)現遠遠沒(méi)有想象中那么簡(jiǎn)單，很多細節的問(wèn)題沒(méi)有預想到，很多關(guān)系的處理想得過(guò)于簡(jiǎn)單，以至于實(shí)施起來(lái)遇到了很大的困難，花了大量的時(shí)間。
2 算法改進(jìn) 關(guān)于這個(gè)程序的缺點(diǎn)方面，由于自己花的時(shí)間不是很多，再加上知識有限，并不會(huì )運用可視化編程工具來(lái)輔助自己編程，所以弄得這個(gè)程序的不足之處還是挺多的，首當其沖的是程序界面，一開(kāi)始的時(shí)候是注重功能的實(shí)現，并沒(méi)有怎么理會(huì )運用界面，而到了后期，當辛辛苦苦搞好了功能之后，界面就沒(méi)有動(dòng)力再去弄了，所以程序的界面很粗糙。
四、 用戶(hù)手冊 在 VC++環(huán)境下，運行該程序。根據提示輸入多叉路口的頂點(diǎn)數和邊數，例如五叉路口的情況，頂點(diǎn) 13 個(gè)，20 條邊，就輸入 13 20 然后回車(chē)，根據提示輸入頂點(diǎn) a b c d e f g h i j k l m 回車(chē)，根據提示輸入兩個(gè)頂點(diǎn)和權值 a j 1 a e 1…回車(chē)，程序結果就出現在屏幕上了“亮燈方案：1 1 1 1 2 2 3 3 1 2 4 4 1” 五、 測試結果 正確輸入時(shí)結果如下圖 第一組：
第二組：
第三組：
第四組：錯誤輸入后，如果不按照要求輸入， 測試結果：系統沒(méi)能作出良好提示，突然退出
六、 附錄 #include <stdio.h> #include <stdlib.h> #define MAXedg 30 #define MAX 0 #define N 4
//亮燈的顏色數 int color[30]={0};//來(lái)存儲對應塊的對應顏色 typedef char vextype; typedef int adjtype; typedef struct
//定義圖 {
vextype vexs[MAXedg];
//存放邊的矩陣
adjtype arcs[MAXedg][MAXedg];
//圖的鄰接矩陣
int vnum,arcnum;
//圖的頂點(diǎn)數和邊數 }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("輸入多叉路口的頂點(diǎn)數和邊數:\n");
scanf("%d%d",&G.vnum,&G.arcnum);
getchar();
printf("輸入多叉路口的各頂點(diǎn)：\n");
for(i=1;i<=G.vnum;i++)
{
scanf("%c",&G.vexs[i]);
getchar();
}
printf("輸入邊的兩個(gè)頂點(diǎn)和權值:\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)//判斷這個(gè)顏色能不能滿(mǎn)足要求 {
int i,flag=0;
for(i=1;i<=s-1;i++)//分別于前面已經(jīng)著(zhù)色的幾塊比較
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 為開(kāi)始圖色的頂點(diǎn)，從 1 開(kāi)始 {
int i;
if(s>G.vnum)
{
output(G);
exit(1);
}
else
{
for(i=1;i<=N;i++)//對每一種色彩逐個(gè)測試
{
color[s]=i;
if(colorsame(s,G)==0)
trycolor(s+1,G);//進(jìn)行下一塊的著(zhù)色
}
} }
int main() {
int i,j;
Graph G;
Create(G);
printf("多叉路口的各頂點(diǎn)：\n");
for(i=1;i<=G.vnum;i++)
printf("%c ",G.vexs[i]);
printf("\n");
printf("相應的亮燈方案:\n");
trycolor(1,G);
return 0;
}
家庭成員的管理問(wèn)題 一、
需求分析 1. 設計背景 例如有這樣的一對老夫妻（A、B），他們生有 n 男 m 女，其中，某個(gè)兒子（D）娶妻（C）生有 x 男 y 女，某個(gè)女兒（E）嫁夫（F）生有 i 男 j 女，其余的子女有可能婚嫁，也有可能單身，已婚的可能生有孩子若干，其孩子相繼婚嫁…… 數據對象是以上所有的家庭成員，要求建立他們之間的夫妻、子女等關(guān)系并方便查詢(xún)。
2. 任務(wù)概述 家譜用于記錄某家族歷代家族成員的情況與關(guān)系?，F編制一個(gè)家譜資料管理程序，實(shí)現對一個(gè)家族所有的資料進(jìn)行收集整理。構建數據模型，按時(shí)間關(guān)系建立他們之間的夫妻，子女等關(guān)系。按姓名查詢(xún)某個(gè)家庭成員及其配偶和孩子 二、
詳細設計 在動(dòng)手編制程序之前，先要做好程序的規劃，包括程序儲存數據所用的結構，數據類(lèi)型等等，只有確定了數據類(lèi)型和數據結構，才能在此基礎上進(jìn)行各種算法的設計和程序的編寫(xiě)。
1. 數據結構 首先是考慮數據類(lèi)型。在家譜中，家族成員是最基本的組成部分，對于家族管理中，已經(jīng)不能再進(jìn)行細分了，所以選定家族成員作為數據的基本類(lèi)型。定義每個(gè)成員為一個(gè)結點(diǎn)，結點(diǎn)屬性包括成員的姓名和左右子樹(shù)的指針，為了查找方便，我設計父親結點(diǎn)的左孩子根結點(diǎn)是該父親結點(diǎn)的配偶，而父親結點(diǎn)的右孩子根結點(diǎn)是其父親結點(diǎn)的孩子。性別的辨別是通過(guò)用戶(hù)輸入“m”或“f”來(lái)辨別，并沒(méi)有定義其屬性。
struct treenode{
char name[10];
struct treenode *left,*right;
}; 2. 算法流程圖
2.1. 建樹(shù)的流程圖
2.2 查找父親節點(diǎn)流程圖
2.3 查找孩子結點(diǎn)流程圖
2.4 插入妻子和孩子函數的流程圖
3 ．函數之間的調用關(guān)系圖 構想好總體規劃之后，便開(kāi)始設計程序中需要用到的各個(gè)功能函數，輸入圖函數、染色函數、輸出函數等。
重要函數的大體思想看下面：
3.1 建樹(shù)函數
struct treenode *creatree()
由屏幕輸入結點(diǎn)姓名和其配偶，再添加孩子結點(diǎn)，逐步建立樹(shù)。
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("父親結點(diǎn):");
scanf("%s",xm);
if(strcmp(xm,"#")==0)contin=0;
else
{ p=findfather(btree,xm);
if(p!=NULL)
{ p=p->left;
if(p==NULL)
printf("不能有孩子,因為沒(méi)有配偶\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("不存在這樣的父親結點(diǎn)!\n");
}
3.2 插入函數
void
insert(struct treenode**p)
插入函數是插入配偶或插入孩子的函數，先從父親結點(diǎn)進(jìn)行查找，如果不存在則結束，倘若存在則遍歷其左子樹(shù)，為空則插入其配偶結點(diǎn)，不空則在其配偶結點(diǎn)右子樹(shù)插入孩子結點(diǎn)。部分代碼如下：
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 查找父親結點(diǎn)函數
struct treenode *findfather(struct treenode *p,char xm[])
對二叉樹(shù)進(jìn)行查找，先進(jìn)行根結點(diǎn)查找，而后左子樹(shù)再右子樹(shù)查找。部分代碼如下：
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 查找孩子結點(diǎn)函數
void findson(struct treenode *bt)
查找孩子結點(diǎn)，是先f(wàn)indfather （）找出這樣的父親結點(diǎn)p是否存在，若存在則p=p->left,再查找 p 是否為空，即是夠有配偶，若配偶存在再查找配偶結點(diǎn)的右子樹(shù)，返回孩子的信息。
p=findfather(bt,xm);
if(p==NULL)
printf("不存在這樣的父親結點(diǎn)\n");
else {
p=p->left;
//p=p->right;
if((!p)||(!(p->right)))
{
printf("配偶:");
printf("%s\n",p->name);
printf("沒(méi)有孩子\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. 經(jīng)驗總結 好的數據結構有時(shí)比好的算法更能給程序帶來(lái)便捷 2. 時(shí)空分析 時(shí)間效率：O(n)； 空間效率:O(n+e)。
3. 算法改進(jìn)分析 家庭成員的以什么數據結構來(lái)存儲對本題來(lái)說(shuō)是非常重要。除了我給出來(lái)的這種程序結構外，還可以嘗試建立二叉樹(shù)，但是鑒于二叉樹(shù)不能不易向上回溯查找父母結點(diǎn)。
4．經(jīng)驗和體會(huì ) 先思而后行可以減少無(wú)謂的時(shí)間，心細與不孜可以減少無(wú)謂的錯誤。
四、
用戶(hù)手冊 在 VC++環(huán)境下，運行該程序。系統提供了良好的提示，根據提示輸入父親、配偶。用戶(hù)可以先自己在草稿紙上建立家庭關(guān)系，然后依照提示嚴格輸入。具體操作可以參考測試結果中用例，這里不再贅述。
五、
測試結果
第一組：
第二組：
第三組：
第四組，查找無(wú)父親結點(diǎn)時(shí)，仍可繼續輸入：
六、
附錄 #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("建立一個(gè)家譜二叉樹(shù)(以#結尾):\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("父親結點(diǎn):");
scanf("%s",xm);
if(strcmp(xm,"#")==0)contin=0;
else
{ p=findfather(btree,xm);
if(p!=NULL)
{ p=p->left;
if(p==NULL)
printf("不能有孩子,因為沒(méi)有配偶\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("不存在這樣的父親結點(diǎn)!\n");
}
}
}
return(btree);
}
void findson(struct treenode *bt)
{
char xm[10];
struct treenode *p;
printf("查找指定父親的所有孩子\n");
printf("父親結點(diǎn)：");
scanf("%s",xm);
p=findfather(bt,xm);
if(p==NULL)
printf("不存在這樣的父親結點(diǎn)\n");
else {
p=p->left;
//p=p->right;
if((!p)||(!(p->right)))
{
printf("配偶:");
printf("%s\n",p->name);
printf("沒(méi)有孩子\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;
}
}
}
