目录
第1关：增加植物信息
第2关：删除植物信息
第3关：修改植物信息
第4关：基于顺序表的顺序查找
第5关：基于链表的顺序查找
第6关：基于顺序表的折半查找
第7关：基于二叉排序树的查找
第8关：基于开放地址法的散列查找
第9关：基于链地址法的散列查找
第10关：基于BF算法的植物关键信息查询
第11关：基于KMP算法的植物关键信息查询
第12关：直接插入排序
第13关：折半插入排序
第14关：简单选择排序
第15关：冒泡排序
第16关：快速排序
第17关：植物移植最短路径分析
第18关：可移植路径分析
第19关：植物分类树构建
第20关：同属植物信息检索
第21关：下属植物信息检索
第1关：增加植物信息
#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，否则，返回trueint 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，否则,返回falseLNode* 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的数据元素//若找到，则返回该元素在表中的下标，否则返回-1int 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){//构造一个空的单链表LL = 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函数值并存入数组nextnext[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 6490using 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 6495using 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 6490using 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 6490using 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 6490using 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 32767using 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 32767using 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 6490using 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="植物界";}BiTree FindNodeByName(BiTree BT,string name){//根据植物名递归找到对应TNode结点，若不存在则返回NULLif (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结点，若不存在则返回NULLif (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关：同属植物信息检索
#include<bits/stdc++.h>#include<stack>#define OK 1#define ERROR 0#define MAXSIZE 6490using 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="植物界";}BiTree FindNodeByName(BiTree BT,string name){//根据植物名递归找到对应TNode结点，若不存在则返回NULLif (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结点，若不存在则返回NULLif (BT == NULL) { return NULL; } // 访问根节点 if(BT->data == name){ father = GetTop(s); return BT;} // 递归遍历左儿子 Push(s,BT->data); BiTree left = Findfather(BT->left,name,s,father); Pop(s); BiTree right = Findfather(BT->right,name,s,father); return left != NULL? left:right;}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 FindBrother(BiTree &BT,string name){//根据植物名，输出其兄弟信息，空格分隔 Stack s; InitStack(s); string father; Findfather(BT, name, s, father); TNode* p = FindNodeByName(BT, father); p = p->left; while(p->right){ if(p->data != name){ cout<<p->data<<" "; } p = p->right; } cout<<p->data; cout<<endl;}
第21关：下属植物信息检索
#include<bits/stdc++.h>using namespace std;typedef struct TNode{string data;struct TNode *left;struct TNode *right;}TNode,*BiTree;struct Cata {//定义分类string father;//右边的分类string child;//左边的分类};void InitTree(BiTree &BT){//初始化二叉树，根结点数据为"植物界"BT=new TNode;BT->left=NULL;BT->right=NULL;BT->data="植物界";}BiTree FindNodeByName(BiTree BT,string name){//根据植物名递归找到对应TNode结点，若不存在则返回NULLif (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;}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;}string plant[6490] = {" "};int k = 0;BiTree FindSon(BiTree &BT){ if(!BT) return NULL; if (BT == NULL) { return NULL; } // 访问根节点 if(BT->left == NULL){ while(BT){ plant[k] = BT->data; k++; BT = BT->right; } return BT;} // 递归遍历左儿子 BiTree lresult = FindSon(BT->left); // 递归遍历右兄弟 BiTree rresult = FindSon(BT->right); return lresult != NULL ? lresult : rresult;}void FindSubLeaf(BiTree &BT,string name){//根据分类词（门、纲、目、科、属中的一个），输出隶属于该分类词的植物，空格分隔 TNode *p = FindNodeByName(BT,name); p = p->left; FindSon(p); int i = 0; while(i<k-1){ cout<<plant[i]<<" "; i++; } cout<<plant[i]<<endl; k = 0;}