寻址方式与存储模式

寻址方式 基本寻址方式 特 征 优 点 缺 点 备 注 隐含寻址 操作数的存放地由操作码决定 立即寻址 操作数直接在指令中 加快执行速度 增加指令长度,不方便修改操作数 适用提供常数,设定初始值 寄存器寻址 操作数在指令指定的寄存器中 方便修改,访问寄存器加快指令执行,缩短指令长度,编程更灵活 直接寻址 操作数地址在指令中,操作数在主存单元中 指令字较长,不方便地址修改 间接寻址 操作数地址的地址在指令中,操作数在主存中 方便修改指针,编程更灵活 访问两次主存获取操作数,降低执行速度 形式地址,有效地址EA(=操作数地址) 寄存器间接寻址 操作数地址在指令指定的寄存器中,操作数在主存单元中 压缩指令长度,修改寄存器内容就可以修改主存地址指针 方便编写循环程序 相对寻址 操作数地址由PC和指令提供的地址偏移量决定,操作数在主存单元中 EA=PC+D,适用与地址无关的程序设计 基址寻址 操作数地址由基址寄存器(RB)和指令提供的地址偏移量决定,操作数在主存单元中 缩短指令长度,扩大寻址空间 大型计算机,用户的逻辑地址→主存的物理地址,EA=(RB)+D 变址寻址 操作数地址由变址寄存器(RI)和指令提供的地址偏移量决定,操作数在主存单元中 寻址到操作数RI内容(地址)自动修改,EA=(RI)+D 堆栈寻址 寻址方式由指令操作码决定 适用涉及堆栈操作的指令,EA=(SP)...

Jul 22, 2021 · 1 min · Archai

外部排序相关

外部排序 由于数据元素太多,无法一次全部读入内存进行内部排序,这是就要通过外部排序来解决 1.外排原理 目的:通过内存的读写操作(每次读写操作都是成块的进行,比如每次1KB),将存放于磁盘中的大量数据变得有序。 (拿二路归并举例) 如图,对于在磁盘中分块存放的数据,每块存入三个元素,共16块 在内存中建立三个缓冲区输出缓冲区、输入缓冲区1以及输入缓冲区2 1.1构造初始归并段 首先,依次地读入前两块数据,分别存入内存中的 缓冲区1、缓冲区2 将输入缓冲区1以及输入缓冲区2中存放的数据经过 内存中的二路归并排序(内排)后,将生成的有序的块经 输出缓冲区 写入磁盘 得到一个有序的归并段 同样的,对剩余块进行同样的操作可以得到 1.2以归并段为单位进行归并 分别选取归并段1和2中较小的一块,依次读入至缓冲区1,2 内排之后,写入内存,注意,输入缓冲区1(或2)空缺后要立即在归并段1(或2)中读入新的块到其中进行归并排序 (以保证输出缓冲区始终输出归并段中较小的元素) 最终,完成所有归并段的第一趟归并之后,会有 之后,4块成一个归并段,两两归并 …… 最终。经过3趟归并,整体会变得有序! 2.优化思路 2.1时间开销分析 在整个排序过程中,时间开销分析如下 可以看到, 外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间 而读写外存时间是关键的时间开销,因此优化应该针对怎么减少读写外存的次数展开 而文件总块数无法优化,只能针对归并的趟数优化 为此,我们需要采用多路归并来解决 2.3结论 2.4 优化思路一:采用多路归并 对上面的例子,如果采用四路归并 只需96次读写即可!! 2.5 优化思路二:减少初始归并段数量r 败者树 归并段数增加之后,内存中缓冲区数目增加,从中对比得出最小关键字的对比次数也会随之增多…… 1.算法思想 构造 如图所示的树结构,叶节点对应(脑补)各归并段(假设共有8个归并段),分支结点记录败者来自哪个归并段,最后根节点记录冠军来自哪个归并段,并且将冠军输出,为这8个归并段中的最小值。 下轮选择冠军记录的那个归并段(归并段3)中的元素6,代替1的位置,如图,并依次向上的与各败者结点对比,胜则往上,败则留下,最终输出冠军 接下来,循环这个过程 2.效率分析 对于k路归并,第一次构造败者树需要对比关键字k-1次 有了败者树,选出最小元素,只需对比关键字次$\left \lceil \log_2k \right \rceil$...

Jun 10, 2021 · 1 min · Archai

排序算法相关

排序算法 平均时间复杂度 空间复杂度 稳定性 适用情况 插入排序 $O(n^2)$ O(1) 稳定 n较小,初始序列基本有序 希尔排序 $O(n^{1.3})$ O(1) 不稳定 冒泡排序 $O(n^2)$ O(1) 稳定 n较小,初始序列基本有序 快速排序 $O(n\log_2n)$ $O(nlog_2n)$ 不稳定 初始序列无序 简单选择排序 $O(n^2)$ O(1) 不稳定 n较小 堆排序 $O(n\log_2n)$ O(1) 不稳定 n较大或只排前几位 2-路归并排序 $O(n\log_2n)$ O(n) 稳定 n很大 链式基数排序 $O(d(n+rd))$ $O(rd)$ 稳定 n大,关键字值小 相关概念 1....

Jun 10, 2021 · 3 min · Archai

查找算法相关

顺序查找 typedef struct{//查找表的数据结构(顺序表) int *elem;//动态数组基址 int TableLen;//查找表长度 }SSTable; int Seq_Search(SSTable ST,int key){ ST.elem[0]=key; int i; for (i = ST.TableLen;ST.elem[i]!=key ; i--) {}//从后往前查找,最终返回下标i return i;//返回0说明没找到 } 效率分析 对于长度为n的顺序表,如果查找成功 $$ ASL={\frac{1+2+…+n}{n}}=\frac{n+1}{2} $$ 若果查找失败,则 $ASL=n+1$ 总体上,该算法时间复杂度为 $O(n)$ 优化思路 1.如果使得表中的元素有序存放……,可以构造出一棵查找判定树 此时,查找失败时$ASL=\frac{1+2+…+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$ 优点: 容易查找失败时ASL更小 2.如果各元素被查找的概率不同……,可以把概率大的靠前 优点: 容易查找成功时ASL更小 折半查找 折半查找,又称“二分查找”,仅适用于有序的顺序表。 针对升序排列的顺序表,代码实现如下 typedef struct{//查找表的数据结构(顺序表) int *elem;//动态数组基址 int TableLen;//查找表长度 }SSTable; int BinarySearch(SSTable L,int key){ int low=0,high=L.TableLen-1,mid; while (low<=high) { mid=(low+high)/2; if (L....

Jun 6, 2021 · 2 min · Archai

图的应用

一、最小生成树 📌什么是生成树? 连通图的生成树是包含图中所有顶点的一个极小连通子图,通俗地讲,就是“边尽可能少,但需保持连通”。 规律: 对于一个顶点数|V|=n的树,其生成树的边数|E|=n-1。如果将|E|+1,必然会形成回路;如果将|E|-1,则会成为非连通图。 📌什么是最小生成树? 最小生成树,也称最小代价树(Minimum Spanning Tree,MST) 是带权连通无向图的生成树中边的权值之和最小的一棵树,联系实际问题不难理解其中“最小代价”的意味。 Prim(普利姆算法),Kruskal(克鲁斯卡尔算法)就是寻找最小生成树的常用算法。 1.Prim(普利姆算法) 从某一顶点开始,每次将代价最小的新顶点纳入生成树,直至所有顶点都纳入为止。 图示 易知,此方法得到的最小生成子树是不唯一的。 代码实现 void MiniSpanTree_PRIMI(Graph G,int u){ //从顶点u出发找G的最小生成树 for (int i = 0; i <G.vexnum; ++i) {//辅助数组初始化 if(i!=u){ closedge[i]={u,G.arcs[u][i]}; } } closedge[u].lowcost=0; for (int j = 0; j < G.vexnum; j++) { k=minimum(closedge);//求生成树的下一个节点 cout<<cloedge[k].adjvex<<G.vex[k]; closedge[k].lowcost=0; for (int i = 0; i < G.vexnum; i++) { if (G.arc[k][j].adj<closedge[j].lowcost) { closedge[j]={G....

Jun 4, 2021 · 3 min · Archai

图的遍历

广度优先遍历(BFS) BFS(Breadth-First-Search),参考对树的层序遍历 对上面的图从①出发进行BFS得到序列: ①②⑤ ⑥ ③⑦ ④⑧ 若采用不同的储存结构,可能会得到不同的遍历结果(这个差异主要来自寻找邻接点的过程),对于邻接矩阵存储的图,由于邻接矩阵是唯一的,所以BFS序列也是唯一的;同理,邻接表存储的图BFS序列不唯一。 BFS算法 与树的层序遍历不同的是,由于图中存在回路,遍历过程中会出现重复访问的问题,故可构造visited数组,用来标记已访问过的数组。 此外,还应针对非连通图做额外的判断,遍历完一个连通分量(极大连通子图)后,遍历查找visited数组中是否还存在未遍历的,如果有即为另一连通分量,继续调用BFS即可。 void BFS(Graph G,int v); bool visited[MAX_VERTEX_NUM]; SqQueue Q;//辅助队列 void BFSTraverse(Graph G){ //初始化visited数组 for (int i = 0; i < G.vexnum; ++i) {//使下标从1开始 visited[i]=false; } //对非连通图的处理 for (int v = 0; v < G.vexnum; ++v) { if (!visited[v]) BFS(G,v); } } //从顶点v出发广度优先遍历图G void BFS(Graph G,int v){ visit(v); visited[v]=true; EnQueue(Q,v);//顶点v入队列Q while(!isEmpty(Q)){ DeQueue(Q,v);//顶点v出队列Q for (w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))//处理v的所有邻接点 if (!...

Jun 3, 2021 · 1 min · Archai