数据结构课程设计--网上拍卖系统.doc

数据结构课程设计任务书数据结构课程设计总结报告 专 业 软件工程 班 级 软件赴日1101 学 号 20112271 姓 名 贾志远 日 期 2013年9月17日 东北大学软件学院2第一章 需求分析1、 实验要求： 设计一个网上拍卖系统，有些类的头文件和主函数已经给出，通过头文件中定义的部分和实验中的提示来编写类的代码，从而完成拍卖系统的全部功能。 实验共分五个部分，由浅入深逐渐完善，而且只有完成了前一部分实验，才能继续进行下一部分的实验内容。2、 问题分析： 根据实验要求，可知此网上拍卖系统大致包含以下几个部分：注册、登陆、增加广告、添加子目录、显示商品列表、查找广告、 广告排序、客户竞标。由实验已给的部分代码来看，应该有以下几个部分：广告（Advertisement） 、广告集合（Listing）、目录（Category）、目录集合（Categories）、标价（bid）、客户（Client）、 客户组（Group），系统应围绕这些部分的关系，编写各自的函数，从而完成拍卖系统的功能。3、 实验目的： 通过实验进一步了解线性表、堆栈、队列、串、数组、广义表、树、图以及一些排序算法等数据结构内容。培养根据用户的要求及系统提供的数据，设计或选择合适的数据结构并能编写正确的算法解决实际问题的能力第二章 系统设计1、总体设计 a.总体思路： 先写好系统的基本骨架：Date、Client 、Advertisement这三个类，完成系统的基本功能，然后根据系统的功能需求编写相应的类完成功能拓展。 具体的类间关系为：Categories储存多个Category，Category通过Listing类储存这个目录下的Advertisement，Listing是Advertisement的集合，而Advertisement信息中包含多个Client对自己的竞标（bid），Client又可以对多个Advertisement进行竞标并发布Advertisement，Group是Client的集合，所以包含多个Client。其他的是过程类，由main调用processrequest类，再由processrequest调用相应的buildbidpage、buildpage、bidhistory类将结果显示在页面中。 体现在UML类图中如图所示： b.基本的数据结构： 数据结构除了上述分析中所定义的类，还包括stl中的优先权队列和Vector集合。c 各类主要操作定义如下：u Class Date： operator=(const Date &rhs) operator(istream&, Date&) operator(istream &stream, Advertisement &a) virtual vector getTopDutchBids (void) const;u Class Client ： Client (const Client &a) operator(istream &stream, Client &c) u Class Listing： add(Advertisement*ptr) operator(const int& number) virtual Listing sort(string field); virtual Listing filter(string keyword);u Class Group： Client *operator(const string& email)u Class Category： virtual void addSubCategory(Category*); virtual void addItem(int); virtual void findOfferings (Listing:iterator start, Listing:iterator finish, Listing &matches); virtual void findOfferingsRecursive (Listing:iterator start, Listing:iterator finish, Listing &matches); virtual bool operator=(const Category& rhs);u Class Bid： virtual bool operator (const Bid &rhs) const; virtual bool operator= (const Bid &rhs) const;u Class bidhistory： Void displayBidHistory(ostringstream &oss, Advertisement* ad);2、程序设计 系统的操作对应系统的功能，共有七种，分别是：客户注册、登陆、添加广告、添加子目录、按关键字查找广告、对广告排序、竞标。用户在使用系统之前需进行注册，然后登陆系统后可以按提示填写广告信息发布广告，或是对已有的广告点击bid按钮进行竞标。用户可创建目录到top level或其子目录下，也可通过关键字查找广告或按广告的属性对广告进行排序查看。具体操作过程如下： 注册：在“Create Account”那一栏下填写用户名，email地址和密码然后点击“create”按钮即可，注意两次输入的密码必须匹配，否则会提示错误。 登陆：输入自己注册的email地址和密码，如果正确点击login按钮后即可 添加广告：用户进入登陆界面后，在Post and Ad一栏按提示填写广告的标题、数量等信息后，点击add按钮后便可将广告发布到左侧的广告列表中。 添加子目录：用户需在添加广告一栏的下面，选择母目录，然后在新目录文本框中输入新目录的名字，便可在选择的目录下创建新的目录。例如想要创建TopLevel/New这个目录，只要选择TopLevel然后在底下的新目录一栏输入New然后点击”Add subcategory”即可。 查找广告：在find按钮后的文本框中，输入想要查找的关键字，然后点击“find”按钮，即可筛选出题目或描述中包含此关键字的广告。也可点击“top only”按钮显示某一层目录的广告，以及点击Recursive按钮显示这层目录及其子目录所有的广告列表。 广告排序：在sort按钮旁的下拉菜单中，选择一种属性，然后点击sort按钮后，广告会按从小到大的顺序对广告进行排序。 竞标：用户选择要竞标的广告，点击“bid”按钮进入竞标页面，然后根据提示，输入竞标的数量和金额，然后点击submit按钮，如果竞标成功，即可在此广告的bid列表中找到自己的竞标。第三章 系统实现与调试重要函数算法说明：a. Date类重载”操作符，比较两个日期大小： 算法：对date的每个属性分三种情况判断，用一个flag变量标记，先判断年是否满足小于关系，如果是，则为true，否则在年相等的情况下再判断月，依次类推，如果年本身满足大于关系false，最后返回flase即可。关键代码如下：bool Date:operator (const Date &rhs)if(yearrhs.getYear() return true;else if(year=rhs.getYear() if(monthrhs.getMonth() return true;else if(month=rhs.getMonth() if(dayrhs.getDay() return true;else if(day=rhs.getDay() if(hourrhs.getHour() return true;else if(hour=rhs.getHour() if(minuterhs.getMinute() return true;else if(minute=rhs.getMinute() if(secondrhs.getSecond() return true;return false;复杂度：O(1)b. Group类重载，返回有特定email地址的用户指针： 算法：遍历objects集合，并判断集合中元素的email地址是否和传入的参数相同，如果相同返回此Client指针，否则返回null。关键代码如下： Client* Group:operator(const string& email)for(int i=0;igetEmail()=email)return objects.at(i);return 0; 复杂度：O(N)c. Advertisement类重载,从输入中读入信息给Advertisement属性赋值： 算法：用getline函数和stream为advertisement属性赋值，为了保证能将空格和回车全部保留，用一个while循环一行读body并用“”标签将结果进行连接，直到读到空行为止。关键代码如下：istream &operate(istream &stream, Advertisement &a)string str;Date dat;int qua;getline(stream,str);a.setTitle(str);streamstr;a.setEmail(str);streamqua;a.setQuantity(qua);streamdat;a.setStart(dat);streamdat;a.setClose(dat);streamstr;a.setBody(str);return stream; 复杂度：O(N)d. Category类的findOfferingsRecursive函数，用递归遍历子目录内容： 算法：递归调用findOfferingsRecursive和findOfferings，先用findOfferings找到本层目录中满足条件的广告加入到matches中， 然后再遍历子目录集合，调用自身函数将子目录中满足条件的广告加入到matches中。关键代码如下：void Category:findOfferingsRecursive (Listing:iterator start, Listing:iterator finish, Listing &matches)for(Listing:iterator is=start;is!=finish;is+)if(*is)-getNumber()=number)matches.add(*is);for(vector:iteratorss=sub_categories.begin();ss!=sub_categories.end();ss+)(*ss)-findOfferingsRecursive(start,finish,matches); 复杂度：O(N)e. Listing类的sort函数，通过使用stl的sort函数实现对广告的排序功能。 算法：定义四个内部函数，再定义sort函数的排序逻辑，然后在sort函数中，以函数指针作为参数传给sort函数。关键代码如下：bool lessQuantity(Advertisement* a,Advertisement* b) return a-getQuantity() getQuantity();bool lessStart(Advertisement* a,Advertisement* b) return a-getStart() getStart();bool lessClose(Advertisement* a,Advertisement* b) return a-getClose() getClose();bool lessEmail(Advertisement* a,Advertisement* b) return a-getEmail() getEmail();Listing Listing:sort(string field) Listing is(*this); if(field=email) std:sort( is.begin() , is.end() , lessEmail); if(field=Quantity) std:sort( is.begin() , is.end() , lessQuantity); if(field=Start) std:sort( is.begin() , is.end() , lessStart); if(field=Close) std:sort( is.begin() , is.end() , lessClose); return is; 复杂度：O(N)f. Listing类的filter函数，通过使用stl的find函数实现对广告的查找功能。 算法：总体思想是在所有的广告集合中找到包含输入关键字的广告，然后将之加入，从而显示满足条件的广告，最后返回这个列表。关键代码如下： Listing Listing:filter(string keyword) Listing is;for(int i=0;igetTitle().find(keyword);string:size_type i2 = objects.at(i)-getBody().find(keyword);if ( i1 != string:npos| i2 != string:npos)is.add(objects.at(i);return is; 复杂度：O(N)g. Advertisement类的getTopDutchBids函数，用以获得竞标成功的bid集合。 算法：竞标成功的bids是指按价位由高到低排，累积竞标的数量和大于等于广告商品本省的数量时停止。因此，需用一个result变量用以统计bids的竞标数量和，遍历广告本身已经排好序的bids集合，依次将bids内的bid出栈，并将出栈的bid数量加到result中，知道result的值大于等于广告的quantity为止，这时，一般情况会多加一个bid，也就是说多加的这个bid内的quantity值，加上前面的bid的quantity值会大于广告本身的quantity，也就是说，这个bid并不会得到它所要求的广告的数量，而是广告的quantity减去前面bid所有quantity剩下的值。关键代码如下：vector Advertisement:getTopDutchBids (void) constvector vb;priority_queue bid(bids);int all=number;while( !bid.empty() & all0)vb.push_back(bid.top();all-=bid.top().getQuantity();bid.pop();return vb; 复杂度：O(N)第4章 系统测试测试方法： 利用Apache运行程序，设置几组测试用例，分别考虑到一般情况和特殊情况，观察测试结果的正确性。测试用例（应该给出几组具有不同特征的数据进行测试）：Client名称