1、数据结构课程设计网上拍卖系统实验报告C+数据结构课程设计总结报告 专 业 班 级 学 号 姓 名 日 期 东北大学软件学院第一章 需求分析随着网络技术的不断发展和人们购物意识的不断革新，网上购物成为一种新型的购物方式，正逐渐被人们所接受和认可，而网上购物的方式之一的网上拍卖形式给人们的购物带来另一种全新的体验，人们可以通过网站发出自己想要拍卖的物品的信息，也可以通过购买自己想要的物品，即具有一般的购物网站的成本低廉，方式灵活，运行快捷的特点，更具有自由竞争和公平合理的特性，如现在流行的拍拍网，淘宝网等都是很好的成功的实例。所以网上拍卖系统有极大的社会需求量。网上拍卖系统是指通过internet
2、实施的价格谈判交易活动，即利用互联网在网站上发布将要招标的物品或服务信息，通过竞争投标的方式将它售给出价最高或出价最低的投标者。其实质是以竞争价格为核心，建立生产者和消费者之间的交流与互动机制，共同确定价格和数量，从而达到均衡的一种市场经济过程。所以一个网上拍卖系统要发挥其重要的作用,它必须允许创建用户、登陆用户。每个用户可以发布拍卖信息、浏览他人的拍卖信息、竞拍拍卖物品。为了提高拍卖的效率，系统应提供搜索和排序等功能，比如按照关键字进行搜索，按照拍卖开始时间，结束时间，拍卖的数量，拍卖者的联系方式，拍卖中的最低价格和最高价格等各种排序.而这些该功能系统都已经实现。第二章 系统设计1、总体设计
3、 设计思想： 既然要完成网上拍卖系统，首先想到是拍卖系统的参与者Client，Advertisement和必不可少的Date类，相应的应该有Client的集合Group和Advertisement的集合Listing，进一步考虑，假如广告非常多时，客户将很难查询相应的信息和找到相应的广告进行投标，为了增加客户的使用体验，可添加category类及其对应的集合类categories来对广告进行分类，方便客户对广告的竞标和相关信息的查询。该系统是网上拍卖系统，Client发布Advertisement和对Advertisement进行竞标，所以还应该有个Bid类。通过分析该系统涉及Client，A
4、dvertisement，Date，Group，Listing，Category，Categories及Bid总共8个类。 基本的数据结构： 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除了一些基本的客户信息外，还分别拥有该客户发布的所有广告offerings及
5、所有的竞标bids。这里的get，set方法都省去不写。addBid()方法是将Client所竞标的广告的id添加到Client的bids集合里。addOffering()方法是将Client所发布的广告的id添加到Client的offerins集合里。verifyPasswd()方法用来Client登录时验证密码的。 Advertisementint number;/广告的唯一标示符即idint quantity;/提供的竞标的数量string title;string seller_email;string body;Date start;Date close;priority_queue
6、 bids;priority_queue& getBids(void);vector getTopDutchBids (void) const;Adervitisement的属性除了一些基本的信息外，还拥有截至目前为止该广告的所有竞标情况即：priority_queue bids;getBids()方法可以获得截至目前为止的该广告的所有竞标bidsgetTopDutchBids()方法返回值是vector,该vector里存放的是所有成功的bids，但bid里并非所有的quantity都竞标上了。Dateint month;int day;int year;int hour;int minut
7、e;int second;bool operator= (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实现在这里重载了,通过email可以直接获得相应的Client句柄，其他三个方法都是对这个集合的基本操作，添加遍历等List
8、ingvector objectsAdvertisement* operator(const int& number);void add(Advertisement* ptr);iterator begin();iterator end();Listing sort(string field);Listing filter(string keyword);Listing类的属性值只有一个，就是Advertisement的集合。方法有：通过重载操作符,可以通过Advertisement的唯一标识符number获得相应的Advertisement对象句柄，这里是Advertisement*类型的指
9、针对该集合的一些操作方法，添加和遍历Sort()方法是按不同的关键字进行排序，方便客户对数据进行分析和决策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 s
10、ubCategoriesEnd();void addSubCategory(int);void addItem(int);bool operator=(const Category& rhs);Category的相关属性有本身的id和客户父亲的id，客户的name，sub_categories是该分类下的所有子分类，items是该分类下所有的广告方法有：Category的构造方法;Items集合和sub_categories集合的遍历,添加;重载操作符=;Categoriesmap objects;static const int TOP_LEVEL;static const int NO_P
11、ARENT;Category* operator(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 &matc
12、hes);Categories的属性有category的集合对象objects；以及两个静态常量TOP_LEVEL和NO_PARENT,用来初始化最开始的category的number和parent属性值Categories的方法有的重载，通过category相应的属性值number可以获得相应的category*;Add方法，向objects中添加category;findOfferings(),查找当前分类下的所有广告;findOfferingsRecursive(),采用递归的方法查找当前分类下的所有广告及当前分类下的所有子分类的所有广告;Bidstring email;float am
13、ount;int quantity;Date date;bool operator (const Bid &rhs) const;bool operator= (const Bid &rhs) const;Bid的基本属性及操作符,=的重载2、程序设计介绍顺序按照上面类的先后顺序：Advertisement中的getTopDutchBids()方法：思路和代码：vector Advertisement:getTopDutchBids (void) constvector winBids;/里面存放竞标成功的bidint totalWinQuantity=0;/记录所有成功bid的属性值quan
14、tity之和priority_queue copyOfBids(this-bids);/复制一份Advertisement的bids，否则会丢失竞标失败的相关信息，避免对原数据的直接修改 while(totalWinQuantitygetQuantity()©OfBids.size()!=0)/这里总共有两个限制条件，缺一不可：/1.totalWinQuantity=Advertisement所提供的quantity时退出循环/2.要对优先权队列进行操作，必须保证其不为空，否则会抛异常totalWinQuantity+=copyOfBids.top().getQuantity();/累
15、加bid的quantitywinBids.push_back(copyOfBids.top();/将amount最大的bid添加到优先权队列winBids中copyOfBids.pop();/弹出amount最大的bid，取amount次大的bidreturn winBids;复杂度分析：时间复杂度分析:最好的情况while循环一次,最坏的情况N(其中N为this-getQuantity()和copyOfBids.size()其中较小的一个)空间复杂度分析：需在栈区申请vector,int, priority_queue类型的变量各一个Bidhistory中displayBidHistory方
16、法的实现：思路：displayBidHistory分别传了两个参数，一个是引用型的输出流，一个是Advertisement*,首先要显示的是该广告的一些基本信息，发布者的名字可以通过广告中的email获得，接下来显示竞标情况：如果没有相应的竞标，则返回，给出相应的提示“该条广告目前没有任何竞标”如果有竞标，假如广告提供的quantity=1，则显示该bid的amount和email假如广告提供的quantity1，遍历存放所有成功bid的集合winBids，假如没有遍历到最后一个bid遍历中需要将总共成功的quantity累加到winQuantity中，每遍历一次显示该bid的quantity
17、，成功的quantity和失败的quantity，此时总的quantity是客户需要的quantity，失败的quantity等于0如果客户需要的大于提供的quantity，则成功的quantity为广告提供的quantity否则成功的quantity等于客户需要的quantity 若遍历到最后一个bid,令left= advertisement-getQuantity()-winQuantity如果bid.getQuantity()getEmail();ossseller :getFname() getLname();ossstart: getStart();ossclose: getClo
18、se();ossquantity: getQuantity();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) osst
19、he winning bid is: ; vector: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(); os
20、stotal quantity:(*it).getQuantity(); 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 quant
21、ity:(*it).getQuantity(); winQuantity+=(*it).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;复杂度分析：时间复杂度：最好的情况是1，最坏的情况是N(N=(vector)
22、winBids.size()空间复杂度：主要是在栈区申请一个vector和priority_queue类型的变量Date类中重要方法的实现:输入流操作符的重载istream &operator(istream& in, Date& date) 实现方法采用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);这个方
23、法实现起来不是很难，在这里提到输入流的重载是为了说明思维惯性的问题。当和同学们讨论时，发现有一个同学是这样实现的：思路比较独特 int month; streammonth; date.setMonth(month); char temp1; /读入第一个“/” streamtemp1; /舍去不要 int day; streamday; date.setDay(day); char temp2; streamtemp2; 他没有使用分隔符，而是按照顺序读取，择我所需，以一颗“平常心”对待那些分隔符，觉得这种思路比较简单明了，但当时的我不太容易想得到，因为受思维惯性的影响，一直在想如何使用分隔
24、符，看来编程人员非常需要灵活变通和淡定的心态。Listing类中重要方法的实现：Listing Listing:sort(string field)方法的分析：思路：根据指导书提供的思路，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 pas
25、sed into this function are email, start, close, and quantity.，仔细阅读之后知道了这个方法体的大概构架，sort函数第三个参数是个判断条件，为了避免写多个判断条件，可以使用函数对象SortBy来简化程序。代码实现：Listing Listing:sort(string field) Listing sortedList;/ a copy of the invoking Listing sortedList.objects=this-objects; SortBy sortBy(field); std:sort(sortedList.o
26、bjects.begin(),sortedList.objects.end(),sortBy); return sortedList; 函数对象（也称“算符”）是重载了“()”操作符的普通类对象。从语法上讲，函数对象与普通的函数行为类似,实现时需要注意几点:1,里面所有的属性方法是public.2,因为要使用外界的参数field，该函数对象得写构造函数3,对操作符()的重载函数对象SortBy的实现：class SortBypublic:/the default value is private! string field; SortBy(string field):field(field)
27、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 return 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
