数据结构课程设计网上拍卖系统实验报告(C++)

1、数据结构课程设计总结报告专 业班 级学 号姓 名日 期东北大学软件学院第一章 需求分析低廉，方式灵活，运行快捷的特点，更具有自由竞争和公平合理的特性，如现在会需求量。网上拍卖系统是指通过 internet 实施的价格谈判交易活动，即利用互联网在交流与互动机制，共同确定价格和数量，从而达到均衡的一种市场经济过程。所以一个网上拍卖系统要发挥其重要的作用,它必须允许创建用户、登陆用户。每个用户可以发布拍卖信息、浏览他人的拍卖信息、竞拍拍卖物品。为了提拍卖开始时间，结束时间，拍卖的数量，拍卖者的联系方式，拍卖中的最低价格和最高价格等各种排序.而这些该功能系统都已经实现。第二章 系统设计1、总体设计设计

2、思想：既然要完成网上拍卖系统，首先想到是拍卖系统的参与者 Client，Advertisement 和必不可少的 Date 类，相应的应该有 Client 的集合 Group 和Advertisement 的集合 Listing，进一步考虑，假如广告非常多时，客户将很难查询相应的信息和找到相应的广告进行投标，为了增加客户的使用体验，可添加 category类及其对应的集合类 categories来对广告进行分类，方便客户对广告的竞标和相关信息的查询。该系统是网上拍卖系统，Client 发布Advertisement和对 Advertisement 进行竞标，所以还应该有个Bid类。通过分析该系

3、统涉及 ClientAdvertisementDateGroupCategoryCategories及 Bid总共 8 个类。基本的数据结构：8 个类的属性和方法如下一个 client 除了一些基本的客户信息外，还分别拥有该客户发布的所有广告offerings及所有的竞标 bids。string fname;string lname;string email;这里的 ，set 方法都省去不写。addBid()方法是将 Client 所竞标的广告的id 添加到 Client 的 bids集合里。方法是将 Client 所发布的广告的 id 添加到 Client的 offerins集合里。veri

4、fyPasswd()方法用来Client登录时验证密码的。void addBid (int item);void addOffering (int item);bool verifyPasswd(string passwd);AdvertisementAdervitisement的属性除了一些基本的信息外，还拥有截至目前为止该广告的所有竞标情况int number;/广告的唯一标示符即 idint quantity;/提供的竞标的数量string title;string seller_email;string body;Date start;Date close;priority_queue

5、 bids;priority_queue& getBids(void);vector getTopDutchBids (void) const;即：priority_queue bids;getBids()方法可以获得截至目前为止的该广告的所有竞标 bidsgetTopDutchBids()方法返回值是vector,该 vector 里存放的是所有成功的 bids bid 里并非所有的 quantity都竞标上了。Date 类中重载了操作符=和为了判断时间的大小int year;bool operator= (const Date &rhs);bool operator(istream& in

6、, Date& date)Groupmapobjects;Client *operator(const string& email);void add(Client* ptr);iterator begin();Group是Client的集合,使用map实现在这里重载了,通过 email 可以直接获得相应的 Client 句柄，其他三个方法都是对这个集合的基本操作，添加遍历等iterator end();1vector objectsAdvertisement* operator(const int& number);void add(Advertisement* ptr);iterator

7、begin();iterator end();Listing sort(string field);Listing filter(string keyword);Listing类的属性值只有一个，就是 Advertisement 的集合。方法有：通过重载操作符,可以通过 Advertisement 的唯一标识符 number 获得相应的Advertisement对象句柄，这里是 Advertisement*类型的指针对该集合的一些操作方法，添加和遍历Sort()方法是按不同的关键字进行排序，方便客户对数据进行分析和决策方法是搜索含有 Keyword的Category的相关属性有本身的idint

8、 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();void addSubCategory(int);void addItem(int);和客户父亲的 id ，sub_categories 是该分类下的所有子分类，items 是该分

9、类下所有的广告方法有：Category的构造方法;Items集合和sub_categories集合的遍历,添加;重载操作符=;bool operator=(const Category& rhs);Categoriesmap objects;static const int TOP_LEVEL;static const int NO_PARENT;Category* operator(const int& number);void add(Category* ptr);findOfferings (int category, Listing:iterator start,Listing:ite

10、rator finish, Listing &matches);void findOfferingsRecursive (int category, Listing:iterator start,Listing:iterator finish, Listing &matches);2Categories的属性有category的集合对象objects TOP_LEVEL和 NO_PARENT,用来初始化最开始的 category的 number和 parent 属性值Categories的方法有的重载，通过 category相应的属性值 number 可以获得相应的 category*;Add

11、方法，向 objects 中添加 category;查找当前分类下的所有广告;findOfferingsRecursive(),采用递归的方法查找当前分类下的所有广告及当前分类下的所有子分类的所有广告;BidBid 的基本属性及操作符,=的重载int quantity;Date date;bool operator (const Bid &rhs) const;bool operator= (const Bid &rhs) const;2、程序设计介绍顺序按照上面类的先后顺序：Advertisement中的 方法：思路和代码：vector Advertisement:getTopDutchBi

12、ds (void) constvector winBids;/里面存放竞标成功的bidint totalWinQuantity=0;/记录所有成功bid的属性值quantity之和priority_queue copyOfBids(this-bids);/复制一份Advertisement的bids，否则会丢失竞标失败的相关信息，避免对原数据的直接修改while(totalWinQuantitygetQuantity()©OfBids.size()!=0)/这里总共有两个限制条件，缺一不可：/1.totalWinQuantity=Advertisement所提供的quantity时退出

13、循环/2.要对优先权队列进行操作，必须保证其不为空，否则会抛异常totalWinQuantity+=copyOfBids.top().getQuantity();/累加bid的quantitywinBids.push_back(copyOfBids.top();/将amount最大的bid添加到优先权队列winBids中copyOfBids.pop();/弹出amount最大的bid，取amount次大的bidreturn winBids;复杂度分析：时间复杂度分析:最好的情况 while 循环一次,最坏的情况 N(其中 N 为this-getQuantity()和 copyOfBids.si

14、ze()其中较小的一个)空间复杂度分析：需在栈区申请 vector,int, priority_queue类型的变量各一个3Bidhistory中 displayBidHistory 方法的实现：思路：displayBidHistory 分别传了两个参数，一个是引用型的输出流，一个是Advertisement*,首先要显示的是该广告的一些基本信息，发布者的名字可以通过广告中的 email获得，接下来显示竞标情况：如果没有相应的竞标，则返回，给出相应的提示“该条广告目前没有任何竞标”如果有竞标，假如广告提供的 quantity=1，则显示该 bid 的 amount 和 email假如广告提供的

15、 quantity1，遍历存放所有成功 bid 的集合 winBids，假如没有遍历到最后一个 bid遍历中需要将总共成功的 quantity 累加到 winQuantity 中，每遍历一次显示该 bid 的 ，成功的quantity 和失败的 quantity的 quantity是客户需要的 quantity，失败的 quantity等于 0如果客户需要的大于提供的 quantity，则成功的 quantity 为广告提供的 quantity否则成功的 quantity等于客户需要的 quantity若遍历到最后一个 bid,令 left= advertisement-getQuantity

16、()-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;int theWinQ

17、uantityOfLastBid=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();4ossamount: (*it).getAmount();ossemail: (*it).getEmail();winQuantity=(*it).getQuantity();else ossthe winning bids are:;for(vector:i

18、terator 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 quantity:

19、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;osslosequantity:(*it).getQuantity()-temp;ossthe amount of items in the ad that ha

20、ve not been bid on is:getQuantity()-winQuantityendl;复杂度分析：时间复杂度：最好的情况是 1，最坏的情况是 N(N=(vector) winBids.size() vector和 priority_queue类型的变量Date类中重要方法的实现:输入流操作符的重载 istream &operator(istream& in, Date& date)实现方法采用 getline()对字符串进行分割部分代码如下：char temp10;int temp1;5in.getline(temp,4,/);temp1=atoi(temp);date.se

21、tMonth(temp1);in.getline(temp,4,/);temp1=atoi(temp);date.setDay(temp1);题。当和同学们讨论时，发现有一个同学是这样实现的：思路比较独特int month;streammonth;date.setMonth(month);char temp1; /读入第一个“/”streamtemp1; /舍去不要int day;streamday;date.setDay(day);char temp2;streamtemp2;他没有使用分隔符，而是按照顺序读取，择我所需，以一颗“平常心”对待那些的心态。Listing类中重要方法的实现：Li

22、sting Listing:sort(string field)方法的分析：思路：根据指导书提供的思路，This method returns acopy of the invoking Listingobjectsorted by the field name given in the parameter. Use an appropriate STLsorting function to sort the advertisements. The field names that can be passed intothis function areemail, start, close,

23、and 这个方法体的大概构架，sort函数第三个参数是个判断条件，为了避免写多个判断条件，可以使用函数对象来简化程序。代码实现：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 sortedList;函数对象（也称“算符”）

24、是重载了“()”操作符的普通类对象。从语法上讲，函数对象与普通的函数行为类似,实现时需要注意几点:61,里面所有的属性方法是 public.2,因为要使用外界的参数 field，该函数对象得写构造函数3,对操作符的重载函数对象 SortBy 的实现：class 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-ge

25、tEmail().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()getTopDutchBids().back()

26、return true;else return false;下面是 lowest的第二种实现方法：在一个广告的所有 bids 里选取 amount 最小的,先拷贝一份 priority_queuecopyOfBids 然后 pop() 直到最后一个，即可获得最小的 amount./*float low1=-1.0,low2=-1.0;priority_queuecopyOfBids1(ad1-getBids(),copyOfBids2(ad2-getBids();if(!copyOfBids1.empty() low1=copyOfBids1.top().getAmount();while(!

27、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();7copyOfBids2.pop();if(low10)&(lo

28、w20) return true; elsereturn false;*/需要说明的是 SortBy 中 lowest 的排序，就是这个 lowest 究竟怎么理解，对于一个广告，它有很多 bid，设 winBids 是成功的 bid，它存放在向量 vector里面，totalBids 是该广告所有的 bid，它存放在 priority_queue里，那么这个lowest是 winBids里的 lowest 还是 totalBids 里的 lowest二:1. 后者的空间复杂度和时间复杂度都比前者高。因为后者是使用priority_queue 进行存储的，要取得最小amount,必须一直 po

29、p()直到最后一个元素，这提高了时间复杂度，再者不能因为比较大小就对原数据进行修改，所以必须 copy 一份原先的 bids，这又提高了空间复杂度，所以从程序的运行效率来看应该选前者。2. 前者更具有现实的指导意义。对于竞标，人们总想着拿最低的价格换取最多将具有非常好的参考价值。所以真正代码的实现时我采用前者。这提醒我们程序员编码前要做好需求分析！Listing filter(string keyword)的实现思路：实现起来和有点类似，同样采用函数对象的方法，难点在于remove_if用法,通过msdn上该函数的定义及对经典例子的分析，对这个函数有了进一步的认识。对msdn上经典例子的分析如

30、下：提供程序的运行结果如图所示：再配合msdn上的解释：Eliminates elements that satisfy a predicate from a given range without disturbing theorder of the remaining elements and returning the end of a new range free of thespecified value.由此可见，使用remove_if,并不能把符合条件的元素删除掉，必须配合使用erase方可彻底删除。实现：Listing Listing:filter(string keyword

31、)Listing filtedList;TheAdHasNoKeyword theAdHasNoKeyword(keyword);filtedList.objects=this-objects;Listing:Container:iteratordelete_end=remove_if(filtedList.objects.begin(),filtedList.objects.end(),theAdHasNoKeyword);filtedList.objects.erase(delete_end,filtedList.objects.end();8return filtedList;TheAd

32、HasNoKeyword和实现类似，在这里就不粘贴了。类重要方法的实现：findOfferings方法的分析：思路：findOfferings (int category, Listing:iterator start, Listing:iterator finish, Listing&matches);该函数主要是将当前分类下所有的广告添加到类型的matches中,其中start和finish是用来遍历系统中所有广告的集合advertisements,所以此方法可以这样来实现，遍历该下所有广告的id(相当于遍历的items属性值id再在advertisements中查找与此id相对应的adv

33、ertisement对象,将其添加到matches中实现：for(map:iteratoritercag=this-objectscategory-itemsBegin();itercag!=this-objectscategory-itemsEnd();itercag+)for(Listing:iterator iter=start;iter!=finish;iter+)if(*iter)-getNumber()=itercag-second)matches.add(*iter);break;复杂度分析：为此分类下的广告数目，MNM无空间复杂度.findOfferingsRecursive(

34、)方法的分析：思路：该方法是要实现查找当前分类下所有的广告及子分类下所有的广告的功能，上面findOfferings已经实现查找当前目录下的所有广告，所以可以采用递归的方法。实现：Category* cag;cag=this-objectscategory;findOfferings(category,start,finish,matches);for(map:iteratoritersub=cag-subCategoriesBegin();itersub!=cag-subCategoriesEnd();itersub+)findOfferingsRecursive(itersub-secon

35、d,start,finish,matches);9复杂度分析：时间复杂度：设该分类的层数总共有P层，则该递归函数递归的深度为P，设每层的分类又有的复杂度为NM，所以findOfferingsRecursive()的复杂度为PQNM第三章 系统测试拍卖现场：按照 quantity进行排序：查找含有关键字“篮球”的所有广告：显示“学习用品”类下的所有广告：对“体育用品”进行拍卖篮球：quantity=1bid1.getAmount()=1 bid2.getAmount()=2运行结果：乒乓球：quantity=10Bid1.getAmount()=5 Bid1.getQuantity()=3Bid2.getAmount()=6 Bid2.getQuantity()=4Bid3.getAmount()=7 Bid3.getQuantity()=5运行结果：竞标情况：Bid4.getAmoun