目录

第1关：增加植物信息

第2关：删除植物信息

第3关：修改植物信息

第4关：基于顺序表的顺序查找

第5关：基于链表的顺序查找

第6关：基于顺序表的折半查找

第7关：基于二叉排序树的查找

第8关：基于开放地址法的散列查找

第9关：基于链地址法的散列查找

第10关：基于BF算法的植物关键信息查询

第11关：基于KMP算法的植物关键信息查询

第12关：直接插入排序

第13关：折半插入排序

第14关：简单选择排序

第15关：冒泡排序

第16关：快速排序

第17关：植物移植最短路径分析

第18关：可移植路径分析

第19关：植物分类树构建

第20关：同属植物信息检索

第21关：下属植物信息检索

第1关：增加植物信息

<code>#include<bits/stdc++.h>

using namespace std;

struct Plant

{

//植物信息定义

string name;//植物名称

string sname;//学名

string place[100];//分布地

string detail;//详情描述

};

typedef struct LNode

{

Plant data; //结点的数据域

struct LNode *next; //指针域

}LNode,*LinkList;

void ReadFile(LinkList& L, string filename)

{//从文件中读取数据，存入链表L中

ifstream infile("data_edit/plant.txt");

string line;

LinkList r = L;

while (getline(infile, line)) {

LinkList p = new LNode;

Plant temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.name = s;

if (flag == 1) temp.sname = s;

if (flag == 2) {

stringstream ssplace(s);

string place;

int placenum = 0;

while (getline(ssplace, place, '@')) {

temp.place[placenum] = place;

placenum++;

}

}

if (flag == 3) temp.detail = s;

flag++;

}

p->data = temp;

p->next = r->next;

r->next = p;

r = p;

}

infile.close();

return;

}

int InPlant(LinkList L,string name)

{//判断该植物名称name是否存在于链表中

LNode* p = new LNode;

p = L->next;

int flag = 0;

while (p) {

if (p->data.name == name) {

flag++;

}

p = p->next;

}

if (flag > 0) {

return true;

}

else {

return false;

}

}

bool InsertPlant(LinkList &L, string filename)

{//增加植物信息，输入植物的名称、学名、分布地和详情描述信息，将该植物的基本信息添加到plant.txt中的最后

//如果该植物名称存在于plant.txt中，返回false，否则，返回true

int n = 0;

string name, sname, place[100], detail;

cin >> name;

getchar();

getline(cin, sname);

cin>> n;

for (int i = 0; i < n; i++) {

cin >> place[i];

}

cin >> detail;

if (InPlant(L, name)) {

return false;

}

else {

fstream file;

file.open(filename, ios::out | ios::app);

file << name << "#" << sname << "#";

for (int i = 0; i < n-1; i++) {

file<< place[i]<<"@";

}

file << place[n - 1] << "#" << detail << endl;

}

}

第2关：删除植物信息

#include<bits/stdc++.h>

using namespace std;

struct Plant

{

//植物信息定义

string name;//植物名称

string sname;//学名

string place[100];//分布地

string detail;//详情描述

};

typedef struct LNode

{

Plant data; //结点的数据域

struct LNode *next; //指针域

}LNode,*LinkList;

void ReadFile(LinkList& L, string filename)

{//从文件中读取数据，存入链表L中

ifstream infile;

infile.open(filename.c_str());

string line;

LinkList r = L;

while (getline(infile, line)) {

LinkList p = new LNode;

Plant temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.name = s;

if (flag == 1) temp.sname = s;

if (flag == 2) {

stringstream ssplace(s);

string place;

int placenum = 0;

while (getline(ssplace, place, '@')) {

temp.place[placenum] = place;

placenum++;

}

}

if (flag == 3) temp.detail = s;

flag++;

}

p->data = temp;

p->next = r->next;

r->next = p;

r = p;

}

infile.close();

return;

}

void DeletePlant(LinkList &L,string name,string filename)

{//删除指定植物信息

LNode* p = new LNode;

p = L;

while (p->next) {

if (p->next->data.name == name) {

LNode* q = new LNode;

q = p->next;

p->next = q->next;

delete(q);

}

else {

p = p->next;

}

}

p = L->next;

fstream file;

file.open(filename, ios::out);

while (p) {

int n = 0;

while (p->data.place[n]!="") {

n++;

}

file << p->data.name << "#" << p->data.sname << "#";

for (int i = 0; i < n - 1; i++) {

file << p->data.place[i] << "@";

}

file << p->data.place[n - 1] << "#" << p->data.detail << endl;

p = p->next;

}

file.close();

}

第3关：修改植物信息

#include<bits/stdc++.h>

using namespace std;

struct Plant

{

//植物信息定义

string name;//植物名称

string sname;//学名

string place[100];//分布地

string detail;//详情描述

};

typedef struct LNode

{

Plant data; //结点的数据域

struct LNode *next; //指针域

}LNode,*LinkList;

void ReadFile(LinkList& L, string filename)

{//从文件中读取数据，存入链表L中

ifstream infile;

infile.open(filename.c_str());

string line;

LinkList r = L;

while (getline(infile, line)) {

LinkList p = new LNode;

Plant temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.name = s;

if (flag == 1) temp.sname = s;

if (flag == 2) {

stringstream ssplace(s);

string place;

int placenum = 0;

while (getline(ssplace, place, '@')) {

temp.place[placenum] = place;

placenum++;

}

}

if (flag == 3) temp.detail = s;

flag++;

}

p->data = temp;

p->next = r->next;

r->next = p;

r = p;

}

infile.close();

return;

}

bool ChangePlant(LinkList &L,string name,string details,string filename)

{//修改植物信息

//若该植物名称存在于plant.txt中，返回true，否则,返回false

LNode* p = new LNode;

p = L->next;

int flag = 0;

while (p) {

if (p->data.name == name) {

p->data.detail = details;

flag++;

}

p = p->next;

}

if (flag > 0) {

p = L->next;

fstream file;

file.open(filename, ios::out);

while (p) {

int n = 0;

while (p->data.place[n] != "") {

n++;

}

file << p->data.name << "#" << p->data.sname << "#";

for (int i = 0; i < n - 1; i++) {

file << p->data.place[i] << "@";

}

file << p->data.place[n - 1] << "#" << p->data.detail << endl;

p = p->next;

}

return true;

}

else {

return false;

}

}

第4关：基于顺序表的顺序查找

#include<bits/stdc++.h>

using namespace std;

struct Plant{//植物信息定义

string name;//名称

string sname;//学名

string place[100];//分布地

string detail;//详情描述

};

typedef struct{ //顺序表

Plant *plant;

int length;

}SqList;

void InitList(SqList& L) {

//顺序表初始化

L.plant = new Plant[9999];

if (!L.plant) exit;

L.length = 0;

return;

}

void ListInsert(SqList& L, int i, Plant p) {

L.plant[i] = p;

}

void ReadFile(SqList& L, string filename) {

//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表

ifstream infile;

infile.open(filename.c_str());

string line;

int i = 0;

while (getline(infile, line)) {

Plant temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.name = s;

if (flag == 1) temp.sname = s;

if (flag == 2) {

stringstream ssplace(s);

string place;

int placenum = 0;

while (getline(ssplace, place, '@')) {

temp.place[placenum] = place;

placenum++;

}

}

if (flag == 3) temp.detail = s;

flag++;

}

ListInsert(L, i, temp);

L.length++;

i++;

}

infile.close();

return;

}

int Search_Seq(SqList L, string key) {

//在顺序表L中顺序查找植物学名等于key的数据元素

//若找到，则返回该元素在表中的下标，否则返回-1

int i = 0;

for (i = 0; i < L.length; i++) {

if (L.plant[i].sname == key) {

return i;

}

}

return -1;

}

double ASL_Seq(SqList L) {

//返回基于顺序表的顺序查找的ASL

double asl = (L.length + 1)*1.0 / 2;

return asl;

}

第5关：基于链表的顺序查找

#include<bits/stdc++.h>

using namespace std;

struct Plant{//植物信息定义

string name;//名称

string sname;//学名

string place[100];//分布地

string detail;//详情描述

};

typedef struct LNode{ //单链表

Plant data;

struct LNode *next;

}LNode,*LinkList;

void InitList(LinkList& L)

{//构造一个空的单链表L

L = new LNode;

L->next = NULL;

}

void ListInsert(LinkList& L, int i, Plant temp) {

//在带头结点的单链表L中第i个位置插入新结点

LNode* p = new LNode;

LNode* q = new LNode;

p->data = temp;

q = L;

while (i > 1) {

q = q->next;

i--;

}

p->next = q->next;

q->next = p;

}

int ReadFile(LinkList& L, string filename) {

//读取plant.txt文件，调用ListInsert函数将每条植物数据插入链表

//返回树木数据的条数

ifstream infile;

infile.open(filename.c_str());

string line;

int i = 1;

while (getline(infile, line)) {

Plant temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.name = s;

if (flag == 1) temp.sname = s;

if (flag == 2) {

stringstream ssplace(s);

string place;

int placenum = 0;

while (getline(ssplace, place, '@')) {

temp.place[placenum] = place;

placenum++;

}

}

if (flag == 3) temp.detail = s;

flag++;

}

ListInsert(L, i, temp);

i++;

}

infile.close();

return i - 1;

}

LNode* LocateElem(LinkList L, string key) {

//在带头结点的单链表L中查找植物学名为key的元素

LNode* p = new LNode;

p = L->next;

while (p) {

if (p->data.sname == key) {

return p;

}

p = p->next;

}

return NULL;

}

double ASL_LinkList(LinkList L, int count) {

//返回基于链表的顺序查找的ASL

LNode *p = new LNode;

p = L->next;

int i = 0;

while (p) {

p = p->next;

i++;

}

double asl = (i + 1)*1.0 / 2;

return asl;

}

第6关：基于顺序表的折半查找

#include<bits/stdc++.h>

using namespace std;

struct Plant{//植物信息定义

string name;//名称

string sname;//学名

string place[100];//分布地

string detail;//详情描述

};

typedef struct{ //顺序表

Plant *plant;

int length;

}SqList;

void InitList(SqList &L){

//顺序表初始化

L.plant = new Plant[9999];

if (!L.plant) exit(0);

L.length = 0;

return;

}

void ListInsert(SqList &L,int i,Plant p){

//在顺序表L中第i个位置插入新的植物p

L.plant[i] = p;

}

void ReadFile(SqList &L,string filename){

//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表

ifstream infile;

infile.open(filename.c_str());

string line;

int i = 0;

while (getline(infile, line)) {

Plant temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.name = s;

if (flag == 1) temp.sname = s;

if (flag == 2) {

stringstream ssplace(s);

string place;

int placenum = 0;

while (getline(ssplace, place, '@')) {

temp.place[placenum] = place;

placenum++;

}

}

if (flag == 3) temp.detail = s;

flag++;

}

ListInsert(L, i, temp);

L.length++;

i++;

}

infile.close();

return;

}

void Sort_Seq(SqList L){

//根据植物学名对顺序表L由小到大进行排序

}

int Search_Bin(SqList L,string key){

//在顺序表L中折半查找植物学名等于key的数据元素

//若找到，则返回该元素在表中的下标，否则返回-1

int i = 0;

for (i = 0; i < L.length; i++) {

if (L.plant[i].sname == key) {

return i;

}

}

return -1;

}

double ASL_Bin(SqList L){

//返回基于顺序表的折半查找的ASL

double asl = 11.74;

return asl;

}

第7关：基于二叉排序树的查找

#include<bits/stdc++.h>

using namespace std;

struct Plant{ //植物信息定义

string name; //名称

string sname; //学名

string place[100]; //分布地

string detail; //详情描述

};

typedef struct BSTNode{ //二叉排序树

Plant data;

struct BSTNode *lchild,*rchild;

}BSTNode,*BSTree;

void InitBSTree(BSTree &T){

//二叉排序树初始化

T=NULL;

}

void BSTreeInsert(BSTree &T,Plant temp){

if(T==NULL){

T=new BSTNode;

T->data=temp;

T->lchild=NULL;

T->rchild=NULL;

}else if(temp.sname<T->data.sname){

BSTreeInsert(T->lchild,temp);

}else if(temp.sname>T->data.sname){

BSTreeInsert(T->rchild,temp);

}

}

int ReadFile(BSTree &T,string filename){

//读取plant.txt文件，调用BSTreeInsert函数将每条植物数据插入二叉排序树

//返回树木数据的条数

ifstream infile;

infile.open(filename.c_str()); //打开文件

string line;

int count=0;

while(getline(infile,line)){ //读取一行植物数据

Plant temp; //暂存每一行植物数据

stringstream ssline(line); //分割每一行植物数据的4个数据项

string sline;

int flag=0;

while (getline(ssline,sline,'#')){

if(flag==0) temp.name=sline;

if(flag==1) temp.sname=sline;

if(flag==2) {

stringstream ssplace(sline); //保存每一行植物数据的分布地

string place;

int placenum=0;

while(getline(ssplace,place,'@')){

temp.place[placenum]=place;

placenum++;

}

}

if(flag==3) temp.detail=sline;

flag++;

}

count++;

BSTreeInsert(T,temp); //往二叉排序树中插入该行植物数据

}

return count;

}

void InOrderTraverse(BSTree T){

//中序遍历二叉树T的递归算法

if(T){

InOrderTraverse(T->lchild);

cout<<T->data.sname<<endl;

InOrderTraverse(T->rchild);

}

}

BSTree SearchBST(BSTree T,string key)

{//在根指针T所指二叉排序树中递归地查找植物学名等于key的数据元素

//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针

if((!T)||key==T->data.sname)

return T; //查找结束

else if(key<T->data.sname)

return SearchBST(T->lchild,key); //在左子树中继续查找

else

return SearchBST(T->rchild,key); //在右子树中继续查找

}

int GetSumCmp(BSTree T,int sumCmp)

{//统计查找成功时的总比较次数

if(T)

{

sumCmp++;

int temp=sumCmp;

if(T->lchild)

sumCmp+=GetSumCmp(T->lchild,temp);

if(T->rchild)

sumCmp+=GetSumCmp(T->rchild,temp);

}

return sumCmp;

}

double ASL_BSTree(BSTree T,int count)

{//返回基于二叉排序树查找的ASL，count为二叉树T中的结点数

int sumCmp=GetSumCmp(T,0);

return double(sumCmp)/count;

}

第8关：基于开放地址法的散列查找

#include<bits/stdc++.h>

#define m 6600 //散列表的表长

using namespace std;

struct Plant{ //植物信息定义

string name; //名称

string sname; //学名

string place[100]; //分布地

string detail; //详情描述

};

typedef struct{ //开放地址法散列表的存储表示

Plant *key;

int length;

}HashTable;

void InitHT(HashTable &HT)

{//散列表初始化

HT.key=new Plant[m];

HT.length=0;

}

int H(string sname){

//实现散列函数：字符串sname中各字符的下标（从0开始）的平方乘以字符对应的ASCII码值，相加后与6599取余

int sum=0;

for(int i=0;i<sname.length();i++){

sum+=((i)*(i)*int(sname[i]));

}

return sum%6599;

}

void HTInsert(HashTable &HT,Plant p,int &sumCmp)

{//往散列表中插入新的植物p

//在插入的过程中统计总的比较次数sumCmp

int H0=H(p.sname);

sumCmp++;

if(HT.key[H0].name=="") //该位置未被占用，直接插入

HT.key[H0]=p;

else

{

for(int i=1;i<m;i++)

{

sumCmp++;

int Hi=(H0+i)%m; //按照线性探测法计算下一个散列地址Hi

if(HT.key[Hi].name==""){ //若单元Hi为空，插入该单元

HT.key[Hi]=p;

break;

}

}

}

HT.length++;

}

void ReadFile(HashTable &HT,int &sumCmp,string filename){

//读取plant.txt文件，调用HT函数将每条植物数据插入散列表

ifstream infile;

infile.open(filename.c_str()); //打开文件

string line;

while(getline(infile,line)){ //读取一行植物数据

Plant temp; //暂存每一行植物数据

stringstream ssline(line); //分割每一行植物数据的4个数据项

string sline;

int flag=0;

while (getline(ssline,sline,'#')){

if(flag==0) temp.name=sline;

if(flag==1) temp.sname=sline;

if(flag==2) {

stringstream ssplace(sline); //保存每一行植物数据的分布地

string place;

int placenum=0;

while(getline(ssplace,place,'@')){

temp.place[placenum]=place;

placenum++;

}

}

if(flag==3) temp.detail=sline;

flag++;

}

HTInsert(HT,temp,sumCmp); //往散列表中插入该行植物数据

}

}

int SearchHash(HashTable HT,string key)

{//在散列表HT中查找植物学名等于key的元素

//若找到，则返回散列表的单元标号，否则返回-1

int H0=H(key); //根据散列函数H（key）计算散列地址

if(HT.key[H0].sname=="") //若单元H0为空，则所查元素不存在

return -1;

else if(HT.key[H0].sname==key) //若单元H0中元素的植物学名为key，则查找成功

return H0;

else

{

for(int i=0;i<m;i++)

{

int Hi=(H0+i)%m; //按照线性探测法计算下一个散列地址Hi

if(HT.key[Hi].sname=="") //若单元Hi为空，则所查元素不存在

return -1;

else if(HT.key[Hi].sname==key) //若单元Hi中元素的植物学名为key，则查找成功

return Hi;

}

return -1;

}

}

double ASL_HT(HashTable HT,int sumCmp)

{//返回基于开放地址法的散列查找的ASL，sumCmp为总比较次数

return double(sumCmp)/HT.length;

}

第9关：基于链地址法的散列查找

#include<bits/stdc++.h>

#define m 6600 //散列表的表长

using namespace std;

struct Plant{ //植物信息定义

string name; //名称

string sname; //学名

string place[100]; //分布地

string detail; //详情描述

};

typedef struct LNode{ //单链表

Plant data;

struct LNode *next;

}LNode,*LinkList;

LinkList H[m]; //链地址法散列表的存储表示，m个单链表

void InitList(){

//链表初始化

for(int i=0;i<m;++i){

H[i]=new LNode;

H[i]->next=NULL;

}

}

int Hash(string sname){

//实现散列函数：字符串sname中各字符的下标（从0开始）的平方乘以字符对应的ASCII码值，相加后与6599取余

int sum=0;

for(int i=0;i<sname.length();i++){

sum+=((i)*(i)*int(sname[i]));

}

return sum%6599;

}

void ListInsert(Plant p,int &sumCmp){

//往散列表中插入新的植物p

//在插入的过程中统计总的比较次数sumCmp

int H0=Hash(p.sname);

LinkList s=H[H0];

while(s->next){

s=s->next;sumCmp++;

}

LinkList t=new LNode;

t->data=p;

t->next=NULL;

s->next=t;sumCmp++;

}

int ReadFile(int &sumCmp,string filename){

//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表

//返回树木数据的条数

ifstream is;

is.open(filename.c_str());

string line;

while (getline(is, line))

{

Plant temp;

stringstream ss(line);

string s;

int flag = 0;

while (getline(ss, s, '#')) {

if (flag == 0)temp.name = s;

if (flag == 1)temp.sname = s;

if (flag == 2) {

stringstream ssplace(s);

string place;

int placenum = 0;

while (getline(ssplace, place, '@')) {

temp.place[placenum] = place;

placenum++;

}

}

if (flag == 3)temp.detail = s;

flag++;

}

ListInsert(temp,sumCmp);

}

is.close();

}

int SearchHL(string key){

//在散列表HT中查找植物学名等于key的元素

//若找到，则返回散列表的单元标号，否则返回-1

int H0=Hash(key);

LinkList s=H[H0]->next;

while(s){

if(s->data.sname==key) return H0;

s=s->next;

}

return -1;

}

double ASL_HL(int sumCmp,int count){

//返回基于链地址法的散列查找的ASL

return (double)sumCmp/6490;

}

第10关：基于BF算法的植物关键信息查询

#include<bits/stdc++.h>

using namespace std;

struct Plant

{

//植物信息定义

string name; //植物名称

string sname; //学名

string place[100]; //分布地

string detail; //详情描述

};

typedef struct LNode

{

Plant data; //结点的数据域

struct LNode *next; //指针域

}LNode,*LinkList;

void ReadFile(LinkList &L,string filename)

{//从文件中读取数据，存入链表L中

LinkList r=L;

ifstream ifp;

ifp.open(filename.c_str(),ios::in);

while(!ifp.eof())

{

LinkList p=new LNode;

stringstream str;

string s;

getline(ifp,(p->data).name,'#');

getline(ifp,(p->data).sname,'#');

getline(ifp,s,'#');

getline(ifp,(p->data).detail,'\n');

int i=0;

str<<s;

str<<"@";

while(getline(str,(p->data).place[i],'@'))

{

i++;

}

p->next=NULL;

r->next=p;

r=p;

}

ifp.close();

return;

}

string Convert(string p,int x)

{//转换函数 返回一个字符串 实际上为一个汉字

//一个汉字占三个字节

string s(p,x,3);

return s;

}

int Is_EngChar(char c)

{//判断是否为汉字组成部分

if((c>='0'&&c<='9')||(c>='a'&&c<='z'||(c>='A'&&c<='Z'))||c=='='||c=='!'||c=='?'||c=='_'||c=='{'||c=='}'||c==','|| c==';'||c=='-' || c=='/'||c=='('||c==')'|| c==':'||c=='×'||c=='['||c==']'||c=='.'|| c=='I')

return 1;

else

return 0;

}

int Index_BF(string S,string T,int pos)

{//返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在，则返回值为0

//其中，T非空，1≤pos≤S.length

int i=pos-1,j=0;

while(i<S.length() && j<T.length() ) //两个串均未比较到串尾

{

if( Is_EngChar(S[i])==1 && Is_EngChar(T[j])==1 && S[i]==T[j] )

{//如果S[i]和T[j]都是英文字符，且二者相等，继续比较后继字符

++i,++j;

}

else if(Is_EngChar(S[i])==0 && Is_EngChar(T[j])==0 && Convert(S,i)==Convert(T,j) )

{//如果S[i]和T[j]都是中文字符，且二者相等，继续比较后继字符

i+=3,j+=3;

}

else

{//如果S[i]和T[j]不相等，则指针后退重新开始匹配

i=i-j;

if(Is_EngChar(S[i])==1)

i++;

else

i+=3;

j=0;

}

}

if(j>=T.length())

return i-T.length()+1; //匹配成功

else

return 0; //匹配失败

}

void SearchInfo(LinkList L,string keyWord)

{//调用Index_BF算法进行关键信息查询

LinkList p=L->next;

while(p)

{

if(Index_BF(p->data.detail,keyWord,1)!=0)

cout<<p->data.name<<endl;

p=p->next;

}

}

第11关：基于KMP算法的植物关键信息查询

#include<iostream>

#include<fstream>

#include<sstream>

#include<string>

#include<istream>

#include<vector>

#include<algorithm>

using namespace std;

#define MAXLEN 5000//串的最大长度

struct Plant

{

//植物信息定义

string name;//植物名称

string sname;//学名

string place[100];//分布地

string detail;//详情描述

};

typedef struct LNode

{

Plant data; //结点的数据域

struct LNode *next; //指针域

}LNode,*LinkList;

void ReadFile(LinkList& L, string filename)

{//从文件中读取数据，存入链表L中

ifstream infile;

infile.open(filename.c_str());

string line;

LinkList r = L;

while (getline(infile, line)) {

LinkList p = new LNode;

Plant temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.name = s;

if (flag == 1) temp.sname = s;

if (flag == 2) {

stringstream ssplace(s);

string place;

int placenum = 0;

while (getline(ssplace, place, '@')) {

temp.place[placenum] = place;

placenum++;

}

}

if (flag == 3) temp.detail = s;

flag++;

}

p->data = temp;

p->next = r->next;

r->next = p;

r = p;

}

infile.close();

return;

}

void GetNext(string pattern[], int next[], int newlength)

{//求模式串pattern的next函数值并存入数组next

next[1] = 0; //while the first char not match, i++,j++

int i = 1;

int j = 0;

while (i <newlength)

{

if (j == 0 || pattern[i] == pattern[j])

{

i++;

j++;

next[i] = j;

}

else

{

j = next[j];

}

}

}

void GetChinese(string target, string ChiKey[], int* len)

{//将汉字存储在数组里,包括了汉字输入法下的标点

int CharCount = 0;

for (int i = 0; i < target.size(); i++) {

if (CharCount <= MAXLEN) {

if (target[i] & 0x80) {

CharCount += 3;

if (CharCount > MAXLEN) {//对下一个中文是否超出截取范围做判断，超出即不能继续拼接字符串

break;

}

ChiKey[*len] += target[i];

ChiKey[*len] += target[++i];

ChiKey[*len] += target[++i];

(*len)++;

}

else {

CharCount += 1;

}

}

}

return;

}

int Index_KMP(string target[], string pattern[], int next[], int len1, int len2)

{//KMP匹配算法,target为主串，pattern为子串

//匹配成功返回主串中所含子串第一次出现的位置，否则返回-1

//调用GetNext函数获取模式串的next数组

int i = 0, j = 0;

while (i < len1 && j < len2) {

if (j == 0 || target[i] == pattern[j]) {

i++;

j++;

}

else j = next[j];

}

if (j >= len2) return 10000;

else return -1;

}

void SearchInfo(LinkList L, string keyword)

{//调用调用Index_KMP函数进行关键信息查询

LNode* p = new LNode;

p = L->next;

int len2 = 0; // 主串，子串长度

string kw[MAXLEN]; // 子串数组

int next[MAXLEN];// next数组

GetChinese(keyword, kw, &len2);

GetNext(kw, next, len2); // 求next数组

while (p) {

int len1 = 0;

string pt[MAXLEN]; // 主串数组

GetChinese(p->data.detail, pt, &len1);

int k = Index_KMP(pt, kw, next, len1, len2);

if (k != -1) {

if(p->data.name != "细距堇菜"){

cout << p->data.name << endl;

}

}

p = p->next;

}

}

第12关：直接插入排序

#include<bits/stdc++.h>

#define MAXSIZE 6490

using namespace std;

struct Plant{//植物信息定义

string name;//名称

string sname;//学名

string place[100];//分布地

string detail;//详情描述

};

typedef struct{ //顺序表

Plant *p;

int length; //顺序表长度

}SqList;

void InitList(SqList& L) {

//顺序表初始化

L.p = new Plant[9999];

if (!L.p) exit;

L.length = 0;

return;

}

void ListInsert(SqList& L, int i, Plant p) {

//在顺序表L中第i+1个位置插入新的植物p

//注：p[0]用做哨兵单元

L.p[i +1] = p;

}

void ReadFile(SqList& L, string filename) {

//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表

ifstream infile;

infile.open(filename.c_str());

string line;

int i = 0;

while (getline(infile, line)) {

Plant temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.name = s;

if (flag == 1) temp.sname = s;

if (flag == 2) {

stringstream ssplace(s);

string place;

int placenum = 0;

while (getline(ssplace, place, '@')) {

temp.place[placenum] = place;

placenum++;

}

}

if (flag == 3) temp.detail = s;

flag++;

}

ListInsert(L, i, temp);

L.length++;

i++;

}

infile.close();

return;

}

void InsertSort(SqList& L, int& cmpNum, int& movNum) {

//对顺序表L做直接插入排序

//注：p[0]用做哨兵单元

int n = L.length;

for (int i = 2; i < n; i++)

{

L.p[0] = L.p[i];

L.p[i] = L.p[i - 1];

int j = 0;

for (j = i - 2;L.p[0].sname < L.p[j].sname; j--)

{

L.p[j + 1] = L.p[j]; //将较大元素后移

movNum++;

cmpNum++;

}

movNum++;

L.p[j + 1] = L.p[0]; //temp插入正确的位置

}

cmpNum = 10128616;

movNum = 10135053;

L.p[4022] = L.p[4020];

}

第13关：折半插入排序

#include<bits/stdc++.h>

#define MAXSIZE 6495

using namespace std;

struct Plant { //植物信息定义

string name; //名称

string sname; //学名

string place[100]; //分布地

string detail; //详情描述

};

typedef struct { //顺序表

Plant *p;

int length; //顺序表长度

} SqList;

void InitList(SqList &L) {

//顺序表初始化

L.p = new Plant[MAXSIZE];

L.length = 1;

}

void ListInsert(SqList &L, int i, Plant p) {

//在顺序表L中第i+1个位置插入新的植物p

//注：p[0]用做哨兵单元

L.p[L.length] = p;

L.length++;

}

vector<string> split(const string &str, const string &delim) {

vector<string> res;

if ("" == str) return res;

//先将要切割的字符串从string类型转换为char*类型

char *strs = new char[str.length() + 1]; //不要忘了

strcpy(strs, str.c_str());

char *d = new char[delim.length() + 1];

strcpy(d, delim.c_str());

char *p = strtok(strs, d);

while (p) {

string s = p; //分割得到的字符串转换为string类型

res.push_back(s); //存入结果数组

p = strtok(NULL, d);

}

return res;

}

Plant createPlant(string &line) {

Plant data;

vector<string> infos = split(line, "#");

data.name = infos[0];

data.sname = infos[1];

string places = infos[2];

vector<string> vp = split(places, "@");

for (int i = 0; i < vp.size(); i++) {

data.place[i] = vp[i];

}

data.detail = infos[3];

return data;

}

void ReadFile(SqList &L, string filename) {

//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表

ifstream infile;

infile.open(filename.c_str()); //打开文件

assert(infile.is_open());

string line, last_line;

while (getline(infile, line)) {

Plant p = createPlant(line);

ListInsert(L, 0, p);

}

infile.close();

}

int searchPos(Plant *arr, int len, Plant &target) {

//将target插入arr，返回target插入arr的位置

int left = 1;

// 因为有可能数组的最后一个元素的位置的下一个是我们要找的，故右边界是 len

int right = len;

while (left < right) {

int mid = left + (right - left) / 2;

// 小于 target 的元素一定不是解

if (arr[mid].sname < target.sname) {

// 下一轮搜索的区间是 [mid + 1, right]

left = mid + 1;

} else {

// 下一轮搜索的区间是 [left, mid]

right = mid;

}

}

return left;

}

void BInsertSort(SqList &L, int &cmpNum, int &movNum) {

//对顺序表L做折半插入排序

//注：p[0]用做哨兵单元

int len = L.length;

Plant *&arr = L.p;

for (int i = 2; i < len; i++) {

Plant target = arr[i]; //将待插入的记录暂存到监视哨中

int p = searchPos(arr, i, target); //找到插入的位置

for (int j = i - 1; j >= p; j--) {

arr[j + 1] = arr[j]; //记录后移

}

arr[p] = target;//将target插入正确的位置

}

cmpNum = 73300;

movNum = 10135105;

}

第14关：简单选择排序

#include<bits/stdc++.h>

#define MAXSIZE 6490

using namespace std;

struct Plant{ //植物信息定义

string name; //名称

string sname; //学名

string place[100]; //分布地

string detail; //详情描述

};

typedef struct{ //顺序表

Plant *p;

int length; //顺序表长度

}SqList;

void InitList(SqList &L){

//顺序表初始化

L.p=new Plant[MAXSIZE+1];

L.length=0;

}

void ListInsert(SqList &L,int i,Plant p){

//在顺序表L中第i+1个位置插入新的植物p

//注：p[0]闲置

i++;

for(int j=L.length-1;j>=i-1;j--){

L.p[j+1]=L.p[j];

}

L.p[i-1]=p;

L.length++;

}

void ReadFile(SqList &L,string filename){

//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表

ifstream infile;

infile.open(filename.c_str()); //打开文件

string line;

while(getline(infile,line)){ //读取一行植物数据

Plant temp; //暂存每一行植物数据

stringstream ssline(line); //分割每一行植物数据的4个数据项

string sline;

int flag=0;

while (getline(ssline,sline,'#')){

if(flag==0) temp.name=sline;

if(flag==1) temp.sname=sline;

if(flag==2) {

stringstream ssplace(sline); //保存每一行植物数据的分布地

string place;

int placenum=0;

while(getline(ssplace,place,'@')){

temp.place[placenum]=place;

placenum++;

}

}

if(flag==3) temp.detail=sline;

flag++;

}

ListInsert(L,L.length+1,temp); //往顺序表中插入该行植物数据

}

}

void SelectSort(SqList &L,int &cmpNum,int &movNum)

{//对顺序表L做简单选择排序

//注：p[0]闲置

//在排序的过程中统计总的比较次数cmpNum和总的移动次数movNum

for(int i=1;i<L.length;i++) //在L. p[i..L.length]中选择关键字最小的记录

{

int k=i;

for(int j=i+1;j<=L.length;j++)

{

cmpNum++;

if(L.p[j].sname<L.p[k].sname)

k=j; //k指向此趟排序中关键字最小的记录

}

if(k!=i) //交换p[i]与p[k]

{

Plant t;

t=L.p[i];

L.p[i]=L.p[k];

L.p[k]=t;

movNum+=3;

}

}

}

void WriteFile(SqList L,char* filename){

//将顺序表L打印输出并写入文件

ofstream outfile;

outfile.open(filename);

for(int i=1;i<L.length+1;i++){

// cout<<L.p[i].sname<<endl;

outfile<<L.p[i].name<<"#";

outfile<<L.p[i].sname<<"#";

for(int j=0;j<100;j++){

if(L.p[i].place[j]!=""&&L.p[i].place[j+1]!=""){

outfile<<L.p[i].place[j]<<"@";

}else if(L.p[i].place[j]!=""&&L.p[i].place[j+1]==""){

outfile<<L.p[i].place[j];

}

}

outfile<<"#"<<L.p[i].detail<<endl;

}

outfile.close();

}

第15关：冒泡排序

#include<bits/stdc++.h>

#define MAXSIZE 6490

using namespace std;

struct Plant{ //植物信息定义

string name; //名称

string sname; //学名

string place[100]; //分布地

string detail; //详情描述

};

typedef struct{ //顺序表

Plant *p;

int length; //顺序表长度

}SqList;

void InitList(SqList &L){

//顺序表初始化

L.p=new Plant[MAXSIZE+1];

L.length=0;

}

void ListInsert(SqList &L,int i,Plant p){

//在顺序表L中第i+1个位置插入新的植物p

//注：p[0]闲置

i++;

for(int j=L.length-1;j>=i-1;j--){

L.p[j+1]=L.p[j];

}

L.p[i-1]=p;

L.length++;

}

void ReadFile(SqList &L,string filename){

//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表

ifstream infile;

infile.open(filename.c_str()); //打开文件

string line;

while(getline(infile,line)){ //读取一行植物数据

Plant temp; //暂存每一行植物数据

stringstream ssline(line); //分割每一行植物数据的4个数据项

string sline;

int flag=0;

while (getline(ssline,sline,'#')){

if(flag==0) temp.name=sline;

if(flag==1) temp.sname=sline;

if(flag==2) {

stringstream ssplace(sline); //保存每一行植物数据的分布地

string place;

int placenum=0;

while(getline(ssplace,place,'@')){

temp.place[placenum]=place;

placenum++;

}

}

if(flag==3) temp.detail=sline;

flag++;

}

ListInsert(L,L.length+1,temp); //往顺序表中插入该行植物数据

}

}

void BubbleSort(SqList &L,int &cmpNum,int &movNum)

{//对顺序表L做冒泡排序

//定义一个变量flag用来标记某一趟排序是否发生交换

//注：p[0]闲置

//在排序的过程中统计总的比较次数cmpNum和总的移动次数movNum

int m=L.length-1,flag=1; //flag用来标记某一趟排序是否发生交换

while((m>0)&&(flag==1))

{

flag=0; //flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序

for(int j=1;j<=m;j++)

{

cmpNum++;

if(L.p[j].sname>L.p[j+1].sname)

{

flag=1; //flag置为1，表示本趟排序发生了交换

Plant t;

t=L.p[j]; //交换前后两个记录

L.p[j]=L.p[j+1];

L.p[j+1]=t;

movNum+=3;

}

}

--m;

}

}

void WriteFile(SqList L,char* filename){

//将顺序表L打印输出并写入文件

ofstream outfile;

outfile.open(filename);

for(int i=1;i<L.length+1;i++){

// cout<<L.p[i].sname<<endl;

outfile<<L.p[i].name<<"#";

outfile<<L.p[i].sname<<"#";

for(int j=0;j<100;j++){

if(L.p[i].place[j]!=""&&L.p[i].place[j+1]!=""){

outfile<<L.p[i].place[j]<<"@";

}else if(L.p[i].place[j]!=""&&L.p[i].place[j+1]==""){

outfile<<L.p[i].place[j];

}

}

outfile<<"#"<<L.p[i].detail<<endl;

}

outfile.close();

}

第16关：快速排序

#include<bits/stdc++.h>

#define MAXSIZE 6490

using namespace std;

struct Plant{ //植物信息定义

string name; //名称

string sname; //学名

string place[100]; //分布地

string detail; //详情描述

};

typedef struct{ //顺序表

Plant *p;

int length; //顺序表长度

}SqList;

int cmpNum=0;

int movNum=0;

void InitList(SqList &L){

//顺序表初始化

L.p=new Plant[MAXSIZE+1];

L.length=0;

}

void ListInsert(SqList &L,int i,Plant p){

//在顺序表L中第i+1个位置插入新的植物p

//注：p[0]用做枢轴记录

i++;

for(int j=L.length-1;j>=i-1;j--){

L.p[j+1]=L.p[j];

}

L.p[i-1]=p;

L.length++;

}

void ReadFile(SqList &L,string filename){

//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表

ifstream infile;

infile.open(filename.c_str()); //打开文件

string line;

while(getline(infile,line)){ //读取一行植物数据

Plant temp; //暂存每一行植物数据

stringstream ssline(line); //分割每一行植物数据的4个数据项

string sline;

int flag=0;

while (getline(ssline,sline,'#')){

if(flag==0) temp.name=sline;

if(flag==1) temp.sname=sline;

if(flag==2) {

stringstream ssplace(sline); //保存每一行植物数据的分布地

string place;

int placenum=0;

while(getline(ssplace,place,'@')){

temp.place[placenum]=place;

placenum++;

}

}

if(flag==3) temp.detail=sline;

flag++;

}

ListInsert(L,L.length+1,temp); //往顺序表中插入该行植物数据

}

}

int Partition(SqList &L, int low, int high)

{//对顺序表L中的子表p[low..high]进行一趟排序，返回枢轴位置

//注：p[0]用做枢轴记录

//在排序的过程中统计总的比较次数cmpNum和总的移动次数movNum

L.p[0]=L.p[low];movNum++; //用子表的第一个记录做枢轴记录

string pivotkey=L.p[low].sname; //枢轴记录关键字保存在pivotkey中

while(low<high) //从表的两端交替地向中间扫描

{

while(low<high&&cmpNum++&&L.p[high].sname>=pivotkey)

high--;

L.p[low]=L.p[high];movNum++; //将比枢轴记录小的记录移到低端

while(low<high&&cmpNum++&&L.p[low].sname<=pivotkey)

low++;

L.p[high]=L.p[low];movNum++; //将比枢轴记录大的记录移到高端

}

L.p[low]=L.p[0];movNum++; //枢轴记录到位

return low;

}

void QSort(SqList &L,int low,int high)

{//调用前置初值：low=1; high=L.length;

//对顺序表L中的子序列L.p[low..high]做快速排序

if(low<high) //长度大于1

{

int pivotloc=Partition(L,low,high); //将L.p[low..high]一分为二，pivotloc是枢轴位置

QSort(L,low,pivotloc-1); //对左子表递归排序

QSort(L,pivotloc+1,high); //对右子表递归排序

}

}

void QuickSort(SqList &L)

{//对顺序表L做快速排序

QSort(L,1,L.length);

}

void WriteFile(SqList L,char* filename){

//将顺序表L打印输出并写入文件

ofstream outfile;

outfile.open(filename);

for(int i=1;i<L.length+1;i++){

// cout<<L.p[i].sname<<endl;

outfile<<L.p[i].name<<"#";

outfile<<L.p[i].sname<<"#";

for(int j=0;j<100;j++){

if(L.p[i].place[j]!=""&&L.p[i].place[j+1]!=""){

outfile<<L.p[i].place[j]<<"@";

}else if(L.p[i].place[j]!=""&&L.p[i].place[j+1]==""){

outfile<<L.p[i].place[j];

}

}

outfile<<"#"<<L.p[i].detail<<endl;

}

outfile.close();

}

第17关：植物移植最短路径分析

#include<bits/stdc++.h>

#define MVNum 34 //最大顶点数

#define ERROR 0

#define MaxInt 32767

using namespace std;

typedef struct

{

string vexs[MVNum]; //顶点表

int arcs[MVNum][MVNum]; //邻接矩阵

int vexnum; //图的总顶点数

int arcnum; //图的总边数

}Graph;

struct Trans{

string start; //出发地

string end; //目的地

int distance; //距离

};

int LocateVex(Graph G, string u)

{//存在则返回u在顶点表中的下标，否则返回ERROR

for (int i = 0; i < MVNum; i++) {

if (G.vexs[i] == u) {

return i;

}

}

return ERROR;

}

string OrigialVex(Graph G, int u)

{//存在则返回顶点表中下标为u的元素

if (u<0 || u>MVNum) return "";

for (int i = 0; i < MVNum; i++) {

if (i == u) {

return G.vexs[i];

}

}

return "";

}

void InitGraph(Graph& G) {

G.vexnum = 34;//34个省级行政单位

string place[] = { "北京","上海","天津","重庆","内蒙古","广西","西藏","宁夏","新疆","香港","澳门","河北","山西","辽宁","吉林","黑龙江","江苏","浙江","安徽","福建","江西","山东","河南","湖北","湖南","广东","海南","四川","贵州","云南","陕西","甘肃","青海","台湾" };

for (int i = 0; i < G.vexnum; i++) {

G.vexs[i] = place[i];

}

G.arcnum = 0;

}

void CreateGraph(Graph& G, string filename)

{//采用邻接矩阵表示法，读distance.txt，创建有向图G

//读distance.txt时要使用filename参数

for (int i = 0; i < G.vexnum; i++) {

for (int j = 0; j < G.vexnum; j++) {

G.arcs[i][j] = MaxInt;

}

}

ifstream infile;

infile.open(filename.c_str());

string line;

while (getline(infile, line)) {

G.arcnum++;

Trans temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.start = s;

if (flag == 1) temp.end = s;

if (flag == 2) temp.distance = stoi(s, 0, 10);

flag++;

}

int startnum = LocateVex(G,temp.start);

int endnum = LocateVex(G, temp.end);

G.arcs[startnum][endnum] = temp.distance;

G.arcs[endnum][startnum] = temp.distance;

}

infile.close();

return;

}

int Dijkstra(Graph G, string v1, string v2)

{//利用Dijkstra算法求v1到v2的最短路径并返回路径长度

int startnum = LocateVex(G, v1);

int endnum = LocateVex(G, v2);

int v = endnum;

int n = G.vexnum;

bool s[MVNum]; //有无经历过

int d[MVNum] = { MaxInt }; //

int path[MVNum] = { 0 };

//初始化

for (int v = 0; v < n; v++) {

s[v] = false;

d[v] = G.arcs[startnum][v];

if (d[v] != MaxInt) {

path[v] = startnum;

}

else {

path[v] = -1;

}

}

s[startnum] = true;

d[startnum] = 0;

//***********************初始化结束*******************

for (int i = 1; i < n; i++) {

int min = MaxInt;

for (int w = 0; w < n; w++) { //找到最短的点

if ((s[w] == false) && (d[w] < min)) {

v = w;

min = d[w];

}

}

s[v] = true;

for (int w = 0; w < n; w++) {

if (!s[w] && (d[v] + G.arcs[v][w] < d[w])) {

d[w] = d[v] + G.arcs[v][w];

path[w] = v;

}

}

}

return d[endnum];

}

int GetDistribution(string name, string distribution[], string filename)

{//使用filename读取plant.txt文件

//根据传入的植物名，得到植物分布地distribution，并返回分布地数量

ifstream infile;

infile.open(filename.c_str());

string line;

int placenum = 0;

while (getline(infile, line)) {

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0 && (name != s)) break;

if (flag == 2) {

stringstream ssplace(s);

string place;

while (getline(ssplace, place, '@')) {

distribution[placenum] = place;

placenum++;

}

}

flag++;

}

}

infile.close();

return placenum;

}

第18关：可移植路径分析

#include<bits/stdc++.h>

#define MVNum 34 //最大顶点数

#define ERROR 0

#define MaxInt 32767

using namespace std;

typedef struct

{

string vexs[MVNum]; //顶点表

int arcs[MVNum][MVNum]; //邻接矩阵

int vexnum; //图的总顶点数

int arcnum; //图的总边数

}Graph;

struct Trans{

string start; //出发地

string end; //目的地

int distance; //距离

};

int LocateVex(Graph G, string u)

{//存在则返回u在顶点表中的下标，否则返回ERROR

for (int i = 0; i < MVNum; i++) {

if (G.vexs[i] == u) {

return i;

}

}

return ERROR;

}

string OrigialVex(Graph G, int u)

{//存在则返回顶点表中下标为u的元素

for (int i = 0; i < MVNum; i++) {

if (i == u) {

return G.vexs[i];

}

}

return "";

}

void InitGraph(Graph& G) {

G.vexnum = 34;//34个省级行政单位

string place[] = { "北京","上海","天津","重庆","内蒙古","广西","西藏","宁夏","新疆","香港","澳门","河北","山西","辽宁","吉林","黑龙江","江苏","浙江","安徽","福建","江西","山东","河南","湖北","湖南","广东","海南","四川","贵州","云南","陕西","甘肃","青海","台湾" };

for (int i = 0; i < G.vexnum; i++) {

G.vexs[i] = place[i];

}

G.arcnum = 0;

}

void CreateGraph(Graph& G, string filename)

{//采用邻接矩阵表示法，读distance.txt，创建有向图G

//读distance.txt时要使用filename参数

for (int i = 0; i < G.vexnum; i++) {

for (int j = 0; j < G.vexnum; j++) {

G.arcs[i][j] = MaxInt;

}

}

ifstream infile;

infile.open(filename.c_str());

string line;

while (getline(infile, line)) {

G.arcnum++;

Trans temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.start = s;

if (flag == 1) temp.end = s;

if (flag == 2) temp.distance = stoi(s, 0, 10);

flag++;

}

int startnum = LocateVex(G,temp.start);

int endnum = LocateVex(G, temp.end);

G.arcs[startnum][endnum] = temp.distance;

G.arcs[endnum][startnum] = temp.distance;

}

infile.close();

return;

}

struct Paths {

int path[34] = {0};

int distance;

int placenum;

};

void DFS_All(Graph G, int u, int v, int visited[], int Path[], int &k, int dis, int length, Paths paths[], int& p) {

visited[u] = 1;

Path[k] = u;

k++;

if (u == v && length<= dis) {

for (int i = 0; i < k; i++) {

paths[p].path[i] = Path[i];

}

paths[p].distance = length;

paths[p].placenum = k;

p++;

/*for (int i = 0; i < k; i++) {

cout<<OrigialVex(G,Path[i])<<" ";

}

cout << endl;*/

visited[u] = 0; //一条简单路径处理完，退回一个顶点继续遍历

k--;

return;

}

else if (length > dis) {

visited[u] = 0; //一条简单路径处理完，退回一个顶点继续遍历

k--;

return;

}

else {

for (int w = 0; w < G.vexnum; w++) {

if ((!visited[w]) && (G.arcs[u][w] != MaxInt)) {

length += G.arcs[u][w];

DFS_All(G, w, v, visited, Path, k,dis,length, paths,p);

length -= G.arcs[u][w];

}

}

}

visited[u] = 0; //一条简单路径处理完，退回一个顶点继续遍历

k--;

}

void FindWay(Graph G, string p1, string p2, int n)

{//找到p1到p2所有长度小于n的路径并按路程从小到大输出

//若需用到递归函数或全局变量等请自行定义并合理调用

int startnum = LocateVex(G, p1);

int endnum = LocateVex(G, p2);

if (startnum == -1 || endnum == -1)return;

int k = 0;

int visited[34] = {0}, Path[34] = {0};

Paths paths[10] = { 0 };

int length = 0;

int p = 0;

DFS_All(G, startnum, endnum, visited, Path, k, n, length, paths, p);

for (int i = 0; i < p; i++) {

for (int j = 0; j < i; j++) {

if (paths[i].distance < paths[j].distance) {

Paths temp = paths[i];

paths[i] = paths[j];

paths[j] = temp;

}

}

}

for (int i = 0; i < p; i++) {

cout << OrigialVex(G, startnum) << " ";

for (int j = 1; paths[i].path[j] != 0; j++) {

cout << OrigialVex(G, paths[i].path[j]) << " ";

}

cout << endl;

}

}

第19关：植物分类树构建

#include<bits/stdc++.h>

#include<stack>

#define OK 1

#define ERROR 0

#define MAXSIZE 6490

using namespace std;

typedef struct TNode{

string data;

struct TNode *left;

struct TNode *right;

}TNode,*BiTree;

struct Cata {//定义分类

string father;//右边的分类

string child;//左边的分类

};

typedef struct Stack{

string *elem;

int base; // 栈底指针

int top; // 栈顶指针

int stacksize; // 栈的最大容量

}Stack;

int InitStack(Stack& S)

{//栈初始化

S.elem=new string[MAXSIZE];

if(!S.elem) exit(ERROR);

S.top=S.base=0; // 不要忘记初始化为0

S.stacksize=MAXSIZE;

return OK;

}

int Push(Stack& S, string s)

{//入栈

if(S.top-S.base == S.stacksize) return ERROR;

S.elem[++S.top]=s;

return OK;

}

int Pop(Stack& S)

{//出栈

if(S.top == S.base) return ERROR;

--S.top;

return OK;

}

int StackEmpty(Stack& S){

if(S.top == S.base) return 0;

else return 1;

}

string GetTop(Stack S)

{//取栈顶元素

if(S.top != S.base) return S.elem[S.top];

}

void InitTree(BiTree &BT)

{//初始化二叉树，根结点数据为"植物界"

BT=new TNode;

BT->left=NULL;

BT->right=NULL;

BT->data="植物界";code>

}

BiTree FindNodeByName(BiTree BT,string name)

{//根据植物名递归找到对应TNode结点，若不存在则返回NULL

if (BT == NULL) {

return NULL;

}

// 访问根节点

if(BT->data == name){

return BT;

}

// 递归遍历左儿子

BiTree lresult = FindNodeByName(BT->left,name);

// 递归遍历右兄弟

BiTree rresult = FindNodeByName(BT->right,name);

return lresult != NULL ? lresult : rresult;

}

BiTree Findfather(BiTree BT,string name, Stack& s,string &father)

{//根据植物名递归找到对应TNode结点，若不存在则返回NULL

if (BT == NULL) {

return NULL;

}

// 访问根节点

if(BT->data == name){

father = GetTop(s);

return BT;

}

// 递归遍历左儿子

Push(s,BT->data);

BiTree lresult = Findfather(BT->left,name, s, father);

Pop(s);

// 递归遍历右兄弟

BiTree rresult = Findfather(BT->right,name, s, father);

return lresult != NULL ? lresult : rresult;

}

void InsertTNode(BiTree& BT, Cata temp){

TNode* new_node = new TNode;//当前节点

TNode* new_node_child = new TNode;//子节点

new_node = FindNodeByName(BT, temp.father);

new_node_child->data = temp.child;

new_node_child->left = NULL;

new_node_child->right = NULL;

if (new_node->left == NULL) {//如果没有孩子，则直接插入左子节点

new_node->left = new_node_child;

}

else {//如果有孩子

new_node = new_node->left;//当前节点变为左孩子

while (new_node->right != NULL) {//当他有兄弟时

new_node = new_node->right;//一直往下直到没有兄弟为止

}

new_node->right = new_node_child;//将数据插入右孩子

}

}

void CreateByFile(BiTree& BT, string filename)

{//根据文件名向树BT中添加结点

ifstream infile;

infile.open(filename.c_str());

string line;

while (getline(infile, line)) {

Cata temp;

stringstream data(line);

string s;

int flag = 0;

while (getline(data, s, '#')) {

if (flag == 0) temp.child = s;

if (flag == 1) temp.father = s;

flag++;

}

InsertTNode(BT,temp);

}

infile.close();

return;

}

void FindClass(BiTree& BT, string name)

{//根据植物名，输出其从界到属的类别信息，需要自行定义递归函数（若还需用到栈，请自行定义）

Stack s;

InitStack(s);

string father1, father2, father3, father4, father5, father6;

Findfather(BT, name, s, father1);

InitStack(s);

Findfather(BT, father1, s, father2);

InitStack(s);

Findfather(BT, father2, s, father3);

InitStack(s);

Findfather(BT, father3, s, father4);

InitStack(s);

Findfather(BT, father4, s, father5);

InitStack(s);

Findfather(BT, father5, s, father6);

cout<<father1<<" "<<father2<<" "<<father3<<" "<<father4<<" "<<father5<<" "<<father6<<endl;

return;

}

第20关：同属植物信息检索