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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計總結(jié)報告 專 業(yè) 班 級 學(xué) 號 姓 名 日 期 東北大學(xué)軟件學(xué)院第一章 需求分析隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展和人們購物意識的不斷革新，網(wǎng)上購物成為一種新型的購物方式，正逐漸被人們所接受和認(rèn)可，而網(wǎng)上購物的方式之一的網(wǎng)上拍賣形式給人們的購物帶來另一種全新的體驗，人們可以通過網(wǎng)站發(fā)出自己想要拍賣的物品的信息，也可以通過購買自己想要的物品，即具有一般的購物網(wǎng)站的成本低廉，方式靈活，運行快捷的特點，更具有自由競爭和公平合理的特性，如現(xiàn)在流行的拍拍網(wǎng)，淘寶網(wǎng)等都是很好的成功的實例。所以網(wǎng)上拍賣系統(tǒng)有極大的社會需求量。網(wǎng)上拍賣系統(tǒng)是指通過internet實施的價格談判交易活動，即利用互聯(lián)網(wǎng)在網(wǎng)

2、站上發(fā)布將要招標(biāo)的物品或服務(wù)信息，通過競爭投標(biāo)的方式將它售給出價最高或出價最低的投標(biāo)者。其實質(zhì)是以競爭價格為核心，建立生產(chǎn)者和消費者之間的交流與互動機制，共同確定價格和數(shù)量，從而達到均衡的一種市場經(jīng)濟過程。所以一個網(wǎng)上拍賣系統(tǒng)要發(fā)揮其重要的作用,它必須允許創(chuàng)建用戶、登陸用戶。每個用戶可以發(fā)布拍賣信息、瀏覽他人的拍賣信息、競拍拍賣物品。為了提高拍賣的效率，系統(tǒng)應(yīng)提供搜索和排序等功能，比如按照關(guān)鍵字進行搜索，按照拍賣開始時間，結(jié)束時間，拍賣的數(shù)量，拍賣者的聯(lián)系方式，拍賣中的最低價格和最高價格等各種排序.而這些該功能系統(tǒng)都已經(jīng)實現(xiàn)。第二章 系統(tǒng)設(shè)計1、總體設(shè)計 設(shè)計思想： 既然要完成網(wǎng)上拍賣系統(tǒng)，首

3、先想到是拍賣系統(tǒng)的參與者client，advertisement和必不可少的date類，相應(yīng)的應(yīng)該有client的集合group和advertisement的集合listing，進一步考慮，假如廣告非常多時，客戶將很難查詢相應(yīng)的信息和找到相應(yīng)的廣告進行投標(biāo)，為了增加客戶的使用體驗，可添加category類及其對應(yīng)的集合類categories來對廣告進行分類，方便客戶對廣告的競標(biāo)和相關(guān)信息的查詢。該系統(tǒng)是網(wǎng)上拍賣系統(tǒng)，client發(fā)布advertisement和對advertisement進行競標(biāo)，所以還應(yīng)該有個bid類。通過分析該系統(tǒng)涉及client，advertisement，date，gr

4、oup，listing，category，categories及bid總共8個類。 基本的數(shù)據(jù)結(jié)構(gòu)： 8個類的屬性和方法如下clientstring fname;string lname;string email;string passwd;vector offerings;vector bids;void addbid (int item);void addoffering (int item);bool verifypasswd(string passwd);一個client除了一些基本的客戶信息外，還分別擁有該客戶發(fā)布的所有廣告offerings及所有的競標(biāo)bids。這里的get，set

5、方法都省去不寫。addbid()方法是將client所競標(biāo)的廣告的id添加到client的bids集合里。addoffering()方法是將client所發(fā)布的廣告的id添加到client的offerins集合里。verifypasswd()方法用來client登錄時驗證密碼的。advertisementint number;/廣告的唯一標(biāo)示符即idint quantity;/提供的競標(biāo)的數(shù)量string title;string seller_email;string body;date start;date close;priority_queue bids;priority_queue&

6、 getbids(void);vector gettopdutchbids (void) const;adervitisement的屬性除了一些基本的信息外，還擁有截至目前為止該廣告的所有競標(biāo)情況即：priority_queue bids;getbids()方法可以獲得截至目前為止的該廣告的所有競標(biāo)bidsgettopdutchbids()方法返回值是vector,該vector里存放的是所有成功的bids，但bid里并非所有的quantity都競標(biāo)上了。dateint month;int day;int year;int hour;int minute;int second;bool ope

7、rator= (const date &rhs);bool operator(istream& in, date& date)date類中重載了操作符=和,為了判斷時間的大小group mapobjects;client *operator(const string& email);void add(client* ptr);iterator begin();iterator end();group是client的集合,使用map實現(xiàn)在這里重載了,通過email可以直接獲得相應(yīng)的client句柄，其他三個方法都是對這個集合的基本操作，添加遍歷等listingvector objectsadve

8、rtisement* operator(const int& number);void add(advertisement* ptr);iterator begin();iterator end();listing sort(string field);listing filter(string keyword);listing類的屬性值只有一個，就是advertisement的集合。方法有：通過重載操作符,可以通過advertisement的唯一標(biāo)識符number獲得相應(yīng)的advertisement對象句柄，這里是advertisement*類型的指針對該集合的一些操作方法，添加和遍歷sor

9、t()方法是按不同的關(guān)鍵字進行排序，方便客戶對數(shù)據(jù)進行分析和決策filter()方法是搜索含有keyword的廣告，方便客戶從大量的廣告中篩選客戶需要的categoryint number;int parent;string name;map sub_categories;map items;category(int parent, string name);map:iterator itemsbegin();map:iterator itemsend();map:iterator subcategoriesbegin();map:iterator subcategoriesend();voi

10、d addsubcategory(int);void additem(int);bool operator=(const category& rhs);category的相關(guān)屬性有本身的id和客戶父親的id，客戶的name，sub_categories是該分類下的所有子分類，items是該分類下所有的廣告方法有：category的構(gòu)造方法;items集合和sub_categories集合的遍歷,添加;重載操作符=;categoriesmap objects;static const int top_level;static const int no_parent;category* opera

11、tor(const int& number);void add(category* ptr);iterator begin();iterator end();findofferings (int category, listing:iterator start, listing:iterator finish, listing &matches);void findofferingsrecursive (int category, listing:iterator start,listing:iterator finish, listing &matches);categories的屬性有ca

12、tegory的集合對象objects；以及兩個靜態(tài)常量top_level和no_parent,用來初始化最開始的category的number和parent屬性值categories的方法有的重載，通過category相應(yīng)的屬性值number可以獲得相應(yīng)的category*;add方法，向objects中添加category;findofferings(),查找當(dāng)前分類下的所有廣告;findofferingsrecursive(),采用遞歸的方法查找當(dāng)前分類下的所有廣告及當(dāng)前分類下的所有子分類的所有廣告;bidstring email;float amount;int quantity;dat

13、e date;bool operator (const bid &rhs) const;bool operator= (const bid &rhs) const;bid的基本屬性及操作符,=的重載2、程序設(shè)計介紹順序按照上面類的先后順序：advertisement中的gettopdutchbids()方法：思路和代碼：vector advertisement:gettopdutchbids (void) constvector winbids;/里面存放競標(biāo)成功的bidint totalwinquantity=0;/記錄所有成功bid的屬性值quantity之和priority_queue

14、copyofbids(this-bids);/復(fù)制一份advertisement的bids，否則會丟失競標(biāo)失敗的相關(guān)信息，避免對原數(shù)據(jù)的直接修改while(totalwinquantitygetquantity()©ofbids.size()!=0)/這里總共有兩個限制條件，缺一不可：/1.totalwinquantity=advertisement所提供的quantity時退出循環(huán)/2.要對優(yōu)先權(quán)隊列進行操作，必須保證其不為空，否則會拋異常totalwinquantity+=copyofbids.top().getquantity();/累加bid的quantitywinbids.p

15、ush_back(copyofbids.top();/將amount最大的bid添加到優(yōu)先權(quán)隊列winbids中copyofbids.pop();/彈出amount最大的bid，取amount次大的bidreturn winbids;復(fù)雜度分析：時間復(fù)雜度分析:最好的情況while循環(huán)一次,最壞的情況n(其中n為this-getquantity()和copyofbids.size()其中較小的一個)空間復(fù)雜度分析：需在棧區(qū)申請vector,int, priority_queue類型的變量各一個bidhistory中displaybidhistory方法的實現(xiàn)：思路：displaybidhist

16、ory分別傳了兩個參數(shù)，一個是引用型的輸出流，一個是advertisement*,首先要顯示的是該廣告的一些基本信息，發(fā)布者的名字可以通過廣告中的email獲得，接下來顯示競標(biāo)情況：如果沒有相應(yīng)的競標(biāo)，則返回，給出相應(yīng)的提示“該條廣告目前沒有任何競標(biāo)”如果有競標(biāo)，假如廣告提供的quantity=1，則顯示該bid的amount和email假如廣告提供的quantity1，遍歷存放所有成功bid的集合winbids，假如沒有遍歷到最后一個bid遍歷中需要將總共成功的quantity累加到winquantity中，每遍歷一次顯示該bid的quantity，成功的quantity和失敗的quanti

17、ty，此時總的quantity是客戶需要的quantity，失敗的quantity等于0如果客戶需要的大于提供的quantity，則成功的quantity為廣告提供的quantity否則成功的quantity等于客戶需要的quantity若遍歷到最后一個bid,令left= advertisement-getquantity()-winquantity如果bid.getquantity()getemail();ossseller :getfname() getlname();ossstart: getstart();ossclose: getclose();ossquantity: getqu

18、antity();ossthe number of bids: getbids().size();vector winbids;priority_queue copyofbids(ad-getbids();winbids=ad-gettopdutchbids();int winquantity=0;int thewinquantityoflastbid=0;oss;if(winbids.empty()ossthe ad dont have any bid until now!;return;if(ad-getquantity()=1) ossthe winning bid is: ;vecto

19、r:iterator it=winbids.begin();ossamount: (*it).getamount();ossemail: (*it).getemail();winquantity=(*it).getquantity();else ossthe winning bids are:;for(vector:iterator it=winbids.begin();it!=winbids.end();it+)ossemail: (*it).getemail();ossamount: (*it).getamount();osstotal quantity:(*it).getquantity

20、();cout(*it).getquantity()(*it).getquantity()endl;if(it!=winbids.end()-1)osswin quantity:(*it).getquantity();winquantity+=(*it).getquantity();osslose quantity: 0;else/最后一個bid的處理情況int temp= ad-getquantity()-winquantity;if(*it).getquantity()=temp)/osswin quantity:(*it).getquantity();winquantity+=(*it)

21、.getquantity();osslose quantity: 0;else osswin quantity:temp;winquantity+=temp;osslose quantity:(*it).getquantity()-temp;ossthe amount of items in the ad that have not been bid on is: getquantity()-winquantityendl;復(fù)雜度分析：時間復(fù)雜度：最好的情況是1，最壞的情況是n(n=(vector) winbids.size()空間復(fù)雜度：主要是在棧區(qū)申請一個vector和priority_q

22、ueue類型的變量date類中重要方法的實現(xiàn):輸入流操作符的重載istream &operator(istream& in, date& date) 實現(xiàn)方法采用getline()對字符串進行分割部分代碼如下：char temp10;int temp1;in.getline(temp,4,/); temp1=atoi(temp);date.setmonth(temp1);in.getline(temp,4,/);temp1=atoi(temp);date.setday(temp1);這個方法實現(xiàn)起來不是很難，在這里提到輸入流的重載是為了說明思維慣性的問題。當(dāng)和同學(xué)們討論時，發(fā)現(xiàn)有一個同學(xué)是這樣

23、實現(xiàn)的：思路比較獨特int month; streammonth; date.setmonth(month); char temp1; /讀入第一個“/” streamtemp1; /舍去不要 int day; streamday; date.setday(day); char temp2; streamtemp2; 他沒有使用分隔符，而是按照順序讀取，擇我所需，以一顆“平常心”對待那些分隔符，覺得這種思路比較簡單明了，但當(dāng)時的我不太容易想得到，因為受思維慣性的影響，一直在想如何使用分隔符，看來編程人員非常需要靈活變通和淡定的心態(tài)。listing類中重要方法的實現(xiàn)：listing listin

24、g:sort(string field)方法的分析：思路：根據(jù)指導(dǎo)書提供的思路，this method returns a copy of the invoking listing object sorted by the field name given in the parameter. use an appropriate stl sorting function to sort the advertisements. the field names that can be passed into this function are email, start, close, and qu

25、antity.，仔細(xì)閱讀之后知道了這個方法體的大概構(gòu)架，sort函數(shù)第三個參數(shù)是個判斷條件，為了避免寫多個判斷條件，可以使用函數(shù)對象sortby來簡化程序。代碼實現(xiàn)：listing listing:sort(string field)listing sortedlist;/ a copy of the invoking listingsortedlist.objects=this-objects;sortby sortby(field);std:sort(sortedlist.objects.begin(),sortedlist.objects.end(),sortby); return so

26、rtedlist; 函數(shù)對象（也稱“算符”）是重載了“()”操作符的普通類對象。從語法上講，函數(shù)對象與普通的函數(shù)行為類似,實現(xiàn)時需要注意幾點:1,里面所有的屬性方法是public.2,因為要使用外界的參數(shù)field，該函數(shù)對象得寫構(gòu)造函數(shù)3,對操作符()的重載函數(shù)對象sortby的實現(xiàn)：class sortbypublic:/the default value is private!string field;sortby(string field):field(field)bool operator()(advertisement* ad1,advertisement* ad2)if(pare

27、(email)=0) if(ad1-getemail().compare(ad2-getemail()getbids().empty()&!ad2-getbids().empty()&(ad1-getbids().top()getbids().top() return true ;else return false; else if(pare(lowest)=0)/在成功的bids里選取amount最小的if(!ad1-gettopdutchbids().empty()&!ad2-gettopdutchbids().empty()&(ad1-gettopdutchbids().back()ge

28、ttopdutchbids().back() return true;else return false; ;下面是lowest的第二種實現(xiàn)方法：在一個廣告的所有bids里選取amount最小的,先拷貝一份priority_queuecopyofbids 然后pop() 直到最后一個，即可獲得最小的amount./*float low1=-1.0,low2=-1.0;priority_queue copyofbids1(ad1-getbids(),copyofbids2(ad2-getbids();if(!copyofbids1.empty() low1=copyofbids1.top().g

29、etamount();while(!copyofbids1.empty() if(low1copyofbids1.top().getamount() low1=copyofbids1.top().getamount(); copyofbids1.pop(); if(!copyofbids2.empty() low2=copyofbids2.top().getamount();while(!copyofbids2.empty() if(low2copyofbids2.top().getamount() low2=copyofbids2.top().getamount(); copyofbids2

30、.pop(); if(low10)&(low20) return true; else return false;*/需要說明的是sortby中l(wèi)owest的排序，就是這個lowest究竟怎么理解，對于一個廣告，它有很多bid，設(shè)winbids是成功的bid，它存放在向量vector里面，totalbids是該廣告所有的bid，它存放在priority_queue里，那么這個lowest是winbids里的lowest還是totalbids里的lowest，這里我選擇前者理由有二:1. 后者的空間復(fù)雜度和時間復(fù)雜度都比前者高。因為后者是使用priority_queue 進行存儲的，要取得最小a

31、mount,必須一直pop()直到最后一個元素，這提高了時間復(fù)雜度，再者不能因為比較大小就對原數(shù)據(jù)進行修改，所以必須copy一份原先的bids，這又提高了空間復(fù)雜度，所以從程序的運行效率來看應(yīng)該選前者。2. 前者更具有現(xiàn)實的指導(dǎo)意義。對于競標(biāo)，人們總想著拿最低的價格換取最多或最好的物品，廣告競標(biāo)成功的最高和最低價格對于下一次相同廣告的競標(biāo)將具有非常好的參考價值。所以真正代碼的實現(xiàn)時我采用前者。這提醒我們程序員編碼前要做好需求分析！listing filter(string keyword)的實現(xiàn)思路：實現(xiàn)起來和sort有點類似，同樣采用函數(shù)對象的方法，難點在于remove_if用法,通過msd

32、n上該函數(shù)的定義及對經(jīng)典例子的分析，對這個函數(shù)有了進一步的認(rèn)識。對msdn上經(jīng)典例子的分析如下：提供程序的運行結(jié)果如圖所示：再配合msdn上的解釋：eliminates elements that satisfy a predicate from a given range without disturbing the order of the remaining elements and returning the end of a new range free of the specified value.由此可見，使用remove_if,并不能把符合條件的元素刪除掉，必須配合使用eras

33、e方可徹底刪除。實現(xiàn)：listing listing:filter(string keyword) listing filtedlist; theadhasnokeyword theadhasnokeyword(keyword); filtedlist.objects=this-objects; listing:container:iterator delete_end=remove_if(filtedlist.objects.begin(),filtedlist.objects.end(),theadhasnokeyword);filtedlist.objects.erase(delete_

34、end,filtedlist.objects.end(); return filtedlist; theadhasnokeyword和sortby實現(xiàn)類似，在這里就不粘貼了。category類重要方法的實現(xiàn)：findofferings方法的分析：思路：findofferings (int category, listing:iterator start, listing:iterator finish, listing &matches);該函數(shù)主要是將當(dāng)前分類下所有的廣告添加到listing類型的matches中,其中start和finish是用來遍歷系統(tǒng)中所有廣告的集合advertisem

35、ents,所以此方法可以這樣來實現(xiàn)，遍歷該category下所有廣告的id(相當(dāng)于遍歷category的items屬性值)，對于每一個id再在advertisements中查找與此id相對應(yīng)的advertisement對象,將其添加到matches中實現(xiàn)：for(map:iterator itercag=this-objectscategory-itemsbegin();itercag!=this-objectscategory-itemsend();itercag+)for(listing:iterator iter=start;iter!=finish;iter+)if(*iter)-ge

36、tnumber()=itercag-second)matches.add(*iter);break;復(fù)雜度分析：時間復(fù)雜度：設(shè)n為此分類下的廣告數(shù)目，m為所有廣告的數(shù)目，則復(fù)雜度為nm無空間復(fù)雜度.findofferingsrecursive()方法的分析：思路：該方法是要實現(xiàn)查找當(dāng)前分類下所有的廣告及子分類下所有的廣告的功能，上面findofferings已經(jīng)實現(xiàn)查找當(dāng)前目錄下的所有廣告，所以可以采用遞歸的方法。實現(xiàn)：category* cag;cag=this-objectscategory;findofferings(category,start,finish,matches);for(

37、map:iterator itersub=cag-subcategoriesbegin();itersub!=cag-subcategoriesend();itersub+)findofferingsrecursive(itersub-second,start,finish,matches);復(fù)雜度分析：時間復(fù)雜度：設(shè)該分類的層數(shù)總共有p層，則該遞歸函數(shù)遞歸的深度為p，設(shè)每層的分類又有q類，而findofferings的復(fù)雜度為nm，所以findofferingsrecursive()的復(fù)雜度為pqnm第三章 系統(tǒng)測試拍賣現(xiàn)場：按照quantity進行排序：查找含有關(guān)鍵字“籃球”的所有廣告：顯

38、示“學(xué)習(xí)用品”類下的所有廣告：對“體育用品”進行拍賣籃球：quantity=1 bid1.getamount()=1 bid2.getamount()=2運行結(jié)果： 乒乓球：quantity=10bid1.getamount()=5 bid1.getquantity()=3bid2.getamount()=6 bid2.getquantity()=4bid3.getamount()=7 bid3.getquantity()=5運行結(jié)果：競標(biāo)情況：bid4.getamount()=8 bid4.getquantity()=8bid4.getamount()=9 bid4.getquantity()=