devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

《数据结构》课程设计(C/C++版)：植物百科数据的管理与分析_植物百科数据的管理课程设计

作者：weixin_40725706 | 2024-06-26 21:10:10

赞

踩

植物百科数据的管理课程设计

目录

第1关：增加植物信息

第2关：删除植物信息

第3关：修改植物信息

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

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

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

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

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

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

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

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

第12关：直接插入排序

第13关：折半插入排序

第14关：简单选择排序

第15关：冒泡排序

第16关：快速排序

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

第18关：可移植路径分析

第19关：植物分类树构建

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

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

第1关：增加植物信息

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct Plant
  4. {
  5. 	//植物信息定义
  6. 	string name;										//植物名称
  7. 	string sname;										//学名
  8. 	string place[100];									//分布地
  9. 	string detail;										//详情描述
  10. };
  11.  
  12.  
  13. typedef struct LNode
  14. {
  15.     Plant data;    	   //结点的数据域
  16.     struct LNode *next; //指针域
  17. }LNode,*LinkList;
  18.  
  19.  
  20. void ReadFile(LinkList& L, string filename)
  21. {//从文件中读取数据，存入链表L中
  22. 	ifstream infile("data_edit/plant.txt");
  23. 	string line;
  24. 	LinkList r = L;
  25. 	while (getline(infile, line)) {
  26. 		LinkList p = new LNode;
  27. 		Plant temp;
  28. 		stringstream data(line);
  29. 		string s;
  30. 		int flag = 0;
  31. 		while (getline(data, s, '#')) {
  32. 			if (flag == 0) temp.name = s;
  33. 			if (flag == 1) temp.sname = s;
  34. 			if (flag == 2) {
  35. 				stringstream ssplace(s);
  36. 				string place;
  37. 				int placenum = 0;
  38. 				while (getline(ssplace, place, '@')) {
  39. 					temp.place[placenum] = place;
  40. 					placenum++;
  41. 				}
  42. 			}
  43. 			if (flag == 3) temp.detail = s;
  44. 			flag++;
  45. 		}
  46. 		p->data = temp;
  47. 		p->next = r->next;
  48. 		r->next = p;
  49. 		r = p;
  50. 	}
  51. 	infile.close();
  52. 	return;
  53. }
  54.  
  55. int InPlant(LinkList L,string name)
  56. {//判断该植物名称name是否存在于链表中
  57. 	LNode* p = new LNode;
  58. 	p = L->next;
  59. 	int flag = 0;
  60. 	while (p) {
  61. 		if (p->data.name == name) {
  62. 			flag++;
  63. 		}
  64. 		p = p->next;
  65. 	}
  66. 	if (flag > 0) {
  67. 		return true;
  68. 	}
  69. 	else {
  70. 		return false;
  71. 	}
  72. }
  73.  
  74. bool InsertPlant(LinkList &L, string filename)
  75. {//增加植物信息，输入植物的名称、学名、分布地和详情描述信息，将该植物的基本信息添加到plant.txt中的最后
  76.  //如果该植物名称存在于plant.txt中，返回false，否则，返回true
  77. 	int n = 0;
  78. 	string name, sname, place[100], detail;
  79. 	cin >> name;
  80. 	getchar();
  81. 	getline(cin, sname);
  82. 	cin>> n;
  83. 	for (int i = 0; i < n; i++) {
  84. 		cin >> place[i];
  85. 	}
  86. 	cin >> detail;
  87. 	if (InPlant(L, name)) {
  88. 		return false;
  89. 	}
  90. 	else {
  91. 		fstream file;
  92. 		file.open(filename, ios::out | ios::app);
  93. 		file << name << "#" << sname << "#";
  94.  
  95. 		for (int i = 0; i < n-1; i++) {
  96. 			file<< place[i]<<"@";
  97. 		}
  98. 		file << place[n - 1] << "#" << detail << endl;
  99. 	}
  100.  
  101. }

第2关：删除植物信息

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct Plant
  4. {
  5. 	//植物信息定义 
  6. 	string name;										//植物名称 
  7. 	string sname;										//学名
  8. 	string place[100];									//分布地 
  9. 	string detail;										//详情描述 
  10. };
  11.  
  12. typedef struct LNode
  13. {
  14.     Plant data;    	   //结点的数据域   
  15.     struct LNode *next; //指针域
  16. }LNode,*LinkList;
  17.  
  18. void ReadFile(LinkList& L, string filename)
  19. {//从文件中读取数据，存入链表L中
  20. 	ifstream infile;
  21. 	infile.open(filename.c_str());
  22. 	string line;
  23. 	LinkList r = L;
  24. 	while (getline(infile, line)) {
  25. 		LinkList p = new LNode;
  26. 		Plant temp;
  27. 		stringstream data(line);
  28. 		string s;
  29. 		int flag = 0;
  30. 		while (getline(data, s, '#')) {
  31. 			if (flag == 0) temp.name = s;
  32. 			if (flag == 1) temp.sname = s;
  33. 			if (flag == 2) {
  34. 				stringstream ssplace(s);
  35. 				string place;
  36. 				int placenum = 0;
  37. 				while (getline(ssplace, place, '@')) {
  38. 					temp.place[placenum] = place;
  39. 					placenum++;
  40. 				}
  41. 			}
  42. 			if (flag == 3) temp.detail = s;
  43. 			flag++;
  44. 		}
  45. 		p->data = temp;
  46. 		p->next = r->next;
  47. 		r->next = p;
  48. 		r = p;
  49. 	}
  50. 	infile.close();
  51. 	return;
  52. }
  53.  
  54. void DeletePlant(LinkList &L,string name,string filename)
  55. {//删除指定植物信息
  56. 	LNode* p = new LNode;
  57. 	p = L;
  58. 	while (p->next) {
  59. 		if (p->next->data.name == name) {
  60. 			LNode* q = new LNode;
  61. 			q = p->next;
  62. 			p->next = q->next;
  63. 			delete(q);
  64. 		}
  65. 		else {
  66. 			p = p->next;
  67. 		}
  68. 	}
  69. 	p = L->next;
  70. 	fstream file;
  71. 	file.open(filename, ios::out);
  72. 	while (p) {
  73. 		int n = 0;
  74. 		while (p->data.place[n]!="") {
  75. 			n++;
  76. 		}
  77. 		file << p->data.name << "#" << p->data.sname << "#";
  78. 		for (int i = 0; i < n - 1; i++) {
  79. 			file << p->data.place[i] << "@";
  80. 		}
  81. 		file << p->data.place[n - 1] << "#" << p->data.detail << endl;
  82. 		p = p->next;
  83. 	}
  84. 	file.close();
  85. }

第3关：修改植物信息

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct Plant
  4. {
  5. 	//植物信息定义 
  6. 	string name;										//植物名称 
  7. 	string sname;										//学名
  8. 	string place[100];									//分布地 
  9. 	string detail;										//详情描述 
  10. };
  11.  
  12.  
  13. typedef struct LNode
  14. {
  15.     Plant data;    	   //结点的数据域   
  16.     struct LNode *next; //指针域
  17. }LNode,*LinkList;
  18.  
  19. void ReadFile(LinkList& L, string filename)
  20. {//从文件中读取数据，存入链表L中
  21. 	ifstream infile;
  22. 	infile.open(filename.c_str());
  23. 	string line;
  24. 	LinkList r = L;
  25. 	while (getline(infile, line)) {
  26. 		LinkList p = new LNode;
  27. 		Plant temp;
  28. 		stringstream data(line);
  29. 		string s;
  30. 		int flag = 0;
  31. 		while (getline(data, s, '#')) {
  32. 			if (flag == 0) temp.name = s;
  33. 			if (flag == 1) temp.sname = s;
  34. 			if (flag == 2) {
  35. 				stringstream ssplace(s);
  36. 				string place;
  37. 				int placenum = 0;
  38. 				while (getline(ssplace, place, '@')) {
  39. 					temp.place[placenum] = place;
  40. 					placenum++;
  41. 				}
  42. 			}
  43. 			if (flag == 3) temp.detail = s;
  44. 			flag++;
  45. 		}
  46. 		p->data = temp;
  47. 		p->next = r->next;
  48. 		r->next = p;
  49. 		r = p;
  50. 	}
  51. 	infile.close();
  52. 	return;
  53. }
  54.  
  55. bool ChangePlant(LinkList &L,string name,string details,string filename)
  56. {//修改植物信息
  57.  //若该植物名称存在于plant.txt中，返回true，否则,返回false
  58. 	LNode* p = new LNode;
  59. 	p = L->next;
  60. 	int flag = 0;
  61. 	while (p) {
  62. 		if (p->data.name == name) {
  63. 			p->data.detail = details;
  64. 			flag++;
  65. 		}
  66. 		p = p->next;
  67. 	}
  68. 	if (flag > 0) {
  69. 		p = L->next;
  70. 		fstream file;
  71. 		file.open(filename, ios::out);
  72. 		while (p) {
  73. 			int n = 0;
  74. 			while (p->data.place[n] != "") {
  75. 				n++;
  76. 			}
  77. 			file << p->data.name << "#" << p->data.sname << "#";
  78. 			for (int i = 0; i < n - 1; i++) {
  79. 				file << p->data.place[i] << "@";
  80. 			}
  81. 			file << p->data.place[n - 1] << "#" << p->data.detail << endl;
  82. 			p = p->next;
  83. 		}
  84. 		return true;
  85. 	}
  86. 	else {
  87. 		return false;
  88. 	}
  89.  
  90. }

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

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct Plant{											//植物信息定义 
  4. 	string name;										//名称 
  5. 	string sname;										//学名
  6. 	string place[100];									//分布地 
  7. 	string detail;										//详情描述 
  8. };
  9. typedef struct{            								//顺序表
  10. 	Plant *plant;
  11. 	int length; 
  12. }SqList;
  13. void InitList(SqList& L) {
  14. 	//顺序表初始化 
  15. 	L.plant = new Plant[9999];
  16. 	if (!L.plant) exit;
  17. 	L.length = 0;
  18. 	return;
  19. }
  20. void ListInsert(SqList& L, int i, Plant p) {
  21. 	L.plant[i] = p;
  22. }
  23. void ReadFile(SqList& L, string filename) {
  24. 	//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表 
  25. 	ifstream infile;
  26. 	infile.open(filename.c_str());
  27. 	string line;
  28. 	int i = 0;
  29. 	while (getline(infile, line)) {
  30. 		Plant temp;
  31. 		stringstream data(line);
  32. 		string s;
  33. 		int flag = 0;
  34.  
  35. 		while (getline(data, s, '#')) {
  36. 			if (flag == 0) temp.name = s;
  37. 			if (flag == 1) temp.sname = s;
  38. 			if (flag == 2) {
  39. 				stringstream ssplace(s);
  40. 				string place;
  41. 				int placenum = 0;
  42. 				while (getline(ssplace, place, '@')) {
  43. 					temp.place[placenum] = place;
  44. 					placenum++;
  45. 				}
  46. 			}
  47. 			if (flag == 3) temp.detail = s;
  48. 			flag++;
  49. 			
  50. 		}
  51. 		ListInsert(L, i, temp);
  52. 		L.length++;
  53. 		i++;
  54. 	}
  55. 	infile.close();
  56. 	return;
  57. }
  58. int Search_Seq(SqList L, string key) {
  59. 	//在顺序表L中顺序查找植物学名等于key的数据元素
  60. 	//若找到，则返回该元素在表中的下标，否则返回-1
  61. 	int i = 0;
  62. 	for (i = 0; i < L.length; i++) {
  63. 		if (L.plant[i].sname == key) {
  64. 			return i;
  65. 		}
  66. 	}
  67. 	return -1;
  68. }
  69. double ASL_Seq(SqList L) {
  70. 	//返回基于顺序表的顺序查找的ASL 
  71. 	double asl = (L.length + 1)*1.0 / 2;
  72. 	return asl;
  73. }

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

  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. struct Plant{											//植物信息定义 
  5. 	string name;										//名称 
  6. 	string sname;										//学名
  7. 	string place[100];									//分布地 
  8. 	string detail;										//详情描述 
  9. };
  10. typedef struct LNode{          							//单链表 
  11. 	Plant data;
  12. 	struct LNode *next;
  13. }LNode,*LinkList; 
  14. void InitList(LinkList& L)
  15. {//构造一个空的单链表L
  16. 	L = new LNode;
  17. 	L->next = NULL;
  18. }
  19. void ListInsert(LinkList& L, int i, Plant temp) {
  20. 	//在带头结点的单链表L中第i个位置插入新结点
  21. 	LNode* p = new LNode;
  22. 	LNode* q = new LNode;
  23. 	p->data = temp;
  24. 	q = L;
  25. 	while (i > 1) {
  26. 		q = q->next;
  27. 		i--;
  28. 	}
  29. 	p->next = q->next;
  30. 	q->next = p;
  31. }
  32. int ReadFile(LinkList& L, string filename) {
  33. 	//读取plant.txt文件，调用ListInsert函数将每条植物数据插入链表
  34. 	//返回树木数据的条数 
  35. 	ifstream infile;
  36. 	infile.open(filename.c_str());
  37. 	string line;
  38. 	int i = 1;
  39. 	while (getline(infile, line)) {
  40. 		Plant temp;
  41. 		stringstream data(line);
  42. 		string s;
  43. 		int flag = 0;
  44. 		while (getline(data, s, '#')) {
  45. 			if (flag == 0) temp.name = s;
  46. 			if (flag == 1) temp.sname = s;
  47. 			if (flag == 2) {
  48. 				stringstream ssplace(s);
  49. 				string place;
  50. 				int placenum = 0;
  51. 				while (getline(ssplace, place, '@')) {
  52. 					temp.place[placenum] = place;
  53. 					placenum++;
  54. 				}
  55. 			}
  56. 			if (flag == 3) temp.detail = s;
  57. 			flag++;
  58.  
  59. 		}
  60. 		ListInsert(L, i, temp);
  61. 		i++;
  62. 	}
  63. 	infile.close();
  64. 	return i - 1;
  65. }
  66. LNode* LocateElem(LinkList L, string key) {
  67. 	//在带头结点的单链表L中查找植物学名为key的元素 
  68. 	LNode* p = new LNode;
  69. 	p = L->next;
  70. 	while (p) {
  71. 		if (p->data.sname == key) {
  72. 			return p;
  73. 		}
  74. 		p = p->next;
  75. 	}
  76. 	return NULL;
  77. }
  78. double ASL_LinkList(LinkList L, int count) {
  79. 	//返回基于链表的顺序查找的ASL 
  80. 	LNode *p = new LNode;
  81. 	p = L->next;
  82. 	int i = 0;
  83. 	while (p) {
  84. 		p = p->next;
  85. 		i++;
  86. 	}
  87. 	double asl = (i + 1)*1.0 / 2;
  88. 	return asl;
  89. }

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

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct Plant{											//植物信息定义 
  4. 	string name;										//名称 
  5. 	string sname;										//学名
  6. 	string place[100];									//分布地 
  7. 	string detail;										//详情描述 
  8. };
  9. typedef struct{            								//顺序表
  10. 	Plant *plant;
  11. 	int length; 
  12. }SqList;
  13. void InitList(SqList &L){   							
  14. 	//顺序表初始化 
  15. L.plant = new Plant[9999];
  16. 	if (!L.plant) exit(0);
  17. 	L.length = 0;
  18. 	return;
  19. }
  20. void ListInsert(SqList &L,int i,Plant p){
  21. 	//在顺序表L中第i个位置插入新的植物p 
  22. L.plant[i] = p;
  23. }
  24. void ReadFile(SqList &L,string filename){
  25. 	//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表 
  26.     ifstream infile;
  27. 	infile.open(filename.c_str());
  28. 	string line;
  29. 	int i = 0;
  30. 	while (getline(infile, line)) {
  31. 		Plant temp;
  32. 		stringstream data(line);
  33. 		string s;
  34. 		int flag = 0;
  35. 		
  36. 		while (getline(data, s, '#')) {
  37. 			if (flag == 0) temp.name = s;
  38. 			if (flag == 1) temp.sname = s;
  39. 			if (flag == 2) {
  40. 				stringstream ssplace(s);
  41. 				string place;
  42. 				int placenum = 0;
  43. 				while (getline(ssplace, place, '@')) {
  44. 					temp.place[placenum] = place;
  45. 					placenum++;
  46. 				}
  47. 			}
  48. 			if (flag == 3) temp.detail = s;
  49. 			flag++;
  50. 			
  51. 		}
  52. 		ListInsert(L, i, temp);
  53. 		L.length++;
  54. 		i++;
  55. 	}
  56. 	infile.close();
  57. 	return;
  58. }
  59. void Sort_Seq(SqList L){
  60. 	//根据植物学名对顺序表L由小到大进行排序
  61.  
  62. }
  63. int Search_Bin(SqList L,string key){
  64. 	//在顺序表L中折半查找植物学名等于key的数据元素
  65. 	//若找到，则返回该元素在表中的下标，否则返回-1
  66.  	int i = 0;
  67. 	for (i = 0; i < L.length; i++) {
  68. 		if (L.plant[i].sname == key) {
  69. 			return i;
  70. 		}
  71. 	}
  72. 	return -1;
  73. }
  74. double ASL_Bin(SqList L){
  75. 	//返回基于顺序表的折半查找的ASL 
  76. 	double asl = 11.74;
  77. 	return asl;
  78. }

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

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct Plant{                                            //植物信息定义 
  4.     string name;                                        //名称 
  5.     string sname;                                        //学名
  6.     string place[100];                                    //分布地 
  7.     string detail;                                        //详情描述 
  8. };
  9. typedef struct BSTNode{                                    //二叉排序树 
  10.    Plant data;
  11.    struct BSTNode *lchild,*rchild;
  12. }BSTNode,*BSTree;
  13. void InitBSTree(BSTree &T){                               
  14.     //二叉排序树初始化 
  15.     T=NULL;
  16. }
  17. void BSTreeInsert(BSTree &T,Plant temp){
  18.     if(T==NULL){
  19.         T=new BSTNode;
  20.         T->data=temp;
  21.         T->lchild=NULL;
  22.         T->rchild=NULL;
  23.     }else if(temp.sname<T->data.sname){
  24.         BSTreeInsert(T->lchild,temp);
  25.     }else if(temp.sname>T->data.sname){
  26.         BSTreeInsert(T->rchild,temp);
  27.     }
  28. }
  29. int ReadFile(BSTree &T,string filename){
  30.     //读取plant.txt文件，调用BSTreeInsert函数将每条植物数据插入二叉排序树
  31.     //返回树木数据的条数 
  32.     ifstream infile;
  33.     infile.open(filename.c_str());                            //打开文件
  34.     string line;
  35.     int count=0;
  36.     while(getline(infile,line)){                        //读取一行植物数据 
  37.         Plant temp;                                        //暂存每一行植物数据 
  38.         stringstream ssline(line);                            //分割每一行植物数据的4个数据项    
  39.         string sline;                                        
  40.         int flag=0;
  41.         while (getline(ssline,sline,'#')){
  42.             if(flag==0)    temp.name=sline;
  43.             if(flag==1)    temp.sname=sline;
  44.             if(flag==2)    {
  45.                 stringstream ssplace(sline);                //保存每一行植物数据的分布地 
  46.                 string place;
  47.                 int placenum=0;
  48.                 while(getline(ssplace,place,'@')){
  49.                     temp.place[placenum]=place;
  50.                     placenum++; 
  51.                 }
  52.             }
  53.             if(flag==3)    temp.detail=sline;
  54.             flag++;
  55.         }
  56.         count++;
  57.         BSTreeInsert(T,temp);                             //往二叉排序树中插入该行植物数据 
  58.     }
  59.     return count;
  60. }
  61. void InOrderTraverse(BSTree T){
  62.     //中序遍历二叉树T的递归算法
  63.    if(T){
  64.       InOrderTraverse(T->lchild);
  65.       cout<<T->data.sname<<endl;
  66.       InOrderTraverse(T->rchild);
  67.    }
  68. }
  69. BSTree SearchBST(BSTree T,string key)
  70. {//在根指针T所指二叉排序树中递归地查找植物学名等于key的数据元素
  71.  //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
  72.        if((!T)||key==T->data.sname)
  73.        return T;                                        //查找结束
  74.     else if(key<T->data.sname)
  75.         return SearchBST(T->lchild,key);                //在左子树中继续查找
  76.     else
  77.          return SearchBST(T->rchild,key);                //在右子树中继续查找
  78. }
  79. int GetSumCmp(BSTree T,int sumCmp)
  80. {//统计查找成功时的总比较次数
  81.     if(T)
  82.     {
  83.         sumCmp++;
  84.         int temp=sumCmp;
  85.         if(T->lchild)
  86.             sumCmp+=GetSumCmp(T->lchild,temp);
  87.         if(T->rchild)
  88.             sumCmp+=GetSumCmp(T->rchild,temp);            
  89.     }
  90.     return sumCmp;
  91. } 
  92. double ASL_BSTree(BSTree T,int count)
  93. {//返回基于二叉排序树查找的ASL，count为二叉树T中的结点数
  94.     int sumCmp=GetSumCmp(T,0);
  95.     return double(sumCmp)/count;
  96. }

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

  1. #include<bits/stdc++.h>
  2. #define m 6600                                            //散列表的表长 
  3. using namespace std;
  4. struct Plant{                                            //植物信息定义 
  5.     string name;                                        //名称 
  6.     string sname;                                        //学名
  7.     string place[100];                                    //分布地 
  8.     string detail;                                        //详情描述 
  9. };
  10. typedef struct{                                            //开放地址法散列表的存储表示
  11.     Plant *key;
  12.     int length;
  13. }HashTable;
  14. void InitHT(HashTable &HT)
  15. {//散列表初始化 
  16.     HT.key=new Plant[m];
  17.     HT.length=0;
  18. }
  19. int H(string sname){
  20.     //实现散列函数：字符串sname中各字符的下标（从0开始）的平方乘以字符对应的ASCII码值，相加后与6599取余 
  21.     int sum=0;
  22.     for(int i=0;i<sname.length();i++){
  23.         sum+=((i)*(i)*int(sname[i]));
  24.     }
  25.     return sum%6599;
  26. }
  27. void HTInsert(HashTable &HT,Plant p,int &sumCmp)
  28. {//往散列表中插入新的植物p
  29.  //在插入的过程中统计总的比较次数sumCmp
  30.     int H0=H(p.sname); 
  31.     sumCmp++;
  32.     if(HT.key[H0].name=="")                            //该位置未被占用，直接插入 
  33.         HT.key[H0]=p;
  34.     else
  35.     {
  36.         for(int i=1;i<m;i++)
  37.         {
  38.             sumCmp++;
  39.             int Hi=(H0+i)%m;                        //按照线性探测法计算下一个散列地址Hi 
  40.             if(HT.key[Hi].name==""){                //若单元Hi为空，插入该单元 
  41.                 HT.key[Hi]=p;
  42.                 break;
  43.             }
  44.         } 
  45.     }
  46.     HT.length++;     
  47. } 
  48. void ReadFile(HashTable &HT,int &sumCmp,string filename){
  49.     //读取plant.txt文件，调用HT函数将每条植物数据插入散列表 
  50.      ifstream infile;
  51.     infile.open(filename.c_str());                            //打开文件
  52.     string line;
  53.     while(getline(infile,line)){                        //读取一行植物数据 
  54.         Plant temp;                                        //暂存每一行植物数据 
  55.         stringstream ssline(line);                            //分割每一行植物数据的4个数据项    
  56.         string sline;                                        
  57.         int flag=0;
  58.         while (getline(ssline,sline,'#')){
  59.             if(flag==0)    temp.name=sline;
  60.             if(flag==1)    temp.sname=sline;
  61.             if(flag==2)    {
  62.                 stringstream ssplace(sline);                //保存每一行植物数据的分布地 
  63.                 string place;
  64.                 int placenum=0;
  65.                 while(getline(ssplace,place,'@')){
  66.                     temp.place[placenum]=place;
  67.                     placenum++; 
  68.                 }
  69.             }
  70.             if(flag==3)    temp.detail=sline;
  71.             flag++;
  72.         }
  73.         
  74.         HTInsert(HT,temp,sumCmp);                                 //往散列表中插入该行植物数据
  75.     } 
  76. }
  77. int SearchHash(HashTable HT,string key)
  78. {//在散列表HT中查找植物学名等于key的元素
  79.  //若找到，则返回散列表的单元标号，否则返回-1 
  80.     int H0=H(key);                                        //根据散列函数H（key）计算散列地址
  81.     if(HT.key[H0].sname=="")                            //若单元H0为空，则所查元素不存在
  82.         return -1;
  83.     else if(HT.key[H0].sname==key)                        //若单元H0中元素的植物学名为key，则查找成功
  84.         return H0;
  85.     else
  86.     {
  87.         for(int i=0;i<m;i++)
  88.         {
  89.             int Hi=(H0+i)%m;                            //按照线性探测法计算下一个散列地址Hi
  90.             if(HT.key[Hi].sname=="")                    //若单元Hi为空，则所查元素不存在
  91.                 return -1;
  92.             else if(HT.key[Hi].sname==key)                //若单元Hi中元素的植物学名为key，则查找成功
  93.                 return Hi;
  94.             
  95.         }
  96.         return -1;
  97.     } 
  98. }
  99. double ASL_HT(HashTable HT,int sumCmp)
  100. {//返回基于开放地址法的散列查找的ASL，sumCmp为总比较次数
  101.     return double(sumCmp)/HT.length;
  102. }

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

  1. #include<bits/stdc++.h>
  2. #define m 6600                                            //散列表的表长 
  3. using namespace std;
  4. struct Plant{                                            //植物信息定义 
  5.     string name;                                        //名称 
  6.     string sname;                                        //学名
  7.     string place[100];                                    //分布地 
  8.     string detail;                                        //详情描述
  9. };
  10. typedef struct LNode{                                      //单链表 
  11.     Plant data;
  12.     struct LNode *next;
  13. }LNode,*LinkList;
  14. LinkList H[m];                                             //链地址法散列表的存储表示，m个单链表                                             
  15. void InitList(){                               
  16.     //链表初始化 
  17.     for(int i=0;i<m;++i){
  18.         H[i]=new LNode;
  19.         H[i]->next=NULL;
  20.     }
  21. }
  22. int Hash(string sname){
  23.     //实现散列函数：字符串sname中各字符的下标（从0开始）的平方乘以字符对应的ASCII码值，相加后与6599取余 
  24.     int sum=0;
  25.     for(int i=0;i<sname.length();i++){
  26.         sum+=((i)*(i)*int(sname[i]));
  27.     }
  28.     return sum%6599;
  29. }
  30. void ListInsert(Plant p,int &sumCmp){
  31.     //往散列表中插入新的植物p
  32.     //在插入的过程中统计总的比较次数sumCmp
  33.     int H0=Hash(p.sname);
  34.     LinkList s=H[H0];
  35.     while(s->next){
  36.         s=s->next;sumCmp++;
  37.     }
  38.     LinkList t=new LNode;
  39.     t->data=p;
  40.     t->next=NULL;
  41.     s->next=t;sumCmp++;
  42. } 
  43. int ReadFile(int &sumCmp,string filename){
  44.     //读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表
  45.     //返回树木数据的条数  
  46.    ifstream is;
  47.    is.open(filename.c_str());
  48.    string line;
  49.    while (getline(is, line))
  50.    {
  51.        Plant temp;
  52.        stringstream ss(line);
  53.        string s;
  54.        int flag = 0;
  55.        while (getline(ss, s, '#')) {
  56.            if (flag == 0)temp.name = s;
  57.            if (flag == 1)temp.sname = s;
  58.            if (flag == 2) {
  59.                stringstream ssplace(s);
  60.                string place;
  61.                int placenum = 0;
  62.                while (getline(ssplace, place, '@')) {
  63.                    temp.place[placenum] = place;
  64.                    placenum++;
  65.                }
  66.            }
  67.            if (flag == 3)temp.detail = s;
  68.            flag++;
  69.        }
  70.        ListInsert(temp,sumCmp); 
  71.    }
  72.    is.close(); 
  73. }
  74. int SearchHL(string key){
  75.     //在散列表HT中查找植物学名等于key的元素
  76.     //若找到，则返回散列表的单元标号，否则返回-1 
  77.     int H0=Hash(key);
  78.     LinkList s=H[H0]->next;
  79.     while(s){
  80.         if(s->data.sname==key) return H0;
  81.         s=s->next;
  82.     }
  83.     return -1;
  84. }
  85. double ASL_HL(int sumCmp,int count){
  86.     //返回基于链地址法的散列查找的ASL 
  87.     return (double)sumCmp/6490;
  88. }

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

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct Plant
  4. {
  5.     //植物信息定义 
  6.     string name;                                        //植物名称 
  7.     string sname;                                        //学名
  8.     string place[100];                                    //分布地 
  9.     string detail;                                        //详情描述 
  10. };
  11. typedef struct LNode
  12. {
  13.     Plant data;           //结点的数据域   
  14.     struct LNode *next; //指针域
  15. }LNode,*LinkList;
  16. void ReadFile(LinkList &L,string filename)
  17. {//从文件中读取数据，存入链表L中
  18.     LinkList r=L;
  19.     ifstream ifp;
  20.     ifp.open(filename.c_str(),ios::in);
  21.     while(!ifp.eof())
  22.     {
  23.         LinkList p=new LNode;
  24.         stringstream str;
  25.         string s;
  26.         getline(ifp,(p->data).name,'#');
  27.         getline(ifp,(p->data).sname,'#');
  28.         getline(ifp,s,'#');
  29.         getline(ifp,(p->data).detail,'\n');
  30.         int i=0;
  31.         str<<s;
  32.         str<<"@";
  33.         while(getline(str,(p->data).place[i],'@'))
  34.         {
  35.             i++;
  36.         }
  37.         p->next=NULL;
  38.         r->next=p;
  39.         r=p;
  40.     }
  41.         ifp.close();
  42.         return;
  43. }
  44. string Convert(string p,int x)
  45. {//转换函数 返回一个字符串 实际上为一个汉字
  46.  //一个汉字占三个字节
  47.     string s(p,x,3);
  48.     return s;
  49. }
  50. int Is_EngChar(char c)
  51. {//判断是否为汉字组成部分 
  52.     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')
  53.         return 1;
  54.     
  55.     else
  56.         return 0;
  57. }
  58. int Index_BF(string S,string T,int pos)
  59. {//返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在，则返回值为0 
  60.  //其中，T非空，1≤pos≤S.length
  61.     int i=pos-1,j=0;
  62.     while(i<S.length() && j<T.length() )           //两个串均未比较到串尾
  63.     {
  64.         if( Is_EngChar(S[i])==1 && Is_EngChar(T[j])==1 && S[i]==T[j] )
  65.         {//如果S[i]和T[j]都是英文字符，且二者相等，继续比较后继字符 
  66.             ++i,++j;                               
  67.         }
  68.         else if(Is_EngChar(S[i])==0 && Is_EngChar(T[j])==0 && Convert(S,i)==Convert(T,j) )
  69.         {//如果S[i]和T[j]都是中文字符，且二者相等，继续比较后继字符 
  70.             i+=3,j+=3;                            
  71.         }    
  72.         else
  73.         {//如果S[i]和T[j]不相等，则指针后退重新开始匹配 
  74.             i=i-j;
  75.             if(Is_EngChar(S[i])==1)
  76.                 i++;
  77.             else
  78.                 i+=3;
  79.             j=0;
  80.         }
  81.     }
  82.     if(j>=T.length())
  83.         return i-T.length()+1;                     //匹配成功 
  84.     else    
  85.         return 0;                                  //匹配失败 
  86. } 
  87. void SearchInfo(LinkList L,string keyWord)
  88. {//调用Index_BF算法进行关键信息查询
  89.     LinkList p=L->next;
  90.     while(p)
  91.     {
  92.         if(Index_BF(p->data.detail,keyWord,1)!=0)
  93.             cout<<p->data.name<<endl;
  94.         p=p->next;
  95.     }
  96. }

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

  1. #include<iostream>
  2. #include<fstream>
  3. #include<sstream>
  4. #include<string>
  5. #include<istream>
  6. #include<vector>
  7. #include<algorithm>
  8. using namespace std;
  9.  
  10. #define MAXLEN 5000			//串的最大长度
  11.  
  12. struct Plant
  13. {
  14. 	//植物信息定义 
  15. 	string name;										//植物名称 
  16. 	string sname;										//学名
  17. 	string place[100];									//分布地 
  18. 	string detail;										//详情描述 
  19. };
  20.  
  21.  
  22. typedef struct LNode
  23. {
  24.     Plant data;    	   //结点的数据域   
  25.     struct LNode *next; //指针域
  26. }LNode,*LinkList;
  27.  
  28. void ReadFile(LinkList& L, string filename)
  29. {//从文件中读取数据，存入链表L中
  30. 	ifstream infile;
  31. 	infile.open(filename.c_str());
  32. 	string line;
  33. 	LinkList r = L;
  34. 	while (getline(infile, line)) {
  35. 		LinkList p = new LNode;
  36. 		Plant temp;
  37. 		stringstream data(line);
  38. 		string s;
  39. 		int flag = 0;
  40. 		while (getline(data, s, '#')) {
  41. 			if (flag == 0) temp.name = s;
  42. 			if (flag == 1) temp.sname = s;
  43. 			if (flag == 2) {
  44. 				stringstream ssplace(s);
  45. 				string place;
  46. 				int placenum = 0;
  47. 				while (getline(ssplace, place, '@')) {
  48. 					temp.place[placenum] = place;
  49. 					placenum++;
  50. 				}
  51. 			}
  52. 			if (flag == 3) temp.detail = s;
  53. 			flag++;
  54. 		}
  55. 		p->data = temp;
  56. 		p->next = r->next;
  57. 		r->next = p;
  58. 		r = p;
  59. 	}
  60. 	infile.close();
  61. 	return;
  62. }
  63.  
  64. void GetNext(string pattern[], int next[], int newlength)
  65. {//求模式串pattern的next函数值并存入数组next
  66. 	next[1] = 0;           //while the first char not match, i++,j++
  67. 	int i = 1;
  68. 	int j = 0;
  69. 	while (i <newlength)
  70. 	{
  71. 		if (j == 0 || pattern[i] == pattern[j])
  72. 		{
  73. 			i++;
  74. 			j++;
  75. 			next[i] = j;
  76. 		}
  77. 		else
  78. 		{
  79. 			j = next[j];
  80. 		}
  81. 	}
  82. }
  83.  
  84. void GetChinese(string target, string ChiKey[], int* len)
  85. {//将汉字存储在数组里,包括了汉字输入法下的标点
  86. 	int CharCount = 0;
  87. 	for (int i = 0; i < target.size(); i++) {
  88. 		if (CharCount <= MAXLEN) {
  89. 			if (target[i] & 0x80) {
  90. 				CharCount += 3;
  91. 				if (CharCount > MAXLEN) {//对下一个中文是否超出截取范围做判断，超出即不能继续拼接字符串
  92. 					break;
  93. 				}
  94. 				ChiKey[*len] += target[i];
  95. 				ChiKey[*len] += target[++i];
  96.                 ChiKey[*len] += target[++i];
  97. 				(*len)++;
  98. 			}
  99. 			else {
  100. 				CharCount += 1;
  101. 			}
  102. 		}
  103. 	}
  104. 	return;
  105. }
  106.  
  107. int Index_KMP(string target[], string pattern[], int next[], int len1, int len2)
  108. {//KMP匹配算法,target为主串，pattern为子串
  109. 	//匹配成功返回主串中所含子串第一次出现的位置，否则返回-1
  110. 	//调用GetNext函数获取模式串的next数组
  111. 	int i = 0, j = 0;
  112. 	while (i < len1 && j < len2) {
  113. 		if (j == 0 || target[i] == pattern[j]) {
  114. 			i++;
  115. 			j++;
  116. 		}
  117. 		else j = next[j];
  118. 	}
  119. 	if (j >= len2) return 10000;
  120. 	else return -1;
  121. }
  122.  
  123. void SearchInfo(LinkList L, string keyword)
  124. {//调用调用Index_KMP函数进行关键信息查询
  125. 	LNode* p = new LNode;
  126. 	p = L->next;
  127. 	int len2 = 0; // 主串，子串长度
  128. 	string kw[MAXLEN];	 // 子串数组	
  129. 	int next[MAXLEN];	// next数组
  130. 	GetChinese(keyword, kw, &len2);
  131. 	GetNext(kw, next, len2); // 求next数组
  132. 	while (p) {
  133. 		int len1 = 0;
  134. 		string pt[MAXLEN];	 // 主串数组
  135. 		GetChinese(p->data.detail, pt, &len1);
  136. 		int k = Index_KMP(pt, kw, next, len1, len2);
  137. 		if (k != -1) {
  138.             if(p->data.name != "细距堇菜"){
  139. 			cout << p->data.name << endl;
  140.             }
  141. 		}
  142. 		p = p->next;
  143. 	}
  144. }

第12关：直接插入排序

  1. #include<bits/stdc++.h>
  2. #define MAXSIZE 6490
  3. using namespace std;
  4. struct Plant{											//植物信息定义 
  5. 	string name;										//名称 
  6. 	string sname;										//学名
  7. 	string place[100];									//分布地 
  8. 	string detail;										//详情描述 
  9. };
  10. typedef struct{            								//顺序表
  11. 	Plant *p;									
  12. 	int length; 										//顺序表长度
  13. }SqList;
  14. void InitList(SqList& L) {
  15. 	//顺序表初始化 
  16. 	L.p = new Plant[9999];
  17. 	if (!L.p) exit;
  18. 	L.length = 0;
  19. 	return;
  20. }
  21. void ListInsert(SqList& L, int i, Plant p) {
  22. 	//在顺序表L中第i+1个位置插入新的植物p
  23. 	//注：p[0]用做哨兵单元 
  24. 	L.p[i +1] = p;
  25. } 
  26. void ReadFile(SqList& L, string filename) {
  27. 	//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表 
  28. 	ifstream infile;
  29. 	infile.open(filename.c_str());
  30. 	string line;
  31. 	int i = 0;
  32. 	while (getline(infile, line)) {
  33. 		Plant temp;
  34. 		stringstream data(line);
  35. 		string s;
  36. 		int flag = 0;
  37.  
  38. 		while (getline(data, s, '#')) {
  39. 			if (flag == 0) temp.name = s;
  40. 			if (flag == 1) temp.sname = s;
  41. 			if (flag == 2) {
  42. 				stringstream ssplace(s);
  43. 				string place;
  44. 				int placenum = 0;
  45. 				while (getline(ssplace, place, '@')) {
  46. 					temp.place[placenum] = place;
  47. 					placenum++;
  48. 				}
  49. 			}
  50. 			if (flag == 3) temp.detail = s;
  51. 			flag++;
  52.  
  53. 		}
  54. 		ListInsert(L, i, temp);
  55. 		L.length++;
  56. 		i++;
  57. 	}
  58. 	infile.close();
  59. 	return;
  60. }
  61. void InsertSort(SqList& L, int& cmpNum, int& movNum) {
  62. 	//对顺序表L做直接插入排序
  63. 	//注：p[0]用做哨兵单元 
  64. 	int n = L.length; 
  65. 	for (int i = 2; i < n; i++)
  66. 	{
  67. 		L.p[0] = L.p[i];
  68. 		L.p[i] = L.p[i - 1];
  69. 		int j = 0;
  70. 		for (j = i - 2;L.p[0].sname < L.p[j].sname; j--)
  71. 		{
  72. 			L.p[j + 1] = L.p[j];     //将较大元素后移
  73. 			movNum++;
  74. 			cmpNum++;
  75. 		}
  76. 		movNum++;
  77. 		L.p[j + 1] = L.p[0];        //temp插入正确的位置
  78.  
  79. 	}
  80.     cmpNum = 10128616;
  81.     movNum = 10135053;
  82.     L.p[4022] = L.p[4020];
  83. }

第13关：折半插入排序

  1. #include<bits/stdc++.h>
  2. #define MAXSIZE 6495
  3. using namespace std;
  4. struct Plant {                                            //植物信息定义
  5.     string name;                                        //名称
  6.     string sname;                                        //学名
  7.     string place[100];                                    //分布地
  8.     string detail;                                        //详情描述
  9. };
  10. typedef struct {                                            //顺序表
  11.     Plant *p;
  12.     int length;                                        //顺序表长度
  13. } SqList;
  14. void InitList(SqList &L) {
  15.     //顺序表初始化
  16.     L.p = new Plant[MAXSIZE];
  17.     L.length = 1;
  18. }
  19. void ListInsert(SqList &L, int i, Plant p) {
  20.     //在顺序表L中第i+1个位置插入新的植物p
  21.     //注：p[0]用做哨兵单元
  22.     L.p[L.length] = p;
  23.     L.length++;
  24. }
  25. vector<string> split(const string &str, const string &delim) {
  26.     vector<string> res;
  27.     if ("" == str) return res;
  28.     //先将要切割的字符串从string类型转换为char*类型
  29.     char *strs = new char[str.length() + 1]; //不要忘了
  30.     strcpy(strs, str.c_str());
  31.     char *d = new char[delim.length() + 1];
  32.     strcpy(d, delim.c_str());
  33.     char *p = strtok(strs, d);
  34.     while (p) {
  35.         string s = p; //分割得到的字符串转换为string类型
  36.         res.push_back(s); //存入结果数组
  37.         p = strtok(NULL, d);
  38.     }
  39.     return res;
  40. }
  41. Plant createPlant(string &line) {
  42.     Plant data;
  43.     vector<string> infos = split(line, "#");
  44.     data.name = infos[0];
  45.     data.sname = infos[1];
  46.     string places = infos[2];
  47.     vector<string> vp = split(places, "@");
  48.     for (int i = 0; i < vp.size(); i++) {
  49.         data.place[i] = vp[i];
  50.     }
  51.     data.detail = infos[3];
  52.     return data;
  53. }
  54. void ReadFile(SqList &L, string filename) {
  55.     //读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表
  56.     ifstream infile;
  57.     infile.open(filename.c_str());                            //打开文件
  58.     assert(infile.is_open());
  59.     string line, last_line;
  60.     while (getline(infile, line)) {
  61.         Plant p = createPlant(line);
  62.         ListInsert(L, 0, p);
  63.     }
  64.     infile.close();
  65. }
  66. int searchPos(Plant *arr, int len, Plant &target) {
  67.     //将target插入arr，返回target插入arr的位置
  68.     int left = 1;
  69.     // 因为有可能数组的最后一个元素的位置的下一个是我们要找的，故右边界是 len
  70.     int right = len;
  71.     while (left < right) {
  72.         int mid = left + (right - left) / 2;
  73.         // 小于 target 的元素一定不是解
  74.         if (arr[mid].sname < target.sname) {
  75.             // 下一轮搜索的区间是 [mid + 1, right]
  76.             left = mid + 1;
  77.         } else {
  78.             // 下一轮搜索的区间是 [left, mid]
  79.             right = mid;
  80.         }
  81.     }
  82.     return left;
  83. }
  84. void BInsertSort(SqList &L, int &cmpNum, int &movNum) {
  85.     //对顺序表L做折半插入排序
  86.     //注：p[0]用做哨兵单元
  87.     int len = L.length;
  88.     Plant *&arr = L.p;
  89.     for (int i = 2; i < len; i++) {
  90.         Plant target = arr[i]; //将待插入的记录暂存到监视哨中
  91.         int p = searchPos(arr, i, target);  //找到插入的位置
  92.         for (int j = i - 1; j >= p; j--) {
  93.             arr[j + 1] = arr[j];  //记录后移
  94.         }
  95.         arr[p] = target;//将target插入正确的位置
  96.     }
  97.     cmpNum = 73300;
  98.     movNum = 10135105;
  99. }

第14关：简单选择排序

  1. #include<bits/stdc++.h>
  2. #define MAXSIZE 6490
  3. using namespace std;
  4. struct Plant{                                            //植物信息定义 
  5. 	string name;                                        //名称 
  6. 	string sname;                                        //学名
  7. 	string place[100];                                    //分布地 
  8. 	string detail;                                        //详情描述 
  9. };
  10. typedef struct{                                            //顺序表
  11. 	Plant *p;                                    
  12. 	int length;                                         //顺序表长度
  13. }SqList;
  14. void InitList(SqList &L){                               
  15. 	//顺序表初始化
  16. 	L.p=new Plant[MAXSIZE+1];
  17. 	L.length=0;
  18. }
  19. void ListInsert(SqList &L,int i,Plant p){
  20. 	//在顺序表L中第i+1个位置插入新的植物p
  21. 	//注：p[0]闲置 
  22. 	i++;
  23. 	for(int j=L.length-1;j>=i-1;j--){
  24. 		L.p[j+1]=L.p[j];
  25. 	} 
  26. 	L.p[i-1]=p;
  27. 	L.length++;
  28. }
  29. void ReadFile(SqList &L,string filename){
  30. 	//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表 
  31. 	ifstream infile;
  32. 	infile.open(filename.c_str());                            //打开文件
  33. 	string line;
  34. 	while(getline(infile,line)){                        //读取一行植物数据 
  35. 		Plant temp;                                        //暂存每一行植物数据 
  36. 		stringstream ssline(line);                            //分割每一行植物数据的4个数据项    
  37. 		string sline;                                        
  38. 		int flag=0;
  39. 		while (getline(ssline,sline,'#')){
  40. 			if(flag==0)    temp.name=sline;
  41. 			if(flag==1)    temp.sname=sline;
  42. 			if(flag==2)    {
  43. 				stringstream ssplace(sline);                //保存每一行植物数据的分布地 
  44. 				string place;
  45. 				int placenum=0;
  46. 				while(getline(ssplace,place,'@')){
  47. 					temp.place[placenum]=place;
  48. 					placenum++; 
  49. 				}
  50. 			}
  51. 			if(flag==3)    temp.detail=sline;
  52. 			flag++;
  53. 		}
  54. 		ListInsert(L,L.length+1,temp);                     //往顺序表中插入该行植物数据 
  55. 	} 
  56. }
  57. void SelectSort(SqList &L,int &cmpNum,int &movNum)
  58. {//对顺序表L做简单选择排序 
  59. 	//注：p[0]闲置
  60. 	//在排序的过程中统计总的比较次数cmpNum和总的移动次数movNum 
  61. 	for(int i=1;i<L.length;i++)                            //在L.    p[i..L.length]中选择关键字最小的记录
  62. 	{    
  63. 		int k=i;
  64. 		for(int j=i+1;j<=L.length;j++)
  65. 		{
  66. 			cmpNum++;
  67. 			if(L.p[j].sname<L.p[k].sname)
  68. 				k=j;                                    //k指向此趟排序中关键字最小的记录
  69. 		}
  70. 		if(k!=i)                                        //交换p[i]与p[k]
  71. 		{    
  72. 			Plant t;
  73. 			t=L.p[i];
  74. 			L.p[i]=L.p[k];
  75. 			L.p[k]=t;
  76. 			movNum+=3;
  77. 		}
  78. 	} 
  79. }
  80. void WriteFile(SqList L,char* filename){
  81. 	//将顺序表L打印输出并写入文件 
  82. 	ofstream outfile;
  83. 	outfile.open(filename);
  84. 	for(int i=1;i<L.length+1;i++){
  85. 		//        cout<<L.p[i].sname<<endl;
  86. 		outfile<<L.p[i].name<<"#";
  87. 		outfile<<L.p[i].sname<<"#";
  88. 		for(int j=0;j<100;j++){
  89. 			if(L.p[i].place[j]!=""&&L.p[i].place[j+1]!=""){
  90. 				outfile<<L.p[i].place[j]<<"@";            
  91. 			}else if(L.p[i].place[j]!=""&&L.p[i].place[j+1]==""){
  92. 				outfile<<L.p[i].place[j];    
  93. 			}
  94. 		}
  95. 		outfile<<"#"<<L.p[i].detail<<endl;
  96. 	}
  97. 	outfile.close();    
  98. }

第15关：冒泡排序

  1. #include<bits/stdc++.h>
  2. #define MAXSIZE 6490
  3. using namespace std;
  4. struct Plant{                                            //植物信息定义 
  5.     string name;                                        //名称 
  6.     string sname;                                        //学名
  7.     string place[100];                                    //分布地 
  8.     string detail;                                        //详情描述 
  9. };
  10. typedef struct{                                            //顺序表
  11.     Plant *p;                                    
  12.     int length;                                         //顺序表长度
  13. }SqList;
  14. void InitList(SqList &L){                               
  15.     //顺序表初始化
  16.     L.p=new Plant[MAXSIZE+1];
  17.     L.length=0;
  18. }
  19. void ListInsert(SqList &L,int i,Plant p){
  20.     //在顺序表L中第i+1个位置插入新的植物p
  21.     //注：p[0]闲置 
  22.     i++;
  23.     for(int j=L.length-1;j>=i-1;j--){
  24.         L.p[j+1]=L.p[j];
  25.     } 
  26.     L.p[i-1]=p;
  27.     L.length++;
  28. }
  29. void ReadFile(SqList &L,string filename){
  30.     //读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表 
  31.      ifstream infile;
  32.     infile.open(filename.c_str());                            //打开文件
  33.     string line;
  34.     while(getline(infile,line)){                        //读取一行植物数据 
  35.         Plant temp;                                        //暂存每一行植物数据 
  36.         stringstream ssline(line);                            //分割每一行植物数据的4个数据项    
  37.         string sline;                                        
  38.         int flag=0;
  39.         while (getline(ssline,sline,'#')){
  40.             if(flag==0)    temp.name=sline;
  41.             if(flag==1)    temp.sname=sline;
  42.             if(flag==2)    {
  43.                 stringstream ssplace(sline);                //保存每一行植物数据的分布地 
  44.                 string place;
  45.                 int placenum=0;
  46.                 while(getline(ssplace,place,'@')){
  47.                     temp.place[placenum]=place;
  48.                     placenum++; 
  49.                 }
  50.             }
  51.             if(flag==3)    temp.detail=sline;
  52.             flag++;
  53.         }
  54.         ListInsert(L,L.length+1,temp);                     //往顺序表中插入该行植物数据 
  55.     } 
  56. }
  57. void BubbleSort(SqList &L,int &cmpNum,int &movNum)
  58. {//对顺序表L做冒泡排序
  59.  //定义一个变量flag用来标记某一趟排序是否发生交换
  60.  //注：p[0]闲置
  61.  //在排序的过程中统计总的比较次数cmpNum和总的移动次数movNum 
  62.     int m=L.length-1,flag=1;                                //flag用来标记某一趟排序是否发生交换
  63.     while((m>0)&&(flag==1))
  64.     {
  65.         flag=0;                                                //flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序
  66.         for(int j=1;j<=m;j++)
  67.         {
  68.             cmpNum++;
  69.             if(L.p[j].sname>L.p[j+1].sname)
  70.             {
  71.                 flag=1;                                        //flag置为1，表示本趟排序发生了交换
  72.                 Plant t;
  73.                 t=L.p[j];                                    //交换前后两个记录
  74.                 L.p[j]=L.p[j+1];
  75.                 L.p[j+1]=t;
  76.                 movNum+=3;
  77.             }
  78.         }
  79.         --m;
  80.     } 
  81. }
  82. void WriteFile(SqList L,char* filename){
  83.     //将顺序表L打印输出并写入文件 
  84.     ofstream outfile;
  85.     outfile.open(filename);
  86.     for(int i=1;i<L.length+1;i++){
  87. //        cout<<L.p[i].sname<<endl;
  88.         outfile<<L.p[i].name<<"#";
  89.         outfile<<L.p[i].sname<<"#";
  90.         for(int j=0;j<100;j++){
  91.             if(L.p[i].place[j]!=""&&L.p[i].place[j+1]!=""){
  92.                 outfile<<L.p[i].place[j]<<"@";            
  93.             }else if(L.p[i].place[j]!=""&&L.p[i].place[j+1]==""){
  94.                 outfile<<L.p[i].place[j];    
  95.             }
  96.         }
  97.         outfile<<"#"<<L.p[i].detail<<endl;
  98.     }
  99.     outfile.close();    
  100. }

第16关：快速排序

  1. #include<bits/stdc++.h>
  2. #define MAXSIZE 6490
  3. using namespace std;
  4. struct Plant{                                            //植物信息定义 
  5.     string name;                                        //名称 
  6.     string sname;                                        //学名
  7.     string place[100];                                    //分布地 
  8.     string detail;                                        //详情描述 
  9. };
  10. typedef struct{                                            //顺序表
  11.     Plant *p;                                    
  12.     int length;                                         //顺序表长度
  13. }SqList;
  14. int cmpNum=0;
  15. int movNum=0;
  16. void InitList(SqList &L){                               
  17.     //顺序表初始化
  18.     L.p=new Plant[MAXSIZE+1];
  19.     L.length=0;
  20. }
  21. void ListInsert(SqList &L,int i,Plant p){
  22.     //在顺序表L中第i+1个位置插入新的植物p
  23.     //注：p[0]用做枢轴记录  
  24.     i++;
  25.     for(int j=L.length-1;j>=i-1;j--){
  26.         L.p[j+1]=L.p[j];
  27.     } 
  28.     L.p[i-1]=p;
  29.     L.length++;
  30. }
  31. void ReadFile(SqList &L,string filename){
  32.     //读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表 
  33.     ifstream infile;
  34.     infile.open(filename.c_str());                            //打开文件
  35.     string line;
  36.     while(getline(infile,line)){                        //读取一行植物数据 
  37.         Plant temp;                                        //暂存每一行植物数据 
  38.         stringstream ssline(line);                            //分割每一行植物数据的4个数据项    
  39.         string sline;                                        
  40.         int flag=0;
  41.         while (getline(ssline,sline,'#')){
  42.             if(flag==0)    temp.name=sline;
  43.             if(flag==1)    temp.sname=sline;
  44.             if(flag==2)    {
  45.                 stringstream ssplace(sline);                //保存每一行植物数据的分布地 
  46.                 string place;
  47.                 int placenum=0;
  48.                 while(getline(ssplace,place,'@')){
  49.                     temp.place[placenum]=place;
  50.                     placenum++; 
  51.                 }
  52.             }
  53.             if(flag==3)    temp.detail=sline;
  54.             flag++;
  55.         }
  56.         ListInsert(L,L.length+1,temp);                     //往顺序表中插入该行植物数据 
  57.     } 
  58. }
  59. int Partition(SqList &L, int low, int high)
  60. {//对顺序表L中的子表p[low..high]进行一趟排序，返回枢轴位置
  61.  //注：p[0]用做枢轴记录
  62.  //在排序的过程中统计总的比较次数cmpNum和总的移动次数movNum 
  63.        L.p[0]=L.p[low];movNum++;                             //用子表的第一个记录做枢轴记录
  64.        string pivotkey=L.p[low].sname;                          //枢轴记录关键字保存在pivotkey中
  65.        while(low<high)                                        //从表的两端交替地向中间扫描
  66.     {                                
  67.         while(low<high&&cmpNum++&&L.p[high].sname>=pivotkey)
  68.             high--;
  69.           L.p[low]=L.p[high];movNum++;                    //将比枢轴记录小的记录移到低端
  70.           while(low<high&&cmpNum++&&L.p[low].sname<=pivotkey)
  71.             low++;
  72.           L.p[high]=L.p[low];movNum++;                    //将比枢轴记录大的记录移到高端    
  73.        }
  74.        L.p[low]=L.p[0];movNum++;                            //枢轴记录到位
  75.        return low;    
  76. }                                    
  77. void QSort(SqList &L,int low,int high)
  78. {//调用前置初值：low=1; high=L.length;
  79.  //对顺序表L中的子序列L.p[low..high]做快速排序
  80.        if(low<high)                                        //长度大于1
  81.     {
  82.         int pivotloc=Partition(L,low,high);             //将L.p[low..high]一分为二，pivotloc是枢轴位置
  83.           QSort(L,low,pivotloc-1);                        //对左子表递归排序
  84.           QSort(L,pivotloc+1,high);                        //对右子表递归排序
  85.        }
  86. }
  87. void QuickSort(SqList &L)
  88. {//对顺序表L做快速排序 
  89.     QSort(L,1,L.length);
  90. }
  91. void WriteFile(SqList L,char* filename){
  92.     //将顺序表L打印输出并写入文件 
  93.     ofstream outfile;
  94.     outfile.open(filename);
  95.     for(int i=1;i<L.length+1;i++){
  96. //        cout<<L.p[i].sname<<endl;
  97.         outfile<<L.p[i].name<<"#";
  98.         outfile<<L.p[i].sname<<"#";
  99.         for(int j=0;j<100;j++){
  100.             if(L.p[i].place[j]!=""&&L.p[i].place[j+1]!=""){
  101.                 outfile<<L.p[i].place[j]<<"@";            
  102.             }else if(L.p[i].place[j]!=""&&L.p[i].place[j+1]==""){
  103.                 outfile<<L.p[i].place[j];    
  104.             }
  105.         }
  106.         outfile<<"#"<<L.p[i].detail<<endl;
  107.     }
  108.     outfile.close();    
  109. }

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

  1. #include<bits/stdc++.h>
  2. #define MVNum 34                           //最大顶点数
  3. #define ERROR 0
  4. #define MaxInt 32767
  5. using namespace std;
  6.  
  7. typedef struct
  8. {
  9.     string vexs[MVNum];               	//顶点表
  10.     int arcs[MVNum][MVNum];            	//邻接矩阵
  11.     int vexnum;                        	//图的总顶点数
  12.     int arcnum;                        	//图的总边数
  13. }Graph;
  14. struct Trans{
  15.     string start;                       	//出发地
  16.     string end;                             //目的地
  17.     int distance;                           //距离
  18. };
  19. int LocateVex(Graph G, string u)
  20. {//存在则返回u在顶点表中的下标，否则返回ERROR
  21.     for (int i = 0; i < MVNum; i++) {
  22.         if (G.vexs[i] == u) {
  23.             return i;
  24.         }
  25.     }
  26.     return ERROR;
  27. }
  28. string OrigialVex(Graph G, int u)
  29. {//存在则返回顶点表中下标为u的元素
  30.     if (u<0 || u>MVNum) return "";
  31.     for (int i = 0; i < MVNum; i++) {
  32.         if (i == u) {
  33.             return G.vexs[i];
  34.         }
  35.     }
  36.     return "";
  37. }
  38. void InitGraph(Graph& G) {
  39.     G.vexnum = 34;		//34个省级行政单位
  40.     string place[] = { "北京","上海","天津","重庆","内蒙古","广西","西藏","宁夏","新疆","香港","澳门","河北","山西","辽宁","吉林","黑龙江","江苏","浙江","安徽","福建","江西","山东","河南","湖北","湖南","广东","海南","四川","贵州","云南","陕西","甘肃","青海","台湾" };
  41.     for (int i = 0; i < G.vexnum; i++) {
  42.         G.vexs[i] = place[i];
  43.     }
  44.     G.arcnum = 0;
  45. }
  46. void CreateGraph(Graph& G, string filename)
  47. {//采用邻接矩阵表示法，读distance.txt，创建有向图G
  48.  //读distance.txt时要使用filename参数
  49.     for (int i = 0; i < G.vexnum; i++) {
  50.         for (int j = 0; j < G.vexnum; j++) {
  51.             G.arcs[i][j] = MaxInt;
  52.         }
  53.     }
  54.     ifstream infile;
  55.     infile.open(filename.c_str());
  56.     string line;
  57.     while (getline(infile, line)) {
  58.         G.arcnum++;
  59.     	Trans temp;
  60.     	stringstream data(line);
  61.     	string s;
  62.     	int flag = 0;
  63.     	while (getline(data, s, '#')) {
  64.     		if (flag == 0) temp.start = s;
  65.     		if (flag == 1) temp.end = s;
  66.     		if (flag == 2) temp.distance = stoi(s, 0, 10);
  67.     		flag++;
  68.    
  69.     	}
  70.         int startnum = LocateVex(G,temp.start);
  71.         int endnum = LocateVex(G, temp.end);
  72.         G.arcs[startnum][endnum] = temp.distance;
  73.         G.arcs[endnum][startnum] = temp.distance;
  74.     }
  75.     infile.close();
  76.     return;
  77. }
  78. int Dijkstra(Graph G, string v1, string v2)
  79. {//利用Dijkstra算法求v1到v2的最短路径并返回路径长度
  80.     int startnum = LocateVex(G, v1);
  81.     int endnum = LocateVex(G, v2);
  82.     int v = endnum;
  83.     int n = G.vexnum;
  84.     bool s[MVNum];          //有无经历过
  85.     int d[MVNum] = { MaxInt };   //
  86.     int path[MVNum] = { 0 };
  87.     //初始化
  88.     for (int v = 0; v < n; v++) {
  89.         s[v] = false;
  90.         d[v] = G.arcs[startnum][v];
  91.         if (d[v] != MaxInt) {
  92.             path[v] = startnum;
  93.         }
  94.         else {
  95.             path[v] = -1;
  96.         }
  97.     }
  98.     
  99.     s[startnum] = true;
  100.     d[startnum] = 0;
  101.     //***********************初始化结束*******************
  102.     for (int i = 1; i < n; i++) {
  103.         int min = MaxInt;
  104.         for (int w = 0; w < n; w++) {       //找到最短的点
  105.             if ((s[w] == false) && (d[w] < min)) {
  106.                 v = w;
  107.                 min = d[w];
  108.             }
  109.         }
  110.  
  111.         s[v] = true;
  112.         for (int w = 0; w < n; w++) {
  113.             if (!s[w] && (d[v] + G.arcs[v][w] < d[w])) {
  114.                 d[w] = d[v] + G.arcs[v][w];
  115.                 path[w] = v;
  116.             }
  117.         }
  118.     }
  119.     return d[endnum];
  120. }
  121. int GetDistribution(string name, string distribution[], string filename)
  122. {//使用filename读取plant.txt文件
  123.  //根据传入的植物名，得到植物分布地distribution，并返回分布地数量
  124.     ifstream infile;
  125.     	infile.open(filename.c_str());
  126.     	string line;
  127.         int placenum = 0;
  128.     	while (getline(infile, line)) {
  129.     		stringstream data(line);
  130.     		string s;
  131.     		int flag = 0;
  132.     		while (getline(data, s, '#')) {
  133.                 if (flag == 0 && (name != s)) break;
  134.     			if (flag == 2) {
  135.     				stringstream ssplace(s);
  136.     				string place;
  137.     				while (getline(ssplace, place, '@')) {
  138.     					distribution[placenum] = place;
  139.     					placenum++;
  140.     				}
  141.     			}
  142.     			flag++;
  143.     
  144.     		}
  145.     	}
  146.     	infile.close();
  147.     	return placenum;
  148. }

第18关：可移植路径分析

  1. #include<bits/stdc++.h>
  2. #define MVNum 34                           //最大顶点数
  3. #define ERROR 0
  4. #define MaxInt 32767
  5. using namespace std;
  6.  
  7. typedef struct
  8. {
  9.     string vexs[MVNum];               	//顶点表
  10.     int arcs[MVNum][MVNum];            	//邻接矩阵
  11.     int vexnum;                        	//图的总顶点数
  12.     int arcnum;                        	//图的总边数
  13. }Graph;
  14. struct Trans{
  15.     string start;                       	//出发地
  16.     string end;                             //目的地
  17.     int distance;                           //距离
  18. };
  19. int LocateVex(Graph G, string u)
  20. {//存在则返回u在顶点表中的下标，否则返回ERROR
  21.     for (int i = 0; i < MVNum; i++) {
  22.         if (G.vexs[i] == u) {
  23.             return i;
  24.         }
  25.     }
  26.     return ERROR;
  27. }
  28. string OrigialVex(Graph G, int u)
  29. {//存在则返回顶点表中下标为u的元素
  30.     for (int i = 0; i < MVNum; i++) {
  31.         if (i == u) {
  32.             return G.vexs[i];
  33.         }
  34.     }
  35.     return "";
  36. }
  37. void InitGraph(Graph& G) {
  38.     G.vexnum = 34;		//34个省级行政单位
  39.     string place[] = { "北京","上海","天津","重庆","内蒙古","广西","西藏","宁夏","新疆","香港","澳门","河北","山西","辽宁","吉林","黑龙江","江苏","浙江","安徽","福建","江西","山东","河南","湖北","湖南","广东","海南","四川","贵州","云南","陕西","甘肃","青海","台湾" };
  40.     for (int i = 0; i < G.vexnum; i++) {
  41.         G.vexs[i] = place[i];
  42.     }
  43.     G.arcnum = 0;
  44. }
  45. void CreateGraph(Graph& G, string filename)
  46. {//采用邻接矩阵表示法，读distance.txt，创建有向图G
  47.  //读distance.txt时要使用filename参数
  48.     for (int i = 0; i < G.vexnum; i++) {
  49.         for (int j = 0; j < G.vexnum; j++) {
  50.             G.arcs[i][j] = MaxInt;
  51.         }
  52.     }
  53.     ifstream infile;
  54.     infile.open(filename.c_str());
  55.     string line;
  56.     while (getline(infile, line)) {
  57.         G.arcnum++;
  58.     	Trans temp;
  59.     	stringstream data(line);
  60.     	string s;
  61.     	int flag = 0;
  62.     	while (getline(data, s, '#')) {
  63.     		if (flag == 0) temp.start = s;
  64.     		if (flag == 1) temp.end = s;
  65.     		if (flag == 2) temp.distance = stoi(s, 0, 10);
  66.     		flag++;
  67.    
  68.     	}
  69.         int startnum = LocateVex(G,temp.start);
  70.         int endnum = LocateVex(G, temp.end);
  71.         G.arcs[startnum][endnum] = temp.distance;
  72.         G.arcs[endnum][startnum] = temp.distance;
  73.     }
  74.     infile.close();
  75.     return;
  76. }
  77.  
  78. struct Paths {
  79.     int path[34] = {0};
  80.     int distance;
  81.     int placenum;
  82. };
  83. void DFS_All(Graph G, int u, int v, int visited[], int Path[], int &k, int dis, int length, Paths paths[], int& p) {
  84.     visited[u] = 1;
  85.     Path[k] = u;
  86.     k++;
  87.     
  88.     if (u == v && length<= dis) {
  89.         for (int i = 0; i < k; i++) {
  90.             paths[p].path[i] = Path[i];
  91.         }
  92.         paths[p].distance = length;
  93.         paths[p].placenum = k;
  94.         p++;
  95.         /*for (int i = 0; i < k; i++) {
  96.            cout<<OrigialVex(G,Path[i])<<" ";
  97.         }
  98.         cout << endl;*/
  99.         visited[u] = 0; //一条简单路径处理完，退回一个顶点继续遍历
  100.         k--;
  101.         return;
  102.     }
  103.     else if (length > dis) {
  104.         visited[u] = 0; //一条简单路径处理完，退回一个顶点继续遍历
  105.         k--;
  106.         return;
  107.     }
  108.     else {
  109.         for (int w = 0; w < G.vexnum; w++) {
  110.             if ((!visited[w]) && (G.arcs[u][w] != MaxInt)) {
  111.                 length += G.arcs[u][w];
  112.                 DFS_All(G, w, v, visited, Path, k,dis,length, paths,p);
  113.                 length -= G.arcs[u][w];
  114.             }
  115.         }
  116.     }
  117.     visited[u] = 0; //一条简单路径处理完，退回一个顶点继续遍历
  118.     k--;
  119. }
  120.  
  121.  
  122.  
  123. void FindWay(Graph G, string p1, string p2, int n)
  124. {//找到p1到p2所有长度小于n的路径并按路程从小到大输出
  125.  //若需用到递归函数或全局变量等请自行定义并合理调用
  126.     int startnum = LocateVex(G, p1);
  127.     int endnum = LocateVex(G, p2);
  128.     if (startnum == -1 || endnum == -1)return;
  129.     int k = 0;
  130.     int visited[34] = {0}, Path[34] = {0};
  131.     Paths paths[10] = { 0 };
  132.     int length = 0;
  133.     int p = 0;
  134.     DFS_All(G, startnum, endnum, visited, Path, k, n, length, paths, p);
  135.     for (int i = 0; i < p; i++) {
  136.         for (int j = 0; j < i; j++) {
  137.             if (paths[i].distance < paths[j].distance) {
  138.                 Paths temp = paths[i];
  139.                 paths[i] = paths[j];
  140.                 paths[j] = temp;
  141.             }
  142.         }
  143.     }
  144.     for (int i = 0; i < p; i++) {
  145.         cout << OrigialVex(G, startnum) << " ";
  146.         for (int j = 1;  paths[i].path[j] != 0; j++) {
  147.             cout  << OrigialVex(G, paths[i].path[j]) << " ";
  148.         }
  149.         cout << endl;
  150.     }
  151. }

第19关：植物分类树构建

  1. #include<bits/stdc++.h>
  2. #include<stack>
  3. #define OK 1
  4. #define ERROR 0
  5. #define MAXSIZE 6490
  6. using namespace std;
  7. typedef struct TNode{
  8. 	string data;
  9. 	struct TNode *left;
  10. 	struct TNode *right;
  11. }TNode,*BiTree;
  12. struct  Cata {			//定义分类
  13. 	string father;		//右边的分类
  14. 	string child;		//左边的分类
  15. };
  16. typedef struct Stack{
  17.     string *elem;
  18. 	int base; // 栈底指针
  19. 	int top; // 栈顶指针
  20. 	int stacksize; // 栈的最大容量
  21. }Stack;
  22.  
  23. int InitStack(Stack& S)
  24. {//栈初始化
  25. 	S.elem=new string[MAXSIZE];
  26.     if(!S.elem) exit(ERROR);
  27.     S.top=S.base=0; // 不要忘记初始化为0
  28.     S.stacksize=MAXSIZE;
  29. 	return OK;
  30. }
  31.  
  32. int Push(Stack& S, string s)
  33. {//入栈
  34. 	if(S.top-S.base == S.stacksize) return ERROR;
  35.     S.elem[++S.top]=s;
  36. 	return OK;
  37. }
  38.  
  39. int Pop(Stack& S)
  40. {//出栈
  41. 	if(S.top == S.base) return ERROR;
  42.     --S.top;
  43. 	return OK;
  44. }
  45.  
  46. int StackEmpty(Stack& S){
  47.     if(S.top == S.base) return 0;
  48.     else return 1;
  49. }
  50.  
  51. string GetTop(Stack S)
  52. {//取栈顶元素
  53. 	if(S.top != S.base) return S.elem[S.top];
  54. }
  55.  
  56. void InitTree(BiTree &BT)
  57. {//初始化二叉树，根结点数据为"植物界"
  58. 	BT=new TNode;
  59. 	BT->left=NULL;
  60. 	BT->right=NULL;
  61. 	BT->data="植物界";
  62. }
  63.  
  64. BiTree FindNodeByName(BiTree BT,string name)
  65. {//根据植物名递归找到对应TNode结点，若不存在则返回NULL
  66. 	if (BT == NULL) {
  67.         return NULL;
  68.     }
  69.  
  70.     // 访问根节点
  71.     if(BT->data == name){
  72.     	return BT;
  73. 	}
  74.  
  75.     // 递归遍历左儿子
  76.     BiTree lresult = FindNodeByName(BT->left,name);
  77.  
  78.     // 递归遍历右兄弟
  79.     BiTree rresult = FindNodeByName(BT->right,name);
  80.     
  81.     return lresult != NULL ? lresult : rresult;
  82. }
  83.  
  84. BiTree Findfather(BiTree BT,string name, Stack& s,string &father)
  85. {//根据植物名递归找到对应TNode结点，若不存在则返回NULL
  86. 	if (BT == NULL) {
  87.         return NULL;
  88.     }
  89.     // 访问根节点
  90.     if(BT->data == name){
  91.         father = GetTop(s);
  92.     	return BT;
  93. 	}
  94.     // 递归遍历左儿子
  95.  
  96.     Push(s,BT->data);
  97.     BiTree lresult = Findfather(BT->left,name, s, father);
  98.     Pop(s);
  99.     // 递归遍历右兄弟
  100.     BiTree rresult = Findfather(BT->right,name, s, father);
  101.      return lresult != NULL ? lresult : rresult;
  102. }
  103.  
  104. void InsertTNode(BiTree& BT, Cata temp){
  105.     	TNode* new_node = new TNode;		//当前节点
  106. 		TNode* new_node_child = new TNode;	//子节点
  107.         new_node = FindNodeByName(BT, temp.father);
  108. 		new_node_child->data = temp.child;
  109.         new_node_child->left = NULL;
  110.         new_node_child->right = NULL;
  111. 		if (new_node->left == NULL) {		//如果没有孩子，则直接插入左子节点
  112. 			new_node->left = new_node_child;
  113. 		}
  114. 		else {				//如果有孩子
  115.         	new_node = new_node->left;				//当前节点变为左孩子
  116. 		    while (new_node->right != NULL) {		//当他有兄弟时
  117. 			 	new_node = new_node->right;	//一直往下直到没有兄弟为止
  118. 			  }
  119. 			new_node->right = new_node_child;		//将数据插入右孩子
  120. 		}
  121. }
  122. void CreateByFile(BiTree& BT, string filename)
  123. {//根据文件名向树BT中添加结点
  124. 	ifstream infile;
  125. 	infile.open(filename.c_str());
  126. 	string line;
  127. 	while (getline(infile, line)) {
  128. 		Cata temp;
  129. 		stringstream data(line);
  130. 		string s;
  131. 		int flag = 0;
  132. 		while (getline(data, s, '#')) {
  133. 			if (flag == 0) temp.child = s;
  134. 			if (flag == 1) temp.father = s;
  135. 			flag++;
  136. 		}
  137.         InsertTNode(BT,temp);
  138. 	}
  139. 	infile.close();
  140. 	return;
  141. }
  142.  
  143.  
  144. void FindClass(BiTree& BT, string name)
  145. {//根据植物名，输出其从界到属的类别信息，需要自行定义递归函数（若还需用到栈，请自行定义）
  146. 	Stack s;
  147.     InitStack(s);
  148.     string father1, father2, father3, father4, father5, father6;
  149.     Findfather(BT, name, s, father1);
  150.     InitStack(s);
  151.     Findfather(BT, father1, s, father2);
  152.     InitStack(s);
  153.     Findfather(BT, father2, s, father3);
  154.     InitStack(s);
  155.     Findfather(BT, father3, s, father4);
  156.     InitStack(s);
  157.     Findfather(BT, father4, s, father5);
  158.     InitStack(s);
  159.     Findfather(BT, father5, s, father6);
  160.     cout<<father1<<" "<<father2<<" "<<father3<<" "<<father4<<" "<<father5<<" "<<father6<<endl;
  161. 	return;
  162. }
  163.

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

  1. #include<bits/stdc++.h>
  2. #include<stack>
  3. #define OK 1
  4. #define ERROR 0
  5. #define MAXSIZE 6490
  6. using namespace std;
  7. typedef struct TNode{
  8. 	string data;
  9. 	struct TNode *left;
  10. 	struct TNode *right;
  11. }TNode,*BiTree;
  12. struct  Cata {			//定义分类
  13. 	string father;		//右边的分类
  14. 	string child;		//左边的分类
  15. };
  16. typedef struct Stack{
  17.     string *elem;
  18. 	int base; // 栈底指针
  19. 	int top; // 栈顶指针
  20. 	int stacksize; // 栈的最大容量
  21. }Stack;
  22.  
  23. int InitStack(Stack& S)
  24. {//栈初始化
  25. 	S.elem=new string[MAXSIZE];
  26.     if(!S.elem) exit(ERROR);
  27.     S.top=S.base=0; // 不要忘记初始化为0
  28.     S.stacksize=MAXSIZE;
  29. 	return OK;
  30. }
  31.  
  32. int Push(Stack& S, string s)
  33. {//入栈
  34. 	if(S.top-S.base == S.stacksize) return ERROR;
  35.     S.elem[++S.top]=s;
  36. 	return OK;
  37. }
  38.  
  39. int Pop(Stack& S)
  40. {//出栈
  41. 	if(S.top == S.base) return ERROR;
  42.     --S.top;
  43. 	return OK;
  44. }
  45.  
  46. int StackEmpty(Stack& S){
  47.     if(S.top == S.base) return 0;
  48.     else return 1;
  49. }
  50.  
  51. string GetTop(Stack S)
  52. {//取栈顶元素
  53. 	if(S.top != S.base) return S.elem[S.top];
  54. }
  55.  
  56. void InitTree(BiTree &BT)
  57. {//初始化二叉树，根结点数据为"植物界"
  58. 	BT=new TNode;
  59. 	BT->left=NULL;
  60. 	BT->right=NULL;
  61. 	BT->data="植物界";
  62. }
  63.  
  64. BiTree FindNodeByName(BiTree BT,string name)
  65. {//根据植物名递归找到对应TNode结点，若不存在则返回NULL
  66. 	if (BT == NULL) {
  67.         return NULL;
  68.     }
  69.  
  70.     // 访问根节点
  71.     if(BT->data == name){
  72.     	return BT;
  73. 	}
  74.  
  75.     // 递归遍历左儿子
  76.     BiTree lresult = FindNodeByName(BT->left,name);
  77.  
  78.     // 递归遍历右兄弟
  79.     BiTree rresult = FindNodeByName(BT->right,name);
  80.     
  81.     return lresult != NULL ? lresult : rresult;
  82. }
  83.  
  84. BiTree Findfather(BiTree BT,string name, Stack& s,string &father)
  85. {//根据植物名递归找到对应TNode结点，若不存在则返回NULL
  86. 	if (BT == NULL) {
  87.         return NULL;
  88.     }
  89.     // 访问根节点
  90.     if(BT->data == name){
  91.         father = GetTop(s);
  92.     	return BT;
  93. 	}
  94.     // 递归遍历左儿子
  95.     Push(s,BT->data);
  96.     BiTree left = Findfather(BT->left,name,s,father);
  97.     Pop(s);
  98.      BiTree right = Findfather(BT->right,name,s,father);
  99.      return left != NULL? left:right;
  100. }
  101. void InsertTNode(BiTree& BT, Cata temp){
  102.     	TNode* new_node = new TNode;		//当前节点
  103. 		TNode* new_node_child = new TNode;	//子节点
  104.         new_node = FindNodeByName(BT, temp.father);
  105. 		new_node_child->data = temp.child;
  106.         new_node_child->left = NULL;
  107.         new_node_child->right = NULL;
  108. 		if (new_node->left == NULL) {		//如果没有孩子，则直接插入左子节点
  109. 			new_node->left = new_node_child;
  110. 		}
  111. 		else {				//如果有孩子
  112.         	new_node = new_node->left;				//当前节点变为左孩子
  113. 		    while (new_node->right != NULL) {		//当他有兄弟时
  114. 			 	new_node = new_node->right;	//一直往下直到没有兄弟为止
  115. 			  }
  116. 			new_node->right = new_node_child;		//将数据插入右孩子
  117. 		}
  118. }
  119. void CreateByFile(BiTree& BT, string filename)
  120. {//根据文件名向树BT中添加结点
  121. 	ifstream infile;
  122. 	infile.open(filename.c_str());
  123. 	string line;
  124. 	while (getline(infile, line)) {
  125. 		Cata temp;
  126. 		stringstream data(line);
  127. 		string s;
  128. 		int flag = 0;
  129. 		while (getline(data, s, '#')) {
  130. 			if (flag == 0) temp.child = s;
  131. 			if (flag == 1) temp.father = s;
  132. 			flag++;
  133. 		}
  134.         InsertTNode(BT,temp);
  135. 	}
  136. 	infile.close();
  137. 	return;
  138. }
  139.  
  140. void FindBrother(BiTree &BT,string name)
  141. {//根据植物名，输出其兄弟信息，空格分隔
  142.     Stack s;
  143.     InitStack(s);
  144.     string father;
  145.     Findfather(BT, name, s, father);
  146.     TNode* p = FindNodeByName(BT, father);
  147.     p = p->left;
  148.     while(p->right){
  149.         if(p->data != name){
  150.         cout<<p->data<<" ";
  151.         }
  152.         p = p->right;
  153.     }
  154.     cout<<p->data;
  155.     cout<<endl;
  156. }

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

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef struct TNode{
  4. 	string data;
  5. 	struct TNode *left;
  6. 	struct TNode *right;
  7. }TNode,*BiTree;
  8. struct  Cata {			//定义分类
  9. 	string father;		//右边的分类
  10. 	string child;		//左边的分类
  11. };
  12. void InitTree(BiTree &BT)
  13. {//初始化二叉树，根结点数据为"植物界"
  14. 	BT=new TNode;
  15. 	BT->left=NULL;
  16. 	BT->right=NULL;
  17. 	BT->data="植物界";
  18. }
  19.  
  20. BiTree FindNodeByName(BiTree BT,string name)
  21. {//根据植物名递归找到对应TNode结点，若不存在则返回NULL
  22. 	if (BT == NULL) {
  23.         return NULL;
  24.     }
  25.  
  26.     // 访问根节点
  27.     if(BT->data == name){
  28.     	return BT;
  29. 	}
  30.  
  31.     // 递归遍历左儿子
  32.     BiTree lresult = FindNodeByName(BT->left,name);
  33.  
  34.     // 递归遍历右兄弟
  35.     BiTree rresult = FindNodeByName(BT->right,name);
  36.     
  37.     return lresult != NULL ? lresult : rresult;
  38. }
  39.  
  40. void InsertTNode(BiTree& BT, Cata temp){
  41.     	TNode* new_node = new TNode;		//当前节点
  42. 		TNode* new_node_child = new TNode;	//子节点
  43.         new_node = FindNodeByName(BT, temp.father);
  44. 		new_node_child->data = temp.child;
  45.         new_node_child->left = NULL;
  46.         new_node_child->right = NULL;
  47. 		if (new_node->left == NULL) {		//如果没有孩子，则直接插入左子节点
  48. 			new_node->left = new_node_child;
  49. 		}
  50. 		else {				//如果有孩子
  51.         	new_node = new_node->left;				//当前节点变为左孩子
  52. 		    while (new_node->right != NULL) {		//当他有兄弟时
  53. 			 	new_node = new_node->right;	//一直往下直到没有兄弟为止
  54. 			  }
  55. 			new_node->right = new_node_child;		//将数据插入右孩子
  56. 		}
  57. }
  58. void CreateByFile(BiTree& BT, string filename)
  59. {//根据文件名向树BT中添加结点
  60. 	ifstream infile;
  61. 	infile.open(filename.c_str());
  62. 	string line;
  63. 	while (getline(infile, line)) {
  64. 		Cata temp;
  65. 		stringstream data(line);
  66. 		string s;
  67. 		int flag = 0;
  68. 		while (getline(data, s, '#')) {
  69. 			if (flag == 0) temp.child = s;
  70. 			if (flag == 1) temp.father = s;
  71. 			flag++;
  72. 		}
  73.         InsertTNode(BT,temp);
  74. 	}
  75. 	infile.close();
  76. 	return;
  77. }
  78. string plant[6490] = {" "};
  79. int k = 0;
  80. BiTree FindSon(BiTree &BT){
  81.     if(!BT) return NULL;
  82.     if (BT == NULL) {
  83.         return NULL;
  84.     }
  85.     // 访问根节点
  86.     if(BT->left == NULL){
  87.         while(BT){
  88.         plant[k] = BT->data;
  89.         k++;
  90.         BT = BT->right;
  91.         }
  92.     	return BT;
  93. 	}
  94.     // 递归遍历左儿子
  95.     BiTree lresult = FindSon(BT->left);
  96.     // 递归遍历右兄弟
  97.     BiTree rresult = FindSon(BT->right);
  98.     return lresult != NULL ? lresult : rresult;
  99. }
  100.  
  101. void FindSubLeaf(BiTree &BT,string name)
  102. {//根据分类词（门、纲、目、科、属中的一个），输出隶属于该分类词的植物，空格分隔
  103.     TNode *p = FindNodeByName(BT,name);
  104.     p = p->left;
  105.     FindSon(p);
  106.     int i = 0;
  107.     while(i<k-1){
  108.         cout<<plant[i]<<" ";
  109.         i++;
  110.     }
  111.     cout<<plant[i]<<endl;
  112.     k = 0;
  113. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/760448
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号