數(shù)據(jù)結構課程設計報告模板插隊買票

數(shù)據(jù)結構課程設計報告(2011--2012年度第1學期)插隊買票專業(yè)網(wǎng)絡技術學生姓名班級學號指導教師完成日期目錄1概述 11.1課程設計目的 11.2課程設計內容 12系統(tǒng)需求分析 12.1系統(tǒng)目標 12.2主體功能 12.3開發(fā)環(huán)境 13系統(tǒng)概要設計 13.1系統(tǒng)的功能模塊劃分 13.2系統(tǒng)流程圖 14系統(tǒng)詳細設計 15測試 15.1測試方案 15.2測試結果 16小結 1參考文獻 2附錄 3附錄1源程序清單 3插隊買票1概述1.1課程設計目的數(shù)據(jù)結構課程設計是為數(shù)據(jù)結構課程獨立開設的實踐性教學環(huán)節(jié)。數(shù)據(jù)結構課程設計對于鞏固數(shù)據(jù)結構知識，加強學生的實際動手能力和提高學生綜合素質是十分必要的。課程設計的目的：1．要求學生達到熟練掌握C語言的基本知識和技能。2．了解并掌握數(shù)據(jù)結構與算法的設計方法，具備初步的獨立分析和設計能力。3．提高程序設計和調試能力。學生通過上機實習，驗證自己設計的算法的正確性。學會有效利用基本調試方法，迅速找出程序代碼中的錯誤并且修改。4．培養(yǎng)算法分析能力。分析所設計算法的時間復雜度和空間復雜度，進一步提高程序設計水平。5．初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能。1.2課程設計內容本課程設計的任務是寫一個程序模擬這種情況。每個隊伍都允許插隊。如果你在排隊，有一個以上的朋友要求插隊，則你可以安排他們的次序。每次一個人入隊，并且如果這個入隊的人發(fā)現(xiàn)隊伍中有自己的朋友，則可以插入到這個朋友的后面；當隊伍中的朋友不止一個的時候，這個人會排在最后一個朋友的后面；如果隊伍中沒有朋友，則他只能夠排在這個隊伍的最后面。每一個入隊的人都先進行上述的判斷。當隊伍前面的人買到車票之后，依次出隊。2系統(tǒng)需求分析2.1系統(tǒng)目標數(shù)據(jù)結構課程設計用C/C++編程實現(xiàn)。1．問題描述與分析：根據(jù)設計題目的要求，充分地分析和理解問題，明確問題要求做什么？限制條件是什么？2．數(shù)據(jù)結構設計：為實現(xiàn)每個功能選擇的邏輯結構和存儲結構，分析原因及合理性。3．軟件結構設計：設計軟件模塊之間的結構。4．算法設計：算法的設計及算法分析。每個部分的算法設計說明，可以用流程圖描述算法。5．程序編碼：把詳細設計的結果進一步求精為程序設計語言程序。源程序要按照軟件工程的規(guī)則來編寫，要求結構清晰，重要功能部分要加上清晰的程序注釋。6．調試分析：掌握調試工具的各種功能，設計測試數(shù)據(jù)，測試輸出的結果。并進行算法的時間復雜度和空間復雜度的分析。7．總結：課程設計過程的收獲，遇到問題以及解決問題的思路和方法，程序調試能力的思考，對數(shù)據(jù)結構這門課程的認識及思考等。8．編寫課程設計報告。2.2主體功能程序從“input.txt”文件讀入測試用例，一個文件可包含多個測試用例。每個用例的第一行是朋友組的數(shù)目n(1<=n<=1000)。對于一個朋友組以朋友的數(shù)目j（1<=j<=1000）開始，由朋友的個數(shù)以及他們的名字組成，一個空格后接該組朋友的名字，以空格分開，并且每個人的名字都不同。每個名字不超過四個字母，由{A,B,…,Z,a,b,…,z}組成。一個朋友組最多有1000個人，每個人只屬于一個朋友組。n=0時，測試數(shù)據(jù)結束。下面是一些具體命令：·ENQUEUE——X入隊；·DEQUEUE——排隊頭的人買票，離開隊伍，即出隊；·STOP——一個測試用例結束。測試結果輸出到“output.txt”文件中。每個測試用例第一行輸出“Scenario#k”，k是測試用例的序號（從1開始）。對每一個出隊命令，輸出剛買票離開隊伍的人名。兩個測試用例之間隔一空行，最后一個用例結束不輸出空行。2.3開發(fā)環(huán)境MicrosoftVisualC++6.03系統(tǒng)概要設計3.1系統(tǒng)的功能模塊劃分@@@@@@@@@@3.2系統(tǒng)流程圖開始開始初始化窗口隊列，讀入測試用例用戶選擇當前測試用例結束是否讀到文件尾結束入隊出隊4系統(tǒng)詳細設計本題目主要解決兩個問題：一是怎么存放和查找大量數(shù)據(jù)（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。用散列表來存放和查找數(shù)據(jù)。由于最多有1000個朋友組，每組最多有1000人，使用平方測探法解決沖突，則表的大小是2*（1000*1000），所以選擇TableSize=2000003(2000003是大于2000000的最小素數(shù))。同一個組內的都是朋友，所以每個人除了記錄他的名字name，還要記錄他屬于哪個組group，另外用info來表示該但愿是否被占用，數(shù)據(jù)結構如圖4.1所示。散列函數(shù)是根據(jù)Honer法則計算一個以64為階的多項式，如圖4.2所示。沖突解決方法采用平方探測法，如圖4.3所示。#defineTabSize2000003typedefstructhashtab*PtrToHash;structhashtab{charname[5];intgroup;charinfo;/*用來表示該單元是否被占用*/};圖4.1數(shù)據(jù)結構：散列表intHash(char*key,intTableSize){intHashVal=0;while(key!=NULL)HashVal=(HashVal<<6)+*key;ReturnHashVal%TableSize;} 圖4.2散列函數(shù)longintFind(PtrToHashhash,char*c){key=c;CurrentPos=Hash(key,TableSize);/*計算散列值*/CollisionNum=0;while((單元被占用)and(單元內的名字與查找的名字不同)){/*使用平方探測法*/CurrentPos+=2*(++CollisionNum)-1;if(CurrentPos>=TabSize)CurrentPos-=TabSize;}returnCurrentPos;}圖4.3用平方探測法解決沖突第二個問題是關于怎么操作“ENQUEUE”和“DEQUEUE”命令。這可以用隊列來模擬。由于有插隊現(xiàn)象的存在，不能單純地用一個數(shù)組來表示隊列，因為這樣的話，插入一個朋友，則他后面的人都要往后移一個單位，刪除一個人，則他后面的人都要前移一個，會降低效率。所以，采用一個Index標記來表示當前元素的后繼元素，最后一個單元的后繼元素是第0個，形成環(huán)，數(shù)據(jù)結構如圖4.4所示。不用鏈表是因為鏈表存放指針也需要空間，并且鏈表插入、刪除的效率沒有數(shù)組高。TypedefstructQue*PtrToQue;StructQue{longintHashVal;longintIndex;};圖4.4數(shù)據(jù)結構：隊列輸入ENQUEUE命令，如果隊伍里有朋友，則排在朋友后面；如果沒有朋友，則排在對尾。入隊時，用一個數(shù)組記錄每個朋友組的最后一位，以便下一個朋友到來時排到他后面，這個數(shù)組被稱為“插隊數(shù)組”。輸入DEQUEUE命令，則根據(jù)“先進先出”，按照各個元素和它后繼元素的先后順序，每次刪除隊列中的第一個。程序結構如圖4.5所示。While(讀測試文件){if(輸入“ENQUEUE”){讀入名字；插入散列表；插入隊列；}elseif(輸入“DEQUEUE”){刪除隊列第一個名字；將該名字輸出到文件；}elsestop;}圖4.5入隊、出對操作5測試5.1測試方案1.按輸入要求輸入正常測試數(shù)據(jù)，測試程序是否能正確解決問題，得到正確答案。2.應注意邊界測試。例如，將n、j分別取為1的用例和n胃1000的用例。n、j比較大時需寫程序生成測試用例。3.不按輸入要求輸入數(shù)據(jù)，測試程序能否對輸入內容進行數(shù)據(jù)合法性檢測并進行相應的異常處理。例如，將n或j取為小于1或大于1000的數(shù)，名字超過4個字母等情況下的測試用例。5.2測試結果正確顯示結果：舉例說明一種異常結果：6小結通過幾天的折騰，總算把課程設計給完成了，這是一個堅苦而又漫長的過程?？粗鴦趧映晒?，很欣慰！剛開始，可以說是沒有頭緒，于是就去圖書館找資料，找到了一些關于程序方面的，可是這點小進展遠遠不夠，這只是一個小小的開始。下一步是上網(wǎng)查，找到了些與我題目相似的，那時我很高興，可是那還不是我要的，于是又上網(wǎng)查到了些有關的函數(shù)等等，終于在我的努力下，完成了這個程序。雖然對著電腦做程序，有點累有點熱，可是當看到勞動成果時，真是別有一番滋味在心頭??！世上無難事，只怕有心人，的確如此。做完這個課程設計，我的自信一下子提高了；盡管對于有些人這種程序會很簡單，可對我說，已經(jīng)很不容易了。這次體驗為以后的學習計算機的我增強了信心。享受勞動成果的滋味實在很美妙。參考文獻[1]范策，周世平，胡嘵琨.《算法與數(shù)據(jù)結構（C語言版）》[M].北京：機械工業(yè)出版社，2004[2]嚴蔚敏.《數(shù)據(jù)結構（C語言版）》.北京：清華大學出版社，2004[3]許卓群，楊冬青，唐世渭，張銘.《數(shù)據(jù)結構與算法》.北京：高等教育出版社，2004[4]徐孝凱.《數(shù)據(jù)結構實用教程（第二版）》.北京：清華大學出版社，2006附錄附錄1源程序清單#include<stdio.h>#include<malloc.h>#include<string.h>#defineTabSize2000003/*散列表大小TabSize是大于表最大空間的素數(shù)*/#defineMax1000001/*隊列空間最大值*/structhashtab;typedefstructhashtab*PtrToHash;structhashtab/*散列表數(shù)據(jù)結構*/{charname[5];/*名字*/intgroup;/*屬于哪個朋友組*/charinfo;/*標志位，該單元是否被占用*/};structQue;typedefstructQue*PtrToQue;structQue/*隊列數(shù)據(jù)結構*/{longintHashVal;/*散列值*/longintIndex;/*在中的隊列序號*/};inthashedx=0;/*標記元素是否已經(jīng)在散列表里*/longintFind(PtrToHashhash,char*c)/*查找在散列表中的位置*/{char*key;longintCurrentPos,CollisionNum;key=c;for(CurrentPos=0;*key;++key)/*散列函數(shù)，計算散列值*/CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize;/*散列值*/CollisionNum=0;/*如果當前單元被占用：單元內的元素與當前操作的名字不同，使用平方探測法解決沖突；與當前操作的名字相同，則直接返回在散列中的位置*/while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c))){/*平方探測法*/CurrentPos+=2*(++CollisionNum)-1;if(CurrentPos>=TabSize)CurrentPos-=TabSize;}if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0))/*元素已經(jīng)在散列表里*/hashedx=1;else/*元素不在散列表里*/hashedx=0;returnCurrentPos;/*返回在散列表中的位置*/}intmain(){longintFind(PtrToHashhash,char*c);/*查找在散列表中的位置*/PtrToHashhash;/*散列表*/PtrToQuequeue;/*隊列*/int*grouppos;/*記錄每個朋友組的最后一位，即插隊數(shù)組*/intn;/*測試用例數(shù)目*/intnum;/*當前測試用例序號*/longinti,ii,j,key,temp;longinthead,last;/*隊列的頭和尾*/charc[8],tempc[8];/*名字*/FILE*fpin,*fpout;/*輸入、輸出文件指針*/if(!(fpin=fopen("input.txt","r")))/*打開測試文件*/{printf("fopenerror!");/*文件打開錯誤*/return-1;}if(!(fpout=fopen("output.txt","w")))/*打開輸出文件*/{printf("fopenerror!");return-1;}hash=(PtrToHash)malloc(sizeof(structhashtab)*TabSize);/*為散列表申請空間*/queue=(PtrToQue)malloc(sizeof(structQue)*Max);/*為隊列申請空間*/grouppos=(int*)malloc(sizeof(int)*1000);/*申請空間記錄每個朋友組的最后一位*/for(i=0,j=1;i<Max;++i,++j)/*初始化隊列，queue[i]的后繼單元是queue[i＋1]*/queue[i].Index=j;queue[i-1].Index=0;/*最后一個單元的后繼單元是第0個，形成環(huán)*/num=0;for(fscanf(fpin,"%d",&n);n;fscanf(fpin,"%d",&n))/*輸入當前測試用例的朋友組數(shù)*/{if(n<1||n>1000)/*處理異常輸入n*/ {fprintf(fpout,"nisoutofrange\n");return-1; }num++;if(num!=1)/*兩個測試用例間輸入一空行*/fprintf(fpout,"\n");for(i=0;i<TabSize;)hash[i++].info=0;/*初始化散列表，標記位置0*/for(i=0;i<n;++i)/*對每一組朋友*/ {fscanf(fpin,"%d",&j);/*當前組里的人數(shù)*/if(j<1||j>1000)/*處理異常輸入j*/ {fprintf(fpout,"jisoutofrange\n");return-1; }for(;j;--j) {fscanf(fpin,"%s",c);/*輸入名字*/for(ii=0;ii<sizeof(tempc);ii++)/*tempc清空，處理異常輸入名字*/tempc[ii]='\0';strcpy(tempc,c); ii=0;while(tempc[ii]!='\0')/*是否由四個以內字母組成*/ {if(tempc[ii]<'A'||('Z'<tempc[ii]&&tempc[ii]<'a')||tempc[ii]>'z'||ii>4) {fprintf(fpout,"Group%d:Nonstandardname\n",i);return-1; } ii++; }key=Find(hash,c);/*找到在散列表中的位置*/if(hashedx==1)/*重名*/ {fprintf(fpout,"repeatedname%s\n",c);return-1; }strcpy(hash[key].name,c);/*插入散列表*/hash[key].info=1;/*標記置1，該單元被占用*/hash[key].group=i;/*記錄他屬于哪個組*/ } }for(i=0;i<1000;)grouppos[i++]=0;/*初始化插隊數(shù)組*/head=0;/*初始化隊列頭、尾標記*/last=0;fprintf(fpout,"Scenario#%d\n",num);/*輸出當前用例序號到文件*/for(fscanf(fpin,"%s",c);;fscanf(fpin,"%s",c))/*輸入命令*/ {if(*c=='E')/*入隊命令*/ {fscanf(fpin,"%s",c);/*輸入名字*/key=Find(hash,c);/*查找在散列表中的位置*/if(hashedx==0)/*散列表里沒這個人*/ {fprintf(fpout,"no%s\n",c);return-1; }temp=queue[0].Index;/*隊列第0個位置記錄隊尾的后繼單元*/queue[0].Index=queue[temp].Index;/*在隊列中申請一個新單元，隊尾標記后移一個位置*/queue[temp].HashVal=key;/*入隊*/if(!head)/*如果是隊列里的第一個元素*/last=head=temp;/*隊頭、隊尾標記指向第一個元素*/if(!grouppos[hash[key].group])/*如果隊列里沒朋友*/ {queue[temp].Index=0;/*隊尾指向對頭，形成環(huán)*/queue[last].Index=temp;/*前一次隊尾的后繼元素是當前元素*/last=temp;/*隊尾標記指向當前元素*/grouppos[hash[key].group]=temp;/*插隊數(shù)組記錄該朋友組里已入隊的最后一位*/ }else/*如果隊列中已經(jīng)有他的朋友*/ {queue[temp].Index=queue[grouppos[hash[key].group]].Index;/*插隊到朋友的后面*/queue[grouppos[hash[key].group]].Index=temp;/*插隊到朋友后面一位的前面*/grouppos[hash[key]