(アルゴリズム構造関係）構造のまとめ
データ構造のまとめをしようと思い夏に向けてさまざまな関数や構造を扱うことにする。
1.構造
線形リスト
スタック・キュー（待ち行列）
二分木
2.サーチ
線形探索
二分探索
2文探索木
B木
AVL木
ハッシュ法
3.整列
シンプルソート（バブルソート）
セレクトソート（基本選択法）
インサートソート
シェルソート
クイックソート
ヒープソート
マージソート
ビンソート
ラディクスソート
4.グラフアルゴリズム
グラフの表現法
グラフィックサーチ
連結性
ダイクストラのアルゴリズム
最小木問題
1.構造
手始めにまとめとしてスタック・キューと2分木の表現と走査をする関数一覧
//リストによるスタックの表現
//liststack
#include
struct cell{
double data;
struct cell *next;
};
//initialize stack
struct cell *listhead='\0';
void end(void)
{
stack ='\0';
exit(1);
}
//push stack
void push(double x)
{
struct cell *p;
p=(struct cell *)malloc(sizeof(struct cell));
p->data=x;
p->next=stack;
stack=p;
}
//pop stack
double pop(void)
{
struct cell *p;
double a;
if(stack=='\0')
{
printf("stack is empity.\n");
exit(1);
}
a=stack->data;
p=stack;
stack=stack->next;
free*1;
p->data=a;
p->next=\0;
if(queuehead==\0)
queuehead=p;
else
queuetail->next=p;
queuetail=p;
}
double deq(void){
double a;
struct cell *p;
if(queuehead==\0)
{
printf("queue is empity.\n");
exit(1);
}
a=queuehead->data;
p=queuehead;
queuehead=queuehead->next;
freeSIZE)
tail=1;
count++;
}
double deq(void){
int data;
if(count<=0">*2{
printf("error!\n");
exit(0);
}
data=a[head];
head++;
if(head>SIZE)
head=1;
count--;
}
//続いて2分木
#include
#include
struct node {
char element;
struct node *left;
struct node *right;
};
void preorder(struct node *);
void inorder(struct node *);
void postorder(struct node *);
int main(void)
{
//木の表現
struct node *root;
root=(struct node *)malloc(sizeof(struct node));
root->right=(struct node *)malloc(sizeof(struct node));
root->left=(struct node *)malloc(sizeof(struct node));
root->left->right=(struct node *)malloc(sizeof(struct node));
root->left->left=(struct node *)malloc(sizeof(struct node));
root->right->left=(struct node *)malloc(sizeof(struct node));
root->right->right=(struct node *)malloc(sizeof(struct node));
root->right->right->left=(struct node *)malloc(sizeof(struct node));
root->right->right->right=(struct node *)malloc(sizeof(struct node));
root->left->right->left=NULL;
root->left->right->right=NULL;
root->left->left->right=NULL;
root->left->left->left=NULL;
root->right->left->right=NULL;
root->right->left->left=NULL;
root->right->right->left->left=NULL;
root->right->right->left->right=NULL;
root->right->right->right->right=NULL;
root->right->right->right->left=NULL;
root->element='*';
root->right->element='-';
root->left->element='+';
root->left->right->element='b';
root->left->left->element='a';
root->right->left->element='c';
root->right->right->element='/';
root->right->right->left->element='d';
root->right->right->right->element='e';
printf("prefix notation ===>");
preorder(root);
printf("\n infix notation ===>");
inorder(root);
printf("\n postfix notation ===>");
postorder(root);
putchar('\n');
printf("***** END OF TRAVERSAL *****\n");
return 0;
}
//木の走査を表す関数（前順、間順、後順）
//preoder traversal
void preorder(struct node *p)
{
if(p!=NULL)
{
printf(" %c",p->element);
preorder(p->left);
preorder(p->right);
}
}
//inorder traversal
void inorder(struct node *p)
{
if(p!=NULL)
{
inorder(p->left);
printf(" %c",p->element);
inorder(p->right);
}
}
//postorder traversal
void postorder(struct node *p)
{
if(p!=NULL)
{
postorder(p->left);
postorder(p->right);
printf(" %c",p->element);
}
}
//**参考文献 岩波講座 ソフトウエア科学3（岩波書店）
//アルゴリズムとデータ構造pp26〜pp54
//C言語によるプログラミング応用編（オーム社）
*1:void*)p);
return a;
}
//リスト構造による待ち行列の表現
//listqueue
#include
*2:void*)p); return a; } //リングバッファによる待ち行列の表現 //ringbuffer queue #define SIZE 50 int a[SIZE]; int head,tail,count; void initq(void){ head=0; tail=0; count=0; } void enq(int data){ if(count>=SIZE){ printf("error!\n"); exit(0); } a[tail]=data; tail++; if(tail>SIZE) tail=1; count++; } double deq(void){ int data; if(count<=0
