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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計網(wǎng)上拍賣系統(tǒng)實(shí)驗報告(C+)actively carry out the law on civil air defense education, drawn out of the air defense in Pingliang city Building under easy fare, daily special inspection and regulation, overfulfilled the province upper and lower knots of up to 500,000 yuan fee collection tasks. 5, further s

2、tandardize internal management, improve staff quality. Adhere to theactively carry out the law on civil air defense education, drawn out of the air defense in Pingliang city Building under easy fare, daily special inspection and regulation, overfulfilled the province upper and lower knots of up to 5

3、00,000 yuan fee collection tasks. 5, further standardize internal management, improve staff quality. Adhere to theactively carry out the law on civil air defense education, drawn out of the air defense in Pingliang city Building under easy fare, daily special inspection and regulation, overfulfilled

4、 the province upper and lower knots of up to 500,000 yuan fee collection tasks. 5, further standardize internal management, improve staff quality. Adhere to the數(shù)據(jù)結(jié)構(gòu)課程設(shè)計總結(jié)報告 專 業(yè) 班 級 學(xué) 號 姓 名 日 期 東北大學(xué)軟件學(xué)院PAGE PAGE 13Clientstring fname;string lname;string email;string passwd;vector offerings;vector bids

5、;void addBid (int item);void addOffering (int item);bool verifyPasswd(string passwd);一個client除了一些基本的客戶信息外，還分別擁有該客戶發(fā)布的所有廣告offerings及所有的競標(biāo)bids。這里的get，set方法都省去不寫。addBid()方法是將Client所競標(biāo)的廣告的id添加到Client的bids集合里。addOffering()方法是將Client所發(fā)布的廣告的id添加到Client的offerins集合里。verifyPasswd()方法用來Client登錄時驗證密碼的。Advertise

6、mentint number;/廣告的唯一標(biāo)示符即idint quantity;/提供的競標(biāo)的數(shù)量string title;string seller_email;string body;Date start;Date close;priority_queue bids;priority_queue& getBids(void);vector getTopDutchBids (void) const;Adervitisement的屬性除了一些基本的信息外，還擁有截至目前為止該廣告的所有競標(biāo)情況即：priority_queue bids;getBids()方法可以獲得截至目前為止的該廣告的所有競

7、標(biāo)bidsgetTopDutchBids()方法返回值是vector,該vector里存放的是所有成功的bids，但bid里并非所有的quantity都競標(biāo)上了。Dateint month;int day;int year;int hour;int minute;int second;bool operator= (const Date &rhs);bool operator(istream& in, Date& date)Date類中重載了操作符=和,為了判斷時間的大小Group mapobjects;Client *operator(const string& email);void ad

8、d(Client* ptr);iterator begin();iterator end();Group是Client的集合,使用map實(shí)現(xiàn)在這里重載了,通過email可以直接獲得相應(yīng)的Client句柄，其他三個方法都是對這個集合的基本操作，添加遍歷等Listingvector objectsAdvertisement* operator(const int& number);void add(Advertisement* ptr);iterator begin();iterator end();Listing sort(string field);Listing filter(string

9、keyword);Listing類的屬性值只有一個，就是Advertisement的集合。方法有：通過重載操作符,可以通過Advertisement的唯一標(biāo)識符number獲得相應(yīng)的Advertisement對象句柄，這里是Advertisement*類型的指針對該集合的一些操作方法，添加和遍歷Sort()方法是按不同的關(guān)鍵字進(jìn)行排序，方便客戶對數(shù)據(jù)進(jìn)行分析和決策Filter()方法是搜索含有Keyword的廣告，方便客戶從大量的廣告中篩選客戶需要的Categoryint number;int parent;string name;map sub_categories;map items;Ca

10、tegory(int parent, string name);map:iterator itemsBegin();map:iterator itemsEnd();map:iterator subCategoriesBegin();map:iterator subCategoriesEnd();void addSubCategory(int);void addItem(int);bool operator=(const Category& rhs);Category的相關(guān)屬性有本身的id和客戶父親的id，客戶的name，sub_categories是該分類下的所有子分類，items是該分類下所

11、有的廣告方法有：Category的構(gòu)造方法;Items集合和sub_categories集合的遍歷,添加;重載操作符=;Categoriesmap objects;static const int TOP_LEVEL;static const int NO_PARENT;Category* operator(const int& number);void add(Category* ptr);iterator begin();iterator end();findOfferings (int category, Listing:iterator start, Listing:iterator

12、finish, Listing &matches);void findOfferingsRecursive (int category, Listing:iterator start,Listing:iterator finish, Listing &matches);Categories的屬性有category的集合對象objects；以及兩個靜態(tài)常量TOP_LEVEL和NO_PARENT,用來初始化最開始的category的number和parent屬性值Categories的方法有的重載，通過category相應(yīng)的屬性值number可以獲得相應(yīng)的category*;Add方法，向obje

13、cts中添加category;findOfferings(),查找當(dāng)前分類下的所有廣告;findOfferingsRecursive(),采用遞歸的方法查找當(dāng)前分類下的所有廣告及當(dāng)前分類下的所有子分類的所有廣告;Bidstring email;float amount;int quantity;Date date;bool operator (const Bid &rhs) const;bool operator= (const Bid &rhs) const;Bid的基本屬性及操作符,=的重載2、程序設(shè)計介紹順序按照上面類的先后順序：Advertisement中的getTopDutchBid

14、s()方法：思路和代碼：vector Advertisement:getTopDutchBids (void) constvector winBids;/里面存放競標(biāo)成功的bidint totalWinQuantity=0;/記錄所有成功bid的屬性值quantity之和priority_queue copyOfBids(this-bids);/復(fù)制一份Advertisement的bids，否則會丟失競標(biāo)失敗的相關(guān)信息，避免對原數(shù)據(jù)的直接修改while(totalWinQuantitygetQuantity()©OfBids.size()!=0)/這里總共有兩個限制條件，缺一不可：/1

15、.totalWinQuantity=Advertisement所提供的quantity時退出循環(huán)/2.要對優(yōu)先權(quán)隊列進(jìn)行操作，必須保證其不為空，否則會拋異常totalWinQuantity+=copyOfBids.top().getQuantity();/累加bid的quantitywinBids.push_back(copyOfBids.top();/將amount最大的bid添加到優(yōu)先權(quán)隊列winBids中copyOfBids.pop();/彈出amount最大的bid，取amount次大的bidreturn winBids;復(fù)雜度分析：時間復(fù)雜度分析:最好的情況while循環(huán)一次,最壞的

16、情況N(其中N為this-getQuantity()和copyOfBids.size()其中較小的一個)空間復(fù)雜度分析：需在棧區(qū)申請vector,int, priority_queue類型的變量各一個Bidhistory中displayBidHistory方法的實(shí)現(xiàn)：思路：displayBidHistory分別傳了兩個參數(shù)，一個是引用型的輸出流，一個是Advertisement*,首先要顯示的是該廣告的一些基本信息，發(fā)布者的名字可以通過廣告中的email獲得，接下來顯示競標(biāo)情況：如果沒有相應(yīng)的競標(biāo)，則返回，給出相應(yīng)的提示“該條廣告目前沒有任何競標(biāo)”如果有競標(biāo)，假如廣告提供的quantity=1

17、，則顯示該bid的amount和email假如廣告提供的quantity1，遍歷存放所有成功bid的集合winBids，假如沒有遍歷到最后一個bid遍歷中需要將總共成功的quantity累加到winQuantity中，每遍歷一次顯示該bid的quantity，成功的quantity和失敗的quantity，此時總的quantity是客戶需要的quantity，失敗的quantity等于0如果客戶需要的大于提供的quantity，則成功的quantity為廣告提供的quantity否則成功的quantity等于客戶需要的quantity若遍歷到最后一個bid,令left= advertiseme

18、nt-getQuantity()-winQuantity如果bid.getQuantity()getEmail();ossseller :getFname() getLname();ossstart: getStart();ossclose: getClose();ossquantity: getQuantity();ossthe number of bids: getBids().size();vector winBids;priority_queue copyOfBids(ad-getBids();winBids=ad-getTopDutchBids();int winQuantity=0

19、;int theWinQuantityOfLastBid=0;oss;if(winBids.empty()ossthe ad dont have any bid until now!;return;if(ad-getQuantity()=1) ossthe winning bid is: ;vector:iterator it=winBids.begin();ossamount: (*it).getAmount();ossemail: (*it).getEmail();winQuantity=(*it).getQuantity();else ossthe winning bids are:;f

20、or(vector:iterator it=winBids.begin();it!=winBids.end();it+)ossemail: (*it).getEmail();ossamount: (*it).getAmount();osstotal quantity:(*it).getQuantity();cout(*it).getQuantity()(*it).getQuantity()endl;if(it!=winBids.end()-1)osswin quantity:(*it).getQuantity();winQuantity+=(*it).getQuantity();osslose

21、 quantity: 0;else/最后一個bid的處理情況int temp= ad-getQuantity()-winQuantity;if(*it).getQuantity()=temp)/osswin quantity:(*it).getQuantity();winQuantity+=(*it).getQuantity();osslose quantity: 0;else osswin quantity:temp;winQuantity+=temp;osslose quantity:(*it).getQuantity()-temp;ossthe amount of items in th

22、e ad that have not been bid on is: getQuantity()-winQuantityendl;復(fù)雜度分析：時間復(fù)雜度：最好的情況是1，最壞的情況是N(N=(vector) winBids.size()空間復(fù)雜度：主要是在棧區(qū)申請一個vector和priority_queue類型的變量Date類中重要方法的實(shí)現(xiàn):輸入流操作符的重載istream &operator(istream& in, Date& date) 實(shí)現(xiàn)方法采用getline()對字符串進(jìn)行分割部分代碼如下：char temp10;int temp1;in.getline(temp,4,/);

23、temp1=atoi(temp);date.setMonth(temp1);in.getline(temp,4,/);temp1=atoi(temp);date.setDay(temp1);這個方法實(shí)現(xiàn)起來不是很難，在這里提到輸入流的重載是為了說明思維慣性的問題。當(dāng)和同學(xué)們討論時，發(fā)現(xiàn)有一個同學(xué)是這樣實(shí)現(xiàn)的：思路比較獨(dú)特int month; streammonth; date.setMonth(month); char temp1; /讀入第一個“/” streamtemp1; /舍去不要 int day; streamday; date.setDay(day); char temp2; st

24、reamtemp2; 他沒有使用分隔符，而是按照順序讀取，擇我所需，以一顆“平常心”對待那些分隔符，覺得這種思路比較簡單明了，但當(dāng)時的我不太容易想得到，因為受思維慣性的影響，一直在想如何使用分隔符，看來編程人員非常需要靈活變通和淡定的心態(tài)。Listing類中重要方法的實(shí)現(xiàn)：Listing Listing: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. Us

25、e an appropriate STL sorting function to sort the advertisements. The field names that can be passed into this function are email, start, close, and quantity.，仔細(xì)閱讀之后知道了這個方法體的大概構(gòu)架，sort函數(shù)第三個參數(shù)是個判斷條件，為了避免寫多個判斷條件，可以使用函數(shù)對象SortBy來簡化程序。代碼實(shí)現(xiàn)：Listing Listing:sort(string field)Listing sortedList;/ a copy of t

26、he invoking ListingsortedList.objects=this-objects;SortBy sortBy(field);std:sort(sortedList.objects.begin(),sortedList.objects.end(),sortBy); return sortedList; 函數(shù)對象（也稱“算符”）是重載了“()”操作符的普通類對象。從語法上講，函數(shù)對象與普通的函數(shù)行為類似,實(shí)現(xiàn)時需要注意幾點(diǎn):1,里面所有的屬性方法是public.2,因為要使用外界的參數(shù)field，該函數(shù)對象得寫構(gòu)造函數(shù)3,對操作符()的重載函數(shù)對象SortBy的實(shí)現(xiàn)：class

27、 SortBypublic:/the default value is private!string field;SortBy(string field):field(field)bool operator()(Advertisement* ad1,Advertisement* ad2)if(pare(email)=0) if(ad1-getEmail().compare(ad2-getEmail()getBids().empty()&!ad2-getBids().empty()&(ad1-getBids().top()getBids().top() return true ;else ret

28、urn false; else if(pare(lowest)=0)/在成功的bids里選取amount最小的if(!ad1-getTopDutchBids().empty()&!ad2-getTopDutchBids().empty()&(ad1-getTopDutchBids().back()getTopDutchBids().back() return true;else return false; ;下面是lowest的第二種實(shí)現(xiàn)方法：在一個廣告的所有bids里選取amount最小的,先拷貝一份priority_queuecopyOfBids 然后pop() 直到最后一個，即可獲得最小

29、的amount./*float low1=-1.0,low2=-1.0;priority_queue copyOfBids1(ad1-getBids(),copyOfBids2(ad2-getBids();if(!copyOfBids1.empty() low1=copyOfBids1.top().getAmount();while(!copyOfBids1.empty() if(low1copyOfBids1.top().getAmount() low1=copyOfBids1.top().getAmount(); copyOfBids1.pop(); if(!copyOfBids2.emp

30、ty() low2=copyOfBids2.top().getAmount();while(!copyOfBids2.empty() if(low2copyOfBids2.top().getAmount() low2=copyOfBids2.top().getAmount(); copyOfBids2.pop(); if(low10)&(low20) return true; else return false;*/需要說明的是SortBy中l(wèi)owest的排序，就是這個lowest究竟怎么理解，對于一個廣告，它有很多bid，設(shè)winBids是成功的bid，它存放在向量vector里面，tota

31、lBids是該廣告所有的bid，它存放在priority_queue里，那么這個lowest是winBids里的lowest還是totalBids里的lowest，這里我選擇前者理由有二:后者的空間復(fù)雜度和時間復(fù)雜度都比前者高。因為后者是使用priority_queue 進(jìn)行存儲的，要取得最小amount,必須一直pop()直到最后一個元素，這提高了時間復(fù)雜度，再者不能因為比較大小就對原數(shù)據(jù)進(jìn)行修改，所以必須copy一份原先的bids，這又提高了空間復(fù)雜度，所以從程序的運(yùn)行效率來看應(yīng)該選前者。前者更具有現(xiàn)實(shí)的指導(dǎo)意義。對于競標(biāo)，人們總想著拿最低的價格換取最多或最好的物品，廣告競標(biāo)成功的最高和最

32、低價格對于下一次相同廣告的競標(biāo)將具有非常好的參考價值。所以真正代碼的實(shí)現(xiàn)時我采用前者。這提醒我們程序員編碼前要做好需求分析！Listing filter(string keyword)的實(shí)現(xiàn)思路：實(shí)現(xiàn)起來和sort有點(diǎn)類似，同樣采用函數(shù)對象的方法，難點(diǎn)在于remove_if用法,通過msdn上該函數(shù)的定義及對經(jīng)典例子的分析，對這個函數(shù)有了進(jìn)一步的認(rèn)識。對msdn上經(jīng)典例子的分析如下：提供程序的運(yùn)行結(jié)果如圖所示：再配合msdn上的解釋：Eliminates elements that satisfy a predicate from a given range without disturbin

33、g the order of the remaining elements and returning the end of a new range free of the specified value.由此可見，使用remove_if,并不能把符合條件的元素刪除掉，必須配合使用erase方可徹底刪除。實(shí)現(xiàn)：Listing Listing:filter(string keyword) Listing filtedList; TheAdHasNoKeyword theAdHasNoKeyword(keyword); filtedList.objects=this-objects; Listin

34、g:Container:iterator delete_end=remove_if(filtedList.objects.begin(),filtedList.objects.end(),theAdHasNoKeyword);filtedList.objects.erase(delete_end,filtedList.objects.end(); return filtedList; TheAdHasNoKeyword和SortBy實(shí)現(xiàn)類似，在這里就不粘貼了。Category類重要方法的實(shí)現(xiàn)：findOfferings方法的分析：思路：findOfferings (int category,

35、Listing:iterator start, Listing:iterator finish, Listing &matches);該函數(shù)主要是將當(dāng)前分類下所有的廣告添加到Listing類型的matches中,其中start和finish是用來遍歷系統(tǒng)中所有廣告的集合advertisements,所以此方法可以這樣來實(shí)現(xiàn)，遍歷該category下所有廣告的id(相當(dāng)于遍歷category的items屬性值)，對于每一個id再在advertisements中查找與此id相對應(yīng)的advertisement對象,將其添加到matches中實(shí)現(xiàn)：for(map:iterator itercag=th

36、is-objectscategory-itemsBegin();itercag!=this-objectscategory-itemsEnd();itercag+)for(Listing:iterator iter=start;iter!=finish;iter+)if(*iter)-getNumber()=itercag-second)matches.add(*iter);break;復(fù)雜度分析：時間復(fù)雜度：設(shè)N為此分類下的廣告數(shù)目，M為所有廣告的數(shù)目，則復(fù)雜度為NM無空間復(fù)雜度.findOfferingsRecursive()方法的分析：思路：該方法是要實(shí)現(xiàn)查找當(dāng)前分類下所有的廣告及子分類

37、下所有的廣告的功能，上面findOfferings已經(jīng)實(shí)現(xiàn)查找當(dāng)前目錄下的所有廣告，所以可以采用遞歸的方法。實(shí)現(xiàn)：Category* cag;cag=this-objectscategory;findOfferings(category,start,finish,matches);for(map:iterator itersub=cag-subCategoriesBegin();itersub!=cag-subCategoriesEnd();itersub+)findOfferingsRecursive(itersub-second,start,finish,matches);復(fù)雜度分析：時間

38、復(fù)雜度：設(shè)該分類的層數(shù)總共有P層，則該遞歸函數(shù)遞歸的深度為P，設(shè)每層的分類又有Q類，而findOfferings的復(fù)雜度為NM，所以findOfferingsRecursive()的復(fù)雜度為PQNM第三章 系統(tǒng)測試拍賣現(xiàn)場：按照quantity進(jìn)行排序：查找含有關(guān)鍵字“籃球”的所有廣告：顯示“學(xué)習(xí)用品”類下的所有廣告：對“體育用品”進(jìn)行拍賣籃球：quantity=1 bid1.getAmount()=1 bid2.getAmount()=2運(yùn)行結(jié)果： 乒乓球：quantity=10Bid1.getAmount()=5 Bid1.getQuantity()=3Bid2.getAmount()=6 Bid2.getQuantity()=4Bid3.getAmount()=7 Bid3.getQuantity()=5運(yùn)行結(jié)果：競標(biāo)情況：Bid4.getAmount()=8 Bid4.getQua