数据结构
|
408复习笔记
|
34

2408 字
|
3.2 小时
本文最后更新于23 天前，其中的信息可能已经过时，如有错误请发送邮件到2213745848@qq.com

外部排序：

总时间=I/O时间+内部排序时间+内部归并时间

优化思路，减少i/o次数:

1.增大k，降低树高，即减少归并排序趟数

2.减少r，减少叶节点个数，即减少归并段个数

r为叶节点个数（归并段个数），h为树高（归并排序趟数S），k为k叉树

败者树：多路平衡归并

败者树：第一次构造时需要两两比较，故需要k-1次比较。

败者树LS[x]节点保存的是败者归并段号，冠军节点LS[0]保存的是胜者的归并段号。

决出一轮胜者以后，对应归并段的下一个元素补位，继续对比

冠军节点不计入树高

置换选择排序：生成初始归并段

每次选择工作区内的比minimax大且最小的数，minimax还需要满足归并段内最大；

满足不了条件则开始下一个归并段

其中选择minimax的过程由败者树实现。

最佳归并树：k叉哈夫曼

代码:

带头结点单链表:

#include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
typedef struct Node
{   
    Elemtype data;
    struct Node* next;
}Node;

typedef Node Node;


//头节点初始化
Node* initList(){
    Node* list=(Node*)malloc(sizeof(Node));
    list->data=0;
    list->next=NULL;
    return list;
}

//头插法
void headInsert(Node* list,int data){
    Node* node=(Node*)malloc(sizeof(Node));
    node->next=list->next;
    node->data=data;
    list->next=node;
    list->data++;
}

//尾插法
void tailInsert(Node* list,int data){
    Node* temp=list;
    while(temp->next){//找到最后一个节点
        temp=temp->next;
    }
    Node* node=(Node*)malloc(sizeof(Node));
    node->next=NULL;
    node->data=data;
    temp->next=node;
    list->data++;
}

void delete(Node* list,int data){
    Node* temp=list;
    while(temp->next){//直到最后一个节点
        if(temp->next->data==data){//如果下一个节点的data值==要找的data
            Node* t=temp->next;//记录下个节点
            temp->next=t->next;//把下个节点从链表中删除
            list->data--;//更新节点数
            free(t);//释放删除掉的节点
        }else{//如果没找到就下一个节点
            temp=temp->next;
        }
    }

}

void printList(Node* list){
    Node* t=list;
    while(t->next){
        t=t->next;
        printf("%d ",t->data);
    }
    printf("\n");
}


//带头结点单链表
int main(){
    Node* list=initList();
    delete(list,1);
    for(int i=0;i<5;i++){
        tailInsert(list,i);
    }
    for(int i=0;i<5;i++){
        headInsert(list,i);
    }
    delete(list,4);
    printList(list);
    return 0;
}

循环队列:

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 6

typedef struct Queue{
    int* data;
    int front;
    int rear;   
}Queue;

//该循环队列最多能放MAXSIZE-1个元素
Queue* initQueue(int n){
    Queue* Q=(Queue*)malloc(sizeof(Queue));
    Q->data=(int*)malloc(sizeof(int)*n);
    Q->front=0;
    Q->rear=0;
    return Q;
}

//若头指针==尾指针,则表示队空
int isEmpty(Queue* Q){
    if(Q->front==Q->rear) return 1;
    return 0;
}

//若(尾指针+1)%MAXSIZE==头指针,则表示队满
int isFull(Queue* Q){
    if((Q->rear+1)%MAXSIZE==Q->front) return 1;
    return 0;
}

int enQueue(Queue* Q,int data){
    if(isFull(Q)) return 0;
    Q->data[Q->rear++]=data;
    Q->rear=(Q->rear+MAXSIZE)%MAXSIZE; //防止越界
    return 1;
}

int deQueue(Queue* Q){
    if(isEmpty(Q)) return 0;
    Q->front++;
    Q->front=(Q->front+MAXSIZE)%MAXSIZE; //防止越界
    return 1;
}

//打印队列
int printQueue(Queue* Q){
    //计算元素个数
    int size=(Q->rear-Q->front+MAXSIZE)%MAXSIZE;
    int index=Q->front;
    for(int i=0;i<size;i++){
        printf("%d ",Q->data[index]);
        index=(index+1)%MAXSIZE;
    }
    printf("\n");
}

int main(){
    Queue* Q = initQueue(MAXSIZE);
    enQueue(Q, 1);
    enQueue(Q, 2);
    enQueue(Q, 3);
    enQueue(Q, 4);
    printQueue(Q);
    deQueue(Q);
    deQueue(Q);
    deQueue(Q);
    deQueue(Q);
    enQueue(Q, 5);
    enQueue(Q, 4);
    enQueue(Q, 3);
    enQueue(Q, 2);
    enQueue(Q, 1);
    printQueue(Q);
    return 0;
}

KMP教科书版

手算时(下标从0开始),next[i]等于前i个字符(0,1,..,i-1)的最长公共前后缀长度

#include<stdio.h>
#include<stdlib.h>

typedef struct String{
    char* data;
    int len;
}String;


String* initString(){
    String* s=(String*)malloc(sizeof(String));
    s->data=NULL;
    s->len=0;
    return s;
}

void stringAssign(String* s,char* data){
    if(s->data){
        free(s->data);
    }
    int len=0;
    char* temp=data;
    while(*temp){
        len++;
        temp++;
    }
    if(len==0){
        s->data=NULL;
        s->len=0;
        
    }else{
        temp=data;
        s->len=len;
        s->data=(char*)malloc(sizeof(char)*(len+1));
        int i;
        for(i=0;i<len;i++,temp++){
            s->data[i]=*temp;
        }
        s->data[i]='\0';
    }

}

void printString(String* s){
    for(int i=0;i<s->len;i++){
        printf(i==0?"%c":"->%c",s->data[i]);
    }
    printf("\n");
}

//next[j]表示回退到指定下标
int* getNext(String* s){
    int* next=(int*)malloc(sizeof(int)*s->len);
    int i=0;//索引
    int j=-1;//值
    next[i]=j; //next[0]=-1;
    while(i<s->len-1){
        if(j==-1||s->data[i]==s->data[j]){
            i++;
            j++;
            next[i]=j;
        }else{
            j=next[j]; 
        }
    }
    return next;
}
//ABACCABABD

void printNext(int* next,int len){
    for(int i=0;i<len;i++){
        printf(i==0?"%d":"->%d",next[i]);
    }
    printf("\n");
}

void kmpMatch(String* master,String* sub,int* next){
    int i=0;
    int j=0;
    while(i<master->len && j<sub->len){
        if(j==-1||master->data[i]==sub->data[j]){
            i++;
            j++;
        }else{
            j=next[j];
        }
    }
    if(j==sub->len){
        printf("kmp match success!\n");
    }else{
        printf("kmp match fail!\n");
    }
}

int main(int argc,char* argv[]){
    String* s=initString();
    String* s1=initString();
    stringAssign(s,"ABACCABABD");
    printString(s);
    stringAssign(s1,"ABAB");
    int* next=getNext(s1);
    printNext(next,s1->len);
    kmpMatch(s,s1,next);

    return 0;
}

//傅哥优化版
#include<stdio.h>
#include<stdlib.h>

typedef struct String{
    char* data;
    int len;
}String;


String* initString(){
    String* s=(String*)malloc(sizeof(String));
    s->data=NULL;
    s->len=0;
    return s;
}

void stringAssign(String* s,char* data){
    if(s->data){
        free(s->data);
    }
    int len=0;
    char* temp=data;
    while(*temp){
        len++;
        temp++;
    }
    if(len==0){
        s->data=NULL;
        s->len=0;
        
    }else{
        temp=data;
        s->len=len;
        s->data=(char*)malloc(sizeof(char)*(len+1));
        int i;
        for(i=0;i<len;i++,temp++){
            s->data[i]=*temp;
        }
        s->data[i]='\0';
    }

}

void printString(String* s){
    for(int i=0;i<s->len;i++){
        printf(i==0?"%c":"->%c",s->data[i]);
    }
    printf("\n");
}

//next[i]记录了i下标之前的i个字符的公共前后缀长度,也可以理解为回退时会跳转的位置
int* getNext(String* s){
    int* next=(int*)malloc(sizeof(int)*s->len);
    int i=0;//索引
    int j=-1;
    next[i]=j; //next[0]=-1;
    while(i<s->len-1){
        //对比下标为i和j的字符若相同则令next[i+1]=j+1,不相同则回退j至上一个公共前后缀长度
        while(j!=-1&&s->data[i]!=s->data[j]) j=next[j];
        printf("i:%d j:%d ",i,j);
        i++;
        j++;
        next[i]=j;
        printf("next[%d]:%d\n",i,next[i]);
    }
    return next;
}
//ABACCABABD

void printNext(int* next,int len){
    for(int i=0;i<len;i++){
        printf(i==0?"%d":"->%d",next[i]);
    }
    printf("\n");
}

void kmpMatch(String* master,String* sub,int* next){
    int i=0;
    int j=0;
    while(i<master->len && j<sub->len){
        while(j!=-1&&master->data[i]!=sub->data[j]) j=next[j];
        i++;
        j++;
    }
    if(j==sub->len){
        printf("kmp match success!\n");
    }else{
        printf("kmp match fail!\n");
    }
}

int main(int argc,char* argv[]){
    String* s=initString();
    String* s1=initString();
    stringAssign(s,"ABABCABABD");
    printString(s);
    stringAssign(s1,"ABABB");
    printString(s1);
    int* next=getNext(s1);
    printNext(next,s1->len);
    kmpMatch(s,s1,next);

    return 0;
}

/**
 * 主串:ABABCABABD
 * 子串:ABABD  i=4时,最长前缀为:AB; 最长后缀为AB,公共前后缀长度为2,next[i]=3;
 * 
 * next数组会记录i之前的最长公共前后缀长度
 * 匹配时,主串的C字符与字串的D字符对应不上,因为字串D处之前有公共前后缀
 * 又因为在C/D之前主串和子串是匹配的
 * 那么肯定能推断出C/D之前主串的后面一部分会等于子串的前面一部分
 * 那么就可以利用next数组进行回退
 * next[j]的值表示失配时会跳转到的位置
 * 设公共前后缀长度为x,那么跳转到的位置正好处于数组的第x+1个
 * 由于数组从0开始,那么跳转位置的下标正好就是x
 * 回退后继续匹配,如果还不行,就继续回退.
 * 
 */

树的应用:

二叉排序树:

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode{
	int data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;

TreeNode* bstSearch(TreeNode* T,int key){
	if(T==NULL){
		return NULL;
	}
	
	if(T->data==key){
		return T;
	}else if(T->data>key){
		return bstSearch(T->lchild,key);
	}else if(T->data<key){
		return bstSearch(T->rchild,key);
	}
}

//TreeNode **T:创建节点的指针的指针,指向节点的指针
//TreeNode *T:创建节点的指针,指向节点
void bstInsert(TreeNode** T,int data){
	if(*T==NULL){
		*T=(TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data=data;
		(*T)->lchild=NULL;
		(*T)->rchild=NULL;
	}else if((*T)->data==data){
		return;
	}else if((*T)->data>data){
		bstInsert(&(*T)->lchild,data);
	}else if((*T)->data<data){
		bstInsert(&(*T)->rchild,data);
	}
}

void inOrder(TreeNode *T){
    if(T==NULL){
        return;
    }
    inOrder(T->lchild);
    printf("%d ",T->data);
    inOrder(T->rchild);
}

int main(){
	TreeNode* g_T=NULL;//节点指针,g_T是根节点的指针,指向根节点;*g_T是根节点
	int nums[6]={4,6,7,5,2,1};
    for(int i=0;i<6;i++){
        bstInsert(&g_T,nums[i]);
    }
    inOrder(g_T);
    
	TreeNode* t=bstSearch(g_T,11);
	if(t!=NULL){
		printf("\n%d",t->data);
	}else{
		printf("\n不存在");
	}

    return 0;
}

平衡二叉树:

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode{
    int data;
    int height;
    struct TreeNode* lchild;
    struct TreeNode* rchild;
}TreeNode;

//初始化一个节点
TreeNode* initNode(int data){
    TreeNode* node=(TreeNode*)malloc(sizeof(TreeNode));
    node->data=data;
    node->height=0;
    node->lchild=NULL;
    node->rchild=NULL;
    return node;
}

int getTreeHeight(TreeNode* T){
    if(T) return T->height;
    else return 0;
}

int getMax(int a,int b){
    return a>b?a:b;
}

//问题节点左旋
void llRolation(TreeNode** T){
    TreeNode* node=(*T)->lchild;
    (*T)->lchild=node->rchild;
    node->rchild=*T;
    (*T)->height=getMax(getTreeHeight((*T)->lchild),getTreeHeight((*T)->rchild))+1;
    *T=node;
    (*T)->height=getMax(getTreeHeight((*T)->lchild),getTreeHeight((*T)->rchild))+1;
}

//问题节点右旋
void rrRolation(TreeNode** T){
    TreeNode* node=(*T)->rchild;
    (*T)->rchild=node->lchild;
    node->lchild=*T;
    (*T)->height=getMax(getTreeHeight((*T)->lchild),getTreeHeight((*T)->rchild))+1;
    *T=node;
    (*T)->height=getMax(getTreeHeight((*T)->lchild),getTreeHeight((*T)->rchild))+1;
}



//平衡二叉树插入
void avlInsert(TreeNode** T,int data){
    if((*T)==NULL){
        *T=initNode(data);
    }else if(data==(*T)->data){
        return;
    }else if(data<(*T)->data){
        avlInsert(&(*T)->lchild,data);
        int l_height=getTreeHeight((*T)->lchild);
        int r_height=getTreeHeight((*T)->rchild);
        //判断失衡,往左边插入,看左边子树有没有比右边子树高2
        if(l_height-r_height>1){
            //判断是ll型还是lr型,如果data比*T左子树的data值要小,则插在了*T左子树的左边
            if(data<(*T)->lchild->data){
                //ll型
                llRolation(T);
            }else{
                //lr型,先让*T的左子树右旋,然后*T再左旋
                rrRolation(&(*T)->lchild);
                llRolation(T);
            }
        }
    }else if(data>(*T)->data){
        avlInsert(&(*T)->rchild,data);
        int l_height=getTreeHeight((*T)->lchild);
        int r_height=getTreeHeight((*T)->rchild);
        //判断失衡
        if(r_height-l_height>1){
            if(data>(*T)->rchild->data){
                //rr型
                rrRolation(T);
            }else{
                //rl型
                llRolation(&(*T)->rchild);
                rrRolation(T);
            }
        }

    }
    //维护当前节点树的高度
    (*T)->height=getMax(getTreeHeight((*T)->lchild),getTreeHeight((*T)->rchild))+1;
}

void preOrder(TreeNode *T){
    if(T==NULL){
        return;
    }
    printf("%d ",T->data);
    preOrder(T->lchild);
    preOrder(T->rchild);
}

int main(){
    TreeNode* T=NULL;
    int nums[5]={1,8,6,7,10};
    for(int i=0;i<5;i++){
        avlInsert(&T,nums[i]);
    }
    preOrder(T);

    printf("\n%d",getTreeHeight(T));
    return 0;
}

哈夫曼树:

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode{
    int parent;
    int lchild;
    int rchild;
    int weight;
}TreeNode;

typedef struct HaffmanTree{
    TreeNode* data;
    int length;
}HaffmanTree;


//初始化
HaffmanTree* initTree(int len,int* nums){
    HaffmanTree* T=(HaffmanTree*)malloc(sizeof(HaffmanTree));
    T->data=(TreeNode*)malloc(sizeof(TreeNode)*(len*2-1));
    T->length=len;
    for(int i=0;i<len;i++){ //初始化原始叶子节点
        T->data[i].lchild=-1;
        T->data[i].rchild=-1;
        T->data[i].parent=-1;
        T->data[i].weight=nums[i];
    }
    return T;
}

//从没有父亲的节点找,找出最小的两个数
int* findMinNum(HaffmanTree* T){
    int* res=(int*)malloc(sizeof(int)*2);
    int min=0x3ffff;
    int second_min=0x3ffff;
    int minIndex;
    int second_minIndex;
    //找出最小数的下标   
    for(int i=0;i<T->length;i++){
        //从没有父亲的节点找
        if(T->data[i].parent==-1){
            if(min>T->data[i].weight){
                min=T->data[i].weight;
                minIndex=i;
            }
        }
    }

    //找出第二小数的下标
    for(int i=0;i<T->length;i++){
        //从没有父亲的节点找
        if(T->data[i].parent==-1&&i!=minIndex){
            if(second_min>T->data[i].weight){
                second_min=T->data[i].weight;
                second_minIndex=i;
            }
        }
    }
    res[0]=minIndex;
    res[1]=second_minIndex;
    return res;
} 

/**
 * haffman树一共会有2n-1个节点,也就是说需要进行n-1轮循环,每次循环找出最小的两个数组成新的节点,会生成n-1个新节点
 */
//构造haffman树
void haffmanTreeGenerate(HaffmanTree** T,int len,int* nums){
    *T=initTree(len,nums);
    int *res;
    //n-1轮循环
    for(int i=len;i<2*len-1;i++){
        //找出最小两个数的下标
        res=findMinNum(*T);
        int minIndex=res[0];
        int second_minIndex=res[1];
        //组成新节点
        (*T)->data[i].weight=(*T)->data[minIndex].weight+(*T)->data[second_minIndex].weight;
        (*T)->data[i].lchild=minIndex;
        (*T)->data[i].rchild=second_minIndex;
        (*T)->data[i].parent=-1;//parent==-1,令其加入下轮找最小值的队伍中
        (*T)->length++;//加入新节点,长度加一
        //更新其parent
        (*T)->data[minIndex].parent=i;
        (*T)->data[second_minIndex].parent=i;
    }
}

void preOrder(HaffmanTree* T,int index){
	if(index!=-1){
		printf("%d ",T->data[index].weight);
		preOrder(T,T->data[index].lchild);
		preOrder(T,T->data[index].rchild);
	}
}

int main(){
    HaffmanTree* T=NULL;
    #define LEN 5
    int nums[LEN]={1,2,3,4,5};
    haffmanTreeGenerate(&T,LEN,nums);
    preOrder(T,T->length-1);
	printf("\n");
	for(int i=0;i<LEN*2-1;i++){
		printf("下标:%d 权重:%d 父亲:%d 左孩子:%d 右孩子:%d\n",i,T->data[i].weight,T->data[i].parent,T->data[i].lchild,T->data[i].rchild);
	}
    return 0;
}

图的构建(邻接矩阵):

#include <stdio.h>
#include <stdlib.h>
#define N 6
#define MAXSIZE 10

typedef struct Graph{
	char* vertexs;
	int** arcs;
	int vertexNum;
	int arcNum;
}Graph;

typedef struct Queue{
    int* data;
    int front;
    int rear;   
}Queue;


Queue* initQueue(int n){
    Queue* Q=(Queue*)malloc(sizeof(Queue));
    Q->data=(int*)malloc(sizeof(int)*n);
    Q->front=0;
    Q->rear=0;
    return Q;
}

int isEmpty(Queue* Q){
    if(Q->front==Q->rear) return 1;
    return 0;
}

int isFull(Queue* Q){
    if((Q->rear+1)%MAXSIZE==Q->front) return 1;
    return 0;
}

int enQueue(Queue* Q,int data){
    if(isFull(Q)) return 0;
    Q->data[Q->rear++]=data;
    Q->rear=(Q->rear+MAXSIZE)%MAXSIZE; //防止越界
    return 1;
}

int deQueue(Queue* Q){
    if(isEmpty(Q)) return -1;
    int x=Q->front;
    Q->front++;
    Q->front=(Q->front+MAXSIZE)%MAXSIZE; //防止越界
    return x;
}

//初始化
Graph* initGraph(int vertexNum){
	Graph* G=(Graph*)malloc(sizeof(Graph));
	G->arcNum=0;
	G->vertexNum=vertexNum;
	G->vertexs=(char*)malloc(sizeof(char)*vertexNum);
	G->arcs=(int**)malloc(sizeof(int*)*vertexNum);
	for(int i=0;i<vertexNum;i++){
		G->arcs[i]=(int*)malloc(sizeof(int)*vertexNum);
	}
	return G;
}

void createGraph(Graph* G,char* vertexs,int *arcs){
    for(int i=0;i<G->vertexNum;i++){
        G->vertexs[i]=vertexs[i];
        for(int j=0;j<G->vertexNum;j++){
            G->arcs[i][j]=*(arcs+i*G->vertexNum+j);
            if(G->arcs[i][j]==1){
                G->arcNum++;
            }
        }
    }
    G->arcNum/=2;
}

void dfs(Graph* G,int* visited,int index){
    visited[index]=1;
    printf("%c ",G->vertexs[index]);
    for(int i=0;i<G->vertexNum;i++){
        if(G->arcs[index][i]==1&&visited[i]==0){
            dfs(G,visited,i);
        }
    }
}

void bfs(Graph* G,int *visited,int index){
    Queue* Q=initQueue(MAXSIZE);
    enQueue(Q,index);//第一个顶点入队
    visited[index]=1;//记录为遍历过的
    while(!isEmpty(Q)){
        index=deQueue(Q);//出队一个顶点
        printf("%c ",G->vertexs[index]);
        for(int i=0;i<G->vertexNum;i++){
            if(G->arcs[index][i]==1&&visited[i]==0){
                enQueue(Q,i);//没遍历过的顶点入队
                visited[i]=1;//记录为遍历过的顶点
            }
        }
    }

}

int main(){
    Graph* G=initGraph(N);
    int arcs[N][N] = {
	    {0,1,1,0,0,0}, // A
	    {1,0,0,1,0,0}, // B
	    {1,0,0,0,1,0}, // C
	    {0,1,0,0,1,1}, // D
	    {0,0,1,1,0,1}, // E
	    {0,0,0,1,1,0}  // F
	};
    createGraph(G,"ABCDEF",(int*)arcs);
    int visited[N];
    for(int i=0;i<N;i++) visited[i]=0;
    dfs(G,visited,0);
    printf("\n");
    for(int i=0;i<N;i++) visited[i]=0;
    bfs(G,visited,0);
	return 0;
}

最小生成树

prim算法

#include <stdio.h>
#include <stdlib.h>

#define N 6
#define MAX 32767

//MAX表示无法到达的距离，0表示自身
typedef struct Graph{
    int vertexNum;
    char* vertexs;
    int arcNum;
    int** arcs;
}Graph;


typedef struct Edge{
    char vertex; //U集合内部距离i最近的点
    int weight;//顶点i加入U集合的开销,开销为0则i表示已经在U集合内部
}Edge;

Edge* initEdge(Graph* G,int index){
    Edge* edge=(Edge*)malloc(sizeof(Edge)*G->vertexNum);
    for(int i=0;i<G->vertexNum;i++){
        edge[i].vertex=G->vertexs[index];
        edge[i].weight=G->arcs[index][i];
    }
    return edge;
}
/* edge.vertex
1 1 1 1 1 1 
1 3 1 1 3 3 
1 3 1 6 3 3 
1 3 1 6 3 3 
1 3 1 6 2 3 
*/
/* edge.weight
0 6 1 5 32767 32767 
0 5 0 5 6 4 
0 5 0 2 6 0 
0 5 0 0 6 0 
0 0 0 0 3 0 
*/

//思想:基于点找边
/**
 * 维护一个U集合,表示局部最优解,
 * 用edge数组实时记录其他节点想要加入U集合需要的开销和距离U集合最近的内部节点,
 * 先把起始点放入U集合,然后从起始点出发,每次找一个加入U集合开销最小的节点,
 * 新的节点加入U集合以后,遍历新加入节点到其他未加入U集合的节点的开销,
 * 如果通过新加入节点去加入U集合开销比原先直接加入U集合开销更小,
 * 则指定这个新加入节点为它距离U集合最近的内部节点,并更新加入需要的开销.
 */
void prim(Graph* G,int index){
    Edge* edge=initEdge(G,index);    //edge[i] 对应 G->vertexs[i]
    for(int i=0;i<G->vertexNum-1;i++){
        int min=MAX;
        int minIndex;
        for(int j=0;j<G->vertexNum;j++){
            //找到j加入U集合开销最小的边和对应的点
            if(min>edge[j].weight&&edge[j].weight!=0){
                min=edge[j].weight;
                minIndex=j;
            }
        }
        printf("v%c->v%c weight:%d\n",edge[minIndex].vertex,G->vertexs[minIndex],min);
        edge[minIndex].weight=0;
        for(int j=0;j<G->vertexNum;j++){
            //维护j加入U集合需要最小的开销和U集合内部距离j最近的点
            if(edge[j].weight>G->arcs[minIndex][j]&&edge[j].weight!=0){
                edge[j].vertex=G->vertexs[minIndex];
                edge[j].weight=G->arcs[minIndex][j];
            }
        }
    }
}

Graph* initGraph(int vertexNum){
    Graph* G=(Graph*)malloc(sizeof(Graph));
    G->vertexNum=vertexNum;
    G->arcNum=0;
    G->vertexs=(char*)malloc(sizeof(char)*vertexNum);
	//类似于二维数组,但内存并不完全连贯
	G->arcs = (int**)malloc(sizeof(int*)*vertexNum); //创建指针数组
	for(int i=0; i < vertexNum;i++){
		G->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); //让指针数组的每一个指针指向一个数组
	}
    return G;
}

void createGraph(Graph* G,char* vertexs,int* arcs){
    for(int i=0;i<G->vertexNum;i++){
        G->vertexs[i]=vertexs[i];
        for(int j=0;j<G->vertexNum;j++){
            G->arcs[i][j]=*(arcs+i*G->vertexNum+j);
            if(G->arcs[i][j]>0 && G->arcs[i][j]!=MAX) G->arcNum++;
        }
    }
    G->arcNum/=2;//无向图中,边会计算两次,真实边数需要除2
}

void dfs(Graph* G,int* visited,int index){
    printf("%c ",G->vertexs[index]);
    visited[index]=1;
    for(int i=0;i<G->vertexNum;i++){
        if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX && visited[i]==0){
            dfs(G,visited,i);
            visited[i];
        }
    }
}

int main(){
    Graph* G=initGraph(N);
	int arcs[N][N] = {
	    {0,6,1,5,MAX,MAX},
        {6,0,5,MAX,3,MAX},
        {1,5,0,5,6,4},
        {5,MAX,5,0,MAX,2},
        {MAX,3,6,MAX,0,6},
        {MAX,MAX,4,2,6,0}
	};
    int visited[N];
    for(int i=0;i<N;i++) visited[i]=0;
    createGraph(G,"123456",(int*)arcs);
    dfs(G,visited,0);
    printf("\n");
    prim(G,0);
    return 0;
}

kruskal算法:

#include <stdio.h>
#include <stdlib.h>

#define N 6
#define MAX 32767

//MAX表示无法到达的距离，0表示自身
typedef struct Graph{
    int vertexNum;
    char* vertexs;
    int arcNum;
    int** arcs;
}Graph;


//边
typedef struct Edge{
	int src;  //起始顶点
	int dst;  //目的顶点
	int weight;  //权值
}Edge;

Edge* initEdge(Graph* G){
    Edge* edge=(Edge*)malloc(sizeof(Edge)*G->arcNum);
    int index=0;
    for(int i=0;i<G->vertexNum;i++){
        for(int j=i+1;j<G->vertexNum;j++){
            if(G->arcs[i][j]>0&&G->arcs[i][j]!=MAX){
                edge[index].src=i;
                edge[index].dst=j;
                edge[index].weight=G->arcs[i][j];
                index++;
            }
        }
    }
    return edge;
}

void sortEdge(Edge* edge,int n){
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(edge[j].weight>edge[j+1].weight){
                Edge t=edge[j];  //c语言中,结构体可以整体拷贝赋值.把整个结构体的内容逐字节复制一份再赋值
                edge[j]=edge[j+1];
                edge[j+1]=t;
            }
        }
    }
}


//若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量
//初始化连通分量
int* initConnectedComponent(Graph* G){
    int* connected=(int*)malloc(sizeof(int)*G->vertexNum);
    for(int i=0;i<G->vertexNum;i++){
        connected[i]=i;  //初始化连通分量编号,让各个顶点的连通分量编号都为自己
    }
    return connected;
}

//思想:基于边构建最小生成树
/**
 * 先把边全部放入Edge数组,按边的权值大小进行从小到大排序.
 * 每个节点都是一个连通分量,为每个顶点赋予不同的连通分量编号
 * 每次找一条权值最小的边,判断边的起点和边的终点是否属于同一个连通分量
 * 若不属于同一个连通分量,则把终点所属的连通分量并入起点所属的连通分量
 */
void kruskal(Graph* G){
    Edge* edge=initEdge(G);
    sortEdge(edge,G->arcNum);
    int* connected=initConnectedComponent(G);
    int cnt=0;//记录找到的边数
    for(int i=0;i<G->arcNum;i++){
        int s_cc=connected[edge[i].src]; //子图1,连通分量编号:s_cc
        int d_cc=connected[edge[i].dst]; //子图2,连通分量编号:d_cc
        if(s_cc!=d_cc){ //如果两个子图的连通分量编号不一致,把d_cc全部并入s_cc
            for(int j=0;j<G->vertexNum;j++){
                if(connected[j]==d_cc){
                    connected[j]=s_cc;
                }
            }
            printf("v%c-->v%c weight:%d\n",G->vertexs[edge[i].src],G->vertexs[edge[i].dst],edge[i].weight);
            cnt++;
            if(cnt==G->vertexNum-1) break;//只需要找(节点数-1次)条边就能构建出最小生成树
        }
    }

}

Graph* initGraph(int vertexNum){
    Graph* G=(Graph*)malloc(sizeof(Graph));
    G->vertexNum=vertexNum;
    G->arcNum=0;
    G->vertexs=(char*)malloc(sizeof(char)*vertexNum);
	//类似于二维数组,但内存并不完全连贯
	G->arcs = (int**)malloc(sizeof(int*)*vertexNum); //创建指针数组
	for(int i=0; i < vertexNum;i++){
		G->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); //让指针数组的每一个指针指向一个数组
	}
    return G;
}

void createGraph(Graph* G,char* vertexs,int* arcs){
    for(int i=0;i<G->vertexNum;i++){
        G->vertexs[i]=vertexs[i];
        for(int j=0;j<G->vertexNum;j++){
            G->arcs[i][j]=*(arcs+i*G->vertexNum+j);
            if(G->arcs[i][j]>0 && G->arcs[i][j]!=MAX) G->arcNum++;
        }
    }
    G->arcNum/=2;//无向图中,边会计算两次,真实边数需要除2
}

void dfs(Graph* G,int* visited,int index){
    printf("%c ",G->vertexs[index]);
    visited[index]=1;
    for(int i=0;i<G->vertexNum;i++){
        if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX && visited[i]==0){
            dfs(G,visited,i);
            visited[i];
        }
    }
}

int main(){
    Graph* G=initGraph(N);
	int arcs[N][N] = {
	    {0,6,1,5,MAX,MAX},
        {6,0,5,MAX,3,MAX},
        {1,5,0,5,6,4},
        {5,MAX,5,0,MAX,2},
        {MAX,3,6,MAX,0,6},
        {MAX,MAX,4,2,6,0}
	};
    int visited[N];
    for(int i=0;i<N;i++) visited[i]=0;
    createGraph(G,"123456",(int*)arcs);
    dfs(G,visited,0);
    printf("\n");
    kruskal(G);
    return 0;
}

最短路径:

dijkstra算法:

找到其他顶点到达起点的最短路径

#include <stdio.h>
#include <stdlib.h>

#define N 6
#define MAX 32767

//MAX表示无法到达的距离，0表示自身
typedef struct Graph{
    int vertexNum;
    char* vertexs;
    int arcNum;
    int** arcs;
}Graph;

//从未加入最短路径集合的节点里找出一个加入集合距离最近的点
int getMinIndex(Graph* G,int* f,int* dist){
    int min=MAX;
    int index;
    for(int i=0;i<G->vertexNum;i++){
        if(min>dist[i]&&!f[i]){
            min=dist[i];
            index=i;
        }
    }
    return index;
}

//思想:实时维护各节点去往起点的最短距离表和前置节点表
//从起点出发,每次加入一个新节点,其他节点都会去尝试通过新节点去到起点
//若发现走新节点距离更近,那么更新最短距离表,并令其成为自己的前置节点
//index:起点
int dijkstra(Graph* G,int index){
    //记录顶点i是否加入最短路径集合
    int* f=(int*)malloc(sizeof(int)*G->vertexNum); 
    //记录任意顶点i到达index的前置节点
    int* pre=(int*)malloc(sizeof(int)*G->vertexNum); 
    //记录任意顶点i到达index的最短距离
    int* dist=(int*)malloc(sizeof(int)*G->vertexNum); 

    //初始化辅助数组
    for(int i=0;i<G->vertexNum;i++){
        f[i]=0;
        if(i==index) f[i]=1;
        pre[i]=-1;
        if(G->arcs[index][i]>0&&G->arcs[index][i]!=MAX) pre[i]=index;
        dist[i]=G->arcs[index][i];
    }

    for(int i=0;i<G->vertexNum-1;i++){
        //找到一个可加入最短路径集合的距离最近的点
        int newIndex=getMinIndex(G,f,dist);
        f[newIndex]=1;
        for(int j=0;j<G->vertexNum;j++){
            //判断通过新加入节点到达index路径的距离是否更短
            if(dist[j]>dist[newIndex]+G->arcs[newIndex][j]&&!f[j]){
                pre[j]=newIndex;//使其成为自己的前置节点
                dist[j]=dist[newIndex]+G->arcs[newIndex][j];//更新距离
            }
        }
    }


    for(int i=0;i<G->vertexNum;i++){
        if(pre[i]==-1){
            printf("vertex:%c 起点 dist:%d\n",G->vertexs[i],dist[i]);
        }else{
            printf("vertex:%c pre:%c dist:%d\n",G->vertexs[i],G->vertexs[pre[i]],dist[i]);
        }
    }
    
}


Graph* initGraph(int vertexNum){
    Graph* G=(Graph*)malloc(sizeof(Graph));
    G->vertexNum=vertexNum;
    G->arcNum=0;
    G->vertexs=(char*)malloc(sizeof(char)*vertexNum);
	//类似于二维数组,但内存并不完全连贯
	G->arcs = (int**)malloc(sizeof(int*)*vertexNum); //创建指针数组
	for(int i=0; i < vertexNum;i++){
		G->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); //让指针数组的每一个指针指向一个数组
	}
    return G;
}

void createGraph(Graph* G,char* vertexs,int* arcs){
    for(int i=0;i<G->vertexNum;i++){
        G->vertexs[i]=vertexs[i];
        for(int j=0;j<G->vertexNum;j++){
            G->arcs[i][j]=*(arcs+i*G->vertexNum+j);
            if(G->arcs[i][j]>0 && G->arcs[i][j]!=MAX) G->arcNum++;
        }
    }
    G->arcNum/=2;//无向图中,边会计算两次,真实边数需要除2
}

void dfs(Graph* G,int* visited,int index){
    printf("%c ",G->vertexs[index]);
    visited[index]=1;
    for(int i=0;i<G->vertexNum;i++){
        if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX && visited[i]==0){
            dfs(G,visited,i);
            visited[i];
        }
    }
}

int main(){
	Graph* G=initGraph(N);
	int arcs[N][N] = {
        { 0,  12, MAX, MAX, MAX, 16, 14 }, // 1
        { 12,  0, 10,  MAX, MAX,  7, MAX }, // 2
        { MAX,10,  0,   3,   5,  6, MAX }, // 3
        { MAX,MAX,3,   0,   4, MAX, MAX }, // 4
        { MAX,MAX,5,   4,   0,  2,  8 }, // 5
        { 16,  7, 6,  MAX,  2,  0,  9 }, // 6
        { 14,MAX,MAX,MAX,  8,  9,  0 }  // 7
	};
    int visited[N];
    for(int i=0;i<N;i++) visited[i]=0;
    createGraph(G,"123456",(int*)arcs);
    dfs(G,visited,0);
    printf("\n");
    dijkstra(G,0);
    return 0;
}

floyd算法:

3for算法

找到各个顶点去往其他各个顶点的最短路径

#include <stdio.h>
#include <stdlib.h>
#define N 4

#define MAX 32727
typedef struct Graph{
	char* vertexs;
	int** arcs;
	int vertexNum;
	int arcNum;
}Graph;

//二维函数传递
//int (*pre)[N]:指向一行的指针,一行有N个int;   int (*pre)[N]等价于int pre[][N]
void findLoad(Graph*G,int pre[][N],int src,int dst){
	
	int i=src;
	int j=dst;
	printf("最短路径:v%c",G->vertexs[dst]);
	while(pre[i][j]!=-1){//一直倒着走,一直走到起点
		int t=pre[i][j];
		printf("->v%c",G->vertexs[t]);
		j=t;
	}
}

//核心:pre数组会记录i到j最短路径上j的前置节点,从终点倒推回起点即可得到最短路径
//思想:三层循环,每次选中一个节点当作中转节点i,
//依次遍历其他各个顶点j能否通过顶点i更近到达其他各个顶点k
//若发现通过i顶点路程更近,那么记录i为j到k的前置节点,并更新最短距离
void floyd(Graph* G){
    int dist[G->vertexNum][G->vertexNum];//记录任意两点之间的最短距离
    int pre[G->vertexNum][G->vertexNum];//记录任意两点之间的前置节点.前置节点:从 i 到 j 的最短路径上，j 的前一个节点
    for(int i = 0;i<G->vertexNum;i++){
		for(int j = 0;j<G->vertexNum;j++){
			dist[i][j]=G->arcs[i][j];
			pre[i][j]=-1;
			if(G->arcs[i][j]>0 && G->arcs[i][j]!=MAX) pre[i][j]=i;
		}
	}

	for(int i = 0;i<G->vertexNum;i++){//i:中转节点
		for(int j = 0;j<G->vertexNum;j++){//j:起点
			for(int k = 0;k<G->vertexNum;k++){//k:终点
				if(j!=i&&k!=i&&j!=k){
					if(dist[j][k]>dist[j][i]+dist[i][k]){
						dist[j][k]=dist[j][i]+dist[i][k];//如果通过中转节点到达目的节点距离更短则更新
						pre[j][k]=pre[i][k];//更新j到k的最短路径上,k的前一个节点
					}
				}
			}
		}
	}
	printf("dist:\n");
	for(int i = 0;i<G->vertexNum;i++){
		for(int j = 0;j<G->vertexNum;j++){
			printf("%d ",dist[i][j]);
		}
		printf("\n");
	}
	printf("pre:\n");
	for(int i = 0;i<G->vertexNum;i++){
		for(int j = 0;j<G->vertexNum;j++){
			printf("%d ",pre[i][j]);
		}
		printf("\n");
	}
	
	findLoad(G,pre,0,2);

}

Graph* initGraph(int vertexNum){
	Graph* G=(Graph*)malloc(sizeof(Graph));
	G->vertexs = (char*)malloc(sizeof(char)*vertexNum);
	
	//类似于二维数组,但内存并不完全连贯
	G->arcs = (int**)malloc(sizeof(int*)*vertexNum); //创建指针数组
	for(int i=0; i < vertexNum;i++){
		G->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); //让指针数组的每一个指针指向一个数组
	}
	G -> vertexNum=vertexNum;
	G -> arcNum=0;
	return G;
}

void createGraph(Graph* G,char* vertexs,int* arcs){
	for(int i=0;i<G->vertexNum;i++){
		G->vertexs[i]=vertexs[i];
		for(int j=0;j<G->vertexNum;j++){
			G->arcs[i][j]=*(arcs + i*G->vertexNum+j);
			if(G->arcs[i][j]!=0&&G->arcs[i][j]!=MAX) G->arcNum++;
		}
	}
	G->arcNum/=2;//无向图中,边会计算两次,真实边数需要除2
}


void dfs(Graph* G,int* visited,int index){
	printf("%c ",G->vertexs[index]);
	visited[index]=1;
	for(int i =0;i<G->vertexNum;i++){
		if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX &&visited[i]==0){
			dfs(G,visited,i);
		}
	}
}


int main(){
	Graph* G=initGraph(N);
	int arcs[N][N] = {
		{0,1,MAX,3},
		{1,0,3,2},
		{MAX,3,0,8},
		{3,2,8,0}
	};
	createGraph(G,"1234",(int*)arcs); 
	int visited[N];
	for(int i=0;i<G->vertexNum;i++){
		visited[i]=0;
	}
	dfs(G,visited,0);
	printf("\n");
	printf("\n");
	floyd(G);
	return 0;
}

拓扑排序:

#include <stdio.h>
#include <stdlib.h>
#define N 6
#define MAX 32727
typedef struct Graph{
	char* vertexs;
	int** arcs;
	int vertexNum;
	int arcNum;
}Graph;

typedef struct Node{
    int data;
    struct Node* next;
}Node;

Node* initStack(){
    Node* stack=(Node*)malloc(sizeof(Node));
    stack->data=0;
    stack->next=NULL;
    return stack;
}

void push(Node* stack,int data){
    Node* newNode=(Node*)malloc(sizeof(Node));
    newNode->next=stack->next;
    newNode->data=data;
    stack->next=newNode;
    stack->data++;
}

int isEmpty(Node* stack){
    if(stack->next==NULL) return 1;
    else return 0;
}

int pop(Node* stack){
    if(isEmpty(stack)) return -1;
    Node* t=stack->next;
    stack->next=t->next;
    stack->data--;
    int data=t->data;
    free(t);
    return data;
}

void findInDegrees(Graph* G,int* inDegrees){
    for(int i=0;i<G->vertexNum;i++){
        inDegrees[i]=0;
    }
    for(int i=0;i<G->vertexNum;i++){
        for(int j=0;j<G->vertexNum;j++){
            if(G->arcs[i][j]>0&&G->arcs[i][j]!=MAX) inDegrees[j]++; //如果被其他节点指向了，入度就加一
        }
    }
}

void topologicalSort(Graph* G){
    Node* stack=initStack();
    int inDegrees[G->vertexNum];//入度数组
    int vertexCount=0;//记录被摘下节点的数量
    int top[G->vertexNum];//保存拓扑排序结果
    findInDegrees(G,inDegrees);

    for(int i=0;i<G->vertexNum;i++){
        if(inDegrees[i]==0){ //摘下当前入度为0的节点
            push(stack,i);
            top[vertexCount++]=i;
        }
    }
    
    while(!isEmpty(stack)){
        int index=pop(stack);
        for(int i=0;i<G->vertexNum;i++){
            if(G->arcs[index][i]>0&&G->arcs[index][i]!=MAX&&inDegrees[i]!=0){
                inDegrees[i]--;  
                if(inDegrees[i]==0){ //摘下当前入度为0的节点
                    push(stack,i);
                    top[vertexCount++]=i;
                }
            }
        }
    }
    for(int i=0;i<vertexCount;i++){
        printf("%c ",G->vertexs[top[i]]);
    }
    printf("\n");
    if(vertexCount==G->vertexNum){
        printf("该图无环路\n");//如果没有环路，所有节点都能被摘下
    }else{
        printf("该图有环路\n");//如果出现环路，就会有节点无法被摘下
    }
}

Graph* initGraph(int vertexNum){
	Graph* G=(Graph*)malloc(sizeof(Graph));
	G->vertexs = (char*)malloc(sizeof(char)*vertexNum);
	
	//类似于二维数组,但内存并不完全连贯
	G->arcs = (int**)malloc(sizeof(int*)*vertexNum); //创建指针数组
	for(int i=0; i < vertexNum;i++){
		G->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); //让指针数组的每一个指针指向一个数组
	}
	G -> vertexNum=vertexNum;
	G -> arcNum=0;
	return G;
}

void createGraph(Graph* G,char* vertexs,int* arcs){
	for(int i=0;i<G->vertexNum;i++){
		G->vertexs[i]=vertexs[i];
		for(int j=0;j<G->vertexNum;j++){
			G->arcs[i][j]=*(arcs + i*G->vertexNum+j);
			if(G->arcs[i][j]!=0&&G->arcs[i][j]!=MAX) G->arcNum++;
		}
	}
}

//有向图中,dfs和bfs不一定能遍历到所有节点,因为可能断掉.
//若要遍历全部节点,可以对未遍历到的节点再次进行dfs/bfs.
void dfs(Graph* G,int* visited,int index){
	printf("%c ",G->vertexs[index]);
	visited[index]=1;
	for(int i=0;i<G->vertexNum;i++){
		if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX &&visited[i]==0){
			dfs(G,visited,i);
		}
	}
}


int main(){
	Graph* G=initGraph(N);
	int arcs[N][N] = {
        { 0, 1, 1, 1, 0, 0 }, // 1
        { 0, 0, 0, 0, 0, 0 }, // 2
        { 0, 1, 0, 0, 1, 0 }, // 3
        { 0, 0, 0, 0, 1, 0 }, // 4
        { 0, 0, 0, 0, 0, 0 }, // 5
        { 0, 0, 0, 1, 1, 0 }  // 6
	};
	createGraph(G,"123456",(int*)arcs); 
	int visited[N];
	for(int i=0;i<G->vertexNum;i++){
		visited[i]=0;
	}
	dfs(G,visited, 0);
	printf("\n");
    topologicalSort(G);
	return 0;
}

关键路径:

#include <stdio.h>
#include <stdlib.h>
#define N 9

#define MAX 32727
typedef struct Graph{
	char* vertexs;
	int** arcs;
	int vertexNum;
	int arcNum;
}Graph;

typedef struct Node{
    int data;
    struct Node* next;
}Node;

Node* initStack(){
    Node* stack=(Node*)malloc(sizeof(Node));
    stack->data=0;
    stack->next=NULL;
    return stack;
}

void push(Node* stack,int data){
    Node* newNode=(Node*)malloc(sizeof(Node));
    newNode->next=stack->next;
    newNode->data=data;
    stack->next=newNode;
    stack->data++;
}

int isEmpty(Node* stack){
    if(stack->next==NULL) return 1;
    else return 0;
}

int pop(Node* stack){
    if(isEmpty(stack)) return -1;
    Node* t=stack->next;
    stack->next=t->next;
    stack->data--;
    int data=t->data;
    free(t);
    return data;
}

int* findInDegrees(Graph* G){
    int *inDegrees=(int*)malloc(sizeof(int)*G->vertexNum); //统计每个节点的入度
    for(int i=0;i<G->vertexNum;i++){
        inDegrees[i]=0;   
    }
    for(int i=0;i<G->vertexNum;i++){
        for(int j=0;j<G->vertexNum;j++){
            if(G->arcs[i][j]&&G->arcs[i][j]!=MAX){ //被其他节点指向了,则入度++
                inDegrees[j]++; 
            } 
        }    
    }
    return inDegrees;
}

int* topologicalSort(Graph* G){
    int *inDegrees=findInDegrees(G);
    int count=0;  //记录被摘下的节点个数
    // for(int i=0;i<G->vertexNum;i++){
    //     printf("%d ",inDegrees[i]);
    // }

    //用栈优化
    Node* stack=initStack();
    int *top=(int*)malloc(sizeof(int)*G->vertexNum);//顺序保存出栈后的节点索引
    for(int i=0;i<G->vertexNum;i++){
        if(inDegrees[i]==0){  //找到入度为0的点,入栈
            push(stack,i);
        }
    }
    while(!isEmpty(stack)){
        int vertex=pop(stack);
        top[count++]=vertex;
        for(int i=0;i<G->vertexNum;i++){
            if(G->arcs[vertex][i]&&G->arcs[vertex][i]!=MAX){
                inDegrees[i]--;
                if(inDegrees[i]==0) push(stack,i);
            }
        }
    }

    for(int i=0;i<G->vertexNum;i++){
        printf("%c ",G->vertexs[top[i]]);
    }

    if(count<G->vertexNum) printf("\n该图有环路");
    else printf("\n该图无环路");
    printf("\n");
    return top;
}

Graph* initGraph(int vertexNum){
	Graph* G=(Graph*)malloc(sizeof(Graph));
	G->vertexs = (char*)malloc(sizeof(char)*vertexNum);
	
	//类似于二维数组,但内存并不完全连贯
	G->arcs = (int**)malloc(sizeof(int*)*vertexNum); //创建指针数组
	for(int i=0; i < vertexNum;i++){
		G->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); //让指针数组的每一个指针指向一个数组
	}
	G -> vertexNum=vertexNum;
	G -> arcNum=0;
	return G;
}

void createGraph(Graph* G,char* vertexs,int* arcs){
	G->vertexs=vertexs; //直接把指向的地址复制给G->vertexs
    for(int i=0;i<G->vertexNum;i++){
		for(int j=0;j<G->vertexNum;j++){
			G->arcs[i][j]=*(arcs + i*G->vertexNum+j);
			if(G->arcs[i][j]!=0&&G->arcs[i][j]!=MAX) G->arcNum++;
		}
	}
	G->arcNum/=2;//无向图中,边会计算两次,真实边数需要除2
}


void dfs(Graph* G,int* visited,int index){
	printf("%c ",G->vertexs[index]);
	visited[index]=1;
	for(int i =0;i<G->vertexNum;i++){
		if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX &&visited[i]==0){
			dfs(G,visited,i);
		}
	}
}

//找到顶点在top数组中的位置返回
int getIndex(Graph* G,int* top,int vertex){
    int j;
    for(j=0;j<G->vertexNum;j++){
        if(top[j]==vertex) break;
    }
    return j;
}

void criticalPath(Graph* G){
    int* top=topologicalSort(G);
    int* early = (int*)malloc(sizeof(int)*G->vertexNum);//记录各个节点最早发生时间，元素顺序与top数组相对应
    int* late = (int*)malloc(sizeof(int)*G->vertexNum);//记录各个节点最晚发生时间，元素顺序与top数组相对应
    for(int i=0;i<G->vertexNum;i++){
        early[i]=0;
        late[i]=0;
    }
    //1.计算事件指标
    //计算top[i]节点最早开始时间,即所有前驱节点的最晚完成时间
    for(int i=1;i<G->vertexNum;i++){ //拓扑序列，这里的i对应top数组的索引
        int max=0;
        for(int j=0;j<G->vertexNum;j++){ //节点j
            if(G->arcs[j][top[i]]>0&&G->arcs[j][top[i]]!=MAX){
                int index=getIndex(G,top,j); //找到前驱节点在top序列的索引值
                if(max<early[index]+G->arcs[j][top[i]]){
                    max=early[index]+G->arcs[j][top[i]];
                }
            }
        }
        early[i]=max;
    }

    for (int i = 0; i < G ->vertexNum; i++) {
        printf("%d ", early[i]);
    }
    printf("\n");

    //计算top[i]节点最晚开始时间,即不耽误所有后续节点按时执行的最晚开始时间
    late[G->vertexNum-1]=early[G->vertexNum-1];//赋初值,下面循环可以从倒数第二个节点开始
    for(int i=G->vertexNum-2;i>=0;i--){ //逆拓扑排序的序列,i对应top数组的索引
        int min=MAX;
        for(int j=0;j<G->vertexNum;j++){ //节点j
            if(G->arcs[top[i]][j]>0&&G->arcs[top[i]][j]!=MAX){
                int index=getIndex(G,top,j); //找到后继节点在top序列的索引值
                if(min>late[index]-G->arcs[top[i]][j]){
                    min=late[index]-G->arcs[top[i]][j];
                }
            }
        }
        late[i]=min;
    }

    for (int i = 0; i < G ->vertexNum; i++) {
        printf("%d ", late[i]);
    }
    //2.找关键活动
    for (int i = 0; i < G ->vertexNum; i++) { //节点i
        for (int j = 0; j < G ->vertexNum; j++) { //节点j
            if(G->arcs[i][j]>0&&G->arcs[i][j]!=MAX){
                int start=getIndex(G,top,i);//找到i节点在top数组的位置
                int end=getIndex(G,top,j);//找到j节点在top数组的位置
                int earlyTime=early[start]; //活动最早完成时间
                int lateTime=late[end]-G->arcs[i][j]; //活动最晚完成时间
                if(earlyTime==lateTime) printf("\n关键活动:v%c->v%c", G->vertexs[i],G->vertexs[j]);
            }
        }
    }
    printf("\n");
}

int main(){
	Graph* G=initGraph(N);
	int arcs[N][N] = {
 /*V0*/ {0,6,4,5,MAX,MAX,MAX,MAX,MAX},
 /*V1*/ {MAX,0,MAX,MAX,1,MAX,MAX,MAX,MAX},
 /*V2*/ {MAX,MAX,0,MAX,1,MAX,MAX,MAX,MAX},
 /*V3*/ {MAX,MAX,MAX,0,MAX,2,MAX,MAX,MAX},
 /*V4*/ {MAX,MAX,MAX,MAX,0,MAX,9,7,MAX},
 /*V5*/ {MAX,MAX,MAX,MAX,MAX,0,MAX,4,MAX},
 /*V6*/ {MAX,MAX,MAX,MAX,MAX,MAX,0,MAX,2},
 /*V7*/ {MAX,MAX,MAX,MAX,MAX,MAX,MAX,0,4},
 /*V8*/ {MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX,0}
	};
	createGraph(G,"012345678\0",(int*)arcs); 
	int visited[N];
	for(int i=0;i<G->vertexNum;i++){
		visited[i]=0;
	}
	dfs(G,visited,0);
	printf("\n");
    criticalPath(G);
	return 0;
}

B树:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//B树节点
typedef struct Node{
    //阶数m
    int level; 
    //关键字个数
    int keyNum;
    //孩子个数
    int childNum;
    //关键字数组,长度为level+1,下标从1到level-1,第0个和第level个预留
    int* keys; 
    //父亲
    struct Node* parent;
    //孩子指针数组
    struct Node** children;
}Node;

//初始化节点
Node* initNode(int level){
    Node* node=(Node*)malloc(sizeof(Node));
    node->level=level;
    node->keyNum=0;
    node->childNum=0;
    node->keys=(int*)malloc(sizeof(int)*(level+1));
    node->parent=NULL;
    node->children=(Node**)malloc(sizeof(Node*)*level);
    for(int i=0;i<node->level;i++){
        node->keys[i]=0;
        node->children[i]=NULL;
    }
    //node->keys[level]=0;
    return node;
}

//找到节点合适的插入位置
int findSuiteIndex(Node* node,int data){
    int index;
    for(index=1;index<=node->keyNum;index++){
        //找到有比自己大的关键字就退出循环
        if(data < node->keys[index]) break;
    }
    return index;//1到m
}

//B树的每个节点的孩子指针个数会比关键字数多一个
//找到合适的叶子节点. B树中叶子节点都在同一层
Node* findSuiteLeafNode(Node* T,int data){
    if(T->childNum==0){
        return T;
    }else{
        int index=findSuiteIndex(T,data);
        return findSuiteLeafNode(T->children[index-1],data);//index-1:0到m-1
    }
}


//添加数据
void addData(Node* node,int data,Node** T){
    int index=findSuiteIndex(node,data);
    //为新数据挪位置
    for(int i=node->keyNum;i>=index;i--){
        node->keys[i+1]=node->keys[i];
    }
    //填入新数据
    node->keys[index]=data;
    node->keyNum++;
    //关键字超出上限,x>m-1
    //进行分裂
    if(node->keyNum==node->level){
        /**
         * 1.分裂出两边子节点
         */
        //找出mid关键字位置
        int mid=node->level/2+node->level%2;
        //新建一个左孩子节点,初始化
        Node* lchild=initNode(node->level);
        //新建一个右孩子节点,初始化
        Node* rchild=initNode(node->level);
        
        //给mid左边孩子节点赋值
        for(int i=1;i<mid;i++){
            addData(lchild,node->keys[i],T);
        }
        //给mid右边孩子节点赋值
        for(int i=mid+1;i<=node->keyNum;i++){
            addData(rchild,node->keys[i],T);
        }

        //把mid左边的孩子交给左孩子
        for (int i = 0; i < mid; i++) {
            lchild -> children[i] = node -> children[i];
            if (node -> children[i] != NULL) {
                node -> children[i] -> parent = lchild;
                lchild -> childNum ++;
            }
        }

        //把mid右边的孩子交给右孩子'
        for(int i=mid;i<node->childNum;i++){
            rchild->children[i-mid]=node->children[i];
            if(node->children[i]!=NULL){
                node->children[i]->parent=rchild;
                rchild->childNum++;
            }
        }
        /**
         * 2.把中间关键字顶上去当新爹,为两边子节点设置新爹,弃用当前节点
         */
        //如果当前节点是否是根节点
        if(node->parent==NULL){
            //若是根节点则建立新爹,令新爹成为新的根节点
            Node* newParent=initNode(node->level);
            addData(newParent,node->keys[mid],T);
            newParent->children[0]=lchild;
            newParent->children[1]=rchild;
            lchild->parent=newParent;
            rchild->parent=newParent;
            newParent->childNum=2;
            *T=newParent;
        }else{
            //若不是根节点,mid会进入爹节点成为新爹,需要维护爹节点
            int index=findSuiteIndex(node->parent,node->keys[mid]);
            lchild->parent=node->parent;
            rchild->parent=node->parent;
            node->parent->children[index-1]=lchild;
            if(node->parent->children[index]!=NULL){
                for(int i=node->parent->childNum-1;i>=index;i--){//孩子指针数组挪位置
                    node->parent->children[i+1]=node->parent->children[i];
                }
            }
            node->parent->children[index]=rchild;
            node->parent->childNum++;
            addData(node->parent,node->keys[mid],T);
        }
        free(node);//弃用当前节点
    }
}

//B数的插入操作都在叶子节点完成
//找到合适的叶子节点,把关键字插入该节点
void insert(Node** T, int data) {
    Node* node = findSuiteLeafNode(*T, data);
    addData(node, data, T);
}

void printTree(Node* T){
    if(T!=NULL){
        for(int i=1;i<=T->keyNum;i++){
            printf("%d ",T->keys[i]);
        }
        printf("\n");
        for(int i=0;i<T->childNum;i++){
            printTree(T->children[i]);
        }
    }
}

Node* find(Node* node,int data){
    if(node==NULL){
        return NULL;
    }
    int i;
    for(i=1;i<=node->keyNum;i++){
        if(node->keys[i]==data) return node;
        if(data<node->keys[i]) break;//遇到一个比自己大的关键字就退出,确认下降方向
    }
    if(node->childNum==0) return NULL; //找到叶子节点都没找到,
    return find(node->children[i-1],data);
}

int main(){
    clock_t start, end;
    start = clock();   // 记录开始时间
    Node* T = initNode(5);
    insert(&T, 1);
    insert(&T, 2);
    insert(&T, 6);
    insert(&T, 7);
    insert(&T, 11);
    insert(&T, 4);
    insert(&T, 8);
    insert(&T, 13);
    insert(&T, 10);
    insert(&T, 5);
    insert(&T, 17);
    insert(&T, 9);
    insert(&T, 16);
    insert(&T, 20);
    insert(&T, 3);
    insert(&T, 12);
    insert(&T, 14);
    insert(&T, 18);
    insert(&T, 19);
    insert(&T, 15);
    printTree(T);
    Node* node=find(T,7);
    for(int i=1;i<=node->keyNum;i++){
        printf("%d ",node->keys[i]);
    }
    printf("\n");
    end = clock();     // 记录结束时间
    double time_used = (double)(end - start) / CLOCKS_PER_SEC;
    printf("running time:%f second\n", time_used);
    return 0;
}
文末附加内容
复习笔记
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
计算机组成原理

							
							

							
操作系统

							
							

							
计算机网络