『データ構造』課程設計(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 Node
{
    Plant data;            // ノードのデータ領域
    struct Node *next;     // ポインタ領域
}Node, *List;

void ReadFile(List& L, string filename)
{// ファイルからデータを読み込み、連結リストLに格納する
    ifstream infile("data_edit/plant.txt");
    string line;
    List r = L;
    while (getline(infile, line)) {
        List p = new Node;
        Plant temp;
        stringstream data(line);
        string s;
        int idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.name = s;
            if (idx == 1) temp.sname = s;
            if (idx == 2) {
                stringstream ssplace(s);
                string place;
                int placeCount = 0;
                while (getline(ssplace, place, '@')) {
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if (idx == 3) temp.detail = s;
            idx++;
        }
        p->data = temp;
        p->next = r->next;
        r->next = p;
        r = p;
    }
    infile.close();
    return;
}

int InPlant(List L, string name)
{// 指定された植物名nameが連結リスト内に存在するか判定
    Node* p = new Node;
    p = L->next;
    int found = 0;
    while (p) {
        if (p->data.name == name) {
            found++;
        }
        p = p->next;
    }
    if (found > 0) {
        return true;
    }
    else {
        return false;
    }
}

bool InsertPlant(List &L, string filename)
{// 植物情報を追加。植物の名称、学名、分布地、詳細説明を入力し、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 Node
{
    Plant data;            // ノードのデータ領域
    struct Node *next;     // ポインタ領域
}Node, *List;

void ReadFile(List& L, string filename)
{// ファイルからデータを読み込み、連結リストLに格納する
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    List r = L;
    while (getline(infile, line)) {
        List p = new Node;
        Plant temp;
        stringstream data(line);
        string s;
        int idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.name = s;
            if (idx == 1) temp.sname = s;
            if (idx == 2) {
                stringstream ssplace(s);
                string place;
                int placeCount = 0;
                while (getline(ssplace, place, '@')) {
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if (idx == 3) temp.detail = s;
            idx++;
        }
        p->data = temp;
        p->next = r->next;
        r->next = p;
        r = p;
    }
    infile.close();
    return;
}

void DeletePlant(List &L, string name, string filename)
{// 指定された植物情報を削除する
    Node* p = new Node;
    p = L;
    while (p->next) {
        if (p->next->data.name == name) {
            Node* q = new Node;
            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 Node
{
    Plant data;            // ノードのデータ領域
    struct Node *next;     // ポインタ領域
}Node, *List;

void ReadFile(List& L, string filename)
{// ファイルからデータを読み込み、連結リストLに格納する
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    List r = L;
    while (getline(infile, line)) {
        List p = new Node;
        Plant temp;
        stringstream data(line);
        string s;
        int idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.name = s;
            if (idx == 1) temp.sname = s;
            if (idx == 2) {
                stringstream ssplace(s);
                string place;
                int placeCount = 0;
                while (getline(ssplace, place, '@')) {
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if (idx == 3) temp.detail = s;
            idx++;
        }
        p->data = temp;
        p->next = r->next;
        r->next = p;
        r = p;
    }
    infile.close();
    return;
}

bool ChangePlant(List &L, string name, string details, string filename)
{// 植物情報を変更する
 // 指定名称が存在すればtrue、存在しなければfalse
    Node* p = new Node;
    p = L->next;
    int found = 0;
    while (p) {
        if (p->data.name == name) {
            p->data.detail = details;
            found++;
        }
        p = p->next;
    }
    if (found > 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 *plants;
    int length;
}SqList;
void InitList(SqList& L) {
    // 順序表の初期化
    L.plants = new Plant[9999];
    if (!L.plants) exit;
    L.length = 0;
    return;
}
void ListInsert(SqList& L, int i, Plant p) {
    L.plants[i] = p;
}
void ReadFile(SqList& L, string filename) {
    // plant.txtファイルを読み込み、各植物データを順序表に挿入
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    int i = 0;
    while (getline(infile, line)) {
        Plant temp;
        stringstream data(line);
        string s;
        int idx = 0;

        while (getline(data, s, '#')) {
            if (idx == 0) temp.name = s;
            if (idx == 1) temp.sname = s;
            if (idx == 2) {
                stringstream ssplace(s);
                string place;
                int placeCount = 0;
                while (getline(ssplace, place, '@')) {
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if (idx == 3) temp.detail = s;
            idx++;
        }
        ListInsert(L, i, temp);
        L.length++;
        i++;
    }
    infile.close();
    return;
}
int Search_Seq(SqList L, string key) {
    // 順序表L内で植物の学名がkeyに等しいデータ要素を順次探索
    // 見つかればそのインデックスを返し、見つからなければ-1を返す
    for (int i = 0; i < L.length; i++) {
        if (L.plants[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 ListNode {                              // 単連結リスト
    Plant data;
    struct ListNode *next;
}ListNode, *List;
void InitList(List& L)
{// 空の単連結リストLを構築
    L = new ListNode;
    L->next = NULL;
}
void ListInsert(List& L, int i, Plant temp) {
    // 先頭ノードを持つ単連結リストのi番目に新しいノードを挿入
    ListNode* p = new ListNode;
    ListNode* q = new ListNode;
    p->data = temp;
    q = L;
    while (i > 1) {
        q = q->next;
        i--;
    }
    p->next = q->next;
    q->next = p;
}
int ReadFile(List& L, string filename) {
    // plant.txtファイルを読み込み、各植物データを連結リストに挿入
    // 植物データの総数を返す
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    int i = 1;
    while (getline(infile, line)) {
        Plant temp;
        stringstream data(line);
        string s;
        int idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.name = s;
            if (idx == 1) temp.sname = s;
            if (idx == 2) {
                stringstream ssplace(s);
                string place;
                int placeCount = 0;
                while (getline(ssplace, place, '@')) {
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if (idx == 3) temp.detail = s;
            idx++;
        }
        ListInsert(L, i, temp);
        i++;
    }
    infile.close();
    return i - 1;
}
ListNode* LocateElem(List L, string key) {
    // 先頭ノードを持つ単連結リストLから学名がkeyの要素を探索
    ListNode* p = new ListNode;
    p = L->next;
    while (p) {
        if (p->data.sname == key) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}
double ASL_LinkList(List L, int count) {
    // 連結リストに基づく順次探索のASLを返す
    ListNode *p = new ListNode;
    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 *plants;
    int length;
}SqList;
void InitList(SqList &L){
    // 順序表の初期化
    L.plants = new Plant[9999];
    if (!L.plants) exit(0);
    L.length = 0;
    return;
}
void ListInsert(SqList &L, int i, Plant p){
    // 順序表Lのi番目に新しい植物pを挿入
    L.plants[i] = p;
}
void ReadFile(SqList &L, string filename){
    // plant.txtファイルを読み込み、各植物データを順序表に挿入
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    int i = 0;
    while (getline(infile, line)) {
        Plant temp;
        stringstream data(line);
        string s;
        int idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.name = s;
            if (idx == 1) temp.sname = s;
            if (idx == 2) {
                stringstream ssplace(s);
                string place;
                int placeCount = 0;
                while (getline(ssplace, place, '@')) {
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if (idx == 3) temp.detail = s;
            idx++;
        }
        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を返す
    for (int i = 0; i < L.length; i++) {
        if (L.plants[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ファイルを読み込み、各植物データを二分探索木に挿入
    // 木のノード数を返す
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    int count = 0;
    while(getline(infile, line)){
        Plant temp;
        stringstream ssline(line);
        string sline;
        int idx = 0;
        while (getline(ssline, sline, '#')){
            if(idx == 0) temp.name = sline;
            if(idx == 1) temp.sname = sline;
            if(idx == 2){
                stringstream ssplace(sline);
                string place;
                int placeCount = 0;
                while(getline(ssplace, place, '@')){
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if(idx == 3) temp.detail = sline;
            idx++;
        }
        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に等しいデータ要素を再帰的に探索
 // 成功時はそのノードのポインタを、失敗時はNULLを返す
    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は木のノード数
    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;                    // 線形探索法で次のハッシュアドレスを計算
            if(HT.key[Hi].name == "") {               // ユニットHiが空の場合、そこに挿入
                HT.key[Hi] = p;
                break;
            }
        }
    }
    HT.length++;
}
void ReadFile(HashTable &HT, int &sumCmp, string filename){
    // plant.txtファイルを読み込み、各植物データをハッシュ表に挿入
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    while(getline(infile, line)){
        Plant temp;
        stringstream ssline(line);
        string sline;
        int idx = 0;
        while (getline(ssline, sline, '#')){
            if(idx == 0) temp.name = sline;
            if(idx == 1) temp.sname = sline;
            if(idx == 2){
                stringstream ssplace(sline);
                string place;
                int placeCount = 0;
                while(getline(ssplace, place, '@')){
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if(idx == 3) temp.detail = sline;
            idx++;
        }
        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;                    // 線形探索法で次のハッシュアドレスを計算
            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 ListNode {                                // 単連結リスト
    Plant data;
    struct ListNode *next;
}ListNode, *List;
List H[m];                                               // チェイン法ハッシュ表の表現、m個の単連結リスト
void InitList(){
    // リストの初期化
    for(int i = 0; i < m; ++i){
        H[i] = new ListNode;
        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);
    List s = H[H0];
    while(s->next){
        s = s->next; sumCmp++;
    }
    List t = new ListNode;
    t->data = p;
    t->next = NULL;
    s->next = t; sumCmp++;
}
int ReadFile(int &sumCmp, string filename){
    // plant.txtファイルを読み込み、各植物データを順序表に挿入
    // 植物データの総数を返す
    ifstream is;
    is.open(filename.c_str());
    string line;
    while (getline(is, line)) {
        Plant temp;
        stringstream ss(line);
        string s;
        int idx = 0;
        while (getline(ss, s, '#')) {
            if (idx == 0) temp.name = s;
            if (idx == 1) temp.sname = s;
            if (idx == 2) {
                stringstream ssplace(s);
                string place;
                int placeCount = 0;
                while (getline(ssplace, place, '@')) {
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if (idx == 3) temp.detail = s;
            idx++;
        }
        ListInsert(temp, sumCmp);
    }
    is.close();
}
int SearchHL(string key){
    // ハッシュ表HTから学名keyに等しい要素を探索
    // 見つかればハッシュ表のユニット番号を返し、見つからなければ-1を返す
    int H0 = Hash(key);
    List 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 ListNode {
    Plant data;            // ノードのデータ領域
    struct ListNode *next; // ポインタ領域
}ListNode, *List;

void ReadFile(List &L, string filename)
{// ファイルからデータを読み込み、連結リストLに格納する
    List r = L;
    ifstream ifp;
    ifp.open(filename.c_str(), ios::in);
    while (!ifp.eof()) {
        List p = new ListNode;
        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)
{// 変換関数：3バイト連続で1つの漢字を返す
    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)
{// 主串Sの中でパターンTがpos文字目から最初に現れる位置を返す。存在しない場合は0を返す
    int i = pos - 1, j = 0;
    while (i < (int)S.length() && j < (int)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 >= (int)T.length())
        return i - (int)T.length() + 1;
    else
        return 0;
}

void SearchInfo(List L, string keyWord)
{// Index_BF関数を呼び出してキー情報を検索
    List 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 ListNode {
    Plant data;             // ノードのデータ領域
    struct ListNode *next;  // ポインタ領域
}ListNode, *List;

void ReadFile(List& L, string filename)
{// ファイルからデータを読み込み、連結リストLに格納する
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    List r = L;
    while (getline(infile, line)) {
        List p = new ListNode;
        Plant temp;
        stringstream data(line);
        string s;
        int idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.name = s;
            if (idx == 1) temp.sname = s;
            if (idx == 2) {
                stringstream ssplace(s);
                string place;
                int placeCount = 0;
                while (getline(ssplace, place, '@')) {
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if (idx == 3) temp.detail = s;
            idx++;
        }
        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;
    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)
{// 連続する3バイト（漢字1文字）をChiKey配列に格納（日本語の句読点を含む）
    int CharCount = 0;
    for (int i = 0; i < (int)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
 // マッチ成功時は主文字列内での出現位置（先頭を表す定数10000）を返し、失敗時は-1を返す
    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(List L, string keyword)
{// Index_KMP関数を呼び出してキー情報を検索
    ListNode* p = new ListNode;
    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のi+1番目に新しい植物pを挿入
    // 注：p[0]は番兵として使用
    L.p[i+1] = p;
}
void ReadFile(SqList& L, string filename) {
    // plant.txtファイルを読み込み、各植物データを順序表に挿入
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    int i = 0;
    while (getline(infile, line)) {
        Plant temp;
        stringstream data(line);
        string s;
        int idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.name = s;
            if (idx == 1) temp.sname = s;
            if (idx == 2) {
                stringstream ssplace(s);
                string place;
                int placeCount = 0;
                while (getline(ssplace, place, '@')) {
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if (idx == 3) temp.detail = s;
            idx++;
        }
        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;
    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 < (int)vp.size(); i++) {
        data.place[i] = vp[i];
    }
    data.detail = infos[3];
    return data;
}
void ReadFile(SqList &L, string filename) {
    // plant.txtファイルを読み込み、各植物データを順序表に挿入
    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に挿入する位置を返す（二分探索）
    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) {
    // 順序表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;
    }
    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ファイルを読み込み、各植物データを順序表に挿入
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    while(getline(infile, line)){
        Plant temp;
        stringstream ssline(line);
        string sline;
        int idx = 0;
        while (getline(ssline, sline, '#')){
            if(idx == 0) temp.name = sline;
            if(idx == 1) temp.sname = sline;
            if(idx == 2){
                stringstream ssplace(sline);
                string place;
                int placeCount = 0;
                while(getline(ssplace, place, '@')){
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if(idx == 3) temp.detail = sline;
            idx++;
        }
        ListInsert(L, L.length+1, temp);
    }
}
void SelectSort(SqList &L, int &cmpNum, int &movNum)
{// 順序表Lに対して単純選択ソートを行う
 // 注：p[0]は未使用
    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){
    // 順序表Lをファイルに書き出す
    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){
    // 順序表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ファイルを読み込み、各植物データを順序表に挿入
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    while(getline(infile, line)){
        Plant temp;
        stringstream ssline(line);
        string sline;
        int idx = 0;
        while (getline(ssline, sline, '#')){
            if(idx == 0) temp.name = sline;
            if(idx == 1) temp.sname = sline;
            if(idx == 2){
                stringstream ssplace(sline);
                string place;
                int placeCount = 0;
                while(getline(ssplace, place, '@')){
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if(idx == 3) temp.detail = sline;
            idx++;
        }
        ListInsert(L, L.length+1, temp);
    }
}
void BubbleSort(SqList &L, int &cmpNum, int &movNum)
{// 順序表Lに対してバブルソートを行う
 // 変数flagを用いて各パスで交換が発生したかどうかを記録
 // 注：p[0]は未使用
    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){
    // 順序表Lをファイルに書き出す
    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){
    // 順序表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ファイルを読み込み、各植物データを順序表に挿入
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    while(getline(infile, line)){
        Plant temp;
        stringstream ssline(line);
        string sline;
        int idx = 0;
        while (getline(ssline, sline, '#')){
            if(idx == 0) temp.name = sline;
            if(idx == 1) temp.sname = sline;
            if(idx == 2){
                stringstream ssplace(sline);
                string place;
                int placeCount = 0;
                while(getline(ssplace, place, '@')){
                    temp.place[placeCount] = place;
                    placeCount++;
                }
            }
            if(idx == 3) temp.detail = sline;
            idx++;
        }
        ListInsert(L, L.length+1, temp);
    }
}
int Partition(SqList &L, int low, int high)
{// 順序表Lの部分表p[low..high]に対して1回の分割を行い、軸の位置を返す
 // 注：p[0]は軸レコードとして使用
    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)
{// 呼び出し前の初期値：low=1; high=L.length;
 // 順序表Lの部分列L.p[low..high]に対してクイックソートを行う
    if(low < high) {
        int pivotloc = Partition(L, low, high);
        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++){
        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 OriginalVex(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を作成
    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 idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.start = s;
            if (idx == 1) temp.end = s;
            if (idx == 2) temp.distance = stoi(s, 0, 10);
            idx++;
        }
        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 n = G.vexnum;
    bool s[MVNum];
    int d[MVNum];
    int path[MVNum];
    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;
        int v = -1;
        for (int w = 0; w < n; w++) {
            if (!s[w] && d[w] < min) {
                v = w;
                min = d[w];
            }
        }
        if (v == -1) break; // 到達不能な場合
        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)
{// plant.txtファイルを読み込み、植物名に対応する分布地を取得し、その数を返す
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    int placeCount = 0;
    while (getline(infile, line)) {
        stringstream data(line);
        string s;
        int idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0 && name != s) break;
            if (idx == 2) {
                stringstream ssplace(s);
                string place;
                while (getline(ssplace, place, '@')) {
                    distribution[placeCount] = place;
                    placeCount++;
                }
            }
            idx++;
        }
    }
    infile.close();
    return placeCount;
}

第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 OriginalVex(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を作成
    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 idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.start = s;
            if (idx == 1) temp.end = s;
            if (idx == 2) temp.distance = stoi(s, 0, 10);
            idx++;
        }
        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 placeCount;
};
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].placeCount = 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)
{// p1からp2への長さn未満の経路をすべて見つけ、距離順に出力
    int startnum = LocateVex(G, p1);
    int endnum = LocateVex(G, p2);
    if (startnum == ERROR || endnum == ERROR) 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 << OriginalVex(G, startnum) << " ";
        for (int j = 1; paths[i].path[j] != 0; j++) {
            cout << OriginalVex(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 TreeNode {
    string data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode, *Tree;
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];
    else return "";
}

void InitTree(Tree &BT)
{// 二分木の初期化、ルートノードのデータは"植物界"
    BT = new TreeNode;
    BT->left = NULL;
    BT->right = NULL;
    BT->data = "植物界";
}

Tree FindNodeByName(Tree BT, string name)
{// 植物名で再帰的に対応するTreeNodeノードを検索、存在しなければNULLを返す
    if (BT == NULL) return NULL;
    if(BT->data == name) return BT;
    Tree lresult = FindNodeByName(BT->left, name);
    Tree rresult = FindNodeByName(BT->right, name);
    return lresult != NULL ? lresult : rresult;
}

Tree FindFather(Tree BT, string name, Stack& s, string &father)
{// 再帰的に親を探す、スタックsにパスを保存
    if (BT == NULL) return NULL;
    if(BT->data == name) {
        father = GetTop(s);
        return BT;
    }
    Push(s, BT->data);
    Tree lresult = FindFather(BT->left, name, s, father);
    Pop(s);
    Tree rresult = FindFather(BT->right, name, s, father);
    return lresult != NULL ? lresult : rresult;
}

void InsertTNode(Tree& BT, Cata temp){
    TreeNode* new_node = FindNodeByName(BT, temp.father);
    TreeNode* child = new TreeNode;
    child->data = temp.child;
    child->left = NULL;
    child->right = NULL;
    if (new_node->left == NULL) {
        new_node->left = child;
    } else {
        new_node = new_node->left;
        while (new_node->right != NULL) {
            new_node = new_node->right;
        }
        new_node->right = child;
    }
}

void CreateByFile(Tree& 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 idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.child = s;
            if (idx == 1) temp.father = s;
            idx++;
        }
        InsertTNode(BT, temp);
    }
    infile.close();
    return;
}

void FindClass(Tree& BT, string name)
{// 植物名から門、綱、目、科、属の分類情報を出力する
    Stack s;
    InitStack(s);
    string f1, f2, f3, f4, f5, f6;
    FindFather(BT, name, s, f1);
    InitStack(s);
    FindFather(BT, f1, s, f2);
    InitStack(s);
    FindFather(BT, f2, s, f3);
    InitStack(s);
    FindFather(BT, f3, s, f4);
    InitStack(s);
    FindFather(BT, f4, s, f5);
    InitStack(s);
    FindFather(BT, f5, s, f6);
    cout << f1 << " " << f2 << " " << f3 << " " << f4 << " " << f5 << " " << f6 << endl;
    return;
}

第20関：同属植物情報検索

#include<bits/stdc++.h>
#include<stack>
#define OK 1
#define ERROR 0
#define MAXSIZE 6490
using namespace std;
typedef struct TreeNode {
    string data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode, *Tree;
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];
    else return "";
}

void InitTree(Tree &BT) {
    BT = new TreeNode;
    BT->left = NULL;
    BT->right = NULL;
    BT->data = "植物界";
}

Tree FindNodeByName(Tree BT, string name) {
    if (BT == NULL) return NULL;
    if(BT->data == name) return BT;
    Tree lresult = FindNodeByName(BT->left, name);
    Tree rresult = FindNodeByName(BT->right, name);
    return lresult != NULL ? lresult : rresult;
}

Tree FindFather(Tree 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);
    Tree left = FindFather(BT->left, name, s, father);
    Pop(s);
    Tree right = FindFather(BT->right, name, s, father);
    return left != NULL ? left : right;
}

void InsertTNode(Tree& BT, Cata temp) {
    TreeNode* new_node = FindNodeByName(BT, temp.father);
    TreeNode* child = new TreeNode;
    child->data = temp.child;
    child->left = NULL;
    child->right = NULL;
    if (new_node->left == NULL) {
        new_node->left = child;
    } else {
        new_node = new_node->left;
        while (new_node->right != NULL) {
            new_node = new_node->right;
        }
        new_node->right = child;
    }
}

void CreateByFile(Tree& BT, string filename) {
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    while (getline(infile, line)) {
        Cata temp;
        stringstream data(line);
        string s;
        int idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.child = s;
            if (idx == 1) temp.father = s;
            idx++;
        }
        InsertTNode(BT, temp);
    }
    infile.close();
    return;
}

void FindBrother(Tree &BT, string name)
{// 植物名から兄弟情報を出力（空白区切り）
    Stack s;
    InitStack(s);
    string father;
    FindFather(BT, name, s, father);
    TreeNode* 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 TreeNode {
    string data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode, *Tree;
struct Cata {            // 分類定義
    string father;       // 親
    string child;        // 子
};
void InitTree(Tree &BT)
{// 二分木の初期化、ルートノードは"植物界"
    BT = new TreeNode;
    BT->left = NULL;
    BT->right = NULL;
    BT->data = "植物界";
}

Tree FindNodeByName(Tree BT, string name)
{// 名前で再帰的にノードを検索
    if (BT == NULL) return NULL;
    if(BT->data == name) return BT;
    Tree lresult = FindNodeByName(BT->left, name);
    Tree rresult = FindNodeByName(BT->right, name);
    return lresult != NULL ? lresult : rresult;
}

void InsertTNode(Tree& BT, Cata temp){
    TreeNode* parent = FindNodeByName(BT, temp.father);
    TreeNode* child = new TreeNode;
    child->data = temp.child;
    child->left = NULL;
    child->right = NULL;
    if (parent->left == NULL) {
        parent->left = child;
    } else {
        parent = parent->left;
        while (parent->right != NULL) {
            parent = parent->right;
        }
        parent->right = child;
    }
}

void CreateByFile(Tree& BT, string filename)
{// ファイルから木にノードを追加
    ifstream infile;
    infile.open(filename.c_str());
    string line;
    while (getline(infile, line)) {
        Cata temp;
        stringstream data(line);
        string s;
        int idx = 0;
        while (getline(data, s, '#')) {
            if (idx == 0) temp.child = s;
            if (idx == 1) temp.father = s;
            idx++;
        }
        InsertTNode(BT, temp);
    }
    infile.close();
    return;
}

string plantList[6490] = {" "};
int k = 0;

Tree FindSon(Tree &BT){
    if(!BT) return NULL;
    if (BT->left == NULL){
        // リーフであればデータを収集
        Tree temp = BT;
        while(temp){
            plantList[k] = temp->data;
            k++;
            temp = temp->right;
        }
        return BT;
    }
    Tree lresult = FindSon(BT->left);
    Tree rresult = FindSon(BT->right);
    return lresult != NULL ? lresult : rresult;
}

void FindSubLeaf(Tree &BT, string name)
{// 分類詞（門、綱、目、科、属）に基づき、その下位の植物名を出力
    TreeNode *p = FindNodeByName(BT, name);
    p = p->left;
    FindSon(p);
    for(int i = 0; i < k-1; i++){
        cout << plantList[i] << " ";
    }
    cout << plantList[k-1] << endl;
    k = 0;
}

タグ: データ構造 C++ 植物百科 探索 ソート

5月22日 03:00 投稿

ホットタグ

©2026 異端開発室