數(shù)據(jù)結(jié)構(gòu)實驗報告

1、第一章 需求分析問題的定義：本次課程設(shè)計所要求完成的是一個網(wǎng)上拍賣系統(tǒng)。該系統(tǒng)是根據(jù)題目描述及寫好的的框架代碼，完成所要求的一些類和函數(shù)去實現(xiàn)網(wǎng)上拍賣系統(tǒng)。本次課程設(shè)計共分為六個部分去逐步實現(xiàn)該拍賣系統(tǒng)，在本次實驗自己完成了拍賣系統(tǒng)的前五個部分。項目分析：利用數(shù)據(jù)結(jié)構(gòu)所學(xué)知識和算法設(shè)計完成該網(wǎng)上拍賣系統(tǒng)。很明顯該系統(tǒng)共分五個部分是由淺入深逐漸完善的，每個實驗部分完成項目不同需求。隨著實驗的進行，功能越來越完備，越往后越符合實際拍賣的需求。實踐資料已經(jīng)為我們提供了完整的項目實踐指導(dǎo)書和附加的框架代碼。研究意義：本系統(tǒng)允許用戶對advertisement根據(jù)不同的關(guān)鍵去排序，同現(xiàn)實生活中我們到網(wǎng)上

2、拍賣購物一樣，用戶需要此種功能來進行對自己更好的選擇。為了使用戶更方便地選擇購物，我們設(shè)置了開始和關(guān)閉的時間、賣方的email以及物品數(shù)量、拍賣的最高最低價，這樣用戶可以更方便的進行搜索，這些從買方和賣方的角度考都是很有必要的。買方還可以根據(jù)自己的需求自己創(chuàng)建商品的子目錄，這樣更有利于商品的分類，可以更為直觀地選擇自己所需的物品。第二章 系統(tǒng)設(shè)計1、總體設(shè)計 給出設(shè)計思想，基本的數(shù)據(jù)結(jié)構(gòu)，抽象數(shù)據(jù)類型的定義，主要的操作的定義（或類的定義） 設(shè)計思想： 根據(jù)拍賣的實際特點和實驗指導(dǎo)書中所給的提示從用戶角度出發(fā)，充分考慮各項基本算法設(shè)計的合理性來選擇合適的數(shù)據(jù)結(jié)構(gòu)來編寫正確的算法解決該拍賣問題?；?/p>

3、本數(shù)據(jù)結(jié)構(gòu)： 優(yōu)先級隊列、串、數(shù)組等常用的一些數(shù)據(jù)結(jié)構(gòu)的邏輯形式、存儲形式以及實現(xiàn)各種操作的算法。主要的抽象數(shù)據(jù)類型和類的定義：主要的抽象數(shù)據(jù)類型包括group和 listing、category等。group是一個client的集合，用來記錄所有的用戶，listing是一個advertisment的集合，是用來存儲拍賣品的集合，category是用來記錄相同類型的拍賣品的集合。2、程序設(shè)計get、set方法及構(gòu)造函數(shù)的實現(xiàn)，在這里不予與說明。實驗一：1.date類的實現(xiàn)：操作符的重載operator=， operator(istream& istr, date& rhs)的實現(xiàn)，由于已經(jīng)規(guī)定

4、了時間的格式，所以通過istream，輸入整型變量和字符變量，重復(fù)輸入簡化對時間字符串格式分割的處理。char ch;int datepart;/read the monthstreamdatepart;streamch;date.setmonth(datepart);2. advertisement類的實現(xiàn)：bool advertisement:operator=(const advertisement& a) const：若advertisement的唯一性標識number相等，則說明兩個產(chǎn)品是同一個產(chǎn)品，等號成立。istream &operator(istream &stream, ad

5、vertisement &a)：同data中的重載方法相同，都是利用輸入整形變量和字符變量來進行區(qū)別實現(xiàn)規(guī)定格式的輸入。3. client類的實現(xiàn)：bool verifypasswd(string passwd)：用來驗證用戶注冊時重復(fù)輸入的密碼與一開始輸入的密碼是否相等。實驗二：1.listing類的實現(xiàn)：本類的實現(xiàn)主要的是vector的使用。本類主要裝載生成的advertisement的對象。virtual void add(advertisement* ptr) 添加advertisement對象virtual iterator begin() 返回vector中第一個advertise

6、ment對象的iterator；virtual iterator end() 返回vector中第一個advertisement對象的iterator；advertisement* listing:operator(const int& number)for(vector:iterator iter = objects.begin();iter != objects.end(); iter+)if(*iter)-getnumber() = number)return *iter;return null;2.group類的實現(xiàn)：本類的實現(xiàn)主要也是vector的使用。本類主要裝載生成的用戶clie

7、nt對象。client* group:operator(const string& email)for(vector:iterator iter = objects.begin(); iter != objects.end(); iter+)if(*iter)-getemail() = email)return *iter;return null; 實驗三：1.第三個實驗完善了系統(tǒng)，添加了對拍賣物品的分類功能；category，categories。主要是處理拍賣物品的分類問題。2.category類的實現(xiàn)：void category:findofferings(listing:iterato

8、r start, listing:iterator finish, listing& matches)listing:iterator iterlist = start;while(iterlist != finish)for(vector:iterator iteritem = this-items.begin();iteritem != this-items.end(); iteritem+)if(*(*iterlist).getnumber() = (*iteritem)matches.add(*iterlist);iterlist+;void category:findoffering

9、srecursive (listing:iterator start, listing:iterator finish, listing &matches)findofferings(start, finish, matches);if(this-sub_categories.empty()return;elsefor(vector:iterator iter = this-sub_categories.begin();iter != this-sub_categories.end(); iter+)(*iter)-findofferingsrecursive(start, finish, m

10、atches);這部分代碼是遍歷遞歸的關(guān)鍵。在此遞歸調(diào)用了findofferings(start,finish,matches);利用循環(huán)返回遍歷子目錄，這就是所用到的遞歸思想。3.categoryies類的實現(xiàn)原理同前面代碼有相似之處，不做分析實驗四：1.更改listing類，實現(xiàn)了sorting和filtering。2.利用的是stl函數(shù)，通過引用函數(shù)對象來完成相關(guān)操作。遍歷查找到匹配的關(guān)鍵字listing listing:sort(string field)listing sortlist;for(listing:iterator iter = this-objects.begin();

11、iter != this-objects.end(); iter+)sortlist.add(*iter);if(field = email)std:sort(sortlist.begin(), sortlist.end(), emailcmp);if(field = start)std:sort(sortlist.begin(), sortlist.end(), startcmp);if(field = close)std:sort(sortlist.begin(), sortlist.end(), closecmp);if(field = quantity)std:sort(sortlis

12、t.begin(), sortlist.end(), quantitycmp);return sortlist;下面代碼是遍歷查找的關(guān)鍵，當(dāng)查找到匹配的關(guān)鍵字時就把它顯示出來class filtstring key;public:filt(string keyword):key(keyword)operator()(advertisement *a)string title = (*a).gettitle();string body = (*a).getbody();if(strstr(title.c_str(), key.c_str() != null| strstr(body.c_str(

13、), key.c_str() != null)return false;elsereturn true;listing listing:filter(string keyword)listing removelist = listing(*this);listing:iterator last;if(keyword = )return removelist;elselast = remove_if(removelist.begin(), removelist.end(), filt(keyword);removelist.objects.erase(last, removelist.objec

14、ts.end();return removelist;實驗五：1. bid類的實現(xiàn)：bid類的主要功能是實現(xiàn)對拍賣物品的投標競拍；主要是實現(xiàn)操作符重載2. 對advertisement類的修改vector advertisement:gettopdutchbids(void) const/返回拍賣值中最高的vector topbid;priority_queue dutchbid = this-bids;int ad = this-quantity;while(ad 0 & dutchbid.size() 0)if(dutchbid.size() 0)if(ad dutchbid.top().

15、getquantity()topbid.push_back(dutchbid.top();ad -= dutchbid.top().getquantity();dutchbid.pop();elsead = 0;topbid.push_back(dutchbid.top();return topbid;3. client類的修改。第三章 系統(tǒng)實現(xiàn)與調(diào)試自己算法設(shè)計主要體現(xiàn)在for循環(huán)的遍歷上，如實驗二listing類中對對象advertisement的遍歷；因為只有一個for循環(huán)，所以空間復(fù)雜度為iter；時間復(fù)雜度為iter；其余for循環(huán)分析類似，有的套用的兩個for循環(huán)，相應(yīng)的時間復(fù)雜度是兩個for循環(huán)的執(zhí)行次數(shù)乘積。第四章 系統(tǒng)測試第五章 結(jié)論程序的最終實現(xiàn)結(jié)果：本次實驗最終實現(xiàn)了課程設(shè)計所給定的前五個部分，完成了一個具有一定功能的網(wǎng)上拍賣系統(tǒng)，完成的功能有：注冊用戶、添加拍賣品、進行競拍、可以對產(chǎn)品進行分類查找等功能。可實現(xiàn)實網(wǎng)上競拍，系統(tǒng)可以顯示出獲勝方的聯(lián)系方式以及獲勝的籌碼。通過本次課程設(shè)計，不但鞏固了所學(xué)過的數(shù)據(jù)結(jié)構(gòu)相關(guān)知識，而且對一些算法有了一個初步的掌握，