搜索到
7
篇
分类为 计算机基础知识 的文章
-
计算机组成原理之存储系统 存储系统1.按作用分主存储器辅助存储器高速缓冲存储器（Cache）2.存取方式分随机存储器（RAM）RAM又分为静态随机存储器（SRAM）和动态随机存储器（DRAM），主存储器由DRAM实现，靠近处理器那一层的由SRAM实现。 SRAMDRAM存储信息触发器电容破坏性读出非是需要刷新不要需要需要重写不要需要送行列地址同时送分两次送（复用）运行速度快慢集成度低高存储成本高低主要用途高速缓存主机内存 DRAM是电容结构，其电荷只能维持1~2ms，所以需要刷新。刷新周期一般取2ms，常见的刷新方式有以下三种：集中刷新：在同一时间依次对所有行逐一再生分散刷新：分两部分，一部分读/写，一部分刷新异步刷新：将刷新的周期数除以行数，得到相邻两行的刷新时间间隔t，每隔t时间产生一次刷新请求 $$ t=\frac{\text周期数}{\text行数} $$只读存储器（ROM）串行访问存储器先总结一部分 -
计算机组原理之数据的表示和运算 数制与编码进位计数制及其相互转换进位计数法不同进制间的相互转换 -例：将二进制数1111000010.01101分别转换为八进制数和十六进制数。$$ \text{高位补0,凑足三位}\space \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\text{分界点}\space\space\space\space\space\space\space\space\space\space\text{低位补0,凑足三位} $$$$ \downarrow\space \space\space\space\space \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space \space\space\space\space\space \downarrow \space\space\space\space\space\space\space\space\space\space\space\space \space\space \downarrow $$$$ \underline001 \space \space\space\space\underline111\space \space\space\space\underline000\space \space\space\space\underline010 \space \space\space\space\underline. \space \space\space\space\underline011 \space \space\space\space\underline010 $$
-
计算机组成原理之计算机系统概述 计算机系统层次机构计算机系统的组成硬件系统和软件系统共同构成了一个完整的计算机系统计算机硬件冯·诺伊曼机的特点：采用“存储程序”的工作方式由运算器、存储器、控制器、输入设备和输出设备五大部件组成指令和数据以同等的地位存储在存储器中指令和代码均用二进制代码表示指令有操作码和地址码组成，操作码指出操作的类型，地址码指出操作数的地址以运算器为中心计算机功能部件输入设备输出设备存储器按地址存取方式MAR：存储器地址寄存器MDR：存储器数据寄存器运算器核心：算术逻辑单元（ALU）累加器（ACC）乘商寄存器（MQ）操作数寄存器（X）变址寄存器（IX）基址寄存器（BR）控制器程序计数器（PC）指令寄存器（IR）控制单元（CU）计算机性能指标计算机的主要性能指标机器字长一般为8的整数倍数据通路带宽数据总线一次所能并行传送信息的位数主存容量主存储器所能存储信息的最大容量运算速度吞吐量和响应时间主频和CPU时钟周期：$\text{CPU时钟周期} = \dfrac{1}{\text{主频}}$CPI ：执行一条指令所需的时钟周期数IPS：每秒执行多少条指令$\text{IPS} = \dfrac{\text{主频}}{\text{平均 CPI}}$CPU执行时间 ：$\text{CPU执行时间}=\dfrac{\text{CPU时钟周期数}}{\text{主频}}=\dfrac{\text{指令条数} \times \text{CPI}}{\text{主频}}$MIPS：每秒执行多少百万条指令$\text{MIPS} = \dfrac{\text{指令条数}}{\text{执行时间} \times 10^6} = \dfrac{\text{主频}}{\text{CPI} \times 10^6}$基准程序进行性能评价的程序
-
数据结构之队列 队列 (Queue)1. 概述队列（Queue）是一种特殊的线性表，只允许在表的一端进行插入操作，而在表的另一端进行删除操作。插入操作称为入队（enqueue），删除操作称为出队（dequeue）。队列遵循先进先出（First In First Out, FIFO）的原则。2. 队列的定义队列是一种线性表，只允许在一端进行插入操作，在另一端进行删除操作。插入的一端称为队尾（Rear），删除的一端称为队头（Front）。3. 队列的基本操作队列的基本操作包括初始化队列、判断队列空、判断队列满、入队、出队和取队头元素。3.1 顺序队列顺序队列是用一组地址连续的存储单元依次存放从队头到队尾的队列元素。定义顺序队列结构#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front; int rear; } SeqQueue;初始化队列void InitQueue(SeqQueue *Q) { Q->front = 0; Q->rear = 0; }判断队列空bool QueueEmpty(SeqQueue Q) { return Q.front == Q.rear; }判断队列满bool QueueFull(SeqQueue Q) { return (Q.rear + 1) % MAXSIZE == Q.front; }入队bool Enqueue(SeqQueue *Q, int e) { if (QueueFull(*Q)) return false; Q->data[Q->rear] = e; Q->rear = (Q->rear + 1) % MAXSIZE; return true; }出队bool Dequeue(SeqQueue *Q, int *e) { if (QueueEmpty(*Q)) return false; *e = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXSIZE; return true; }取队头元素bool GetFront(SeqQueue Q, int *e) { if (QueueEmpty(Q)) return false; *e = Q.data[Q.front]; return true; }3.2 链队列链队列是用链表来存储队列中的元素。定义链队列节点结构typedef struct QNode { int data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue;初始化队列void InitQueue(LinkQueue *Q) { Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q->front) exit(1); Q->front->next = NULL; }判断队列空bool QueueEmpty(LinkQueue Q) { return Q.front == Q.rear; }入队bool Enqueue(LinkQueue *Q, int e) { QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); if (!p) return false; p->data = e; p->next = NULL; Q->rear->next = p; Q->rear = p; return true; }出队bool Dequeue(LinkQueue *Q, int *e) { if (QueueEmpty(*Q)) return false; QueuePtr p = Q->front->next; *e = p->data; Q->front->next = p->next; if (Q->rear == p) Q->rear = Q->front; free(p); return true; }取队头元素bool GetFront(LinkQueue Q, int *e) { if (QueueEmpty(Q)) return false; *e = Q.front->next->data; return true; }4. 队列的应用队列在计算机科学中有广泛的应用，例如：操作系统中的任务调度：使用队列实现任务的先进先出调度。网络数据缓冲：在网络通信中，使用队列保存接收到的数据包。树和图的广度优先搜索：在树和图的遍历中使用队列实现广度优先搜索。打印队列：管理打印任务的顺序。5. 示例代码下面是使用队列实现广度优先搜索（BFS）的示例代码：#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAXVEX 100 typedef struct { int data[MAXVEX]; int front; int rear; } SeqQueue; void InitQueue(SeqQueue *Q) { Q->front = 0; Q->rear = 0; } bool QueueEmpty(SeqQueue Q) { return Q.front == Q.rear; } bool Enqueue(SeqQueue *Q, int e) { if ((Q->rear + 1) % MAXVEX == Q->front) return false; Q->data[Q->rear] = e; Q->rear = (Q->rear + 1) % MAXVEX; return true; } bool Dequeue(SeqQueue *Q, int *e) { if (QueueEmpty(*Q)) return false; *e = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXVEX; return true; } void BFS(int graph[MAXVEX][MAXVEX], int n, int start) { bool visited[MAXVEX] = {false}; SeqQueue Q; InitQueue(&Q); printf("%d ", start); visited[start] = true; Enqueue(&Q, start); while (!QueueEmpty(Q)) { int v; Dequeue(&Q, &v); for (int i = 0; i < n; i++) { if (graph[v][i] == 1 && !visited[i]) { printf("%d ", i); visited[i] = true; Enqueue(&Q, i); } } } } int main() { int graph[MAXVEX][MAXVEX] = { {0, 1, 1, 0, 0, 0}, {1, 0, 0, 1, 1, 0}, {1, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 1}, {0, 0, 0, 1, 1, 0} }; int n = 6; BFS(graph, n, 0); return 0; }上述代码实现了使用顺序队列进行广度优先搜索（BFS）的功能。通过队列保存待访问的节点，依次访问每个节点，并将其未访问的邻接节点加入队列，从而实现广度优先搜索。
-
数据结构之栈 栈 (Stack)1. 概述栈（Stack）是一种线性表，但限定在表的一端进行插入和删除操作的特殊线性表。按后进先出（Last In First Out, LIFO）的原则进行操作。栈的插入操作称为进栈（push），删除操作称为出栈（pop）。2. 栈的定义栈是一种只允许在一端进行插入和删除操作的线性表。这个端被称为栈顶（Top），相对的另一端为栈底（Bottom）。3. 栈的基本操作栈的基本操作包括初始化栈、判断栈空、判断栈满、进栈、出栈和取栈顶元素。3.1 顺序栈顺序栈是用一组地址连续的存储单元依次存放自栈底到栈顶的栈中元素。定义顺序栈结构#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; } SeqStack;初始化栈void InitStack(SeqStack *S) { S->top = -1; }判断栈空bool StackEmpty(SeqStack S) { return S.top == -1; }判断栈满bool StackFull(SeqStack S) { return S.top == MAXSIZE - 1; }进栈bool Push(SeqStack *S, int e) { if (S->top == MAXSIZE - 1) return false; S->data[++S->top] = e; return true; }出栈bool Pop(SeqStack *S, int *e) { if (S->top == -1) return false; *e = S->data[S->top--]; return true; }取栈顶元素bool GetTop(SeqStack S, int *e) { if (S.top == -1) return false; *e = S.data[S.top]; return true; }3.2 链栈链栈是用链表来存储栈中的元素。定义链栈节点结构typedef struct StackNode { int data; struct StackNode *next; } StackNode, *LinkStack;初始化栈void InitStack(LinkStack *S) { *S = NULL; }判断栈空bool StackEmpty(LinkStack S) { return S == NULL; }进栈bool Push(LinkStack *S, int e) { StackNode *p = (StackNode *)malloc(sizeof(StackNode)); if (!p) return false; p->data = e; p->next = *S; *S = p; return true; }出栈bool Pop(LinkStack *S, int *e) { if (*S == NULL) return false; StackNode *p = *S; *e = p->data; *S = p->next; free(p); return true; }取栈顶元素bool GetTop(LinkStack S, int *e) { if (S == NULL) return false; *e = S->data; return true; }4. 栈的应用栈在计算机科学中有广泛的应用，例如：表达式求值：使用栈可以实现中缀表达式转换为后缀表达式，并求值。括号匹配：使用栈可以检测表达式中的括号是否匹配。函数调用：函数调用过程中使用栈保存返回地址和局部变量，实现递归调用。深度优先搜索：在图的遍历中使用栈实现深度优先搜索。5. 示例代码下面是使用栈实现括号匹配的示例代码：#include <stdio.h> #include <stdbool.h> #include <stdlib.h> typedef struct StackNode { char data; struct StackNode *next; } StackNode, *LinkStack; void InitStack(LinkStack *S) { *S = NULL; } bool StackEmpty(LinkStack S) { return S == NULL; } bool Push(LinkStack *S, char e) { StackNode *p = (StackNode *)malloc(sizeof(StackNode)); if (!p) return false; p->data = e; p->next = *S; *S = p; return true; } bool Pop(LinkStack *S, char *e) { if (*S == NULL) return false; StackNode *p = *S; *e = p->data; *S = p->next; free(p); return true; } bool GetTop(LinkStack S, char *e) { if (S == NULL) return false; *e = S->data; return true; } bool BracketMatch(char *exp) { LinkStack S; InitStack(&S); for (int i = 0; exp[i] != '\0'; i++) { if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') { Push(&S, exp[i]); } else if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') { if (StackEmpty(S)) return false; char topElem; Pop(&S, &topElem); if ((exp[i] == ')' && topElem != '(') || (exp[i] == ']' && topElem != '[') || (exp[i] == '}' && topElem != '{')) { return false; } } } return StackEmpty(S); } int main() { char *exp = "{[(2+3)*(4+5)]}"; if (BracketMatch(exp)) { printf("The brackets match.\n"); } else { printf("The brackets do not match.\n"); } return 0; }上述代码实现了使用链栈进行括号匹配的功能。通过遍历表达式，将左括号入栈，遇到右括号时出栈，并检查是否匹配，最后检查栈是否为空来判断括号是否匹配。
