《数据结构》课程设计(C/C++版)：植物百科数据的管理与分析
目录
第1关：增加植物信息
第2关：删除植物信息
第3关：修改植物信息
第4关：基于顺序表的顺序查找
第5关：基于链表的顺序查找
第6关：基于顺序表的折半查找
第7关：基于二叉排序树的查找
第8关：基于开放地址法的散列查找
第9关：基于链地址法的散列查找
第10关：基于BF算法的植物关键信息查询
第11关：基于KMP算法的植物关键信息查询
第12关：直接插入排序
第13关：折半插入排序
第14关：简单选择排序
第15关：冒泡排序
第16关：快速排序
第17关：植物移植最短路径分析
第18关：可移植路径分析
第19关：植物分类树构建
第20关：同属植物信息检索
第21关：下属植物信息检索
第1关：增加植物信息
#include<bits/stdc++.h>
using namespace std;
struct Plant
{
string name;
string sname;
string place[100];
string detail;
};
typedef struct LNode
{
Plant data;
struct LNode *next;
}LNode,*LinkList;
void ReadFile(LinkList& L, string filename)
{
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)
{
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)
{
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)
{
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)
{
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)
{
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) {
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) {
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) {
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 = new LNode;
L->next = NULL;
}
void ListInsert(LinkList& L, int i, Plant temp) {
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) {
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) {
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) {
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.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关：基于二叉排序树的查找
#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关：基于开放地址法的散列查找
#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关：基于链地址法的散列查找
#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算法的植物关键信息查询
#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算法的植物关键信息查询
#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关：直接插入排序
#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.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关：折半插入排序
#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关：简单选择排序
#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关：冒泡排序
#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关：快速排序
#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关：植物移植最短路径分析
#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关：可移植路径分析
#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关：植物分类树构建
#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;
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)
{
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)
{
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)
{
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;
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)
{
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)
{
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)
{
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)
{
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++版
花店卖花系统课程设计
一个可敬的队友
3.ElasticSearch分布式数据分析引擎基础概念与使用
基于Java的花卉销售系统的设计与实现/管理系统/鲜花网站
花草百科识别软件下载,花草百科识别软件下载手机版 v1.1
基于大数据背景的云南花卉物流系统升级研究
基于Java+SpringBoot+Vue+Redis+RabbitMq的鲜花商城
兰花的繁殖与管理
网址: 《数据结构》课程设计(C/C++版)：植物百科数据的管理与分析 https://m.huajiangbk.com/newsview104784.html
| 上一篇: 国际国内中学生重要竞赛规则[[教 |
下一篇: 天津市西青区公开招聘41名机关事 |
