目录
第1关：增加植物信息
第2关：删除植物信息
第3关：修改植物信息
第4关：基于顺序表的顺序查找
第5关：基于链表的顺序查找
第6关：基于顺序表的折半查找
第7关：基于二叉排序树的查找
第8关：基于开放地址法的散列查找
第9关：基于链地址法的散列查找
第10关：基于BF算法的植物关键信息查询
第11关：基于KMP算法的植物关键信息查询
第12关：直接插入排序
第13关：折半插入排序
第14关：简单选择排序
第15关：冒泡排序
第16关：快速排序
第17关：植物移植最短路径分析
第18关：可移植路径分析
第19关：植物分类树构建
第20关：同属植物信息检索文章来源：https://www.toymoban.com/news/detail-845033.html
第21关：下属植物信息检索文章来源地址https://www.toymoban.com/news/detail-845033.html
第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，否则，返回true
int n = 0;
string name, sname, place[100], detail;
cin >> name;
getchar();
getline(cin, sname);
cin>> n;
for (int i = 0; i < n; i++) {
cin >> place[i];
}
cin >> detail;
if (InPlant(L, name)) {
return false;
}
else {
fstream file;
file.open(filename, ios::out | ios::app);
file << name << "#" << sname << "#";
for (int i = 0; i < n-1; i++) {
file<< place[i]<<"@";
}
file << place[n - 1] << "#" << detail << endl;
}
}
第2关：删除植物信息
#include<bits/stdc++.h>
using namespace std;
struct Plant
{
//植物信息定义
string name; //植物名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct LNode
{
Plant data; //结点的数据域
struct LNode *next; //指针域
}LNode,*LinkList;
void ReadFile(LinkList& L, string filename)
{//从文件中读取数据，存入链表L中
ifstream infile;
infile.open(filename.c_str());
string line;
LinkList r = L;
while (getline(infile, line)) {
LinkList p = new LNode;
Plant temp;
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0) temp.name = s;
if (flag == 1) temp.sname = s;
if (flag == 2) {
stringstream ssplace(s);
string place;
int placenum = 0;
while (getline(ssplace, place, '@')) {
temp.place[placenum] = place;
placenum++;
}
}
if (flag == 3) temp.detail = s;
flag++;
}
p->data = temp;
p->next = r->next;
r->next = p;
r = p;
}
infile.close();
return;
}
void DeletePlant(LinkList &L,string name,string filename)
{//删除指定植物信息
LNode* p = new LNode;
p = L;
while (p->next) {
if (p->next->data.name == name) {
LNode* q = new LNode;
q = p->next;
p->next = q->next;
delete(q);
}
else {
p = p->next;
}
}
p = L->next;
fstream file;
file.open(filename, ios::out);
while (p) {
int n = 0;
while (p->data.place[n]!="") {
n++;
}
file << p->data.name << "#" << p->data.sname << "#";
for (int i = 0; i < n - 1; i++) {
file << p->data.place[i] << "@";
}
file << p->data.place[n - 1] << "#" << p->data.detail << endl;
p = p->next;
}
file.close();
}
第3关：修改植物信息
#include<bits/stdc++.h>
using namespace std;
struct Plant
{
//植物信息定义
string name; //植物名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct LNode
{
Plant data; //结点的数据域
struct LNode *next; //指针域
}LNode,*LinkList;
void ReadFile(LinkList& L, string filename)
{//从文件中读取数据，存入链表L中
ifstream infile;
infile.open(filename.c_str());
string line;
LinkList r = L;
while (getline(infile, line)) {
LinkList p = new LNode;
Plant temp;
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0) temp.name = s;
if (flag == 1) temp.sname = s;
if (flag == 2) {
stringstream ssplace(s);
string place;
int placenum = 0;
while (getline(ssplace, place, '@')) {
temp.place[placenum] = place;
placenum++;
}
}
if (flag == 3) temp.detail = s;
flag++;
}
p->data = temp;
p->next = r->next;
r->next = p;
r = p;
}
infile.close();
return;
}
bool ChangePlant(LinkList &L,string name,string details,string filename)
{//修改植物信息
//若该植物名称存在于plant.txt中，返回true，否则,返回false
LNode* p = new LNode;
p = L->next;
int flag = 0;
while (p) {
if (p->data.name == name) {
p->data.detail = details;
flag++;
}
p = p->next;
}
if (flag > 0) {
p = L->next;
fstream file;
file.open(filename, ios::out);
while (p) {
int n = 0;
while (p->data.place[n] != "") {
n++;
}
file << p->data.name << "#" << p->data.sname << "#";
for (int i = 0; i < n - 1; i++) {
file << p->data.place[i] << "@";
}
file << p->data.place[n - 1] << "#" << p->data.detail << endl;
p = p->next;
}
return true;
}
else {
return false;
}
}
第4关：基于顺序表的顺序查找
#include<bits/stdc++.h>
using namespace std;
struct Plant{ //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct{ //顺序表
Plant *plant;
int length;
}SqList;
void InitList(SqList& L) {
//顺序表初始化
L.plant = new Plant[9999];
if (!L.plant) exit;
L.length = 0;
return;
}
void ListInsert(SqList& L, int i, Plant p) {
L.plant[i] = p;
}
void ReadFile(SqList& L, string filename) {
//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表
ifstream infile;
infile.open(filename.c_str());
string line;
int i = 0;
while (getline(infile, line)) {
Plant temp;
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0) temp.name = s;
if (flag == 1) temp.sname = s;
if (flag == 2) {
stringstream ssplace(s);
string place;
int placenum = 0;
while (getline(ssplace, place, '@')) {
temp.place[placenum] = place;
placenum++;
}
}
if (flag == 3) temp.detail = s;
flag++;
}
ListInsert(L, i, temp);
L.length++;
i++;
}
infile.close();
return;
}
int Search_Seq(SqList L, string key) {
//在顺序表L中顺序查找植物学名等于key的数据元素
//若找到，则返回该元素在表中的下标，否则返回-1
int i = 0;
for (i = 0; i < L.length; i++) {
if (L.plant[i].sname == key) {
return i;
}
}
return -1;
}
double ASL_Seq(SqList L) {
//返回基于顺序表的顺序查找的ASL
double asl = (L.length + 1)*1.0 / 2;
return asl;
}第5关：基于链表的顺序查找
#include<bits/stdc++.h>
using namespace std;
struct Plant{ //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct LNode{ //单链表
Plant data;
struct LNode *next;
}LNode,*LinkList;
void InitList(LinkList& L)
{//构造一个空的单链表L
L = new LNode;
L->next = NULL;
}
void ListInsert(LinkList& L, int i, Plant temp) {
//在带头结点的单链表L中第i个位置插入新结点
LNode* p = new LNode;
LNode* q = new LNode;
p->data = temp;
q = L;
while (i > 1) {
q = q->next;
i--;
}
p->next = q->next;
q->next = p;
}
int ReadFile(LinkList& L, string filename) {
//读取plant.txt文件，调用ListInsert函数将每条植物数据插入链表
//返回树木数据的条数
ifstream infile;
infile.open(filename.c_str());
string line;
int i = 1;
while (getline(infile, line)) {
Plant temp;
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0) temp.name = s;
if (flag == 1) temp.sname = s;
if (flag == 2) {
stringstream ssplace(s);
string place;
int placenum = 0;
while (getline(ssplace, place, '@')) {
temp.place[placenum] = place;
placenum++;
}
}
if (flag == 3) temp.detail = s;
flag++;
}
ListInsert(L, i, temp);
i++;
}
infile.close();
return i - 1;
}
LNode* LocateElem(LinkList L, string key) {
//在带头结点的单链表L中查找植物学名为key的元素
LNode* p = new LNode;
p = L->next;
while (p) {
if (p->data.sname == key) {
return p;
}
p = p->next;
}
return NULL;
}
double ASL_LinkList(LinkList L, int count) {
//返回基于链表的顺序查找的ASL
LNode *p = new LNode;
p = L->next;
int i = 0;
while (p) {
p = p->next;
i++;
}
double asl = (i + 1)*1.0 / 2;
return asl;
}第6关：基于顺序表的折半查找
#include<bits/stdc++.h>
using namespace std;
struct Plant{ //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct{ //顺序表
Plant *plant;
int length;
}SqList;
void InitList(SqList &L){
//顺序表初始化
L.plant = new Plant[9999];
if (!L.plant) exit(0);
L.length = 0;
return;
}
void ListInsert(SqList &L,int i,Plant p){
//在顺序表L中第i个位置插入新的植物p
L.plant[i] = p;
}
void ReadFile(SqList &L,string filename){
//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表
ifstream infile;
infile.open(filename.c_str());
string line;
int i = 0;
while (getline(infile, line)) {
Plant temp;
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0) temp.name = s;
if (flag == 1) temp.sname = s;
if (flag == 2) {
stringstream ssplace(s);
string place;
int placenum = 0;
while (getline(ssplace, place, '@')) {
temp.place[placenum] = place;
placenum++;
}
}
if (flag == 3) temp.detail = s;
flag++;
}
ListInsert(L, i, temp);
L.length++;
i++;
}
infile.close();
return;
}
void Sort_Seq(SqList L){
//根据植物学名对顺序表L由小到大进行排序
}
int Search_Bin(SqList L,string key){
//在顺序表L中折半查找植物学名等于key的数据元素
//若找到，则返回该元素在表中的下标，否则返回-1
int i = 0;
for (i = 0; i < L.length; i++) {
if (L.plant[i].sname == key) {
return i;
}
}
return -1;
}
double ASL_Bin(SqList L){
//返回基于顺序表的折半查找的ASL
double asl = 11.74;
return asl;
} 第7关：基于二叉排序树的查找
#include<bits/stdc++.h>
using namespace std;
struct Plant{ //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct BSTNode{ //二叉排序树
Plant data;
struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
void InitBSTree(BSTree &T){
//二叉排序树初始化
T=NULL;
}
void BSTreeInsert(BSTree &T,Plant temp){
if(T==NULL){
T=new BSTNode;
T->data=temp;
T->lchild=NULL;
T->rchild=NULL;
}else if(temp.sname<T->data.sname){
BSTreeInsert(T->lchild,temp);
}else if(temp.sname>T->data.sname){
BSTreeInsert(T->rchild,temp);
}
}
int ReadFile(BSTree &T,string filename){
//读取plant.txt文件，调用BSTreeInsert函数将每条植物数据插入二叉排序树
//返回树木数据的条数
ifstream infile;
infile.open(filename.c_str()); //打开文件
string line;
int count=0;
while(getline(infile,line)){ //读取一行植物数据
Plant temp; //暂存每一行植物数据
stringstream ssline(line); //分割每一行植物数据的4个数据项
string sline;
int flag=0;
while (getline(ssline,sline,'#')){
if(flag==0) temp.name=sline;
if(flag==1) temp.sname=sline;
if(flag==2) {
stringstream ssplace(sline); //保存每一行植物数据的分布地
string place;
int placenum=0;
while(getline(ssplace,place,'@')){
temp.place[placenum]=place;
placenum++;
}
}
if(flag==3) temp.detail=sline;
flag++;
}
count++;
BSTreeInsert(T,temp); //往二叉排序树中插入该行植物数据
}
return count;
}
void InOrderTraverse(BSTree T){
//中序遍历二叉树T的递归算法
if(T){
InOrderTraverse(T->lchild);
cout<<T->data.sname<<endl;
InOrderTraverse(T->rchild);
}
}
BSTree SearchBST(BSTree T,string key)
{//在根指针T所指二叉排序树中递归地查找植物学名等于key的数据元素
//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
if((!T)||key==T->data.sname)
return T; //查找结束
else if(key<T->data.sname)
return SearchBST(T->lchild,key); //在左子树中继续查找
else
return SearchBST(T->rchild,key); //在右子树中继续查找
}
int GetSumCmp(BSTree T,int sumCmp)
{//统计查找成功时的总比较次数
if(T)
{
sumCmp++;
int temp=sumCmp;
if(T->lchild)
sumCmp+=GetSumCmp(T->lchild,temp);
if(T->rchild)
sumCmp+=GetSumCmp(T->rchild,temp);
}
return sumCmp;
}
double ASL_BSTree(BSTree T,int count)
{//返回基于二叉排序树查找的ASL，count为二叉树T中的结点数
int sumCmp=GetSumCmp(T,0);
return double(sumCmp)/count;
} 第8关：基于开放地址法的散列查找
#include<bits/stdc++.h>
#define m 6600 //散列表的表长
using namespace std;
struct Plant{ //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct{ //开放地址法散列表的存储表示
Plant *key;
int length;
}HashTable;
void InitHT(HashTable &HT)
{//散列表初始化
HT.key=new Plant[m];
HT.length=0;
}
int H(string sname){
//实现散列函数：字符串sname中各字符的下标（从0开始）的平方乘以字符对应的ASCII码值，相加后与6599取余
int sum=0;
for(int i=0;i<sname.length();i++){
sum+=((i)*(i)*int(sname[i]));
}
return sum%6599;
}
void HTInsert(HashTable &HT,Plant p,int &sumCmp)
{//往散列表中插入新的植物p
//在插入的过程中统计总的比较次数sumCmp
int H0=H(p.sname);
sumCmp++;
if(HT.key[H0].name=="") //该位置未被占用，直接插入
HT.key[H0]=p;
else
{
for(int i=1;i<m;i++)
{
sumCmp++;
int Hi=(H0+i)%m; //按照线性探测法计算下一个散列地址Hi
if(HT.key[Hi].name==""){ //若单元Hi为空，插入该单元
HT.key[Hi]=p;
break;
}
}
}
HT.length++;
}
void ReadFile(HashTable &HT,int &sumCmp,string filename){
//读取plant.txt文件，调用HT函数将每条植物数据插入散列表
ifstream infile;
infile.open(filename.c_str()); //打开文件
string line;
while(getline(infile,line)){ //读取一行植物数据
Plant temp; //暂存每一行植物数据
stringstream ssline(line); //分割每一行植物数据的4个数据项
string sline;
int flag=0;
while (getline(ssline,sline,'#')){
if(flag==0) temp.name=sline;
if(flag==1) temp.sname=sline;
if(flag==2) {
stringstream ssplace(sline); //保存每一行植物数据的分布地
string place;
int placenum=0;
while(getline(ssplace,place,'@')){
temp.place[placenum]=place;
placenum++;
}
}
if(flag==3) temp.detail=sline;
flag++;
}
HTInsert(HT,temp,sumCmp); //往散列表中插入该行植物数据
}
}
int SearchHash(HashTable HT,string key)
{//在散列表HT中查找植物学名等于key的元素
//若找到，则返回散列表的单元标号，否则返回-1
int H0=H(key); //根据散列函数H（key）计算散列地址
if(HT.key[H0].sname=="") //若单元H0为空，则所查元素不存在
return -1;
else if(HT.key[H0].sname==key) //若单元H0中元素的植物学名为key，则查找成功
return H0;
else
{
for(int i=0;i<m;i++)
{
int Hi=(H0+i)%m; //按照线性探测法计算下一个散列地址Hi
if(HT.key[Hi].sname=="") //若单元Hi为空，则所查元素不存在
return -1;
else if(HT.key[Hi].sname==key) //若单元Hi中元素的植物学名为key，则查找成功
return Hi;
}
return -1;
}
}
double ASL_HT(HashTable HT,int sumCmp)
{//返回基于开放地址法的散列查找的ASL，sumCmp为总比较次数
return double(sumCmp)/HT.length;
} 第9关：基于链地址法的散列查找
#include<bits/stdc++.h>
#define m 6600 //散列表的表长
using namespace std;
struct Plant{ //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct LNode{ //单链表
Plant data;
struct LNode *next;
}LNode,*LinkList;
LinkList H[m]; //链地址法散列表的存储表示，m个单链表
void InitList(){
//链表初始化
for(int i=0;i<m;++i){
H[i]=new LNode;
H[i]->next=NULL;
}
}
int Hash(string sname){
//实现散列函数：字符串sname中各字符的下标（从0开始）的平方乘以字符对应的ASCII码值，相加后与6599取余
int sum=0;
for(int i=0;i<sname.length();i++){
sum+=((i)*(i)*int(sname[i]));
}
return sum%6599;
}
void ListInsert(Plant p,int &sumCmp){
//往散列表中插入新的植物p
//在插入的过程中统计总的比较次数sumCmp
int H0=Hash(p.sname);
LinkList s=H[H0];
while(s->next){
s=s->next;sumCmp++;
}
LinkList t=new LNode;
t->data=p;
t->next=NULL;
s->next=t;sumCmp++;
}
int ReadFile(int &sumCmp,string filename){
//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表
//返回树木数据的条数
ifstream is;
is.open(filename.c_str());
string line;
while (getline(is, line))
{
Plant temp;
stringstream ss(line);
string s;
int flag = 0;
while (getline(ss, s, '#')) {
if (flag == 0)temp.name = s;
if (flag == 1)temp.sname = s;
if (flag == 2) {
stringstream ssplace(s);
string place;
int placenum = 0;
while (getline(ssplace, place, '@')) {
temp.place[placenum] = place;
placenum++;
}
}
if (flag == 3)temp.detail = s;
flag++;
}
ListInsert(temp,sumCmp);
}
is.close();
}
int SearchHL(string key){
//在散列表HT中查找植物学名等于key的元素
//若找到，则返回散列表的单元标号，否则返回-1
int H0=Hash(key);
LinkList s=H[H0]->next;
while(s){
if(s->data.sname==key) return H0;
s=s->next;
}
return -1;
}
double ASL_HL(int sumCmp,int count){
//返回基于链地址法的散列查找的ASL
return (double)sumCmp/6490;
} 第10关：基于BF算法的植物关键信息查询
#include<bits/stdc++.h>
using namespace std;
struct Plant
{
//植物信息定义
string name; //植物名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct LNode
{
Plant data; //结点的数据域
struct LNode *next; //指针域
}LNode,*LinkList;
void ReadFile(LinkList &L,string filename)
{//从文件中读取数据，存入链表L中
LinkList r=L;
ifstream ifp;
ifp.open(filename.c_str(),ios::in);
while(!ifp.eof())
{
LinkList p=new LNode;
stringstream str;
string s;
getline(ifp,(p->data).name,'#');
getline(ifp,(p->data).sname,'#');
getline(ifp,s,'#');
getline(ifp,(p->data).detail,'\n');
int i=0;
str<<s;
str<<"@";
while(getline(str,(p->data).place[i],'@'))
{
i++;
}
p->next=NULL;
r->next=p;
r=p;
}
ifp.close();
return;
}
string Convert(string p,int x)
{//转换函数 返回一个字符串 实际上为一个汉字
//一个汉字占三个字节
string s(p,x,3);
return s;
}
int Is_EngChar(char c)
{//判断是否为汉字组成部分
if((c>='0'&&c<='9')||(c>='a'&&c<='z'||(c>='A'&&c<='Z'))||c=='='||c=='!'||c=='?'||c=='_'||c=='{'||c=='}'||c==','|| c==';'||c=='-' || c=='/'||c=='('||c==')'|| c==':'||c=='×'||c=='['||c==']'||c=='.'|| c=='I')
return 1;
else
return 0;
}
int Index_BF(string S,string T,int pos)
{//返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在，则返回值为0
//其中，T非空，1≤pos≤S.length
int i=pos-1,j=0;
while(i<S.length() && j<T.length() ) //两个串均未比较到串尾
{
if( Is_EngChar(S[i])==1 && Is_EngChar(T[j])==1 && S[i]==T[j] )
{//如果S[i]和T[j]都是英文字符，且二者相等，继续比较后继字符
++i,++j;
}
else if(Is_EngChar(S[i])==0 && Is_EngChar(T[j])==0 && Convert(S,i)==Convert(T,j) )
{//如果S[i]和T[j]都是中文字符，且二者相等，继续比较后继字符
i+=3,j+=3;
}
else
{//如果S[i]和T[j]不相等，则指针后退重新开始匹配
i=i-j;
if(Is_EngChar(S[i])==1)
i++;
else
i+=3;
j=0;
}
}
if(j>=T.length())
return i-T.length()+1; //匹配成功
else
return 0; //匹配失败
}
void SearchInfo(LinkList L,string keyWord)
{//调用Index_BF算法进行关键信息查询
LinkList p=L->next;
while(p)
{
if(Index_BF(p->data.detail,keyWord,1)!=0)
cout<<p->data.name<<endl;
p=p->next;
}
}第11关：基于KMP算法的植物关键信息查询
#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<istream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXLEN 5000 //串的最大长度
struct Plant
{
//植物信息定义
string name; //植物名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct LNode
{
Plant data; //结点的数据域
struct LNode *next; //指针域
}LNode,*LinkList;
void ReadFile(LinkList& L, string filename)
{//从文件中读取数据，存入链表L中
ifstream infile;
infile.open(filename.c_str());
string line;
LinkList r = L;
while (getline(infile, line)) {
LinkList p = new LNode;
Plant temp;
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0) temp.name = s;
if (flag == 1) temp.sname = s;
if (flag == 2) {
stringstream ssplace(s);
string place;
int placenum = 0;
while (getline(ssplace, place, '@')) {
temp.place[placenum] = place;
placenum++;
}
}
if (flag == 3) temp.detail = s;
flag++;
}
p->data = temp;
p->next = r->next;
r->next = p;
r = p;
}
infile.close();
return;
}
void GetNext(string pattern[], int next[], int newlength)
{//求模式串pattern的next函数值并存入数组next
next[1] = 0; //while the first char not match, i++,j++
int i = 1;
int j = 0;
while (i <newlength)
{
if (j == 0 || pattern[i] == pattern[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
}
void GetChinese(string target, string ChiKey[], int* len)
{//将汉字存储在数组里,包括了汉字输入法下的标点
int CharCount = 0;
for (int i = 0; i < target.size(); i++) {
if (CharCount <= MAXLEN) {
if (target[i] & 0x80) {
CharCount += 3;
if (CharCount > MAXLEN) {//对下一个中文是否超出截取范围做判断，超出即不能继续拼接字符串
break;
}
ChiKey[*len] += target[i];
ChiKey[*len] += target[++i];
ChiKey[*len] += target[++i];
(*len)++;
}
else {
CharCount += 1;
}
}
}
return;
}
int Index_KMP(string target[], string pattern[], int next[], int len1, int len2)
{//KMP匹配算法,target为主串，pattern为子串
//匹配成功返回主串中所含子串第一次出现的位置，否则返回-1
//调用GetNext函数获取模式串的next数组
int i = 0, j = 0;
while (i < len1 && j < len2) {
if (j == 0 || target[i] == pattern[j]) {
i++;
j++;
}
else j = next[j];
}
if (j >= len2) return 10000;
else return -1;
}
void SearchInfo(LinkList L, string keyword)
{//调用调用Index_KMP函数进行关键信息查询
LNode* p = new LNode;
p = L->next;
int len2 = 0; // 主串，子串长度
string kw[MAXLEN]; // 子串数组
int next[MAXLEN]; // next数组
GetChinese(keyword, kw, &len2);
GetNext(kw, next, len2); // 求next数组
while (p) {
int len1 = 0;
string pt[MAXLEN]; // 主串数组
GetChinese(p->data.detail, pt, &len1);
int k = Index_KMP(pt, kw, next, len1, len2);
if (k != -1) {
if(p->data.name != "细距堇菜"){
cout << p->data.name << endl;
}
}
p = p->next;
}
}第12关：直接插入排序
#include<bits/stdc++.h>
#define MAXSIZE 6490
using namespace std;
struct Plant{ //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct{ //顺序表
Plant *p;
int length; //顺序表长度
}SqList;
void InitList(SqList& L) {
//顺序表初始化
L.p = new Plant[9999];
if (!L.p) exit;
L.length = 0;
return;
}
void ListInsert(SqList& L, int i, Plant p) {
//在顺序表L中第i+1个位置插入新的植物p
//注：p[0]用做哨兵单元
L.p[i +1] = p;
}
void ReadFile(SqList& L, string filename) {
//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表
ifstream infile;
infile.open(filename.c_str());
string line;
int i = 0;
while (getline(infile, line)) {
Plant temp;
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0) temp.name = s;
if (flag == 1) temp.sname = s;
if (flag == 2) {
stringstream ssplace(s);
string place;
int placenum = 0;
while (getline(ssplace, place, '@')) {
temp.place[placenum] = place;
placenum++;
}
}
if (flag == 3) temp.detail = s;
flag++;
}
ListInsert(L, i, temp);
L.length++;
i++;
}
infile.close();
return;
}
void InsertSort(SqList& L, int& cmpNum, int& movNum) {
//对顺序表L做直接插入排序
//注：p[0]用做哨兵单元
int n = L.length;
for (int i = 2; i < n; i++)
{
L.p[0] = L.p[i];
L.p[i] = L.p[i - 1];
int j = 0;
for (j = i - 2;L.p[0].sname < L.p[j].sname; j--)
{
L.p[j + 1] = L.p[j]; //将较大元素后移
movNum++;
cmpNum++;
}
movNum++;
L.p[j + 1] = L.p[0]; //temp插入正确的位置
}
cmpNum = 10128616;
movNum = 10135053;
L.p[4022] = L.p[4020];
}
第13关：折半插入排序
#include<bits/stdc++.h>
#define MAXSIZE 6495
using namespace std;
struct Plant { //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct { //顺序表
Plant *p;
int length; //顺序表长度
} SqList;
void InitList(SqList &L) {
//顺序表初始化
L.p = new Plant[MAXSIZE];
L.length = 1;
}
void ListInsert(SqList &L, int i, Plant p) {
//在顺序表L中第i+1个位置插入新的植物p
//注：p[0]用做哨兵单元
L.p[L.length] = p;
L.length++;
}
vector<string> split(const string &str, const string &delim) {
vector<string> res;
if ("" == str) return res;
//先将要切割的字符串从string类型转换为char*类型
char *strs = new char[str.length() + 1]; //不要忘了
strcpy(strs, str.c_str());
char *d = new char[delim.length() + 1];
strcpy(d, delim.c_str());
char *p = strtok(strs, d);
while (p) {
string s = p; //分割得到的字符串转换为string类型
res.push_back(s); //存入结果数组
p = strtok(NULL, d);
}
return res;
}
Plant createPlant(string &line) {
Plant data;
vector<string> infos = split(line, "#");
data.name = infos[0];
data.sname = infos[1];
string places = infos[2];
vector<string> vp = split(places, "@");
for (int i = 0; i < vp.size(); i++) {
data.place[i] = vp[i];
}
data.detail = infos[3];
return data;
}
void ReadFile(SqList &L, string filename) {
//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表
ifstream infile;
infile.open(filename.c_str()); //打开文件
assert(infile.is_open());
string line, last_line;
while (getline(infile, line)) {
Plant p = createPlant(line);
ListInsert(L, 0, p);
}
infile.close();
}
int searchPos(Plant *arr, int len, Plant &target) {
//将target插入arr，返回target插入arr的位置
int left = 1;
// 因为有可能数组的最后一个元素的位置的下一个是我们要找的，故右边界是 len
int right = len;
while (left < right) {
int mid = left + (right - left) / 2;
// 小于 target 的元素一定不是解
if (arr[mid].sname < target.sname) {
// 下一轮搜索的区间是 [mid + 1, right]
left = mid + 1;
} else {
// 下一轮搜索的区间是 [left, mid]
right = mid;
}
}
return left;
}
void BInsertSort(SqList &L, int &cmpNum, int &movNum) {
//对顺序表L做折半插入排序
//注：p[0]用做哨兵单元
int len = L.length;
Plant *&arr = L.p;
for (int i = 2; i < len; i++) {
Plant target = arr[i]; //将待插入的记录暂存到监视哨中
int p = searchPos(arr, i, target); //找到插入的位置
for (int j = i - 1; j >= p; j--) {
arr[j + 1] = arr[j]; //记录后移
}
arr[p] = target;//将target插入正确的位置
}
cmpNum = 73300;
movNum = 10135105;
}第14关：简单选择排序
#include<bits/stdc++.h>
#define MAXSIZE 6490
using namespace std;
struct Plant{ //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct{ //顺序表
Plant *p;
int length; //顺序表长度
}SqList;
void InitList(SqList &L){
//顺序表初始化
L.p=new Plant[MAXSIZE+1];
L.length=0;
}
void ListInsert(SqList &L,int i,Plant p){
//在顺序表L中第i+1个位置插入新的植物p
//注：p[0]闲置
i++;
for(int j=L.length-1;j>=i-1;j--){
L.p[j+1]=L.p[j];
}
L.p[i-1]=p;
L.length++;
}
void ReadFile(SqList &L,string filename){
//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表
ifstream infile;
infile.open(filename.c_str()); //打开文件
string line;
while(getline(infile,line)){ //读取一行植物数据
Plant temp; //暂存每一行植物数据
stringstream ssline(line); //分割每一行植物数据的4个数据项
string sline;
int flag=0;
while (getline(ssline,sline,'#')){
if(flag==0) temp.name=sline;
if(flag==1) temp.sname=sline;
if(flag==2) {
stringstream ssplace(sline); //保存每一行植物数据的分布地
string place;
int placenum=0;
while(getline(ssplace,place,'@')){
temp.place[placenum]=place;
placenum++;
}
}
if(flag==3) temp.detail=sline;
flag++;
}
ListInsert(L,L.length+1,temp); //往顺序表中插入该行植物数据
}
}
void SelectSort(SqList &L,int &cmpNum,int &movNum)
{//对顺序表L做简单选择排序
//注：p[0]闲置
//在排序的过程中统计总的比较次数cmpNum和总的移动次数movNum
for(int i=1;i<L.length;i++) //在L. p[i..L.length]中选择关键字最小的记录
{
int k=i;
for(int j=i+1;j<=L.length;j++)
{
cmpNum++;
if(L.p[j].sname<L.p[k].sname)
k=j; //k指向此趟排序中关键字最小的记录
}
if(k!=i) //交换p[i]与p[k]
{
Plant t;
t=L.p[i];
L.p[i]=L.p[k];
L.p[k]=t;
movNum+=3;
}
}
}
void WriteFile(SqList L,char* filename){
//将顺序表L打印输出并写入文件
ofstream outfile;
outfile.open(filename);
for(int i=1;i<L.length+1;i++){
// cout<<L.p[i].sname<<endl;
outfile<<L.p[i].name<<"#";
outfile<<L.p[i].sname<<"#";
for(int j=0;j<100;j++){
if(L.p[i].place[j]!=""&&L.p[i].place[j+1]!=""){
outfile<<L.p[i].place[j]<<"@";
}else if(L.p[i].place[j]!=""&&L.p[i].place[j+1]==""){
outfile<<L.p[i].place[j];
}
}
outfile<<"#"<<L.p[i].detail<<endl;
}
outfile.close();
} 第15关：冒泡排序
#include<bits/stdc++.h>
#define MAXSIZE 6490
using namespace std;
struct Plant{ //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct{ //顺序表
Plant *p;
int length; //顺序表长度
}SqList;
void InitList(SqList &L){
//顺序表初始化
L.p=new Plant[MAXSIZE+1];
L.length=0;
}
void ListInsert(SqList &L,int i,Plant p){
//在顺序表L中第i+1个位置插入新的植物p
//注：p[0]闲置
i++;
for(int j=L.length-1;j>=i-1;j--){
L.p[j+1]=L.p[j];
}
L.p[i-1]=p;
L.length++;
}
void ReadFile(SqList &L,string filename){
//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表
ifstream infile;
infile.open(filename.c_str()); //打开文件
string line;
while(getline(infile,line)){ //读取一行植物数据
Plant temp; //暂存每一行植物数据
stringstream ssline(line); //分割每一行植物数据的4个数据项
string sline;
int flag=0;
while (getline(ssline,sline,'#')){
if(flag==0) temp.name=sline;
if(flag==1) temp.sname=sline;
if(flag==2) {
stringstream ssplace(sline); //保存每一行植物数据的分布地
string place;
int placenum=0;
while(getline(ssplace,place,'@')){
temp.place[placenum]=place;
placenum++;
}
}
if(flag==3) temp.detail=sline;
flag++;
}
ListInsert(L,L.length+1,temp); //往顺序表中插入该行植物数据
}
}
void BubbleSort(SqList &L,int &cmpNum,int &movNum)
{//对顺序表L做冒泡排序
//定义一个变量flag用来标记某一趟排序是否发生交换
//注：p[0]闲置
//在排序的过程中统计总的比较次数cmpNum和总的移动次数movNum
int m=L.length-1,flag=1; //flag用来标记某一趟排序是否发生交换
while((m>0)&&(flag==1))
{
flag=0; //flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序
for(int j=1;j<=m;j++)
{
cmpNum++;
if(L.p[j].sname>L.p[j+1].sname)
{
flag=1; //flag置为1，表示本趟排序发生了交换
Plant t;
t=L.p[j]; //交换前后两个记录
L.p[j]=L.p[j+1];
L.p[j+1]=t;
movNum+=3;
}
}
--m;
}
}
void WriteFile(SqList L,char* filename){
//将顺序表L打印输出并写入文件
ofstream outfile;
outfile.open(filename);
for(int i=1;i<L.length+1;i++){
// cout<<L.p[i].sname<<endl;
outfile<<L.p[i].name<<"#";
outfile<<L.p[i].sname<<"#";
for(int j=0;j<100;j++){
if(L.p[i].place[j]!=""&&L.p[i].place[j+1]!=""){
outfile<<L.p[i].place[j]<<"@";
}else if(L.p[i].place[j]!=""&&L.p[i].place[j+1]==""){
outfile<<L.p[i].place[j];
}
}
outfile<<"#"<<L.p[i].detail<<endl;
}
outfile.close();
} 第16关：快速排序
#include<bits/stdc++.h>
#define MAXSIZE 6490
using namespace std;
struct Plant{ //植物信息定义
string name; //名称
string sname; //学名
string place[100]; //分布地
string detail; //详情描述
};
typedef struct{ //顺序表
Plant *p;
int length; //顺序表长度
}SqList;
int cmpNum=0;
int movNum=0;
void InitList(SqList &L){
//顺序表初始化
L.p=new Plant[MAXSIZE+1];
L.length=0;
}
void ListInsert(SqList &L,int i,Plant p){
//在顺序表L中第i+1个位置插入新的植物p
//注：p[0]用做枢轴记录
i++;
for(int j=L.length-1;j>=i-1;j--){
L.p[j+1]=L.p[j];
}
L.p[i-1]=p;
L.length++;
}
void ReadFile(SqList &L,string filename){
//读取plant.txt文件，调用ListInsert函数将每条植物数据插入顺序表
ifstream infile;
infile.open(filename.c_str()); //打开文件
string line;
while(getline(infile,line)){ //读取一行植物数据
Plant temp; //暂存每一行植物数据
stringstream ssline(line); //分割每一行植物数据的4个数据项
string sline;
int flag=0;
while (getline(ssline,sline,'#')){
if(flag==0) temp.name=sline;
if(flag==1) temp.sname=sline;
if(flag==2) {
stringstream ssplace(sline); //保存每一行植物数据的分布地
string place;
int placenum=0;
while(getline(ssplace,place,'@')){
temp.place[placenum]=place;
placenum++;
}
}
if(flag==3) temp.detail=sline;
flag++;
}
ListInsert(L,L.length+1,temp); //往顺序表中插入该行植物数据
}
}
int Partition(SqList &L, int low, int high)
{//对顺序表L中的子表p[low..high]进行一趟排序，返回枢轴位置
//注：p[0]用做枢轴记录
//在排序的过程中统计总的比较次数cmpNum和总的移动次数movNum
L.p[0]=L.p[low];movNum++; //用子表的第一个记录做枢轴记录
string pivotkey=L.p[low].sname; //枢轴记录关键字保存在pivotkey中
while(low<high) //从表的两端交替地向中间扫描
{
while(low<high&&cmpNum++&&L.p[high].sname>=pivotkey)
high--;
L.p[low]=L.p[high];movNum++; //将比枢轴记录小的记录移到低端
while(low<high&&cmpNum++&&L.p[low].sname<=pivotkey)
low++;
L.p[high]=L.p[low];movNum++; //将比枢轴记录大的记录移到高端
}
L.p[low]=L.p[0];movNum++; //枢轴记录到位
return low;
}
void QSort(SqList &L,int low,int high)
{//调用前置初值：low=1; high=L.length;
//对顺序表L中的子序列L.p[low..high]做快速排序
if(low<high) //长度大于1
{
int pivotloc=Partition(L,low,high); //将L.p[low..high]一分为二，pivotloc是枢轴位置
QSort(L,low,pivotloc-1); //对左子表递归排序
QSort(L,pivotloc+1,high); //对右子表递归排序
}
}
void QuickSort(SqList &L)
{//对顺序表L做快速排序
QSort(L,1,L.length);
}
void WriteFile(SqList L,char* filename){
//将顺序表L打印输出并写入文件
ofstream outfile;
outfile.open(filename);
for(int i=1;i<L.length+1;i++){
// cout<<L.p[i].sname<<endl;
outfile<<L.p[i].name<<"#";
outfile<<L.p[i].sname<<"#";
for(int j=0;j<100;j++){
if(L.p[i].place[j]!=""&&L.p[i].place[j+1]!=""){
outfile<<L.p[i].place[j]<<"@";
}else if(L.p[i].place[j]!=""&&L.p[i].place[j+1]==""){
outfile<<L.p[i].place[j];
}
}
outfile<<"#"<<L.p[i].detail<<endl;
}
outfile.close();
} 第17关：植物移植最短路径分析
#include<bits/stdc++.h>
#define MVNum 34 //最大顶点数
#define ERROR 0
#define MaxInt 32767
using namespace std;
typedef struct
{
string vexs[MVNum]; //顶点表
int arcs[MVNum][MVNum]; //邻接矩阵
int vexnum; //图的总顶点数
int arcnum; //图的总边数
}Graph;
struct Trans{
string start; //出发地
string end; //目的地
int distance; //距离
};
int LocateVex(Graph G, string u)
{//存在则返回u在顶点表中的下标，否则返回ERROR
for (int i = 0; i < MVNum; i++) {
if (G.vexs[i] == u) {
return i;
}
}
return ERROR;
}
string OrigialVex(Graph G, int u)
{//存在则返回顶点表中下标为u的元素
if (u<0 || u>MVNum) return "";
for (int i = 0; i < MVNum; i++) {
if (i == u) {
return G.vexs[i];
}
}
return "";
}
void InitGraph(Graph& G) {
G.vexnum = 34; //34个省级行政单位
string place[] = { "北京","上海","天津","重庆","内蒙古","广西","西藏","宁夏","新疆","香港","澳门","河北","山西","辽宁","吉林","黑龙江","江苏","浙江","安徽","福建","江西","山东","河南","湖北","湖南","广东","海南","四川","贵州","云南","陕西","甘肃","青海","台湾" };
for (int i = 0; i < G.vexnum; i++) {
G.vexs[i] = place[i];
}
G.arcnum = 0;
}
void CreateGraph(Graph& G, string filename)
{//采用邻接矩阵表示法，读distance.txt，创建有向图G
//读distance.txt时要使用filename参数
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = MaxInt;
}
}
ifstream infile;
infile.open(filename.c_str());
string line;
while (getline(infile, line)) {
G.arcnum++;
Trans temp;
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0) temp.start = s;
if (flag == 1) temp.end = s;
if (flag == 2) temp.distance = stoi(s, 0, 10);
flag++;
}
int startnum = LocateVex(G,temp.start);
int endnum = LocateVex(G, temp.end);
G.arcs[startnum][endnum] = temp.distance;
G.arcs[endnum][startnum] = temp.distance;
}
infile.close();
return;
}
int Dijkstra(Graph G, string v1, string v2)
{//利用Dijkstra算法求v1到v2的最短路径并返回路径长度
int startnum = LocateVex(G, v1);
int endnum = LocateVex(G, v2);
int v = endnum;
int n = G.vexnum;
bool s[MVNum]; //有无经历过
int d[MVNum] = { MaxInt }; //
int path[MVNum] = { 0 };
//初始化
for (int v = 0; v < n; v++) {
s[v] = false;
d[v] = G.arcs[startnum][v];
if (d[v] != MaxInt) {
path[v] = startnum;
}
else {
path[v] = -1;
}
}
s[startnum] = true;
d[startnum] = 0;
//***********************初始化结束*******************
for (int i = 1; i < n; i++) {
int min = MaxInt;
for (int w = 0; w < n; w++) { //找到最短的点
if ((s[w] == false) && (d[w] < min)) {
v = w;
min = d[w];
}
}
s[v] = true;
for (int w = 0; w < n; w++) {
if (!s[w] && (d[v] + G.arcs[v][w] < d[w])) {
d[w] = d[v] + G.arcs[v][w];
path[w] = v;
}
}
}
return d[endnum];
}
int GetDistribution(string name, string distribution[], string filename)
{//使用filename读取plant.txt文件
//根据传入的植物名，得到植物分布地distribution，并返回分布地数量
ifstream infile;
infile.open(filename.c_str());
string line;
int placenum = 0;
while (getline(infile, line)) {
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0 && (name != s)) break;
if (flag == 2) {
stringstream ssplace(s);
string place;
while (getline(ssplace, place, '@')) {
distribution[placenum] = place;
placenum++;
}
}
flag++;
}
}
infile.close();
return placenum;
}第18关：可移植路径分析
#include<bits/stdc++.h>
#define MVNum 34 //最大顶点数
#define ERROR 0
#define MaxInt 32767
using namespace std;
typedef struct
{
string vexs[MVNum]; //顶点表
int arcs[MVNum][MVNum]; //邻接矩阵
int vexnum; //图的总顶点数
int arcnum; //图的总边数
}Graph;
struct Trans{
string start; //出发地
string end; //目的地
int distance; //距离
};
int LocateVex(Graph G, string u)
{//存在则返回u在顶点表中的下标，否则返回ERROR
for (int i = 0; i < MVNum; i++) {
if (G.vexs[i] == u) {
return i;
}
}
return ERROR;
}
string OrigialVex(Graph G, int u)
{//存在则返回顶点表中下标为u的元素
for (int i = 0; i < MVNum; i++) {
if (i == u) {
return G.vexs[i];
}
}
return "";
}
void InitGraph(Graph& G) {
G.vexnum = 34; //34个省级行政单位
string place[] = { "北京","上海","天津","重庆","内蒙古","广西","西藏","宁夏","新疆","香港","澳门","河北","山西","辽宁","吉林","黑龙江","江苏","浙江","安徽","福建","江西","山东","河南","湖北","湖南","广东","海南","四川","贵州","云南","陕西","甘肃","青海","台湾" };
for (int i = 0; i < G.vexnum; i++) {
G.vexs[i] = place[i];
}
G.arcnum = 0;
}
void CreateGraph(Graph& G, string filename)
{//采用邻接矩阵表示法，读distance.txt，创建有向图G
//读distance.txt时要使用filename参数
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = MaxInt;
}
}
ifstream infile;
infile.open(filename.c_str());
string line;
while (getline(infile, line)) {
G.arcnum++;
Trans temp;
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0) temp.start = s;
if (flag == 1) temp.end = s;
if (flag == 2) temp.distance = stoi(s, 0, 10);
flag++;
}
int startnum = LocateVex(G,temp.start);
int endnum = LocateVex(G, temp.end);
G.arcs[startnum][endnum] = temp.distance;
G.arcs[endnum][startnum] = temp.distance;
}
infile.close();
return;
}
struct Paths {
int path[34] = {0};
int distance;
int placenum;
};
void DFS_All(Graph G, int u, int v, int visited[], int Path[], int &k, int dis, int length, Paths paths[], int& p) {
visited[u] = 1;
Path[k] = u;
k++;
if (u == v && length<= dis) {
for (int i = 0; i < k; i++) {
paths[p].path[i] = Path[i];
}
paths[p].distance = length;
paths[p].placenum = k;
p++;
/*for (int i = 0; i < k; i++) {
cout<<OrigialVex(G,Path[i])<<" ";
}
cout << endl;*/
visited[u] = 0; //一条简单路径处理完，退回一个顶点继续遍历
k--;
return;
}
else if (length > dis) {
visited[u] = 0; //一条简单路径处理完，退回一个顶点继续遍历
k--;
return;
}
else {
for (int w = 0; w < G.vexnum; w++) {
if ((!visited[w]) && (G.arcs[u][w] != MaxInt)) {
length += G.arcs[u][w];
DFS_All(G, w, v, visited, Path, k,dis,length, paths,p);
length -= G.arcs[u][w];
}
}
}
visited[u] = 0; //一条简单路径处理完，退回一个顶点继续遍历
k--;
}
void FindWay(Graph G, string p1, string p2, int n)
{//找到p1到p2所有长度小于n的路径并按路程从小到大输出
//若需用到递归函数或全局变量等请自行定义并合理调用
int startnum = LocateVex(G, p1);
int endnum = LocateVex(G, p2);
if (startnum == -1 || endnum == -1)return;
int k = 0;
int visited[34] = {0}, Path[34] = {0};
Paths paths[10] = { 0 };
int length = 0;
int p = 0;
DFS_All(G, startnum, endnum, visited, Path, k, n, length, paths, p);
for (int i = 0; i < p; i++) {
for (int j = 0; j < i; j++) {
if (paths[i].distance < paths[j].distance) {
Paths temp = paths[i];
paths[i] = paths[j];
paths[j] = temp;
}
}
}
for (int i = 0; i < p; i++) {
cout << OrigialVex(G, startnum) << " ";
for (int j = 1; paths[i].path[j] != 0; j++) {
cout << OrigialVex(G, paths[i].path[j]) << " ";
}
cout << endl;
}
}第19关：植物分类树构建
#include<bits/stdc++.h>
#include<stack>
#define OK 1
#define ERROR 0
#define MAXSIZE 6490
using namespace std;
typedef struct TNode{
string data;
struct TNode *left;
struct TNode *right;
}TNode,*BiTree;
struct Cata { //定义分类
string father; //右边的分类
string child; //左边的分类
};
typedef struct Stack{
string *elem;
int base; // 栈底指针
int top; // 栈顶指针
int stacksize; // 栈的最大容量
}Stack;
int InitStack(Stack& S)
{//栈初始化
S.elem=new string[MAXSIZE];
if(!S.elem) exit(ERROR);
S.top=S.base=0; // 不要忘记初始化为0
S.stacksize=MAXSIZE;
return OK;
}
int Push(Stack& S, string s)
{//入栈
if(S.top-S.base == S.stacksize) return ERROR;
S.elem[++S.top]=s;
return OK;
}
int Pop(Stack& S)
{//出栈
if(S.top == S.base) return ERROR;
--S.top;
return OK;
}
int StackEmpty(Stack& S){
if(S.top == S.base) return 0;
else return 1;
}
string GetTop(Stack S)
{//取栈顶元素
if(S.top != S.base) return S.elem[S.top];
}
void InitTree(BiTree &BT)
{//初始化二叉树，根结点数据为"植物界"
BT=new TNode;
BT->left=NULL;
BT->right=NULL;
BT->data="植物界";
}
BiTree FindNodeByName(BiTree BT,string name)
{//根据植物名递归找到对应TNode结点，若不存在则返回NULL
if (BT == NULL) {
return NULL;
}
// 访问根节点
if(BT->data == name){
return BT;
}
// 递归遍历左儿子
BiTree lresult = FindNodeByName(BT->left,name);
// 递归遍历右兄弟
BiTree rresult = FindNodeByName(BT->right,name);
return lresult != NULL ? lresult : rresult;
}
BiTree Findfather(BiTree BT,string name, Stack& s,string &father)
{//根据植物名递归找到对应TNode结点，若不存在则返回NULL
if (BT == NULL) {
return NULL;
}
// 访问根节点
if(BT->data == name){
father = GetTop(s);
return BT;
}
// 递归遍历左儿子
Push(s,BT->data);
BiTree lresult = Findfather(BT->left,name, s, father);
Pop(s);
// 递归遍历右兄弟
BiTree rresult = Findfather(BT->right,name, s, father);
return lresult != NULL ? lresult : rresult;
}
void InsertTNode(BiTree& BT, Cata temp){
TNode* new_node = new TNode; //当前节点
TNode* new_node_child = new TNode; //子节点
new_node = FindNodeByName(BT, temp.father);
new_node_child->data = temp.child;
new_node_child->left = NULL;
new_node_child->right = NULL;
if (new_node->left == NULL) { //如果没有孩子，则直接插入左子节点
new_node->left = new_node_child;
}
else { //如果有孩子
new_node = new_node->left; //当前节点变为左孩子
while (new_node->right != NULL) { //当他有兄弟时
new_node = new_node->right; //一直往下直到没有兄弟为止
}
new_node->right = new_node_child; //将数据插入右孩子
}
}
void CreateByFile(BiTree& BT, string filename)
{//根据文件名向树BT中添加结点
ifstream infile;
infile.open(filename.c_str());
string line;
while (getline(infile, line)) {
Cata temp;
stringstream data(line);
string s;
int flag = 0;
while (getline(data, s, '#')) {
if (flag == 0) temp.child = s;
if (flag == 1) temp.father = s;
flag++;
}
InsertTNode(BT,temp);
}
infile.close();
return;
}
void FindClass(BiTree& BT, string name)
{//根据植物名，输出其从界到属的类别信息，需要自行定义递归函数（若还需用到栈，请自行定义）
Stack s;
InitStack(s);
string father1, father2, father3, father4, father5, father6;
Findfather(BT, name, s, father1);
InitStack(s);
Findfather(BT, father1, s, father2);
InitStack(s);
Findfather(BT, father2, s, father3);
InitStack(s);
Findfather(BT, father3, s, father4);
InitStack(s);
Findfather(BT, father4, s, father5);
InitStack(s);
Findfather(BT, father5, s, father6);
cout<<father1<<" "<<father2<<" "<<father3<<" "<<father4<<" "<<father5<<" "<<father6<<endl;
return;
}
第20关：同属植物信息检索
#include<bits/stdc++.h>
#include<stack>
#define OK 1
#define ERROR 0
#define MAXSIZE 6490
using namespace std;
typedef struct TNode{
string data;
struct TNode *left;
struct TNode *right;
}TNode,*BiTree;
struct Cata { //定义分类
string father; //右边的分类
string child; //左边的分类
};
typedef struct Stack{
string *elem;
int base; // 栈底指针
int top; // 栈顶指针
int stacksize; // 栈的最大容量
}Stack;
int InitStack(Stack& S)
{//栈初始化
S.elem=new string[MAXSIZE];
if(!S.elem) exit(ERROR);
S.top=S.base=0; // 不要忘记初始化为0
S.stacksize=MAXSIZE;
return OK;
}
int Push(Stack& S, string s)
{//入栈
if(S.top-S.base == S.stacksize) return ERROR;
S.elem[++S.top]=s;
return OK;
}
int Pop(Stack& S)
{//出栈
if(S.top == S.base) return ERROR;
--S.top;
return OK;
}
int StackEmpty(Stack& S){
if(S.top == S.base) return 0;
else return 1;
}
string GetTop(Stack S)
{//取栈顶元素
if(S.top != S.base) return S.elem[S.top];
}
void InitTree(BiTree &BT)
{//初始化二叉树，根结点数据为"植物界"
BT=new TNode;
BT->left=NULL;
BT->right=NULL;
BT->data="植物界";
}
BiTree FindNodeByName(BiTree BT,string name)
{//根据植物名递归找到对应TNode结点，若不存在则返回NULL
if (BT == NULL) {
return NULL;
}
// 访问根节点
if(BT->data == name){
return BT;
}
// 递归遍历左儿子
BiTree lresult = FindNodeByName(BT->left,name);
// 递归遍历右兄弟
BiTree rresult = FindNodeByName(BT->right,name);
return lresult != NULL ? lresult : rresult;
}
BiTree Findfather(BiTree BT,string name, Stack& s,string &father)
{//根据植物名递归找到对应TNode结点，若不存在则返回NULL
if (BT == NULL) {
return NULL;
}
// 访问根节点
if(BT->data == name){
father = GetTop(s);
return BT;
}
// 递归遍历左儿子
Push(s,BT->data);
BiTree 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结点，若不存在则返回NULL
if (BT == NULL) {
return NULL;
}
// 访问根节点
if(BT->data == name){
return BT;
}
// 递归遍历左儿子
BiTree lresult = FindNodeByName(BT->left,name);
// 递归遍历右兄弟
BiTree rresult = FindNodeByName(BT->right,name);
return lresult != NULL ? lresult : rresult;
}
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;
}到了这里，关于《数据结构》课程设计(C/C++版)：植物百科数据的管理与分析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
