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

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

数据结构课程设计

专班学姓 日

总结报告

业 级 号 名

期

东北大学软件学院

一个client除了一些基本的客户信息外，还分别拥有该客户发布的所有广告offerings及所有的竞标bids。 这里的get，set方法都省去不写。

addBid()方法是将Client所竞标的广告的id添加到Client的bids集合里。

addOffering()方法是将Client所发布的

void addBid (int item); 广告的id添加到Client的offerins集合void addOffering (int item); 里。 bool verifyPasswd(string passwd); verifyPasswd()方法用来Client登录时验

证密码的。

Advertisement

int number;//广告的唯一标示符即id Adervitisement的属性除了一些

int quantity;//提供的竞标的数量 基本的信息外，还拥有截至目前

string title; 为止该广告的所有竞标情况 string seller_email; 即：priority_queue bids; string body; getBids()方法可以获得截至目前Date start; Date close; 为止的该广告的所有竞标bids priority_queue bids; getTopDutchBids()方法返回值是priority_queue& getBids(void); vector,该vector里存放的vector getTopDutchBids (void) const; 是所有成功的bids，但bid里并

非所有的quantity都竞标上了。 Client string fname; string lname; string email; string passwd; vector offerings; vector bids;

Date int month; int day; int year; int hour; int minute; int second; bool operator== (const Date &rhs); bool operator< (const Date &left); istream &operator>>(istream& in, Date& date)

Group mapobjects;

Date类中重载了操作符==和<,为了判断时间的大小

Client *operator[](const string& email); void add(Client* ptr); iterator begin(); iterator end(); 遍历等

Group是Client的集合,使用map实现

在这里重载了[],通过email可以直接获得相应的Client句柄，其他三个方法都是对这个集合的基本操作，添加

Listing vector objects Advertisement* operator[](const int& number); void add(Advertisement* ptr); iterator begin(); iterator end(); Listing sort(string field); Listing filter(string keyword);

Listing类的属性值只有一个，就是Advertisement的集合。

方法有：

Category 通过重载操作符[],可以通过

int number; Advertisement的唯一标识符int parent; number获得相应的string name; Advertisement对象句柄，这里

map sub_categories; 是Advertisement*类型的指针 map items; 对该集合的一些操作方法，添加Category(int parent, string name); 和遍历 map::iterator itemsBegin(); Sort()方法是按不同的关键字进map::iterator itemsEnd(); map::iterator subCategoriesBegin(); 行排序，方便客户对数据进行分map::iterator subCategoriesEnd(); 析和决策 void addSubCategory(int); Filter()方法是搜索含有void addItem(int); Keyword的广告，方便客户从大

bool operator==(const Category& rhs); 量的广告中筛选客户需要的

Category的相关属性有本身的id和客户父亲的id，客户的name，sub_categories是该分类下的所有子分类，items是该分类下所有的广告 方法有：

Category的构造方法;

Items集合和sub_categories集合的遍历,添加; 重载操作符==;

1

Categories map 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 finish, Listing &matches); void findOfferingsRecursive (int category, Listing::iterator start, Listing::iterator finish, Listing &matches); Categories的属性有category的集合对象objects；以及两个静态常量TOP_LEVEL和NO_PARENT,用来初始化最开始的category的number和parent属性值

Categories的方法有

[]的重载，通过category相应的属性值number可以获得相应的category*; Add方法，向objects中添加category;

findOfferings(),查找当前分类下的所有广告;

findOfferingsRecursive(),采用递归的方法查找当前分类下的所有广告及当前分类下的所有子分类的所有广告;

Bid Bid的基本属性及操作符<,==的重

string email; 载 float amount;

int quantity;

Date date;

bool operator< (const Bid &rhs) const; bool operator== (const Bid &rhs) const;

2、程序设计

介绍顺序按照上面类的先后顺序：

Advertisement中的getTopDutchBids()方法：

思路和代码：

vector Advertisement::getTopDutchBids (void) const{ vector winBids;//里面存放竞标成功的bid

int totalWinQuantity=0;//记录所有成功bid的属性值quantity之和 priority_queue copyOfBids(this->bids);

//复制一份Advertisement的bids，否则会丢失竞标失败的相关信息，避免对原数据的直接修改

while(totalWinQuantitygetQuantity()&©OfBids.size()!=0){

//这里总共有两个限制条件，缺一不可：

//1.totalWinQuantity>=Advertisement所提供的quantity时退出循环

2

//2.要对优先权队列进行操作，必须保证其不为空，否则会抛异常

totalWinQuantity+=copyOfBids.top().getQuantity();//累加bid的quantity winBids.push_back(copyOfBids.top());//将amount最大的bid添加到优先权队列winBids中

copyOfBids.pop();//弹出amount最大的bid，取amount次大的bid }

return winBids; }

复杂度分析：

时间复杂度分析:最好的情况while循环一次,最坏的情况N(其中N为this->getQuantity()和copyOfBids.size()其中较小的一个) 空间复杂度分析：需在栈区申请vector,int, priority_queue类型的变量各一个

Bidhistory中displayBidHistory方法的实现：

思路：

displayBidHistory分别传了两个参数，一个是引用型的输出流，一个是Advertisement*,首先要显示的是该广告的一些基本信息，发布者的名字可以通过广告中的email获得，接下来显示竞标情况：

如果没有相应的竞标，则返回，给出相应的提示“该条广告目前没有任何竞标” 如果有竞标，

假如广告提供的quantity=1，则显示该bid的amount和email

假如广告提供的quantity>1，遍历存放所有成功bid的集合winBids，

假如没有遍历到最后一个bid

遍历中需要将总共成功的quantity累加到winQuantity中，每遍历一次显示该bid的quantity，成功的quantity和失败的quantity，此时总的quantity是客户需要的quantity，失败的quantity等于0

如果客户需要的大于提供的quantity，则成功的quantity为广告

提供的quantity

否则成功的quantity等于客户需要的quantity

若遍历到最后一个bid,

令left= advertisement->getQuantity()-winQuantity 如果bid.getQuantity()

则成功的quantity等于客户需要的quantity，失败的quantity=0

否则成功的quantity=left 失败的quantity=客户需要的quantity-left 代码实现：

void displayBidHistory(ostringstream &oss, Advertisement* ad){ Client *c=users[ad->getEmail()];

oss<<\\<getFname()<<\<getLname()<<\; oss<<\<getStart()<<\; oss<<\<getClose()<<\;

oss<<\<getQuantity()<<\;

oss<<\<getBids().size()<<\;

3

vector winBids;

priority_queue copyOfBids(ad->getBids()); winBids=ad->getTopDutchBids(); int winQuantity=0;

int theWinQuantityOfLastBid=0; oss<<\;

if(winBids.empty()){

oss<<\<<\<<\; return; }

if(ad->getQuantity()==1) {

oss<<\<<\;

vector::iterator it=winBids.begin(); oss<<\<<(*it).getAmount()<<\; oss<<\<<(*it).getEmail()<<\; winQuantity=(*it).getQuantity(); }else {

oss<<\<<\;

for(vector::iterator it=winBids.begin();it!=winBids.end();it++){ oss<<\<<(*it).getEmail()<<\; oss<<\<<(*it).getAmount()<<\;

oss<<\<<(*it).getQuantity()<<\; cout<<\<<(*it).getQuantity()<

oss<<\<<(*it).getQuantity()<<\; winQuantity+=(*it).getQuantity(); oss<<\<<\; }else{//最后一个bid的处理情况

int temp= ad->getQuantity()-winQuantity; if((*it).getQuantity()<=temp){//

oss<<\<<(*it).getQuantity()<<\; winQuantity+=(*it).getQuantity(); oss<<\<<\; }else {

oss<<\<

oss<<\

quantity:\<<(*it).getQuantity()-temp<<\\;

} } } }

oss<<\

4

\<getQuantity()-winQuantity<

复杂度分析：

时间复杂度：最好的情况是1，最坏的情况是N(N=(vector) winBids.size()) 空间复杂度：主要是在栈区申请一个vector和priority_queue类型的变量

Date类中重要方法的实现:

输入流操作符的重载istream &operator>>(istream& in, Date& date) 实现方法采用getline()对字符串进行分割 部分代码如下：

char temp[10]; int temp1;

in.getline(temp,4,'/'); temp1=atoi(temp);

date.setMonth(temp1); in.getline(temp,4,'/'); temp1=atoi(temp); date.setDay(temp1);

这个方法实现起来不是很难，在这里提到输入流的重载是为了说明思维惯性的问题。当和同学们讨论时，发现有一个同学是这样实现的：思路比较独特 int month;

stream>>month;

date.setMonth(month);

char temp1; //读入第一个“/” stream>>temp1; //舍去不要 int day;

stream>>day;

date.setDay(day); char temp2; stream>>temp2;

他没有使用分隔符，而是按照顺序读取，择我所需，以一颗“平常心”对待那些分隔符，觉得这种思路比较简单明了，但当时的我不太容易想得到，因为受思维惯性的影响，一直在想如何使用分隔符，看来编程人员非常需要灵活变通和淡定的心态。

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 passed into this function are \

5

\，仔细阅读之后知道了这个方法体的大概构架，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.objects.begin(),sortedList.objects.end(),sortBy);

return sortedList; }

函数对象（也称“算符”）是重载了“()”操作符的普通类对象。从语法上讲，函数对象与普通的函数行为类似,实现时需要注意几点: 1,里面所有的属性方法是public.

2,因为要使用外界的参数field，该函数对象得写构造函数 3,对操作符()的重载

函数对象SortBy的实现：

class SortBy{

public://the default value is private!!! string field;

SortBy(string field):field(field){}

bool operator()(Advertisement* ad1,Advertisement* ad2){ if(field.compare(\)==0){

if(ad1->getEmail().compare(ad2->getEmail())<0) return true ; else return false; ……为减少篇幅，雷同代码已省去……

}else if(field.compare(\)==0){

if(!ad1->getBids().empty()&&!ad2->getBids().empty()&&(ad1->getBids().top()getBids().top()))

return true ;else return false; }else if(field.compare(\)==0){

//在成功的bids里选取amount最小的

if(!ad1->getTopDutchBids().empty()&&!ad2->getTopDutchBids().empty()&&(ad1->getTopDutchBids().back()getTopDutchBids().back())) return true;else return false; } } };

下面是lowest的第二种实现方法：

在一个广告的所有bids里选取amount最小的,先拷贝一份priority_queue

6

copyOfBids 然后pop() 直到最后一个，即可获得最小的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(low1>copyOfBids1.top().getAmount()) { low1=copyOfBids1.top().getAmount(); }

copyOfBids1.pop(); }

if(!copyOfBids2.empty()) low2=copyOfBids2.top().getAmount(); while(!copyOfBids2.empty()) {

if(low2>copyOfBids2.top().getAmount()) { low2=copyOfBids2.top().getAmount(); }

copyOfBids2.pop(); }

if((low10)&&(low2>0)) return true; else return false;*/

需要说明的是SortBy中lowest的排序，就是这个lowest究竟怎么理解，对于一个广告，它有很多bid，设winBids是成功的bid，它存放在向量vector里面，totalBids是该广告所有的bid，它存放在priority_queue里，那么这个lowest是winBids里的lowest还是totalBids里的lowest，这里我选择前者理由有二:

1. 后者的空间复杂度和时间复杂度都比前者高。因为后者是使用

priority_queue 进行存储的，要取得最小amount,必须一直pop()直到最后一个元素，这提高了时间复杂度，再者不能因为比较大小就对原数据进行修改，所以必须copy一份原先的bids，这又提高了空间复杂度，所以从程序的运行效率来看应该选前者。

2. 前者更具有现实的指导意义。对于竞标，人们总想着拿最低的价格换取最多

或最好的物品，广告竞标成功的最高和最低价格对于下一次相同广告的竞标将具有非常好的参考价值。

所以真正代码的实现时我采用前者。这提醒我们程序员编码前要做好需求分析！

Listing filter(string keyword)的实现

思路：实现起来和sort有点类似，同样采用函数对象的方法，难点在于remove_if 用法,通过msdn上该函数的定义及对经典例子的分析，对这个函数有了进一步的认识。对msdn上经典例子的分析如下： 提供程序的运行结果如图所示：

7

再配合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,并不能把符合条件的元素删除掉，必须配合使用erase方可彻底删除。 实现：

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_end,filtedList.objects.end()); return filtedList; }

TheAdHasNoKeyword和SortBy实现类似，在这里就不粘贴了。

Category类重要方法的实现：

findOfferings方法的分析：

思路：findOfferings (int category, Listing::iterator start, Listing::iterator finish, Listing &matches);该函数主要是将当前分类下所有的广告添加到Listing类型的matches中,其中start和finish是用来遍历系统中所有广告的集合advertisements,所以此方法可以这样来实现，遍历该category下所有广告的id(相当于遍历

category的items属性值)，对于每一个id再在advertisements中查找与此id相对应的advertisement对象,将其添加到matches中 实现：

for(map::iterator

itercag=this->objects[category]->itemsBegin();itercag!=this->objects[category]->itemsEnd();itercag++) { for(Listing::iterator iter=start;iter!=finish;iter++) { if((*iter)->getNumber()==itercag->second) { matches.add((*iter)); break; } } }

复杂度分析： 时间复杂度：设N为此分类下的广告数目，M为所有广告的数目，则复杂度为NM

8

无空间复杂度.

findOfferingsRecursive()方法的分析：

思路：该方法是要实现查找当前分类下所有的广告及子分类下所有的广告的功能，上面findOfferings已经实现查找当前目录下的所有广告，所以可以采用递归的方法。 实现：

Category* cag;

cag=this->objects[category];

findOfferings(category,start,finish,matches); for(map::iterator

itersub=cag->subCategoriesBegin();itersub!=cag->subCategoriesEnd();itersub++) {

findOfferingsRecursive(itersub->second,start,finish,matches); }

复杂度分析：

时间复杂度：设该分类的层数总共有P层，则该递归函数递归的深度为P，设每层的分类又有Q类，而findOfferings的复杂度为NM，所以findOfferingsRecursive()的复杂度为PQNM

第三章 系统测试

拍卖现场：

按照quantity进行排序：

查找含有关键字“篮球”的所有广告：

显示“学习用品”类下的所有广告：

对“体育用品”进行拍卖 篮球：quantity=1

bid1.getAmount()=1 bid2.getAmount()=2 运行结果：

9

乒乓球：quantity=10

Bid1.getAmount()=5 Bid1.getQuantity()=3 Bid2.getAmount()=6 Bid2.getQuantity()=4 Bid3.getAmount()=7 Bid3.getQuantity()=5 运行结果：

竞标情况：

Bid4.getAmount()=8 Bid4.getQuantity()=8

Bid4.getAmount()=9 Bid4.getQuantity()=12

出现的问题及解决办法：

出现的问题很多，在这里只列举一些

1. 向category中添加item时，出现如下问题

一步一步调试后发现错误的位置是：addItem的方法体写的有问题 原先的：this->items.push_back(item);

改正后：this->items.insert(pair((this->items.size()-1),item));(map实现)

10

2. 在实现getTopDutchBids()方法是出现的问题：

解决的方法：定义了一个priority_queue copyOfBids(this->bids)

3. 出现问题最多的是下面这个：

这种错误都是因为没有对vector或者priority_queue进行非空判断而直接访问其内容导致程序中断

解决办法：使用之前保证他们非空即可

4. 在第六个试验中，Group.cpp中用map实现时[]的重载时，VS2008的智能提示无论如何都调不出来（调不出来就意味着程序有错误），一般这种问题都是由于程序的cpp或h文件没有复制到vs2008的项目文件夹下导致的，可这次的问题却不是因为这个。

解决办法：利用vs2008自动画出项目类图的功能，从类图中发现Group.h文件居然重复导入，而真正经过map声明的那个Group.h文件却没有导入到项目中。

5. 当客户所需要的数量大于广告提供的数量时，total quantity(客户所需要的数量)显示有问题，比如广告提供5个足球，客户需要10个篮球，运行结果应该为total quantity=10 win quantity=5 lose quantity=5 可结果却是

解决办法：一步一步调试，发现系统中有这样的设置：

11

要想真实反映客户的需求，只需注释掉else if即可。

第五章 结论

该系统允许创建用户、登陆用户。每个用户可以发布拍卖信息、浏览他人的拍卖信息、竞拍拍卖物品。浏览拍卖信息的时候还可以按照各种关键字排序，其中包括按照拍卖开始时间，结束时间，拍卖的数量，拍卖者的联系方式，拍卖

中的最低价格和最高价格，还可以通过关键字查询到相关的拍卖信息。 系统主要的创新之处在于

1. 不仅显示某个广告竞拍成功的最高价，还显示了竞拍成功的最低价,这一功

能将有利于竞标者获得物美价廉的东西； 2. 实现了按竞价高低对广告进行排序；

3. 在显示竞价信息时更加详细，不仅显示成功的数量而且显示失败的数量; 4. 修改系统的默认设置，真实显示客户的需求，这有利于发布者发布适合市场

需求的广告，进而从中获利。 系统遗留的问题如下：

1. 对于拍卖系统的整个框架还不是很清楚，还需要在研究研究

2. 该系统只实现了增加广告，对于已经竞标完成的广告，应将其删除，删除功

能还没实现

3. 对于显示的竞标信息，采用表格的形式会更清晰明了些

解决的办法：只要再给一些时间，我相信我能解决这些问题

参考文献

例：

[1] 萨师煊，王珊.数据库系统概论（第三版）[M].北京: 高等教育出版

社,2002,122-150.

[2] 侯敏.Java编程思想[M].北京:机械工业出版社,2002,22-35.

12