分类

课内:
不限
类型:
不限 毕业设计 课程设计 小学期 大作业
汇编语言 C语言 C++ JAVA C# JSP PYTHON PHP
数据结构与算法 操作系统 编译原理 数据库 计算机网络 软件工程 VC++程序设计
游戏 PC程序 APP 网站 其他
评分:
不限 10 9 8 7 6 5 4 3 2 1
年份:
不限 2018 2019

资源列表

  • 小型人员信息管理系统的设计与实现(控制台版本和MFC版本)

    摘 要现实生活中许多小型公司会用职工信息管理系统,通过应用电脑软件来对员工信息进行管理能够提高管理效率,使用Visual C++ 6.0的控制台工程和MFC工程分别实现了对员工信息的录入,更新,查看,以及保存。
    关键词:员工管理;职工信息;动态数组;MFC工程
    1 需求分析在日常生活工作中有很多地方需要用到信息管理,小型创业公司等都需要人工管理,这种情况下会有较高的错误率,并且信息易丢失,而采用电子信息进行存储与管理将会避免这个问题,能够大大提高管理信息准确性,提高企业效率。
    本系统需要实现对员工信息从文件中录入,并进行相关管理,进行数据更新,计算每个人的月薪,能够进行信息查询,信息存储到单独文件。
    2 算法基本原理2.1 数据读入从文件中分别读取经理,销售经理,兼职技术人员和兼职推销员的基本信息,使用ifstream类读取文件中的数据。通过判断文件指针是否指向文件尾来判断是否读取员工数据完成。
    2.2 数据存储员工数目是未知的,为了能够更合理的分配内存空间,使用vecotr类建立动态数组存储从文件中读取到的员工信息。
    对员工信息处理完成后,存储信息到磁盘使用ofstream类,建立文件流,实现对文件内容写入。
    2.3 数据计算经理的薪资为固定工资8000,销售经理的薪资为5000固定工资加所管辖部门的销售额的0.5%,兼职推销员的薪资为其当月销售额的4%,兼职技术人员的薪资为每小时100元。
    3 类设计3.1 类的概述本系统用到了员工类,员工类派生出经理类,销售经理类,兼职技术员类,兼职销售员类。员工类包含基础信息姓名,级别,工资等信息,能够实现信息打印,员工升级,保存信息到文件。
    经理类能够实现信息打印,保存信息到文件。
    销售经理类,新增部门销售额成员变量,计算工资,保存信息到文件的方法。兼职推销员类,新增销售额成员变量。
    兼职技术员类,新增工作时间类。
    3.2 类的接口设计/*******************************************************************//* 类定义 *//*******************************************************************///员工class Man{ public: string name; //姓名 int ID; //编号 int rank; //级别 double salary; //当月薪水 Man(string name); //构造函数 void print(); //输出函数 void SaveInfoToFile(); int UpRankTo(int newRank); //升级函数};class Manager: public Man //经理{ public: Manager(string name); //构造函数 void print(); void SaveInfoToFile();};class Salemanager: public Man //销售经理{ public: double salesum; //部门总销售额 Salemanager(string name, double salesum); //构造函数 void print(); void SetNewSalary(double salesum); void SaveInfoToFile();};class Saleman: public Man //兼职推销员{ public: double saleroom; //销售额 Saleman(string name, double saleroom); //构造函数 void print(); void SaveInfoToFile();};class Technologist: public Man //兼职技术员{ public: double workTime; //工作时间 Technologist(string name, double workTime); //构造函数 void print(); void SaveInfoToFile();};
    因为每个类的成员变量都不同,因此print方法都不同,而且由于每个类的信息要单独存放,因此每个类的SaveInfoToFile方法也不同。
    3.3 类的实现/*******************************************************************//* 类函数实现 *//*******************************************************************/static int count = 1000; //编号基础值1000 vector <Man*> man; //基础人员 vector <Manager*> mag; //经理 vector <Technologist*> tec; //技术员动态数组 vector <Salemanager*> slmag;//销售经理 vector <Saleman*> sl; //推销员Man::Man(string name) //基础类构造函数 { this->name = name; this->rank = 1; this->salary = 0; this->ID = count++;}void Man::print(){ cout << "id: " << this->ID; cout << " name: " << this->name; cout << " rank: " << this->rank; cout << " position: None\t"; cout << " salary: " << this->salary << endl;}int Man::UpRankTo(int rank) //升级函数 { int workTime, saleroom; if(rank == 1) //经理 { Manager *m = new Manager(this->name); mag.push_back(m); //入栈 this->rank = 4; } else if(rank == 2) //销售经理 { Salemanager *s = new Salemanager(this->name, 0); slmag.push_back(s); //入栈 this->rank = 3; } else if(rank == 3) //技术员 { cout << "输入他的工作时间:" ; cin >> workTime; Technologist *t = new Technologist(this->name, workTime); tec.push_back(t); //入栈 this->rank = 3; } else if(rank == 4) //推销员 { cout << "输入他的销售额:" ; cin >> saleroom; Saleman *t = new Saleman(this->name, saleroom); sl.push_back(t); //入栈 this->rank = 1; } else return 0; //错误 return 1; //成功升级 }Manager::Manager(string name):Man(name) //经理构造函数{ this->rank = 4; this->salary = 8000;}void Manager::print(){ cout << "id: " << this->ID; cout << " name: " << this->name; cout << " rank: " << this->rank; cout << " position: Manager\t"; cout << " salary: " << this->salary << endl;}void Manager::SaveInfoToFile() //保存信息到文件 { ofstream outfile; outfile.open("aaManager1.txt", ios_base::out | ios::app); //在文件尾插入新内容 outfile << "id: " << this->ID; outfile << " name: " << this->name; outfile << " rank: " << this->rank; outfile << " position: Manager\t"; outfile << " salary: " << this->salary << endl; outfile.close(); }Salemanager::Salemanager(string name, double salesum):Man(name) //销售经理构造函数{ this->rank = 3; this->salesum = salesum; this->salary = 5000 + 0.005 * salesum; //固定工资5000,提成0.005}void Salemanager::print(){ cout << "id: " << this->ID; cout << " name: " << this->name; cout << " rank: " << this->rank; cout << " position: Salemanager\t"; cout << " salary: " << this->salary; cout << " salesum: " << this->salesum << endl;}void Salemanager::SetNewSalary(double salesum) //根据部门销售额总和计算薪资 { this->salesum = salesum; this->salary = 5000 + 0.005 * salesum; //固定工资5000,提成0.005}void Salemanager::SaveInfoToFile() //保存信息到文件 { ofstream outfile; outfile.open("aaSalemanager1.txt", ios_base::out | ios::app); //在文件尾插入新内容 outfile << "id: " << this->ID; outfile << " name: " << this->name; outfile << " rank: " << this->rank; outfile << " position: Salemanager\t"; outfile << " salary: " << this->salary; outfile << " salesum: " << this->salesum << endl; outfile.close(); }Technologist::Technologist(string name, double workTime):Man(name)//技术员构造函数{ this->rank = 3; this->workTime = workTime; this->salary = workTime * 100; //每小时100元}void Technologist::print(){ cout << "id: " << this->ID; cout << " name: " << this->name; cout << " rank: " << this->rank; cout << " position: Technologist\t"; cout << " salary: " << this->salary; cout << " workTime: " << this->workTime << endl;}void Technologist::SaveInfoToFile() //保存信息到文件 { ofstream outfile; outfile.open("aaTechnologist1.txt", ios_base::out | ios::app); //在文件尾插入新内容 outfile << "id: " << this->ID; outfile << " name: " << this->name; outfile << " rank: " << this->rank; outfile << " position: Technologist\t"; outfile << " salary: " << this->salary; outfile << " workTime: " << this->workTime << endl; outfile.close(); }Saleman::Saleman(string name, double saleroom):Man(name) //推销员构造函数{ this->saleroom = saleroom; this->salary = 0.04 * saleroom;}void Saleman::print(){ cout << "id: " << this->ID; cout << " name: " << this->name; cout << " rank: " << this->rank; cout << " position: Saleman\t"; cout << " salary: " << this->salary; cout << " saleroom: " << this->saleroom << endl;}void Saleman::SaveInfoToFile(){ ofstream outfile; outfile.open("aaSaleman1.txt", ios_base::out | ios::app); //在文件尾插入新内容 outfile << "id: " << this->ID; outfile << " name: " << this->name; outfile << " rank: " << this->rank; outfile << " position: Saleman\t"; outfile << " salary: " << this->salary; outfile << " saleroom: " << this->saleroom << endl; outfile.close(); }
    4 基于控制台的应用程序4.1 主函数设计主函数又有几个功能,分别实现信息读取,信息存储,信息更新,获取所有信息,菜单操作几个功能。
    //信息读取函数void LoadInfo(){ ifstream infile; string name; int workTime; //技术员工作时间 int saleroom; //推销员月销售额 infile.open("Saleman.txt", ios::in); //打开推销员文件 while(infile >> name) //判断是不是到文件结尾 { infile >> saleroom; Saleman *t = new Saleman(name, saleroom); sl.push_back(t); //入栈 } infile.close(); infile.open("Technologist.txt", ios::in); //打开技术员文件 while(infile >> name) //判断是不是到文件结尾 { infile >> workTime; Technologist *t = new Technologist(name, workTime); tec.push_back(t); //入栈 } infile.close(); infile.open("Salemanager.txt", ios::in); //打开销售经理文件 while(infile >> name) //判断是不是到文件结尾 { Salemanager *t = new Salemanager(name, 0); slmag.push_back(t); //入栈 } infile.close(); infile.open("Manager.txt", ios::in); //打开经理文件 while(infile >> name) //判断是不是到文件结尾 { infile >> saleroom; Manager *t = new Manager(name); mag.push_back(t); //入栈 } infile.close();}//信息存储 void Store(){ for(int i = 0; i < sl.size(); i++) //推销员 sl.at(i)->SaveInfoToFile(); for(int i = 0; i < tec.size(); i++) //技术员 tec.at(i)->SaveInfoToFile(); for(int i = 0; i < slmag.size(); i++) //销售经理 slmag.at(i)->SaveInfoToFile(); for(int i = 0; i < mag.size(); i++) //经理 mag.at(i)->SaveInfoToFile(); }//信息更新 void UpData(){ double saleSum = 0; for(int i = 0; i < sl.size(); i++) //推销员 saleSum += sl.at(i)->saleroom; for(int i = 0; i < slmag.size(); i++) //销售经理 slmag.at(i)->SetNewSalary(saleSum);}//获取所有信息void GetAllInfo(){ for(int i = 0; i < sl.size(); i++) //推销员 sl.at(i)->print(); for(int i = 0; i < tec.size(); i++) //技术员 tec.at(i)->print(); for(int i = 0; i < slmag.size(); i++) //销售经理 slmag.at(i)->print(); for(int i = 0; i < mag.size(); i++) //经理 mag.at(i)->print(); }//菜单操作函数void menu(){ int cmd; static int updataFlag = 0; static int loadFlag = 0; cout << "1.Load 2.Updata 3.Dispaly 4.Store 0.Exit\n"; cin >> cmd; switch(cmd) { case 1: LoadInfo(); loadFlag = 1; //读取数据标志位置1 updataFlag = 0; //清空数据更新标志位 cout << "OK!\n"; break; case 2: if(loadFlag == 1) //判断是否已经读取数据 { UpData(); updataFlag = 1; //数据更新标志位置1 cout << "OK!\n"; } else cout << "Please Load First!\n"; break; case 3: if(loadFlag == 1) //判断是否已经读取数据 GetAllInfo(); else cout << "Please Load First!\n";break; case 4: if(updataFlag == 1) //判断是否已经更新数据(销售经理薪资) { Store(); cout << "OK!\n"; } else cout << "Please UpData First!\n"; break; case 0: exit(0); }}//主函数int main(){ cout << "Author\t:Liyi\nDate\t:20171222\nCopyright (C) 2017 Liyi. All Rights Reserved.\n\n\n"; while(1) menu(); return 0;}
    主函数中循环执行menu函数,通过用户输入的操作指令实现相应的功能。
    4.2 运行结果及分析
    能够正确读取文件信息,并做出相应的运算之后在进行文件信息写入。

    要注意的是先读取数据才能显示数据,先对数据更新才能进行数据保存。

    文件处理之前的文件内容,程序读取这些文件的内容信息。

    信息处理完之后存储的结果信息。
    5 基于MFC的应用程序MFC的图形界面程序设计可在上述类设计的基础上进行改造,MFC的图形界面程序与DOS界面程序的主要不同点是:MFC图形界面程序与DOS界面程序的输入输出方式不同,DOS界面程序采用字符交互式实现数据输入输出,主要通过cin,cout等I/O流实现,而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出,因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类,并通过图形界面的输入输出改造来完成。
    5.1 图形界面设计首先在VC中建立MFC AppWizard(exe)工程,名称为DD,并在向导的Step1中选择Dialog based,即建立基于对话框的应用程序,如图所示。


    将对话框资源中的默认对话框利用工具箱改造成如图所示界面。

    5.2 程序代码设计为了能够将对话框界面上的控件能够与代码联系起来,需要为Edit Box控件和Radio控件建立Member Variables,按Ctrl+w键进入MFC ClassWizard界面,选择Member Variables选项卡,可显示成员变量设置界面,如图所示。

    为了能够使按钮做出相应的响应,需要为按钮添加事件响应函数。

    如图所示,清除按钮事件响应函数是OnButtonClear(),确定按键响应函数是OnBUTTONqueding();
    下面是编写代码的重要阶段,可以借鉴在设计基于DOS界面的控制台应用程序的代码,并将其作必要的改写,具体改写内容如下。
    HCURSOR CDDDlg::OnQueryDragIcon(){ return (HCURSOR) m_hIcon;}void CDDDlg::OnRadioLoad() { // TODO: Add your control notification handler code here m_radio = 1;}void CDDDlg::OnRADIOxianshi() { // TODO: Add your control notification handler code here m_radio = 3;}void CDDDlg::OnRadioUpdata() { // TODO: Add your control notification handler code here m_radio = 2;}void CDDDlg::OnRadioStore() { // TODO: Add your control notification handler code here m_radio = 4; }void CDDDlg::OnBUTTONqueding() { // TODO: Add your control notification handler code here static int updataFlag = 0; static int loadFlag = 0; switch(m_radio) { case 1: LoadInfo(); loadFlag = 1; //读取数据标志位置1 updataFlag = 0; //清空数据更新标志位 MessageBox(_T("Load OK!")); break; case 2: if(loadFlag == 1) //判断是否已经读取数据 { UpData(); updataFlag = 1; //数据更新标志位置1 MessageBox(_T("Updata OK!")); } else MessageBox(_T("Please Load First!!")); break; case 3: if(loadFlag == 1) //判断是否已经读取数据 { UpdateData(true); m_edit = GetAllInfo().c_str(); UpdateData(false); } else MessageBox(_T("Please Load First!!"));break; case 4: if(updataFlag == 1) //判断是否已经更新数据(销售经理薪资) { Store(); MessageBox(_T("Store OK!")); } else MessageBox(_T("Please UpData First!!")); break; case 0: exit(0); }}void CDDDlg::OnButtonClear() //清除按钮{ // TODO: Add your control notification handler code here UpdateData(true); m_edit = ""; UpdateData(false); }void LoadInfo(){ ifstream infile; ifstream infile2; ifstream infile3; ifstream infile4; string name; int workTime; //技术员工作时间 int saleroom; //推销员月销售额 infile.open("Saleman.txt", ios::in); //打开推销员文件 while(infile >> name) //判断是不是到文件结尾 { infile >> saleroom; Saleman *t = new Saleman(name, saleroom); sl.push_back(t); //入栈 } infile.close(); infile2.open("Technologist.txt", ios::in); //打开技术员文件 while(infile2 >> name) //判断是不是到文件结尾 { infile2 >> workTime; Technologist *t = new Technologist(name, workTime); tec.push_back(t); //入栈 } infile2.close(); infile3.open("Salemanager.txt", ios::in); //打开销售经理文件 while(infile3 >> name) //判断是不是到文件结尾 { Salemanager *t = new Salemanager(name, 0); slmag.push_back(t); //入栈 } infile3.close(); infile4.open("Manager.txt", ios::in); //打开经理文件 while(infile4 >> name) //判断是不是到文件结尾 { infile4 >> saleroom; Manager *t = new Manager(name); mag.push_back(t); //入栈 } infile4.close(); }//信息存储 void Store(){ int i; for(i = 0; i < sl.size(); i++) //推销员 sl.at(i)->SaveInfoToFile(); for(i = 0; i < tec.size(); i++) //技术员 tec.at(i)->SaveInfoToFile(); for(i = 0; i < slmag.size(); i++) //销售经理 slmag.at(i)->SaveInfoToFile(); for(i = 0; i < mag.size(); i++) //经理 mag.at(i)->SaveInfoToFile(); }//信息更新 void UpData(){ int i; double saleSum = 0; for(i = 0; i < sl.size(); i++) //推销员 saleSum += sl.at(i)->saleroom; for(i = 0; i < slmag.size(); i++) //销售经理 slmag.at(i)->SetNewSalary(saleSum);} string GetAllInfo(){ int i; string re; for(i = 0; i < sl.size(); i++) //推销员 re += sl.at(i)->print(); for(i = 0; i < tec.size(); i++) //技术员 re += tec.at(i)->print(); for(i = 0; i < slmag.size(); i++) //销售经理 re += slmag.at(i)->print(); for(i = 0; i < mag.size(); i++) //经理 re += mag.at(i)->print(); return re;}// employee.h //类定义文件//#ifndef _EMPLOYEE_H#define _EMPLOYEE_H#include <iostream>#include <string> #include <sstream> //字符串流 #include <fstream> //文件操作 #include <vector> //动态数组 using namespace std;string itos(int i) // 将int 转换成string { stringstream s; s << i; return s.str(); } /*******************************************************************//* 类定义 *//*******************************************************************/class Man //员工 { public: string name; //姓名 int ID; //编号 int rank; //级别 double salary; //当月薪水 Man(string name); //构造函数 string print(); //输出函数 void SaveInfoToFile(); int UpRankTo(int newRank); //升级函数};class Manager: public Man //经理{ public: Manager(string name); //构造函数 string print(); void SaveInfoToFile();};class Salemanager: public Man //销售经理{ public: double salesum; //部门总销售额 Salemanager(string name, double salesum); //构造函数 string print(); void SetNewSalary(double salesum); void SaveInfoToFile();};class Saleman: public Man //兼职推销员{ public: double saleroom; //销售额 Saleman(string name, double saleroom); //构造函数 string print(); void SaveInfoToFile();};class Technologist: public Man //兼职技术员{ public: double workTime; //工作时间 Technologist(string name, double workTime); //构造函数 string print(); void SaveInfoToFile();};/*******************************************************************//* 类函数实现 *//*******************************************************************/static int count = 1000; //编号基础值1000 vector <Man*> man; //基础人员 vector <Manager*> mag; //经理 vector <Technologist*> tec; //技术员动态数组 vector <Salemanager*> slmag;//销售经理 vector <Saleman*> sl; //推销员Man::Man(string name) //基础类构造函数 { this->name = name; this->rank = 1; this->salary = 0; this->ID = count++;}string Man::print(){ string re; re = "id: " + itos(this->ID) + " name: " + this->name + " rank: " + itos(this->rank) + " position: None\t" + " salary: " + itos(this->salary) + "\r\n"; return re;}int Man::UpRankTo(int rank) //升级函数 { int workTime, saleroom; if(rank == 1) //经理 { Manager *m = new Manager(this->name); mag.push_back(m); //入栈 this->rank = 4; } else if(rank == 2) //销售经理 { Salemanager *s = new Salemanager(this->name, 0); slmag.push_back(s); //入栈 this->rank = 3; } else if(rank == 3) //技术员 { cout << "输入他的工作时间:" ; cin >> workTime; Technologist *t = new Technologist(this->name, workTime); tec.push_back(t); //入栈 this->rank = 3; } else if(rank == 4) //推销员 { cout << "输入他的销售额:" ; cin >> saleroom; Saleman *t = new Saleman(this->name, saleroom); sl.push_back(t); //入栈 this->rank = 1; } else return 0; //错误 return 1; //成功升级 }Manager::Manager(string name):Man(name) //经理构造函数{ this->rank = 4; this->salary = 8000;}string Manager::print(){ string re; re = "id: " + itos(this->ID) + " name: " + this->name + " rank: " + itos(this->rank) + " position: Manager\t" + " salary: " + itos(this->salary) + "\r\n"; return re;}void Manager::SaveInfoToFile() //保存信息到文件 { ofstream outfile; outfile.open("aaManager1.txt", ios_base::out | ios::app); //在文件尾插入新内容 outfile << "id: " << this->ID; outfile << " name: " << this->name; outfile << " rank: " << this->rank; outfile << " position: Manager\t"; outfile << " salary: " << this->salary << endl; outfile.close(); }Salemanager::Salemanager(string name, double salesum):Man(name) //销售经理构造函数{ this->rank = 3; this->salesum = salesum; this->salary = 5000 + 0.005 * salesum; //固定工资5000,提成0.005}string Salemanager::print(){ string re; re = "id: " + itos(this->ID) + " name: " + this->name + " rank: " + itos(this->rank) + " position: Salemanager\t" + " salary: " + itos(this->salary) + " salesum: " + itos(this->salesum) + "\r\n"; return re;}void Salemanager::SetNewSalary(double salesum) //根据部门销售额总和计算薪资 { this->salesum = salesum; this->salary = 5000 + 0.005 * salesum; //固定工资5000,提成0.005}void Salemanager::SaveInfoToFile() //保存信息到文件 { ofstream outfile; outfile.open("aaSalemanager1.txt", ios_base::out | ios::app); //在文件尾插入新内容 outfile << "id: " << this->ID; outfile << " name: " << this->name; outfile << " rank: " << this->rank; outfile << " position: Salemanager\t"; outfile << " salary: " << this->salary; outfile << " salesum: " << this->salesum << endl; outfile.close(); }Technologist::Technologist(string name, double workTime):Man(name)//技术员构造函数{ this->rank = 3; this->workTime = workTime; this->salary = workTime * 100; //每小时100元}string Technologist::print(){ string re; re = "id: " + itos(this->ID) + " name: " + this->name + " rank: " + itos(this->rank) + " position: Technologist\t" + " salary: " + itos(this->salary) + " workTime: " + itos(this->workTime) + "\r\n"; return re;}void Technologist::SaveInfoToFile() //保存信息到文件 { ofstream outfile; outfile.open("aaTechnologist1.txt", ios_base::out | ios::app); //在文件尾插入新内容 outfile << "id: " << this->ID; outfile << " name: " << this->name; outfile << " rank: " << this->rank; outfile << " position: Technologist\t"; outfile << " salary: " << this->salary; outfile << " workTime: " << this->workTime << endl; outfile.close(); }Saleman::Saleman(string name, double saleroom):Man(name) //推销员构造函数{ this->saleroom = saleroom; this->salary = 0.04 * saleroom;}string Saleman::print(){ string re; re = "id: " + itos(this->ID) + " name: " + this->name + " rank: " + itos(this->rank) + " position: Saleman\t" + " salary: " + itos(this->salary) + " saleroom: " + itos(this->saleroom) + "\r\n"; return re;}void Saleman::SaveInfoToFile(){ ofstream outfile; outfile.open("aaSaleman1.txt", ios_base::out | ios::app); //在文件尾插入新内容 outfile << "id: " << this->ID; outfile << " name: " << this->name; outfile << " rank: " << this->rank; outfile << " position: Saleman\t"; outfile << " salary: " << this->salary; outfile << " saleroom: " << this->saleroom << endl; outfile.close(); }#endif
    5.3 运行结果及分析




    需要先读取数据才能进行后续操作。

    需要先更新数据才能保存数据。
    结 论MFC程序与DOS界面程序编写的最大不同是程序员需要将编程精力放在图形界面设计、图形界面输入输出以及界面元素和代码对应转换等问题上,而这些问题在DOS界面程序中是不存在的,因此,初学MFC的编程者会对此感到困难,然而,当你编写出一个基于Windows界面的程序时,所获得的满足程度远远大于简单的DOS界面程序,况且基于Windows的图形界面的程序设计已成为主流,作为程序员而言,是非学会不可的。
    本次课程设计作为编写Windows程序的初步尝试,能够实现程序的主要功能,可以说是取得了成功,然而好的程序绝不仅仅是只有功能性这一个指标,本此编写的MFC程序虽然能实现所需功能,但从面向对象程序设计理念和图形界面设计要求来说,尚存在不足,主要包括以下几个方面:

    图形界面太过于简陋,没有良好的使用体验
    MFC程序中没有很好的使用其特有的数据类型,没有把MFC的性能发挥好
    DOS界面程序中对各个类的方法的工作效率没有做到很好的优化
    1 评论 9 下载 2018-11-05 18:28:08 下载需要10点积分
  • 基于Dijkstra算法的最短路径问题求解

    摘 要现实生活中许多数据的处理依赖于Dijkstra算法的应用,通过应用Dijkstra算法使复杂问题更加简单化。算法是以起始点为中心向外层层扩展,直到扩展到终点为止,最终求出最短路径。采用Visual C++ 6.0的控制台工程和MFC工程分别实现了Dijkstra的应用。
    关键词:Dijkstra算法;最短路径;MFC工程
    1 需求分析Dijkstra算法是由荷兰计算机科学家艾兹格•迪科斯彻发现的,算法解决的是有向图中最短路径问题。举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离。Dijkstra 算法可以用来找到两个城市之间的最短路径。
    Dijkstra算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。图中的每一个边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 假设E为所有边的集合,而边的权重则由权重函数w: E→[0,∞]定义。 因此,w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。 已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低花费路径(i.e.最短路径)。这个算法也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。
    如果将交通网络化成带权图,假如用顶点表示城市,边表示公路段,则由这些顶点和边组成的图可表示沟通个城市的公路图,边的权用以表示两个城市之间的距离或者表示走过这段公路所需要的时间或通过这段路的难易程度等。作为司机和乘汽车的人,自然会关心如下两个问题:

    从甲地到乙地是否有公路
    从甲地到乙地有几条公路,哪条公路最短或花费的代价最小

    这就是我们要讨论的最短路径问题。
    迪杰斯特拉提出的一个求最短路径的算法。其基本思想是:按路径长度递增的顺序,逐个产生各最短路径。
    首先引进辅助向量dist[],它的每一个分量dist[i]表示已经找到的且从源点v_0到每一个终点v_i的当前最短路径长度。它的初态为:如果从v_0到v_i有弧,则dist[i]为弧的权值;否则dist[i]为∞。其中,长度为dist[j]=min{dist[i]| v_i∈V}的路径是从v_0出发的长度最短的一条最短路径,此路径为(v_0,v_i)。
    2 算法基本原理根据以上分析,可以得到如下描述的算法:
    1.假设用带权的邻接矩阵arce[i][j]来表示带权有向图,arce[i][j]表示弧<v\_i, v\_j>上的权值。若<v\_i, v\_j>不存在,则置arce[i][j]为∞(在计算机上可用允许的最大值代替)。S为已找到的从v_0出发的最短路径的终点的集合,它的初始状态为空集。那么,从v_0出发到图上其余个顶点(终点)v_i可能达到的最短路径长度的初值为:
    dist[i]=arce[Locate Vex(G,v_0)][i] v_i∈S2.选择v_j得
    dist[j]=min{dist[i]| v_i∈V-S}v_j就是当前求得的一条从v_0出发的最短路径的终点。令S=S∪{j}。
    3.修改从v_0出发到集合V-S上任一顶点v_k可达的最短顶点长度。如果
    dist[j]+arce[j][k]<dist[k]则修改dist[k]为
    dist[k]=dist[j]+arce[j][k]4.重复操作2、3共n-1次。由此求得从v_0到图上其余各顶点的最短路径是依路径长度递增的序列。
    用Dijkstra算法求有向图G的v_0顶点到其余顶点v的最短路径P[v]及其带权长度D[v]。
    这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时,源点s的路径长度值被赋为0(d[s]=0),同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于V中所有顶点v除s外d[v]= ∞)。当算法结束时,d[v]中储存的便是从s到v的最短路径,或者是无穷大(如果路径不存在的话)。
    Dijstra算法的基础操作是边的拓展:如果存在一条从u到v的边,那么从s到v的最短路径可以通过将边(u,v)添加到s到u的尾部来拓展。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过适当的组织因而当d[u]达到它最终的值的时候,每条边(u,v)都只被拓展一次。
    算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点,而集合Q则保留其他所有顶点。集合S初始状态为空,而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中,算法对每条外接边(u,v)进行拓展。
    Dijkstra(G,D,s){ //用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度 S={s};D[s]=0; //设置初始的红点集及最短距离 for( all i∈ V-S )do //对蓝点集中每个顶点i D[i]=G[s][i]; //设置i初始的估计距离为w<s,i> for(i=0;i<n-1;i++)do{ //最多扩充n-1个蓝点到红点集 D[k]=min{D[i]:all i V-S}; //在当前蓝点集中选估计距离最小的顶点k if(D[k]=∞) return; //蓝点集中所有蓝点的估计距离均为∞时,表示这些顶点的最短路径不存 S=S∪{k}; //将蓝点k涂红后扩充到红点集 for( all j∈V-S )do //调整剩余蓝点的估计距离 if(D[j]>D[k]+G[k][j]) //新红点k使原D[j]值变小时,用新路径的长度修改D[j], //使j离s更近。 D[j]=D[k]+G[k][j]; } }
    3 类设计3.1 类的概述从上面的算法分析可以看到,根据算法设计了类class SPFA,public: int n;表示图里面的点数,public: int path[MAX][MAX];定义链接矩阵最多是1000个点,public: int dis[MAX];定义源点到其他点的距离,public: int src;定义源点,bool used[MAX]={false};定义点是否访问过了,初始化为未访问,初始化一下到各个点的距离,如果从k点走到j点的路很比原来的要短,那么更新,采用图的邻接矩阵或邻接表实现最短路径问题中图的存储,采用Dijkstra算法求从某个源点到其余各顶点的最短路径。

    第一步 先取W(v_1 )=0意即v_1到v_1的距离为0,而T(v_j)是对T(v_j)所赋的初值
    第二步 利用W(v_1 )已知,根据min{T(v_j ),W(v_1 )+w_ij }对T(v_j)进行修正
    第三步 对所有修正后的T(v_j)求出其最小者T(v_k)

    其对应的点v_k是v_1所能一步到达的点v_j中最近的一个,由于所有W(u)≥0。因此任何从其它点v_j中转而到达v_k的通路上的距离都大于v_1直接到v_k的距离T(v_k),因此T(v_k)就是v_1到v_k的最短距离,所以在算法中令W(v_k )=T(v_k)并从s中删去v_k,若k=n则W(v_k )=W(v_n)就是v_1到v_n的最短路线,计算结束。否则令v_i=v_k回到第二步,继续运算,直到k=n为止。
    这样每一次迭代,得到 到一点 的最短距离,重复上述过程直到v_k=v_n。
    Floyd算法的基本原理和实现方法为:如果一个矩阵D=[d_ij ]其中d_ij>0表示 与 间的距离,若i与j间无路可通,则d_ij为无穷大。i与j间的最短距离存在经过i与j间的k和不经过k两种情况,所以可以令k=1,2,3⋯,n,n(n为节点数)。检查d_ij与d_ik+d_kj的值,在此,d_ik与d_kj分别为目前所知的i到k与k到j的最短距离,在此d_ik+d_kj就是i到j经过k的最短距离。所以,若有d_ij> d_ik+d_kj,就表示从i出发经k再到j的距离要比原来的i到j距离短,自然把i到j的d_ij重写成d_ik+d_kj。每当一个k搜索完,d_ij就是目前i到j的最短距离。重复这一过程,最后当查完所有k时,d_ij就为i到j的最短距离。
    3.2 类的接口设计#include<iostream>using namespace std;const int MAX=1000;const int INF=1000000000;class SPFA{ public: int n; // 表示图里面的点数 public: int path[MAX][MAX]; // 定义链接矩阵最多是1000个点 public: int dis[MAX]; // 定义源点到其他点的距离 public: int src; // 定义源点经过公有派生
    在类的接口定义了图里面的点数,定义链接矩阵最多是1000个点,定义源点到其他点的距离,定义源点经过公有派生,这些变量int n,int path[MAX][MAX],int dis[MAX],int src都是public型。
    3.3 类的实现 public:void Cal() { int i,j,k; bool used[MAX]={false};//定义点是否访问过了,初始化为未访问 for(i=0;i<n;i++)//初始化一下到各个点的距离 { dis[i]=path[src][i]; } dis[src]=0; int min_=INF; for(i=0;i<n;i++) { k=-1; min_=INF; for(j=0;j<n;j++) { if(dis[j]<min_&&!used[j]) { min_=dis[j]; k=j; } } if(k==-1)//已经找不到有路可走的点 { return; } used[k]=true; for(j=0;j<n;j++) { if(!used[j]&&dis[j]>min_+path[k][j])//如果从k点走到j点的路很比原来的要短,那么更新 { dis[j]=min_+path[k][j]; } } } }};
    在类的成员函数实现过程中,设计了几个循环语句,和判断语句,定义点是否访问过了,初始化为未访问,初始化一下到各个点的距离,已经找不到有路可走的点
    if(!used[j]&&dis[j]>min_+path[k][j])//如果从k点走到j点的路很比原来的要短,那么更新
    4 基于控制台的应用程序4.1 主函数设计int main(){//按照下面的数据格式输入,-1表示没有路,自己到自己是0/*30 -1 -13 0 -13 4 030 100 13 0 -13 4 030 1 23 0 -13 4 0*/ SPFA* a=new SPFA(); cout<<"请输入点数:"; cin>>a->n; int i,j; for(i=0;i<a->n;i++) { for(j=0;j<a->n;j++) { cin>>a->path[i][j]; if(a->path[i][j]==-1) { a->path[i][j]=INF; } } } a->src=0;//源点暂时定为0 a->Cal(); for(i=0;i<a->n;i++) { cout<<"dis["<<i<<"]"<<a->dis[i]<<endl; } return 0;}
    在程序的主函数部分,可以显示”请输入点数:”输入一个邻接矩阵,a->src=0;//源点暂时定为0,然后通过循环语句,调用类中的函数,算出最短路径。
    4.2 运行结果及分析程序初始化运行的结果如图1所示。从图1中可以看出通过将有向图的邻接矩阵的输入,求出最短路径。

    分析:
    整个程序中的矩阵存储采用的是一维数组和动态内存分配方式。通过此类定义链接矩阵,采用图的邻接矩阵或邻接表实现最短路径问题中图的存储,然后通过主函数main调用class来实现,采用Dijkstra算法求从某个源点到其余各顶点的最短路径。
    5 基于MFC的应用程序MFC的图形界面程序设计可在上述类设计的基础上进行改造,MFC的图形界面程序与DOS界面程序的主要不同点是:MFC图形界面程序与DOS界面程序的输入输出方式不同,DOS界面程序采用字符交互式实现数据输入输出,主要通过cin,cout等I/O流实现,而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出,因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类,并通过图形界面的输入输出改造来完成。
    5.1 图形界面设计首先在VC中建立MFC AppWizard(exe)工程,名称为GassineGU,并在向导的Step1中选择Dialog based,即建立基于对话框的应用程序,如图2~3所示。


    将对话框资源中的默认对话框利用工具箱改造成如图4所示界面。

    图4所示的界面中包含了3个Static Text控件,1个Button控件,和20个Edit Box控件,控件的基本信息列表如下表1所示。



    控件类别
    控件ID
    控件Caption
    说明




    Static Text
    IDC_STATIC
    邻接矩阵: 最短路径为: (源点为1)















    Botton
    IDC_BUTTON_CALC
    最短路径



    Edit Box
    IDC_EDIT_A00~ IDC_EDIT_A15

    有向图的邻接矩阵


    IDC_EDIT_b0~ IDC_EDIT_b3

    源点到每个顶点的最小路径



    5.2 程序代码设计为了能够将对话框界面上的控件能够与代码联系起来,需要为2个Edit Box控件建立Member Variables,按Ctrl+w键进入MFC ClassWizard界面,选择Member Variables选项卡,可显示成员变量设置界面,如图5所示。

    下面是编写代码的重要阶段,可以借鉴在设计基于DOS界面的控制台应用程序的代码,并将其作必要的改写,具体改写的步骤与内容如下。
    // 123Dlg.cpp : implementation file//#include "stdafx.h"#include "123.h"#include "123Dlg.h"#include "SPFA.h"#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE[] = __FILE__;#endif/////////////////////////////////////////////////////////////////////////////// CAboutDlg dialog used for App Aboutclass CAboutDlg : public CDialog{public: CAboutDlg();// Dialog Data //{{AFX_DATA(CAboutDlg) enum { IDD = IDD_ABOUTBOX }; //}}AFX_DATA // ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CAboutDlg) protected: virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support //}}AFX_VIRTUAL// Implementationprotected: //{{AFX_MSG(CAboutDlg) //}}AFX_MSG DECLARE_MESSAGE_MAP()};CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD){ //{{AFX_DATA_INIT(CAboutDlg) //}}AFX_DATA_INIT}void CAboutDlg::DoDataExchange(CDataExchange* pDX){ CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CAboutDlg) //}}AFX_DATA_MAP}BEGIN_MESSAGE_MAP(CAboutDlg, CDialog) //{{AFX_MSG_MAP(CAboutDlg) // No message handlers //}}AFX_MSG_MAPEND_MESSAGE_MAP()/////////////////////////////////////////////////////////////////////////////// CMy123Dlg dialogCMy123Dlg::CMy123Dlg(CWnd* pParent /*=NULL*/) : CDialog(CMy123Dlg::IDD, pParent){ //{{AFX_DATA_INIT(CMy123Dlg) m_e1 = 0.0; m_e10 = 0.0; m_e11 = 0.0; m_e12 = 0.0; m_e13 = 0.0; m_e14 = 0.0; m_e15 = 0.0; m_e16 = 0.0; m_e17 = 0.0; m_e18 = 0.0; m_e19 = 0.0; m_e2 = 0.0; m_e3 = 0.0; m_e4 = 0.0; m_e5 = 0.0; m_e6 = 0.0; m_e7 = 0.0; m_e8 = 0.0; m_e9 = 0.0; m_e20 = 0.0; //}}AFX_DATA_INIT // Note that LoadIcon does not require a subsequent DestroyIcon in Win32 m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);}void CMy123Dlg::DoDataExchange(CDataExchange* pDX){ CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CMy123Dlg) DDX_Text(pDX, IDC_EDIT1, m_e1); DDX_Text(pDX, IDC_EDIT10, m_e10); DDX_Text(pDX, IDC_EDIT11, m_e11); DDX_Text(pDX, IDC_EDIT12, m_e12); DDX_Text(pDX, IDC_EDIT13, m_e13); DDX_Text(pDX, IDC_EDIT14, m_e14); DDX_Text(pDX, IDC_EDIT15, m_e15); DDX_Text(pDX, IDC_EDIT16, m_e16); DDX_Text(pDX, IDC_EDIT17, m_e17); DDX_Text(pDX, IDC_EDIT18, m_e18); DDX_Text(pDX, IDC_EDIT19, m_e19); DDX_Text(pDX, IDC_EDIT2, m_e2); DDX_Text(pDX, IDC_EDIT3, m_e3); DDX_Text(pDX, IDC_EDIT4, m_e4); DDX_Text(pDX, IDC_EDIT5, m_e5); DDX_Text(pDX, IDC_EDIT6, m_e6); DDX_Text(pDX, IDC_EDIT7, m_e7); DDX_Text(pDX, IDC_EDIT8, m_e8); DDX_Text(pDX, IDC_EDIT9, m_e9); DDX_Text(pDX, IDC_EDIT20, m_e20); //}}AFX_DATA_MAP}BEGIN_MESSAGE_MAP(CMy123Dlg, CDialog) //{{AFX_MSG_MAP(CMy123Dlg) ON_WM_SYSCOMMAND() ON_WM_PAINT() ON_WM_QUERYDRAGICON() ON_BN_CLICKED(IDC_BUTTON1, OnButton1) //}}AFX_MSG_MAPEND_MESSAGE_MAP()/////////////////////////////////////////////////////////////////////////////// CMy123Dlg message handlersBOOL CMy123Dlg::OnInitDialog(){ CDialog::OnInitDialog(); // Add "About..." menu item to system menu. // IDM_ABOUTBOX must be in the system command range. ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX); ASSERT(IDM_ABOUTBOX < 0xF000); CMenu* pSysMenu = GetSystemMenu(FALSE); if (pSysMenu != NULL) { CString strAboutMenu; strAboutMenu.LoadString(IDS_ABOUTBOX); if (!strAboutMenu.IsEmpty()) { pSysMenu->AppendMenu(MF_SEPARATOR); pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu); } } // Set the icon for this dialog. The framework does this automatically // when the application's main window is not a dialog SetIcon(m_hIcon, TRUE); // Set big icon SetIcon(m_hIcon, FALSE); // Set small icon // TODO: Add extra initialization here return TRUE; // return TRUE unless you set the focus to a control}void CMy123Dlg::OnSysCommand(UINT nID, LPARAM lParam){ if ((nID & 0xFFF0) == IDM_ABOUTBOX) { CAboutDlg dlgAbout; dlgAbout.DoModal(); } else { CDialog::OnSysCommand(nID, lParam); }}// If you add a minimize button to your dialog, you will need the code below// to draw the icon. For MFC applications using the document/view model,// this is automatically done for you by the framework.void CMy123Dlg::OnPaint() { if (IsIconic()) { CPaintDC dc(this); // device context for painting SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0); // Center icon in client rectangle int cxIcon = GetSystemMetrics(SM_CXICON); int cyIcon = GetSystemMetrics(SM_CYICON); CRect rect; GetClientRect(&rect); int x = (rect.Width() - cxIcon + 1) / 2; int y = (rect.Height() - cyIcon + 1) / 2; // Draw the icon dc.DrawIcon(x, y, m_hIcon); } else { CDialog::OnPaint(); }}// The system calls this to obtain the cursor to display while the user drags// the minimized window.HCURSOR CMy123Dlg::OnQueryDragIcon(){ return (HCURSOR) m_hIcon;}void CMy123Dlg::OnButton1() { UpdateData(TRUE); SPFA* a=new SPFA(); //变量初始化 a->path[0][0] = m_e1; a->path[0][1] =m_e2; a->path[0][2] = m_e3; a->path[0][3] = m_e4; a->path[1][0] = m_e5; a->path[1][1] = m_e6; a->path[1][2] = m_e7; a->path[1][3]=m_e8; a->path[2][0] = m_e9; a->path[2][1] = m_e10; a->path[2][2] = m_e11; a->path[2][3] = m_e12; a->path[3][0]= m_e13; a->path[3][1]= m_e14; a->path[3][2]= m_e15; a->path[3][3]=m_e16; a->src=0; a->Cal(); m_e17=a->dis[0]; m_e18=a->dis[1]; m_e19=a->dis[2]; m_e20=a->dis[3]; UpdateData(FALSE); // TODO: Add your control notification handler code here}
    5.3 运行结果及分析运行程序后,首先出现的界面如图6所示。

    输入临接矩阵的数据后,可将临接矩阵数据在界面上显示出来,如图7所示。

    单击最短路径按钮,实现算法并将最短路径显示出来,如图8所示。

    结 论Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法
    Dijkstra算法的本质思想是: 按路径长度递增依次产生最短路径。
    Dijkstra算法大致流程如下:

    初始化所有结点并将起始点设为标记,进入以下循环
    在到达某点的最短路径中找最小且未标记的点(可以用一维数组表示)
    标记找到的点,以此标记点为中间点重新计算所有未标记点的最短路径(更新最短路径表)
    循环1.2步至n-1次(n为顶点数,若最后还有未被标记的,说明无法到达此点)

    MFC程序与DOS界面程序编写的最大不同是程序员需要将编程精力放在图形界面设计、图形界面输入输出以及界面元素和代码对应转换等问题上,而这些问题在DOS界面程序中是不存在的,因此,初学MFC的编程者会对此感到困难,然而,当你编写出一个基于Windows界面的程序时,所获得的满足程度远远大于简单的DOS界面程序,况且基于Windows的图形界面的程序设计已成为主流,作为程序员而言,是非学会不可的。
    本次课程设计作为编写Windows程序的初步尝试,能够实现程序的主要功能,可以说是取得了成功,然而好的程序绝不仅仅是只有功能性这一个指标,本此编写的MFC程序虽然能实现所需功能,但从面向对象程序设计理念和图形界面设计要求来说,尚存在不足,主要包括以下几个方面。

    使用全局变量存储邻接矩阵、输入加权值的数据
    将类的定义与实现放在同一个头文件class中也违背了面向对象程序设计理念,需要将二者分开成定义文件和实现文件
    输入邻接矩阵,显示最短路径

    参考文献[1] 谭浩强.C++基础入门大全.北京:清华大学出版社,2012:100-102
    [2] 郑莉,董渊,张瑞丰.C++语言程序设计(第3版).北京:清华大学出版社,2007:25-60
    [3] 钱能.C++程序设计教程(第2版).北京:清华大学出版社,2007:100-130
    [4] 陈志泊,王春玲. 面向对象的程序设计语言—C++. 北京:人民邮电出版社,2002
    [5] 李庆扬,王能超,易大义. 数值分析. 湖北:华中理工大学出版社,1986
    1 评论 6 下载 2018-11-05 18:19:18 下载需要7点积分
  • 基于时空数据分析的决策支持报告

    概 述本人完成了出租车经营策略研究中的基础分析、原地待命策略、低速巡游策略和选作中的城市POI分析与推荐。工程代码在压缩包的DSpj文件夹内。相关数据在data文件夹内。
    一、环境说明
    GUN GCC Compiler
    Code::Blocks 13.12
    Windows10 64bit

    二、算法与数据结构介绍2.1 geohash算法将经纬度hash成一个long long。算法流程如下,比如(120, 30) 范围精度是0-180 唯独是0-90:
    120>=(0+180)/2 故h[0]=1 30<=(0+90)/2 h[1]=0120<=(90+180)/2 h[2]=0 30>=(0+45)/2 h[3]=1120>=(90+135)/2 h[4]=1 30<=(22.5+45)/2 h[5]=0以此类推二分得到每个坐标唯一的hash值。
    因为用了64位,所以可以保证每个点的hash是唯一的。所以用这个确实可以查到最近的点,唯一的cheat是在分割线附近,比如经度90和经度89.9999999会有很大差别。但在线上的点很少,而且这种情况依然能查询到另外一边的最近的点,所以我觉得geohash非常适合这个pj。
    这个算法的优点是代码简单且容易维护,准确度高速度快。缺点是分割线上不能保证最优解。但大部分情况有最优解,极小部分有较优解。
    验证发现在前四十层分割线上1e-5范围内只有437个点
    空间复杂度O(nlogn)
    查询复杂度O(logn*E) E为从最hash值最接近的E个点找最近点。
    2.2 A*搜索算法A*搜索用于求指定起点和终点的最短路。估价函数采用当前点到终点的欧几里德距离。实现上用优先队列来弹出 到起点距离+估价值 最小的点,之后把所有相邻点插入优先队列。
    这里给大家介绍一种双向A*的算法。

    对于这张图,从起点到终点要跑大量的无关格子,但如果从终点到起点呢?

    可以看出这种数据终点到起点跑得非常快,这种数据大概属于起点附近的图比较稠密,终点附近的图比较稀疏。
    这里也可以看出如果两个点在河的两端,桥在较远的地方,A*算法会退化成类似BFS。这也提醒我们如果追求速度的话可以基于图的类型设计不同的算法。
    还有可以用动态调整的策略,我们发现离目标点远的时候算短距离很重要,近的时候就没那么在意距离了。
    f(s)=real(s)+predict(s)*w(s) real是当前距离,predict是估计距离,w是权重,离目标越近权重越小。
    另外我们发现对于距离近的点对dijkstra很快 远的很慢。考虑双向搜索中一边用A*,另外一边在终点附近用dijkstra? 还有就是可以从大量经过起点和终点的订单轨迹中提取出关键点,从关键点往两个方向搜索最短路。
    2.3 计算几何用叉积和面积等基础知识求点到线段的距离。但经度和纬度并不是严格意义上的二维平面。需要经过转换。
    2.4 平衡树大量的数据使用平衡树维护,比如根据hash值来查找点。实现上直接使用了stl的map。
    2.5 排序算法快速排序。
    三、一些功能的实现3.1 GPS偏移//找到离p点最近的边(a,b)pair<int,int> findNearestRoad(pair<double,double> p);
    根据p点的hash值在map中查询hash值最接近的20个点。遍历这20个点的所有边,找到离p点最近的边,返回边两头的点编号。
    3.2 坐标转换理论上应该把经纬度坐标映射到x, y坐标。以确保点到线段距离的正确性。实践中发现经纬度乘上某些常数映射后与直接把经纬度当作x, y坐标影响肉眼不可见。
    3.3 司机找最近订单int getNearestorder(pair<double,double> pos,Road &road,Order &order);
    给出位置,找最近的订单。实现上先将司机的位置哈希得到_hash。在所有当前订单起点哈希值构成的平衡树中查找_hash.将_hash附近的40个订单取出。按照他们与司机的距离排序,返回最近的订单。
    3.4 维护当前订单把订单按时间排序,每次单调的把当前时刻前的订单插入map。(key为起点位置,value为订单编号)
    3.5 模拟等待策略void lowStrategy(Order &order,Road &road);
    先得到司机的初始位置,初始时间。然后查找最近的订单,如果在三公里内的话,接上乘客并驶向目的地。否则找到司机位置和最近订单的最短路。每走过一条路并且距离上次查询时间大于300秒,则查询最近订单,若小于三公里,则接单,否则继续跑。
    3.6 路口对接路网的构建中有些路是同一个端点,但经纬度有少许偏移。做法是在建立路网的过程中把点的坐标*10000去整看待来辨别是否相同。
    四、必做部分4.1 模拟司机订单这个任务涉及到大规模的数据处理,我们用遍历字符串的方式把所有提供的数据都存在了数据类型State中。对于每个司机,他的每个状态之间的距离就是他的行驶距离,每次顶灯亮起的状态则是载客状态,可以求得载客距离。之后输出每个司机的收入,支出,利润即可。

    x坐标是收入范围,y坐标是司机数目,可以看出收入在600-700

    4.2 模拟原地待命策略先把所有司机在每个时段的第一个时间点的位置提取出来。如上文所提到的实现即可。注意要删除已经接到的单避免重复刷单(如果点对很近的话可以刷起步价)。对于不连通的点对,直接直线到达。
    这是四个时段的收入分布

    4.3 模拟低速巡游策略如上文所提到的实现即可。注意如果和最近订单之间没有路的话,删除该订单并换一个订单。

    五、选作部分(城市POI分析与推荐)5.1 POI估价通过geohash用类似找最近订单(找最近的点)的方法找到poi附近的所有上车点和下车点,如果在两公里以内则估价+1,在500以内估价+3。
    实践中发现如人民广场这样的餐厅密集的地方无法把这些餐厅做一个区分。考虑把人流量除以餐厅数量,发现效果一般。因为在人民广场附近你还是要推人民广场的餐厅的吧。
    5.2 推荐估价void POI::Introduce(pair<double,double> p,Road &road)
    通过geohash找到离查询点p最近的100个poi。将距离和他们的估价作为参数,得到一个score。把score最高的20个poi推送出来。
    参数我调了一会儿大概就是500米内和两公里内有小幅加成。因为这个查询数量较少可以把poi数扩展到10000个甚至100000个。

    6 实例分析我们来选取几个例子来推荐餐厅。
    下述都是张江附近人气比较高的餐厅:


    下述是邯郸附近人气比较高的餐厅:


    下述是江湾附近人气比较高的餐厅:


    下述是外滩附近人气比较高的餐厅:

    1 评论 4 下载 2018-11-05 18:14:20 下载需要6点积分
  • 基于C#实现并对比三种基本的字符串匹配算法-RK算法-KMP算法-朴素算法

    1 需求分析1.1 系统目标
    实现题目说所要求的三种匹配算法的算法设计,算法实现,程序能够稳定,准确的运行并实现字符串匹配的功能,做出相应的窗体界面程序
    分析完成三种算法的时间复杂度,通过程序实验实现三种算法之间用时的比较
    按时撰写完成课程设计的文档和进度表
    优化设计程序的健全度和用户体验

    1.2 系统功能需求
    文本的输入选择功能

    可以选择键入英文文本或者从文件中读入英文文本
    错误检查功能

    可以检查输入的英文文本以及输入的模式串中是否有非英文文本字符,如果有提示修改并重新输入
    字符串匹配算法选择功能

    提供朴素算法、Rabin-Karp算法、KMP算法,3种算法进行比较这四个选择
    重复匹配功能

    如果文本中多次出现需要匹配的模式串,输出重复出现的次数,以及每次在主串中匹配成功的初始位置
    时间的计算和比较

    选择一种算法匹配,如果匹配成功,输出该算法匹配成功所花费的时间,如果匹配失败,则输出匹配失败。选择3种算法比较,如果匹配成功,输出3种算法匹配成功耗时和耗时最长和最短的算法的名字,如果匹配失败,则输出匹配失败
    显示文本功能

    匹配之后会显示每次在主串中匹配成功的位置,点击位置,会弹出文本框,显示匹配上的位置

    1.3 系统关键技术
    hash散列法。Rabin-Karp 算法的实现原理需要用到hash散列法,将所有的字符分别映射到(0.1.2…n)中。文本的匹配转换成数字的匹配,文本字符串右移通过减去最高位,乘上进制数,再加上下一位字符对应的hash值,实现巧妙的右移
    在RK算法中会出现一个问题,一旦模式串的长度过大,减去最高位,乘上进制数,再加上下一位字符对应的hash值,实现右移的时候有可能会溢出,使得该算法失效,于是使用求余的方法来解决,mod一个比较合适的质素,可以避免其溢出
    KMP的关键以及精华在于next数组。Next[i] = j 表示0…j-1与i-j ….i-1这两段匹配串是相同的。Next数组的定义为Next[0] = -1,Next[1] = 0;接下来的Next都通过递推的方式求出。

    2 算法设计2.1 系统整体思路由于选题原因,开发设计从三个方面分别进行,分别是:朴素匹配算法的设计和实现,KR算法的设计和实现,KMP算法的设计和实现。
    2.2 关键数据结构设计顺序结构存储字符串,next数组。
    2.3 朴素算法2.3.1 算法基本思想将主串S中某个位置i起始的子串和模式串P相比较。即从 j=0 起比较 S[i+j] 与 P[j],若相等,则在主串 S 中存在以 i 为起始位置匹配成功的可能性,继续往后比较( j逐步增1 ),直至与P串中最后一个字符相等为止,否则改从S串的下一个字符起重新开始进行下一轮的”匹配”,即将串T向后滑动一位,即 i 增1,而 j 退回至0,重新开始新一轮的匹配。
    2.3.2 算法流程图
    2.4 Rabin-Karp算法2.4.1 算法基本思想预处理长度与模式串长度相同的主串长度,每一字符哈希映射对应0…N中的一个。根据所在的位乘上相应的进制数相加成一个整型数。匹配转换成两个整型数的比较,如果两个整型数相等,说明他们哈希值相同,有可能是相同的串,于是深入匹配这两段串,如果匹配失败,模式串往后移开始新一轮的匹配。
    2.4.2 算法流程图
    2.5 KMP算法2.5.1 算法基本思想用模式串预处理Next数组,Next[i] = j 表示0…j-1与i -j -1….i-1这两段匹配串是相同的。每次匹配失败后,模式串并不是直接重头开始,而是从Next数组里找出起始位置,这样减少了不必要的匹配,节省了时间。
    2.5.2 算法流程图
    3 算法实现3.1 开发语言及工具
    开发语言:C#
    开发工具:visual studio

    3.2 算法关键代码3.2.1 朴素算法关键代码将主串S中某个位置i起始的子串和模式串P相比较。即从 j=0 起比较 S[i+j] 与 P[j],若相等,则在主串 S 中存在以 i 为起始位置匹配成功的可能性,继续往后比较( j逐步增1 ),直至与P串中最后一个字符相等为止,否则改从S串的下一个字符起重新开始进行下一轮的”匹配”,即将串T向后滑动一位,即 i 增1,而 j 退回至0,重新开始新一轮的匹配。
    匹配部分的代码:

    3.2.2 Rabin-Karp算法关键代码预处理最高位和主串哈希值以及模式串哈希值的代码。
    预处理长度与模式串长度相同的主串长度,每一字符哈希映射对应0…N中的一个。根据所在的位乘上相应的进制数相加成一个整型数。

    匹配转换成两个整型数的比较,如果两个整型数相等,说明他们哈希值相同,有可能是相同的串,于是深入匹配这两段串,如果匹配失败,模式串往后移开始新一轮的匹配,以为通过主串减去最高位,乘上进制数再加上最低位。

    3.2.3 KMP算法关键代码预处理next数组的代码。
    通过递推往下求next数组,当p[i] == p[k] 则说明p[0..k] == p[i-k..i],于是就有next[i+1] = k+1;

    每次匹配失败后,模式串并不是直接重头开始,而是从Next数组里找出起始位置,这样减少了不必要的匹配,节省了时间。

    3.3 主要功能界面3.3.1 文本输入的选择功能可以选择从文件中导入英文文本,或者手动输入英文文本。

    选择从文件中导入后的界面

    选择手动输入后的界面

    3.3.2 错误检查功能检查输入的文本和匹配字符串中是否有非英文字符,若有,则提示出错。


    3.3.3 字符串匹配算法选择功能可以选择相应的算法进行字符串匹配。

    3.3.4 重复匹配功能当匹配字符串在文本中多次出现,则输出匹配成功的次数,和每次匹配成功的起始位置。


    若匹配失败,则输出匹配失败。


    3.3.5 时间的计算和比较选择单独是算法,则是输出第一次匹配成功所花费的时间。


    选择3种算法进行比较,则输出3种匹配所花费的时间和匹配耗时最多和最少的算法名称。


    3.3.6 显示文本功能
    点击下面的数字,可以显示匹配上的串在文本中的位置。

    4 算法分析4.1 算法复杂性分析4.1.1 朴素算法朴素的字符串匹配过程可以形象的看成一个包含模式的“模板”P沿文本T移动,同时对每个位移注意模板上的字符是否与文本中的相应字符相等。外层循环的次数最多为len(s) - len(p),内层循环的次数最多为len(p),最坏情况下的时间复杂度:O((len(T) - len(P) + 1) * len(P))。
    4.1.2 Rabin-Karp算法Horner法则p = p[m] + 10(p[m -1] + 10(p[m-2]+…+10(p[2]+10p[1])…)),求出模式字符串的哈稀值p,而对于文本字符串来说,对应于每个长度为m的子串的 哈稀值为t(s+1)=10(t(s)-10^(m-1)T[s+1])+T[s+m+1],然后比较此哈稀值与模式字符串的哈稀值是否相等,若不相同, 则字符串一定不同,若相同,则需要进一步的按位比较,所以它的最坏情况下的时间复杂度为O(mn)。
    4.1.3 KMP算法KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。
    4.2 算法优缺点分析4.2.1 朴素算法的优缺点
    优点:朴素算法简单易懂,代码容易实现
    缺点:时间复杂度太高,字符串和英文文本中连续相同的子串太多的时候花费时间比较大

    4.2.2 Rabin-Karp算法优缺点
    优点:思路新颖,用hash映射后的值进行字符串匹配,巧妙移位,代码不难实现
    缺点:因为用到hash,会出现冲突,进行多次不必要的深度匹配,浪费了时间。进制数和质素需要适当的选取

    4.2.3 KMP算法的优缺点
    优点:运用next数组很快的找到匹配失败后应该重新匹配的启示位置,而不是重头再来。节省了时间
    缺点:求next数组需要一定的时间开销

    总的来说,字符串和英文文本有较少的连续相同子串的时候,朴素是不错的选择,这个时候朴素的时间可以接近o(n),而Rabin-Karp和KMP都需要启动时间,就有可能比朴素慢。当字符串和英文文本有较多的连续相同子串的时候,KMP是个不错的选择,他的next数组就能很好的解决匹配失败后字符串该从哪里开始的问题,使时间接近于o(n)。而这时候朴素的复杂度是接近o(n^2)的。RK算法适合较长的英文文本匹配,这样可以忽略他的启动时间,文本较短的时候会跑不过朴素,重复较多的常文本也许会跑不过KMP,其他请客都比这两个算法要快。
    5 项目总结经过了一个月的努力,终于成功的完成了整个项目系统。一开始对RK,KMP算法的一无所知,在查阅了大量资料,翻阅了许多博客后,学会了这些算法,并且知道了这些算法的优缺点和适合在什么场合使用。小组三人分工合作,让我们体会到了在完成项目的过程中合作的难度和重要性。
    同时,在代码初步完成后,我们进行了大量的测试工作,我们曾经以为KMP算法不管在什么情况下都是耗时最少的,朴素算法不管在什么情况下都是耗时最多的,RK算法则处于两者之间。测试后我们发现我们错了,每种算法在不同的情况下会有不同的效果,并没有绝对的谁会最快,谁会最慢,测试工作完成后,发现命令行操作界面并不美观,也不适合广大用户,于是我们对用户体验进行优化,做了一个系统界面,把所有的功能都实现,方便用户使用。
    在这一过程中,我们发现了大量的不足,同时也了解到要完成一个健壮性极强,用户体验很好的软件需要些什么。经过许多讨论和修改,最终完成了界面的制作。总之,在这次课程设计中,我们不仅学会了新的算法,还了解了算法的本质,学会对算法进行纵向比较,也学会了如何完成一个优秀的软件。总之,收获良多。
    1 评论 2 下载 2018-11-05 18:07:17 下载需要5点积分
  • 基于easyx实现的小蓝鲸跑酷游戏

    1 游戏介绍本程序是一款以“小蓝鲸”为主角的跑酷游戏。本游戏通过操作 “w”、“s” 或方向键 “↑”、“↓” 控制小蓝鲸上浮下潜以躲避海底障碍物,在水面上时按“空格键”可以让小蓝鲸跳跃以越过岛屿,游戏过程中小蓝鲸存活时间越久得分越高。与此同时,小蓝鲸吃到鱼可以获得加分或者无敌。难度方面共设计了四个难度,难度乘以时间决定最终的总分。除了游戏部分之外,玩家还可以查看规则及团队介绍。
    本程序设计灵感来源于《flappy bird》,但实际上程序设计思路完全是团队原创。玩家在游戏中还能发现许多亮点,如千奇百怪的障碍物、奖励设置、跳跃操作、小蓝鲸吐槽等,界面精美,可玩性高,是一款操作简易娱乐性强的游戏。
    2 数据结构本程序主要使用了Whale、Rect、Bonus结构体和wImg、wImgx数组,没有明显数据结构。
    3 模块功能介绍
    4 程序框架图
    5 主要功能实现
    透明贴图:因为物体绘制时需要去掉背景,所以如何实现透明贴图成了一大难题,最初是想通过导入Png实现,发现easyx不支持Png且只支持Bmp与Jpg格式。之后又从网上下载easyx第三方Png支持库,结果安装失败。最后通过绘制补码图和原图实现了透明贴图
    随机障碍:一开始打算通过人工导入地图的方式来绘制地图,但发现数据不好处理,因此采用了随机算法每个一段时间生成障碍。在最初的Demo版本里,出现了随机物体组合导致小蓝鲸无法通过的情况,因为是纯随机生成,所以通过检测随机数以防出现通不过的障碍组合避免了该问题。
    操作捕捉:小蓝鲸移动过程中会出现“先动一下,再缓缓移动”的情况,也就是动作不流畅的问题。这一问题是由于使用getch()来捕捉按键导致的,getch()获取输入存在系统给定的0.5毫秒的间隔。之后我们实现了用GetAsyncKeystate解决了该问题,实现了平滑移动。与此同时还有一个问题是,玩家按住某一个键小蓝鲸会一直移动下去,灵敏度很高,之后我们设置了“按下并弹起”的条件,这样小蓝鲸的动作更加易于控制
    移动问题:物体移动是游戏的一大难题,在最初物体移动是通过坐标自增减实现的,但物体的速度是通过Sleep控制的并且不稳定不直观。之后我们通过获取系统时间来测量间隔时间,据此计算出物体坐标,实现了物体更精确的移动
    碰撞判定:物体碰撞需要知道坐标、长、宽三个量,而这和图片大小密切相关。我们游戏图片都是矩形,碰撞检测也以矩形为判定,如果物体的轮廓不接近矩形就会有很奇怪的碰撞判定,于是芮雨琛同学把物体做的更像矩形,缓解了该问题
    界面切换:图形移动过程中前一刻图像未擦除导致重复出现,在循环移动过程中不断覆盖背景图片以营造擦除效果;界面切换时鼠标不断获取信息进行判断,造成界面2的信息放到了界面1使用判断条件下,导致判断错误,界面切换乱套,在程序中放入多个goto结构使得信息去往正确的位置
    跳跃功能:在实现跳跃功能时直接使用岳翔在物体移动中的相关函数会出现一些逻辑性和变量重复的问题,通过编写新的专用于跳跃判定的函数解决了这个问题。其他没有遇到问题

    6 总结最初的希望就是——努力制作出一款真正由我们设计和实现的高水准游戏。
    即使它是一款只有一千行代码的小游戏,但是我们一直用玩家视角不断审视,比如鼠标移到按钮上的效果、跳跃和下落时的重力加速度等,我们将一开始天马行空的想象逐步落实到每一个细节。
    为了这个目标,几乎每一个成员在前期都为了这款游戏熬夜到两三点甚至更晚:背景、角色、障碍物,都是亲自设计和制作,用PS、VS反复调试效果;为了更流畅更真实,碰撞判定、操作捕捉、物体移动,一次次讨论、修改。但是,当看到它一点点成长时,其中的喜悦溢于言表。
    它小巧精致,倾注了我们所有的努力,而这些,都没有白费。
    从理论上说,一个完整的程序设计的开头应该将整个程序的整体结构和具体功能确定,但是由于对C语言的理解还不够,我们在早期的一些设定在后期被陆续推翻、修改、重建,当然主体框架得以保留;同时还有很多新的功能和想法在具体编写过程中出现。
    在这个过程中我们得到了类似于对游戏进行更新的体验,我从中认识到了一个良好的程序的框架的重要性:一个好的框架能够很好的适应修改和更新,对于维护也更加方便;而当程序现有框架不能很好的满足程序功能上的需求的时候应该果断重写框架,这样能够大大的提高效率。
    同时我还认识到了团队合作完成工程项目中沟通交流的重要性:在编写jump()函数的时候,因为我们是将同学的代码作为主体框架,在上面加以修改,而不同的代码编写习惯导致我直接阅读同学的代码时非常困难。在将jump()函数整合到主题代码中时,程序整体逻辑出现了很多问题,而后我加强了和同学之间的沟通和交流,后面的功能整合就基本没有遇到什么问题了。同时我也得到了一个启发:在编写团队合作的项目时最好确定一套统一的书写规范,同时多打注释多交流,这样能够很好的提高工作效率。
    7 游戏演示游戏初始界面

    游戏介绍

    游戏难度选择

    游戏画面1

    游戏画面2

    游戏结束
    1 评论 95 下载 2018-11-05 18:00:09 下载需要7点积分
  • 基于VC++和Oracle数据库的邮件管理系统的设计与实现

    摘 要电子邮件的使用简易,投递迅速,收费低廉,易于保存,全球畅通无阻,使得电子邮件被广泛地应用,当前流行的各大邮件系统除了最主要的收发信件之外,功能越来越复杂,但是人们平常真正用到的功能很少,很多功能尤其对于那些计算机知识相对缺乏的人来说,更见显得太过于华丽而不太实用。有鉴于此,开发一个集收、发、管理为一体的功能相对简单实用的电子邮件系统可以大大方便我们对邮件的收发和管理。
    一、 引言1.1 电子邮件简单介绍电子邮件(简称E-mai1)又称电子信箱、电子邮政,它是—种用电子手段提供信息交换的通信方式。它是全球多种网络上使用最普遍的一项服务。这种非交互式的通信,加速了信息的交流及数据传送,它是—个简易、快速的方法。通过连接全世界的Internet,实现各类信号的传送、接收、存贮等处理,将邮件送到世界的各个角落。到目前为止,可以说电子邮件是Internet资源使用最多的一种服务,E-mai1不只局限于信件的传递,还可用来传递文件、声音及图形、图像等不同类型的信息。
    1.2 开发背景及意义当前流行的各大邮件客户端软件的除了最主要的收发信件之外,功能越来越复杂,但是人们平常真正用到的功能很少,很多功能尤其对于那些计算机知识相对缺乏的人来说,更加显得太过于华丽而不太实用。有鉴于此,我们开发了这个各种功能相对简单实用的邮件客户端程序,简化了很多不必要的功能。
    1.3 开发及运行环境
    开发环境

    VC6.0+Oracle 11g 32位
    PC内存8G,硬盘500G

    环境

    Microsoft Windows XP以上操作系统

    二、数据库设计2.1 需求分析本系统定位于中小型单位,暂时考虑单机环境下的实现;本系统针对的用户环境为Windows系统(从XP系统到目前最新的Windows10系统),能够在Windows系统上稳定运行。
    本系统采用会员式管理,每个已经注册过的用户都有一个属于自己的用户名和密码,通过该用户名和密码就可以登陆系统执行基于自己权限范围内的操作。其中用户名(也是邮箱地址)有一个特定的后缀sk.mail.com,一个完整的用户名示例如下:123@sk.mail.com。
    根据权限的大小,将用户分为两类:第一类:超级用户,有且仅有一人,其用户名为“”(空串),密码为955219。此用户可以查看本应用程序各个普通用户的信息,查看所有的邮件,查看,修改,删除所有的邮件或联系人或邮件类型等。另一类:普通用户,用户名以sk.mail.com结尾,密码为在注册的时候用户自己指定,不可为空,只能查看自己的联系人、邮件记录、邮件类型等。
    系统功能应包括联系人基本信息的输入输出与修改、邮件记录的基本信息输入修改、联系人分组的基本情况、用户等级的计算、统计分析。用户可以通过此系统查询自己的等级。
    本系统功能可分为四大部分:联系人管理,邮件记录管理,用户管理以及其它的零碎管理。
    2.2 联系人管理联系人管理又分为联系人信息管理,联系人分组管理,黑名单管理。

    联系人信息应包括:联系人的ID(contact_id),联系人的姓名(contact_name),联系人邮箱(e_mail),头像和联系人所在组(group_id)
    联系人分组信息应包括:组的id(group_id),组名(group_name)和组备注(group_desc)
    黑名单的信息:表结构和联系人的表结构完全一样

    2.3 邮件记录管理邮件记录管理包括:邮件记录管理,回收站管理,附件管理。

    邮件记录信息应包括:记录ID(record_id),收件人姓名(contact_name),邮件的发送日期(send_date),是否添加附件(is_fujian),邮件类型(type_id),邮件内容(email_info)和附件名(fujian_name)
    回收站的表结构应与邮件记录的表结构完全一样
    附件信息应包括:附件ID(fid),附件名(fname)和附件描述(fdesc)

    2.4 用户管理
    用户信息应包括:用户ID(user_id)、用户名(user_name),用户名即邮件地址,用户密码(user_passwd)
    2.5 其它
    邮件类型信息应包括:类型id(type_id),类型名(type_name)
    3 概念结构设计这里我采用自底向上的设计方法,即首先定义各局部应用的概念结构,然后将它们集成起来,得到全局的概念结构。
    联系人实体
    联系人的姓名和Email是联系人实体的固有属性。但是因为同名现象的出现,我们增加联系人编号这一属性,便于数据库的管理管理。又因为添加了黑名单管理和用户头像的管理的功能,所以增加是否拉黑的标记和头像路径这两个属性。
    所以联系人的分E-R图如下:

    声明:在此过程,我们为实体的每个属性,赋予一个英文简称,便于交流和数据库编程,后文中不再出现中文名称,以下几个实体同理!
    联系人分组
    组名是分组实体的固有属性,同样也是便于管理和数据库编程,添加id属性。又因为人性化设计为分组实体添加了一个组备注的属性,用户可以简单记录一下本组中放了那些联系人或者这个组是因为什么而创建的。
    所以联系人分组的分E-R图如下:

    邮件类型实体
    邮件名自然是邮件类型实体的固有属性,添加id属性的原因和上一个实体相同。
    所以,邮件类型实体分E-R图如下:

    附件实体
    附件名和附件内容是福建实体的固有属性,添加附件编号的原因同上。为了用户友好,添加一个附件备注的属性。
    又因为练习一下Oracle数据库提供的blob,所以还有一个附件的二进制内容属性。
    所以附件实体的分E-R图如下:

    邮件记录实体
    收件人id、发送日期、是否添加附件、类型id、邮件内容是邮件记录实体的固有属性。添加编号属性的原因同上。
    因为添加了回收站功能,所以添加了一个是否移动到了回收站的标记;因为添加了一个草稿箱的功能,所以添加了一个是否作为草稿的标记;因为可以添加附件,添加一个附件id属性;因为添加了一个查看已读未读邮件的功能,所以应具备是否已读的属性。
    所以邮件记录实体的分E-R图如下:

    用户实体
    用户名和密码是固有属性,添加id属性的原因同上。
    所以用户实体分E-R图如下:

    各实体间的联系
    一个用户可以有多个联系人和多个邮件记录,但是一个一个联系人只属于一个用户,一个邮件记录也只属于一个用户。一个分组中有多个联系人,但是一个联系人只属于一个分组。一条邮件记录只属于一种邮件类型,一种邮件类型可以对应对个邮件记录。一个邮件记录只能对应一个附件,一个附件也只能对应一个记录。

    集成后的E-R图
    在本次数据库设计中不存在命名冲突的情况,所以直接进行E-R图的合并。

    四、逻辑结构设计4.1 确定关系模式联系人实体
    contact_info_tab(contact_id, contact_name, e_mail, group_id, is_black, head_pic_path);
    为什么要增加组id这个属性呢?
    因为我增加了一个联系人分组管理,联系人和联系人分组是两个不同的实体,他们之间存在1:n的联系,即一个组内有多个联系人,但是一个联系人只属于一个分组。
    又因为数据库学科重用这样一条原理:

    所以,为了简便,不把组与联系人之间的联系单独做成一个实体,而是将组id作为联系人的属性。
    联系人分组
    contact_group(group_id, group_name, group_desc);
    邮件类型
    email_type_tab(type_id, type_name);
    附件实体
    email_fujian(fid, fname, fdescribe, fbolb);
    邮件记录
    email_record_tab(record_id, contact_id, send_date, is_fujian, type_id, email_info, fujian_id, isread, is_recycle_bin, is_draft);
    邮件记录和邮件类型之间存在联系,邮件记录和邮件附件之间也存在联系,所以将邮件类型和邮件附件的主码作为邮件记录的属性,理由同上(1:n的联系转化为关系模式的原理)。
    用户关系模式
    email_user(user_id, user_name, user_passwd);
    用户拥有关系模式
    user_own(user_id, contact_id, record_id, group_id, fujian_id);
    为什么要创建这么一个关系模式呢?
    m:n的联系(多对多的联系)转化为关系模式的原理如下:

    所以,加用户拥有这个联系转化为关系模式。
    那么问题又来了:根据以上理论关系模式应该是user_own(user_id, contact_id, record_id),主键是全码情况就可以了,为什么会多出两个属性呢?
    这是为了查询时候的方便,如果不添加这两个属性,以后再查询的时候会做表的链接查询或潜逃查询,比较麻烦,所以直接把group_id,fujian_id也添加进来。
    这样,我们就形成了一般的数据模型。一般情况下,这一步之后就是向特定的RDBMS转换,但是对于Oracle数据库来说,Oracle是关系型数据库,所以不必转换。
    4.2 数据模型的优化确定函数依赖
    contact_info_tab(contact_id, contact_name, e_mail, group_id, is_black, head_pic_path);contact_group(group_id, group_name, group_desc);email_type_tab(type_id, type_name);email_fujian(fid, fname, fdescribe, fblob);email_user(user_id, user_name, user_passwd);email_record_tab(record_id, contact_id, send_date, is_fujian, type_id, email_info, fujian_id, isread, is_recycle_bin, is_draft);
    对于以上几个关系模式,已经达到了BCNF的要求,不必进行化简。一般来说只要达到3NF就可以了,更不用说达到了BCNF。
    下面以email_fujian为例说明这几个关系为什么达到了BCNF:
    对于email_fujian存在函数依赖(id→fanme)、(fid→fdescribe)、(fid→fblob)。因为主属性只有一个,肯定不存在非主属性对于码的部分函数依赖,关系达到了2NF;又因为不存在非主属性对于码的传递函数依赖,所以达到了3NF;又因为主属性只有一个,所以主属性对于码的部分函数依赖,达到了BCNF。其余几个同理。

    下面我们分析user_own(user_id, contact_id, record_id, group_id, fujian_id);对于user_own存在函数依赖:(user_id, contact_id, record_id→group_id)、(user_id, contact_id, record_id→fujian_id)。(contact_id→group_id)、(record_id→fujian_id)。存在非主属性对于主属性的部分函数依赖,此关系模式属于1NF,存在数据冗余,可能存在删除异常,修改异常,数据不一致的情况。
    对关系模式进行合并或分解
    对于BCNF的几个关系模式来说,没有必要进行合并或分解,可以全部原样保留。但是对于user_own我们是不是要进行处理呢?
    答案是在此处不需要进行处理。按照规范化理论,user_own关系模式是可以继续分解的,以减少数据冗余,消灭数据不一致的情况。但是,此邮件管理系统设计之初就是中小型的,数据量不会很大,达到几十万,几百万,上千万,这样庞大的数据量。
    有一些冗余也是可以接受的。还有一个原因就是如果对user_own这个关系模式进行分解,查询的时候就会进行连接运算,对编程的人来说麻烦,对效率来说,连接查询代价十分高。对此课本中也有相关的论述。

    4.3 设计用户子模式子模式,就是外模式,在数据库中与这个概念相对应的就是视图。
    在此,我设计了4个视图,分别是:view_black_list,黑名单视图,用于查询所有已经拉黑的联系人;view_email_notread,未读邮件视图,用于查询所有的未读邮件的信息;
    view_email_readed,已读邮件视图,用于查询所有的已读邮件的信息;
    view_record_recycle_bin,垃圾箱视图,用于查看已经移动到垃圾箱的所有邮件记录。
    定义视图的目的如下:

    保证了系统的安全性,让用户(程序员)只能查看视图的内容,对其屏蔽数据库内其他的内容
    方便用户使用。在定义视图的时候对某些属性列的列名进行了重新命名,使用户能够“见名知意”,更加方便
    简化用户的编程操作。某些局部应用要是用很复杂的查询,比如垃圾箱,在邮件记录表中,有很多属性都是编号,而用户往往并不关心编号,需要的是相应的名称,这就需要很多的联接查询,相当麻烦。将这些复杂查询定义为视图,用户只需对视图进行操作,大大方便了用户

    这四个视图的定义sql语句如下:




    5 物理结构设计阶段数据库在物理设备上的存储结构与存取方法称为数据库的物理结构,它依赖于选定的数据库管理系统。为一个给定的逻辑数据模型选取一个最适合的应用要求的物理结构的过程,就是数据库的物理设计。
    数据库的物理设计通常分为两步:

    确定数据库的物理结构,在关系数据库中主要指存取方法和存储结构
    对物理结构进行评价,评价的重点是时间和空间的效率

    5.1 关系模式存取方法的选择确定数据库的存取方法,就是确定建立哪些存储路径以实现快速存取数据库中的数据。现行的DBMS一般都提供了多种存取方法,如索引法、HASH法等。其中,最常用的是索引法。我们在经常需要搜索的列和主关键字上建立了唯一索引
    5.2 确定数据库的存储结构由于不同PC机所安装的数据库软件位置不一定相同,所以数据文件与日志文件的存放位置也不一定相同。
    在此次课程设计中,本人并未建立索引等,但是Oracle数据库会自动做一些处理,比如建索引,存放文件等。此步骤已经省略。
    6 数据库实施阶段
    本系统前端开发工具我们选择VC6.0,后台数据库采用Oracle 11g 32bit版本,本系统是通过MFC(C++)代码进行连接的。
    各表的定义及约束条件如下:



    声明:本系统中的所有索引信息都是有Oracle数据库自动添加的,Oracle数据库对主属性列和唯一属性列添加索引。下面几个表类似,不再赘述。









    邮件记录表
    表定义如下:
    CREATE TABLE "SCOTT"."EMAIL_RECORD_TAB" ( "RECORD_ID" NUMBER, "CONTACT_ID" NUMBER NOT NULL ENABLE, "SEND_DATE" DATE NOT NULL ENABLE, "IS_FUJIAN" NUMBER NOT NULL ENABLE, "TYPE_ID" NUMBER NOT NULL ENABLE, "EMAIL_INFO" VARCHAR2(128 BYTE) NOT NULL ENABLE, "FUJIAN_ID" NUMBER, "ISREAD" NUMBER, "IS_RECYCLE_BIN" NUMBER, "IS_DRAFT" NUMBER DEFAULT 0 NOT NULL ENABLE, CHECK (is_fujian in(0,1)) ENABLE, PRIMARY KEY ("RECORD_ID") USING INDEX PCTFREE 10 INITRANS 2 MAXTRANS 255 COMPUTE STATISTICS STORAGE(INITIAL 65536 NEXT 1048576 MINEXTENTS 1 MAXEXTENTS 2147483645 PCTINCREASE 0 FREELISTS 1 FREELIST GROUPS 1 BUFFER_POOL DEFAULT FLASH_CACHE DEFAULT CELL_FLASH_CACHE DEFAULT) TABLESPACE "USERS" ENABLE, CONSTRAINT "CK_READ_RECYCLE" CHECK ((ISREAD=1 and IS_RECYCLE_BIN=1)or(ISREAD=0 and IS_RECYCLE_BIN=0)or(ISREAD=1 and IS_RECYCLE_BIN=0)) ENABLE, FOREIGN KEY ("TYPE_ID") REFERENCES "SCOTT"."EMAIL_TYPE_TAB" ("TYPE_ID") ENABLE, CONSTRAINT "FK_FJ_ID" FOREIGN KEY ("FUJIAN_ID") REFERENCES "SCOTT"."EMAIL_FUJIAN" ("FID") ENABLE, FOREIGN KEY ("CONTACT_ID") REFERENCES "SCOTT"."CONTACT_INFO_TAB" ("CONTACT_ID") ON DELETE CASCADE ENABLE ) SEGMENT CREATION IMMEDIATE PCTFREE 10 PCTUSED 40 INITRANS 1 MAXTRANS 255 NOCOMPRESS LOGGING STORAGE(INITIAL 65536 NEXT 8192 MINEXTENTS 1 MAXEXTENTS 2147483645 PCTINCREASE 0 FREELISTS 1 FREELIST GROUPS 1 BUFFER_POOL DEFAULT FLASH_CACHE DEFAULT CELL_FLASH_CACHE DEFAULT) TABLESPACE "USERS" ;
    检查信息是对该表中数据进行操作(增,删,改)的时候,自动检查属性列的取值范围,如果不符合check语句的条件,就会报错。例如:在is_fujian这个属性中,取值只能是0或1,如果输入了其他值就会报错。下面几个表类似,不再赘述。















    7 应用系统设计7.1 需求分析邮件管理系统用户需求分析
    实际结合邮件管理系统的现实情况来说,主要有如下一些需求:

    邮件帐户管理,新建邮件帐户,删除邮件帐户
    新建邮件,选择一个邮件帐户,输入收件人地址,发送邮件
    接收邮件,选择一个邮件帐户,接收该邮件帐户上的邮件
    邮件夹管理,包括发件箱,收件箱

    根据以上的分析,本系统主要实现邮件账户管理;邮件发送;邮件接收;收件箱、发件箱管理等功能。希望通过该系统的建设能够基本实现一个简单且功能较为完备的邮件收发客户端系统。
    系统功能需求分析概述
    根据用户需求,该邮件管理系统主要应包括如下功能:

    邮件帐户设置邮件管理系统客户端软件需要支持多帐户邮件收发,类似OutLook Express、FoxMail等邮件客户端软件。本系统能够支持新建邮件帐户、删除邮件账户等功能
    邮件发送发送邮件是一个邮件客户端软件的最基本功能,要求可以输入收件人的地址、邮件标题、邮件正文内容、并能够支持邮件附件。能够正常发送普通邮件和带附件的邮件
    邮件接收要求能够接收系统中所有帐户的邮件,具体是先选择一个帐户,然后将该账户下的邮件接收到收件箱中。接收到的是一个邮件列表,主要包括邮件发件人、邮件标题、发送时间等信息
    邮件夹管理要求能够将用户收到的邮件放入收件箱中以列表的形式进行显示,对用户发送的邮件同样在发件箱中以列表形式进行显示
    其他功能主要包括邮件管理系统界面要美观,操作简便等

    7.2 性能需求分析由于本邮件管理系统软件是安装在个人电脑上的客户端软件,所以要求用户界面简洁,友好,方便使用和操作。
    邮件管理系统的基本功能是收发邮件和账户管理,要求账户管理能够实时响应,发送邮件时要求系统响应速度快,发送普通邮件要求在3秒内发送完成。发送带附件的邮件能够在1分钟之内发送完成。系统响应速度决定用户体验,如果一款软件每个操作都要用户等待很长时间,那这注定是一款失败的软件系统。
    邮件收取同样要求速度不能太慢,对于普通邮件,要求5秒钟之内可以收取一封。对于带附件的邮件,要求能够在1分钟之内收取完成。
    此外,系统运行时候不能占用太多资源,试想一下,假如,当用户使用这款软件时,软件占用了太多的系统资源而导致用户对电脑的其他操作都很难进行,那么,谁还会用这款软件呢?所以,该软件还应该具备一种特点就是:低的系统资源占用率。
    8 概要设计软件模块结构设计

    软件架构设计

    9 详细设计9.1 系统用例图和流程图

    9.2 系统登录界面模块使用邮件管理系统必须要登录,系统登录界面如下图48所示:


    9.3 系统主界面模块登录后进入系统主页面,主页面分为上下两部分,上一部分由标题栏、菜单栏和图标栏构成。下一部分显示邮件夹、邮件列表等信息。
    系统主界面如下图所示:

    9.4 注册邮件帐户(用户)模块单击菜单栏里的用户–注册,添加新的邮件账户。邮件账户信息保存到系统的email_user表中,其运行界面如下图所示:


    9.5 系统发送邮件界面模块单击主对话框的发送邮件button,弹出发送邮件界面,如下图5.5.1所示:
    选择相应的联系人,输入收件人地址、邮件主题、邮件内容,可以增加附件。单击确定。


    10 测试与调试10.1 测试我个人做的是这个软件收发系统的一个最基本也是最主要的功能之一:发送邮件。所以主要的测试也是围绕发送邮件展开的,具体的可以分为以下几个方面。
    同一用户,发送一封纯文本邮件的测试

    发送一封文本邮件给一个收信人测试中,发一封不带附件的纯文字的邮件给联系人,然后切换用户,查看一下收件箱是否有此邮件
    发送一封文本邮件给多个收件人测试中仍然在同一用户下同时发往不同的邮箱,切换用户检查,都可以正常的接收到。从而很好的验证了,我们的邮件发送系统支持群发的功能

    一个用户,发送带附件的邮件的测试

    发送一封带附件的邮件给一个收信人测试中,发一封带附件的邮件给联系人,然后切换用户,查看一下收件箱是否有此邮件。并查看附件情况
    发送一封带附件邮件给多个收件人测试中仍然在同一用户下同时发往不同的邮箱,切换用户检查,都可以正常的接收到,在查看附件,都是存在的。从而很好的验证了,我们的邮件发送系统支持群发的功能

    10.2 其他测试比如黑名单,垃圾箱等,操作一下,检查是否符合预期目标,如果符合,切换不同用户,继续测试,如果还ok,那就可以了。如果不符合预期值,那就debug一下。还让其他同学也来体验一下我的程序,会有意外收获的。
    10.3 调试总而言之,在编程过程中,不知道会出现什么样的情况,而且出错频率还是很高的,而在课程设计的过程中,几乎有一半的时间是在debug,这是不可避免的,无论他的编程水平有多高。
    关键是在这个过程中学习熟练解决之道。不要妄想我能记住所有的错误情况,就算你历尽千辛万苦记住了VC的所有错误,你记得住Java吗?PHP呢?在出现错误之后,不要着急,先看一下报错的原因,所有的语法错误都可以在这里解决;然后还有问题的话,就要debug,确定是哪一行出现问题,调试期间还可以理清思路,看是不是逻辑错误;最后就可以百度了,我们遇到过的问题,别人肯定遇到过。最后大杀招,问老师同学,因为我们写的是一样的程序,交一样的作业,大家遇到的问题差不多。
    11 特色以及在原基础上添加的功能11.1 联系人分组管理添加组


    查看并修改组

    如上图所示,当组内没有成员的时候,设组合框为不可编辑,写明“该组内没有成员”。

    如上图所示,当组内有成员的时候,组合框下拉可以看到该组内所有成员。如上面两张图所示:当察看组情况的时候,组名不可编辑,不允许更改。
    删除一个分组




    发送邮件时,分组和联系人相互关联


    如上图所示,当用户点击组名的时候,联系人组合框会自动筛选出该组内左右的成员,以便用户查找联系人。


    上传用户头像



    添加附件

    如上图所示:初始情况下,关于附件的所有控件都是不可见的。

    如上图所示:在选中添加附件的选项后,所有控件全部显示。



    查看附件


    如图所示:当点击附件名的时候,会调用windows系统自带的软件打开附件。
    群发功能


    如图85和86所示:当用户从组合框中选取值的时候,会自动添加到编辑框中,并且编辑框不可修改。


    模糊查询


    如图所示:当用户选中选项时,会自动跳出隐藏的相关控件。下同。



    草稿箱


    查看已读、未读邮件
    1 评论 9 下载 2018-11-05 17:47:06 下载需要9点积分
  • 基于WIN32 API界面编程实现的数位飞机大战小游戏

    1 游戏介绍《数位飞机大战》(DigitPlane)是经典游戏“飞机大战”的仿制。游戏背景为,玩家被敌人困在计算机内由数字组成的世界里,只能驾驶飞机,发射子弹,尽量多地击毁敌机,以获得逃离的机会。飞机,子弹,敌机都是由数字构成的,若飞机被击中,会幻化消失在茫茫的数字世界中。
    游戏界面上主要元素均为数字,玩家使用最经典的输入设备——键盘控制自己飞机的飞行。游戏提供多种道具供玩家拾取以增加趣味性。
    2 游戏流程游戏流程如下图所示。

    3 界面设计游戏界面总体采用简单的纯色、像素风格,如下图所示。

    4 概要设计4.1 系统架构主要函数、模块层次划分如下图所示。

    4.2 核心代码流程游戏逻辑的主要部分,核心代码之所在,Run_Timer函数的流程如下所示。

    流程开始:由WinProc调用
    S0:更新计时器全局变量
    S1:遍历所有敌机,调用HitHero判断是否与我机相撞(如相撞,标记敌机)
    S2:遍历所有子弹和所有飞机,调用Hit判断是否击中(如击中,标记子弹和飞机)
    S3:遍历所有道具,调用GetToy判断是否被我机拾获(如拾获,标记道具,产生道具效果,设置相应全局变量)
    S4:判断当前分数和关卡,如果需要,升级关卡
    S5:判断计时器全局变量的值,如符合频率要求,创建一架新敌机
    S6:遍历所有敌机,产生位移
    S7:判断计时器全局变量的值,如符合频率要求,以一定概率随机使敌机产生新的子弹
    S8:遍历所有敌机,若飞出屏幕,调用DestroyPlane清除
    S9:遍历所有子弹,产生位移
    S10:遍历所有道具,产生位移
    S11:判断计时器全局变量的值,如符合频率要求,使我机产生新的子弹。根据全局变量记录的道具信息产生不同子弹,更新道具冷却时间全局变量
    S12:加分
    S13:清除无效的飞机。遍历所有敌机,若发现被标记,调用DestroyPlane清除之。在大飞机被清除时产生道具,在Hero快没血的时候以更大的概率产生 toyBLD
    S14:清除无效的子弹。遍历所有子弹,若发现被标记,调用DestoryBullet清除之
    S15:清除无效的道具。遍历所有道具,若发现被标记,调用DestoryToy清除之
    S16:动画进帧
    流程结束,控制流交还WinProc以绘图

    5 总结与感悟在大一第一学期的诸课程中,软件工程(1)是使我收获最大的一门课程,软件工程(1)的大作业是使我收获最大的一项作业。
    大作业的完成综合应用了一学期以来通过C语言程序设计课程学习到的知识和技能。特别是数组、结构体的大量使用,使我对该部分内容掌握非常牢固。我想,正是这样——不管学了什么东西,一定要用起来,才能真正掌握好。
    大作业锻炼了我的自学能力。助教提供的参考书是大部头,不可能全部读完,我选择性地读了对我最有帮助的两章,这帮助我了解了Windows API编程的基本知识,迅速读懂助教提供的框架代码,使我仅用数小时便完成所有必须的功能点成为可能。大作业的完成过程增加了我对编程的兴趣,增强了我的自信。毕竟本课程是本学期诸课程中唯一我觉得在同学中间有优势的课程了……
    我的大作业代码达到两千行。良好的编程习惯的重要性显示出来。而且这样规模的程序已经需要一定的层次架构了,完成大作业的过程是这方面的一种启蒙。
    在大作业完成过程中,我自己摸索出了打印调试信息、合理设置断点、利用Visual Studio提供的多种调试工具等进行调试的方法,可以说是用自己的智慧解决了一开始看起来难以解决的Win32应用程序难以调试的问题。
    在帮助同学调试飞机大战程序的过程中,我见到了不少其他同学犯的错误,有些很难发现。这使我积累了很多调试经验,对我自己以后编写程序也是一种提示。
    6 游戏演示游戏初始界面

    游戏画面1

    游戏画面2

    游戏结束
    1 评论 10 下载 2018-11-05 17:35:47 下载需要8点积分
  • 基于Winpcap实现的发送ARP数据包和IP数据包

    1 项目介绍1.1 基本任务
    完成两台主机之间的数据通信(数据链路层)
    仿真ARP协议获得网段内主机的MAC表
    使用帧完成两台主机的通信(Hello! I’m …)

    1.2 高端任务
    完成两台主机通过中间主机的数据通信(网络层)
    增加基于IP地址的转发功能
    增加网络层封装

    2 帧结构2.1 以太网帧格式
    2.2 ARP帧的数据结构表达方式typedefstructarphdr {   unsigned short arp_hrd; /*硬件类型*/   unsigned short arp_pro; /*协议类型*/   unsigned char arp_hln; /*硬件地址长度*/   unsigned char arp_pln; /*协议地址长度*/   unsigned short arp_op; /*ARP操作类型*/   unsigned char arp_sha[6]; /*发送者的硬件地址*/   unsigned long arp_spa; /*发送者的协议地址*/   unsigned char arp_tha[6]; /*目标的硬件地址*/   unsigned long arp_tpa; /*目标的协议地址*/ }ARPHDR,*PARPHDR;
    2.3 对于基本任务获取本机mac的实现原理:主机A发送了一个广播帧,sourceip则随便设置了一个,主要用于在接收帧的时候识别,在GetSelfMac的方法里,利用winpcap的pcap_next_ex抓取包的时候,判断sourceip是不是之前设定的那个就可以。

    获取活动主机的原理:广播arp包对返回的arp包进行数据解析。由于arp包的简洁性,发送和接收都很简单。
    Main.cpp主要的活动:获取自己的mac—>获取局域网内的活动主机—>用户选择发送给哪台机器—>根据选择的主机,封装数据,目的mac,目的ip—>等待接收消息—>接收到消息,解包,解析出收到包的所有信息
    Receive.cpp主要的活动:获取自己的mac—>等待接收数据—>接收到消息,解析,展示,然后提取出源mac,ip—>返回消息

    图1:main获取mac(获取活动主机的忘记截图了,代码里有体现,为了测试,取消了这部分),发送消息之后,立刻把发送消息的信息输出来.

    图2:receive接收到消息,把接收到的消息解析出来,然后再发送

    图3:main接收到发送过来的消息,timeover是一个超时标志,每隔一段时间receive会在检测一下,如果在这段时间内没有受到消息,就输出一个超时标志

    2.4 对于高级任务| 以太网数据头 | IP数据头 | TCP数据头 | 数据| 校验和 |
    主要的思想还是封装数据,发送,过滤接收。
    为了实现的简易性,限定A只进行发送数据,C只接收数据,B则接收A发送来的消息,并转发给C。B有两块网卡,分别和A,C在不同的局域网内。A仅仅知道C的ip和B的mac。A,C不再赘述,仅仅是简单的main去掉了接收功能,和receive去掉了发送功能
    这里利用B的代码详细再了解下winpcap以及整个思路。
    前面定义的几个结构体是标准以太网帧和arp帧各部分的结构体,数据大小严格遵循标准以太网帧的结构。
    由于时间原因,可能数据结构有些凌乱,各种重定义。

    获取本机设备列表,打印列表,跳转到选中的适配器,打开设备,都是中文api里面有的
    过滤器的设置是标准格式的,网络上的。而,过滤器的语法则要自己写
    receiveMessage :
    while ((ret = pcap_next_ex(adhandle, &header, &pkt_data)) >= 0 && (!getit))
    这是主要的循环判断条件,利用了winpcap的pcap_next_ex来抓包,而getit是一个是否抓取到指定条件包的标志,这是为了配合实验写的,一个更真实的过程应该是抓到包以后判断目的mac,ip然后从前面扫描到的表里面找对应的mac和ip。抓到后些出了目的mac,因为是标准帧,所以只需要截取在指定位置数据即可。下面又添加了一个过滤条件是为了过滤出发送到C的包。因为在这个高级任务中,A可能给B发送好多包,但是仅仅一个过滤条件是不够的。把抓到的包的主要信息输出来。并置getit为true
    然后,跳转到和C在同一号段的网卡(实际上仅仅是适配器),扫描局域网,获取局域网内活动的主机,然后在这个列表中搜索目的ip,进行路由转发
    sendHello:填充一个标准以太网帧,这里的目的mac,ip都是在代码中手写的,一个更真实的方法应该是利用抓到的包提取出来填充。我这里实现的时候出了一些问题,可能对c中的指针和一些格式匹配问题不太熟悉,没能成功
    关于校验和,每次都是先占好位置,然后再根据数据,重新计算,重新覆盖原来的部分。本来想利用一个指针,然后逐渐在后面添加数据方式,实现的时候出现了很多问题,最后放弃了。直接覆盖方式简单暴力

    2.5 遇到的问题
    首先最主要的就是标准以太网帧格式如何写,理论都知道,落到代码就比较困难,百度解决之
    B在抓包过程中,总是一开始抓就抓到了,后来才知道,A不是只有我写的程序在给B发送数据,多添加了一层过滤解决
    过滤器语法,关于通过mac地址来过滤的,网上的几乎没有说对的,或者说针对winpcap,没有说对的,最后从百度知道获取了灵感,ether dst 74-E5-0B-F4-BD-07
    由于对c++的语法了解不够深入,在写指针和字符串处理的时候,耗费了大量时间和精力,导致进展缓慢,主要是在对抓到的包进行解析时,以及发送的包进行数据填充时。还有对vs的不熟悉,写的时候各种神奇的bug。对c++的学习产生了严重的恐惧感

    2.6 写在最后的非常喜欢老师的上课方式,老师讲课思路比较清晰,感觉更符合“问题出现—>解决方法出现—>方法不足的优化—>更多可替换方案的出现—>方法的同时进化,互相学习借鉴—>新问题的出现”这样的发展过程,同时讲课的内容也并非照搬课本,有些问题能拓展出来,让我见识了好多新的东西。
    1 评论 29 下载 2018-11-05 17:31:24 下载需要14点积分
  • 基于VS2012和Cocos2d-x实现的StickToLast益智小游戏

    第1章 问题陈述1.1 项目背景手机用户在休闲时倾向于玩一些类似于Flappy Bird、2048等游戏,这类游戏用户界面简单,游戏模式单一,单手即可操作,随着游戏地进行,游戏的难度会增加。随着手机用户地爆发式增长,这类游戏的需求量愈发庞大。StickToLast 是一款益智类游戏。主角陷于宇宙漩涡之中,被吸入中央的黑洞或者逃离该区域都无法被即将来到的救援部队拯救,只能停留在这一区域,躲避宇宙陨石,坚持的时间越久,被营救的希望越大,得分越高。
    1.2 项目目标为了适应手机用户日渐增加的游戏需求,项目旨在开发一款基于Android的、操作模式简单有趣的休闲益智积分类游戏。
    1.3 项目受众安卓手机用户。
    1.4 运行环境
    操作系统:win7 64位/win8 64位/Windows8.1 64位
    VS版本:vs2012
    cocos2d-x3.0:cocos2d-x 3.0
    使用系统:Android4.0以上

    1.5 功能概述
    用户可以选择开始游戏,暂停游戏
    运行过程中,用户点击跳跃按钮可让游戏目标从低轨道跃迁到高轨道
    用户操纵游戏目标收集轨道上的奖励目标来累加积分
    用户需要跳跃来保证自己不会被吸入中间的黑洞
    用户需注意躲避轨道上的障碍
    得分也会随着时间增长

    第2章 需求分析2.1 StickToLast 用例图
    2.2 游戏流程图
    第3章 逻辑架构设计引擎架构

    游戏架构

    第4章 模块划分

    主角管理模块

    功能:负责游戏中主角(方块)运动对象的位置变更和碰撞检测设计模式:暂无对应代码:Classes/BlockManager.cpp & Classes/BlockManager.h
    怪物管理模块

    功能:负责游戏中怪物(圆形)运动对象的位置变更设计模式:暂无对应代码:Classes/CircleManager.cpp & Classes/CircleManager.h
    游戏实体模块

    功能:定制不同的游戏,负责管理所有游戏模块生命周期(对游戏中的游戏提供统一的定制方法);设计模式:单例模式(MainScene.cpp第29行左右)、工厂模式(CircleManager类和BlockManager的不同create函数)对应代码:Classes/Entyity.h & Classes/Player.h & Classes/Circle.h & Classes/FloatBox.h
    游戏成就模块

    功能:记录用户成就,并随游戏进行实时更新用户成就设计模式:暂无对应代码:MainScene.cpp & MainScenge.h(核心函数:setScore()函数)
    通用工具模块

    功能:提供通用坐标计算服务和区域计算服务设计模式:暂无对应代码:Classes/Util.h & Classes/Util.cpp

    第5章 游戏演示使用apk文件进行安装,进入游戏界面


    左下角按钮用于向外跳跃一圈,右下角按钮用于暂停
    红色点为玩家,白色点为怪物,碰到怪物游戏结束,跳跃一次得一分

    暂停和结束界面
    1 评论 3 下载 2018-11-05 17:28:27 下载需要5点积分
  • 基于Swift实现的最小生成树应用-室内布线

    1 问题内容与目的要求求解最优化问题的算法通常需要经过一系列的步骤,在每个步骤都面临多种选择。对于许多最优化问题,使用动态规划算法求最优解显得大材小用,可以使用更简单、更高效的算法。贪心算法就是这样的算法,它在每一步都做出当时看起来最佳的选择。也就是说能找到最优解的最优化问题。贪心算法并不能保证得到最优解,但对很多问题确实可以求得最优解。
    贪心方法是一种强有力的算法设计方法,可以很好的解决很多问题。采用贪心策略设计的算法就有很多,包括最小生成树的Prim算法和Kruskal算法、单源最短路径的Dijkstra算法,以及集合覆盖问题的Chvatal贪心启发式算法。
    本课题的目的是设计一个程序,来帮助房主完成装修新房子这项颇为复杂的工程的室内电线的布局,具体内容如下:
    首先,墙壁上插座的位置是固定的,插座间需要有电线相连,而且要布置得整齐美观,即要求每条线都与至少一条墙边平行,且嵌入四壁或者地板(不能走屋顶)。
    房主要求知道,要将所有插座连通,自己需要买的电线最短长度。

    另外,别忘了每个房间都有门,电线不可以穿门而过,上图给出了一个有4插座的房子的电线布局。
    输入要求
    输入由若干组测试数据组成。
    每组数据的第1行包含房间的长、宽、高和插座的个数N(N为一个不超过20的正整数)。
    接下去的N行中,第i行给出第i个插座的位置坐标(xi, yi, zi);最后一行包含4个3元组(x1, y1, z1) 、(x2, y2, z2) 、(x3, y3, z3)、 (x4, y4, z4),分别是长方形门框的4个角的三维坐标。4个数字全部为0表示全部测试结束,不要对该数据做任何处理。
    注意:这里假设长方形形状的房间完全位于三维直角坐标系的第一象限内,并且有一个角落在原点上。地板位于x-y平面。题目数据保证,每个插座仅属于四面墙中的一面,门上没有插座。要求每段电线的两端必须仅与插座连接,电线之间不能互相交叉焊接。
    输入数据



    房子(长:宽:高)
    门(x:y:z)
    插座坐标(x:y:z)




    (10:10:10)
    (10:10:10)
    (20:15:20)



    输出要求
    对每一组测试,在一行里输出要将所有插座联通需要买的电线的最短整数长度。
    输出数据



    理论值
    20.3




    上取整
    21



    因此,本课题的实验任务要求如下:

    创建房子,门,插座,并且它们的长度和坐标均为非负数,插座上限为20个
    地板位于x-y平面
    做到室内布线美观,即插线拐角、转角少,布线平行墙边和地脚线,不能走屋顶,插线不能交叉焊接
    判断插座同墙,邻墙和对墙三种情况的布线的求解,以及有门的情况如何求解
    使用最小生成树算法完成室内最短布线的求解

    2 概要设计2.1 系统功能模块
    2.2 项目结构2.2.1 项目总体结构建立名为“最小生成树的应用:室内布线”的工程项目,整个实验将在其中进行。计划编写以如下截图中工程文件目录树为源文件文件结构的包括main.swift等源程序文件在内的Swift源程序,图3体现工程项目的模块结构。

    2.2.2 函数之间的调用关系
    2.2.3 数据结构




    2.2.4 函数








    2.2.5 函数原型及功能
    compareMinimumOfTwo(_:_:)

    原型:func compareMinimumOfTwo(_ a: Double, _ b: Double) -> Double功能:比较两个插座中的权值的最小值,有两个参数,返回值数据类型是双精度浮点数类型,参数传值正确的情况下返回该数据类型对应的值。
    findCost13(_:_:_:_:_:_:)

    原型:func findCost13(_ a: Outlet, _ b: Outlet, _ pointOfDoor1: PointOfDoor, _ pointOfDoor2: PointOfDoor, _ pointOfDoor3: PointOfDoor, _ room: Room) -> Double功能:计算相对墙上两个插座的最短布线,插座a在墙1,在墙1与墙2相交墙边12插入一个临时插座temp1,在墙1与墙3相交墙边13插入一个临时插座temp3,有六个参数,分别是两个插座结构体,三个门的门角的坐标的结构体,房子的结构体,返回值数据类型是双精度浮点数类型,参数传值正确的情况下返回该数据类型对应的值。
    findCost24(_:_:_:_:_:_:)

    原型:func findCost24(_ a: Outlet, _ b: Outlet, _ pointOfDoor1: PointOfDoor, _ pointOfDoor2: PointOfDoor, _ pointOfDoor3: PointOfDoor, _ room: Room) -> Double功能:计算相对墙上两个插座的最短布线,插座a在墙4,在墙4与墙2相交墙边24插入一个临时插座temp2,在墙4与墙3相交墙边34插入一个临时插座temp4,有六个参数,分别是两个插座结构体,三个门的门角的坐标的结构体,房子的结构体,返回值数据类型是双精度浮点数类型,参数传值正确的情况下返回该数据类型对应的值。
    findCost12(_:_:_:_:_:_:)

    原型:func findCost12(_ a: Outlet, _ b: Outlet, _ pointOfDoor1: PointOfDoor, _ pointOfDoor2: PointOfDoor, _ pointOfDoor3: PointOfDoor, _ room: Room) -> Double功能:计算相对墙上两个插座的最短布线,插座a在墙2,在墙2与墙1相交墙边12插入一个临时插座temp1,在墙2与墙4相交墙边24插入一个临时插座temp2,有六个参数,分别是两个插座结构体,三个门的门角的坐标的结构体,房子的结构体,返回值数据类型是双精度浮点数类型,参数传值正确的情况下返回该数据类型对应的值。
    findCost34(_:_:_:_:_:_:)

    原型:func findCost34(_ a: Outlet, _ b: Outlet, _ pointOfDoor1: PointOfDoor, _ pointOfDoor2: PointOfDoor, _ pointOfDoor3: PointOfDoor, _ room: Room) -> Double功能:计算相对墙上两个插座的最短布线,插座a在墙3,在墙3与墙1相交墙边13插入一个临时插座temp3,在墙3与墙4相交墙边34插入一个临时插座temp4,有六个参数,分别是两个插座结构体,三个门的门角的坐标的结构体,房子的结构体,返回值数据类型是双精度浮点数类型,参数传值正确的情况下返回该数据类型对应的值。
    findTogetherLowcost(_:_:_:_:_:_:)

    原型:func findTogetherLowcost(_ a: Outlet, _ b: Outlet, _ pointOfDoor1: PointOfDoor, _ pointOfDoor2: PointOfDoor, _ pointOfDoor3: PointOfDoor, _ room: Room) -> Double功能:求同墙两插座最短布线,有六个参数,分别是两个插座结构体,三个门的门角的坐标的结构体,房子的结构体,返回值数据类型是双精度浮点数类型,参数传值正确的情况下返回该数据类型对应的值。
    findBesideLowcost(_:_:_:_:_:_:)

    原型:func findBesideLowcost(_ a: Outlet, _ b: Outlet, _ pointOfDoor1: PointOfDoor, _ pointOfDoor2: PointOfDoor, _ pointOfDoor3: PointOfDoor, _ room: Room) -> Double功能:求相邻墙两插座最短布线,有六个参数,分别是两个插座结构体,三个门的门角的坐标的结构体,房子的结构体,返回值数据类型是双精度浮点数类型,参数传值正确的情况下返回该数据类型对应的值。
    findAcrossLowcost (_:_:_:_:_:_:)

    原型:func findAcrossLowcost(_ a: Outlet, _ b: Outlet, _ pointOfDoor1: PointOfDoor, _ pointOfDoor2: PointOfDoor, _ pointOfDoor3: PointOfDoor, _ room: Room) -> Double功能:求相对墙两插座最短布线,有六个参数,分别是两个插座结构体,三个门的门角的坐标的结构体,房子的结构体,返回值数据类型是双精度浮点数类型,参数传值正确的情况下返回该数据类型对应的值。
    findTwoLowcost(_ :_:_:_: _:_:)

    原型:func findTwoLowcost(_ a: Outlet, _ b: Outlet, _ pointOfDoor1: PointOfDoor, _ pointOfDoor2: PointOfDoor, _ pointOfDoor3: PointOfDoor, _ room: Room) -> Double?功能:计算墙上任意两个插座的最短布线,返回值数据类型是一个可选的显式闭包的双精度浮点数类型,有六个参数,分别是两个插座结构体,三个门的门角的坐标的结构体,房子的结构体,参数传值正确返回其包装值,参数传值错误返回nil值。
    judgeCrossDoor(_ :_:_:_: _:_:)

    原型:func judgeCrossDoor(_ a: Outlet, _ b: Outlet, _ pointOfDoor1: PointOfDoor, _ pointOfDoor2: PointOfDoor, _ pointOfDoor3: PointOfDoor, _ room: Room) -> Bool?功能:判断两个插座间连线是否穿门,返回值数据类型是一个可选的显式闭包的布尔数类型,有六个参数,分别是两个插座结构体,三个门的门角的坐标的结构体,房子的结构体,参数传值正确返回其包装值,参数传值错误返回nil值。
    judgePositionOutlet(_:_:)

    原型:func judgePositionOutlet(_ outlet: Outlet, _ room: Room) -> Int!功能:判断插座在哪个墙面,有两个参数,一个是插座的结构体,另外一个是房子的结构体,返回值的数据类型是一个隐式强制闭包的整型数类型,参数传递正确返回其自动解包的实际值,参数传递会导致编译错误。
    judgePositionOfDoor(_:_:_:_:)

    原型:func judgePositionOfDoor(_ door1: PointOfDoor, _ door2: PointOfDoor, _ door3: PointOfDoor, _ room: Room) -> Int?功能:判断门在哪个墙面,有四个参数,分别是三个门的门角坐标的结构体和房子的结构体,返回值的数据类型是一个可选的显式可选闭包的整数型,参数传递正确返回其包装值,参数传值错误返回缺省值nil值。
    isTogether(_:_:_:)

    原型:func isTogether(_ a: Outlet, _ b: Outlet, _ room: Room) -> Bool功能:判断是否在同一墙面,有三个参数,分别是两个插座的结构体和一个房子的结构体,返回值的数据类型是布尔数型。
    isBeside(_:_:_:)

    原型:func isBeside(_ a: Outlet, _ b: Outlet, _ room: Room) -> Bool?功能:判断是否在相邻墙面,有三个参数,分别是两个插座的结构体和一个房子的结构体,返回值的数据类型是布尔数型。
    isAcross(_:_:_:)

    原型:func isAcross(_ a: Outlet, _ b: Outlet, _ room: Room) -> Bool功能:判断是否在相对墙面,有三个参数,分别是两个插座的结构体和一个房子的结构体,返回值的数据类型是布尔数型。
    kruskalAlgorithm<T>(_:)

    原型:func kruskalAlgorithm<T>(_ graph: Graph<T>) -> (lowcost: Double, tree: Graph<T>)功能:求最小生成树的算法,主要运用了Kruskal算法,该函数是一个泛型定义的函数,有一个参数,返回值的数据类型是一个二元组,表示最小生成树的长度和哪棵树,用插座和插线表示。
    sorted(_:)

    原型:func sorted(by areInIncreasingOrder: (Wire<T>, Wire<T>) throws -> Bool) rethrows -> [Wire<T>]功能:排序算法,按照升序排序,返回值类型是一个数组元素类型为插线结构体的数组。
    myRoomGroups(_:)

    原型:func myRoomGroups(_ indexOfMyRoomSets: Int) -> Room功能:房子的创建,几组已经存放好的房子的长、宽、高,一个参数,返回值数据类型是一个Room结构体。
    myPointOfDoorGroups(_:_:)

    原型:func myPointOfDoorGroups(_ indexOfMyPointOfDoorSets: Int, _ room: Room) -> [PointOfDoor]功能:门的创建,几组已经存放好的门的门角集合的坐标,两个参数,返回值数据类型是一个数组元素类型为门角结构体的数组。
    myOutletSetsGroups(_:_:)

    原型:func myOutletSetsGroups(_ indexOfOutletSets: Int, _ room: Room) -> [Outlet]功能:一组插座的创建,几组已经已经存放好的插座集合的坐标,两个参数,返回值数据类型是一个数组元素类型为插座结构体的数组。
    addWire(_:_:_:)

    原型:public mutating func addWire(outlet1 o1: T, outlet2 o2: T, weight w: Double)功能:无向完全图的初始化加边函数,含有三个参数,分别是两个插座结构体和一个权该两个插座之间权重,无返回值。
    addWire(_:)

    原型:public mutating func addWire(_ wire: Wire<T>)功能:无向完全图的初始化加边函数的重载,参数为插线的结构体,无返回值。public mutating func addSetWith(_ element: T)
    addSetWith(_:)

    原型:public mutating func addSetWith(_ element: T)功能:Graph<T>结构体下的可以重写的函数,一个参数,参数类型是属于泛型。
    setByIndex(_:)

    原型:private mutating func setByIndex(_ index: Int) -> Int功能:在集合选出新的代表,并指向它,返回值类型为整型。
    setOf(_:)

    原型:public mutating func setOf(_ element: T) -> Int?功能:元素的集合,有一个参数,返回值的数据类型是一个可选闭包整型。
    unionSetsContaining(_:_:)

    原型:public mutating func unionSetsContaining(_ firstElement: T, and secondElement: T)功能:删除一个顶点,即通过合并,保留一个,无返回值。
    inSameSet(_:_:)

    原型:public mutating func inSameSet(_ firstElement: T, and secondElement: T) -> Bool功能:两个顶点在同一个集合中,两个参数,类型均为泛型,都是指插座
    abs<T>(_:)

    原型:func abs<T>(_ x: T) -> T where T : FloatingPoint, T == T.Magnitude功能:两个数相减的取绝对值的,返回类型为浮点数。
    init()

    原型:public init()功能:结构体的构造无参数方法,初始化结构体时的成员属性。

    3 数据结构3.1 用于不相交集合的高级数据结构(并查集)3.1.1 逻辑结构:属于非线形结构的无向完全图结构
    3.1.2 存储结构:通过有根树来表示集合,存储在集合中并查集的Swift代码:
    /********** 并查集结构体 **********/// 并查集的结构体定义,符合Hashable协议public struct UnionFindSets<T: Hashable> { private var index = [T: Int]() // 索引 private var parent = [Int]() // 父节点 private var size = [Int]() // 大小 // 默认的初始化函数 init() public init() { } // 追加元素 public mutating func addSetWith(_ element: T) { index[element] = parent.count parent.append(parent.count) size.append(1) } // 在集合选出新元素作为新的代表,并指向它 private mutating func setByIndex(_ index: Int) -> Int { if parent[index] == index { return index } else { parent[index] = setByIndex(parent[index]) // 递归调用setByIndex(_:)函数 return parent[index] } } // 元素的集合 public mutating func setOf(_ element: T) -> Int? { // 集合自身 if let indexOfElement = index[element] { return setByIndex(indexOfElement) } else { return nil } } // 删除一个顶点,即通过合并,保留一个 public mutating func unionSetsContaining(_ firstElement: T, and secondElement: T) { if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) { if firstSet != secondSet { // 两个集合不等 if size[firstSet] < size[secondSet] { // 第一个集合的权值小于第二个集合的权值 parent[firstSet] = secondSet // 将第二个集合合并到第一个集合中,即第一个集合成为新代表 size[secondSet] += size[firstSet] // 权值相加赋给权值原来大的第二个集合 } else { // 第一个集合的权值大于第二个集合的权值 parent[secondSet] = firstSet // 将第一个集合合并到第二个集合中,即第二个集合成为新代表 size[firstSet] += size[secondSet] // 权值相加赋给权值原来大的第一个集合 } } } } // 两个顶点在同一个集合中 public mutating func inSameSet(_ firstElement: T, and secondElement: T) -> Bool { if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) { return firstSet == secondSet } else { return false } }}
    3.1.3 使用该数据结构的优缺点优点

    并查集适用于所有集合的合并与查找的操作,进一步还可以延伸到一些图论中判断两个元素是否属于同一个连通块时的操作。由于使用启发式合并和路径压缩技术,可以讲并查集的时间复杂度近似的看作O(1),空间复杂度是O(N),这样就将一个大规模的问题转变成空间极小、速度极快的简单操作
    缺点

    需要耗费的存储单元较多
    3.2 无向图的邻接矩阵的数据结构3.2.1 逻辑结构:属于非线性结构的无向完全图结构房子上的所有插座连线后构成的一个无向完全连通图

    无向完全连通图的初始化过程

    最终最小生成树的生成的权值及其顺序情况

    3.2.2 存储结构:链式存储结构的邻接矩阵
    下三角邻接矩阵的Swift代码:
    // 下三角邻接矩阵for firstIndex in myOutletSets.enumerated() { for secondIndex in myOutletSets.enumerated() { // 去掉上三角和本身的情况 if firstIndex.offset >= secondIndex.offset { continue } }}
    3.2.3 使用该数据结构的优缺点优点

    便于判断两个顶点之间是否有边
    便于计算各个顶点的度

    缺点

    不便于增加和删除顶点
    对于稀疏图而言,是一种浪费存储空间的存储方式
    不便于统计边的数目,需要扫描邻接矩阵所有元素才能统计完毕,时间复杂度为O(n2)

    该选题我使用的是无向完全图对称的特点,对其进行了压缩存储的方法,既可以存为下三角的元素,也可以选择上三角的元素,该选题我选择了下三角方式。这样只需要更少的存储单元。
    4 关键问题与主要算法注意:以下描述文字中,在“关键问题的说明”中的均为一般性理论,不限于实验选题的特殊性,在“主要算法”中说明的是一般性理论的具体使用到实验选题要求上的。
    4.1 关键问题的说明4.1.1 证明前的铺设引理墙边上的一个插座同时属于两个不同的邻面;如图10:o1既属于墙a,也属于墙b。

    两个插座分居在相邻墙边上,则两插座既属于同墙关系,也属于邻墙关系;如图11:o1和o2,o2和o3两组组属于同墙关系a或b,也属于邻墙关系a和b或b和a;

    两个插座分居在相对墙边上,则两插座既属于邻墙关系,也属于对墙关系。如图12:o1与o2既属于邻墙关系a和b,也属于对墙关系a和c。

    4.1.2 如何将邻墙和对墙的情况化归为同墙求两插座最短布线问题(只走墙面)同墙

    说明:图13,同墙情况,很自然而然知道两个插座的对应的三维进行相减的绝对值的和,这就是同墙两个插座的最短布线s1或s2或s3,其中s1和s2一样的简洁美观,s3在s1和s2之间,有无数种情况,但都可以通过水平和垂直投射到成s1或s2的情况,长度虽同,实际不美观,所以不必考虑s3情况。
    邻墙

    说明:图14,邻墙情况,出现这样子的三维问题,首先最朴素的方式就是展开为两墙为同一平面,即通过化归一个较复杂的问题为一个简单的问题,在这里,我们可以声明一个辅助的临时全局变量temp,temp可以与两插座任一个完全相同,然后将其水平移至两墙相邻墙面的交线上,即墙边上,这样子该temp插座就相当于搭建起两个插座的联系,从而将问题转化为两组同墙插座的问题,求得两个长度s1和s2后,相加即可。
    对墙

    说明:图15,对墙情况,同样这也是一个三维问题,依旧使用朴素的思想,就是将该三维问题转换为由三个墙面组成的一个平面问题,然后,在这里声明两个辅助的临时全局变量temp1和temp2,这两个临时插座变量可以与两个插座中任一相等,然后将他们水平移至两条相邻的墙边上,不同时在一条墙边上,这样就转换成三组求同墙插座的问题,求得三个长度s1, s2和s3后,相加即可。
    注:走地板亦同,具体见【4.1.3 在两插座的三种关系中的每种关系下,对4.1.2中两插座最短布线的挑选 -> ¬4.1.3.1 ¬前提是墙面上无门 -> (3)对墙】描述,然后套用该化归方法即可。
    4.1.3 在两插座的三种关系中的每种关系下,对4.1.2中两插座最短布线的挑选4.1.3.1 前提是墙面上无门同墙

    说明:同墙情况,图16下的图a和图b的效果是一样子的,图c不予考虑,即便结果相同。
    邻墙

    说明:邻墙情况,走法有三种,图17下的图b和图c结果一样,现在证明图a与图b两种布线长度最短的走法,首先通过平移法则可以很直观地比较出两个图都拥有l1和l2,其次,比较差异部分,图a的l3是从高度较高的插座向下引线的,不穿过地脚线,而图b的走法穿过地脚线,直观证明可知,必然多出l4和l5,显然l4大于或等于l3,当且仅当另一个插座在地脚线时,所以图a的布线方式比图b更短。同理,可得图a的布线方式比图c更短。
    因此,邻墙时,只考虑图a走法即可。
    对墙

    说明:对墙情况,走法有三种,严格上讲,有四种,这第四种其实就时图c情况,当以不同插座为静止参考点去分析时,会发现其实选题设计中是不允许插线过天花板,这就意味着,习惯上以较高的那个插座向下引线,而不是较低的那个插座向上引线,即便是没穿天花板。然后,图18下的图a和图b表示横跨邻墙的走法,这两种本质上是一样的分析方式,但计算的时候不可忽略其中任何一种。
    最后,计算出图a的s1,图b的s2和图c的s3后,比较三者中最小的即可求得最短布线。
    4.1.3.2 前提是¬墙面上有门此时,【4.1.2 如何将邻墙和同墙的情况化归为同墙求两插座最短布线问题(只走墙面)】中两插座最短布线的挑选是建立在只走墙面的前提,在此基础上,就需要补充上可以走地脚线和走地板,这样子才适用于有门的情况。
    4.1.4 有门情况如何判断插座连线穿不穿门穿门概念的强调:这里的“穿门”首先不是指插座在门上后连线的意思,因为这在初始化门和插座时,程序会进行异常判断,只要出现插座装在门上,就会抛出异常,终止编译,所以这是不可能出现在“穿门”的意思理解上,而“穿门”在这里的意思是假定不存在门时,按照正常情况连线两插座,后在其连线通过的任一墙面上插进一扇门,若门跨过了连线,这样子才叫做“穿门”。
    那判断穿不穿门,最简单的方式,可以想到,只要两插座距离地板最高的那个Height的比门顶线的Height还低,或者插座一直处于地脚线上,这两种情况,都是绝对不穿门的情况。
    然后剩下的其他情况都是穿门的,而穿门情况也是存在三种位置关系,进而使用上述【4.1.3 在两插座的三种关系中的每种关系下,对4.1.2中两插座最短布线的挑选】的求解思路。
    4.1.5 最小生成树中用于不相交集合的高级数据结构(并查集)的理解
    该图是我参考文献后和自己理解后,自己制作的所需的算法层次示意图,黄色高亮部分表示我有落实用到的,属于对并查集的初步理解使用,更高级的优化,我仍然看不懂,因为基础知识储备有限,具体的使用请见【4.2算法说明】下的【4.2.2 最小生成树求解之Kruskal算法】
    4.2 主要算法的说明本选题实验主要涉及到两种核心重难点算法,即墙有门时两顶点对墙和邻墙化归同墙算法、以用于不相交集合的高级数据结构(并查集)为前提的最小生成树Kruskal算法。
    其中,一方面,墙有门时两顶点对墙和邻墙化归同墙算法主要涉及到布尔代数的灵活运用,这也说明了本实验也偏向于使用函数式的编程范式进行编程实验活动的一次实验;另一方面,用于不相交集合的高级数据结构(并查集)算法是为最小生成树之Kruskal算法做预先准备的。除此之外,还涉及到排序算法这样重要但不是选题实验难点的算法。
    下面分别介绍这两种算法的设计思想。
    4.2.1 对墙和邻墙有门时两插座化归同墙插座求解问题的算法图20,同墙情况:很明显采用的是isTogether(_:_:_:)和findTogetherLowcost(_:_:_:_:_:_:) 算法。

    图21,邻墙情况:很明显采用的是isBeside (_:_:_:)和findBesideLowcost(_:_:_:_:_:_:) 算法。

    图22,对墙情况:很明显采用的是isAcross(_:_:_:)和findAcrossLowcost(_:_:_:_:_:_:)算法。

    4.2.2 最小生成树求解之Kruskal算法对于最小生成树的问题的求解,涉及到的是两个经典的算法,分别是Prim算法和Kruskal算法,在本选题实验中,更加适合选择使用Krusakl算法,因为Kruskal算法是逐步增加生成树的边,与Prim算法相比,可以称之为“加边法”,插线的长度就与边及其权值直接关联,与室内布线问题的初衷就很契合。
    Kruskal算法的具体思想如下:
    假设存在连通图N=(V, E),将N中的边按照权值从小到大顺序排序。

    初始状态为只有n个顶点而无边的非连通图T=(V, {}),图中每个顶点自成一个连通分量
    在E中选择权值最小的边,若该边依附的顶点落在T中的不同的连通分量上(即不形成回路),则将此边加入到T中,否则舍去此边而选择下一条权值最小的边
    重复2,直至T中所有顶点都在同一连通分量上为止

    其中,上述描述隐含了一个高级数据结构,是用于不相交集合的数据结构,也称之为并查集。所以就有必要探讨该算法,因为我的初衷和目的是,发现选题实验要求中出现了最大的插座数N=20,一个房间中装上这么多的插座,单纯使用最小生成树固然能够完成,但是到了更大规模的插座时,必然会因为算法时间复杂度过大造成算法效率低下,所以我通过搜索引擎和《算法导论》书籍了解到了有这么一种数据结构,了解到并查集适用于所有集合的合并与查找的操作,进一步还可以延伸到一些图论中判断两个元素是否属于同一个连通块时的操作,更进一步了解到由于使用启发式合并和路径压缩技术,可以讲并查集的时间复杂度近似的看作O(1),空间复杂度是O(N),这样就将一个大规模的问题转变成空间极小、速度极快的简单操作。
    但是因为基础和能力有限,依然看不太懂《算法导论》并查集后部分的“按秩合并”和“路径压缩”的启发式策略,所以比较着看《算法导论》并查集前部分和严蔚敏《数据结构》(C语言)第2版P168~P170,主要理解并查集的核心思想,并用Swift语言实现了。
    其核心思想基本如下:
    设有一个动态集合S={S1, S2, S3, ……, Sn },每个集合通过一个代表来标识,代表就是动态集合S中的某个元素,接着用一个对象表示一个集合的每个元素,设x表示一个对象,则将会支持如下操作:

    MAKE-SET(x):建立一个新的集合,它的唯一元素是x,所以x是代表,同时,各个集合是不相交的,故x不会出现在别的某个集合中
    UNION(x, y):将包含x和y的两个动态集合(表示为Sx和Sy)合并成一个新的集合,即这两个集合的并集。假定在操作之前这两个集合是不相交的。虽然UNION的很多实现中特别的选择Sx或Sy的代表作为新的代表,然而结果集的代表可以是Sx U Sy的任何元素。由于要求各个集合不相交,故要“消除”原有的集合Sx和Sy,即把它们从S中删除。实际上,把其中一个元素并入另一个集合中,就达到了代替删除的操作
    FIND-SET(x):返回一个指针,这个指针指向包含x的(唯一)集合的代表

    5 测试5.1 实验组别及其截图测试前的存储准备:准备存储的三个房子,三扇门和三堆插座(4个,5个,20个)这三组相应的以各自元素为元素的二维数组,则意味着可以进行3*3*3=27组相对客观的事实验证的测试实验,但是由于论文篇幅有限,所以只进行三组测试,其中默认组就是课题要求验证的,即r1-d1-o1组,另外测试验证的两组分别为r1-d2-o2,r2-d1-o3。
    除此之外,房子,门,插座的创建和传值的异常不合法我都试过了,在main.swift源程序和TestCodes下三个源程序文件中有我结合使用条件语句和格式化输出语句,自己制作了简易的异常抛出检测代码块,同时由于Swift语言的存在可选数据类型,这样子程序编译抛出异常时,也会终止编译,而不会导致运行时错误,尽可能停在编译时错误,有需要我可以当场演示。
    多组测试输入数据的组织图如下所示:

    5.1.1 第一组:r1-d1-o1


    结合立体图和手算,结果一致,符合预期。
    5.1.2 第二组:r1-d2-o2



    结合立体图和手算,结果一致,符合预期。
    5.1.3 第三组:r2-d1-o3




    没有手算,数据量太多,根据程序设计的可靠性,外推结论,结果正确,符合预期。
    6 总结6.1 任务完成情况全面完成了课程设计任务,达到了相关要求,具体表现在:

    能够完成算法,正确地输入、输出内容,并且有充分的注释
    代码总量达到1000+级别
    优化格式化的输出结果,表现在有控制台输出立方图,更加直观
    程序适用于一般情况,具备一般性检验机制,涵盖更广的插座位置情况
    程序具备异常输入值的检测,自己结合if条件语句和格式化输出语句写了简易的的异常判断并抛出错误最后终止编译的代码
    为了避免输入若干组坐标等数据键入失误,我把房子,门的门角,插座集合的数值和坐标事先存储在三个二维数组里面,最后只需在main.swift通过程序手势编号指令修改三组数组下标共三次,完成一次实验测试数据输入。程序手势编号指令请见【5.2 实验组别及其截图】表格
    使用到了并查集这样子的高级数据结构;
    课程设计的报告文中全部图文均为自己原创,通过PPT和PS制作,画质和表现力精良;
    使用了开源的编程语言Swift语言完成工程项目实现。

    6.2 不足与改进设想6.2.1 不足的地方
    程序只能通过控制台输出
    程序代码不是最优的,时间复杂度较大的情况仍不可避免
    最小生成树算法只使用了Kruskal算法,没有写Prim算法

    6.2.2 改进设想
    使用Cocoa框架下的GUI,尝试过但是还有很多不懂的,放弃之
    重新修改代码,减少嵌套使用多层循环语句和条件语句
    有空尝试重新用Prim算法再写一遍最小生成树算法

    附录一 实验环境


    电脑
    系统
    集成开发工具
    编程语言
    编译器




    MacBook Pro
    macOS High Sierra
    Xcode
    Swift4.1
    LLVM-Clang



    附录二 用户手册截止到我完成课程设计,Swift语言的版本为Swift4.2,当前使用的是Swift4.1.2版本,Swift语言与C语言有很大的差别,Swift工程里面没有主函数main( ),整个工程项目的入口是一个main.swift源程序文件,可以简单理解C语言里面的主函数main( )与Swift语言中程序入口main.swift是一样子的。
    工程项目编译通过在控制台打开的同时会在Products的目录组中生成一个命名与工程项目名称一样的“UNIX可执行文件”,可以认为跟Windows平台下生成的以exe为扩展名的可执行文件是相同的,但是该文件是通过Xcode编译生成的,只能在macOS中的终端Terminal运行,因为macOS属于类UNIX操作系统,与Linux属于同大分支操作系统,所以我亲身尝试在Linux的一个最新发行版服务器版Ubuntu 18.04上面的终端Terminal打开这个,发现会报错,截图对比如下:
    macOS



    Ubuntu Linux

    到目前为止,Swift语言支持的平台只有macOS和Linux,需要在Linux下执行Swift工程项目,就必须下载Swift for Linux打包语言程序,解包安装需要的环境,这样子才能在Linux重新编译原工程文件,生成一个在Linux下能打开的UNIX可执行文件,我暂未尝试过,Windows平台目前还没有出现Swift for Windows的开发环境和工具集。
    1 评论 1 下载 2018-11-05 17:21:18 下载需要6点积分
  • 基于C#实现的坦克大战游戏的最短路

    1 项目概述1.1 项目背景《坦克大战》(Battle City)是1985年日本南梦宫Namco 游戏公司开发并且在任天堂FC平上,推出的一款多方位平面射击游戏。游戏以坦克战斗及保卫基地为主题,属于策略型联机类。本项目(《坦克大战最短路》)就是以《坦克大战》作为背景并结合广度优先算法实现的一款“最短路”游戏。
    该游戏包含的游戏对象

    坦克
    砖块
    钢墙
    河水
    子弹
    星星

    该游戏目标
    坦克要在尽可能小的消耗到达星星的位置。在此约定,坦克每前进一步或是改变一次方向都消耗一个能量值。坦克不能穿过砖块、钢墙、河水等障碍物,但是可以发射子弹(保证坦克拥有足量的子弹)对砖块、钢墙进行摧毁。其中摧毁砖块需要消耗一个能量值,摧毁钢墙需要消耗两个能量值。
    1.2 功能需求1.2.1 核心功能
    开始新游戏
    绘制地图: 手动绘制和自动绘制
    模式选择:自动模式和手动模式

    1.2.2 其他功能
    自带截图
    实时显示当前能量消耗

    1.3 非功能需求1.3.1 界面
    图形界面,具有良好的菜单层次结构,简单清晰
    实时显示当前系统时间
    实时显示当前鼠标坐标和当前坦克坐标

    1.3.2 操作操作方式友好,支持鼠标和键盘操作,并且具有较好的容错能力,用户在使用过程中,除了规定的按键外,其他按键均忽略,不予处理。<br>
    1.3.3 运行环境(软件)
    操作系统:Windows XP 及以上版本
    框架:.NET Framework V4.0 及以上版本

    二、系统设计2.1 详细设计2.1.1 算法设计算法主要包括两个:优先队列和广度优先搜索,接下来分别进行介绍。
    优先队列(priority queue)
    普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (largest-in,first-out)的行为征。
    广度优先搜索(Breadth First Search)
    广度优先搜索 ,常常与深度优先搜索并列提及。这是一种相当常用的图算法,其特点是:每次搜索指定点,并将其所有未访问过的近邻加入搜索队列(而深度优先搜索则是栈),循环搜索过程直到队列为空。
    《坦克大战最短路》实际上就是求两点之间的的路径,可以采用搜索算法(BFS和DFS) 。但由于要求的是最短路径,所以采用BFS效率会高出许多。另外,这个图每向前拓展一个节点,其权值很可能是不一样的,因此我还要保证每次用队列中取出的节点权值要最小,所以还需要用到优先队列算法。二者相结合也就实现了该游戏的核心功能。
    2.1.2 编程环境
    操作系统: Windows 8.1 专业版(64位)
    编程工具: Microsoft Visual Studio Professional 2013
    编程语言: C#、C++

    2.1.3 具体实现游戏界面采用C#实现,内部核心算法采用C++实现。(用C++编写的程序生成DLL 动态链接库,直接导入到C# 当中)
    2.1.3.1.界面地图

    大小 12*12 每个方格 边长60个像素
    左上角为原点(0, 0)

    对象

    坦克(Tank)
    砖块(Brick) 1次打破
    钢墙(Steel) 2次打破
    河水(River) 子弹可以穿过,坦克不可以
    星星(Star)
    子弹(Bullet) 可以对障碍物进行摧毁

    菜单

    添加对象
    手动模式
    自动模式
    自动生成地图
    手动绘制地图
    截取屏幕

    显示

    当前能量消耗
    当前鼠标坐标
    当前坦克坐标
    当前系统时间
    游戏规则说明

    三、总体结构3.1 类图
    3.2 类设计3.2.1 游戏父类 GameObject属性

    x 游戏对象横坐标
    y 游戏对象纵坐标
    width游戏对象图片宽度
    height width游戏对象图片高度
    image游戏对象图片

    方法

    构造函数(初始化)
    Draw(); 游戏对象绘制方法
    GetRectangle(); 获取游戏对象

    3.2.2 墙壁父类 WallFather:GameObject属性

    +life 生命值
    方法

    构造函数(初始化)
    重写Draw(); 绘制游戏对象
    IsOver(); 判断是否到被子弹摧毁

    3.2.3 River&Star父类 RSFather:GameObject**方法

    构造函数(初始化)
    重写Draw(); 绘制游戏对象

    3.2.4 Bullet :GameObject属性

    +power 火力值
    方法

    构造函数(初始化)
    重写Draw();

    3.2.5 Tank: GameObject 游戏对象方法

    重写Draw(g); 绘制游戏对象
    Move(); 移动
    Fire(); 开火

    3.2.6 SingleObject 单例对象方法

    GetSingle(); 获取单例对象
    Draw(); 绘制对象
    Check(); 边界检查

    4 游戏截图游戏地图编辑绘制

    游戏画面1

    游戏画面2
    1 评论 25 下载 2018-11-05 17:00:15 下载需要10点积分
  • 基于Shadowsocks的科学上网用户管理系统APP的设计与实现

    一、课程设计概述1.1 目的对于中国网络的封锁,中国网民失去了一笔宝贵的财富,在程序上的一些错误国外的程序员有着更深入的了解跟解决办法,这些资料大多藏匿于Google,中国的程序员想要使用Google搜索引擎就只有科学上网这一条路了。所以Shadowsocks(众多科学上网工具之一,较为稳定)诞生了。但是个人租用一台服务器浪费了大量的资源,闲置的部分又无法利用。这样,多人合租模式就出现了。我们需要搭建一个科学上网用户管理系统,管理每一个节点的用户,给用户分配适当流量,带宽,当然用户需要支付一定费用用来购买流量。定时提醒余额不足用户,定时清理长时间未使用用户。
    总体上按照软件生命周期的六个阶段:计算机系统工程、需求分析、设计、编码、测试、运行和维护来进行。
    具体地,我们首先进行项目的可行性研究与分析确定系统项目的目标和功能,进而编写项目可行性报告,接下来编写项目开发计划文档;进行全面的需求分析阶段,准确定义系统的目标,即系统“做什么”的问题,获得需求规格说明书;进行设计阶段分为概要设计和详细设计,概要设计即设计软件的结构,包括组成模块、模块的层次结构、模块的调用关系、每个模块的功能等,模块设计即为每个模块完成的功能进行描述,把功能描述变为精确的结构化的过程描述;进行编码阶段,即把每个模块的控制结构转化为计算机接受的程序代码;进行测试阶段,即在设计测试用例的基础上检验软件的各个部分,分为模块测试、组装测试和确认测试等;进行运行维护阶段就剩软件开发过程未发现的错误,增强改进和完善软件的功能和性能,以适应软件的发展,延长软件的寿命,使其创造更多的价值。
    1.2 开发环境
    服务器:Centos,OpenVZ
    开发工具:Android,Phpstorm,PhotoShop,Xampp(Apache,Mysql)

    二、可行性研究报告2.1编写目的可行性研究的目的是为了对问题进行研究,以最小的代价在最短的时间内确定问题是否可解。经过对此项目进行详细调查研究,初拟系统实现报告,对软件开发中将要面临的问题及其解决方案进行初步设计及合理安排。明确开发风险及其所带来的经济效益。本报告经审核后,交软件经理审查。
    2.2 项目背景本项目采用客户机/服务器原理,客户端的程序是建立在Android系统上以Android Studio为开发软件的应用程序,服务器端采用CentOS为操作系统的工作站,是采用Mysql的为开发软件的数据库服务程序。
    2.3可行性研究的前提
    主要功能:为科学上网用户提供一个可查余额,可查流量,可查上网时长等用户信息的平台
    性能要求:要求在线观看视频无卡顿,每个节点满足50用户同时在线
    输出要求:数据完整,详实
    输出要求:简捷,快速,实时
    安全与保密要求:只有管理员具有修改所有用户信息的权限
    硬件条件:服务器阿里云CentOS,android
    运行环境:Linux
    数据库:Mysql
    成本/效益分析结果,效益 〉成本
    技术可行,现有技术可完全承担开发任务。

    2.4 技术可行性分析提供科学上网的是一台美国洛杉矶的VPS,是科学上网的核心。用户服务平台是阿里云学生机,提供数据交换,信息展示。
    处理流程和数据流程图如下所示:

    三、软件需求说明3.1 科学上网用户管理系统的功能要求科学上网用户管理系统的总目标是:在计算机网络,数据库和先进的开发平台上,利用现有的软件,配置一定的硬件,开发一个具有开放体系结构的、易扩充的、易维护的、具有良好人机交互界面的科学上网用户管理系统,实现科学上网账号自动化的贩售系统,为用户提供一个公开透明的信息查询平台。
    根据可行性研究的结果和客户的要求,分析现有情况及问题,采用Client/Server结构,将科学上网用户管理系统划分为两个子系统:客户端子系统,服务器端子系统。
    下面分析各个子系统的功能需求:
    3.1.1 客户端子系统在客户端系统的功能实现上,可以分为以下几个部分:

    科学上网账号注册及修改密码:在客户端可以实现免邀请码注册(限时开放)。修改科学上网连接密码以及账号密码的修改
    用户流量使用信息查询在客户端用户可以查询流量的使用情况
    弹幕以及版本更新的推送在客户端用户之间可以通过弹幕的形式进行交流,还有新版本的更新推送
    新闻资讯浏览以利用知乎提供的新闻API进行整合,形成了新闻资讯模块

    3.1.2 服务器端的功能要求通过计算机网络将客户端与服务器的数据库相连,将从客户端得到的信息进行处理,实现流量查询,密码修改,新闻资讯浏览等子系统。
    在客户端系统的功能实现上,可以分为以下几个部分:

    接收由用户发送的弹幕信息:通过网络接收用户弹幕信息存入服务器数据库
    生成系统信息:根据用户数量,服务器流量消耗,生成一个明确的系统信息
    传递更新信息到客户端:把新的版本推送到客户端
    接收用户的弹幕评论:弹幕墙功能具有展示用户弹幕所有信息,用户可以在线发送弹幕评论
    推送余额不足到客户端:根据用户的流量使用情况,及时推送余额不足信息给用户

    3.2 科学上网用户管理系统的性能需求为了保证系统能够长期、安全、稳定、可靠、高效的运行,科学上网用户管理系统应该满足以下的性能需求:
    3.2.1 系统处理的准确性和及时性系统处理的准确性和及时性是系统的必要性能。在系统设计和开发过程中,要充分考虑系统当前和将来可能承受的工作量,使系统的处理能力和响应时间能够满足企业对信息处理的需求。
    3.2.2 系统的开放性和系统的可扩充性在开发过程中,应该充分考虑以后的可扩充性。所有这些,都要求系统提供足够的手段进行功能的调整和扩充。而要实现这一点,应通过系统的开放性来完成,既系统应是一个开放系统,只要符合一定的规范,可以简单的加入和减少系统的模块,配置系统的硬件。通过软件的修补、替换完成系统的升级和更新换代。
    3.2.3 系统的易用性和易维护性科学上网用户管理系统是直接面对使用人员的,而使用人员往往对计算机并不时非常熟悉。这就要求系统能够提供良好的用户接口,易用的人机交互界面。要实现这一点,就要求系统应该尽量使用用户熟悉的术语和中文信息的界面;针对用户可能出现的使用问题,要提供足够的在线帮助,缩短用户对系统熟悉的过程。
    3.2.4 系统的标准性系统在设计开发使用过程中都要涉及到很多计算机硬件、软件。所有这些都要符合主流国际、国家和行业标准。例如在开发中使用的操作系统、网络系统、开发工具都必须符合通用标准。如规范的数据库操纵界面、作为业界标准的TCP/IP网络协议及ISO9002标准所要求的质量规范等;同时,在自主开发本系统时,要进行良好的设计工作,制订行之有效的软件工程规范,保证代码的易读性、可操作性和可移植性。
    3.2.5 系统的先进性目前计算系统的技术发展相当快,做为科学上网用户管理系统工程,应该保证系统在下个世纪仍旧是先进的,在系统的生命周期尽量做到系统的先进,充分完成企业信息处理的要求而不至于落后。这一方面通过系统的开放性和可扩充性,不断改善系统的功能完成。另一方面,在系统设计和开发的过程中,应在考虑成本的基础上尽量采用当前主流并先进且有良好发展前途的产品。
    3.2.6 系统的响应速度科学上网用户管理系统系统在日常处理中的响应速度为秒级,达到实时要求, 以及时反馈信息。在进行统计分析时,根据所需数据量的不同而从秒级到分级, 原则是保证操作人员不会因为速度问题而影响工作效率。
    3.3 科学上网用户管理系统的数据需求科学上网用户管理系统的数据需求包括如下几点:
    3.3.1 数据录入和处理的准确性和实时性数据的输入是否准确是数据处理的前提,错误的输入会导致系统输出的不正确和不可用,从而使系统的工作失去意义。数据的输入来源是手工输入。手工输入要通过系统界面上的安排系统具有容错性,并且对操作人员要进行系统的培训。
    在系统中,数据的输入往往是大量的,因此系统要有一定的处理能力,以保证迅速的处理数据。
    3.3.2 数据的共享与独立性整个机票预定系统的数据是共享的。然而,从系统开发的角度上看,共享会给设计和调试带来困难。因此,应该提供灵活的配置,使各个分系统能够独立运行,而通过人工干预的手段进行系统数据的交换。这样,也能提供系统的强壮性。
    3.4 科学上网用户管理系统的数据流图
    3.5 科学上网用户管理系统的数据逻辑模型科学上网用户管理系统的数据逻辑模型如下图所示:

    3.6 科学上网用户管理系统的运行要求科学上网用户管理系统中的各个子系统的硬件和软件的配置如下:
    3.6.1 服务器端子系统的运行要求
    系统软件: Linux
    数据库管理系统:Mysql
    硬件要求:以上CentOS 6, 1024M RAM, 20G HD

    3.6.2 客户端子系统的运行要求
    系统软件: Apache
    数据库管理系统:SQLite
    硬件要求:android4.4以上, 1048M RAM, 4.3G HD

    3.7 建立科学上网用户管理系统的约束3.7.1 Client/Server结构总体设计方案对它的约束科学上网用户管理系统做为Client/Server 结构的一个应用系统,不可避免的要受到Client/Server结构的约束。在其实施的各个阶段都要服从它的一些规划,包括功能设计、系统配置和计划。同时,由于信息的共享,用户管理系统还受到其它系统的信息约束。
    3.7.2 技术发展规律的约束计算机技术和产品的发展日新月异,将会给信息处理带来更多的手段,同时也会带来更加丰富的信息表达形式。例如图象和语音技术的进步,多媒体技术的发展,这些都要求系统在设计时考虑技术变化的可能性,为可能的变化预留一定的处理。
    四、概要设计4.1 任务概述系统将由两部分程序组成,安装在用户手机上的客户程序及阿里云内的数据服务器程序。
    个人独占国外服务器进行科学上网大量浪费资源,需要服务商进行统一管理,多人 合租服务器,资源得到合理分配。
    4.2 总体设计下面将使用(结构化设计)面向数据流的方法对机票预定系统的处理流程进行分析。系统可分为两大部分:客户机上的程序和服务器上的程序。以下将分别对系统的这两大部分进行流程分析:
    4.2.1 客户机程序流程客户端通过邮箱注册的账号密码进行客户端登录,登陆成功后会自动获取科学上网账号,客户端只需要启动开关就可以实现科学上网。

    4.2.2 服务器程序流程
    4.3 总体结构和模块外部设计下面以结构图来描述机票预定系统的软件总体结构。框内注明了模块的名字;方框之间的直线表示模块的调用关系。
    4.3.1 客户机部分
    4.3.2 服务器程序部分
    4.4 数据结构设计4.4.1 数据库数据结构设计DBMS 的使用上系统将采用Mysql,系统主要需要维护4张数据表:
    弹幕消息表

    广告投放表

    用户表

    新闻资讯表

    4.5 数据结构与程序的关系
    用户表存储用户信息,流量使用情况,注册日期等信息,客户端登录时需要验证账号密码是否正确通过该表验证
    弹幕消息表完成了弹幕的发送功能与展示功能,通过分页处理显示在弹幕墙
    新闻资讯表通过分页处理显示在新闻资讯功能
    广告投放表通过后台控制修改广告内容,存储在此表

    五、详细设计客户机模块结构图


    SplashActivity 开屏页,展示广告
    LoginActivity 登录界面,与服务器交换数据,登录成功获取科学上网账号
    WebActivity(账号注册/忘记密码)H5账号注册,修改密码
    MainActivity 浏览器主界面,接入Google,Youtube等web界面
    MenuLeftFragment 侧边抽屉(WebActivity{信息更新,用户中心,弹幕墙,系统信息,关 于};ZhihuActivity{知乎新闻界面};设置,退出应用)

    服务器模块结构图


    环境搭建使用Xampp(Apache,Mysql)
    使用PHP语言进行Mysql的操作(select,insert,update等)
    使用PHP语言返回Json数据提供给客户端
    Index.php Web端展示界面
    User Web端用户界面
    Admin Web端管理员界面
    Qiniu Web端管理员广告投放
    Wechat 提供客户端的H5界面
    Danmu 提供弹幕消息透传服务

    六、程序演示










    1 评论 3 下载 2018-11-05 16:53:34 下载需要20点积分
  • 基于Cocos2d-x实现的畜不及防鬼畜音乐节奏游戏

    1 开发环境
    Window10 下 VS2015,server.jar
    2 项目阐述2.1 简介这是一款类似节奏大师的游戏,结合 B 站上火爆且富有带感的鬼畜音乐,让玩家在游戏中挑战手速、准确性和迷之笑点。
    2.2 功能
    登录界面:新玩家输入姓名,点击“Play”、“Help”、“Rank”或“Exit”,依次实现进入开始游戏、新手帮助、玩家排名和退出游戏界面。同时,实现了自动登录的功能,为每个玩家保存数据
    游戏界面:

    玩家进入后会看到 6 个音轨,而且序列化的音符随机下落,左侧跳动的计时器,游戏分数和积聚的能量槽。还有供玩家直接退出的“exit”按钮
    随着玩家 游戏的进行,检测玩家的操作情况,并根据每次操作的准确性(即音符与相应位置的距离) 会在屏幕上即时显示“Miss”、“ Good”、“ Perfect”三种操作级别。这里“Miss”操作不会增加玩家的成绩和能量槽。否则添加相应的分数和显示玩家操作级别,鼓励玩家更快、更准
    当能量槽聚满之后,清屏条立即从上往下快速扫过,将所有屏幕上的音符消灭并有奖励分数, 缓解玩家游戏压力,增加用户体验
    在某些时间点会随机有音符飞出,用户必须在该音 符穿过的时间内按相应的键来实现切水果的效果,如果成功操作,音符一分为二(分开的两 部分也有自己的速度),然后受重力下落。否则该音符与边界碰撞后消失

    游戏结束:玩家可以选择重新开始游戏或退出

    2.3 服务器在这款游戏中,登陆、上传分数和排名等功能是直接使用了 14 周 TA 给的服务器(Windows 10 下) 。 使用时需在服务器所在目录打开命令提示符 CMD,输入 java -jar server.jar 则可运行服务器。
    2.4 亮点鬼畜音乐的结合,玩家数据保存及查看排名情况网络物理世界与碰撞游戏动画汇聚的能量槽向量队列等数据结构调度器及事件分发。
    3 项目展示游戏开始界面,右侧的四个按钮点击后跳转相应的界面

    游戏说明

    查看排名

    游戏界面

    不及时按钮“切掉”音符的话,音符走 与边界碰撞后消失

    按空格键将飞出的音乐切成两半,碰撞边缘也会被清除

    下面的图是 good 等级操作,意味着当玩家按下对应音轨的键时音符和固定的位置还有一定距离

    玩家判断精确,操作 perfect!

    能量槽聚满,清屏条快速向上消除所有音符,玩家获得相应的 bonus

    游戏时间到结束

    4 项目难点及解决方案在代码中碰到两个关于碰撞的问题:

    碰撞后在removeFromParentAndCleanup(true)函数后相应的指针并没有设置成空指针,这样导致运行时中断,通过处理相应位置的指针后问题依然存在,这是因为在游戏过程中不断的创建音符,所以就需要用向量来处理是比较合适的,这里解 决方案是设置状态变量来解决问题
    对CategoryBitmask、CollisionBitmask、 ContactTestBitmask这三个之间的关系的理解,一开始为了省事直接用的原来作业的参数。但是由于本次碰撞的对象较多,所以处理时有些问题,所以可以看出ContactTestBitmask是标明对和谁的碰撞检测感兴趣,请注意这不表示物体会发生碰撞,而是会不会传达碰撞。理解这之间的差 异,才可以明晰系统会不会调用监听器做出反馈

    另外就是击打音符分数等级判定的问题。分数等级有三种判定:Perfect, Good, Miss,因为音符是储存在队列中的,因此当音符消失时(击中音符或与清屏道具碰撞等情况)将队头的音符出队,故在队头的音符总是最接近音键的音符(即高度最低的音符)。当没有点击相应轨道的按钮时,音符直接与音键碰撞,则判定为Miss,这是在音符(note)与音键(key)的碰撞相应事件中判定的。
    而其他两种情况,则是在击打音键时计算音键与最近的音符(即队头的音符)的距离来判断分数等级。点击相应的按钮,在键盘响应事件onKeyPressed中则会调用checkMeet函数,如点击A键,则会向checkMeet函数传一个参数0,表示击打的是第0条轨道,此时checkMeet 函数就会计算第0条轨道中音键(key)与最近音符(note)的距离:(注:音键与轨道的锚点位置相同,故计算时可直接用轨道的位置计算)
    float distance = tracks[trackNum]->getPosition().getDistance(notes.front()->getPosition());
    当距离在半个音符大小范围内则判定为Perfect,当距离大于该距离且在一个音符大小范围内则判定 为Good。
    5 项目总结经过两次的课程项目,体会最深的是在实践中才能更好地掌握技术,以作业为驱动,在写自 己项目的过程中重温和学习以前的知识,尤其是在完成某一功能的过程中,你不得不去面对一大堆不 曾想过的问题,面对曾经模糊两可的知识点。这可能会打击一部分同学的积极型和继续向前的勇气, 但是只要我们相信自己,耐心去查资料、查文档,我想问题还是可以得以解决的,这之后是收获感、 是成就感、是快乐和能量。
    注重团队合作提高开发效率。本次课程的队友都是相当有想法灵感的,在完成作业的过程中 也非常认真,一起讨论分工合作,讨论遇到的问题。让我们感觉到团队的强大,互相学习、一起解决 问题。
    1 评论 9 下载 2018-11-05 16:15:24 下载需要6点积分
  • 基于Python的PyGame库实现的贪吃蛇小游戏

    1 项目介绍1.1 简介键盘上下左右控制蛇的前进方向,每吃到一个食物,蛇的长度增加一个单位,并生成一个新的食物,得分scores加一;当蛇撞到边界或自己时,游戏结束。时间time随蛇的步子增加,每走一步time加一。游戏结束后,按下空格键重新开始游戏,按下回车键结束游戏,退出。全程有音乐,退出后音乐也停止。
    1.2 开发环境
    开发语言:Python,pyCharm,pygame
    2 方案2.1 模块
    pygame
    sys
    random
    pyglet

    2.2 数据
    蛇类和食物类
    初始化窗口为600*600
    像素块为25*25
    蛇和食物都是正方形的结点

    2.3 接口
    蛇的身体设置为列表,初始化蛇有5节身体,依次递增
    食物为小正方形,随机生成,一次一个
    字体显示为函数控制

    2.4 类
    蛇类:初始化了各种有关蛇的属性。一开始初始化方向为向右,初始化蛇身为长度为五的列表。接着在蛇头处添加结点。再删除最后一个结点,判断是否死亡
    食物类:初始化食物小方块,随机设置食物位置,如果蛇吃到了食物,则抹掉了该食物,重新设置食物
    字体:设置字体,并且可以在窗口中显示

    2.5 流程
    先绘制窗口,设置窗口名字为“Snake Game”,设置时钟
    初始化分数scores和time为0,是否死亡属性为false
    初始化蛇类与食物类
    当正常运行时,如果检测到键盘上下左右输入了,则改变蛇前进方向
    如果碰到四周或者自己的身体,则死亡
    死亡后如果按空格键,则重新开始
    如果按回车键,则结束进程,游戏结束

    3 关键技术3.1 蛇身设为一个列表self.body = [] for x in range(5): self.addnode()
    3.2 音乐的播放pygame.init()pygame.mixer.init()sound = pygame.mixer.Sound("music.wav")sound.play()
    3.3 蛇增长的函数def addnode(self): left, top = (0, 0) if self.body: left, top = (self.body[0].left, self.body[0].top) node = pygame.Rect(left, top, 25, 25) if self.dirction == pygame.K_LEFT: node.left -= 25 elif self.dirction == pygame.K_RIGHT: node.left += 25 elif self.dirction == pygame.K_UP: node.top -= 25 elif self.dirction == pygame.K_DOWN: node.top += 25 self.body.insert(0, node)
    3.4 改变方向但是左右上下不能被逆向更改def chdirection(self, head): LR = [pygame.K_LEFT, pygame.K_RIGHT] UD = [pygame.K_UP, pygame.K_DOWN] if head in LR + UD: if (head in LR) and (self.dirction in LR): return if (head in UD) and (self.dirction in UD): return self.dirction = head
    4 结果和效果

    5 总结和不足这次贪吃蛇的实现对我来说有很大收获,python虽然是一门陌生的语言,但是却与之前学习过的c和c++有很大的相似性,学习起来也就轻松了很多。但是python也确实是一门新的语言,有些规则与c,c++毕竟是不一样的,还是有难度的。而且python的运行环境与vs不一样,运行所需要的库也不一样,这些不一样就造成了python的难度。虽然有些难度,但是学习起来的时候,能把所有的问题挨个解决的感觉也还是很好的。
    编程过程中有很多的问题,例如,文字的内容无法直接判断得出,我是一个个的测试,最后找到了最佳位置。加音乐的问题,我修改了好久的bug,一开始使用的pygame.mixer一直都显示有问题,无法打开mp3等,后来请教了老师,老师表示不要用mp3格式。但是我修改了格式,还是显示打不开文件。然后我上网换了另一种方法,运用系统的os来播放音乐,但是os是调用了系统自身的软件,打开了音乐播放器,而且当我游戏结束的时候无法正常关闭音乐。后来又找到了pyglet的模块,尝试使用,问题出现在只能播放音乐或者游戏,二者不能兼得,播放了音乐,游戏就卡住;开始游戏就无法正常播放音乐。最后找到了的方法是换音乐,用了一个纯wav格式的音乐,再次使用pygame的方法,这才成功。最后的教训在于不能直接改后缀名,要么就用正规的软件修改,要么就使用纯正的格式。
    在这一次的编写小游戏的过程中,我上网查阅了很多资料,绝大部分是英文的,这让我明白了英文在计算机领域的重要性。并且我认识到了我的不足,在编程过程方面我还有很多不足之处的,以后的道路任重道远,要不断充实自己,丰富自己,感谢老师和同学对我的帮助,通过这次学习,我学习到了很多知识,以及深刻了解到自学和英语的重要性。
    1 评论 22 下载 2018-11-05 16:11:15 下载需要7点积分
  • 基于C++实现的单词消除游戏(3个版本)

    1 题目一设计要求
    实现闯关者,出题者本地的注册,登录
    程序支持多人注册,同一时间只有一人可以登录
    任何角色均可查询所有闯关者,出题者,按照属性查找相应闯关者,出题者
    可以根据闯关者闯过关卡数,经验,等级等对闯关者排名,根据出题者出题数目,等级对出题者排名

    2 设计思路共设计了4个类:

    User-用户类
    Player-玩家类
    TestBuilder-出题者类
    Game-游戏类

    类继承关系图如下所示:

    类调用关系图如下所示:

    用户数据采用.csv文件的存储方式,存储格式对用户更加友好。有playerList.csv、testerList.csv、wordList.csv三个文件,分别存储挑战者信息、出题者信息、题库。

    采用容器的数据存储方式,存储方式更加灵活,长度可自由伸缩。
    为方便文件更新,自定义了字符分割数组函数:
    vector<string> split(const string& s, const string& delim);
    3 关键算法流程图功能模块图如下图所示:

    4 程序模块结构
    5 题目二设计要求
    必须在题目一的基础上进行修改
    请根据要求设计每一关的出题方式,注意随着关卡数增加,题目难度增加。请合理处理出题人新添加新词的使用方式,并且新加词组不会影响游戏难度
    设计闯关者经验值,等级增加策略。出题者等级升级策略

    6 设计思路及实现用二维vector容器 vector<vector> 组织单词,词库中的单词构成一个单词池,根据单词的长度来组织存储。每次出题时,系统从该单词池中按照关卡难度随机的选择相应长度的单词。随着关卡的升级,单词长度也越来越长。单词库效果图如下:

    出题者新加单词不会影响游戏难度,出题者新增的单词会被自动识别难度系数并插入到单词池的合理位置。(此处设计存储文件更新)
    实现方法

    闯关者及出题者升级策略为:

    7 关键算法流程图
    8 程序模块结构
    9 题目三设计要求
    除单人游戏外,增加双人对战游戏,要求参与闯关者均已经登录,双人同时面对一个单词,最先打出正确单词者获得经验增长,在双人对战中获胜所获得的经验增长 要高于 从同等难度的单人游戏中所获得的经验增长,失败者则需要扣除一定经验值
    可以查看同时在线的游戏闯关者,可以挑战在线的游戏玩家,被挑战者接受挑战后进入双人对战

    10 实现思路与实现
    使用socket进行通信技术
    采用客户端/服务器(C/S)处理模型

    客户端主要完成界面交互功能,如接收用户输入数据、显示服务端处理结果等服务端主要完成存储和计算等处理功能,如完成登录/注销操作、存取数据、处理排序等,所有闯关者,出题者信息保存在服务器
    增加了对战类Battle, 用于实现双人对战。关于实现双人对战的方式,涉及操作双线程的问题,由于两个客户端分别通过两个线程与服务器交互 ,为了实现对战的同步性,所以对战的信息应该以全局变量的形式存储。对战过程中两个玩家可以同步获取对战信息,否则,不能保证对战的同步性。为此,增加了双人对战类Battle, Battle类持有两个挑战者的socket等信息,以便于与两个用户进行及时通信。Battle类主要属性设计如下:


    闯关者可通过服务器端向在线玩家发送消息邀其进行对战,对方接受后进入对战模式。

    对战过程中,服务器同时向两客户端发送数据,对战中及时更新存放在服务器端的用时等数据信息,通知对战对象对战结果。具体实现如下:


    采用tcp多线程通信技术,服务器收到一个客户端请求,就给其分配一个线程与其通信,与此同时,记录该客户端端口号对应的闯关者。便于查看在线用户列表及进行双人对战
    实现方法:
    服务器收到一个客户端请求,就给其分配一个线程:

    11 服务器端关键算法流程图
    12 程序模块结构
    13 实验总结与感想前两个题目实现过程相对顺利,没遇到太大的困难,主要的难点是我设计的文件的更新与定位操作。关于最后一个题目,自学了socket网络编程的部分内容,实现的最后一个题目的设计,在设计双人对战模式的时候,我想出了两个设计方案:

    方案一:两个挑战者分别在各自的线程中答题,由于的局部变量,最终各自的答题用时等信息必须发送给对方从而判定对战结果
    方案二:在服务器端设计全局变量用于存储两个挑战者各自用时等信息,服务器端通过全局变量可直接判定对战结果然后通知对战者

    比较上述两个方案,在对战过程中,方案一仍然需要两个客户端进行通信; 而方案二不需两个客户端再次进行通信。显然方案二的实现效率更高,且新增对战类使系统易于维护。于是我选择了方案二并加以实现。
    实验中遇到的较大的Bug涉及文件更新操作,由于针对特定的某一行进行操作,重新写数据的时候可能会发生内存覆盖,所以一定要为每一行分配足够的缓存。
    通过实验,再实践中进一步熟悉了C++语言的基本语法规则,掌握了基本的面向对象的程序设计方法及各种面向对象的程序设计技术。最重要的是体会到了掌握新技能的兴奋之感,感觉编程能力又有了一定程度地提高,并且对编程提高了兴趣。虽然编写代码的过程中会遇到各种棘手的问题,但解决问题之后的快感是令人振奋的。问题会有的,解决问题的方法也会随之到来!
    14 程序使用说明
    本程序的开发环境为:操作系统-Win7操作系统
    集成开发环境-Microsoft Visual Studio 2013
    编译器-MSVC编译器
    系统为便于管理用户,默认出题者的用户名以’t’开头。出题者注册时,用户名需要以’t’开头,其他情况下默认为玩家注册,而挑战者注册不可使用以’t’开头的用户名,否则默认为出题者注册
    用户需正常退出,以保证系统信息的正常更新

    15 程序截图主界面

    注册

    登录

    开始游戏

    游戏画面
    1 评论 182 下载 2018-11-05 16:04:14 下载需要6点积分
显示 735 到 750 ,共 15 条
eject