多叉路口交通燈數據結構

　多叉路口交通燈管理 一、

　需求分析 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. 任務概述 家譜用于記錄某家族歷代家族成員的情況與關系?，F編制一個家譜資料管理程序，實現對一個家族所有的資料進行收集整理。構建數據模型，按時間關系建立他們之間的夫妻，子女等關系。按姓名查詢某個家庭成員及其配偶和孩子 二、

　詳細設計 在動手編制程序之前，先要做好程序的規劃，包括程序儲存數據所用的結構，數據類型等等，只有確定了數據類型和數據結構，才能在此基礎上進行各種算法的設計和程序的編寫。

　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;

　}

　}

　 }