データ構造とアルゴリズム(Cコード実装)
879902 ワード
コードディレクトリ:第3章リニアテーブル 01リニアテーブル順序格納_List リニア時計チェーン式記憶_Link List 静的チェーン_Static Link List 第4章スタックとキュー 01シーケンススタック_Stock 二スタックの共有空間_DoubleStock 03チェーンスタック_LinkStock フィボナッチ関数_Fibonacci 05順番待ち行列_Queue 06チェーン列_LinkQue 第5章串 01串_String モードマッチング_KMP 第6章ツリー 01二叉樹順構造を実現しました.BiTreeAray 02二叉木チェーン構造の実現BiTreeLink 手がかり二叉樹_ThreadBinaryTree 第7章図 隣接マトリクス作成_CreateMGraph 隣接表作成_CreateALGraph 03隣接マトリックス深さと広さはDFS_を巡回する.BFS 04隣接テーブル深さと広さはDFS_を巡回する.BFS 05最小生成樹_Prim 06最小生成樹_Kruskyal 07最短経路_Dijkstra 08最短経路_Floyd 09トポロジ並べ替え_Topological Sort 10キーパス_CriticalPath 第8章検索 静的検索_Search 02二叉並び替えツリー_BinarySortTree 03バランス二叉樹_AVLTRE 04 B樹_BTree 05散リスト_hashTable 第9章ランキング 1並べ替え_ソト 第3章リニアテーブル
01リニアテーブル順記憶_List
01シーケンススタック_Stock
01_String
01二叉樹順構造実現_BiTreeAray
01隣接マトリクス作成_CreateMGraph
01静的検索_Search
01ソート_ソトこれは「大話データ構造」の本のノートです. 文章は長すぎます.何を使って検索すればいいですか? 部分の重要な知識点は徐々に更新されます. ソースリンク(本人は学習用だけです.転載は元の作者を明記してください.私ではありません.)
01リニアテーブル順記憶_List
//01 _List
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* */
typedef int Status; /* Status , ， OK */
typedef int ElemType; /* ElemType ， int */
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
typedef struct
{
ElemType data[MAXSIZE]; /* ， */
int length; /* */
}SqList;
/* */
Status InitList(SqList *L)
{
L->length=0;
return OK;
}
/* ： L 。 ： L ， TRUE， FALSE */
Status ListEmpty(SqList L)
{
if(L.length==0)
return TRUE;
else
return FALSE;
}
/* ： L 。 ： L */
Status ClearList(SqList *L)
{
L->length=0;
return OK;
}
/* ： L 。 ： L */
int ListLength(SqList L)
{
return L.length;
}
/* ： L ，1≤i≤ListLength(L) */
/* ： e L i , i ， 1 0 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}
/* ： L */
/* ： L 1 e 。 */
/* ， 0 */
int LocateElem(SqList L,ElemType e)
{
int i;
if (L.length==0)
return 0;
for(i=0;i<L.length;i++)
{
if (L.data[i]==e)
break;
}
if(i>=L.length)
return 0;
return i+1;
}
/* ： L ,1≤i≤ListLength(L)， */
/* ： L i e，L 1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length==MAXSIZE) /* */
return ERROR;
if (i<1 || i>L->length+1)/* i */
return ERROR;
if (i<=L->length) /* */
{
for(k=L->length-1;k>=i-1;k--) /* */
L->data[k+1]=L->data[k];
}
L->data[i-1]=e; /* */
L->length++;
return OK;
}
/* ： L ，1≤i≤ListLength(L) */
/* ： L i ， e ，L 1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length==0) /* */
return ERROR;
if (i<1 || i>L->length) /* */
return ERROR;
*e=L->data[i-1];
if (i<L->length) /* */
{
for(k=i;k<L->length;k++)/* */
L->data[k-1]=L->data[k];
}
L->length--;
return OK;
}
/* ： L */
/* ： L */
Status ListTraverse(SqList L)
{
int i;
for(i=0;i<L.length;i++)
visit(L.data[i]);
printf("
");
return OK;
}
void unionL(SqList *La,SqList Lb)
{
int La_len,Lb_len,i;
ElemType e;
La_len=ListLength(*La);
Lb_len=ListLength(Lb);
for (i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,&e);
if (!LocateElem(*La,e))
ListInsert(La,++La_len,e);
}
}
int main()
{
SqList L;
SqList Lb;
ElemType e;
Status i;
int j,k;
i=InitList(&L);
printf(" L ：L.length=%d
",L.length);
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf(" L 1～5 ：L.data=");
ListTraverse(L);
printf("L.length=%d
",L.length);
i=ListEmpty(L);
printf("L ：i=%d(1: 0: )
",i);
i=ClearList(&L);
printf(" L ：L.length=%d
",L.length);
i=ListEmpty(L);
printf("L ：i=%d(1: 0: )
",i);
for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf(" L 1～10 ：L.data=");
ListTraverse(L);
printf("L.length=%d
",L.length);
ListInsert(&L,1,0);
printf(" L 0 ：L.data=");
ListTraverse(L);
printf("L.length=%d
",L.length);
GetElem(L,5,&e);
printf(" 5 ：%d
",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j);
if(k)
printf(" %d %d
",k,j);
else
printf(" %d
",j);
}
k=ListLength(L); /* k */
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e); /* j */
if(i==ERROR)
printf(" %d
",j);
else
printf(" %d ：%d
",j,e);
}
printf(" L ：");
ListTraverse(L);
j=5;
ListDelete(&L,j,&e); /* 5 */
printf(" %d ：%d
",j,e);
printf(" L ：");
ListTraverse(L);
// 10 Lb
i=InitList(&Lb);
for(j=6;j<=15;j++)
i=ListInsert(&Lb,1,j);
unionL(&L,Lb);
printf(" Lb L ：");
ListTraverse(L);
return 0;
}
//02 _LinkList
#include "stdio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* */
typedef int Status;/* Status , ， OK */
typedef int ElemType;/* ElemType ， int */
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; /* LinkList */
/* */
Status InitList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node)); /* , L */
if(!(*L)) /* */
return ERROR;
(*L)->next=NULL; /* */
return OK;
}
/* ： L 。 ： L ， TRUE， FALSE */
Status ListEmpty(LinkList L)
{
if(L->next)
return FALSE;
else
return TRUE;
}
/* ： L 。 ： L */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next; /* p */
while(p) /* */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL; /* */
return OK;
}
/* ： L 。 ： L */
int ListLength(LinkList L)
{
int i=0;
LinkList p=L->next; /* p */
while(p)
{
i++;
p=p->next;
}
return i;
}
/* ： L ，1≤i≤ListLength(L) */
/* ： e L i */
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p; /* p */
p = L->next; /* p L */
j = 1; /* j */
while (p && j<i) /* p j i ， */
{
p = p->next; /* p */
++j;
}
if ( !p || j>i )
return ERROR; /* i */
*e = p->data; /* i */
return OK;
}
/* ： L */
/* ： L 1 e 。 */
/* ， 0 */
int LocateElem(LinkList L,ElemType e)
{
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(p->data==e) /* */
return i;
p=p->next;
}
return 0;
}
/* ： L ,1≤i≤ListLength(L)， */
/* ： L i e，L 1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = *L;
j = 1;
while (p && j < i) /* i */
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR; /* i */
s = (LinkList)malloc(sizeof(Node)); /* (C ) */
s->data = e;
s->next = p->next; /* p s */
p->next = s; /* s p */
return OK;
}
/* ： L ，1≤i≤ListLength(L) */
/* ： L i ， e ，L 1 */
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j;
LinkList p,q;
p = *L;
j = 1;
while (p->next && j < i) /* i */
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR; /* i */
q = p->next;
p->next = q->next; /* q p */
*e = q->data; /* q e */
free(q); /* ， */
return OK;
}
/* ： L */
/* ： L */
Status ListTraverse(LinkList L)
{
LinkList p=L->next;
while(p)
{
visit(p->data);
p=p->next;
}
printf("
");
return OK;
}
/* n ， L（ ） */
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand(time(0)); /* */
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL; /* */
for (i=0; i<n; i++)
{
p = (LinkList)malloc(sizeof(Node)); /* */
p->data = rand()%100+1; /* 100 */
p->next = (*L)->next;
(*L)->next = p; /* */
}
}
/* n ， L（ ） */
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
srand(time(0)); /* */
*L = (LinkList)malloc(sizeof(Node)); /* L */
r=*L; /* r */
for (i=0; i<n; i++)
{
p = (Node *)malloc(sizeof(Node)); /* */
p->data = rand()%100+1; /* 100 */
r->next=p; /* */
r = p; /* */
}
r->next = NULL; /* */
}
int main()
{
LinkList L;
ElemType e;
Status i;
int j,k;
i=InitList(&L);
printf(" L ：ListLength(L)=%d
",ListLength(L));
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf(" L 1～5 ：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d
",ListLength(L));
i=ListEmpty(L);
printf("L ：i=%d(1: 0: )
",i);
i=ClearList(&L);
printf(" L ：ListLength(L)=%d
",ListLength(L));
i=ListEmpty(L);
printf("L ：i=%d(1: 0: )
",i);
for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf(" L 1～10 ：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d
",ListLength(L));
ListInsert(&L,1,0);
printf(" L 0 ：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d
",ListLength(L));
GetElem(L,5,&e);
printf(" 5 ：%d
",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j);
if(k)
printf(" %d %d
",k,j);
else
printf(" %d
",j);
}
k=ListLength(L); /* k */
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e); /* j */
if(i==ERROR)
printf(" %d
",j);
else
printf(" %d ：%d
",j,e);
}
printf(" L ：");
ListTraverse(L);
j=5;
ListDelete(&L,j,&e); /* 5 */
printf(" %d ：%d
",j,e);
printf(" L ：");
ListTraverse(L);
i=ClearList(&L);
printf("
L ：ListLength(L)=%d
",ListLength(L));
CreateListHead(&L,20);
printf(" L ( )：");
ListTraverse(L);
i=ClearList(&L);
printf("
L ：ListLength(L)=%d
",ListLength(L));
CreateListTail(&L,20);
printf(" L ( )：");
ListTraverse(L);
return 0;
}
//03 _StaticLinkList
#include "string.h"
#include "ctype.h"
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 1000 /* */
typedef int Status; /* Status , ， OK */
typedef char ElemType; /* ElemType ， char */
Status visit(ElemType c)
{
printf("%c ",c);
return OK;
}
/* */
typedef struct
{
ElemType data;
int cur; /* (Cursor) ， 0 */
} Component,StaticLinkList[MAXSIZE];
/* space ，space[0].cur ，"0" */
Status InitList(StaticLinkList space)
{
int i;
for (i=0; i<MAXSIZE-1; i++)
space[i].cur = i+1;
space[MAXSIZE-1].cur = 0; /* ， cur 0 */
return OK;
}
/* ， ， 0 */
int Malloc_SSL(StaticLinkList space)
{
int i = space[0].cur; /* cur */
/* */
if (space[0]. cur)
space[0]. cur = space[i].cur; /* ， */
/* */
/* */
return i;
}
/* k */
void Free_SSL(StaticLinkList space, int k)
{
space[k].cur = space[0].cur; /* cur cur */
space[0].cur = k; /* cur */
}
/* ： L 。 ： L */
int ListLength(StaticLinkList L)
{
int j=0;
int i=L[MAXSIZE-1].cur;
while(i)
{
i=L[i].cur;
j++;
}
return j;
}
/* L i e */
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
int j, k, l;
k = MAXSIZE - 1; /* k */
if (i < 1 || i > ListLength(L) + 1)
return ERROR;
j = Malloc_SSL(L); /* */
if (j)
{
L[j].data = e; /* data */
for(l = 1; l <= i - 1; l++) /* i */
k = L[k].cur;
L[j].cur = L[k].cur; /* i cur cur */
L[k].cur = j; /* i ur */
return OK;
}
return ERROR;
}
/* L i */
Status ListDelete(StaticLinkList L, int i)
{
int j, k;
if (i < 1 || i > ListLength(L))
return ERROR;
k = MAXSIZE - 1;
for (j = 1; j <= i - 1; j++)
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[j].cur;
Free_SSL(L, j);
return OK;
}
Status ListTraverse(StaticLinkList L)
{
int j=0;
int i=L[MAXSIZE-1].cur;
while(i)
{
visit(L[i].data);
i=L[i].cur;
j++;
}
return j;
printf("
");
return OK;
}
int main()
{
StaticLinkList L;
Status i;
i=InitList(L);
printf(" L ：L.length=%d
",ListLength(L));
i=ListInsert(L,1,'F');
i=ListInsert(L,1,'E');
i=ListInsert(L,1,'D');
i=ListInsert(L,1,'B');
i=ListInsert(L,1,'A');
printf("
L FEDBA ：
L.data=");
ListTraverse(L);
i=ListInsert(L,3,'C');
printf("
L “B” “D” “C” ：
L.data=");
ListTraverse(L);
i=ListDelete(L,1);
printf("
L “A” ：
L.data=");
ListTraverse(L);
printf("
");
return 0;
}
01シーケンススタック_Stock
//01 _Stack
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* */
typedef int Status;
typedef int SElemType; /* SElemType ， int */
/* */
typedef struct
{
SElemType data[MAXSIZE];
int top; /* */
}SqStack;
Status visit(SElemType c)
{
printf("%d ",c);
return OK;
}
/* S */
Status InitStack(SqStack *S)
{
/* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */
S->top=-1;
return OK;
}
/* S */
Status ClearStack(SqStack *S)
{
S->top=-1;
return OK;
}
/* S ， TRUE， FALSE */
Status StackEmpty(SqStack S)
{
if (S.top==-1)
return TRUE;
else
return FALSE;
}
/* S ， */
int StackLength(SqStack S)
{
return S.top+1;
}
/* ， e S ， OK； ERROR */
Status GetTop(SqStack S,SElemType *e)
{
if (S.top==-1)
return ERROR;
else
*e=S.data[S.top];
return OK;
}
/* e */
Status Push(SqStack *S,SElemType e)
{
if(S->top == MAXSIZE -1) /* */
{
return ERROR;
}
S->top++; /* */
S->data[S->top]=e; /* */
return OK;
}
/* ， S ， e ， OK； ERROR */
Status Pop(SqStack *S,SElemType *e)
{
if(S->top==-1)
return ERROR;
*e=S->data[S->top]; /* e */
S->top--; /* */
return OK;
}
/* */
Status StackTraverse(SqStack S)
{
int i;
i=0;
while(i<=S.top)
{
visit(S.data[i++]);
}
printf("
");
return OK;
}
int main()
{
int j;
SqStack s;
int e;
if(InitStack(&s)==OK)
for(j=1;j<=10;j++)
Push(&s,j);
printf(" ：");
StackTraverse(s);
Pop(&s,&e);
printf(" e=%d
",e);
printf(" ：%d(1: 0: )
",StackEmpty(s));
GetTop(s,&e);
printf(" e=%d %d
",e,StackLength(s));
ClearStack(&s);
printf(" ， ：%d(1: 0: )
",StackEmpty(s));
return 0;
}
//02 _DoubleStack
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* */
typedef int Status;
typedef int SElemType; /* SElemType ， int */
/* */
typedef struct
{
SElemType data[MAXSIZE];
int top1; /* 1 */
int top2; /* 2 */
}SqDoubleStack;
Status visit(SElemType c)
{
printf("%d ",c);
return OK;
}
/* S */
Status InitStack(SqDoubleStack *S)
{
S->top1=-1;
S->top2=MAXSIZE;
return OK;
}
/* S */
Status ClearStack(SqDoubleStack *S)
{
S->top1=-1;
S->top2=MAXSIZE;
return OK;
}
/* S ， TRUE， FALSE */
Status StackEmpty(SqDoubleStack S)
{
if (S.top1==-1 && S.top2==MAXSIZE)
return TRUE;
else
return FALSE;
}
/* S ， */
int StackLength(SqDoubleStack S)
{
return (S.top1+1)+(MAXSIZE-S.top2);
}
/* e */
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
if (S->top1+1==S->top2) /* ， push */
return ERROR;
if (stackNumber==1) /* 1 */
S->data[++S->top1]=e; /* 1 top1+1 。 */
else if (stackNumber==2) /* 2 */
S->data[--S->top2]=e; /* 2 top2-1 。 */
return OK;
}
/* ， S ， e ， OK； ERROR */
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{
if (stackNumber==1)
{
if (S->top1==-1)
return ERROR; /* 1 ， */
*e=S->data[S->top1--]; /* 1 */
}
else if (stackNumber==2)
{
if (S->top2==MAXSIZE)
return ERROR; /* 2 ， */
*e=S->data[S->top2++]; /* 2 */
}
return OK;
}
Status StackTraverse(SqDoubleStack S)
{
int i;
i=0;
while(i<=S.top1)
{
visit(S.data[i++]);
}
i=S.top2;
while(i<MAXSIZE)
{
visit(S.data[i++]);
}
printf("
");
return OK;
}
int main()
{
int j;
SqDoubleStack s;
int e;
if(InitStack(&s)==OK)
{
for(j=1;j<=5;j++)
Push(&s,j,1);
for(j=MAXSIZE;j>=MAXSIZE-2;j--)
Push(&s,j,2);
}
printf(" ：");
StackTraverse(s);
printf(" ：%d
",StackLength(s));
Pop(&s,&e,2);
printf(" e=%d
",e);
printf(" ：%d(1: 0: )
",StackEmpty(s));
for(j=6;j<=MAXSIZE-2;j++)
Push(&s,j,1);
printf(" ：");
StackTraverse(s);
printf(" ：%d(1: 0: )
",Push(&s,100,1));
ClearStack(&s);
printf(" ， ：%d(1: 0: )
",StackEmpty(s));
return 0;
}
//03 _LinkStack
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* */
typedef int Status;
typedef int SElemType; /* SElemType ， int */
/* */
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct
{
LinkStackPtr top;
int count;
}LinkStack;
Status visit(SElemType c)
{
printf("%d ",c);
return OK;
}
/* S */
Status InitStack(LinkStack *S)
{
S->top = (LinkStackPtr)malloc(sizeof(StackNode));
if(!S->top)
return ERROR;
S->top=NULL;
S->count=0;
return OK;
}
/* S */
Status ClearStack(LinkStack *S)
{
LinkStackPtr p,q;
p=S->top;
while(p)
{
q=p;
p=p->next;
free(q);
}
S->count=0;
return OK;
}
/* S ， TRUE， FALSE */
Status StackEmpty(LinkStack S)
{
if (S.count==0)
return TRUE;
else
return FALSE;
}
/* S ， */
int StackLength(LinkStack S)
{
return S.count;
}
/* ， e S ， OK； ERROR */
Status GetTop(LinkStack S,SElemType *e)
{
if (S.top==NULL)
return ERROR;
else
*e=S.top->data;
return OK;
}
/* e */
Status Push(LinkStack *S,SElemType e)
{
LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
s->data=e;
s->next=S->top; /* ， ① */
S->top=s; /* s ， ② */
S->count++;
return OK;
}
/* ， S ， e ， OK； ERROR */
Status Pop(LinkStack *S,SElemType *e)
{
LinkStackPtr p;
if(StackEmpty(*S))
return ERROR;
*e=S->top->data;
p=S->top; /* p， ③ */
S->top=S->top->next; /* ， ， ④ */
free(p); /* p */
S->count--;
return OK;
}
Status StackTraverse(LinkStack S)
{
LinkStackPtr p;
p=S.top;
while(p)
{
visit(p->data);
p=p->next;
}
printf("
");
return OK;
}
int main()
{
int j;
LinkStack s;
int e;
if(InitStack(&s)==OK)
for(j=1;j<=10;j++)
Push(&s,j);
printf(" ：");
StackTraverse(s);
Pop(&s,&e);
printf(" e=%d
",e);
printf(" ：%d(1: 0: )
",StackEmpty(s));
GetTop(s,&e);
printf(" e=%d %d
",e,StackLength(s));
ClearStack(&s);
printf(" ， ：%d(1: 0: )
",StackEmpty(s));
return 0;
}
//04 _Fibonacci
#include "stdio.h"
int Fbi(int i) /* */
{
if( i < 2 )
return i == 0 ? 0 : 1;
return Fbi(i - 1) + Fbi(i - 2); /* Fbi ， */
}
int main()
{
int i;
int a[40];
printf(" ：
");
a[0]=0;
a[1]=1;
printf("%d ",a[0]);
printf("%d ",a[1]);
for(i = 2;i < 40;i++)
{
a[i] = a[i-1] + a[i-2];
printf("%d ",a[i]);
}
printf("
");
printf(" ：
");
for(i = 0;i < 40;i++)
printf("%d ", Fbi(i));
return 0;
}
//05 _Queue
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* */
typedef int Status;
typedef int QElemType; /* QElemType ， int */
/* */
typedef struct
{
QElemType data[MAXSIZE];
int front; /* */
int rear; /* ， ， */
}SqQueue;
Status visit(QElemType c)
{
printf("%d ",c);
return OK;
}
/* Q */
Status InitQueue(SqQueue *Q)
{
Q->front=0;
Q->rear=0;
return OK;
}
/* Q */
Status ClearQueue(SqQueue *Q)
{
Q->front=Q->rear=0;
return OK;
}
/* Q , TRUE, FALSE */
Status QueueEmpty(SqQueue Q)
{
if(Q.front==Q.rear) /* */
return TRUE;
else
return FALSE;
}
/* Q ， */
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
/* , e Q , OK, ERROR */
Status GetHead(SqQueue Q,QElemType *e)
{
if(Q.front==Q.rear) /* */
return ERROR;
*e=Q.data[Q.front];
return OK;
}
/* ， e Q */
Status EnQueue(SqQueue *Q,QElemType e)
{
if ((Q->rear+1)%MAXSIZE == Q->front) /* */
return ERROR;
Q->data[Q->rear]=e; /* e */
Q->rear=(Q->rear+1)%MAXSIZE;/* rear ， */
/* */
return OK;
}
/* ， Q ， e */
Status DeQueue(SqQueue *Q,QElemType *e)
{
if (Q->front == Q->rear) /* */
return ERROR;
*e=Q->data[Q->front]; /* e */
Q->front=(Q->front+1)%MAXSIZE; /* front ， */
/* */
return OK;
}
/* Q */
Status QueueTraverse(SqQueue Q)
{
int i;
i=Q.front;
while((i+Q.front)!=Q.rear)
{
visit(Q.data[i]);
i=(i+1)%MAXSIZE;
}
printf("
");
return OK;
}
int main()
{
Status j;
int i=0,l;
QElemType d;
SqQueue Q;
InitQueue(&Q);
printf(" ， ？%u(1: 0: )
",QueueEmpty(Q));
printf(" ( %d ),-1 : ",MAXSIZE-1);
do
{
/* scanf("%d",&d); */
d=i+100;
if(d==-1)
break;
i++;
EnQueue(&Q,d);
}while(i<MAXSIZE-1);
printf(" : %d
",QueueLength(Q));
printf(" ？%u(1: 0: )
",QueueEmpty(Q));
printf(" %d , :
",MAXSIZE);
for(l=1;l<=MAXSIZE;l++)
{
DeQueue(&Q,&d);
printf(" %d, :%d
",d,l+1000);
/* scanf("%d",&d); */
d=l+1000;
EnQueue(&Q,d);
}
l=QueueLength(Q);
printf(" :
");
QueueTraverse(Q);
printf(" %d
",i+MAXSIZE);
if(l-2>0)
printf(" %d :
",l-2);
while(QueueLength(Q)>2)
{
DeQueue(&Q,&d);
printf(" %d
",d);
}
j=GetHead(Q,&d);
if(j)
printf(" : %d
",d);
ClearQueue(&Q);
printf(" , ？%u(1: 0: )
",QueueEmpty(Q));
return 0;
}
//06 _LinkQueue
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* */
typedef int Status;
typedef int QElemType; /* QElemType ， int */
typedef struct QNode /* */
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct /* */
{
QueuePtr front,rear; /* 、 */
}LinkQueue;
Status visit(QElemType c)
{
printf("%d ",c);
return OK;
}
/* Q */
Status InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q->front)
exit(OVERFLOW);
Q->front->next=NULL;
return OK;
}
/* Q */
Status DestroyQueue(LinkQueue *Q)
{
while(Q->front)
{
Q->rear=Q->front->next;
free(Q->front);
Q->front=Q->rear;
}
return OK;
}
/* Q */
Status ClearQueue(LinkQueue *Q)
{
QueuePtr p,q;
Q->rear=Q->front;
p=Q->front->next;
Q->front->next=NULL;
while(p)
{
q=p;
p=p->next;
free(q);
}
return OK;
}
/* Q , TRUE, FALSE */
Status QueueEmpty(LinkQueue Q)
{
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}
/* */
int QueueLength(LinkQueue Q)
{
int i=0;
QueuePtr p;
p=Q.front;
while(Q.rear!=p)
{
i++;
p=p->next;
}
return i;
}
/* , e Q , OK, ERROR */
Status GetHead(LinkQueue Q,QElemType *e)
{
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
*e=p->data;
return OK;
}
/* e Q */
Status EnQueue(LinkQueue *Q,QElemType e)
{
QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
if(!s) /* */
exit(OVERFLOW);
s->data=e;
s->next=NULL;
Q->rear->next=s; /* e s ， ① */
Q->rear=s; /* s ，rear s， ② */
return OK;
}
/* , Q , e , OK, ERROR */
Status DeQueue(LinkQueue *Q,QElemType *e)
{
QueuePtr p;
if(Q->front==Q->rear)
return ERROR;
p=Q->front->next; /* p， ① */
*e=p->data; /* e */
Q->front->next=p->next;/* p->next ， ② */
if(Q->rear==p) /* ， rear ， ③ */
Q->rear=Q->front;
free(p);
return OK;
}
/* Q */
Status QueueTraverse(LinkQueue Q)
{
QueuePtr p;
p=Q.front->next;
while(p)
{
visit(p->data);
p=p->next;
}
printf("
");
return OK;
}
int main()
{
int i;
QElemType d;
LinkQueue q;
i=InitQueue(&q);
if(i)
printf(" !
");
printf(" ？%d(1: 0: ) ",QueueEmpty(q));
printf(" %d
",QueueLength(q));
EnQueue(&q,-5);
EnQueue(&q,5);
EnQueue(&q,10);
printf(" 3 (-5,5,10) , %d
",QueueLength(q));
printf(" ？%d(1: 0: ) ",QueueEmpty(q));
printf(" ：");
QueueTraverse(q);
i=GetHead(q,&d);
if(i==OK)
printf(" ：%d
",d);
DeQueue(&q,&d);
printf(" %d
",d);
i=GetHead(q,&d);
if(i==OK)
printf(" ：%d
",d);
ClearQueue(&q);
printf(" ,q.front=%u q.rear=%u q.front->next=%u
",q.front,q.rear,q.front->next);
DestroyQueue(&q);
printf(" ,q.front=%u q.rear=%u
",q.front, q.rear);
return 0;
}
01_String
//01 _String
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 40 /* */
typedef int Status; /* Status , ， OK */
typedef int ElemType; /* ElemType ， int */
typedef char String[MAXSIZE+1]; /* 0 */
/* chars T */
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
/* S T */
Status StrCopy(String T,String S)
{
int i;
for(i=0;i<=S[0];i++)
T[i]=S[i];
return OK;
}
/* S , TRUE, FALSE */
Status StrEmpty(String S)
{
if(S[0]==0)
return TRUE;
else
return FALSE;
}
/* : S T */
/* : S>T, >0; S=T, =0; S
int StrCompare(String S,String T)
{
int i;
for(i=1;i<=S[0]&&i<=T[0];++i)
if(S[i]!=T[i])
return S[i]-T[i];
return S[0]-T[0];
}
/* */
int StrLength(String S)
{
return S[0];
}
/* : S 。 : S */
Status ClearString(String S)
{
S[0]=0;/* */
return OK;
}
/* T S1 S2 。 ， TRUE， FALSE */
Status Concat(String T,String S1,String S2)
{
int i;
if(S1[0]+S2[0]<=MAXSIZE)
{ /* */
for(i=1;i<=S1[0];i++)
T[i]=S1[i];
for(i=1;i<=S2[0];i++)
T[S1[0]+i]=S2[i];
T[0]=S1[0]+S2[0];
return TRUE;
}
else
{ /* S2 */
for(i=1;i<=S1[0];i++)
T[i]=S1[i];
for(i=1;i<=MAXSIZE-S1[0];i++)
T[S1[0]+i]=S2[i];
T[0]=MAXSIZE;
return FALSE;
}
}
/* Sub S pos len 。 */
Status SubString(String Sub,String S,int pos,int len)
{
int i;
if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)
return ERROR;
for(i=1;i<=len;i++)
Sub[i]=S[pos+i-1];
Sub[0]=len;
return OK;
}
/* T S pos 。 , 0。 */
/* ,T ,1≤pos≤StrLength(S)。 */
int Index(String S, String T, int pos)
{
int i = pos; /* i S ， pos 1， pos */
int j = 1; /* j T */
while (i <= S[0] && j <= T[0]) /* i S j T ， */
{
if (S[i] == T[j]) /* */
{
++i;
++j;
}
else /* */
{
i = i-j+2; /* i */
j = 1; /* j T */
}
}
if (j > T[0])
return i-T[0];
else
return 0;
}
/* T 。 S pos T ， */
/* S ， 0 */
int Index2(String S, String T, int pos)
{
int n,m,i;
String sub;
if (pos > 0)
{
n = StrLength(S); /* S */
m = StrLength(T); /* T */
i = pos;
while (i <= n-m+1)
{
SubString (sub, S, i, m); /* i T sub */
if (StrCompare(sub,T) != 0) /* */
++i;
else /* */
return i; /* i */
}
}
return 0; /* T ， 0 */
}
/* : S T ,1≤pos≤StrLength(S)+1 */
/* : S pos T。 TRUE, FALSE */
Status StrInsert(String S,int pos,String T)
{
int i;
if(pos<1||pos>S[0]+1)
return ERROR;
if(S[0]+T[0]<=MAXSIZE)
{ /* */
for(i=S[0];i>=pos;i--)
S[i+T[0]]=S[i];
for(i=pos;i<pos+T[0];i++)
S[i]=T[i-pos+1];
S[0]=S[0]+T[0];
return TRUE;
}
else
{ /* */
for(i=MAXSIZE;i<=pos;i--)
S[i]=S[i-T[0]];
for(i=pos;i<pos+T[0];i++)
S[i]=T[i-pos+1];
S[0]=MAXSIZE;
return FALSE;
}
}
/* : S ,1≤pos≤StrLength(S)-len+1 */
/* : S pos len */
Status StrDelete(String S,int pos,int len)
{
int i;
if(pos<1||pos>S[0]-len+1||len<0)
return ERROR;
for(i=pos+len;i<=S[0];i++)
S[i-len]=S[i];
S[0]-=len;
return OK;
}
/* : S,T V ,T （ ） */
/* : V S T */
Status Replace(String S,String T,String V)
{
int i=1; /* S T */
if(StrEmpty(T)) /* T */
return ERROR;
do
{
i=Index(S,T,i); /* i i T */
if(i) /* S T */
{
StrDelete(S,i,StrLength(T)); /* T */
StrInsert(S,i,V); /* T V */
i+=StrLength(V); /* V T */
}
}while(i);
return OK;
}
/* T */
void StrPrint(String T)
{
int i;
for(i=1;i<=T[0];i++)
printf("%c",T[i]);
printf("
");
}
int main()
{
int i,j;
Status k;
char s;
String t,s1,s2;
printf(" s1: ");
k=StrAssign(s1,"abcd");
if(!k)
{
printf(" MAXSIZE(=%d)
",MAXSIZE);
exit(0);
}
printf(" %d ？%d(1: 0: )
",StrLength(s1),StrEmpty(s1));
StrCopy(s2,s1);
printf(" s1 : ");
StrPrint(s2);
printf(" s2: ");
k=StrAssign(s2,"efghijk");
if(!k)
{
printf(" MAXSIZE(%d)
",MAXSIZE);
exit(0);
}
i=StrCompare(s1,s2);
if(i<0)
s=';
else if(i==0)
s='=';
else
s='>';
printf(" s1%c s2
",s);
k=Concat(t,s1,s2);
printf(" s1 s2 t : ");
StrPrint(t);
if(k==FALSE)
printf(" t
");
ClearString(s1);
printf(" , s1 : ");
StrPrint(s1);
printf(" %d ？%d(1: 0: )
",StrLength(s1),StrEmpty(s1));
printf(" t , , : ");
i=2;
j=3;
printf("%d,%d
",i,j);
k=SubString(s2,t,i,j);
if(k)
{
printf(" s2 : ");
StrPrint(s2);
}
printf(" t pos , len ， pos,len: ");
i=4;
j=2;
printf("%d,%d
",i,j);
StrDelete(t,i,j);
printf(" t : ");
StrPrint(t);
i=StrLength(s2)/2;
StrInsert(s2,i,t);
printf(" s2 %d t , s2 :
",i);
StrPrint(s2);
i=Index(s2,t,1);
printf("s2 %d t
",i);
SubString(t,s2,1,1);
printf(" t ：");
StrPrint(t);
Concat(s1,t,t);
printf(" s1 ：");
StrPrint(s1);
Replace(s2,t,s1);
printf(" s1 s2 t , s2 : ");
StrPrint(s2);
return 0;
}
//02 _KMP
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* */
typedef int Status; /* Status , ， OK */
typedef int ElemType; /* ElemType ， int */
typedef char String[MAXSIZE+1]; /* 0 */
/* chars T */
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
Status ClearString(String S)
{
S[0]=0;/* */
return OK;
}
/* T。 */
void StrPrint(String T)
{
int i;
for(i=1;i<=T[0];i++)
printf("%c",T[i]);
printf("
");
}
/* Next 。 */
void NextPrint(int next[],int length)
{
int i;
for(i=1;i<=length;i++)
printf("%d",next[i]);
printf("
");
}
/* */
int StrLength(String S)
{
return S[0];
}
/* */
int Index(String S, String T, int pos)
{
int i = pos; /* i S ， pos 1， pos */
int j = 1; /* j T */
while (i <= S[0] && j <= T[0]) /* i S j T ， */
{
if (S[i] == T[j]) /* */
{
++i;
++j;
}
else /* */
{
i = i-j+2; /* i */
j = 1; /* j T */
}
}
if (j > T[0])
return i-T[0];
else
return 0;
}
/* T next 。 */
void get_next(String T, int *next)
{
int i,j;
i=1;
j=0;
next[1]=0;
while (i<T[0]) /* T[0] T */
{
if(j==0 || T[i]== T[j]) /* T[i] ，T[j] */
{
++i;
++j;
next[i] = j;
}
else
j= next[j]; /* ， j */
}
}
/* T S pos 。 ， 0。 */
/* T ，1≤pos≤StrLength(S)。 */
int Index_KMP(String S, String T, int pos)
{
int i = pos; /* i S ， pos 1， pos */
int j = 1; /* j T */
int next[255]; /* next */
get_next(T, next); /* T ， next */
while (i <= S[0] && j <= T[0]) /* i S j T ， */
{
if (j==0 || S[i] == T[j]) /* ， j=0 */
{
++i;
++j;
}
else /* */
j = next[j];/* j ，i */
}
if (j > T[0])
return i-T[0];
else
return 0;
}
/* T next nextval */
void get_nextval(String T, int *nextval)
{
int i,j;
i=1;
j=0;
nextval[1]=0;
while (i<T[0]) /* T[0] T */
{
if(j==0 || T[i]== T[j]) /* T[i] ，T[j] */
{
++i;
++j;
if (T[i]!=T[j]) /* */
nextval[i] = j; /* j nextval i */
else
nextval[i] = nextval[j]; /* ， */
/* nextval nextval i */
}
else
j= nextval[j]; /* ， j */
}
}
int Index_KMP1(String S, String T, int pos)
{
int i = pos; /* i S ， pos 1， pos */
int j = 1; /* j T */
int next[255]; /* next */
get_nextval(T, next); /* T ， next */
while (i <= S[0] && j <= T[0]) /* i S j T ， */
{
if (j==0 || S[i] == T[j]) /* ， j=0 */
{
++i;
++j;
}
else /* */
j = next[j];/* j ，i */
}
if (j > T[0])
return i-T[0];
else
return 0;
}
int main()
{
int i,*p;
String s1,s2;
StrAssign(s1,"abcdex");
printf(" : ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf("Next : ");
NextPrint(p,StrLength(s1));
printf("
");
StrAssign(s1,"abcabx");
printf(" : ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf("Next : ");
NextPrint(p,StrLength(s1));
printf("
");
StrAssign(s1,"ababaaaba");
printf(" : ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf("Next : ");
NextPrint(p,StrLength(s1));
printf("
");
StrAssign(s1,"aaaaaaaab");
printf(" : ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf("Next : ");
NextPrint(p,StrLength(s1));
printf("
");
StrAssign(s1,"ababaaaba");
printf(" : ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf(" Next : ");
NextPrint(p,StrLength(s1));
get_nextval(s1,p);
printf("NextVal : ");
NextPrint(p,StrLength(s1));
printf("
");
StrAssign(s1,"aaaaaaaab");
printf(" : ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf(" Next : ");
NextPrint(p,StrLength(s1));
get_nextval(s1,p);
printf("NextVal : ");
NextPrint(p,StrLength(s1));
printf("
");
StrAssign(s1,"00000000000000000000000000000000000000000000000001");
printf(" : ");
StrPrint(s1);
StrAssign(s2,"0000000001");
printf(" : ");
StrPrint(s2);
printf("
");
printf(" %d （ ）
",Index(s1,s2,1));
printf(" %d （KMP ）
",Index_KMP(s1,s2,1));
printf(" %d （KMP ）
",Index_KMP1(s1,s2,1));
return 0;
}
01二叉樹順構造実現_BiTreeAray
//01 _BiTreeArray
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* */
#define MAX_TREE_SIZE 100 /* */
typedef int Status; /* Status , ， OK */
typedef int TElemType; /* ， */
typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0 */
typedef struct
{
int level,order; /* , ( ) */
}Position;
TElemType Nil=0; /* 0 */
Status visit(TElemType c)
{
printf("%d ",c);
return OK;
}
/* T。 T ， ， & */
Status InitBiTree(SqBiTree T)
{
int i;
for(i=0;i<MAX_TREE_SIZE;i++)
T[i]=Nil; /* */
return OK;
}
/* ( ), T */
Status CreateBiTree(SqBiTree T)
{
int i=0;
printf(" ( )，0 ， 999 。 ≤%d:
",MAX_TREE_SIZE);
while(i<10)
{
T[i]=i+1;
if(i!=0&&T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* ( ) */
{
printf(" %d
",T[i]);
exit(ERROR);
}
i++;
}
while(i<MAX_TREE_SIZE)
{
T[i]=Nil; /* T */
i++;
}
return OK;
}
#define ClearBiTree InitBiTree /* ， */
/* : T */
/* : T , TRUE, FALSE */
Status BiTreeEmpty(SqBiTree T)
{
if(T[0]==Nil) /* , */
return TRUE;
else
return FALSE;
}
/* : T 。 : T */
int BiTreeDepth(SqBiTree T)
{
int i,j=-1;
for(i=MAX_TREE_SIZE-1;i>=0;i--) /* */
if(T[i]!=Nil)
break;
i++;
do
j++;
while(i>=powl(2,j));/* 2 j 。 */
return j;
}
/* : T */
/* : T , e T , OK; ERROR,e */
Status Root(SqBiTree T,TElemType *e)
{
if(BiTreeEmpty(T)) /* T */
return ERROR;
else
{
*e=T[0];
return OK;
}
}
/* : T ,e T ( ) */
/* : e( , ) */
TElemType Value(SqBiTree T,Position e)
{
return T[(int)powl(2,e.level-1)+e.order-2];
}
/* : T ,e T ( ) */
/* : e( , ) value */
Status Assign(SqBiTree T,Position e,TElemType value)
{
int i=(int)powl(2,e.level-1)+e.order-2; /* 、 */
if(value!=Nil&&T[(i+1)/2-1]==Nil) /* */
return ERROR;
else if(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /* （ ） */
return ERROR;
T[i]=value;
return OK;
}
/* : T ,e T */
/* : e T , , ＂ ＂ */
TElemType Parent(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) /* */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* e */
return T[(i+1)/2-1];
return Nil; /* e */
}
/* : T ,e T */
/* : e 。 e , ＂ ＂ */
TElemType LeftChild(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) /* */
return Nil;
for(i=0;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* e */
return T[i*2+1];
return Nil; /* e */
}
/* : T ,e T */
/* : e 。 e , ＂ ＂ */
TElemType RightChild(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) /* */
return Nil;
for(i=0;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* e */
return T[i*2+2];
return Nil; /* e */
}
/* : T ,e T */
/* : e 。 e T , ＂ ＂ */
TElemType LeftSibling(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) /* */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e&&i%2==0) /* e ( ) */
return T[i-1];
return Nil; /* e */
}
/* : T ,e T */
/* : e 。 e T , ＂ ＂ */
TElemType RightSibling(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) /* */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e&&i%2) /* e ( ) */
return T[i+1];
return Nil; /* e */
}
/* PreOrderTraverse() */
void PreTraverse(SqBiTree T,int e)
{
visit(T[e]);
if(T[2*e+1]!=Nil) /* */
PreTraverse(T,2*e+1);
if(T[2*e+2]!=Nil) /* */
PreTraverse(T,2*e+2);
}
/* : */
/* : T。 */
Status PreOrderTraverse(SqBiTree T)
{
if(!BiTreeEmpty(T)) /* */
PreTraverse(T,0);
printf("
");
return OK;
}
/* InOrderTraverse() */
void InTraverse(SqBiTree T,int e)
{
if(T[2*e+1]!=Nil) /* */
InTraverse(T,2*e+1);
visit(T[e]);
if(T[2*e+2]!=Nil) /* */
InTraverse(T,2*e+2);
}
/* : */
/* : T。 */
Status InOrderTraverse(SqBiTree T)
{
if(!BiTreeEmpty(T)) /* */
InTraverse(T,0);
printf("
");
return OK;
}
/* PostOrderTraverse() */
void PostTraverse(SqBiTree T,int e)
{
if(T[2*e+1]!=Nil) /* */
PostTraverse(T,2*e+1);
if(T[2*e+2]!=Nil) /* */
PostTraverse(T,2*e+2);
visit(T[e]);
}
/* : T */
/* : T。 */
Status PostOrderTraverse(SqBiTree T)
{
if(!BiTreeEmpty(T)) /* */
PostTraverse(T,0);
printf("
");
return OK;
}
/* */
void LevelOrderTraverse(SqBiTree T)
{
int i=MAX_TREE_SIZE-1,j;
while(T[i]==Nil)
i--; /* */
for(j=0;j<=i;j++) /* , */
if(T[j]!=Nil)
visit(T[j]); /* */
printf("
");
}
/* 、 */
void Print(SqBiTree T)
{
int j,k;
Position p;
TElemType e;
for(j=1;j<=BiTreeDepth(T);j++)
{
printf(" %d : ",j);
for(k=1;k<=powl(2,j-1);k++)
{
p.level=j;
p.order=k;
e=Value(T,p);
if(e!=Nil)
printf("%d:%d ",k,e);
}
printf("
");
}
}
int main()
{
Status i;
Position p;
TElemType e;
SqBiTree T;
InitBiTree(T);
CreateBiTree(T);
printf(" , ？%d(1: 0: ) =%d
",BiTreeEmpty(T),BiTreeDepth(T));
i=Root(T,&e);
if(i)
printf(" ：%d
",e);
else
printf(" ，
");
printf(" :
");
LevelOrderTraverse(T);
printf(" :
");
PreOrderTraverse(T);
printf(" :
");
InOrderTraverse(T);
printf(" :
");
PostOrderTraverse(T);
printf(" 3 2。");
p.level=3;
p.order=2;
e=Value(T,p);
printf(" %d :50 ",e);
e=50;
Assign(T,p,e);
printf(" :
");
PreOrderTraverse(T);
printf(" %d %d, ",e,Parent(T,e));
printf("%d,%d, ",LeftChild(T,e),RightChild(T,e));
printf("%d,%d
",LeftSibling(T,e),RightSibling(T,e));
ClearBiTree(T);
printf(" , ？%d(1: 0: ) =%d
",BiTreeEmpty(T),BiTreeDepth(T));
i=Root(T,&e);
if(i)
printf(" ：%d
",e);
else
printf(" ，
");
return 0;
}
//02 _BiTreeLink
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* */
typedef int Status; /* Status , ， OK */
/* ********************************** */
int index=1;
typedef char String[24]; /* 0 */
String str;
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
/* ************************************************ */
typedef char TElemType;
TElemType Nil=' '; /* */
Status visit(TElemType e)
{
printf("%c ",e);
return OK;
}
typedef struct BiTNode /* */
{
TElemType data; /* */
struct BiTNode *lchild,*rchild; /* */
}BiTNode,*BiTree;
/* T */
Status InitBiTree(BiTree *T)
{
*T=NULL;
return OK;
}
/* : T 。 : T */
void DestroyBiTree(BiTree *T)
{
if(*T)
{
if((*T)->lchild) /* */
DestroyBiTree(&(*T)->lchild); /* */
if((*T)->rchild) /* */
DestroyBiTree(&(*T)->rchild); /* */
free(*T); /* */
*T=NULL; /* 0 */
}
}
/* （ ） */
/* # ， T。 */
void CreateBiTree(BiTree *T)
{
TElemType ch;
/* scanf("%c",&ch); */
ch=str[index++];
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=ch; /* */
CreateBiTree(&(*T)->lchild); /* */
CreateBiTree(&(*T)->rchild); /* */
}
}
/* : T */
/* : T , TRUE, FALSE */
Status BiTreeEmpty(BiTree T)
{
if(T)
return FALSE;
else
return TRUE;
}
#define ClearBiTree DestroyBiTree
/* : T 。 : T */
int BiTreeDepth(BiTree T)
{
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
return i>j?i+1:j+1;
}
/* : T 。 : T */
TElemType Root(BiTree T)
{
if(BiTreeEmpty(T))
return Nil;
else
return T->data;
}
/* : T ，p T */
/* : p */
TElemType Value(BiTree p)
{
return p->data;
}
/* p value */
void Assign(BiTree p,TElemType value)
{
p->data=value;
}
/* : T */
/* : T */
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c",T->data);/* ， */
PreOrderTraverse(T->lchild); /* */
PreOrderTraverse(T->rchild); /* */
}
/* : T */
/* : T */
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild); /* */
printf("%c",T->data);/* ， */
InOrderTraverse(T->rchild); /* */
}
/* : T */
/* : T */
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /* */
PostOrderTraverse(T->rchild); /* */
printf("%c",T->data);/* ， */
}
int main()
{
int i;
BiTree T;
TElemType e1;
InitBiTree(&T);
StrAssign(str,"ABDH#K###E##CFI###G#J##");
CreateBiTree(&T);
printf(" , ？%d(1: 0: ) =%d
",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);
printf(" : %c
",e1);
printf("
:");
PreOrderTraverse(T);
printf("
:");
InOrderTraverse(T);
printf("
:");
PostOrderTraverse(T);
ClearBiTree(&T);
printf("
, ？%d(1: 0: ) =%d
",BiTreeEmpty(T),BiTreeDepth(T));
i=Root(T);
if(!i)
printf(" ，
");
return 0;
}
//03 _ThreadBinaryTree
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* */
typedef int Status; /* Status , , OK */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag; /* Link==0 , */
/* Thread==1 */
typedef struct BiThrNode /* */
{
TElemType data; /* */
struct BiThrNode *lchild, *rchild; /* */
PointerTag LTag;
PointerTag RTag; /* */
} BiThrNode, *BiThrTree;
TElemType Nil='#'; /* */
Status visit(TElemType e)
{
printf("%c ",e);
return OK;
}
/* , T */
/* 0( )/ ( ) */
Status CreateBiThrTree(BiThrTree *T)
{
TElemType h;
scanf("%c",&h);
if(h==Nil)
*T=NULL;
else
{
*T=(BiThrTree)malloc(sizeof(BiThrNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=h; /* ( ) */
CreateBiThrTree(&(*T)->lchild); /* */
if((*T)->lchild) /* */
(*T)->LTag=Link;
CreateBiThrTree(&(*T)->rchild); /* */
if((*T)->rchild) /* */
(*T)->RTag=Link;
}
return OK;
}
BiThrTree pre; /* , */
/* */
void InThreading(BiThrTree p)
{
if(p)
{
InThreading(p->lchild); /* */
if(!p->lchild) /* */
{
p->LTag=Thread; /* */
p->lchild=pre; /* */
}
if(!pre->rchild) /* */
{
pre->RTag=Thread; /* */
pre->rchild=p; /* ( p) */
}
pre=p; /* pre p */
InThreading(p->rchild); /* */
}
}
/* T, ,Thrt */
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{
*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if(!*Thrt)
exit(OVERFLOW);
(*Thrt)->LTag=Link; /* */
(*Thrt)->RTag=Thread;
(*Thrt)->rchild=(*Thrt); /* */
if(!T) /* , */
(*Thrt)->lchild=*Thrt;
else
{
(*Thrt)->lchild=T;
pre=(*Thrt);
InThreading(T); /* */
pre->rchild=*Thrt;
pre->RTag=Thread; /* */
(*Thrt)->rchild=pre;
}
return OK;
}
/* T( ) */
Status InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
p=T->lchild; /* p */
while(p!=T)
{ /* ,p==T */
while(p->LTag==Link)
p=p->lchild;
if(!visit(p->data)) /* */
return ERROR;
while(p->RTag==Thread&&p->rchild!=T)
{
p=p->rchild;
visit(p->data); /* */
}
p=p->rchild;
}
return OK;
}
int main()
{
BiThrTree H,T;
printf(" ( :'ABDH##I##EJ###CF##G##')
");
CreateBiThrTree(&T); /* */
InOrderThreading(&H,T); /* , */
printf(" ( ) :
");
InOrderTraverse_Thr(H); /* ( ) */
printf("
");
return 0;
}
01隣接マトリクス作成_CreateMGraph
//01 _CreateMGraph
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* ， */
#define INFINITY 65535
typedef int Status; /* Status , ， OK */
typedef char VertexType; /* */
typedef int EdgeType; /* */
typedef struct
{
VertexType vexs[MAXVEX]; /* */
EdgeType arc[MAXVEX][MAXVEX];/* ， */
int numNodes, numEdges; /* */
}MGraph;
/* */
void CreateMGraph(MGraph *G)
{
int i,j,k,w;
printf(" :
");
scanf("%d,%d",&G->numNodes,&G->numEdges); /* */
for(i = 0;i <G->numNodes;i++) /* , */
scanf(&G->vexs[i]);
for(i = 0;i <G->numNodes;i++)
for(j = 0;j <G->numNodes;j++)
G->arc[i][j]=INFINITY; /* */
for(k = 0;k <G->numEdges;k++) /* numEdges ， */
{
printf(" (vi,vj) i， j w:
");
scanf("%d,%d,%d",&i,&j,&w); /* (vi,vj) w */
G->arc[i][j]=w;
G->arc[j][i]= G->arc[i][j]; /* ， */
}
}
int main(void)
{
MGraph G;
CreateMGraph(&G);
return 0;
}
//02 _CreateALGraph
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* , */
typedef int Status; /* Status , , OK */
typedef char VertexType; /* */
typedef int EdgeType; /* */
typedef struct EdgeNode /* */
{
int adjvex; /* , */
EdgeType info; /* , */
struct EdgeNode *next; /* , */
}EdgeNode;
typedef struct VertexNode /* */
{
VertexType data; /* , */
EdgeNode *firstedge;/* */
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numNodes,numEdges; /* */
}GraphAdjList;
/* */
void CreateALGraph(GraphAdjList *G)
{
int i,j,k;
EdgeNode *e;
printf(" :
");
scanf("%d,%d",&G->numNodes,&G->numEdges); /* */
for(i = 0;i < G->numNodes;i++) /* , */
{
scanf(&G->adjList[i].data); /* */
G->adjList[i].firstedge=NULL; /* */
}
for(k = 0;k < G->numEdges;k++)/* */
{
printf(" (vi,vj) :
");
scanf("%d,%d",&i,&j); /* (vi,vj) */
e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* , */
e->adjvex=j; /* j */
e->next=G->adjList[i].firstedge; /* e */
G->adjList[i].firstedge=e; /* e */
e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* , */
e->adjvex=i; /* i */
e->next=G->adjList[j].firstedge; /* e */
G->adjList[j].firstedge=e; /* e */
}
}
int main(void)
{
GraphAdjList G;
CreateALGraph(&G);
return 0;
}
//03 DFS_BFS
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; /* Status , ， OK */
typedef int Boolean; /* Boolean , TRUE FALSE */
typedef char VertexType; /* */
typedef int EdgeType; /* */
#define MAXSIZE 9 /* */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535
typedef struct
{
VertexType vexs[MAXVEX]; /* */
EdgeType arc[MAXVEX][MAXVEX];/* ， */
int numVertexes, numEdges; /* */
}MGraph;
/* ********************************** */
/* */
typedef struct
{
int data[MAXSIZE];
int front; /* */
int rear; /* ， ， */
}Queue;
/* Q */
Status InitQueue(Queue *Q)
{
Q->front=0;
Q->rear=0;
return OK;
}
/* Q , TRUE, FALSE */
Status QueueEmpty(Queue Q)
{
if(Q.front==Q.rear) /* */
return TRUE;
else
return FALSE;
}
/* ， e Q */
Status EnQueue(Queue *Q,int e)
{
if ((Q->rear+1)%MAXSIZE == Q->front) /* */
return ERROR;
Q->data[Q->rear]=e; /* e */
Q->rear=(Q->rear+1)%MAXSIZE;/* rear ， */
/* */
return OK;
}
/* ， Q ， e */
Status DeQueue(Queue *Q,int *e)
{
if (Q->front == Q->rear) /* */
return ERROR;
*e=Q->data[Q->front]; /* e */
Q->front=(Q->front+1)%MAXSIZE; /* front ， */
/* */
return OK;
}
/* ****************************************************** */
void CreateMGraph(MGraph *G)
{
int i, j;
G->numEdges=15;
G->numVertexes=9;
/* ， */
G->vexs[0]='A';
G->vexs[1]='B';
G->vexs[2]='C';
G->vexs[3]='D';
G->vexs[4]='E';
G->vexs[5]='F';
G->vexs[6]='G';
G->vexs[7]='H';
G->vexs[8]='I';
for (i = 0; i < G->numVertexes; i++)/* */
{
for ( j = 0; j < G->numVertexes; j++)
{
G->arc[i][j]=0;
}
}
G->arc[0][1]=1;
G->arc[0][5]=1;
G->arc[1][2]=1;
G->arc[1][8]=1;
G->arc[1][6]=1;
G->arc[2][3]=1;
G->arc[2][8]=1;
G->arc[3][4]=1;
G->arc[3][7]=1;
G->arc[3][6]=1;
G->arc[3][8]=1;
G->arc[4][5]=1;
G->arc[4][7]=1;
G->arc[5][6]=1;
G->arc[6][7]=1;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
Boolean visited[MAXVEX]; /* */
/* */
void DFS(MGraph G, int i)
{
int j;
visited[i] = TRUE;
printf("%c ", G.vexs[i]);/* ， */
for(j = 0; j < G.numVertexes; j++)
if(G.arc[i][j] == 1 && !visited[j])
DFS(G, j);/* */
}
/* */
void DFSTraverse(MGraph G)
{
int i;
for(i = 0; i < G.numVertexes; i++)
visited[i] = FALSE; /* */
for(i = 0; i < G.numVertexes; i++)
if(!visited[i]) /* DFS， ， */
DFS(G, i);
}
/* */
void BFSTraverse(MGraph G)
{
int i, j;
Queue Q;
for(i = 0; i < G.numVertexes; i++)
visited[i] = FALSE;
InitQueue(&Q); /* */
for(i = 0; i < G.numVertexes; i++) /* */
{
if (!visited[i]) /* */
{
visited[i]=TRUE; /* */
printf("%c ", G.vexs[i]);/* ， */
EnQueue(&Q,i); /* */
while(!QueueEmpty(Q)) /* */
{
DeQueue(&Q,&i); /* ， i */
for(j=0;j<G.numVertexes;j++)
{
/* */
if(G.arc[i][j] == 1 && !visited[j])
{
visited[j]=TRUE; /* */
printf("%c ", G.vexs[j]); /* */
EnQueue(&Q,j); /* */
}
}
}
}
}
}
int main(void)
{
MGraph G;
CreateMGraph(&G);
printf("
：");
DFSTraverse(G);
printf("
：");
BFSTraverse(G);
return 0;
}
//04 DFS_BFS
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 9 /* */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535
typedef int Status; /* Status , , OK */
typedef int Boolean; /* Boolean , TRUE FALSE */
typedef char VertexType; /* */
typedef int EdgeType; /* */
/* */
typedef struct
{
VertexType vexs[MAXVEX]; /* */
EdgeType arc[MAXVEX][MAXVEX];/* , */
int numVertexes, numEdges; /* */
}MGraph;
/* ****************** */
typedef struct EdgeNode /* */
{
int adjvex; /* , */
int weight; /* , */
struct EdgeNode *next; /* , */
}EdgeNode;
typedef struct VertexNode /* */
{
int in; /* */
char data; /* , */
EdgeNode *firstedge;/* */
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes,numEdges; /* */
}graphAdjList,*GraphAdjList;
/* **************************** */
/* ********************************** */
/* */
typedef struct
{
int data[MAXSIZE];
int front; /* */
int rear; /* , , */
}Queue;
/* Q */
Status InitQueue(Queue *Q)
{
Q->front=0;
Q->rear=0;
return OK;
}
/* Q , TRUE, FALSE */
Status QueueEmpty(Queue Q)
{
if(Q.front==Q.rear) /* */
return TRUE;
else
return FALSE;
}
/* , e Q */
Status EnQueue(Queue *Q,int e)
{
if ((Q->rear+1)%MAXSIZE == Q->front) /* */
return ERROR;
Q->data[Q->rear]=e; /* e */
Q->rear=(Q->rear+1)%MAXSIZE;/* rear , */
/* */
return OK;
}
/* , Q , e */
Status DeQueue(Queue *Q,int *e)
{
if (Q->front == Q->rear) /* */
return ERROR;
*e=Q->data[Q->front]; /* e */
Q->front=(Q->front+1)%MAXSIZE; /* front , */
/* */
return OK;
}
/* ****************************************************** */
void CreateMGraph(MGraph *G)
{
int i, j;
G->numEdges=15;
G->numVertexes=9;
/* , */
G->vexs[0]='A';
G->vexs[1]='B';
G->vexs[2]='C';
G->vexs[3]='D';
G->vexs[4]='E';
G->vexs[5]='F';
G->vexs[6]='G';
G->vexs[7]='H';
G->vexs[8]='I';
for (i = 0; i < G->numVertexes; i++)/* */
{
for ( j = 0; j < G->numVertexes; j++)
{
G->arc[i][j]=0;
}
}
G->arc[0][1]=1;
G->arc[0][5]=1;
G->arc[1][2]=1;
G->arc[1][8]=1;
G->arc[1][6]=1;
G->arc[2][3]=1;
G->arc[2][8]=1;
G->arc[3][4]=1;
G->arc[3][7]=1;
G->arc[3][6]=1;
G->arc[3][8]=1;
G->arc[4][5]=1;
G->arc[4][7]=1;
G->arc[5][6]=1;
G->arc[6][7]=1;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{
int i,j;
EdgeNode *e;
*GL = (GraphAdjList)malloc(sizeof(graphAdjList));
(*GL)->numVertexes=G.numVertexes;
(*GL)->numEdges=G.numEdges;
for(i= 0;i <G.numVertexes;i++) /* , */
{
(*GL)->adjList[i].in=0;
(*GL)->adjList[i].data=G.vexs[i];
(*GL)->adjList[i].firstedge=NULL; /* */
}
for(i=0;i<G.numVertexes;i++) /* */
{
for(j=0;j<G.numVertexes;j++)
{
if (G.arc[i][j]==1)
{
e=(EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex=j; /* j */
e->next=(*GL)->adjList[i].firstedge; /* e */
(*GL)->adjList[i].firstedge=e; /* e */
(*GL)->adjList[j].in++;
}
}
}
}
Boolean visited[MAXSIZE]; /* */
/* */
void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;
visited[i] = TRUE;
printf("%c ",GL->adjList[i].data);/* , */
p = GL->adjList[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
DFS(GL, p->adjvex);/* */
p = p->next;
}
}
/* */
void DFSTraverse(GraphAdjList GL)
{
int i;
for(i = 0; i < GL->numVertexes; i++)
visited[i] = FALSE; /* */
for(i = 0; i < GL->numVertexes; i++)
if(!visited[i]) /* DFS, , */
DFS(GL, i);
}
/* */
void BFSTraverse(GraphAdjList GL)
{
int i;
EdgeNode *p;
Queue Q;
for(i = 0; i < GL->numVertexes; i++)
visited[i] = FALSE;
InitQueue(&Q);
for(i = 0; i < GL->numVertexes; i++)
{
if (!visited[i])
{
visited[i]=TRUE;
printf("%c ",GL->adjList[i].data);/* , */
EnQueue(&Q,i);
while(!QueueEmpty(Q))
{
DeQueue(&Q,&i);
p = GL->adjList[i].firstedge; /* */
while(p)
{
if(!visited[p->adjvex]) /* */
{
visited[p->adjvex]=TRUE;
printf("%c ",GL->adjList[p->adjvex].data);
EnQueue(&Q,p->adjvex); /* */
}
p = p->next; /* */
}
}
}
}
}
int main(void)
{
MGraph G;
GraphAdjList GL;
CreateMGraph(&G);
CreateALGraph(G,&GL);
printf("
:");
DFSTraverse(GL);
printf("
:");
BFSTraverse(GL);
return 0;
}
//05 _Prim
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef int Status; /* Status , ， OK */
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
void CreateMGraph(MGraph *G)/* */
{
int i, j;
/* printf(" :"); */
G->numEdges=15;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1]=10;
G->arc[0][5]=11;
G->arc[1][2]=18;
G->arc[1][8]=12;
G->arc[1][6]=16;
G->arc[2][8]=8;
G->arc[2][3]=22;
G->arc[3][8]=21;
G->arc[3][6]=24;
G->arc[3][7]=16;
G->arc[3][4]=20;
G->arc[4][7]=7;
G->arc[4][5]=26;
G->arc[5][6]=17;
G->arc[6][7]=19;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* Prim */
void MiniSpanTree_Prim(MGraph G)
{
int min, i, j, k;
int adjvex[MAXVEX]; /* */
int lowcost[MAXVEX]; /* */
lowcost[0] = 0;/* 0， v0 */
/* lowcost 0， */
adjvex[0] = 0; /* 0 */
for(i = 1; i < G.numVertexes; i++) /* 0 */
{
lowcost[i] = G.arc[0][i]; /* v0 */
adjvex[i] = 0; /* v0 */
}
for(i = 1; i < G.numVertexes; i++)
{
min = INFINITY; /* ∞， */
/* 32767、65535 */
j = 1;k = 0;
while(j < G.numVertexes) /* */
{
if(lowcost[j]!=0 && lowcost[j] < min)/* 0 min */
{
min = lowcost[j]; /* */
k = j; /* k */
}
j++;
}
printf("(%d, %d)
", adjvex[k], k);/* */
lowcost[k] = 0;/* 0, */
for(j = 1; j < G.numVertexes; j++) /* */
{
if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
{/* k */
lowcost[j] = G.arc[k][j];/* lowcost */
adjvex[j] = k; /* k adjvex */
}
}
}
}
int main(void)
{
MGraph G;
CreateMGraph(&G);
MiniSpanTree_Prim(G);
return 0;
}
//06 _Kruskal
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; /* Status , ， OK */
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef struct
{
int begin;
int end;
int weight;
}Edge; /* Edge */
/* */
void CreateMGraph(MGraph *G)
{
int i, j;
/* printf(" :"); */
G->numEdges=15;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1]=10;
G->arc[0][5]=11;
G->arc[1][2]=18;
G->arc[1][8]=12;
G->arc[1][6]=16;
G->arc[2][8]=8;
G->arc[2][3]=22;
G->arc[3][8]=21;
G->arc[3][6]=24;
G->arc[3][7]=16;
G->arc[3][4]=20;
G->arc[4][7]=7;
G->arc[4][5]=26;
G->arc[5][6]=17;
G->arc[6][7]=19;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* */
void Swapn(Edge *edges,int i, int j)
{
int temp;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
/* */
void sort(Edge edges[],MGraph *G)
{
int i, j;
for ( i = 0; i < G->numEdges; i++)
{
for ( j = i + 1; j < G->numEdges; j++)
{
if (edges[i].weight > edges[j].weight)
{
Swapn(edges, i, j);
}
}
}
printf(" :
");
for (i = 0; i < G->numEdges; i++)
{
printf("(%d, %d) %d
", edges[i].begin, edges[i].end, edges[i].weight);
}
}
/* */
int Find(int *parent, int f)
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}
/* */
void MiniSpanTree_Kruskal(MGraph G)
{
int i, j, n, m;
int k = 0;
int parent[MAXVEX];/* */
Edge edges[MAXEDGE];/* ,edge begin,end,weight, */
/* ********************* */
for ( i = 0; i < G.numVertexes-1; i++)
{
for (j = i + 1; j < G.numVertexes; j++)
{
if (G.arc[i][j]<INFINITY)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G.arc[i][j];
k++;
}
}
}
sort(edges, &G);
/* ******************************************* */
for (i = 0; i < G.numVertexes; i++)
parent[i] = 0; /* 0 */
printf(" ：
");
for (i = 0; i < G.numEdges; i++) /* */
{
n = Find(parent,edges[i].begin);
m = Find(parent,edges[i].end);
if (n != m) /* n m ， */
{
parent[n] = m; /* parent 。 */
/* */
printf("(%d, %d) %d
", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
int main(void)
{
MGraph G;
CreateMGraph(&G);
MiniSpanTree_Kruskal(G);
return 0;
}
//07 _Dijkstra
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef int Status; /* Status , ， OK */
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX]; /* */
typedef int ShortPathTable[MAXVEX];/* */
/* */
void CreateMGraph(MGraph *G)
{
int i, j;
/* printf(" :"); */
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* */
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)/* */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1]=1;
G->arc[0][2]=5;
G->arc[1][2]=3;
G->arc[1][3]=7;
G->arc[1][4]=5;
G->arc[2][4]=1;
G->arc[2][5]=7;
G->arc[3][4]=2;
G->arc[3][6]=3;
G->arc[4][5]=3;
G->arc[4][6]=6;
G->arc[4][7]=9;
G->arc[5][7]=5;
G->arc[6][7]=2;
G->arc[6][8]=7;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* Dijkstra ， G v0 v P[v] D[v] */
/* P[v] ,D[v] v0 v */
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
int v,w,k,min;
int final[MAXVEX];/* final[w]=1 v0 vw */
for(v=0; v<G.numVertexes; v++) /* */
{
final[v] = 0; /* */
(*D)[v] = G.arc[v0][v];/* v0 */
(*P)[v] = -1; /* P -1 */
}
(*D)[v0] = 0; /* v0 v0 0 */
final[v0] = 1; /* v0 v0 */
/* ， v0 v */
for(v=1; v<G.numVertexes; v++)
{
min=INFINITY; /* v0 */
for(w=0; w<G.numVertexes; w++) /* v0 */
{
if(!final[w] && (*D)[w]<min)
{
k=w;
min = (*D)[w]; /* w v0 */
}
}
final[k] = 1; /* 1 */
for(w=0; w<G.numVertexes; w++) /* */
{
/* v */
if(!final[w] && (min+G.arc[k][w]<(*D)[w]))
{ /* ， D[w] P[w] */
(*D)[w] = min + G.arc[k][w]; /* */
(*P)[w]=k;
}
}
}
}
int main(void)
{
int i,j,v0;
MGraph G;
Patharc P;
ShortPathTable D; /* */
v0=0;
CreateMGraph(&G);
ShortestPath_Dijkstra(G, v0, &P, &D);
printf(" :
");
for(i=1;i<G.numVertexes;++i)
{
printf("v%d - v%d : ",v0,i);
j=i;
while(P[j]!=-1)
{
printf("%d ",P[j]);
j=P[j];
}
printf("
");
}
printf("
:
");
for(i=1;i<G.numVertexes;++i)
printf("v%d - v%d : %d
",G.vexs[0],G.vexs[i],D[i]);
return 0;
}
//08 _Floyd
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef int Status; /* Status , ， OK */
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* */
void CreateMGraph(MGraph *G)
{
int i, j;
/* printf(" :"); */
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* */
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)/* */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1]=1;
G->arc[0][2]=5;
G->arc[1][2]=3;
G->arc[1][3]=7;
G->arc[1][4]=5;
G->arc[2][4]=1;
G->arc[2][5]=7;
G->arc[3][4]=2;
G->arc[3][6]=3;
G->arc[4][5]=3;
G->arc[4][6]=6;
G->arc[4][7]=9;
G->arc[5][7]=5;
G->arc[6][7]=2;
G->arc[6][8]=7;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* Floyd ， G v w P[v][w] D[v][w]。 */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
int v,w,k;
for(v=0; v<G.numVertexes; ++v) /* D P */
{
for(w=0; w<G.numVertexes; ++w)
{
(*D)[v][w]=G.arc[v][w]; /* D[v][w] */
(*P)[v][w]=w; /* P */
}
}
for(k=0; k<G.numVertexes; ++k)
{
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
{/* k */
(*D)[v][w]=(*D)[v][k]+(*D)[k][w];/* */
(*P)[v][w]=(*P)[v][k];/* k */
}
}
}
}
}
int main(void)
{
int v,w,k;
MGraph G;
Patharc P;
ShortPathTable D; /* */
CreateMGraph(&G);
ShortestPath_Floyd(G,&P,&D);
printf(" :
");
for(v=0; v<G.numVertexes; ++v)
{
for(w=v+1; w<G.numVertexes; w++)
{
printf("v%d-v%d weight: %d ",v,w,D[v][w]);
k=P[v][w]; /* */
printf(" path: %d",v); /* */
while(k!=w) /* */
{
printf(" -> %d",k); /* */
k=P[k][w]; /* */
}
printf(" -> %d
",w); /* */
}
printf("
");
}
printf(" D
");
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
printf("%d\t",D[v][w]);
}
printf("
");
}
printf(" P
");
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
printf("%d ",P[v][w]);
}
printf("
");
}
return 0;
}
//09 _TopologicalSort
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 14
#define INFINITY 65535
typedef int Status; /* Status , ， OK */
/* */
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/* ****************** */
typedef struct EdgeNode /* */
{
int adjvex; /* ， */
int weight; /* ， */
struct EdgeNode *next; /* ， */
}EdgeNode;
typedef struct VertexNode /* */
{
int in; /* */
int data; /* ， */
EdgeNode *firstedge;/* */
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes,numEdges; /* */
}graphAdjList,*GraphAdjList;
/* **************************** */
void CreateMGraph(MGraph *G)/* */
{
int i, j;
/* printf(" :"); */
G->numEdges=MAXEDGE;
G->numVertexes=MAXVEX;
for (i = 0; i < G->numVertexes; i++)/* */
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)/* */
{
for ( j = 0; j < G->numVertexes; j++)
{
G->arc[i][j]=0;
}
}
G->arc[0][4]=1;
G->arc[0][5]=1;
G->arc[0][11]=1;
G->arc[1][2]=1;
G->arc[1][4]=1;
G->arc[1][8]=1;
G->arc[2][5]=1;
G->arc[2][6]=1;
G->arc[2][9]=1;
G->arc[3][2]=1;
G->arc[3][13]=1;
G->arc[4][7]=1;
G->arc[5][8]=1;
G->arc[5][12]=1;
G->arc[6][5]=1;
G->arc[8][7]=1;
G->arc[9][10]=1;
G->arc[9][11]=1;
G->arc[10][13]=1;
G->arc[12][9]=1;
}
/* */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{
int i,j;
EdgeNode *e;
*GL = (GraphAdjList)malloc(sizeof(graphAdjList));
(*GL)->numVertexes=G.numVertexes;
(*GL)->numEdges=G.numEdges;
for(i= 0;i <G.numVertexes;i++) /* ， */
{
(*GL)->adjList[i].in=0;
(*GL)->adjList[i].data=G.vexs[i];
(*GL)->adjList[i].firstedge=NULL; /* */
}
for(i=0;i<G.numVertexes;i++) /* */
{
for(j=0;j<G.numVertexes;j++)
{
if (G.arc[i][j]==1)
{
e=(EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex=j; /* j */
e->next=(*GL)->adjList[i].firstedge; /* e */
(*GL)->adjList[i].firstedge=e; /* e */
(*GL)->adjList[j].in++;
}
}
}
}
/* ， GL ， 1， 0。 */
Status TopologicalSort(GraphAdjList GL)
{
EdgeNode *e;
int i,k,gettop;
int top=0; /* */
int count=0;/* */
int *stack; /* 0 */
stack=(int *)malloc(GL->numVertexes * sizeof(int) );
for(i = 0; i<GL->numVertexes; i++)
if(0 == GL->adjList[i].in) /* 0 */
stack[++top]=i;
while(top!=0)
{
gettop=stack[top--];
printf("%d -> ",GL->adjList[gettop].data);
count++; /* i ， */
for(e = GL->adjList[gettop].firstedge; e; e = e->next)
{
k=e->adjvex;
if( !(--GL->adjList[k].in) ) /* i 1， 1 0， */
stack[++top]=k;
}
}
printf("
");
if(count < GL->numVertexes)
return ERROR;
else
return OK;
}
int main(void)
{
MGraph G;
GraphAdjList GL;
int result;
CreateMGraph(&G);
CreateALGraph(G,&GL);
result=TopologicalSort(GL);
printf("result:%d",result);
return 0;
}
//10 _CriticalPath
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 30
#define MAXVEX 30
#define INFINITY 65535
typedef int Status; /* Status , ， OK */
int *etv,*ltv; /* ， */
int *stack2; /* */
int top2; /* stack2 */
/* */
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/* ****************** */
typedef struct EdgeNode /* */
{
int adjvex; /* ， */
int weight; /* ， */
struct EdgeNode *next; /* ， */
}EdgeNode;
typedef struct VertexNode /* */
{
int in; /* */
int data; /* ， */
EdgeNode *firstedge;/* */
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes,numEdges; /* */
}graphAdjList,*GraphAdjList;
/* **************************** */
void CreateMGraph(MGraph *G)/* */
{
int i, j;
/* printf(" :"); */
G->numEdges=13;
G->numVertexes=10;
for (i = 0; i < G->numVertexes; i++)/* */
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)/* */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j]=INFINITY;
}
}
G->arc[0][1]=3;
G->arc[0][2]=4;
G->arc[1][3]=5;
G->arc[1][4]=6;
G->arc[2][3]=8;
G->arc[2][5]=7;
G->arc[3][4]=3;
G->arc[4][6]=9;
G->arc[4][7]=4;
G->arc[5][7]=6;
G->arc[6][9]=2;
G->arc[7][8]=5;
G->arc[8][9]=3;
}
/* */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{
int i,j;
EdgeNode *e;
*GL = (GraphAdjList)malloc(sizeof(graphAdjList));
(*GL)->numVertexes=G.numVertexes;
(*GL)->numEdges=G.numEdges;
for(i= 0;i <G.numVertexes;i++) /* ， */
{
(*GL)->adjList[i].in=0;
(*GL)->adjList[i].data=G.vexs[i];
(*GL)->adjList[i].firstedge=NULL; /* */
}
for(i=0;i<G.numVertexes;i++) /* */
{
for(j=0;j<G.numVertexes;j++)
{
if (G.arc[i][j]!=0 && G.arc[i][j]<INFINITY)
{
e=(EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex=j; /* j */
e->weight=G.arc[i][j];
e->next=(*GL)->adjList[i].firstedge; /* e */
(*GL)->adjList[i].firstedge=e; /* e */
(*GL)->adjList[j].in++;
}
}
}
}
/* */
Status TopologicalSort(GraphAdjList GL)
{ /* GL ， 1， 0。 */
EdgeNode *e;
int i,k,gettop;
int top=0; /* */
int count=0;/* */
int *stack; /* 0 */
stack=(int *)malloc(GL->numVertexes * sizeof(int) );
for(i = 0; i<GL->numVertexes; i++)
if(0 == GL->adjList[i].in) /* 0 */
stack[++top]=i;
top2=0;
etv=(int *)malloc(GL->numVertexes * sizeof(int) ); /* */
for(i=0; i<GL->numVertexes; i++)
etv[i]=0; /* */
stack2=(int *)malloc(GL->numVertexes * sizeof(int) );/* */
printf("TopologicalSort:\t");
while(top!=0)
{
gettop=stack[top--];
printf("%d -> ",GL->adjList[gettop].data);
count++; /* i ， */
stack2[++top2]=gettop; /* */
for(e = GL->adjList[gettop].firstedge; e; e = e->next)
{
k=e->adjvex;
if( !(--GL->adjList[k].in) ) /* i 1， 1 0， */
stack[++top]=k;
if((etv[gettop] + e->weight)>etv[k]) /* etv */
etv[k] = etv[gettop] + e->weight;
}
}
printf("
");
if(count < GL->numVertexes)
return ERROR;
else
return OK;
}
/* ,GL ， G */
void CriticalPath(GraphAdjList GL)
{
EdgeNode *e;
int i,gettop,k,j;
int ete,lte; /* */
TopologicalSort(GL); /* ， etv stack2 */
ltv=(int *)malloc(GL->numVertexes*sizeof(int));/* */
for(i=0; i<GL->numVertexes; i++)
ltv[i]=etv[GL->numVertexes-1]; /* */
printf("etv:\t");
for(i=0; i<GL->numVertexes; i++)
printf("%d -> ",etv[i]);
printf("
");
while(top2!=0) /* ltv */
{
gettop=stack2[top2--];
for(e = GL->adjList[gettop].firstedge; e; e = e->next) /* ltv */
{
k=e->adjvex;
if(ltv[k] - e->weight < ltv[gettop])
ltv[gettop] = ltv[k] - e->weight;
}
}
printf("ltv:\t");
for(i=0; i<GL->numVertexes; i++)
printf("%d -> ",ltv[i]);
printf("
");
for(j=0; j<GL->numVertexes; j++) /* ete,lte */
{
for(e = GL->adjList[j].firstedge; e; e = e->next)
{
k=e->adjvex;
ete = etv[j]; /* */
lte = ltv[k] - e->weight; /* */
if(ete == lte) /* */
printf(" length: %d
" ,GL->adjList[j].data,GL->adjList[k].data,e->weight);
}
}
}
int main(void)
{
MGraph G;
GraphAdjList GL;
CreateMGraph(&G);
CreateALGraph(G,&GL);
CriticalPath(GL);
return 0;
}
01静的検索_Search
//01 _Search
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* */
typedef int Status; /* Status , ， OK */
int F[100]; /* */
/* ，a ，n ，key */
int Sequential_Search(int *a,int n,int key)
{
int i;
for(i=1;i<=n;i++)
{
if (a[i]==key)
return i;
}
return 0;
}
/* */
int Sequential_Search2(int *a,int n,int key)
{
int i;
a[0]=key;
i=n;
while(a[i]!=key)
{
i--;
}
return i;
}
/* */
int Binary_Search(int *a,int n,int key)
{
int low,high,mid;
low=1; /* */
high=n; /* */
while(low<=high)
{
mid=(low+high)/2; /* */
if (key<a[mid]) /* */
high=mid-1; /* */
else if (key>a[mid])/* */
low=mid+1; /* */
else
{
return mid; /* mid */
}
}
return 0;
}
/* */
int Interpolation_Search(int *a,int n,int key)
{
int low,high,mid;
low=1; /* */
high=n; /* */
while(low<=high)
{
mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* */
if (key<a[mid]) /* */
high=mid-1; /* */
else if (key>a[mid])/* */
low=mid+1; /* */
else
return mid; /* mid */
}
return 0;
}
/* */
int Fibonacci_Search(int *a,int n,int key)
{
int low,high,mid,i,k=0;
low=1; /* */
high=n; /* */
while(n>F[k]-1)
k++;
for (i=n;i<F[k]-1;i++)
a[i]=a[n];
while(low<=high)
{
mid=low+F[k-1]-1;
if (key<a[mid])
{
high=mid-1;
k=k-1;
}
else if (key>a[mid])
{
low=mid+1;
k=k-2;
}
else
{
if (mid<=n)
return mid; /* mid */
else
return n;
}
}
return 0;
}
int main(void)
{
int a[MAXSIZE+1],i,result;
int arr[MAXSIZE]={0,1,16,24,35,47,59,62,73,88,99};
for(i=0;i<=MAXSIZE;i++)
{
a[i]=i;
}
result=Sequential_Search(a,MAXSIZE,MAXSIZE);
printf("Sequential_Search:%d
",result);
result=Sequential_Search2(a,MAXSIZE,1);
printf("Sequential_Search2:%d
",result);
result=Binary_Search(arr,10,62);
printf("Binary_Search:%d
",result);
result=Interpolation_Search(arr,10,62);
printf("Interpolation_Search:%d
",result);
F[0]=0;
F[1]=1;
for(i = 2;i < 100;i++)
{
F[i] = F[i-1] + F[i-2];
}
result=Fibonacci_Search(arr,10,62);
printf("Fibonacci_Search:%d
",result);
return 0;
}
//02 _BinarySortTree
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* */
typedef int Status; /* Status , ， OK */
/* */
typedef struct BiTNode /* */
{
int data; /* */
struct BiTNode *lchild, *rchild; /* */
} BiTNode, *BiTree;
/* T key, */
/* f T ， NULL */
/* ， p ， TRUE */
/* p FALSE */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
if (!T) /* */
{
*p = f;
return FALSE;
}
else if (key==T->data) /* */
{
*p = T;
return TRUE;
}
else if (key<T->data)
return SearchBST(T->lchild, key, T, p); /* */
else
return SearchBST(T->rchild, key, T, p); /* */
}
/* T key ， */
/* key TRUE， FALSE */
Status InsertBST(BiTree *T, int key)
{
BiTree p,s;
if (!SearchBST(*T, key, NULL, &p)) /* */
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
if (!p)
*T = s; /* s */
else if (key<p->data)
p->lchild = s; /* s */
else
p->rchild = s; /* s */
return TRUE;
}
else
return FALSE; /* ， */
}
/* p， 。 */
Status Delete(BiTree *p)
{
BiTree q,s;
if((*p)->rchild==NULL) /* （ ) */
{
q=*p; *p=(*p)->lchild; free(q);
}
else if((*p)->lchild==NULL) /* */
{
q=*p; *p=(*p)->rchild; free(q);
}
else /* */
{
q=*p; s=(*p)->lchild;
while(s->rchild) /* ， （ ） */
{
q=s;
s=s->rchild;
}
(*p)->data=s->data; /* s （ ） */
if(q!=*p)
q->rchild=s->lchild; /* q */
else
q->lchild=s->lchild; /* q */
free(s);
}
return TRUE;
}
/* T key ， , */
/* TRUE； FALSE。 */
Status DeleteBST(BiTree *T,int key)
{
if(!*T) /* key */
return FALSE;
else
{
if (key==(*T)->data) /* key */
return Delete(T);
else if (key<(*T)->data)
return DeleteBST(&(*T)->lchild,key);
else
return DeleteBST(&(*T)->rchild,key);
}
}
int main(void)
{
int i;
int a[10]={62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i=0;i<10;i++)
{
InsertBST(&T, a[i]);
}
DeleteBST(&T,93);
DeleteBST(&T,47);
printf(" ");
return 0;
}
//03 _AVLTree
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* */
typedef int Status; /* Status , ， OK */
/* */
typedef struct BiTNode /* */
{
int data; /* */
int bf; /* */
struct BiTNode *lchild, *rchild; /* */
} BiTNode, *BiTree;
/* p ， */
/* p ， */
void R_Rotate(BiTree *P)
{
BiTree L;
L=(*P)->lchild; /* L P */
(*P)->lchild=L->rchild; /* L P */
L->rchild=(*P);
*P=L; /* P */
}
/* P ， */
/* P ， 0 */
void L_Rotate(BiTree *P)
{
BiTree R;
R=(*P)->rchild; /* R P */
(*P)->rchild=R->lchild; /* R P */
R->lchild=(*P);
*P=R; /* P */
}
#define LH +1 /* */
#define EH 0 /* */
#define RH -1 /* */
/* T */
/* ， T */
void LeftBalance(BiTree *T)
{
BiTree L,Lr;
L=(*T)->lchild; /* L T */
switch(L->bf)
{ /* T ， */
case LH: /* T ， */
(*T)->bf=L->bf=EH;
R_Rotate(T);
break;
case RH: /* T ， */
Lr=L->rchild; /* Lr T */
switch(Lr->bf)
{ /* T */
case LH: (*T)->bf=RH;
L->bf=EH;
break;
case EH: (*T)->bf=L->bf=EH;
break;
case RH: (*T)->bf=EH;
L->bf=LH;
break;
}
Lr->bf=EH;
L_Rotate(&(*T)->lchild); /* T */
R_Rotate(T); /* T */
}
}
/* T ， */
/* ， T */
void RightBalance(BiTree *T)
{
BiTree R,Rl;
R=(*T)->rchild; /* R T */
switch(R->bf)
{ /* T ， */
case RH: /* T ， */
(*T)->bf=R->bf=EH;
L_Rotate(T);
break;
case LH: /* T ， */
Rl=R->lchild; /* Rl T */
switch(Rl->bf)
{ /* T */
case RH: (*T)->bf=LH;
R->bf=EH;
break;
case EH: (*T)->bf=R->bf=EH;
break;
case LH: (*T)->bf=EH;
R->bf=RH;
break;
}
Rl->bf=EH;
R_Rotate(&(*T)->rchild); /* T */
L_Rotate(T); /* T */
}
}
/* T e ， */
/* e ， 1， 0。 */
/* ， ， taller T 。 */
Status InsertAVL(BiTree *T,int e,Status *taller)
{
if(!*T)
{ /* ， “ ”， taller TRUE */
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH;
*taller=TRUE;
}
else
{
if (e==(*T)->data)
{ /* e */
*taller=FALSE; return FALSE;
}
if (e<(*T)->data)
{ /* T */
if(!InsertAVL(&(*T)->lchild,e,taller)) /* */
return FALSE;
if(*taller) /* T “ ” */
switch((*T)->bf) /* T */
{
case LH: /* ， */
LeftBalance(T); *taller=FALSE; break;
case EH: /* 、 ， */
(*T)->bf=LH; *taller=TRUE; break;
case RH: /* ， 、 */
(*T)->bf=EH; *taller=FALSE; break;
}
}
else
{ /* T */
if(!InsertAVL(&(*T)->rchild,e,taller)) /* */
return FALSE;
if(*taller) /* T “ ” */
switch((*T)->bf) /* T */
{
case LH: /* ， 、 */
(*T)->bf=EH; *taller=FALSE; break;
case EH: /* 、 ， */
(*T)->bf=RH; *taller=TRUE; break;
case RH: /* ， */
RightBalance(T); *taller=FALSE; break;
}
}
}
return TRUE;
}
int main(void)
{
int i;
int a[10]={3,2,1,4,5,6,7,10,9,8};
BiTree T=NULL;
Status taller;
for(i=0;i<10;i++)
{
InsertAVL(&T,a[i],&taller);
}
printf(" ");
return 0;
}
//04B _BTree
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* */
#define m 3 /* B ， 3 */
#define N 17 /* */
#define MAX 5 /* +1 */
typedef int Status; /* Status , ， OK */
typedef struct BTNode
{
int keynum; /* ， */
struct BTNode *parent; /* */
struct Node /* */
{
int key; /* */
struct BTNode *ptr; /* */
int recptr; /* */
}node[m+1]; /* key,recptr 0 */
}BTNode,*BTree; /* B B */
typedef struct
{
BTNode *pt; /* */
int i; /* 1..m， */
int tag; /* 1: ，O: */
}Result; /* B */
/* p->node[1..keynum].key i, p->node[i].key≤K＜p->node[i+1].key */
int Search(BTree p, int K)
{
int i=0,j;
for(j=1;j<=p->keynum;j++)
if(p->node[j].key<=K)
i=j;
return i;
}
/* m B T K， (pt,i,tag)。 ， */
/* tag=1， pt i K； tag=0， K */
/* Pt i i+1 。 */
Result SearchBTree(BTree T, int K)
{
BTree p=T,q=NULL; /* ，p ，q p */
Status found=FALSE;
int i=0;
Result r;
while(p&&!found)
{
i=Search(p,K); /* p->node[i].key≤Knode[i+1].key */
if(i>0&&p->node[i].key==K) /* */
found=TRUE;
else
{
q=p;
p=p->node[i].ptr;
}
}
r.i=i;
if(found) /* */
{
r.pt=p;
r.tag=1;
}
else /* ， K */
{
r.pt=q;
r.tag=0;
}
return r;
}
/* r->key、r ap q->key[i+1]、q->recptr[i+1] q->ptr[i+1] */
void Insert(BTree *q,int i,int key,BTree ap)
{
int j;
for(j=(*q)->keynum;j>i;j--) /* (*q)->node[i+1] */
(*q)->node[j+1]=(*q)->node[j];
(*q)->node[i+1].key=key;
(*q)->node[i+1].ptr=ap;
(*q)->node[i+1].recptr=key;
(*q)->keynum++;
}
/* q ， ， ap */
void split(BTree *q,BTree *ap)
{
int i,s=(m+1)/2;
*ap=(BTree)malloc(sizeof(BTNode)); /* ap */
(*ap)->node[0].ptr=(*q)->node[s].ptr; /* ap */
for(i=s+1;i<=m;i++)
{
(*ap)->node[i-s]=(*q)->node[i];
if((*ap)->node[i-s].ptr)
(*ap)->node[i-s].ptr->parent=*ap;
}
(*ap)->keynum=m-s;
(*ap)->parent=(*q)->parent;
(*q)->keynum=s-1; /* q ， keynum */
}
/* (T,r,ap) &T， T ap */
void NewRoot(BTree *T,int key,BTree ap)
{
BTree p;
p=(BTree)malloc(sizeof(BTNode));
p->node[0].ptr=*T;
*T=p;
if((*T)->node[0].ptr)
(*T)->node[0].ptr->parent=*T;
(*T)->parent=NULL;
(*T)->keynum=1;
(*T)->node[1].key=key;
(*T)->node[1].recptr=key;
(*T)->node[1].ptr=ap;
if((*T)->node[1].ptr)
(*T)->node[1].ptr->parent=*T;
}
/* m B T *q key[i] key[i+1] K r。 */
/* , , T m B 。 */
void InsertBTree(BTree *T,int key,BTree q,int i)
{
BTree ap=NULL;
Status finished=FALSE;
int s;
int rx;
rx=key;
while(q&&!finished)
{
Insert(&q,i,rx,ap); /* r->key、r ap q->key[i+1]、q->recptr[i+1] q->ptr[i+1] */
if(q->keynum<m)
finished=TRUE; /* */
else
{ /* *q */
s=(m+1)/2;
rx=q->node[s].recptr;
split(&q,&ap); /* q->key[s+1..m],q->ptr[s..m] q->recptr[s+1..m] *ap */
q=q->parent;
if(q)
i=Search(q,key); /* *q rx->key */
}
}
if(!finished) /* T ( q NULL) *q *ap */
NewRoot(T,rx,ap); /* (T,rx,ap) *T， T ap */
}
void print(BTNode c,int i) /* TraverseDSTable() */
{
printf("(%d)",c.node[i].key);
}
int main()
{
int r[N]={22,16,41,58,8,11,12,16,17,22,23,31,41,52,58,59,61};
BTree T=NULL;
Result s;
int i;
for(i=0;i<N;i++)
{
s=SearchBTree(T,r[i]);
if(!s.tag)
InsertBTree(&T,r[i],s.pt,s.i);
}
printf("
: ");
scanf("%d",&i);
s=SearchBTree(T,i);
if(s.tag)
print(*(s.pt),s.i);
else
printf(" ");
printf("
");
return 0;
}
//05 _HashTable
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* */
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /* */
#define NULLKEY -32768
typedef int Status; /* Status , ， OK */
typedef struct
{
int *elem; /* ， */
int count; /* */
}HashTable;
int m=0; /* ， */
/* */
Status InitHashTable(HashTable *H)
{
int i;
m=HASHSIZE;
H->count=m;
H->elem=(int *)malloc(m*sizeof(int));
for(i=0;i<m;i++)
H->elem[i]=NULLKEY;
return OK;
}
/* */
int Hash(int key)
{
return key % m; /* */
}
/* */
void InsertHash(HashTable *H,int key)
{
int addr = Hash(key); /* */
while (H->elem[addr] != NULLKEY) /* ， */
{
addr = (addr+1) % m; /* */
}
H->elem[addr] = key; /* */
}
/* */
Status SearchHash(HashTable H,int key,int *addr)
{
*addr = Hash(key); /* */
while(H.elem[*addr] != key) /* ， */
{
*addr = (*addr+1) % m; /* */
if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* */
return UNSUCCESS; /* */
}
return SUCCESS;
}
int main()
{
int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};
int i,p,key,result;
HashTable H;
key=39;
InitHashTable(&H);
for(i=0;i<m;i++)
InsertHash(&H,arr[i]);
result=SearchHash(H,key,&p);
if (result)
printf(" %d ：%d
",key,p);
else
printf(" %d 。
",key);
for(i=0;i<m;i++)
{
key=arr[i];
SearchHash(H,key,&p);
printf(" %d ：%d
",key,p);
}
return 0;
}
01ソート_ソト
//01 _Sort
#include
");
}
/* L （ ） */
void BubbleSort0(SqList *L)
{
int i,j;
for(i=1;i<L->length;i++)
{
for(j=i+1;j<=L->length;j++)
{
if(L->r[i]>L->r[j])
{
swap(L,i,j);/* L->r[i] L->r[j] */
}
}
}
}
/* L */
void BubbleSort(SqList *L)
{
int i,j;
for(i=1;i<L->length;i++)
{
for(j=L->length-1;j>=i;j--) /* j */
{
if(L->r[j]>L->r[j+1]) /* （ ）*/
{
swap(L,j,j+1);/* L->r[j] L->r[j+1] */
}
}
}
}
/* L */
void BubbleSort2(SqList *L)
{
int i,j;
Status flag=TRUE; /* flag */
for(i=1;i<L->length && flag;i++) /* flag true ， */
{
flag=FALSE; /* False */
for(j=L->length-1;j>=i;j--)
{
if(L->r[j]>L->r[j+1])
{
swap(L,j,j+1); /* L->r[j] L->r[j+1] */
flag=TRUE; /* ， flag true */
}
}
}
}
/* L */
void SelectSort(SqList *L)
{
int i,j,min;
for(i=1;i<L->length;i++)
{
min = i; /* */
for (j = i+1;j<=L->length;j++)/* */
{
if (L->r[min]>L->r[j]) /* */
min = j; /* min */
}
if(i!=min) /* min i， ， */
swap(L,i,min); /* L->r[i] L->r[min] */
}
}
/* L */
void InsertSort(SqList *L)
{
int i,j;
for(i=2;i<=L->length;i++)
{
if (L->r[i]<L->r[i-1]) /* L->r[i] */
{
L->r[0]=L->r[i]; /* */
for(j=i-1;L->r[j]>L->r[0];j--)
L->r[j+1]=L->r[j]; /* */
L->r[j+1]=L->r[0]; /* */
}
}
}
/* L */
void ShellSort(SqList *L)
{
int i,j,k=0;
int increment=L->length;
do
{
increment=increment/3+1;/* */
for(i=increment+1;i<=L->length;i++)
{
if (L->r[i]<L->r[i-increment])/* L->r[i] */
{
L->r[0]=L->r[i]; /* L->r[0] */
for(j=i-increment;j>0 && L->r[0]<L->r[j];j-=increment)
L->r[j+increment]=L->r[j]; /* ， */
L->r[j+increment]=L->r[0]; /* */
}
}
printf(" %d : ",++k);
print(*L);
}
while(increment>1);
}
/* ********************************** */
/* L->r[s..m] L->r[s] ， */
/* L->r[s] , L->r[s..m] */
void HeapAdjust(SqList *L,int s,int m)
{
int temp,j;
temp=L->r[s];
for(j=2*s;j<=m;j*=2) /* */
{
if(j<m && L->r[j]<L->r[j+1])
++j; /* j */
if(temp>=L->r[j])
break; /* rc s */
L->r[s]=L->r[j];
s=j;
}
L->r[s]=temp; /* */
}
/* L */
void HeapSort(SqList *L)
{
int i;
for(i=L->length/2;i>0;i--) /* L r */
HeapAdjust(L,i,L->length);
for(i=L->length;i>1;i--)
{
swap(L,1,i); /* */
HeapAdjust(L,1,i-1); /* L->r[1..i-1] */
}
}
/* **************************************** */
/* ********************************** */
/* SR[i..m] SR[m+1..n] TR[i..n] */
void Merge(int SR[],int TR[],int i,int m,int n)
{
int j,k,l;
for(j=m+1,k=i;i<=m && j<=n;k++) /* SR TR */
{
if (SR[i]<SR[j])
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
if(i<=m)
{
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; /* SR[i..m] TR */
}
if(j<=n)
{
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; /* SR[j..n] TR */
}
}
/* */
/* SR[s..t] TR1[s..t] */
void MSort(int SR[],int TR1[],int s, int t)
{
int m;
int TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; /* SR[s..t] SR[s..m] SR[m+1..t] */
MSort(SR,TR2,s,m); /* SR[s..m] TR2[s..m] */
MSort(SR,TR2,m+1,t); /* SR[m+1..t] TR2[m+1..t] */
Merge(TR2,TR1,s,m,t); /* TR2[s..m] TR2[m+1..t] TR1[s..t] */
}
}
/* L */
void MergeSort(SqList *L)
{
MSort(L->r,L->r,1,L->length);
}
/* */
/* SR[] s TR[] */
void MergePass(int SR[],int TR[],int s,int n)
{
int i=1;
int j;
while(i <= n-2*s+1)
{/* */
Merge(SR,TR,i,i+s-1,i+2*s-1);
i=i+2*s;
}
if(i<n-s+1) /* */
Merge(SR,TR,i,i+s-1,n);
else /* */
for(j =i;j <= n;j++)
TR[j] = SR[j];
}
/* L */
void MergeSort2(SqList *L)
{
int* TR=(int*)malloc(L->length * sizeof(int));/* */
int k=1;
while(k<L->length)
{
MergePass(L->r,TR,k,L->length);
k=2*k;/* */
MergePass(TR,L->r,k,L->length);
k=2*k;/* */
}
}
/* **************************************** */
/* ******************************** */
/* L ， ， */
/* ( ) ( ) 。 */
int Partition(SqList *L,int low,int high)
{
int pivotkey;
pivotkey=L->r[low]; /* */
while(low<high) /* */
{
while(low<high&&L->r[high]>=pivotkey)
high--;
swap(L,low,high);/* */
while(low<high&&L->r[low]<=pivotkey)
low++;
swap(L,low,high);/* */
}
return low; /* */
}
/* L L->r[low..high] */
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low<high)
{
pivot=Partition(L,low,high); /* L->r[low..high] ， pivot */
QSort(L,low,pivot-1); /* */
QSort(L,pivot+1,high); /* */
}
}
/* L */
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}
/* **************************************** */
/* ******************************** */
/* */
int Partition1(SqList *L,int low,int high)
{
int pivotkey;
int m = low + (high - low) / 2; /* */
if (L->r[low]>L->r[high])
swap(L,low,high); /* ， */
if (L->r[m]>L->r[high])
swap(L,high,m); /* ， */
if (L->r[m]>L->r[low])
swap(L,m,low); /* ， */
pivotkey=L->r[low]; /* */
L->r[0]=pivotkey; /* L->r[0] */
while(low<high) /* */
{
while(low<high&&L->r[high]>=pivotkey)
high--;
L->r[low]=L->r[high];
while(low<high&&L->r[low]<=pivotkey)
low++;
L->r[high]=L->r[low];
}
L->r[low]=L->r[0];
return low; /* */
}
void QSort1(SqList *L,int low,int high)
{
int pivot;
if((high-low)>MAX_LENGTH_INSERT_SORT)
{
while(low<high)
{
pivot=Partition1(L,low,high); /* L->r[low..high] ， pivot */
QSort1(L,low,pivot-1); /* */
/* QSort(L,pivot+1,high); /* */
low=pivot+1; /* */
}
}
else
InsertSort(L);
}
/* L */
void QuickSort1(SqList *L)
{
QSort1(L,1,L->length);
}
/* **************************************** */
#define N 9
int main()
{
int i;
/* int d[N]={9,1,5,8,3,7,4,6,2}; */
int d[N]={50,10,90,30,70,40,80,60,20};
/* int d[N]={9,8,7,6,5,4,3,2,1}; */
SqList l0,l1,l2,l3,l4,l5,l6,l7,l8,l9,l10;
for(i=0;i<N;i++)
l0.r[i+1]=d[i];
l0.length=N;
l1=l2=l3=l4=l5=l6=l7=l8=l9=l10=l0;
printf(" :
");
print(l0);
printf(" :
");
BubbleSort0(&l0);
print(l0);
printf(" :
");
BubbleSort(&l1);
print(l1);
printf(" :
");
BubbleSort2(&l2);
print(l2);
printf(" :
");
SelectSort(&l3);
print(l3);
printf(" :
");
InsertSort(&l4);
print(l4);
printf(" :
");
ShellSort(&l5);
print(l5);
printf(" :
");
HeapSort(&l6);
print(l6);
printf(" （ ）:
");
MergeSort(&l7);
print(l7);
printf(" （ ）:
");
MergeSort2(&l8);
print(l8);
printf(" :
");
QuickSort(&l9);
print(l9);
printf(" :
");
QuickSort1(&l10);
print(l10);
/* */
/*
srand(time(0));
int Max=10000;
int d[10000];
int i;
SqList l0;
for(i=0;i
return 0;
}