北京工業(yè)大學 數(shù)據(jù)結(jié)構(gòu)課設_理發(fā)館 報告

1、理發(fā)館學 號_110703xx_ 姓 名_xxx_指導教師_xx_2013年10月目錄1 需求分析 31.1 程序功能介紹 31.2 程序數(shù)據(jù)要求 3 1.3 開發(fā)與運行環(huán)境需求 41.4 用戶界面設計 52 數(shù)據(jù)結(jié)構(gòu)設計 72.1 主要數(shù)據(jù)結(jié)構(gòu) 72.2 程序整體結(jié)構(gòu) 112.3 模塊功能描述 113 詳細設計 124 測試 224.1 正確運行示例 224.2 錯誤運行示例 245 總結(jié)提高 251需求分析1.1程序功能介紹本程序模擬理發(fā)館一天的經(jīng)營狀況，理發(fā)館的環(huán)境如下：1理發(fā)館有N把理發(fā)椅，可同時為N位顧客進行理發(fā)(2<N<9)；2理發(fā)師按技術水平分為三個等級（一級最高，三

2、級最低），對應不同的服務收費。理發(fā)館一天的工作過程如下：1顧客進門時，需要選擇某級別的理發(fā)師，只要該級別的理發(fā)師有空椅，則可立即坐下理發(fā)，否則需排隊等候；2一旦該級別的理發(fā)師有顧客理發(fā)完離去，排在該位理發(fā)師隊列隊頭的顧客便可以開始理發(fā)。理發(fā)館老板統(tǒng)計每天不同級別理發(fā)師的營業(yè)時間、創(chuàng)收和每天理發(fā)館總創(chuàng)收，并寫入文本文件中，可作為理發(fā)師工資與獎金的發(fā)放依據(jù)。1.2程序數(shù)據(jù)要求1.2.1輸入數(shù)據(jù)（由文本文件輸入）：7 ：3061 12 13 24 35 26 30.6數(shù)據(jù)說明：第一行的09：30表示理發(fā)館將于九點半開門；第二行的6表示理發(fā)館有6張理發(fā)椅(此處可輸入39的任意值)；隨后的N行：表示第i

3、張椅子的理發(fā)師的級別（如：第1張理發(fā)椅是1級理發(fā)師，第2張理發(fā)椅是1級理發(fā)師）。最后一行的0.6代表折扣（可選）1.2.2隨機數(shù)據(jù)需求：每個顧客進門時將負責生成三個隨機數(shù)：1）理發(fā)時間durtime：進門顧客理發(fā)所需服務時間；2）間隔時間intertime：該顧客與下一位顧客到達的時間間隔；3）服務選項select：該顧客選擇理發(fā)師的級別。由隨機數(shù)函數(shù)產(chǎn)生。1.2.3輸出數(shù)據(jù)（輸出到文本文件中）： 本日賬目清單 =按理發(fā)師=理發(fā)師編號： 1 級別： 1 工作時長： 17 本日盈收： 17理發(fā)師編號： 2 級別： 1 工作時長： 29 本日盈收： 29理發(fā)師編號： 3 級別： 2 工作時長： 2

4、8 本日盈收： 14理發(fā)師編號： 4 級別： 3 工作時長： 73 本日盈收： 23理發(fā)師編號： 5 級別： 2 工作時長： 24 本日盈收： 12理發(fā)師編號： 6 級別： 3 工作時長： 27 本日盈收： 9理發(fā)師編號： 7 級別： 3 工作時長： 20 本日盈收： 6理發(fā)師編號： 8 級別： 1 工作時長： 30 本日盈收： 30=按級別=1級別理發(fā)師總工時： 76 總收入： 762級別理發(fā)師總工時： 52 總收入： 263級別理發(fā)師總工時： 120 總收入： 38=總匯=本日總創(chuàng)收： 1401.3開發(fā)與運行環(huán)境需求1.3.1開發(fā)環(huán)境： Visual studio 20101.3.2運行環(huán)

5、境： Win xp/Win 7/Win 81.4用戶界面設計1.4.1初始化界面（例：6個隊列）8隊列界面1.4.2顧客到達、理發(fā)及等待界面1.4.3顧客離開界面1.4.4 DOS/GUI同步演示程序過程1.4.5折扣選擇界面2數(shù)據(jù)結(jié)構(gòu)設計2.1 主要數(shù)據(jù)結(jié)構(gòu) 2.1.1事件類（Event）/事件類：包含事件發(fā)生時間，事件類型，和下一個事件（指針）三個數(shù)據(jù)成員class Event public: int occurtime; int event_type; Event* next_event; Event() Event(int occurtime, int event_type): occ

6、urtime(occurtime), event_type(event_type), next_event(NULL) Event() ;2.1.2事件表（EventList）/事件表類:數(shù)據(jù)成員 ：頭指針，兩個用于插入刪除事件結(jié)點的指針，和事件表長度class EventList public: Event *head, *ptr_before, *ptr_after; int length; /事件表長度 EventList() head = new Event(-1, -1); length=1; EventList() void OrderIn(Event* new_in); int

7、ListEmpty(); int Cmp(Event* new_in, Event* t1) ;2.1.3顧客類（Customer）class Customer public: int durtime; int select; Customer* next; Customer(): select(-1) Customer(int durtime, int select): durtime(durtime), select(select), next(NULL) Customer() ;2.1.4顧客隊列類（CustomerQueue）class CustomerQueue public: Cu

8、stomer *front, *rear; int select; int length; int worktime; int money; CustomerQueue(): front(NULL), rear(NULL), select(-1), length(0), money(0), worktime(0) CustomerQueue() void EnQueue(Customer* add); void DelQueue();2.1.5隨機函數(shù)類（Random）：class Random public: int durtime; int intertime; int select; R

9、andom() srand(int)time(NULL); Random() int Durtime(); int Intertime(); int Select();2.1.6文件操作類（FileOperation）：class FileOperation public: int input_time2;/接收輸入時間 小時、分鐘 char maohao;/接收中間的冒號 int number11;/用于接收理發(fā)師編號信息 int chairs;/理發(fā)師人數(shù) float discount;/折扣（可選） char zhekou; FileOperation(): discount(1.0)

10、FileOperation() void FileInput(ifstream &from_file, int &opentime, CustomerQueue cq, int &closetime); void FileOutput(ofstream &to_file, CustomerQueue cq, int& total_money);2.1.7繪圖類（barbergraph）：class barbergraph public: IMAGE background_img;/顧客去背景圖片 IMAGE baber_desk;/理發(fā)師桌子背景 IMA

11、GE my_clock;/時鐘背景 IMAGE door;/門 char now_time10;/時鐘信息存儲 char barber_info20;/理發(fā)師信息 char graphic_symbol15;/圖例信息 Customer* p;/獲取當前動作顧客 int chairs;/獲取理發(fā)師人數(shù) barbergraph() /讀取背景圖片集 loadimage(&background_img, _T("背景1.jpg"); loadimage(&baber_desk, _T("六張桌子.jpg"); loadimage(&m

12、y_clock, _T("時鐘.jpg"); loadimage(&door, _T("門.jpg"); void set_chairs (int chairs);/初始化理發(fā)師人數(shù) void CommonGraph(CustomerQueue cq, int opentime);/通用繪圖界面 void BarberGraph(CustomerQueue cq,int opentime);/無事件狀態(tài)界面 void ArriveBarberGraph(CustomerQueue cq, int arrival, int nowtime);/顧客

13、到來界面 void DepartBarberGraph(CustomerQueue cq, int departure, int nowtime);/顧客離開界面 barbergraph() ;2.1.8理發(fā)館類（Barbershop）：class BarberShop public: EventList ev;/事件表 CustomerQueue cq11;/六個顧客隊列110可選 int opentime;/開門時間 Event* cur_event;/當前事件 Event* new_event;/初始事件 Customer* new_customer;/新顧客 指針 int closet

14、ime;/TODO：目前為調(diào)試數(shù)據(jù)（22:00理想，未實現(xiàn)） int total_money;/理發(fā)館一天總收入 int chairs;/接收理發(fā)師人數(shù) BarberShop(): cur_event(NULL), new_customer(NULL), total_money(0) void OpenForDay(barbergraph &bg, int chairs);/開門初始化函數(shù) int Minimum(int select);/求同級別最短隊列函數(shù) void CustomerArrived(Random &ran, barbergraph &bg);/顧客到

15、來 void CustomerDeparture(barbergraph &bg);/顧客離開 void BarberSimulation(Random &ran, barbergraph &bg, int chairs);/事件驅(qū)動模型 BarberShop() ;2.2 程序整體結(jié)構(gòu)main2.2.1函數(shù)調(diào)用圖：FileoutputFileinputBarberSimulationListEmptyCustomerDepartureCustomerArrivedOpenForDayDelQueueEnQueueOrderInBarberGraphMinimumDep

16、artBarberGraphArriveBarberGraph2.3 模塊功能描述2.3.1 Event：作為EventList的結(jié)點元素，數(shù)據(jù)：事件類型、事件發(fā)生的時間2.3.2 EventList：事件表，為有序表。數(shù)據(jù)：頭指針，時間表長度length；操作：插入、刪除Event2.3.3 Customer：保存顧客信息。數(shù)據(jù)：durtime，select2.3.4 CustomerQueue：保存顧客隊列信息以及理發(fā)師信息。數(shù)據(jù)：select，length，worktime，money，頭尾指針；操作：入隊，出隊；2.3.5 Random：生成要求中的三個隨機數(shù)。2.3.6 FileOp

17、eration:從文件讀入數(shù)據(jù)，向文件輸出數(shù)據(jù)。2.3.7 BarberGraph：繪制圖形界面，包括初始化界面、顧客到來、顧客離開界面。2.3.8 barbershop：處理顧客到來，顧客離開，含事件驅(qū)動主程序。3詳細設計3.1.1 eventlist.cpp#include "eventlist.h"void EventList:OrderIn(Event* new_in)/插入事件表 if (1 = length) /如果長度為一，直接插入 head->next_event = new_in; length+; return; else /如果長度不為一，用兩指

18、針一前一后進行插入操作 ptr_before = head->next_event; ptr_after = head; while (ptr_before != NULL) if (-1 = Cmp(new_in,ptr_before) /如果插入事件在前 new_in->next_event = ptr_before; ptr_after->next_event = new_in; length+; return; /如果在此結(jié)點之后，后移一位繼續(xù)比較 ptr_after = ptr_before; ptr_before = ptr_before->next_eve

19、nt; ptr_after->next_event = new_in;/如果在最后，直接插到表尾 length+; int EventList:ListEmpty() if (length > 1) return 0; else return 1;3.1.2 customerqueue.cpp#include "customerqueue.h"void CustomerQueue:EnQueue(Customer* add) if (NULL = rear) /如果隊伍沒人，直接入隊 front = rear = add; else rear->next

20、= add; rear = rear->next; length+;void CustomerQueue:DelQueue() if (0 != length) Customer* p = front; front = front->next; if (rear = p) rear = NULL; delete p;/釋放隊頭結(jié)點空間 length-; 3.1.3 random.cpp#include "random.h"int Random:Durtime() return rand()%21+10;/隨機一個1030的數(shù)（持續(xù)時間）int Random:In

21、tertime() return rand()%6;/隨機一個0到5的數(shù)（間隔時間）int Random:Select() return rand()%3+1;/隨機一個13的數(shù)（級別）3.1.4 fileoperation.cpp#include "fileoperation.h"using namespace std;void FileOperation:FileInput(ifstream &from_file, int &opentime, CustomerQueue cq, int &closetime) from_file>>

22、input_time0>>maohao>>input_time1;/接收開門時間 opentime = 60*input_time0+input_time1;/將時間轉(zhuǎn)化為int from_file>>chairs;/接收理發(fā)師人數(shù) if (chairs>8|chairs<3) cout<<"input error, the number of chairs should between 3 and 8!"<<endl; _getch(); exit(0); for (int i = 1; i <

23、 chairs+1; i+) /初始化理發(fā)師信息 from_file>>numberi; from_file>>cqi.select; from_file>>input_time0>>maohao>>input_time1;/接收關門時間 closetime = 60*input_time0+input_time1;/關門時間轉(zhuǎn)化 cout<<"提供折扣？ y/n"<<endl; cin>>zhekou; if ('y' = zhekou) from_file&g

24、t;>discount; cout<<"本日折扣為 "<<discount <<" !"<<endl; else cout<<"本店今日不打折！"<<endl; from_file.close();/關閉讀文件void FileOperation:FileOutput(ofstream &to_file, CustomerQueue cq, int& total_money) int class_money4 = 0;/按理發(fā)師級別統(tǒng)計當天收

25、入 int class_worktime4 = 0;/按理發(fā)師級別統(tǒng)計當天工時 to_file<<" 本日賬目清單 "<<endl<<endl; to_file<<"=按理發(fā)師="<<endl<<endl; for (int i = 1; i < chairs+1; i+) to_file<<"理發(fā)師編號： "<<i<<" 級別： "<<cqi.select<<" 工作

26、時長： "<<cqi.worktime<<" 本日盈收： "<<cqi.money<<endl; to_file<<"=按級別="<<endl<<endl; for (int i = 1; i < chairs+1; i+) /按級別統(tǒng)計理發(fā)師工資和工時 if (1 = cqi.select) class_money1 += cqi.money; class_worktime1 += cqi.worktime; if (2 = cqi.select) cl

27、ass_money2 += cqi.money; class_worktime2 += cqi.worktime; if (3 = cqi.select) class_money3 += cqi.money; class_worktime3 += cqi.worktime; for (int i = 1; i < 4; i+) /按級別將理發(fā)師的工資和工時、總創(chuàng)收輸出到文件中 to_file<<i<<"級別理發(fā)師總工時： "<<class_worktimei<<" 總收入： "<<clas

28、s_moneyi<<endl; to_file<<"=總匯="<<endl<<endl; to_file<<"本日總創(chuàng)收： "<<total_money; to_file.close();/關閉寫文件3.1.5 barbergraph.cpp#include "barbergraph.h"void barbergraph:set_chairs (int chairs) this->chairs = chairs;/通用繪圖函數(shù)，負責繪制圖例，時鐘，理發(fā)師信息

29、（不包括隊列），主要用于刷新界面void barbergraph:CommonGraph(CustomerQueue cq, int opentime) /此處的opentime為nowtime BeginBatchDraw();/開始批量繪圖，避免閃爍 putimage(0, 0, &my_clock);/將圖片集分別插到對應區(qū)域 putimage(120, 100, &background_img); putimage(120, 0, &baber_desk); putimage(0, 470, &door); rectangle(0, 0, 120, 65

30、0);/左側(cè)框 /輸出時鐘信息 if (opentime-420)%60 < 10) /如果分鐘小于10，在顯示前面加0 sprintf_s(now_time, "%d:0%d", 7+(opentime-420)/60, (opentime-420)%60); else sprintf_s(now_time, "%d:%d", 7+(opentime-420)/60, (opentime-420)%60); setfont(50, 0, "黑體");/設置時鐘字體 setcolor(RED);/時鐘字體顏色 outtextxy

31、(10, 20, now_time); setfont(15, 0, "黑體");/恢復初始字體 setcolor(WHITE);/恢復初始字體顏色 /輸出圖例信息 for (int i = 0; i < 5; i+) if (0 = i) sprintf_s(graphic_symbol, " 圖例："); if (1 = i) sprintf_s(graphic_symbol, "顧客到達"); rectangle(20, 170+i*70, 90, 190+i*70); setfillstyle(BLUE,SOLID_FI

32、LL); floodfill(55, 175+i*70, WHITE); if (2 = i) sprintf_s(graphic_symbol, "顧客等待"); rectangle(20, 170+i*70, 90, 190+i*70); setfillstyle(RED,SOLID_FILL); floodfill(55, 175+i*70, WHITE); if (3 = i) sprintf_s(graphic_symbol, "顧客離開"); rectangle(20, 170+i*70, 90, 190+i*70); setfillstyl

33、e(GREEN,SOLID_FILL); floodfill(55, 175+i*70, WHITE); if (4 = i) sprintf_s(graphic_symbol, "顧客理發(fā)中"); rectangle(20, 170+i*70, 90, 190+i*70); setfillstyle(YELLOW,SOLID_FILL); floodfill(55, 175+i*70, WHITE); outtextxy(20, 150+i*70,graphic_symbol); /繪制理發(fā)師信息 for (int i = 0; i < chairs; i+) re

34、ctangle(120+i*150, 0, 120+(i+1)*150, 100); for (int i = 1; i < chairs+1; i+) sprintf_s(barber_info, "編號%d 級別：%d", i, cqi.select); outtextxy(155+150*(i-1), 40, barber_info); /靜態(tài)繪圖函數(shù)，用于初始化界面和顧客離開后暫停畫面void barbergraph:BarberGraph(CustomerQueue cq,int opentime) CommonGraph(cq, opentime); fo

35、r (int i = 1; i < chairs+1; i+) p = cqi.front; int j = 0; while (p != NULL) circle(195+150*(i-1), 230+50*j+, 20); if (1= j) setfillstyle(YELLOW,SOLID_FILL);/設置填充模式： 黃色，固實填充 floodfill(195+150*(i-1), 230+50*(j-1), WHITE);/坐標所在的封閉區(qū)域為填充對象，最后一個參數(shù)為邊框顏色 else setfillstyle(RED,SOLID_FILL);/設置填充模式： 紅色，固實填充

36、 floodfill(195+150*(i-1), 230+50*(j-1), WHITE);/坐標所在的封閉區(qū)域為填充對象，最后一個參數(shù)為邊框顏色 p = p->next; EndBatchDraw();/結(jié)束批量繪圖 _getch(); /cleardevice();/以當前背景色清屏（黑色）/繪制顧客到來瞬間界面void barbergraph:ArriveBarberGraph(CustomerQueue cq, int arrival, int nowtime) CommonGraph(cq, nowtime); for (int i = 1; i < chairs+1;

37、 i+) p = cqi.front; int j = 0; while (p != NULL) circle(195+150*(i-1), 230+50*j+, 20); if (1= j) setfillstyle(YELLOW,SOLID_FILL);/設置填充模式： 黃色，固實填充 floodfill(195+150*(i-1), 230+50*(j-1), WHITE);/坐標所在的封閉區(qū)域為填充對象，最后一個參數(shù)為邊框顏色 if (i = arrival && p->next = NULL) setfillstyle(BLUE,SOLID_FILL);/設置填

38、充模式： 藍色，固實填充 floodfill(195+150*(i-1), 230+50*(j-1), WHITE);/坐標所在的封閉區(qū)域為填充對象，最后一個參數(shù)為邊框顏色 else if (j > 1) setfillstyle(RED,SOLID_FILL);/設置填充模式： 紅色，固實填充 floodfill(195+150*(i-1), 230+50*(j-1), WHITE);/坐標所在的封閉區(qū)域為填充對象，最后一個參數(shù)為邊框顏色 p = p->next; EndBatchDraw(); _getch(); /cleardevice();/以當前背景色清屏（黑色）/繪制顧

39、客離開瞬間界面void barbergraph:DepartBarberGraph(CustomerQueue cq, int departure, int nowtime) CommonGraph(cq, nowtime); for (int i = 1; i < chairs+1; i+) /隊列動態(tài)變換部分 p = cqi.front; int j = 0; while (p != NULL) circle(195+150*(i-1), 230+50*j+, 20); if (1= j) setfillstyle(YELLOW,SOLID_FILL);/設置填充模式： 黃色，固實填

40、充 floodfill(195+150*(i-1), 230+50*(j-1), WHITE);/坐標所在的封閉區(qū)域為填充對象，最后一個參數(shù)為邊框顏色 if (i = departure && p = cqi.front) setfillstyle(GREEN,SOLID_FILL); floodfill(195+150*(i-1), 230+50*(j-1), WHITE); else if (j > 1) setfillstyle(RED,SOLID_FILL);/設置填充模式： 紅色，固實填充 floodfill(195+150*(i-1), 230+50*(j-1

41、), WHITE);/坐標所在的封閉區(qū)域為填充對象，最后一個參數(shù)為邊框顏色 p = p->next; EndBatchDraw(); _getch(); /cleardevice();/以當前背景色清屏（黑色）3.1.6 barbershop.cpp#include "barbershop.h"using namespace std;void BarberShop:OpenForDay(barbergraph &bg, int chairs) this->chairs = chairs;/從輸入函數(shù)中得到理發(fā)師人數(shù) bg.set_chairs(chair

42、s);/將理發(fā)師人數(shù)傳到繪圖對象中 initgraph(1024+(chairs-6)*150, 650, 1);/初始化界面大?。ǜ鶕?jù)理發(fā)師人數(shù)來初始化大小） setbkmode(TRANSPARENT);/設置文字或圖片輸出背景為透明 setfont(15, 0, "黑體");/初始化字體 setcolor(WHITE);/初始化字體顏色 bg.BarberGraph(cq, opentime);/初始化界面信息 Event* new_event = new Event(opentime, 0);/創(chuàng)建第一個事件 ev.OrderIn(new_event);/插入事件表

43、/OpenForDayint BarberShop:Minimum(int select) int min_cq = 1000;/最短隊列初始值 int min_length = 1000;/假定初始最短長度為無窮 for (int i = 1; i <= chairs; i+) /尋找符合select的最短隊列 if (cqi.select = select && cqi.length < min_length) min_length = cqi.length; min_cq = i; return min_cq;/返回最短隊列號void BarberShop:C

44、ustomerArrived(Random &ran, barbergraph &bg, float discount) /處理客戶到達事件 int select = ran.Select();/隨機生成本顧客的理發(fā)師級別選擇 int durtime = ran.Durtime();/隨機生成本顧客的理發(fā)時長 int intertime = ran.Intertime();/隨機生成下一個顧客的到來時間間隔 int money = durtime/select*discount;/本顧客的消費額（收費公式） int min_cq; /記錄最短隊列信息 new_customer

45、= new Customer(durtime, select);/生成本顧客實體 total_money += money;/計入總收入 min_cq = Minimum(select);/求最短隊列 cout<<"min_cq:"<<min_cq<<" " cout<<"selece:"<<select<<" "<<"durtime:"<<durtime<<" "&l

46、t;<"intertime:"<<intertime<<" " cout<<"("<<7+(cur_event->occurtime-420)/60<<":" <<(cur_event->occurtime-420)%60<<","<<cur_event->event_type<<")"<<endl;/時間轉(zhuǎn)換公式 cqmin_cq.

47、money += money; /計入min_cq隊列理發(fā)師總收入 cqmin_cq.worktime += durtime;/計入min_cq隊列理發(fā)師工作時間 cqmin_cq.EnQueue(new_customer);/入隊 bg.ArriveBarberGraph(cq, min_cq, cur_event->occurtime);/在圖形界面上顯示到來顧客 int t = cur_event->occurtime + intertime;/下一顧客的到來時間 if (t < closetime) /下一顧客到來未關門 new_event = new Event(t

48、, 0); ev.OrderIn(new_event);/生成下一顧客到達事件插入事件表 if (1 = cqmin_cq.length) /如果新來的顧客在隊頭 new_event = new Event(cur_event->occurtime+durtime, min_cq); ev.OrderIn(new_event);/生成本顧客的離開事件插入事件表 /CustomerArrived/客戶離開事件void BarberShop:CustomerDeparture(barbergraph &bg) /注意：隊列中超過兩個人時下個人的離開事件從前一個人離開時開始計時。 in

49、t i = cur_event->event_type; /記錄要刪除的隊列編號 cout<<"dep_cq:"<<i<<" " cout<<"("<<7+(cur_event->occurtime-420)/60<<":" <<(cur_event->occurtime-420)%60<<","<<cur_event->event_type<<&quo

50、t;)"<<endl; bg.DepartBarberGraph(cq, i, cur_event->occurtime);/將離開的顧客用圖形表示出來 cqi.DelQueue(); /刪除第i隊的排頭客戶 bg.BarberGraph(cq, cur_event->occurtime);/繪制顧客離開后的畫面 if (0 != cqi.length) /設定第i隊列的隊頭離開事件插入事件表 new_event = new Event(cur_event->occurtime + cqi.front->durtime, i); ev.OrderIn(new_event); /CustomerDeparturevoid BarberShop:BarberSimulation(Random &ran, barbergraph &bg, int chairs, float discount) OpenForDay(bg, chairs);/開門初始化 while (!ev.ListEmpty() /事件驅(qū)動主體，只要事件表不為空則一直執(zhí)行第一個事件 cur_event = ev.head->next_event;/獲取當前事件(表中第二個結(jié)點) if (0 = cur_event->ev