一、邻接矩阵 #include <iostream> using namespace std; #define MaxVertexNum 100 //顶点最大数目 //邻接矩阵存储结构 typedef struct{ char Vex[MaxVertexNum]; //顶点表 int Edge[MaxVertexNum][MaxVertexNum]; //边表 int vexnum,arcnum; //图当前顶点数和弧数 }MGraph;  二、邻接表 #include <iostream> using namespace std; #define MaxVertexN...

一、BFS，也称广度优先搜索，和二叉树的层次遍历算法类似 //BFS bool visited[MaxVertexNum]; void BFSTraverse(Graph G){ for(i=0;i<G.vexnum;i++) visited[i]=FALSE; InitQueue(Q); for(i=0;i<G.vexnum;i++) if(!visited[i]) BFS(G,i); } void BFS(Graph G,int v){ visit(v); visited[v]=TRUE; EnQueue(Q,v); while(!isEmpty(Q)){ DeQueue(Q,...

来自王道数据结构

多思考递归的过程！  //DFS实现逆拓扑排序 bool visited[MaxVertexNum]; void DFSTraverse(Graph G){ for(v=0;v<G.vexnum;v++) visited[v]=FALSE; for(v=0;v<G.vexnum;v++) if(!visited[v]) DFS(G,v); } void DFS(Graph G,int v){ visit(v); visited[v]=TRUE; for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) if(!visited[w...

From王道数据结构  

一、直接插入排序 空间复杂度：O(1) 时间复杂度：O(n^2) 稳定性：稳定 适用性：顺序表和链表 //直接插入排序 void InsertSort1(int A[],int n){ int i,j,temp; for(i=1;i<n;i++){ if(A[i]<A[i-1]){ temp=A[i]; for(j=i-1;j>=0&&A[j]>temp;j--){ A[j+1]=A[j]; //元素右移 } A[j+1]=temp; } } }  二、折半插入排序 空间复杂度：O(1) 时间复杂度：O(n^2) 稳定性：稳定 适用性：顺序表 //折半插...

一、冒泡排序 空间复杂度：O(1) 时间复杂度：最好O(n)，最坏和平均为O(n^2) 稳定性：稳定 适用性：顺序表、链表 //冒泡排序 void BubbleSort(int A[],int n){ for(i=0;i<n-1;i++){ flag=false; //本趟是否发生了交换 for(j=n-1;j>i;j--){ if(A[j]<A[j-1]){ swap(A[j-1],A[j]); flag=true; } } if(flag==false) //说明没发生交换，已经有序 return; } }  二、快速排序 空间复杂度：最好和平均为O(logn)，最坏O(...

一、简单选择排序 空间复杂度：O(1) 时间复杂度：O(n^2) 稳定性：不稳定 适用性：顺序表、链表 //简单选择排序 void SelectSort(int A[],int n){ for(i=0;i<n-1;i++){ min=i; for(j=i+1;j<n;j++){ if(A[j]<A[min]) min=j; } if(min!=i) swap(A[i],A[min]); } } 二、堆排序 空间复杂度：O(1) 时间复杂度：O(nlogn) 稳定性：不稳定 //堆排序 //首先，建立大根堆 void BuildMaxHeap(int A[],int len){...

空间复杂度：O(n) 时间复杂度：O(nlogn) 稳定性：稳定 //归并排序 int *B=(int *)malloc((n+1)*sizeof(int)); //构造辅助数组B void Merge(int A[],int low,int high,int mid){ //二路归并 for(int k=low;k<=high;k++){ B[k]=A[k]; //将待排序的元素复制到B中 } for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){ if(B[i]<=B[j]) A[k]=B[i++]; else A[k...

空间复杂度：O(r)，r为队列的个数，同时也是基数的值，如果每位取值为0~9，则r=10 时间复杂度：O(d(n+r))，d为位数，比如每个数字有百位、十位和个位，则d=3，n为数字的个数，r为队列的个数 稳定性：稳定   

来自王道计算机组成原理   

From王道数据结构   

首先要清楚够减是什么概念，被减数的绝对值大于减数的绝对值称为“够减”。 如：计算A（被除数）/B（除数）时，在后面的计算中余数为被除数，由补码的不恢复余数除法（加减交替法）我们可以知道，若A、B同号，则计算A-B得到余数R，若R与B同号，则说明|A|>|B|，亦说明够减商1，否则商0；若A、B异号，则计算A+B得到余数R，若R与B异号，则说明够减，商0. 教大家一个方便记忆的方法：我们知道在补码不恢复余数除法中，若余数与除数同号则商1，异号则商0。 当同号相除时，余数与除数同号表示够减；异号相除时，余数与除数异号表示够减！ 最后记住两句话就行啦 同号相除时，够减商1，不够减商0； 异号相...

页式存储管理为操作系统中的内容，但是在计算机组成原理中的虚拟存储器部分也用到了这一方式。 分区式存储管理最大的缺点是碎片问题严重，内存利用率低。究其原因，主要在于连续分配的限制，即它要求每个作用在内存中必须占一个连续的分区。 如果允许将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存，而无需再进行“紧凑”。 基于这一思想，产生了“非连续分配方式”，或者称为“离散分配方式”。    连续分配：为用户进程分配的必须是一个连续的内存空间。 非连续分配：为用户进程分配的可以是一些分散的内存空间。 分页存储管理的思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。 分页...