Freedom Striker

6/16ノート

ヒープソート(Heap Sort)

｢ヒープ｣データ構造

定義→二分木の各節点にデータを保持する
　　　ただし次の条件を満たす
木の形状に関する条件
1.木の高さをｈとするとき、深さｈ－１までの部分は完全二分木
　深さｈの葉は木の左部分に詰められている
要素の大小に関する条件
2.節点ｖの親をuとするとき、それぞれの要素をXv、Xuとすると、次の条件　を満たす　　　Xu＝＜Xv

ヒープソートのアルゴリズム
1.入力された配列Aの要素をヒープの条件を満たすように並び替える。
　ただし大小の定義を逆としてヒープを構成する。
　(ヒープの根に最大要素が入る.　Xu >= Xv　)

2.作成したヒープに対して、DELETEMAX操作をn回適用
　このとき、ヒープ内の最大要素が取り除かれ、配列Aのうしろから前へ並べる
→最終的に元のAのｎ要素が小さいものから順に整列される

→ヒープ再構にかかる時間＝ヒープソートの実行時間
O(logn)×n＝O(nlogn)

デモ
入力データ　７→５→１→２→８→３
段階１:INSERT(大小関係は逆にする、つまり親の方が大きい)

段階２:DELETEMAX(一番大きいものを取り除く)

6/11ノート

バケットソート・基数ソート
要素の値で決まる位置のバケット(入れ物)にその要素を挿入する。


バケットソート … 一桁の整数を整列
基数ソート … バケットソートを繰り返して、k桁の整数を整列

解析適当な仮定(見てすぐに入れ物に入れられること)のもとでn要素をO(n)で整列


バケットソート
入力：要素、整数　０ =< A[i] =< (m-1)←ｍ進数の1桁( 0 =< i =< n-1 )
用意するもの：ｍ個のバケット
　　　B[j]:j=0,1,…,m-1　　　←領域がせまいこと

アルゴリズム
・各要素のA[i]をB[A[i]]に入れる
実現方法：各バケットにはいくつ要素が入るかわからないのでポインタにより実現

・バケットをB[j]；j = m-1,m-2,m-3,…,0の順に操作し、各バケット内の要素を前から順に
配列A[i]のうしろから i = n-1,n-2,n-3,…,0 の順にもどしていく

※もし整列だけでよいのであれば
バケットに何個データが入っているかのみ記憶すればよい

基数ソート(ラディックス(radix)ソート)
入力：要素A[i]が0以上 ｍのk乗以下の整数値
(k桁のｍ進数)ｍ:基数

→各桁ごとにk回のバケットソートを適用するとすべての要素を整列

Lab8：比較を行わないソートアルゴリズム(バケットソート・基数ソート)

※少しバグってます
次の手順で動作するプログラムradix.cを作成し，その動作を確認せよ．

１：まずファイルから保存されているデータ数nを読み込み，その数だけデータを読み込み配列に格納する．ただし，配列は「５桁整数の各桁の数が入る配列」を列挙した配列とせよ（教科書参照）．
２：次に，格納された配列をディスプレイ上に表示する．
３：そして，データが保存された配列について基数ソートを実行する関数 radixsort()を呼び出し，配列データを整列する．
４：最後に，整列された配列をディスプレイ上に表示しプログラムを終了する．

#include
#include
#define N 10000
#define m 10
#define k 5

struct xyz{
int L[k];
};

struct cell{
int id;
struct cell *next;
};

void radixsort(struct xyz *A,int *B,int n);
void bucketsort(struct xyz *A,int *B,int n,int s);
void insert(struct xyz *A,int B,struct cell **C,int s);

int main(void)
{
int i,j,n,a,b;
int B[N];
struct xyz A[N];

FILE *fp;
//ここでファイルを開く
fscanf(fp,"%d",&n);

for(i=0;ifscanf(fp,"%d",&a);
for(j=k-1;j>=0;j--){
b=a%10;
a=(a-b)/10;
A[i].L[j]=b;
}
B[i]=i;
}

printf("整列前\n");

for(i=0;ifor(j=0;jprintf("%d",A[B[i]].L[j]);
printf("\n");
}

printf("\n");

radixsort(A,B,n);

printf("整列後\n");

for(i=0;ifor(j=0;jprintf("%d",A[B[i]].L[j]);
printf("\n");
}

fclose(fp);

return 0;
}

void radixsort(struct xyz *A,int *B,int n)
{
int s;

for(s=k-1;s>=0;s--)
bucketsort(A,B,n,s);

return;

}

void bucketsort(struct xyz *A,int *B,int n,int s)
{
struct cell *C[m];
struct cell *p,*q;
int i,j;
for(j=0;jC[j]=NULL;

for(i=0;iinsert(A,B[i],C,s);

i=n-1;

for(j=m-1;j>=0;j--){
p=C[j];
while(p!=NULL){
B[i]=p->id;
i=i-1;
q=p->next;
free(p);
p=q;
}
}

return;
}

void insert(struct xyz *A,int B,struct cell **C,int s){
struct cell *p;
p=malloc(sizeof(struct cell));
p->id=B;
p->next=C[A[B].L[s]];
C[A[B].L[s]]=p;
return ;
}

/*実行結果
H:\algo>radix.exe
整列前
27446
58007
00103
56548
21869
21538
07867
65552
91919
76211

整列後
00103
07867
21538
21869
27446
56548
58007
65552
76211
91919
*/

Lab7：単純なソートアルゴリズム(挿入ソート)

※文字化けして少しバグってる
次の手順で動作するプログラムinsert.cを作成し，その動作を確認せよ．

１．まずファイルから保存されているデータ数nを読み込み，その数だけデータを読み込み配列に格納する．
２．次に，格納された配列をディスプレイ上に表示する．
３．そして，データが保存された配列について挿入ソートを実行する関数 insertionsort()を呼び出し，配列データを整列する．
４．最後に，整列された配列をディスプレイ上に表示しプログラムを終了する.

#include
#define N 100000

void insertionsort(int k,int *A);

int main(void){

int A[N];
int a,b,i;

FILE *fp;
//ここでファイルを開く
fscanf(fp,"%d",&a);
//scanf("%d",&A[i]);


for(i=0;ifscanf(fp,"%d",&A[i]);
//scanf("%d",&A[i]);


printf("整列前\n");

for(i=0;iprintf("%d\n",A[i]);

printf("\n整列後\n");

insertionsort(a,A);

for(i=0;iprintf("%d\n",A[i]);

fclose(fp);

return 0;
}

void insertionsort(int k,int *A)
{
int i,j;
int tmp;

for (i=1;itmp=A[i];
for(j=i ; j>0&&A[j-1]>tmp ; j--){
A[j]=A[j-1];
}
A[j]=tmp;
}
}

/*実行結果
H:\algo>insert.exe
整列前
27446
58007
103
56548
21869
21538
7867
65552
91919
76211

整列後
103
7867
21538
21869
27446
56548
58007
65552
76211
91919
*/

Lab6：単純なソートアルゴリズム（バブルソート）

※文字化けして少しバグってる
次の手順で動作するプログラムbubble.cを作成し，その動作を確認せよ．

１、まずファイルから保存されているデータ数nを読み込み，その数だけデータを読み込み配列に格納する．
２、次に，格納された配列をディスプレイ上に表示する．
３、そして，データが保存された配列についてバブルソートを実行する関数 bubblesort()を呼び出し，配列データを整列する．
４、最後に，整列された配列をディスプレイ上に表示しプログラムを終了する．

#include
#define N 100000

void bubblesort(int k,int *A);
void swap(int i,int j,int *A);

int main(void){

int A[N];
int a,b,i;

FILE *fp;
//ここでファイルを開き読み込む
fscanf(fp,"%d",&a);

for(i=1;i
fscanf(fp,"%d",&A[i]);

bubblesort(a,A);

for(i=1;i<=a;i++)
printf("%d\n",A[i]);

fclose(fp);

return 0;
}

void bubblesort(int k,int *A)
{
int i,j;
int test;


for(i=0;itest=1;
for(j=k;j>=i+1;j--){
if(A[j]swap(j,j-1,A);
test=0;
}
}
if(test==1)
return;
}

return;
}

void swap(int i,int j,int *A)
{
int temp;

temp=A[i];
A[i]=A[j];
A[j]=temp;

return;
}

/*実行結果
H:\algo>bubble.exe
103
7867
21538
21869
27446
56548
58007
65552
76211
91919
*/

Lab5A(ヒープ)

※文字化けして少しバグってる
まず，ヒープに保存する整数データの個数をキーボードから入力する．
次にデータを１つキーボードから入力する．そして入力された１個のデータをヒープに挿入する関数（insert()）を呼び出しヒープを完成させる．データが１つ挿入されるたびにヒープの状態をディスプレイ上に表示する（表示方法は各自に任せる）．この動作を繰り返し，個数分のデータをすべてヒープに保存する．
個数分のデータが全て入力できたら，ヒープの完成状態（木構造）をディスプレイ上に表示する．
同様に，ヒープ中の最小データを１つずつ取り出す関数（deletemin()）を呼び出し，保存されているデータがなくなるまで個数分だけ繰り返す．データ挿入時と同様にヒープの各状態をディスプレイ上に表示する．

配列にて実現
#include
#include
#define N 500

int deletemin(int *a,int *n);
void downmin(int i,int *a,int n);
void swap(int i,int j,int *a);
void insert(int x,int *a,int *n);
void upmin(int i,int *a,int n);

int A[N];
int a,b,n=0,i,m,temp,j,k;

int main(void)
{
printf("要素の数を入力してください：");
scanf("%d",&a);//要素の数の入力

for(i=0;iprintf("\n要素に数をいれてください：");
scanf("%d",&b);//新しい要素に数を入れる
printf("\ninput:%d",b);
insert(b,A,&n);
printf("\n");

temp=1;

for(j=1;j<=n;j++){
if(temp==j){
if(j!=1)
printf("\n");
temp*=2;
}
printf("%d",A[j-1]);
}
}

while(n>=0){
deletemin(A,&n);
printf("\n");

temp=1;

for(j=1;j<=n;j++){
if(temp==j){
if(j!=1)
printf("\n");
temp*=2;
}
printf("%d",A[j-1]);
}
}

return 0;
}

//ヒープ内の一番小さい数を消す関数
int deletemin(int *A,int *n)
{
int min,n1;

n1=*n;

if(n1<1){
printf("Error: heap is empty.\n");
exit(1);
}

min=A[0];
A[0]=A[n1-1];

if(n1>1)
downmin(0,A,n1-1);

printf("\ndelete:%d",min);

*n=n1-1;

return (min);
}

//木をヒープの順に並び変える関数
void downmin(int i,int *A,int n)
{
int j;

if(i<0 || i>=n){
printf("Illegal element i=%d for n%d\n",i,n);
exit(1);
}

j=2*i+1;

if(j>=n)
return;

if(j+1A[j+1])
j=j+1;

if(A[j]swap(i,j,A);
downmin(j,A,n);
}

return;
}

//配列A[i]とA[j]を入れ替える関数
void swap(int i,int j,int *A)
{
int temp;
temp=A[i];
A[i]=A[j];
A[j]=temp;

return;
}

//木に新しい要素を入れる関数
void insert(int x,int *A,int *n)
{
int n1;

n1=*n;

if(n1>=N){
printf("Error: heap is empty.\n");
exit(1);
}

A[n1]=x;
upmin(n1,A,n1+1);
*n=n1+1;

return;
}

//ヒープの数を比較し、親の方が大きかったとき入れ替える関数
void upmin(int i,int *a,int n)
{
int j;

if(i<0 || i>=n){
printf("Illegal element i=%d for n=%d\n",i,n);
exit(1);
}

if(i==0)
return;

j=(i-1)/2;

if(A[j]>A[i]){
swap(i,j,a);
upmin(j,a,n);
}

return;
}



//実行結果
/*
H:\algo>bcc32 heap1.c
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
heap1.c:
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland

H:\algo>heap1.exe
要素の数を入力してください：10

要素に数をいれてください：8

input:8
8
要素に数をいれてください：4

input:4
4
8
要素に数をいれてください：1

input:1
1
84
要素に数をいれてください：6

input:6
1
64
8
要素に数をいれてください：3

input:3
1
34
86
要素に数をいれてください：7

input:7
1
34
867
要素に数をいれてください：9

input:9
1
34
8679
要素に数をいれてください：0

input:0
0
14
3679
8
要素に数をいれてください：5

input:5
0
14
3679
85
要素に数をいれてください：2

input:2
0
14
3279
856
delete:0
1
24
3679
85
delete:1
2
34
5679
8
delete:2
3
54
8679
delete:3
4
57
869
delete:4
5
67
89
delete:5
6
87
9
delete:6
7
89
delete:7
8
9
delete:8
9
delete:9
Error: heap is empty.
*/

Lab4A(木構造)

10個の整数データを教科書p.42図2.20(a)の木構造に保存するときを考える．まず,教科書p.43図2.21に従って，ポインタにより木を実現し，データを保存せよ．（ファイルからデータを読み込み，木構造ができるようにすると良い）
次に，キーボードから前順，中順，後順を選択する．
すると，その順で木をなぞり，指定した順にデータを表示する（再帰プログラミングで作成せよ）．
#include
#include
#define N 100

struct cell{
int element;
struct cell *next;
};

int root=0,i,n;
struct cell *q,*r,*s,*t,*S[N];

//関数の宣言
void input(void);
void hope(void);
void preorder(int k,struct cell **S);
void postorder(int k,struct cell **S);
void inorder(int k,struct cell **S);

int main(void)
{
input();
hope();

return 0;
}

//木の作成
void input(void)
{

for(i=0;i<10;i++){
S[i]=(struct cell *)malloc(sizeof(struct cell));
S[i]->next=NULL;
S[i]->element=11;
}

for(i=2;i>0;i--){
q=(struct cell *)malloc(sizeof(struct cell));
q->element=i;
q->next=S[root]->next;
S[root]->next=q;
}

for(i=5;i>2;i--){
r=(struct cell *)malloc(sizeof(struct cell));
r->element=i;
r->next=S[1]->next;
S[1]->next=r;
}

for(i=7;i>5;i--){
s=(struct cell *)malloc(sizeof(struct cell));
s->element=i;
s->next=S[2]->next;
S[2]->next=s;
}

for(i=9;i>7;i--){
t=(struct cell *)malloc(sizeof(struct cell));
t->element=i;
t->next=S[6]->next;
S[6]->next=t;
}

return;

}

//操作の決定
void hope(void)
{
printf("次の中から操作するものをえらんでください。\n");
printf("1:前順　2:後順　3:中順　→");
scanf("%d",&n);

switch(n){
case 1:
printf("preorder → ");
preorder(root,S);
break;
case 2:
printf("postorder → ");
postorder(root,S);
break;
case 3:
printf("inorder → ");
inorder(root,S);
break;
}

return;
}

//前順
void preorder(int k,struct cell **S)
{
struct cell *q;

printf("%d",k);
q=S[k];
if(q->element==11)
q=q->next;
while(q != NULL){
preorder(q->element,S);
q=q->next;
}

return;
}

//後順
void postorder(int k,struct cell **S)
{
struct cell *q;

q=S[k];
if(q->element==11)
q=q->next;

while(q != NULL){
postorder(q->element,S);
q=q->next;
}

printf("%d",k);

return;
}

//中順
void inorder(int k,struct cell **S)
{
int count=0;
struct cell *q;

q=S[k];
if(q->element==11)
q=q->next;

while(q != NULL){
inorder(q->element,S);
if(count==0)
printf("%d",k);
q=q->next;
count++;
}

if(count==0)
printf("%d",k);

return;
}


/*実行結果
H:\algo>tree.exe
次の中から操作するものをえらんでください。
1:前順　2:後順　3:中順　→1
preorder → 0134526897
H:\algo>tree.exe
次の中から操作するものをえらんでください。
1:前順　2:後順　3:中順　→2
postorder → 3451896720
H:\algo>tree.exe
次の中から操作するものをえらんでください。
1:前順　2:後順　3:中順　→3
inorder → 3145086927
*/

Lab3A(基本データ構造、リスト・スタック・キュー)

ポインタを用いた線形リストデータ構造を利用して，キーボードから順に入力した複数の整数値（int型）を空の「スタック」および「キュー」にそれぞれ保存し，取り出した時，出力される整数値を順に表示するプログラムを作成し，そのソースファイルを添付せよ．また，次のようにして行った動作確認の結果も報告せよ．
動作確認のために入力する整数値は，各自の学籍番号の数字の部分とせよ（例えばH107123なら，「1→0→7→1→2→3」の順）．また，スタックとキューに保存されているデータがどのような順で出力されるかをそれぞれ表示するようにせよ．（スタックの場合は「3→2→1→7→0→1」の順で出力され，キューの場合は「1→0→7→1→2→3」の順で出力されることを表示させ確認せよ）


#include
#include

typedef struct stack{
int s;
struct stack *next_s;
}STACK;
STACK *top_s = NULL,*bottom_s = NULL,*cell_s;

typedef struct queue{
int q;
struct queue *next_q;
}Queue;
Queue *top_q = NULL,*bottom_q = NULL,*cell_q,*ptr_q;

int i;

//スタックのPUSH
void stack_push(void)
{
printf("学籍番号を入力\n");

for(i=0;i<6;i++){
cell_s = (STACK * )malloc( sizeof(STACK) );
bottom_s = top_s;
cell_s -> next_s = bottom_s;
top_s = cell_s;
scanf("%d",&cell_s -> s);
}
}

//スタックのPOP
void stack_pop(void)
{
for(i=0;i<6;i++){
if(top_s != NULL){
bottom_s = top_s;
top_s = top_s -> next_s;
printf("%d",bottom_s -> s);
free(bottom_s);
}else{
printf("Error\n");
exit(1);
}
}
}

//エンキュー
void enqueue(void)
{
printf("学籍番号を入力\n");

for(i=0;i<6;i++){
cell_q = (Queue *)malloc(sizeof(Queue));
if(bottom_q != NULL){
bottom_q -> next_q = cell_q;
bottom_q = cell_q;
}else if(bottom_q == NULL){
bottom_q = cell_q;
top_q =bottom_q;
}
scanf("%d",&cell_q -> q);
cell_q -> next_q = NULL;
}

}

//デキュー
void dequeue(void)
{
for(i=0;i<6;i++){
Queue *ptr_q;
ptr_q = top_q;
printf("%d",ptr_q -> q);
top_q = ptr_q -> next_q;
free(ptr_q);
}
}


int main(void)
{
int t;
printf("スタックの操作：[1]\nキューの操作：[2]\n");
scanf("%d",&t);
switch(t){
//スタックの操作
case 1:

stack_push();
stack_pop();

break;
//キューの操作
case 2:

enqueue();
dequeue();

break;
}

return 0;
}

/*実行結果
H:\algo\lab1>s_q.exe
スタックの操作：[1]
キューの操作：[2]
1
学籍番号を入力
1
0
7
0
0
0
000701
H:\algo\lab1>s_q.exe
スタックの操作：[1]
キューの操作：[2]
2
学籍番号を入力
1
0
7
0
0
0
107000
*/

放置プレイしてたよ。

なんか久しぶりに書いて見ますよっとｗ



最近は大学のレポートやらなんやらが忙しくて遊ぶ暇が無いんですけどー


暇な時はサドンアタックってFPSをやってますよｗ






気になる人は試しにやってみるといいでしょうｗ










まぁ書くこともないんでー









ﾉｼ

オーラなんとかかんとか

とりあえずイベントだったんで打ってきましたｗ




まぁ昼から行ったんでハイスペック機はあいてませんでしたｗｗｗ











でもミドルスペックのルパンに人がいないので、全台アツイイベントなので1個だけ回してない台があったのでうってみることにしたんですが・・・































千円で1100枚以上でちゃいましたｗｗｗｗｗｗｗｗｗ













開始3分でノーマルＢＩＧ引いて札刺さっちゃいましたｗ













4日連続のイベントなんでここはミドルスペック狙いでいってみようかと思います。






明日も昼まで学校ですからねｗ














でわでわｗ










今日の収支　ルパン　＋20600円　　（6枚交換）