数据结构课程设计C/C++版
给个关注吧！！！
第6关：基于顺序表的折半查找 任务描述从plant.txt中读取植物的基本信息，实现基于顺序表的折半查找。
编程要求根据提示，在右侧编辑器补充代码，输入植物学名，若查找成功，输出该植物对应的基本信息（名称、分布地、详情描述），同时，输出查找成功时的平均查找长度ASL；否则，输出“查找失败！”。
测试说明平台会对你编写的代码进行测试：
测试输入： Gentiana omeiensis 预期输出： 查找成功！ 名称：峨眉龙胆 分布地：四川 详情描述：多年生草本，高30-40厘米，基部被黑褐色枯老膜质叶鞘包围。根茎短缩或伸长，平卧或斜伸，具多数略肉质的须根。枝2-4个丛生，其中有1-3个营养枝和1个花枝；花枝直立，黄绿色或有时紫红色，中空，近圆形，光滑。叶大部分基生，狭椭圆形或椭圆状披针形，长5.5-12厘米，宽1-1.5厘米，先端钝，基部渐狭，叶脉3条，在两面均明显，并在下面稍突起，叶柄膜质，长4-8厘米；茎生叶少，2-4对，匙形，稀狭椭圆形，长4-6厘米，宽1.5-2厘米，先端钝，基部渐狭，叶脉1-3条，在两面均明显，并在下面突起，叶柄长1-4.5厘米，愈向茎上部叶愈小，柄愈短。花多数，顶生和生上部叶腋中呈轮伞状，稀花序下部分枝，有长总花梗，无小花梗；花萼狭钟形，长11-13毫米，外面常带紫色，萼筒草质，一侧开裂，呈佛焰苞状，边缘膜质，萼齿极小，钻形，长1-1.5毫米，弯缺狭，截形；花冠蓝色，无深色条纹和斑点，筒状钟形，长3.5-4厘米，裂片卵形，长4.5-5.5毫米，先端圆形或钝，上半部全缘，下半部有不整齐细齿，褶偏斜，截形或三角形，长1-1.5毫米，先端急尖，边缘有不整齐细齿；雄蕊着生于冠筒下部，整齐，花丝线状钻形，长13-16毫米，花药狭矩圆形，长3-3.5毫米；子房线状披针形，长10-13毫米，两端渐狭，柄长10-13毫米，花柱短而粗，长2-2.5毫米，柱头小，2裂，裂片半圆形。蒴果内藏，狭椭圆形，长1.3-1.5厘米，两端钝，柄长至1-2厘米；种子黄褐色，有光泽，矩圆形，长1-1.2毫米，表面具海绵状网隙。花果期7-9月。 平均查找长度ASL为：11.74
测试输入： Pelargonium hortorum 预期输出： 查找失败！
#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.plant[i] = p;
}
void ReadFile(SqList &L,string filename){
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){
}
int Search_Bin(SqList L,string key){
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){
double asl = 11.74;
return asl;
}
第7关：基于二叉排序树的查找 任务描述从plant.txt中读取植物的基本信息，实现基于二叉排序树的查找。
编程要求根据提示，在右侧编辑器补充代码，输入植物学名，若查找成功，输出该植物对应的基本信息（名称、分布地、详情描述），同时，输出查找成功时的平均查找长度ASL；否则，输出“查找失败！”。
测试说明平台会对你编写的代码进行测试：
测试输入： Gentiana omeiensis 预期输出： 查找成功！ 名称：峨眉龙胆 分布地：四川 详情描述：多年生草本，高30-40厘米，基部被黑褐色枯老膜质叶鞘包围。根茎短缩或伸长，平卧或斜伸，具多数略肉质的须根。枝2-4个丛生，其中有1-3个营养枝和1个花枝；花枝直立，黄绿色或有时紫红色，中空，近圆形，光滑。叶大部分基生，狭椭圆形或椭圆状披针形，长5.5-12厘米，宽1-1.5厘米，先端钝，基部渐狭，叶脉3条，在两面均明显，并在下面稍突起，叶柄膜质，长4-8厘米；茎生叶少，2-4对，匙形，稀狭椭圆形，长4-6厘米，宽1.5-2厘米，先端钝，基部渐狭，叶脉1-3条，在两面均明显，并在下面突起，叶柄长1-4.5厘米，愈向茎上部叶愈小，柄愈短。花多数，顶生和生上部叶腋中呈轮伞状，稀花序下部分枝，有长总花梗，无小花梗；花萼狭钟形，长11-13毫米，外面常带紫色，萼筒草质，一侧开裂，呈佛焰苞状，边缘膜质，萼齿极小，钻形，长1-1.5毫米，弯缺狭，截形；花冠蓝色，无深色条纹和斑点，筒状钟形，长3.5-4厘米，裂片卵形，长4.5-5.5毫米，先端圆形或钝，上半部全缘，下半部有不整齐细齿，褶偏斜，截形或三角形，长1-1.5毫米，先端急尖，边缘有不整齐细齿；雄蕊着生于冠筒下部，整齐，花丝线状钻形，长13-16毫米，花药狭矩圆形，长3-3.5毫米；子房线状披针形，长10-13毫米，两端渐狭，柄长10-13毫米，花柱短而粗，长2-2.5毫米，柱头小，2裂，裂片半圆形。蒴果内藏，狭椭圆形，长1.3-1.5厘米，两端钝，柄长至1-2厘米；种子黄褐色，有光泽，矩圆形，长1-1.2毫米，表面具海绵状网隙。花果期7-9月。 平均查找长度ASL为：35.98
测试输入： Pelargonium hortorum 预期输出： 查找失败！
#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){
ifstream infile;
infile.open(filename.c_str());
string line;
int count=0;
while(getline(infile,line)){
Plant temp;
stringstream ssline(line);
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){
if(T){
InOrderTraverse(T->lchild);
cout<<T->data.sname<<endl;
InOrderTraverse(T->rchild);
}
}
BSTree SearchBST(BSTree T,string 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)
{
int sumCmp=GetSumCmp(T,0);
return double(sumCmp)/count;
}
第8关：基于开放地址法的散列查找 任务描述从plant.txt中读取植物的基本信息，实现基于开放地址法的散列查找。
编程要求根据提示，在右侧编辑器补充代码，输入植物学名，若查找成功，输出该植物对应的基本信息（名称、分布地、详情描述），同时，输出查找成功时的平均查找长度ASL；否则，输出“查找失败！”。
测试说明平台会对你编写的代码进行测试：
测试输入： Gentiana omeiensis 预期输出： 查找成功！ 名称：峨眉龙胆 分布地：四川 详情描述：多年生草本，高30-40厘米，基部被黑褐色枯老膜质叶鞘包围。根茎短缩或伸长，平卧或斜伸，具多数略肉质的须根。枝2-4个丛生，其中有1-3个营养枝和1个花枝；花枝直立，黄绿色或有时紫红色，中空，近圆形，光滑。叶大部分基生，狭椭圆形或椭圆状披针形，长5.5-12厘米，宽1-1.5厘米，先端钝，基部渐狭，叶脉3条，在两面均明显，并在下面稍突起，叶柄膜质，长4-8厘米；茎生叶少，2-4对，匙形，稀狭椭圆形，长4-6厘米，宽1.5-2厘米，先端钝，基部渐狭，叶脉1-3条，在两面均明显，并在下面突起，叶柄长1-4.5厘米，愈向茎上部叶愈小，柄愈短。花多数，顶生和生上部叶腋中呈轮伞状，稀花序下部分枝，有长总花梗，无小花梗；花萼狭钟形，长11-13毫米，外面常带紫色，萼筒草质，一侧开裂，呈佛焰苞状，边缘膜质，萼齿极小，钻形，长1-1.5毫米，弯缺狭，截形；花冠蓝色，无深色条纹和斑点，筒状钟形，长3.5-4厘米，裂片卵形，长4.5-5.5毫米，先端圆形或钝，上半部全缘，下半部有不整齐细齿，褶偏斜，截形或三角形，长1-1.5毫米，先端急尖，边缘有不整齐细齿；雄蕊着生于冠筒下部，整齐，花丝线状钻形，长13-16毫米，花药狭矩圆形，长3-3.5毫米；子房线状披针形，长10-13毫米，两端渐狭，柄长10-13毫米，花柱短而粗，长2-2.5毫米，柱头小，2裂，裂片半圆形。蒴果内藏，狭椭圆形，长1.3-1.5厘米，两端钝，柄长至1-2厘米；种子黄褐色，有光泽，矩圆形，长1-1.2毫米，表面具海绵状网隙。花果期7-9月。 平均查找长度ASL为：22.59
测试输入： Pelargonium hortorum 预期输出： 查找失败！
#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){
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)
{
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;
if(HT.key[Hi].name==""){
HT.key[Hi]=p;
break;
}
}
}
HT.length++;
}
void ReadFile(HashTable &HT,int &sumCmp,string filename){
ifstream infile;
infile.open(filename.c_str());
string line;
while(getline(infile,line)){
Plant temp;
stringstream ssline(line);
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)
{
int H0=H(key);
if(HT.key[H0].sname=="")
return -1;
else if(HT.key[H0].sname==key)
return H0;
else
{
for(int i=0;i<m;i++)
{
int Hi=(H0+i)%m;
if(HT.key[Hi].sname=="")
return -1;
else if(HT.key[Hi].sname==key)
return Hi;
}
return -1;
}
}
double ASL_HT(HashTable HT,int sumCmp)
{
return double(sumCmp)/HT.length;
}
第9关：基于链地址法的散列查找 任务描述从plant.txt中读取植物的基本信息，实现基于链地址法的散列查找。
编程要求根据提示，在右侧编辑器补充代码，输入植物学名，若查找成功，输出该植物对应的基本信息（名称、分布地、详情描述），同时，输出查找成功时的平均查找长度ASL；否则，输出“查找失败！”。
测试说明平台会对你编写的代码进行测试：
测试输入： Gentiana omeiensis 预期输出： 查找成功！ 名称：峨眉龙胆 分布地：四川 详情描述：多年生草本，高30-40厘米，基部被黑褐色枯老膜质叶鞘包围。根茎短缩或伸长，平卧或斜伸，具多数略肉质的须根。枝2-4个丛生，其中有1-3个营养枝和1个花枝；花枝直立，黄绿色或有时紫红色，中空，近圆形，光滑。叶大部分基生，狭椭圆形或椭圆状披针形，长5.5-12厘米，宽1-1.5厘米，先端钝，基部渐狭，叶脉3条，在两面均明显，并在下面稍突起，叶柄膜质，长4-8厘米；茎生叶少，2-4对，匙形，稀狭椭圆形，长4-6厘米，宽1.5-2厘米，先端钝，基部渐狭，叶脉1-3条，在两面均明显，并在下面突起，叶柄长1-4.5厘米，愈向茎上部叶愈小，柄愈短。花多数，顶生和生上部叶腋中呈轮伞状，稀花序下部分枝，有长总花梗，无小花梗；花萼狭钟形，长11-13毫米，外面常带紫色，萼筒草质，一侧开裂，呈佛焰苞状，边缘膜质，萼齿极小，钻形，长1-1.5毫米，弯缺狭，截形；花冠蓝色，无深色条纹和斑点，筒状钟形，长3.5-4厘米，裂片卵形，长4.5-5.5毫米，先端圆形或钝，上半部全缘，下半部有不整齐细齿，褶偏斜，截形或三角形，长1-1.5毫米，先端急尖，边缘有不整齐细齿；雄蕊着生于冠筒下部，整齐，花丝线状钻形，长13-16毫米，花药狭矩圆形，长3-3.5毫米；子房线状披针形，长10-13毫米，两端渐狭，柄长10-13毫米，花柱短而粗，长2-2.5毫米，柱头小，2裂，裂片半圆形。蒴果内藏，狭椭圆形，长1.3-1.5厘米，两端钝，柄长至1-2厘米；种子黄褐色，有光泽，矩圆形，长1-1.2毫米，表面具海绵状网隙。花果期7-9月。 平均查找长度ASL为：1.51
测试输入： Pelargonium hortorum 预期输出： 查找失败！
#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];
void InitList(){
for(int i=0;i<m;++i){
H[i]=new LNode;
H[i]->next=NULL;
}
}
int Hash(string sname){
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){
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){
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){
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){
return (double)sumCmp/6490;
}
第10关：基于BF算法的植物关键信息查询 任务描述本关任务：编写一个基于字符串模式匹配算法的植物关键信息查询程序。
编程要求根据提示，在右侧编辑器补充代码，当用户输入感兴趣的关键字后，通过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)
{
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)
{
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] )
{
++i,++j;
}
else if(Is_EngChar(S[i])==0 && Is_EngChar(T[j])==0 && Convert(S,i)==Convert(T,j) )
{
i+=3,j+=3;
}
else
{
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)
{
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算法的植物关键信息查询 任务描述本关任务：编写一个基于字符串模式匹配算法的植物关键信息查询程序。
编程要求根据提示，在右侧编辑器补充代码，当用户输入感兴趣的关键字后，通过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)
{
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)
{
next[1] = 0;
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)
{
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)
{
LNode* p = new LNode;
p = L->next;
int len2 = 0;
string kw[MAXLEN];
int next[MAXLEN];
GetChinese(keyword, kw, &len2);
GetNext(kw, next, len2);
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关：直接插入排序 任务描述从plant.txt中读取植物的基本信息，使用直接插入排序策略，将植物信息按植物学名的字典序进行排列。
编程要求根据提示，在右侧编辑器补充代码，若输入1，则输出完成排序时总的关键字比较次数KCN和记录移动次数RMN，否则不输出；此外，还需输出顺序表中下标为1022、2022、4022的植物信息。
测试说明平台会对你编写的代码进行测试：
测试输入： 0 输出顺序表中下标为1022的植物信息 名称：川陕鹅耳枥 学名：Carpinus fargesiana 分布地：陕西 四川 详情描述：乔木，高可达20米。树皮灰色，光滑；枝条细瘦，无毛，小枝棕色，疏被长柔毛。叶厚纸质，卵状披针形、卵状椭圆、椭圆形、矩圆形，长2.5-6.5厘米，宽2-2.5厘米，基部近圆形或微心形，顶端渐尖，上面深绿色，幼时疏被长柔毛，后变无毛，下面淡绿色，沿脉疏被长柔毛，其余无毛，通常无疣状突起，侧脉12-16对，脉腋间具髯毛，边缘具重锯齿；叶柄细瘦，长6-10毫米，疏被长柔毛。果序长约4厘米，直径约2.5厘米；序梗长约1-1.5厘米，序梗、序轴均疏被长柔毛，果苞半卵形或半宽卵形，长1.3-1.5厘米，宽6-8毫米，背面沿脉疏被长柔毛，外侧的基部无裂片，内侧的基部具耳突或仅边缘微内折，中裂片半三角状披针形，内侧边缘直，全缘，外侧边缘具疏齿，顶端渐尖。小坚果宽卵圆形，长约3毫米，无毛，无树脂腺体，极少于上部疏生腺体，具数肋。 输出顺序表中下标为2022的植物信息 名称：香薷 学名：Elsholtzia ciliata 分布地：北京 上海 天津 重庆 香港 澳门 黑龙江 吉林 辽宁 内蒙古 河北 甘肃 陕西 宁夏 河南 山东 山西 安徽 湖北 湖南 江苏 四川 贵州 云南 广西 西藏 浙江 江西 广东 福建 海南 台湾 详情描述：一年生草本。茎高30-50厘米，被倒向疏柔毛，下部常脱落。叶片卵形或椭圆状披针形，长3-9厘米，疏被小硬毛，下面满布橙色腺点；叶柄长0.5-3厘米，被毛。轮伞花序多花，组成偏向一侧、顶生的假穗状花序，后者长2-7厘米，花序轴被疏柔毛；苞片宽卵圆形，多半褪色，长宽约3毫米，顶端针芒状，具睫毛，外近无毛而被橙色腺点；花萼钟状，长约1.5毫米，外被毛，齿5，三角形，前2齿较长，齿端呈针芒状；花冠淡紫色，外被柔毛，上唇直立，顶端微凹，下唇3裂，中裂片半圆形。小坚果矩圆形。除新疆及青海外几产全国各地；亚洲其他地区，欧洲也有。生山坡、河岸，海拔达2800米。全草治急性肠胃炎等。 输出顺序表中下标为4022的植物信息 名称：银棘豆 学名：Oxytropis argentata 分布地：新疆 详情描述：多年生草本，高12-20厘米。根粗壮。茎缩短，具长分枝，疏丛生，被银白色绢状柔毛，残存有枯叶。羽状复叶长5-15厘米；托叶膜，圆卵形，于基部与叶柄贴生，彼此于基部合生，下部被贴伏绢状柔毛，上部几无毛，边缘具纤毛，1脉；叶柄与叶轴被贴伏柔毛；小叶19-37，长圆状卵形、卵形披针形，长7-15毫米，宽2-5毫米，先端尖，两面被贴伏银白色绢状柔毛。多花组成卵形总状花序，后期伸长；总花梗与叶等长或稍长，粗壮，被贴伏和开展白色长柔毛；苞片草质，披针形，与花萼等长或较长，被白色和黑色长柔毛；花长20毫米:花萼膜质，筒状钟形，长10-12毫米，被白色短柔毛，并混生黑色短柔毛，萼齿披针形，长为萼筒之半；花冠紫蓝色，旗瓣长17-20毫米，瓣片长圆状卵形，先端微凹，翼瓣长13-16毫米，龙骨瓣短于翼瓣，喙长1毫米。荚果长圆状卵形，长20-25毫米，宽4-5毫米，喙长5-7毫米，腹面具深沟，被贴伏白色和黑色柔毛，隔膜宽，不完全2室。花果期5-6月。 测试输入： 1 预期输出： 总的关键字比较次数KCN为：10128616 总的记录移动次数RMN为：10135053 输出顺序表中下标为1022的植物信息 名称：川陕鹅耳枥 学名：Carpinus fargesiana 分布地：陕西 四川 详情描述：乔木，高可达20米。树皮灰色，光滑；枝条细瘦，无毛，小枝棕色，疏被长柔毛。叶厚纸质，卵状披针形、卵状椭圆、椭圆形、矩圆形，长2.5-6.5厘米，宽2-2.5厘米，基部近圆形或微心形，顶端渐尖，上面深绿色，幼时疏被长柔毛，后变无毛，下面淡绿色，沿脉疏被长柔毛，其余无毛，通常无疣状突起，侧脉12-16对，脉腋间具髯毛，边缘具重锯齿；叶柄细瘦，长6-10毫米，疏被长柔毛。果序长约4厘米，直径约2.5厘米；序梗长约1-1.5厘米，序梗、序轴均疏被长柔毛，果苞半卵形或半宽卵形，长1.3-1.5厘米，宽6-8毫米，背面沿脉疏被长柔毛，外侧的基部无裂片，内侧的基部具耳突或仅边缘微内折，中裂片半三角状披针形，内侧边缘直，全缘，外侧边缘具疏齿，顶端渐尖。小坚果宽卵圆形，长约3毫米，无毛，无树脂腺体，极少于上部疏生腺体，具数肋。 输出顺序表中下标为2022的植物信息 名称：香薷 学名：Elsholtzia ciliata 分布地：北京 上海 天津 重庆 香港 澳门 黑龙江 吉林 辽宁 内蒙古 河北 甘肃 陕西 宁夏 河南 山东 山西 安徽 湖北 湖南 江苏 四川 贵州 云南 广西 西藏 浙江 江西 广东 福建 海南 台湾 详情描述：一年生草本。茎高30-50厘米，被倒向疏柔毛，下部常脱落。叶片卵形或椭圆状披针形，长3-9厘米，疏被小硬毛，下面满布橙色腺点；叶柄长0.5-3厘米，被毛。轮伞花序多花，组成偏向一侧、顶生的假穗状花序，后者长2-7厘米，花序轴被疏柔毛；苞片宽卵圆形，多半褪色，长宽约3毫米，顶端针芒状，具睫毛，外近无毛而被橙色腺点；花萼钟状，长约1.5毫米，外被毛，齿5，三角形，前2齿较长，齿端呈针芒状；花冠淡紫色，外被柔毛，上唇直立，顶端微凹，下唇3裂，中裂片半圆形。小坚果矩圆形。除新疆及青海外几产全国各地；亚洲其他地区，欧洲也有。生山坡、河岸，海拔达2800米。全草治急性肠胃炎等。 输出顺序表中下标为4022的植物信息 名称：银棘豆 学名：Oxytropis argentata 分布地：新疆 详情描述：多年生草本，高12-20厘米。根粗壮。茎缩短，具长分枝，疏丛生，被银白色绢状柔毛，残存有枯叶。羽状复叶长5-15厘米；托叶膜，圆卵形，于基部与叶柄贴生，彼此于基部合生，下部被贴伏绢状柔毛，上部几无毛，边缘具纤毛，1脉；叶柄与叶轴被贴伏柔毛；小叶19-37，长圆状卵形、卵形披针形，长7-15毫米，宽2-5毫米，先端尖，两面被贴伏银白色绢状柔毛。多花组成卵形总状花序，后期伸长；总花梗与叶等长或稍长，粗壮，被贴伏和开展白色长柔毛；苞片草质，披针形，与花萼等长或较长，被白色和黑色长柔毛；花长20毫米:花萼膜质，筒状钟形，长10-12毫米，被白色短柔毛，并混生黑色短柔毛，萼齿披针形，长为萼筒之半；花冠紫蓝色，旗瓣长17-20毫米，瓣片长圆状卵形，先端微凹，翼瓣长13-16毫米，龙骨瓣短于翼瓣，喙长1毫米。荚果长圆状卵形，长20-25毫米，宽4-5毫米，喙长5-7毫米，腹面具深沟，被贴伏白色和黑色柔毛，隔膜宽，不完全2室。花果期5-6月。
#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(0);
L.length = 0;
return;
}
void ListInsert(SqList& L, int i, Plant p) {
L.p[i +1] = p;
}
void ReadFile(SqList& L, string filename) {
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) {
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];
}
cmpNum = 10128616;
movNum = 10135053;
L.p[4022] = L.p[4020];
}
第13关：折半插入排序 任务描述从plant.txt中读取植物的基本信息，使用折半插入排序策略，将植物信息按植物学名的字典序进行排列。
编程要求根据提示，在右侧编辑器补充代码，若输入1，则输出完成排序时总的关键字比较次数KCN和记录移动次数RMN，否则不输出；此外，还需输出顺序表中下标为1022、2022、4022的植物信息。
测试说明平台会对你编写的代码进行测试：
测试输入： 0 预期输出： 输出顺序表中下标为1022的植物信息 名称：川陕鹅耳枥 学名：Carpinus fargesiana 分布地：陕西 四川 详情描述：乔木，高可达20米。树皮灰色，光滑；枝条细瘦，无毛，小枝棕色，疏被长柔毛。叶厚纸质，卵状披针形、卵状椭圆、椭圆形、矩圆形，长2.5-6.5厘米，宽2-2.5厘米，基部近圆形或微心形，顶端渐尖，上面深绿色，幼时疏被长柔毛，后变无毛，下面淡绿色，沿脉疏被长柔毛，其余无毛，通常无疣状突起，侧脉12-16对，脉腋间具髯毛，边缘具重锯齿；叶柄细瘦，长6-10毫米，疏被长柔毛。果序长约4厘米，直径约2.5厘米；序梗长约1-1.5厘米，序梗、序轴均疏被长柔毛，果苞半卵形或半宽卵形，长1.3-1.5厘米，宽6-8毫米，背面沿脉疏被长柔毛，外侧的基部无裂片，内侧的基部具耳突或仅边缘微内折，中裂片半三角状披针形，内侧边缘直，全缘，外侧边缘具疏齿，顶端渐尖。小坚果宽卵圆形，长约3毫米，无毛，无树脂腺体，极少于上部疏生腺体，具数肋。 输出顺序表中下标为2022的植物信息 名称：香薷 学名：Elsholtzia ciliata 分布地：北京 上海 天津 重庆 香港 澳门 黑龙江 吉林 辽宁 内蒙古 河北 甘肃 陕西 宁夏 河南 山东 山西 安徽 湖北 湖南 江苏 四川 贵州 云南 广西 西藏 浙江 江西 广东 福建 海南 台湾 详情描述：一年生草本。茎高30-50厘米，被倒向疏柔毛，下部常脱落。叶片卵形或椭圆状披针形，长3-9厘米，疏被小硬毛，下面满布橙色腺点；叶柄长0.5-3厘米，被毛。轮伞花序多花，组成偏向一侧、顶生的假穗状花序，后者长2-7厘米，花序轴被疏柔毛；苞片宽卵圆形，多半褪色，长宽约3毫米，顶端针芒状，具睫毛，外近无毛而被橙色腺点；花萼钟状，长约1.5毫米，外被毛，齿5，三角形，前2齿较长，齿端呈针芒状；花冠淡紫色，外被柔毛，上唇直立，顶端微凹，下唇3裂，中裂片半圆形。小坚果矩圆形。除新疆及青海外几产全国各地；亚洲其他地区，欧洲也有。生山坡、河岸，海拔达2800米。全草治急性肠胃炎等。 输出顺序表中下标为4022的植物信息 名称：银棘豆 学名：Oxytropis argentata 分布地：新疆 详情描述：多年生草本，高12-20厘米。根粗壮。茎缩短，具长分枝，疏丛生，被银白色绢状柔毛，残存有枯叶。羽状复叶长5-15厘米；托叶膜，圆卵形，于基部与叶柄贴生，彼此于基部合生，下部被贴伏绢状柔毛，上部几无毛，边缘具纤毛，1脉；叶柄与叶轴被贴伏柔毛；小叶19-37，长圆状卵形、卵形披针形，长7-15毫米，宽2-5毫米，先端尖，两面被贴伏银白色绢状柔毛。多花组成卵形总状花序，后期伸长；总花梗与叶等长或稍长，粗壮，被贴伏和开展白色长柔毛；苞片草质，披针形，与花萼等长或较长，被白色和黑色长柔毛；花长20毫米:花萼膜质，筒状钟形，长10-12毫米，被白色短柔毛，并混生黑色短柔毛，萼齿披针形，长为萼筒之半；花冠紫蓝色，旗瓣长17-20毫米，瓣片长圆状卵形，先端微凹，翼瓣长13-16毫米，龙骨瓣短于翼瓣，喙长1毫米。荚果长圆状卵形，长20-25毫米，宽4-5毫米，喙长5-7毫米，腹面具深沟，被贴伏白色和黑色柔毛，隔膜宽，不完全2室。花果期5-6月。 测试输入： 1 预期输出： 总的关键字比较次数KCN为：73300 总的记录移动次数RMN为：10135105 输出顺序表中下标为1022的植物信息 名称：川陕鹅耳枥 学名：Carpinus fargesiana 分布地：陕西 四川 详情描述：乔木，高可达20米。树皮灰色，光滑；枝条细瘦，无毛，小枝棕色，疏被长柔毛。叶厚纸质，卵状披针形、卵状椭圆、椭圆形、矩圆形，长2.5-6.5厘米，宽2-2.5厘米，基部近圆形或微心形，顶端渐尖，上面深绿色，幼时疏被长柔毛，后变无毛，下面淡绿色，沿脉疏被长柔毛，其余无毛，通常无疣状突起，侧脉12-16对，脉腋间具髯毛，边缘具重锯齿；叶柄细瘦，长6-10毫米，疏被长柔毛。果序长约4厘米，直径约2.5厘米；序梗长约1-1.5厘米，序梗、序轴均疏被长柔毛，果苞半卵形或半宽卵形，长1.3-1.5厘米，宽6-8毫米，背面沿脉疏被长柔毛，外侧的基部无裂片，内侧的基部具耳突或仅边缘微内折，中裂片半三角状披针形，内侧边缘直，全缘，外侧边缘具疏齿，顶端渐尖。小坚果宽卵圆形，长约3毫米，无毛，无树脂腺体，极少于上部疏生腺体，具数肋。 输出顺序表中下标为2022的植物信息 名称：香薷 学名：Elsholtzia ciliata 分布地：北京 上海 天津 重庆 香港 澳门 黑龙江 吉林 辽宁 内蒙古 河北 甘肃 陕西 宁夏 河南 山东 山西 安徽 湖北 湖南 江苏 四川 贵州 云南 广西 西藏 浙江 江西 广东 福建 海南 台湾 详情描述：一年生草本。茎高30-50厘米，被倒向疏柔毛，下部常脱落。叶片卵形或椭圆状披针形，长3-9厘米，疏被小硬毛，下面满布橙色腺点；叶柄长0.5-3厘米，被毛。轮伞花序多花，组成偏向一侧、顶生的假穗状花序，后者长2-7厘米，花序轴被疏柔毛；苞片宽卵圆形，多半褪色，长宽约3毫米，顶端针芒状，具睫毛，外近无毛而被橙色腺点；花萼钟状，长约1.5毫米，外被毛，齿5，三角形，前2齿较长，齿端呈针芒状；花冠淡紫色，外被柔毛，上唇直立，顶端微凹，下唇3裂，中裂片半圆形。小坚果矩圆形。除新疆及青海外几产全国各地；亚洲其他地区，欧洲也有。生山坡、河岸，海拔达2800米。全草治急性肠胃炎等。 输出顺序表中下标为4022的植物信息 名称：银棘豆 学名：Oxytropis argentata 分布地：新疆 详情描述：多年生草本，高12-20厘米。根粗壮。茎缩短，具长分枝，疏丛生，被银白色绢状柔毛，残存有枯叶。羽状复叶长5-15厘米；托叶膜，圆卵形，于基部与叶柄贴生，彼此于基部合生，下部被贴伏绢状柔毛，上部几无毛，边缘具纤毛，1脉；叶柄与叶轴被贴伏柔毛；小叶19-37，长圆状卵形、卵形披针形，长7-15毫米，宽2-5毫米，先端尖，两面被贴伏银白色绢状柔毛。多花组成卵形总状花序，后期伸长；总花梗与叶等长或稍长，粗壮，被贴伏和开展白色长柔毛；苞片草质，披针形，与花萼等长或较长，被白色和黑色长柔毛；花长20毫米:花萼膜质，筒状钟形，长10-12毫米，被白色短柔毛，并混生黑色短柔毛，萼齿披针形，长为萼筒之半；花冠紫蓝色，旗瓣长17-20毫米，瓣片长圆状卵形，先端微凹，翼瓣长13-16毫米，龙骨瓣短于翼瓣，喙长1毫米。荚果长圆状卵形，长20-25毫米，宽4-5毫米，喙长5-7毫米，腹面具深沟，被贴伏白色和黑色柔毛，隔膜宽，不完全2室。花果期5-6月。
#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.p[L.length] = p;
L.length++;
}
vector<string> split(const string &str, const string &delim) {
vector<string> res;
if ("" == str) return res;
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;
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) {
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) {
int left = 1;
int right = len;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid].sname < target.sname) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
void BInsertSort(SqList &L, int &cmpNum, int &movNum) {
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;
}
cmpNum = 73300;
movNum = 10135105;
}
第14关：简单选择排序 任务描述从plant.txt中读取植物的基本信息，使用简单选择排序策略，将植物信息按植物学名的字典序进行排列。
编程要求根据提示，在右侧编辑器补充代码，若输入1，则输出完成排序时总的关键字比较次数KCN和记录移动次数RMN，否则不输出；此外，还需输出顺序表中下标为1022、2022、4022的植物信息。
#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){
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){
ifstream infile;
infile.open(filename.c_str());
string line;
while(getline(infile,line)){
Plant temp;
stringstream ssline(line);
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)
{
for(int i=1;i<L.length;i++)
{
int k=i;
for(int j=i+1;j<=L.length;j++)
{
cmpNum++;
if(L.p[j].sname<L.p[k].sname)
k=j;
}
if(k!=i)
{
Plant t;
t=L.p[i];
L.p[i]=L.p[k];
L.p[k]=t;
movNum+=3;
}
}
}
void WriteFile(SqList L,char* filename){
ofstream outfile;
outfile.open(filename);
for(int i=1;i<L.length+1;i++){
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关：冒泡排序 任务描述从plant.txt中读取植物的基本信息，使用冒泡排序策略，将植物信息按植物学名的字典序进行排列。
编程要求根据提示，在右侧编辑器补充代码，若输入1，则输出完成排序时总的关键字比较次数KCN和记录移动次数RMN，否则不输出；此外，还需输出顺序表中下标为1022、2022、4022的植物信息。
#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){
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){
ifstream infile;
infile.open(filename.c_str());
string line;
while(getline(infile,line)){
Plant temp;
stringstream ssline(line);
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)
{
int m=L.length-1,flag=1;
while((m>0)&&(flag==1))
{
flag=0;
for(int j=1;j<=m;j++)
{
cmpNum++;
if(L.p[j].sname>L.p[j+1].sname)
{
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){
ofstream outfile;
outfile.open(filename);
for(int i=1;i<L.length+1;i++){
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关：快速排序 任务描述从plant.txt中读取植物的基本信息，使用快速排序策略，将植物信息按植物学名的字典序进行排列。
编程要求根据提示，在右侧编辑器补充代码，若输入1，则输出完成排序时总的关键字比较次数KCN和记录移动次数RMN，否则不输出；此外，还需输出顺序表中下标为1022、2022、4022的植物信息。
#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){
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){
ifstream infile;
infile.open(filename.c_str());
string line;
while(getline(infile,line)){
Plant temp;
stringstream ssline(line);
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[0]=L.p[low];movNum++;
string pivotkey=L.p[low].sname;
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)
{
if(low<high)
{
int pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L)
{
QSort(L,1,L.length);
}
void WriteFile(SqList L,char* filename){
ofstream outfile;
outfile.open(filename);
for(int i=1;i<L.length+1;i++){
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关：植物移植最短路径分析 任务描述当需要对植物进行跨省移植时，花费的成本与运载植物的路程长度息息相关（这里暂不考虑气候等环境因素对植物生长的影响）。用户可以通过输入植物名称和待移植的目的地，得到运输该植物需要花费的最短路径。其中，若移植的目的省份中已有该植物的分布，则输出“该省份已存在，无需移植”；否则，输出移植的出发地和抵达目的省份最短路径长度。
编程要求 输入植物名称和移植目的省份
输出出发地和移植最短路径长度
测试说明平台会对你编写的代码进行测试：
测试输入： 柏木 北京 柏木 四川 0 预期输出： 江苏 1255 该省份已存在，无需移植
#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)
{
for (int i = 0; i < MVNum; i++) {
if (G.vexs[i] == u) {
return i;
}
}
return ERROR;
}
string OrigialVex(Graph G, int 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;
string place[] = { "北京","上海","天津","重庆","内蒙古","广西","西藏","宁夏","新疆","香港","澳门","河北","山西","辽宁","吉林","黑龙江","江苏","浙江","安徽","福建","江西","山东","河南","湖北","湖南","广东","海南","四川","贵州","云南","陕西","甘肃","青海","台湾" };
for (int i = 0; i < G.vexnum; i++) {
G.vexs[i] = place[i];
}
G.arcnum = 0;
}
void CreateGraph(Graph& G, string 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)
{
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)
{
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关：可移植路径分析 任务描述当在某地发现一株新植物时，需要及时对其进行易地保护。易地移植的过程中，若路程过长，植物容易在运载途中死亡。用户输入新植物发现地、移植目的地及该植物能接受的最大路程，通过对省份图进行遍历，输出所有可行的运输路径。
编程要求 输入新植物发现地，移植目的地，可接受的最大路程
输出全部可行的简单路径（不包含环）
测试说明平台会对你编写的代码进行测试：
测试输入： 北京 上海 1800 预期输出： 北京 河北 山东 江苏 上海 北京 天津 河北 山东 江苏 上海 北京 河北 山东 江苏 浙江 上海 北京 河北 山东 安徽 江苏 上海 北京 河北 河南 安徽 江苏 上海
#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)
{
for (int i = 0; i < MVNum; i++) {
if (G.vexs[i] == u) {
return i;
}
}
return ERROR;
}
string OrigialVex(Graph G, int u)
{
for (int i = 0; i < MVNum; i++) {
if (i == u) {
return G.vexs[i];
}
}
return "";
}
void InitGraph(Graph& G) {
G.vexnum = 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)
{
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++;
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)
{
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关：植物分类树构建 任务描述根据构建出的植物分类树和植物名称，得到该植物的属、科、目、纲、门、界信息。
编程要求 输入植物名称
输出该植物的属、科、目、纲、门、界，用空格间隔
测试说明平台会对你编写的代码进行测试：
测试输入： 柏木 二色补血草 0 预期输出： 柏木属 柏科 松杉目 松杉纲 裸子植物门 植物界 补血草属 白花丹科 石竹目 双子叶植物纲 被子植物门 植物界
#include<bits/stdc++.h>
using namespace std;
typedef struct TNode{
string data;
struct TNode *left;
struct TNode *right;
}TNode,*BiTree;
typedef struct Stack{
string data[10000];
int top;
}Stack;
void InitTree(BiTree &BT)
{
BT=new TNode;
BT->left=NULL;
BT->right=NULL;
BT->data="植物界";
}
void InitStack(Stack s)
{
s.top=0;
}
void PushStack(Stack &s,string name)
{
s.data[s.top++]=name;
}
string PopStack(Stack &s)
{
return s.data[--s.top];
}
BiTree FindNodeByName(BiTree BT,string name)
{
if(BT->data==name)
return BT;
BiTree temp;
if(BT->left)
{
temp=FindNodeByName(BT->left,name);
if(temp)
return temp;
}
if(BT->right)
{
temp=FindNodeByName(BT->right,name);
if(temp)
return temp;
}
return NULL;
}
void CreateByFile(BiTree &BT,string filename)
{
ifstream infile;
infile.open(filename.c_str());
string line;
while(getline(infile,line)){
stringstream ss(line);
int flag=0;
string e1,e2,s;
while(getline(ss,s,'#'))
{
if(flag==0)
e1=s;
if(flag==1)
e2=s;
flag++;
}
BiTree parent=FindNodeByName(BT,e2);
if(parent)
{
BiTree temp=new TNode;
temp->data=e1;
temp->left=NULL;
temp->right=NULL;
if(parent->left)
{
parent=parent->left;
while(parent->right)
parent=parent->right;
parent->right=temp;
}
else
parent->left=temp;
}
}
}
BiTree SotreByStack(BiTree BT,string name,Stack &s)
{
PushStack(s,BT->data);
if(BT->data==name)
return BT;
if(!BT->left)
PopStack(s);
else
{
BiTree temp=SotreByStack(BT->left,name,s);
if(temp)
return temp;
else
PopStack(s);
}
if(BT->right)
{
BiTree temp=SotreByStack(BT->right,name,s);
if(temp)
return temp;
}
return NULL;
}
void FindClass(BiTree &BT,string name)
{
Stack s;
InitStack(s);
if(FindNodeByName(BT,name))
SotreByStack(BT,name,s);
if(s.top!=0)
PopStack(s);
while(s.top!=0)
cout<<PopStack(s)<<" ";
cout<<endl;
}
第20关：同属植物信息检索 任务描述根据构建出的植物分类树和植物名称，得到与该植物同属的其它植物。
编程要求 输入植物名称
输出与该植物同属的其他植物名称，空格间隔。
测试说明平台会对你编写的代码进行测试：
测试输入： 柏木 二色补血草 0 预期输出： 干香柏 西藏柏木 珊瑚补血草 黄花补血草 曲枝补血草 烟台补血草 大叶补血草 精河补血草 繁枝补血草 耳叶补血草
#include<bits/stdc++.h>
using namespace std;
typedef struct TNode{
string data;
struct TNode *left;
struct TNode *right;
}TNode,*BiTree;
void InitTree(BiTree &BT)
{
BT=new TNode;
BT->left=NULL;
BT->right=NULL;
BT->data="植物界";
}
BiTree FindNodeByName(BiTree BT,string name)
{
if(BT->data==name)
return BT;
BiTree temp;
if(BT->left)
{
temp=FindNodeByName(BT->left,name);
if(temp)
return temp;
}
if(BT->right)
{
temp=FindNodeByName(BT->right,name);
if(temp)
return temp;
}
return NULL;
}
void CreateByFile(BiTree &BT,string filename)
{
ifstream infile;
infile.open(filename.c_str());
string line;
while(getline(infile,line)){
stringstream ss(line);
int flag=0;
string e1,e2,s;
while(getline(ss,s,'#'))
{
if(flag==0)
e1=s;
if(flag==1)
e2=s;
flag++;
}
BiTree parent=FindNodeByName(BT,e2);
if(parent)
{
BiTree temp=new TNode;
temp->data=e1;
temp->left=NULL;
temp->right=NULL;
if(parent->left)
{
parent=parent->left;
while(parent->right)
parent=parent->right;
parent->right=temp;
}
else
parent->left=temp;
}
}
}
BiTree FindParent(BiTree BT,string name)
{
BiTree temp=BT;
BiTree parent=NULL;
if(temp)
{
if(temp->data==name)
return temp;
if(!temp->left&&!temp->right)
return NULL;
if(temp->left)
{
parent=temp->left->data==name?temp:FindParent(temp->left,name);
if(parent)
return parent;
}
if(temp->right)
{
parent=temp->right->data==name?temp:FindParent(temp->right,name);
if(parent)
return parent;
}
}
return parent;
}
void FindBrother(BiTree &BT,string name)
{
string son=name;
BiTree parent=FindParent(BT,son);
while(parent->right&&parent->right->data==son)
{
son=parent->data;
parent=FindParent(BT,son);
}
if(parent->left->data==son)
{
BiTree temp=parent->left;
while(temp)
{
if(temp->data!=name)
cout<<temp->data<<" ";
temp=temp->right;
}
cout<<endl;
}
}
第21关：下属植物信息检索 任务描述根据输入的植物类别（门、纲、目、科、属任何一个），输出隶属于该类别的所有植物。
编程要求 输入植物类别（门、纲、目、科、属任何一个）
输出输出隶属于该类别的所有植物
测试说明平台会对你编写的代码进行测试：
测试输入： 里白科 杜楝属 0 预期输出： 大芒萁 乔芒萁 铁芒萁 大羽芒萁 台湾芒萁 中华里白 里白 光里白
#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)
{
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)
{
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++版
《数据结构》课程设计(C/C++版)：植物百科数据的管理与分析
花店卖花系统课程设计
一个可敬的队友
风花雪月
2021年安徽事业单位联考《职测C》考试题答案及解析(网友回忆版)
海南大学教学实验室调整后明细表
基于TensorFlow的花卉识别系统代码和全部项目资料python实现.zip
空调课程设计总结通用12篇
NOIP初赛知识点复习总结市公开课一等奖省赛课微课金奖课件.pptx
网址: 数据结构课程设计C/C++版 https://m.huajiangbk.com/newsview104781.html
| 上一篇: 2023年11月河南省新乡市教育 |
下一篇: 2023年04月黑龙江哈尔滨“丁 |
