
本文共 21063 字,大约阅读时间需要 70 分钟。
���
������������(Graph)���������������������������������������������������������������������������������������G(V,E)������������G������������������V������G���������������������E������G������������������
������������������������������������������������������������������������������������������������(Vertex)���
������������������������������������������������������������������������������������������������������������������V������������������
���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������
���������������������Vi���Vj������������������������������������������������������(Edge)���������������(Vi���Vj)������������
������������������������Vi���Vj������������������������������������������������������������(Arc)���������������<Vi���Vj>������������Vi���������������Vj���������������
���������������������������������������������������������������������������������������������������������������������������������������
������������������������������������������������������������������������������������������������������������������������n������������������������������n(n-1)/2���������
���������������������������������������������������������������������������������������������������������������������������������������������������n������������������������������n(n-1)���������
������������������������������������������������������n*logn(n������������������)������������������������������������������������
���(Weight)���������������������������������������������������������������(Network)���
���������������������������������
������������������������������������������������������������������������������������������������������������������n���������������������������������������������n-1���������
������������������
������������������������������������������
#include#include #define X 8#define Y 8int chess[X][Y];// ������������(x,y)���������������������������������int nextxy(int *x, int *y, int count){ switch(count) { case 0: if( *x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0 ) { *x = *x + 2; *y = *y - 1; return 1; } break; case 1: if( *x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0 ) { *x = *x + 2; *y = *y + 1; return 1; } break; case 2: if( *x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0 ) { *x = *x + 1; *y = *y - 2; return 1; } break; case 3: if( *x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0 ) { *x = *x + 1; *y = *y + 2; return 1; } break; case 4: if( *x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0 ) { *x = *x - 2; *y = *y - 1; return 1; } break; case 5: if( *x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0 ) { *x = *x - 2; *y = *y + 1; return 1; } break; case 6: if( *x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0 ) { *x = *x - 1; *y = *y - 2; return 1; } break; case 7: if( *x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0 ) { *x = *x - 1; *y = *y + 2; return 1; } break; default: break; } return 0;}void print(){ int i, j; for( i=0; i < X; i++ ) { for( j=0; j < Y; j++ ) { printf("%2d\t", chess[i][j]); } printf("\n"); } printf("\n");}// ������������������������// (x,y)���������������// tag���������������������������������tag+1int TravelChessBoard(int x, int y, int tag){ int x1=x, y1=y, flag=0, count=0; chess[x][y] = tag; // ������tag==X*Y��������������������������������� if( tag == X*Y ) { print(); return 1; } flag = nextxy(&x1, &y1, count); while( 0==flag && count < 7 ) { count++; flag = nextxy(&x1, &y1, count); } while( flag ) { if( TravelChessBoard(x1, y1, tag+1) ) { return 1; } x1 = x; y1 = y; count++; flag = nextxy(&x1, &y1, count); while( 0==flag && count < 7 ) { count++; flag = nextxy(&x1, &y1, count); } } if( 0 == flag ) { chess[x][y] = 0; } return 0;}int main(){ int i, j; clock_t start, finish; start = clock(); for( i=0; i < X; i++ ) { for( j=0; j < Y; j++ ) { chess[i][j] = 0; } } if( !TravelChessBoard(2, 0, 1) ) { printf("������������������������������~\n"); } finish = clock(); printf("\n������������������������: %f���\n\n", (double)(finish-start)/CLOCKS_PER_SEC); return 0;}
������������������
������������������(BreadthFirstSearch)������������������������������������BFS���
//���������������������������������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
Prim������
������������������������������������������������������������������������������������������������������������������������������������
//Prim���������������������������void MiniSpanTree_Prim(MGraph G){ int min, i, j, k; int adjvex[MAXVEX]; //������������������������ int lowcost[MAXVEX]; //��������������������������������� lowcost[0] = 0; //V0���������������������������������������������������0 adjvex[0] = 0; //V0��������������� //��������������� for(i = 1; j < G.numVertexes; i++ ) { lowcost[i] = G.arc[0][i]; //������������������0������������������������������ adjvex[i] = 0; //���������������������V0��������� } //������������������������������������ for(i=1; i < G.numVertexes; i++ ) { min = INFINITY; //������������������������65535������������������ j = 1; k = 0; //������������������ while( j < G.numVertexes ) { //������lowcost������������������������������ if( lowcost[j] != 0 && lowcost[j] < min ) { min = lowcost[j]; k = j; //���������������������������������������k��������������� } j++; } //������������������������������������������ printf("(%d, %d)", adjvex[k], k); lowcost[k] = 0; //���������������������������������0������������������������������������������������������������������ //������������k��������������������������� for( j=1; j< G.numVertexes; j++ ) { if( lowcost[j] != 0 && G.arc[k][j] < lowcost[j] ) { lowcost[j] = G.arc[k][j]; adjvex[j] = k; } } }}
Kruskal���������������������������
//Kruskal���������������������������int Find( int *parent, int f){ while(parent[f] > 0 ) { f = parent[f]; } return f;}void MiniSpanTree_Kruskal(MGraph G){ int i, n, m; Edge edges[MAGEDGE]; //������������������ int parent[MAXVEX]; //������parent��������������������������������������������� for( i=0; i < G.numVertexes; i++ ) { parent[i] = 0; } 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); } }}
���������������������
#define MAXVEX 9#define INFINITY 65535typedef int Patharc[MAXVEX]; //���������������������������������������typedef int ShortPathTable[MAXVEX]; //���������������������������������������������void ShortestPath_Dijkstar(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] = 0; //���������������������P���0 } (*D)[V0] = 0; //v0���v0������������0 final[V0] = 1; //v0���v0������������������ //������������������������������V0���������v��������������������� for( v=1; v < G.numVertexes; v++ ) { min = INFINITY; for( w=0; w < G.numVertexes; w++ ) { if( !final[w] && (*D)[w] < min ) { k = w; min = (*D)[w]; } } final[k] = 1; //������������������������������������1 //��������������������������������� for( w=0; w < G.numVextes; w++ ) { //������������v��������������������������������������������������������������� if( !final[w] && (min+G.arc[k][w] < (*D)[w]) ) { (*D)[w] = min +G.arc[k][w]; //������������������������ (*p)[w] = k; //������������������ } } }}
floyd������
typedef int Pathmatrirx[MAXVEX][MAXVEX];typedef int ShortPathTable[MAXVEX][MAXVEX];void ShortestPath_Floyd(MGraph G, Pathmatrirx *P, ShortPathTable *D){ int v, w, k; //���������D���P for( v=0; v < G.numVertexes; v++ ) { for( w=0; w < G.numVertexes; w++ ) { (*D)[v][w] = G.matrix[v][w]; (*P)[v][w] = w; } } //������������������ 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] ) { (*D)[v][w] = (*D)[v][k] + (*D)[k][w]; (*P)[v][w] = (*P)[v][k]; } } } }}
������������
������������������������������������������Directed Acyclic Graph)���������DAG������
���������������������������������������������������������������������������������������������������������������������������������������������������������������AOV���(Active On Vertex Network)���
// ������������������typedef struct EdgeNode{ int adjvex; 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;// ������������������// ���GL������������������������������������������������OK���������������ERRORStatus 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 ) { stack[++top] = i; // ���������0��������������������� } } while( 0 != top ) { gettop = stack[top--]; // ������ printf("%d -> ", GL->adjList[gettop].data); count++; for( e=GL->adjList[gettop].firstedge; e; e=e->next ) { k = e->adjvex; // ���������������������if��������������������������������������� // ���k���������������������������-1��������������������������������� // ������������-1������������������0������������0������������ if( !(--GL->adjList[k].in) ) { stack[++top] = k; } } } if( count < GL->numVertexes ) // ������count��������������������������������� { return ERROR; } else { return OK; }}
������������
// ������������������typedef struct EdgeNode{ int adjvex; 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;int *etv, *ltv;int *stack2; // ������������������������������int top2; // ������stack2���������������// ������������������// ���GL������������������������������������������������OK���������������ERRORStatus 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 ) { stack[++top] = i; // ���������0��������������������� } } // ���������etv������0 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)); while( 0 != top ) { gettop = stack[top--]; // ������ // printf("%d -> ", GL->adjList[gettop].data); stack2[++top2] = gettop; // ������������������������ C1 C2 C3 C4 .... C9 count++; for( e=GL->adjList[gettop].firstedge; e; e=e->next ) { k = e->adjvex; // ���������������������if��������������������������������������� // ���k���������������������������-1��������������������������������� // ������������-1������������������0������������0������������ if( !(--GL->adjList[k].in) ) { stack[++top] = k; } if( (etv[gettop]+e->weight) > etv[k] ) { etv[k] = etv[gettop] + e->weight; } } } if( count < GL->numVertexes ) // ������count��������������������������������� { return ERROR; } else { return OK; }}// ������������������GL���������������������GL���������������������void CriticalPath(GraphAdjList GL){ EdgeNode *e; int i, gettop, k, j; int ete, lte; // ���������������������������������������etv���stack2������ TopologicalSort(GL); // ���������ltv��������������������� ltv = (int *)malloc(GL->numVertexes*sizeof(int)); for( i=0; i < GL->numVertexes; i++ ) { ltv[i] = etv[GL->numVertexes-1]; } // ������������������������������ltv while( 0 != top2 ) { gettop = stack2[top2--]; // ��������������������������������� for( e=GL->adjList[gettop].firstedge; e; e=e->next ) { k = e->adjvex; if( (ltv[k] - e->weight) < ltv[gettop] ) { ltv[gettop] = ltv[k] - e->weight; } } } // ������etv���ltv���ete���lte for( j=0; j < GL->numVertexes; j++ ) { 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 Search_Bin(int a[], int n, int target)//a[0]���������a[1]~a[n]������������{ int low = 1; int high = n; while(low <= high) { int mid = low + (high - low) / 2; if(a[mid] == target) return mid; else if(a[mid] > target) high = mid - 1; else low = mid + 1; } return 0;}
������������������(���������������������)
public static int MaxSize=20; //������������������������������������ //������������������������ public static int[] fib(){ int[] f=new int[MaxSize]; f[0]=1; f[1]=1; for (int i=2;if[k]-1){ //���������f[k]���arr���������������������������������������������������-1���������������������������(���������������������������������������-1) k++; } int[] temp=Arrays.copyOf(arr,f[k]); //��������������������������������������������������������������������������������������������������������������������������������������������� //������������ for (int i=right+1;i temp[mid]){ left=mid+1; k-=2; }else { if (mid
������������������
���������������
//������������������//������������������������������������������typedef struct BiTNode{ int data; struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;//���������������������������T���������������key//������f������T������������������������������������NULL//���������������������������p���������������������������������������TRUE//������������p������������������������������������������������������������FALSEStatus 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���������������FALSEStatus 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 ) //������������key { *T = s; //������s������������������ } else if( key < p->data ) { p->lchild = s; //������s������������ } else { p->rchild = s; //������s������������ } return TRUE; } else { return FALSE; //��������������������������������������������������� }}
//���������������Status DeleteBST(BiTree *T, int key){ if( !*T ) { return FALSE; } else { if( key == (*T)->data ) { return Delete(T); } else if( key < (*T)->data ) { return DeleteBST(&(*T)->lchild, key); } else { return DeleteBST(&(*T)->rchild, key); } }}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; if( q != *p) { q->rchild = s->lchild; } else { q->lchild = s->lchild; } free(s); } return TRUE;}
���������������
//AVL#define LH 1#define EH 0#define RH -1typedef struct BiTNode{ int data; int bf; struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;void R_Rotate(BiTree *p){ BiTree L; L = (*p)->lchild; (*p)->lchild = L->rchild; L->rchild = (*p); *p = L;}void LeftBalance(BiTree *T){ BiTree L, Lr; L = (*T)->lchild; switch(L->bf) { case LH: (*T)->bf = L->bf = EH; R_Rotate(T); break; case RH: Lr = L->rchild; switch(Lr->bf) { 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); R_Rotate(T); break; }}int InsertAVL(BiTree *T, int e, int *taller){ if( !*T ) { *T = (BiTree)malloc(sizeof(BiTNode)); (*T)->data = e; (*T)->lchild = (*T)->rchild = NULL; (*T)->bf = EH; *taller = TRUE; } else { if(e == (*T)->data) { *taller = FALSE; return FALSE; } if(e < (*T)->data) { if(!InsertAVL(&(*T)->lchild, e, taller)) { return FALSE; } if(*taller) { switch((*T)->bf) { case LH: LeftBalance(T); *taller = FALSE; break; case EH: (*T)->bf = LH; *taller = FALSE; break; case RH: (*T)->bf = EH; *taller = FALSE; break; } } } else { if(!InsertAVL(&(*T)->rchild, e, taller)) { return FALSE; } if(*taller) { switch((*T)->bf) { case LH: (*T)->bf = EH; *taller = FALSE; break; case EH: (*T)->bf = RH; *taller = TRUE; break; case RH: RightBalance(T); *taller = FALSE; break; } } }}
���������(���������)������
- ���������������������������
- ������������������������������������������������������������������������
- ������������������������������������������������������������������������������������������������������������������������������
发表评论
最新留言
关于作者
