数据结构实验报告

1、第一章 需求分析问题的定义：本次课程设计所要求完成的是一个网上拍卖系统。该系统是根据题目描述及写好的的框架代码，完成所要求的一些类和函数去实现网上拍卖系统。本次课程设计共分为六个部分去逐步实现该拍卖系统，在本次实验自己完成了拍卖系统的前五个部分。项目分析：利用数据结构所学知识和算法设计完成该网上拍卖系统。很明显该系统共分五个部分是由浅入深逐渐完善的，每个实验部分完成项目不同需求。随着实验的进行，功能越来越完备，越往后越符合实际拍卖的需求。实践资料已经为我们提供了完整的项目实践指导书和附加的框架代码。研究意义：本系统允许用户对advertisement根据不同的关键去排序，同现实生活中我们到网上

2、拍卖购物一样，用户需要此种功能来进行对自己更好的选择。为了使用户更方便地选择购物，我们设置了开始和关闭的时间、卖方的email以及物品数量、拍卖的最高最低价，这样用户可以更方便的进行搜索，这些从买方和卖方的角度考都是很有必要的。买方还可以根据自己的需求自己创建商品的子目录，这样更有利于商品的分类，可以更为直观地选择自己所需的物品。第二章 系统设计1、总体设计 给出设计思想，基本的数据结构，抽象数据类型的定义，主要的操作的定义（或类的定义） 设计思想： 根据拍卖的实际特点和实验指导书中所给的提示从用户角度出发，充分考虑各项基本算法设计的合理性来选择合适的数据结构来编写正确的算法解决该拍卖问题。基

3、本数据结构： 优先级队列、串、数组等常用的一些数据结构的逻辑形式、存储形式以及实现各种操作的算法。主要的抽象数据类型和类的定义：主要的抽象数据类型包括group和 listing、category等。group是一个client的集合，用来记录所有的用户，listing是一个advertisment的集合，是用来存储拍卖品的集合，category是用来记录相同类型的拍卖品的集合。2、程序设计get、set方法及构造函数的实现，在这里不予与说明。实验一：1.date类的实现：操作符的重载operator=， operator(istream& istr, date& rhs)的实现，由于已经规定

4、了时间的格式，所以通过istream，输入整型变量和字符变量，重复输入简化对时间字符串格式分割的处理。char ch;int datepart;/read the monthstreamdatepart;streamch;date.setmonth(datepart);2. advertisement类的实现：bool advertisement:operator=(const advertisement& a) const：若advertisement的唯一性标识number相等，则说明两个产品是同一个产品，等号成立。istream &operator(istream &stream, ad

5、vertisement &a)：同data中的重载方法相同，都是利用输入整形变量和字符变量来进行区别实现规定格式的输入。3. client类的实现：bool verifypasswd(string passwd)：用来验证用户注册时重复输入的密码与一开始输入的密码是否相等。实验二：1.listing类的实现：本类的实现主要的是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类的实现：本类的实现主要也是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.第三个实验完善了系统，添加了对拍卖物品的分类功能；category，categories。主要是处理拍卖物品的分类问题。2.category类的实现：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);这部分代码是遍历递归的关键。在此递归调用了findofferings(start,finish,matches);利用循环返回遍历子目录，这就是所用到的递归思想。3.categoryies类的实现原理同前面代码有相似之处，不做分析实验四：1.更改listing类，实现了sorting和filtering。2.利用的是stl函数，通过引用函数对象来完成相关操作。遍历查找到匹配的关键字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;下面代码是遍历查找的关键，当查找到匹配的关键字时就把它显示出来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类的实现：bid类的主要功能是实现对拍卖物品的投标竞拍；主要是实现操作符重载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类的修改。第三章 系统实现与调试自己算法设计主要体现在for循环的遍历上，如实验二listing类中对对象advertisement的遍历；因为只有一个for循环，所以空间复杂度为iter；时间复杂度为iter；其余for循环分析类似，有的套用的两个for循环，相应的时间复杂度是两个for循环的执行次数乘积。第四章 系统测试第五章 结论程序的最终实现结果：本次实验最终实现了课程设计所给定的前五个部分，完成了一个具有一定功能的网上拍卖系统，完成的功能有：注册用户、添加拍卖品、进行竞拍、可以对产品进行分类查找等功能。可实现实网上竞拍，系统可以显示出获胜方的联系方式以及获胜的筹码。通过本次课程设计，不但巩固了所学过的数据结构相关知识，而且对一些算法有了一个初步的掌握