xiao's blog

1234567891011121314151617181920212223242526272829303132333435void dijkstra(int graph[][6],int len,int start){ int isshort[len];/*记录是否找到最短路径*/ int dis[len]; int path[len];/*recode pre node*/ for(int i=0;i<len;i++){ dis[i]=graph[start][i]; if(graph[start][i]!=INF) path[i]=start; else path[i]=-1; isshort[i]=0; } isshort[start]=1; for(int i=0;i<len;i++){ int min=INF; int minindex=-1; for(int j=0;j<len;j++){ if(isshort[j]!=1&&dis[j]<min){ ...

程序的虚拟地址空间 函数的调用依赖于栈。调用函数，栈增加。函数返回，栈缩小 函数调用栈区栈底处于高地址，减小栈指针，分配栈空间。增加栈指针对应Pop操作，减小栈指针对应Push操作 参数传递函数的参数是存储在寄存器中的，分别存储在di，si，dx，cx，r8,r9寄存器中。如果函数的参数大于6，超过的部分需要使用栈来进行传递 局部变量12345678long caller() { long argl = 534; long arg2 = 1057; long sum= swap_add(&argl, &arg2); long diff = argl -arg2; return sum* diff; } 对应汇编代码 12subq $16, %rsp movq $534, (%rsp) 创建局部变量 栈帧每个函数会有栈帧

实现思路 将图中的边按从小到大的顺序排列 遍历边所在的数组 如果边的两个顶点不存在于同一集合，则将两点所在的集合合并，两点连通 否则跳过 模拟过程 按边从小到大排序，构建辅助数组 算法实现克鲁斯卡尔算法需要一个辅助数组，数据元素结构如下 12345typedef struct Edge{ int head; int tail; int weight;}Edge; Edges数组需要根据边的长度weight从小到大进行排序,排序的算法如下 123456789101112131415161718/*快速排序*/void Sort(struct Edge edges[],int l,int r){ if (l >= r) return; int i=l-1; int j=r+1; int mid=edges[(l+r)/2].weight; while(i<j){ while(edges[++i].weight<mid); while(edges[-- ...

并查集并查集的数据结构 1int S[MAXSIZE]; 查询元素所在的集合 1234567int Find(int sets[],int x){ int index=x; while(sets[index]!=-1){ index=sets[index]; } return index;} 合并两个集合 1234void Union(int sets[],int root1,int root2){ if(root1==root2) return; sets[root2]=root1;} 并查集和优化Union优化123456789101112131415161718/*将两个根节点所在的集合合并集合*/void UnionSets(int sets[],int root1,int root2){ if(root1==root2) return; if(sets[root1]>=sets[root2]){ ...

算法介绍普利姆算法是一种图算法，用于构建最小生成树。最小生成树的顶点全部连通，即沿任意顶点出发，可以达到图的全部顶点，且其所有边的权值最小。 算法描述: 从最小生成树集合中选择边权值最小且不在生成树集合中的顶点加入最小生成树集合，重复上述操作直到全部的点加入最小生成树集合。 算法实现现有5个村落(编号为0-4)需要在各个村庄中修路，使各村庄联通，且代价最小。 这里我们使用邻接矩阵来表示上图 普利姆算法执行过程实现普利姆算法需要利用两个辅助数组lowcost和edge。 lowcost数组用于保存最小生成树集合到各顶点的距离，数组索引与顶点相关联。l例如owcost[3]表示最小生成树集合到顶点4的距离 如果数组中元素值为0则表示顶点存在于最小生成树集合，否则表示权值大小。 edge用于存储顶点的边关系，edge[1]=2表示与节点1与节点2相连。 12int lowcost[graph->vexnum];int edge[graph->vexnum]; 执行过程： 选定一个节点加入最小生成树集合,初始化lowcost和edge数组 重复下面3的步骤， ...

在查找过程中应该尽量避免哈希冲突

图的遍历包括广度优先搜索和深度优先搜索。 广度优先搜索广度优先搜索类似于树的层次遍历，利用队列实现 队列结构设计： 12345typedef struct QueueNode{ struct AdjNode* node; /*顶点*/ struct QueueNode* next; struct QueueNode* pre;}QueueNode; 队列相关操作 123456789101112131415161718192021222324252627282930313233343536373839/*循环队列*/QueueNode* initQueue(){ QueueNode* Q=(QueueNode*)malloc(sizeof(QueueNode*)); Q->next=Q; Q->pre=Q; Q->node=NULL; return Q;}int isEmpty(QueueNode *Q){ if(Q->next==Q) ...

图的邻接矩阵表示法数据结构定义123456789typedef struct AdjNode { struct AdjNode* next;/*后继顶点*/ char vtxname; /*顶点名称*/}AdjNode;typedef struct Graph{ struct AdjNode* list[MAX_SIZE]; /*头节点列表*/ int vtxnum; /*顶点数*/}Graph; 图的操作12345678910111213141516171819202122232425/*初始化图*/struct Graph* initGraph();/*根据顶点名称找到顶点索引*/int findNodeIndex(Graph *graph,char vtxname);/*根据顶点名称找到顶点指针*/AdjNode *findNode(Graph *graph,char vtxname);/*在邻边链表中删除元素的辅助函数*/int deleteEdgeHelp(AdjNode* head,char vtx);/ ...

图是一种中一对多的数据类型。图的表示方法有邻接矩阵法，十字链表法。 图的操作包括 Adjacent(G,x,y):判断图G是否存在边<x,y>或(x,y)。 Neighbors(G,x):列出图G中与结点x邻接的边。 InsertVertex(G,x):在图G中插入顶点x。 DeleteVertex(G,x):从图G中删除顶点x。 AddEdge(G,x,y):若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边。 RemoveEdge(6,x,y):若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边。 FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。 邻接矩阵表示适合密集图 图的存储方式1234567#define MAX_SIZE 10typedef struct Graph{ int vexnum; /*节点个数*/ int vertices[MAX_SIZE]; /*节点数组*/ ...

哈夫曼树是一种带权路径最小的树，运用于压缩编码算法。 带权路径又称WPL，是所有非叶子节点的路径之和，路径=深度*权值 哈夫曼树的节点个数=2*带权节点个数-1 哈夫曼树的构造过程在未组成哈夫曼树的节点中寻找权值最小和第二小的节点，作为左右孩子,构造一个新节点作为父节点，父节点的权值为左右孩子的权值之和 哈夫曼树的表示哈夫曼树用顺序存储的数组表示。 存储结构如下 12345678910111213typedef struct TreeNode{ int weight; int parent; int lchild; int rchild;} TreeNode;typedef struct HaffTree{ struct TreeNode *node; int length;} HaffTree; 哈夫曼树的初始化操作123456789101112131415HaffTree *initTree(int *weight, int length){ HaffTre ...