常用データ構造コード--C言語版(メモ)


コードディレクトリ:
第3章リニアテーブル01リニアテーブル順序格納_List
02リニアチェーンストレージ_LinkList
03スタティックチェーンテーブル_StaticLinkList
第4章スタックとキュー01シーケンススタック_Stack
02 2つのスタックの共有スペース_DoubleStack
03チェーンスタック_LinkStack
04フィボナッチ関数_Fibonacci
05シーケンスキュー_Queue
06チェーンキュー_LinkQueue
第5章シリアル01番_String
02パターンマッチング_KMP
第6章ツリー01ツリー順構造実現_BiTreeArray
02ツリーチェーン構造実装_BiTreeLink
03スレッドツリー_ThreadBinaryTree
第7章図01隣接行列作成_CreateMGraph
02隣接テーブル作成_CreateALGraph
03隣接行列の深さと広さはDFS_を遍歴するBFS
04隣接テーブルの深さと広さDFS_を遍歴するBFS
05最小生成ツリー_Prim
06最小生成ツリー_Kruskal
07最短パス_Dijkstra
08最短パス_Floyd
09トポロジーソート_TopologicalSort
10キーパス_CriticalPath
第8章検索01静的検索_Search
02二叉ソートツリー_BinarySortTree
03バランスツリー_AVLTree
04 Bツリー_BTree
05ハッシュ_HashTable
9章ソート01ソート_Sort
注:1、これは『大話データ構造』という本のノートです.
2、文章が长すぎて、何で検索すればいいですか.
3、一部の重要な知識点は徐々に更新されます.
第3章、リニアメーター
//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)
            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 (ilength)                /*            */
    {
        for(k=i;klength;k++)/*             */
			L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}

/*     :     L    */
/*     :   L          */
Status ListTraverse(SqList L)
{
	int i;
    for(i=0;i=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 && jnext;  /*  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; idata = 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; idata = 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 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; }

第4章、スタックとキュー
//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-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(i0) 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; }

第5章、串
//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; SS[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;iS[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=''; 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]) 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]) 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; }

第6章、木
//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=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; }

第7章、図
//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 numNodes;i++) /* , */ scanf(&G->vexs[i]); for(i = 0;i numNodes;i++) for(j = 0;j numNodes;j++) G->arc[i][j]=INFINITY; /* */ for(k = 0;k 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
//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 adjList[i].in=0;
		(*GL)->adjList[i].data=G.vexs[i];
		(*GL)->adjList[i].firstedge=NULL; 	/*         */
	}
	
	for(i=0;iadjvex=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]
//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
//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(*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 %d",k); /* */ k=P[k][w]; /* */ } printf(" -> %d
",w); /* */ } printf("
"); } printf(" D
"); for(v=0; v
//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 adjList[i].in=0;
		(*GL)->adjList[i].data=G.vexs[i];
		(*GL)->adjList[i].firstedge=NULL; 	/*         */
	}
	
	for(i=0;iadjvex=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; inumVertexes; 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 adjList[i].in=0;
		(*GL)->adjList[i].data=G.vexs[i];
		(*GL)->adjList[i].firstedge=NULL; 	/*         */
	}
	
	for(i=0;iadjvex=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; inumVertexes; i++)                
		if(0 == GL->adjList[i].in) /*     0      */           
			stack[++top]=i;    

	top2=0;    
	etv=(int *)malloc(GL->numVertexes * sizeof(int) ); /*            */    
	for(i=0; inumVertexes; 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; inumVertexes; i++) ltv[i]=etv[GL->numVertexes-1]; /* */ printf("etv:\t"); for(i=0; inumVertexes; 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; inumVertexes; i++) printf("%d -> ",ltv[i]); printf("
"); for(j=0; jnumVertexes; 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; }

第8章、検索
//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 (keya[mid])/*   が  より きい  */
low=mid+1;		/*     き  を    き  に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 (keya[mid])/*   が   より きい  */
low=mid+1;		/*   きズームを    きズームより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;ia[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 (keydata) 
		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 (keydata) 
			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 (keydata)
			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 (edata)
		{ /*      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->keynumnode[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
//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;ielem[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

第9章、並べ替え
//01  _Sort
#include     
#include 
#include       
#include    
#include   
#include   
#include 

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAX_LENGTH_INSERT_SORT 7 /*                     */

typedef int Status; 


#define MAXSIZE 10000  /*             ,        */
typedef struct
{
	int r[MAXSIZE+1];	/*          ,r[0]          */
	int length;			/*            */
}SqList;

/*   L   r    i j   */
void swap(SqList *L,int i,int j) 
{ 
	int temp=L->r[i]; 
	L->r[i]=L->r[j]; 
	L->r[j]=temp; 
}

void print(SqList L)
{
	int i;
	for(i=1;ilength;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;ilength;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;ilength && 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;ilength;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]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]r[i-increment])/*    L->r[i]         */ 
			{ 
				L->r[0]=L->r[i]; /*     L->r[0] */
				for(j=i-increment;j>0 && L->r[0]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(jr[j]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]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(ilength * sizeof(int));/*        */
    int k=1;
	while(klength)
	{
		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(lowr[high]>=pivotkey)
			high--;
		 swap(L,low,high);/*                 */
		 while(lowr[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(lowr[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(lowr[high]>=pivotkey)
			high--;
		 L->r[low]=L->r[high];
		 while(lowr[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(lowr[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