數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)網(wǎng)上拍賣系統(tǒng)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)報(bào)告專 業(yè) 軟件工程 班 級(jí) 軟件赴日1101學(xué) 號(hào) 20112271姓 名賈志遠(yuǎn) 日 期 2013年9月17日東北大學(xué)軟件學(xué)院第一章 需求分析1、 實(shí)驗(yàn)要求：設(shè)計(jì)一個(gè)網(wǎng)上拍賣系統(tǒng)，有些類的頭文件和主函數(shù)已經(jīng)給出，通過頭文件中定義的部分和實(shí)驗(yàn)中的提示來編寫類的代碼，從而完成拍賣系統(tǒng)的全部功能。實(shí)驗(yàn)共分五個(gè)部分，由淺入深逐漸完善，而且只有完成了前一部分實(shí)驗(yàn)，才能繼續(xù)進(jìn)行下一部分的實(shí)驗(yàn)內(nèi)容。2、 問題分析：根據(jù)實(shí)驗(yàn)要求，可知此網(wǎng)上拍賣系統(tǒng)大致包含以下幾個(gè)部分：注冊(cè)、登陸、增加廣告、添加子目錄、顯示商品列表、查找廣告、廣告排序、客戶競(jìng)標(biāo)。由實(shí)驗(yàn)已給的部分代碼來看，應(yīng)該有以下幾個(gè)部

2、分：廣告（Advertisement）、廣告集合（Listing）、目錄（Category）、目錄集合（Categories）、標(biāo)價(jià)（bid）、客戶（Client）、客戶組（Group），系統(tǒng)應(yīng)圍繞這些部分的關(guān)系，編寫各自的函數(shù)，從而完成拍賣系統(tǒng)的功能。3、 實(shí)驗(yàn)?zāi)康模和ㄟ^實(shí)驗(yàn)進(jìn)一步了解線性表、堆棧、隊(duì)列、串、數(shù)組、廣義表、樹、圖以及一些排序算法等數(shù)據(jù)結(jié)構(gòu)內(nèi)容。培養(yǎng)根據(jù)用戶的要求及系統(tǒng)提供的數(shù)據(jù)，設(shè)計(jì)或選擇合適的數(shù)據(jù)結(jié)構(gòu)并能編寫正確的算法解決實(shí)際問題的能力第二章 系統(tǒng)設(shè)計(jì)1、總體設(shè)計(jì)a.總體思路：先寫好系統(tǒng)的基本骨架：Date、Client 、Advertisement這三個(gè)類，完成系統(tǒng)的基本

3、功能，然后根據(jù)系統(tǒng)的功能需求編寫相應(yīng)的類完成功能拓展。 具體的類間關(guān)系為：Categories儲(chǔ)存多個(gè)Category，Category通過Listing類儲(chǔ)存這個(gè)目錄下的Advertisement，Listing是Advertisement的集合，而Advertisement信息中包含多個(gè)Client對(duì)自己的競(jìng)標(biāo)（bid），Client又可以對(duì)多個(gè)Advertisement進(jìn)行競(jìng)標(biāo)并發(fā)布Advertisement，Group是Client的集合，所以包含多個(gè)Client。其他的是過程類，由main調(diào)用processrequest類，再由processrequest調(diào)用相應(yīng)的buildbidp

4、age、buildpage、bidhistory類將結(jié)果顯示在頁面中。 體現(xiàn)在UML類圖中如圖所示： b.基本的數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)除了上述分析中所定義的類，還包括stl中的優(yōu)先權(quán)隊(duì)列和Vector集合。c 各類主要操作定義如下：u Class Date： operator=(const Date &rhs) operator(istream&, Date&) operator(istream &stream, Advertisement &a) virtual vector getTopDutchBids (void) const;u Class Client ： Client (const

5、Client &a) operator(istream &stream, Client &c) u Class Listing： add(Advertisement*ptr) operator(const int& number) virtual Listing sort(string field); virtual Listing filter(string keyword);u Class Group： Client *operator(const string& email)u Class Category： virtual void addSubCategory(Category*);

6、 virtual void addItem(int); virtual void findOfferings (Listing:iterator start, Listing:iterator finish, Listing &matches); virtual void findOfferingsRecursive (Listing:iterator start, Listing:iterator finish, Listing &matches); virtual bool operator=(const Category& rhs);u Class Bid： virtual boolop

7、erator (const Bid &rhs) const; virtual bool operator= (const Bid &rhs) const;u Class bidhistory： VoiddisplayBidHistory(ostringstream&oss,Advertisement* ad);2、程序設(shè)計(jì)系統(tǒng)的操作對(duì)應(yīng)系統(tǒng)的功能，共有七種，分別是：客戶注冊(cè)、登陸、添加廣告、添加子目錄、按關(guān)鍵字查找廣告、對(duì)廣告排序、競(jìng)標(biāo)。用戶在使用系統(tǒng)之前需進(jìn)行注冊(cè)，然后登陸系統(tǒng)后可以按提示填寫廣告信息發(fā)布廣告，或是對(duì)已有的廣告點(diǎn)擊bid按鈕進(jìn)行競(jìng)標(biāo)。用戶可創(chuàng)建目錄到top level或其子目

8、錄下，也可通過關(guān)鍵字查找廣告或按廣告的屬性對(duì)廣告進(jìn)行排序查看。具體操作過程如下：注冊(cè)：在“Create Account”那一欄下填寫用戶名，email地址和密碼然后點(diǎn)擊“create”按鈕即可，注意兩次輸入的密碼必須匹配，否則會(huì)提示錯(cuò)誤。登陸：輸入自己注冊(cè)的email地址和密碼，如果正確點(diǎn)擊login按鈕后即可添加廣告：用戶進(jìn)入登陸界面后，在Post and Ad一欄按提示填寫廣告的標(biāo)題、數(shù)量等信息后，點(diǎn)擊add按鈕后便可將廣告發(fā)布到左側(cè)的廣告列表中。添加子目錄：用戶需在添加廣告一欄的下面，選擇母目錄，然后在新目錄文本框中輸入新目錄的名字，便可在選擇的目錄下創(chuàng)建新的目錄。例如想要?jiǎng)?chuàng)建TopLe

9、vel/New這個(gè)目錄，只要選擇TopLevel然后在底下的新目錄一欄輸入New然后點(diǎn)擊”Add subcategory”即可。查找廣告：在find按鈕后的文本框中，輸入想要查找的關(guān)鍵字，然后點(diǎn)擊“find”按鈕，即可篩選出題目或描述中包含此關(guān)鍵字的廣告。也可點(diǎn)擊“top only”按鈕顯示某一層目錄的廣告，以及點(diǎn)擊Recursive按鈕顯示這層目錄及其子目錄所有的廣告列表。廣告排序：在sort按鈕旁的下拉菜單中，選擇一種屬性，然后點(diǎn)擊sort按鈕后，廣告會(huì)按從小到大的順序?qū)V告進(jìn)行排序。競(jìng)標(biāo)：用戶選擇要競(jìng)標(biāo)的廣告，點(diǎn)擊“bid”按鈕進(jìn)入競(jìng)標(biāo)頁面，然后根據(jù)提示，輸入競(jìng)標(biāo)的數(shù)量和金額，然后點(diǎn)擊s

10、ubmit按鈕，如果競(jìng)標(biāo)成功，即可在此廣告的bid列表中找到自己的競(jìng)標(biāo)。第三章 系統(tǒng)實(shí)現(xiàn)與調(diào)試重要函數(shù)算法說明：a. Date類重載”操作符，比較兩個(gè)日期大?。核惴ǎ簩?duì)date的每個(gè)屬性分三種情況判斷，用一個(gè)flag變量標(biāo)記，先判斷年是否滿足小于關(guān)系，如果是，則為true，否則在年相等的情況下再判斷月，依次類推，如果年本身滿足大于關(guān)系false，最后返回flase即可。關(guān)鍵代碼如下：bool Date:operator (const Date &rhs)if(yearrhs.getYear()return true;else if(year=rhs.getYear()if(monthrhs.g

11、etMonth()return true;else if(month=rhs.getMonth()if(dayrhs.getDay()return true;else if(day=rhs.getDay()if(hourrhs.getHour()return true;else if(hour=rhs.getHour()if(minuterhs.getMinute()return true;else if(minute=rhs.getMinute()if(secondrhs.getSecond()return true;return false;復(fù)雜度：O(1)b. Group類重載，返回有特

12、定email地址的用戶指針：算法：遍歷objects集合，并判斷集合中元素的email地址是否和傳入的參數(shù)相同，如果相同返回此Client指針，否則返回null。關(guān)鍵代碼如下：Client* Group:operator(const string& email)for(int i=0;igetEmail()=email)return objects.at(i);return 0;復(fù)雜度：O(N)c. Advertisement類重載,從輸入中讀入信息給Advertisement屬性賦值：算法：用getline函數(shù)和stream為advertisement屬性賦值，為了保證能將空格和回車全部保留

13、，用一個(gè)while循環(huán)一行讀body并用“”標(biāo)簽將結(jié)果進(jìn)行連接，直到讀到空行為止。關(guān)鍵代碼如下：istream &operate(istream &stream, Advertisement &a)string str;Date dat;int qua;getline(stream,str);a.setTitle(str);streamstr;a.setEmail(str);streamqua;a.setQuantity(qua);streamdat;a.setStart(dat);streamdat;a.setClose(dat);streamstr;a.setBody(str);retur

14、n stream;復(fù)雜度：O(N)d. Category類的findOfferingsRecursive函數(shù)，用遞歸遍歷子目錄內(nèi)容：算法：遞歸調(diào)用findOfferingsRecursive和findOfferings，先用findOfferings找到本層目錄中滿足條件的廣告加入到matches中， 然后再遍歷子目錄集合，調(diào)用自身函數(shù)將子目錄中滿足條件的廣告加入到matches中。關(guān)鍵代碼如下：void Category:findOfferingsRecursive (Listing:iterator start, Listing:iterator finish, Listing &matc

15、hes)for(Listing:iterator is=start;is!=finish;is+)if(*is)-getNumber()=number)matches.add(*is);for(vector:iteratorss=sub_categories.begin();ss!=sub_categories.end();ss+)(*ss)-findOfferingsRecursive(start,finish,matches);復(fù)雜度：O(N)e. Listing類的sort函數(shù)，通過使用stl的sort函數(shù)實(shí)現(xiàn)對(duì)廣告的排序功能。算法：定義四個(gè)內(nèi)部函數(shù)，再定義sort函數(shù)的排序邏輯，然后在

16、sort函數(shù)中，以函數(shù)指針作為參數(shù)傳給sort函數(shù)。關(guān)鍵代碼如下：bool lessQuantity(Advertisement* a,Advertisement* b) return a-getQuantity() getQuantity();bool lessStart(Advertisement* a,Advertisement* b) return a-getStart() getStart();bool lessClose(Advertisement* a,Advertisement* b) return a-getClose() getClose();bool lessEmail(

17、Advertisement* a,Advertisement* b) return a-getEmail() getEmail();Listing Listing:sort(string field) Listing is(*this); if(field=email) std:sort( is.begin() , is.end() , lessEmail); if(field=Quantity) std:sort( is.begin() , is.end() , lessQuantity); if(field=Start) std:sort( is.begin() , is.end() ,

18、lessStart); if(field=Close) std:sort( is.begin() , is.end() , lessClose); return is; 復(fù)雜度：O(N)f. Listing類的filter函數(shù)，通過使用stl的find函數(shù)實(shí)現(xiàn)對(duì)廣告的查找功能。算法：總體思想是在所有的廣告集合中找到包含輸入關(guān)鍵字的廣告，然后將之加入，從而顯示滿足條件的廣告，最后返回這個(gè)列表。關(guān)鍵代碼如下：Listing Listing:filter(string keyword) Listing is;for(int i=0;igetTitle().find(keyword);string:s

19、ize_type i2 = objects.at(i)-getBody().find(keyword);if ( i1 != string:npos| i2 != string:npos)is.add(objects.at(i);return is; 復(fù)雜度：O(N)g. Advertisement類的getTopDutchBids函數(shù)，用以獲得競(jìng)標(biāo)成功的bid集合。算法：競(jìng)標(biāo)成功的bids是指按價(jià)位由高到低排，累積競(jìng)標(biāo)的數(shù)量和大于等于廣告商品本省的數(shù)量時(shí)停止。因此，需用一個(gè)result變量用以統(tǒng)計(jì)bids的競(jìng)標(biāo)數(shù)量和，遍歷廣告本身已經(jīng)排好序的bids集合，依次將bids內(nèi)的bid出棧，并將出

20、棧的bid數(shù)量加到result中，知道result的值大于等于廣告的quantity為止，這時(shí)，一般情況會(huì)多加一個(gè)bid，也就是說多加的這個(gè)bid內(nèi)的quantity值，加上前面的bid的quantity值會(huì)大于廣告本身的quantity，也就是說，這個(gè)bid并不會(huì)得到它所要求的廣告的數(shù)量，而是廣告的quantity減去前面bid所有quantity剩下的值。關(guān)鍵代碼如下：vector Advertisement:getTopDutchBids (void) constvector vb;priority_queue bid(bids);int all=number;while( !bid.empty() & all0)vb.push_back(bid.top();all-=bid.top().getQuantity();bid.pop();return vb;復(fù)雜度：O(N)第4章 系統(tǒng)測(cè)試測(cè)試方法：利用Apache運(yùn)行程序，設(shè)置幾組測(cè)試用例，分別考慮到一般情況和特殊情況，觀察測(cè)試結(jié)果的正確性。測(cè)試用例（應(yīng)該給出幾組具有不同特征的數(shù)據(jù)進(jìn)行測(cè)試）：Client名稱