データ構造実践プロジェクト——データ構造、アルゴリズム、プログラム設計
18786 ワード
【項目1-C/C++言語における関数パラメータ伝達の3つの方式】C言語は、伝達値と伝達アドレスの2つの関数パラメータ伝達方式を提供する.C++では、また参照方式が拡張されています.本プロジェクトを通じて、自分がこの3つの方法の原理を把握していることを確認し、後続の学習のために準備をします.次は、2つの整数変数を交換できるswap関数の3つのバージョンです(カリキュラムのホームページからプロジェクトリンクが見つかり、コピーするとデバッグでき、コードを叩く必要はありません):
次に、main()関数を呼び出します.
3つのプログラムを作成して、それぞれ3つのバージョンの交換関数を呼び出して、結果を観察してください.博文を発表し、プログラムと実行結果を展示し、交換に成功した理由と交換に成功しなかった原因を説明します.呼び出し中の各変数の変化過程を紙に描いてください.自分で説明できないなら、必ず「兄弟」に手伝ってもらい、この小さな山を取ってください.
【項目2−プログラムのマルチファイル組織】学習データ構造は,かなりの規模のプログラムを作成することを目標とする.すべてのコードを1つのファイルに配置する方法は、現段階のニーズには適用できません.このプロジェクトを通して、マルチファイルでプログラムを整理する能力があることを確認します.後で各章では,あるデータ構造についてアルゴリズムライブラリを定義し,アルゴリズムライブラリを参照して実践することができる.最も簡単なマルチファイル組織で、1つのプロジェクトには3つのファイルがあります:(1).hヘッダファイル:データ型の定義、カスタム関数の宣言、マクロの定義など(2).cppソースファイル1:ヘッダファイルに宣言するカスタム関数(3)を実現する.cppソースファイル2:main()関数を定義し、関連関数を呼び出し、問題解決目標を実現する.例1.13でシナリオ3で実装したプログラムを、マルチファイル形式で整理して実行してください.必要な場合は、#includeの「カスタムヘッダファイル」を使用して、ファイル間の内容を「合わせて」タスクを完了させます.うまくできない場合は、「CodeBlocksのプログラムのマルチファイル組織」を参照してください.次はファイルに書かれたプログラムです.
【項目3−体験複雑度】(1)2つのソートアルゴリズムの実行時間ソートはコンピュータ科学における基本的な問題であり,異なる場合に適用するのに適したアルゴリズムが多く発生し,アルゴリズム研究の焦点となっている.本プロジェクトでは,複雑度O(n 2)の選択ソートselectsortと複雑度O(nlogn)の高速ソートquicksortの2つのソートアルゴリズムを提供し,main関数に実行時間の統計を加えた.添付のプログラム1とプログラム2を読んで、10万件近くのデータのファイルを入力データとしてプログラムを実行し、2つのアルゴリズムの実行時間の違いを感じてください.
(2)ハノータにはインドの古い伝説がある.世界の中心部であるベナレス(インド北部)の聖廟には、黄銅板に宝石の針が3本差し込まれている.ヒンドゥー教の主神梵天が世界を創造した時、その中の1本の針に下から上まで大きな64枚の金片を着ていた.これがいわゆるハノータだ.昼も夜も、僧侶が次の法則に従ってこれらの金片を移動しています.一度に1枚だけ移動し、どの針においても、小片は大きな上になければなりません.僧侶たちは、すべての金片が梵天が着た針から別の針に移ると、世界は霹靂の中で消滅し、梵塔、廟宇、衆生も一緒に終わると予言した.皿数がn個の場合、移動する回数はf(n)=2 n−1とすることができる.n=64の場合、1秒ごとに移動すると、18446744073709551615秒が必要になります.平年365日で3153600秒、閏年366日で31622400秒、平均で年間3156952秒、これらの金片を移すには5845.54億年以上かかりますが、地球は現在45億年しか存在しません.太陽系の予想寿命は数百億年と言われています.本当に5845.54億年が過ぎて、太陽系と銀河系は言うまでもなく、少なくとも地球上のすべての生命は、ゴッホ、寺院などとともに、とっくに灰と煙が消えていた.これにより,2 nは桁数的に大きくてたまらない.再帰アルゴリズムを用いてハノータ問題を解き,その複雑さはO(2 n)と求めることができ,指数級のアルゴリズムである.コースのホームページにプログラムをダウンロードして実行してください.ディスク数discCountが4、8、16、20、24の時間の違いを体験してください.どれだけのdiscCountに耐えられますか.ソースプログラムは添付のプログラム3を参照してください.
附:プロジェクト3のプログラム1——複雑度はO(n 2)の選択ソートプログラム実行に必要なデータファイル
添付:プロジェクト3のプログラム2-複雑度O(nlogn)のクイックソートプログラム実行に必要なデータファイル
附:プロジェクト3のプログラム3——ハノータプログラム
//（1）
void myswap(int x, int y)
{
int t;
t=x;
x=y;
y=t;
}//（2）
void myswap(int *p1, int *p2)
{
int t;
t=*p1;
*p1=*p2;
*p2=t;
}//（3）
void myswap(int &x, int &y)
{
int t;
t=x;
x=y;
y=t;
}次に、main()関数を呼び出します.
int main()
{
int a, b;
printf(" ：");
scanf("%d %d", &a, &b);
__________________; // ， myswap
printf(" ：%d %d
", a, b);
return 0;
}3つのプログラムを作成して、それぞれ3つのバージョンの交換関数を呼び出して、結果を観察してください.博文を発表し、プログラムと実行結果を展示し、交換に成功した理由と交換に成功しなかった原因を説明します.呼び出し中の各変数の変化過程を紙に描いてください.自分で説明できないなら、必ず「兄弟」に手伝ってもらい、この小さな山を取ってください.
【項目2−プログラムのマルチファイル組織】学習データ構造は,かなりの規模のプログラムを作成することを目標とする.すべてのコードを1つのファイルに配置する方法は、現段階のニーズには適用できません.このプロジェクトを通して、マルチファイルでプログラムを整理する能力があることを確認します.後で各章では,あるデータ構造についてアルゴリズムライブラリを定義し,アルゴリズムライブラリを参照して実践することができる.最も簡単なマルチファイル組織で、1つのプロジェクトには3つのファイルがあります:(1).hヘッダファイル:データ型の定義、カスタム関数の宣言、マクロの定義など(2).cppソースファイル1:ヘッダファイルに宣言するカスタム関数(3)を実現する.cppソースファイル2:main()関数を定義し、関連関数を呼び出し、問題解決目標を実現する.例1.13でシナリオ3で実装したプログラムを、マルチファイル形式で整理して実行してください.必要な場合は、#includeの「カスタムヘッダファイル」を使用して、ファイル間の内容を「合わせて」タスクを完了させます.うまくできない場合は、「CodeBlocksのプログラムのマルチファイル組織」を参照してください.次はファイルに書かれたプログラムです.
#include if (s2[j].no==i) // i
{
n++;
sum+=s2[j].deg;
}
return(sum/n);
}
double couravg(struct stud2 s2[],int m,int i) // i
{
int j,n=0; //n i
double sum=0; // i
for (j=0; jif (s2[j].cno==i) // i
{
n++;
sum+=s2[j].deg;
}
}
return(sum/n);
}
void allavg(struct stud1 s1[],int n,struct stud2 s2[],int m) //
{
int i,j;
printf(" :
");
printf("
");
i=0;
while (iprintf("%4d %10s %g
",s1[i].no,s1[i].name,studavg(s2,m,j));
i++;
}
printf(" :
");
for (i=1; i<=6; i++)
printf(" %d:%g
",i,couravg(s2,m,i));
}
int main()
{
int n=7; //
int m=21; //
struct stud1 s1[MaxStud]=
{
{1," ",9901},
{8," ",9902},
{34," ",9901},
{20," ",9902},
{12," ",9901},
{26," ",9902},
{5," ",9901}
};
struct stud2 s2[MaxCour]= // 1 6,
{
{1,1,67},
{1,2,98},
{1,4,65},
{8,1,98},
{8,3,90},
{8,6,67},
{34,2,56},
{34,4,65},
{34,6,77},
{20,1,68},
{20,2,92},
{20,3,64},
{12,4,76},
{12,5,75},
{12,6,78},
{26,1,67},
{26,5,78},
{26,6,62},
{5,1,94},
{5,2,92},
{5,6,89}
};
allavg(s1,n,s2,m);
return 0;
} 【項目3−体験複雑度】(1)2つのソートアルゴリズムの実行時間ソートはコンピュータ科学における基本的な問題であり,異なる場合に適用するのに適したアルゴリズムが多く発生し,アルゴリズム研究の焦点となっている.本プロジェクトでは,複雑度O(n 2)の選択ソートselectsortと複雑度O(nlogn)の高速ソートquicksortの2つのソートアルゴリズムを提供し,main関数に実行時間の統計を加えた.添付のプログラム1とプログラム2を読んで、10万件近くのデータのファイルを入力データとしてプログラムを実行し、2つのアルゴリズムの実行時間の違いを感じてください.
(2)ハノータにはインドの古い伝説がある.世界の中心部であるベナレス(インド北部)の聖廟には、黄銅板に宝石の針が3本差し込まれている.ヒンドゥー教の主神梵天が世界を創造した時、その中の1本の針に下から上まで大きな64枚の金片を着ていた.これがいわゆるハノータだ.昼も夜も、僧侶が次の法則に従ってこれらの金片を移動しています.一度に1枚だけ移動し、どの針においても、小片は大きな上になければなりません.僧侶たちは、すべての金片が梵天が着た針から別の針に移ると、世界は霹靂の中で消滅し、梵塔、廟宇、衆生も一緒に終わると予言した.皿数がn個の場合、移動する回数はf(n)=2 n−1とすることができる.n=64の場合、1秒ごとに移動すると、18446744073709551615秒が必要になります.平年365日で3153600秒、閏年366日で31622400秒、平均で年間3156952秒、これらの金片を移すには5845.54億年以上かかりますが、地球は現在45億年しか存在しません.太陽系の予想寿命は数百億年と言われています.本当に5845.54億年が過ぎて、太陽系と銀河系は言うまでもなく、少なくとも地球上のすべての生命は、ゴッホ、寺院などとともに、とっくに灰と煙が消えていた.これにより,2 nは桁数的に大きくてたまらない.再帰アルゴリズムを用いてハノータ問題を解き,その複雑さはO(2 n)と求めることができ,指数級のアルゴリズムである.コースのホームページにプログラムをダウンロードして実行してください.ディスク数discCountが4、8、16、20、24の時間の違いを体験してください.どれだけのdiscCountに耐えられますか.ソースプログラムは添付のプログラム3を参照してください.
附:プロジェクト3のプログラム1——複雑度はO(n 2)の選択ソートプログラム実行に必要なデータファイル
#include
");
exit(1);
}
while(fscanf(fp, "%d", &x[n])!=EOF)
n++;
printf(" ：%d, ....", n);
t1=time(0);
selectsort(x, n);
t2=time(0);
printf(" %d !", (int)(t2-t1));
fclose(fp);
return 0;
}添付:プロジェクト3のプログラム2-複雑度O(nlogn)のクイックソートプログラム実行に必要なデータファイル
#include while(data[i]<=base && i/* */
if(i1);
quicksort(data,i+1,last);
}
int main()
{
int x[MAXNUM];
int n = 0;
double t1,t2;
FILE *fp;
fp = fopen("numbers.txt", "r");
if(fp==NULL)
{
printf(" ！ ， 。
");
exit(1);
}
while(fscanf(fp, "%d", &x[n])!=EOF)
n++;
printf(" ：%d, ....", n);
t1=time(0);
quicksort(x, 0, n-1);
t2=time(0);
printf(" %d !", (int)(t2-t1));
fclose(fp);
return 0;
} 附:プロジェクト3のプログラム3——ハノータプログラム
#include
", discCount, count);
return 0;
}
long move(int n, char A, char B,char C)
{
long c1,c2;
if(n==1)
return 1;
else
{
c1=move(n-1,A,C,B);
c2=move(n-1,B,A,C);
return c1+c2+1;
}
}