济南快速建站模板,方案设计基本步骤,网加商学院网站怎么做,资阳市住房和城乡建设局网站文章目录 1.用循环比递归的效率高吗2.顺序表和链表的比较3.头指针和头结点的区别4.如何区分循环队列是队满还是队空#xff1f;5.栈在通过后缀表达式求值的算法思想6.栈在递归中的应用7.队列在层次遍历中的作用8.队列在计算机系统中的应用9.矩阵的压缩存储10.串的模式匹配11.如… 文章目录 1.用循环比递归的效率高吗2.顺序表和链表的比较3.头指针和头结点的区别4.如何区分循环队列是队满还是队空5.栈在通过后缀表达式求值的算法思想6.栈在递归中的应用7.队列在层次遍历中的作用8.队列在计算机系统中的应用9.矩阵的压缩存储10.串的模式匹配11.如何由遍历序列构造一棵二叉树12.线索二叉树的概念13.树的4种存储方式14.平衡二叉树15.dijkstra算法16.Floyd算法17.Prim算法18.Kraskal算法19.拓扑排序20.B树和B树21.哈希表的概念、构造方法哈希冲突的解决方法22.内部排序辨析23.外部排序辨析 1.用循环比递归的效率高吗
循环和递归两者是可以互换的无法陈述谁效率高。
递归 优点代码简洁清晰容易检查正确性 缺点递归调用次数较多时要增加额外的堆栈处理有可能产生堆栈溢出的情况会对执行效率有一定的影响。
循环 优点结构检点速度快 缺点不能解决全部问题有些问题适合于用递归来解决不适合用循环解决。
2.顺序表和链表的比较
从 存取方式、 逻辑结构和物理结构、 查找插入和删除操作、空间分配四个方面分别做比较即可。
3.头指针和头结点的区别
头指针是指向第一个结点存储位置的指针具有表示作用头指针是链表的必要元素无论链表是否为空头指针都存在。
头结点是放在第一个元素结点之前便于在第一个元素结点之前进行插入和删除的操作头结点不是链表的必须元素可有可无头结点的数据域也可以不存储任何信息。
4.如何区分循环队列是队满还是队空
①牺牲一个单元来区分队满和队空。 队空就是Q.front Q.rear 队满就是(Q.rear1)%Maxsize Q.front
②增设数据成员元素 队空Q.size0 队满Q.sizeMaxsize
③标记上一次是入队还是出队 若是入队flag1此时出现Q.frontQ.rear那么即为队满 若是出队flag0此时出现Q.frontQ.rear那么即为队空
5.栈在通过后缀表达式求值的算法思想
但凡出现左括号做入栈操作否则做以下操作 是否为空与栈顶元素是否匹配
表达式检验结束后还要检查栈中是否还有元素。
6.栈在递归中的应用
在递归函数中每次函数调用都会创建一个新的函数调用帧frame这个帧包含了函数的局部变量、参数值以及函数返回地址等信息。 当函数调用自身递归调用时每次都会创建一个新的函数调用帧。这些函数调用帧被存储在内存中的栈数据结构中这就是所谓的调用栈call stack。
当递归函数开始执行时会一直递归调用自身每次递归调用都会将一个新的函数调用帧压入调用栈中。 当递归条件不再满足函数开始返回时会从栈顶依次弹出函数调用帧并执行相应的返回操作直到栈为空整个递归过程结束。
7.队列在层次遍历中的作用
遇到某类信息需要逐层/逐行处理时往往是在处理当前层或当前行时就对下一层或下一行做预处理把处理顺序安排好待当前层或当前行处理完毕就可以处理下一层或下一行。
二叉树的层序遍历、广度优先搜索、任务调度、消息队列、缓冲池、批处理系统。
8.队列在计算机系统中的应用
任务调度和作业管理 操作系统使用队列来管理和调度各种任务和作业。例如多任务操作系统可以使用队列来安排进程的执行顺序确保按照优先级和其他调度策略执行任务。I/O请求管理 计算机系统中的I/O设备通常会产生大量的请求如磁盘I/O请求、网络数据包等。队列被广泛应用于管理这些请求以便按照请求到达的顺序来处理它们。消息传递和事件处理 在事件驱动的系统中队列用于管理事件和消息的处理顺序。例如图形用户界面GUI应用程序可以使用队列来处理用户输入事件、定时器事件等。网络数据包排队 在网络系统中路由器和交换机使用队列来缓冲传入和传出的数据包。这些队列可以帮助调节网络流量并确保数据包按照一定的优先级和服务质量要求被处理。缓存系统 队列常被用于实现缓存系统例如最近最少使用LRU缓存算法。在缓存满时新的数据项可以被放入队列而最久未使用的数据项可以从队列的头部被移除。并发编程 在多线程和并发编程中队列常被用于实现线程间的通信和同步。例如生产者-消费者模型中一个线程生产者向队列中放入数据而另一个线程消费者则从队列中取出数据进行处理。日志和消息处理系统 队列可用于实现日志和消息处理系统用于收集、存储和处理系统产生的日志和消息。通过将日志和消息放入队列中可以实现异步处理和解耦。批处理系统 在数据处理领域队列被广泛用于构建批处理系统。数据处理任务可以被放入队列中然后由后台任务逐个处理从而提高处理效率。
9.矩阵的压缩存储
矩阵的压缩存储是一种优化存储矩阵的方法特别是当矩阵中有大量的重复值或者是稀疏矩阵大部分元素为零时。 它的主要目的是减少内存占用提高存储和处理效率。
行压缩存储、列压缩存储、对角线压缩存储、十字链表法。
10.串的模式匹配
朴素算法Naive Algorithm 也称为暴力匹配算法它是最简单直观的模式匹配算法。它的思路是在文本串中从头到尾逐个字符地与模式串进行比较直到找到匹配或者遍历完整个文本串。 朴素算法的时间复杂度为 O(m*n)其中 m 是模式串的长度n 是文本串的长度。
// 朴素算法函数
int naiveSearch(char *text, char *pattern) {int textLength strlen(text);int patternLength strlen(pattern);for (int i 0; i textLength - patternLength; i) {int j;// 检查文本串中从第 i 个位置开始的子串是否与模式串匹配for (j 0; j patternLength; j) {if (text[i j] ! pattern[j])break; // 如果当前字符不匹配则跳出内循环}// 如果内循环完全匹配了模式串则返回匹配位置if (j patternLength)return i;}return -1; // 没有找到匹配的子串返回 -1
}Knuth-Morris-Pratt 算法KMP Algorithm KMP 算法是一种高效的模式匹配算法它利用了模式串中已经匹配的信息来避免不必要的比较。 通过构建部分**匹配表Partial Match Table**来记录模式串中的前缀和后缀的最长公共部分KMP 算法能够在 O(nm) 的时间复杂度内完成匹配其中 n 是文本串的长度m 是模式串的长度。
// 构建部分匹配表
void buildPartialMatchTable(char *pattern, int *table) {int patternLength strlen(pattern);table[0] 0; // 首字符的部分匹配值总是 0int length 0; // 用于记录当前匹配的长度for (int i 1; i patternLength; i) {// 如果当前字符和当前匹配长度处的字符相同匹配长度加1if (pattern[i] pattern[length]) {length;table[i] length;} else {// 如果当前字符和当前匹配长度处的字符不同根据部分匹配表更新当前匹配长度if (length ! 0) {length table[length - 1];--i; // 回退一步重新尝试匹配} else table[i] 0;}}
}
// KMP算法函数
int KMP(char *text, char *pattern) {int textLength strlen(text);int patternLength strlen(pattern);int *table (int*)malloc(patternLength * sizeof(int));buildPartialMatchTable(pattern, table);int i 0, j 0; // i用于遍历文本串j用于遍历模式串while (i textLength) {if (text[i] pattern[j]) {i;j;}if (j patternLength) {free(table);return i - j; // 匹配成功返回匹配位置的起始索引} else if (i textLength text[i] ! pattern[j]) {if (j ! 0)j table[j - 1]; // 根据部分匹配表更新模式串的起始位置elsei;}}free(table);return -1; // 未找到匹配返回 -1
}调用KMP(text,pattern); //text文本串pattern模式串11.如何由遍历序列构造一棵二叉树
先序中序
后序中序
层序中序
12.线索二叉树的概念
对于n个结点的二叉树在二叉链存储结构中有n1个空链域利用这些空链域存放在某种遍历次 序下该结点的前驱结点和后继结点的指针这些指针称为线索加上线索的二叉树称为线索二叉树。
注意线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题解决了二叉链表找左、右孩子困难的问题。
13.树的4种存储方式
①双亲表示法这种存储方式采用一组连续空间来存储每个结点同时在每个结点中增设一个伪指针指示 其双亲结点在数组中的位置。结构体为【[data][parent]】。
struct TreeNode {int data;int parent; // 父节点的索引
};
void addChild(int parentIndex, int childData) {int childIndex -1;// 查找一个空闲的位置存储新的子节点for (int i 0; i MAX_NODES; i) {if (tree[i].parent -1) {childIndex i;break;}}if (childIndex ! -1) {tree[childIndex].data childData;tree[childIndex].parent parentIndex;} else {printf(No space to add child.\n);}
}该存储结构利用了每个结点根结点除外只有唯一双亲的性质可以很快得到每个结点的 双亲结点但求结点的孩子时需要遍历整个结构。
②孩子表示法将每个结点的孩子结点都用单链表链接起来形成一个线性结构此时n 个结点 就有n 个孩子链表叶子结点的孩子链表为空表这种存储方式寻找子女的操作非常直接而 寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。
// 定义树节点结构
struct TreeNode {int data;struct TreeNode *firstChild; // 指向第一个孩子节点struct TreeNode *nextSibling; // 指向右兄弟节点
};
//链式结构③孩子兄弟表示法二叉树表示法使每个结点包括三部分内容结点值、指向结点第一个孩子结点的指针及指向结点下一个兄弟结点的指针沿此域可以找到结点的所有兄弟结点。
// 定义树节点结构
struct TreeNode {int data;struct TreeNode *firstChild; // 指向第一个孩子节点struct TreeNode *nextSibling; // 指向右兄弟节点
};
//结构相同但是写法不同④左右孩子表示法用于二叉树每个结点包括三部分内容结点值、指向结点左孩子结点的指针及指向结点右孩子结点的指针。
// 定义树节点结构
struct TreeNode {int data;struct TreeNode *LeftChild; // 指向结点左孩子节点struct TreeNode *RightChild; // 指向结点右孩子节点
};14.平衡二叉树
为避免树的高度增长过快降低二叉排序树的性能规定在插入和删除二叉树结点时要保证任 意结点的左、右子树高度差的绝对值不超过1, 将这样的二叉树称为平衡二叉树(Balanced Binary Tree), 简称平衡树。 定义结点左子树与右子树的高度差为该结点的平衡因子则平衡二叉树结点 的平衡因子的值只可能是-1 、0 或1 。
15.dijkstra算法
一种用于计算图中单源最短路径的贪心算法。Dijkstra 算法基于贪心策略每次选择当前距离起点最近的节点作为下一个中间节点并更新与该节点相邻的节点的最短路径。
基本步骤 1.初始化距离数组 dist 和标记数组 visited用于记录每个节点到起点的最短距离和节点是否已经访问过。 2.将起点的最短距离设为0并标记起点为已访问。 3.对于起点相邻的所有节点更新它们的最短距离为起点到它们的距离并标记它们为已访问。 4.重复以下步骤直到所有节点都被访问过 a. 从未访问的节点中选择距离起点最近的节点。 b. 对于选中的节点更新其相邻节点的最短距离为起点到该节点的距离加上选中节点的最短距离。 c. 将选中的节点标记为已访问。 5.当所有节点都被访问过后距离数组 dist 中存储的即为起点到每个节点的最短距离。
// 计算未访问节点中距离起点最近的节点的索引
int minDistance(int dist[], bool visited[]) {int min INF, min_index;for (int v 0; v V; v) {if (visited[v] false dist[v] min) {min dist[v];min_index v;}}return min_index;
}
// 使用 Dijkstra 算法计算单源最短路径
void dijkstra(int graph[V][V], int src) {int dist[V]; // 存储从源到每个顶点的最短距离bool visited[V]; // 记录每个顶点是否已被访问// 初始化所有距离为无穷大所有节点均未被访问for (int i 0; i V; i) { dist[i] INF;visited[i] false;} //可以用memset(dist, INF, sizeof(dist));替换dist[src] 0; // 源节点到自身的距离为0for (int count 0; count V - 1; count) {int u minDistance(dist, visited); // 选取未访问节点中距离最近的节点visited[u] true; // 标记该节点为已访问// 更新相邻节点的最短距离for (int v 0; v V; v) {if (!visited[v] graph[u][v] dist[u] ! INF dist[u] graph[u][v] dist[v])dist[v] dist[u] graph[u][v];}}printSolution(dist);
}// 打印最短路径
void printSolution(int dist[]) {printf(Vertex \t Distance from Source\n);for (int i 0; i V; i)printf(%d \t %d\n, i, dist[i]);
}16.Floyd算法
一种用于求解所有节点对之间最短路径的动态规划算法。它可以处理带权重的有向图或无向图即使存在负权边或负权环也能正确计算出最短路径。
void floyd(int graph[][MAX_NODES], int n) {int i, j, k;// 逐步考察每一个中间节点for (k 0; k n; k) { //枚举每一个中间结点// 以结点 i 为起点for (i 0; i n; i) {// 以结点 j 为终点for (j 0; j n; j) {// 如果从结点i经过结点k再到结点j的路径更短则更新最短路径if (graph[i][k] graph[k][j] graph[i][j]) {graph[i][j] graph[i][k] graph[k][j];}}}}
}17.Prim算法
一种用于求解最小生成树的贪心算法。最小生成树是一棵包含图中所有节点且边权重之和最小的树。Prim算法从一个初始节点开始逐步选取与当前生成树相连的权重最小的边直到所有节点都被加入到生成树中为止。
Prim算法的基本思想 1.选择一个初始节点作为生成树的根节点并将其加入生成树中。 2.在生成树与剩余节点之间的边中选择权重最小的边并将其加入生成树。 3.重复步骤2直到所有节点都被加入到生成树中。
void prim(int start) {bool visited[MAX_NODES] {false}; // 记录已加入生成树的节点visited[start] true;int MST[MAX_NODES][2]; // 最小生成树的边集合int edgeCount 0;while (edgeCount n - 1) {int minEdge INF;int minNode -1;for (int node 0; node n; node) {if (visited[node]) {for (int neighbor 0; neighbor n; neighbor) {if (!visited[neighbor] graph[node][neighbor] minEdge) {minEdge graph[node][neighbor];minNode neighbor;}}}}if (minNode ! -1) {MST[edgeCount][0] minNode;MST[edgeCount][1] minEdge;edgeCount;visited[minNode] true;}}// 输出最小生成树的边集合printf(Minimum Spanning Tree edges:\n);for (int i 0; i n - 1; i) {printf(%d - %d\n, start, MST[i][0]);}
}18.Kraskal算法
一种用于求解最小生成树Minimum Spanning TreeMST的贪心算法。其基本思想是从图中所有边中选择权重最小的边然后逐步添加边直到所有的顶点都被连接为止。在添加边的过程中要确保不形成环路因为最小生成树是一个树不应该包含环路。
以下是Kruskal算法的基本步骤 1.将图中的所有边按照权重进行排序。 2.初始化一个空的最小生成树。 3.依次遍历排好序的边每次选择一条边判断加入后是否形成环路。若不形成环路则将该边加入最小生成树。 4.重复步骤3直到最小生成树中包含了所有的顶点。
// Kruskal算法
void KruskalMST(struct Graph* graph) {int V graph-V;struct Edge result[V]; // 存储最小生成树的边int e 0; // 用于result数组的索引int i 0; // 用于遍历graph-edge数组int parent[V]; // 用于记录顶点的父节点// 初始化parent数组for (int v 0; v V; v) parent[v] -1;// 将图的所有边按照权重进行排序qsort(graph-edge, graph-E, sizeof(graph-edge[0]), [](const void* a, const void* b) {struct Edge* a1 (struct Edge*)a;struct Edge* b1 (struct Edge*)b;return a1-weight b1-weight;});// 遍历排序后的边数组构建最小生成树while (e V - 1 i graph-E) {struct Edge next_edge graph-edge[i];int x find(parent, next_edge.src);int y find(parent, next_edge.dest);// 如果不形成环路则加入最小生成树if (x ! y) {result[e] next_edge;Union(parent, x, y);}}// 输出最小生成树的边printf(Edges in the minimum spanning tree:\n);int minimumCost 0;for (i 0; i e; i) {printf(%d - %d: %d\n, result[i].src, result[i].dest, result[i].weight);minimumCost result[i].weight;}printf(Minimum cost of MST: %d\n, minimumCost);
}19.拓扑排序
一种对有向无环图DAG进行排序的算法它使得图中的所有顶点按照一定的顺序排列使得所有的有向边从前面的顶点指向后面的顶点。如果图中存在环路则无法进行拓扑排序。
拓扑排序的基本思想 不断地从图中选择入度为0的顶点并删除以该顶点为起点的边直到图中所有的顶点都被选择完毕为止。如果图中有顶点无法被选择则说明图中存在环路无法进行拓扑排序。
拓扑排序的算法步骤 1.初始化一个队列并将所有入度为0的顶点加入队列。 2.不断地从队列中取出顶点并将该顶点输出到拓扑排序结果中。 3.对于每个被取出的顶点遍历其所有邻接顶点将这些邻接顶点的入度减1。若某个邻接顶点的入度减为0则将其加入队列。 4.重复步骤2和步骤3直到队列为空。
// 拓扑排序算法
void topologicalSort(struct Graph* graph) {int V graph-V;int* indegree graph-indegree;// 初始化一个队列int queue[MAX_VERTICES];int front 0, rear -1;// 将入度为0的顶点加入队列for (int i 0; i V; i) {if (indegree[i] 0) {queue[rear] i;}}// 记录拓扑排序结果int count 0;int* topologicalOrder (int*)malloc(V * sizeof(int));while (front rear) {int vertex queue[front]; // 出队列topologicalOrder[count] vertex;// 遍历顶点的邻接顶点减少其入度struct Node* temp graph-adjList[vertex];while (temp ! NULL) {indegree[temp-vertex]--;if (indegree[temp-vertex] 0) {queue[rear] temp-vertex;}temp temp-next;}}// 输出拓扑排序结果printf(Topological Sort Order: );for (int i 0; i count; i) {printf(%d , topologicalOrder[i]);}printf(\n);
}20.B树和B树
B树B-tree
B树是一种平衡的多路搜索树其中每个节点可以包含多个子节点。每个节点中的关键字按非递减顺序排列且节点中关键字的数量至少等于子节点数目的一半。所有叶子节点位于同一层并且没有数据的重复。B树的节点在插入和删除操作后可以进行自平衡使得树保持平衡状态。
B树B±tree
B树是在B树的基础上进行了改进它与B树相比有更大的节点容量。B树的内部节点不存储数据只存储关键字和指向子节点的指针。所有数据都存储在叶子节点中叶子节点之间使用指针连接成一个有序链表使得范围查询更加高效。B树的叶子节点形成了一个有序链表可以进行范围查询等操作。
B树通常被认为是一种更适合数据库索引的数据结构因为它的数据存储方式更加有序可以更快地进行范围查询和顺序遍历。
21.哈希表的概念、构造方法哈希冲突的解决方法
哈希表基于哈希函数Hash Function实现将关键字映射到表中的位置。 通常哈希函数将关键字转换为固定长度的哈希值然后根据哈希值确定关键字在表中的位置。
构造方法 1.选择哈希函数选择合适的哈希函数是构造哈希表的第一步。哈希函数应该将关键字均匀地分布到哈希表中的位置以避免冲突。 2.确定哈希表大小确定哈希表的大小通常选择素数作为表的大小以减少冲突的可能性。 3.解决冲突在确定了哈希函数和哈希表大小后需要解决哈希冲突的问题。常见的冲突解决方法包括开放定址法如线性探测和二次探测、链地址法和再哈希法等。
哈希冲突的解决方法
开放定址法当发生冲突时通过探测序列来找到下一个可用的位置。常见的探测方法有线性探测、二次探测和双重散列。链地址法将哈希表的每个位置都连接一个链表当发生冲突时将冲突的元素添加到链表中。这种方法需要在表中存储指向链表头的指针。再哈希法当发生冲突时使用另一个哈希函数对冲突的关键字进行重新哈希直到找到空闲位置为止。通常需要多个哈希函数。
22.内部排序辨析
内部排序是指对数据集合通常是存储在内存中进行排序的过程。 在内部排序中整个数据集合可以一次性加载到内存中并且所有的排序操作都在内存中进行因此也称为内存排序。
冒泡排序Bubble Sort依次比较相邻的元素将较大或较小的元素逐步交换至右侧直到整个序列有序。时间复杂度O(n^2) 空间复杂度O(1)选择排序Selection Sort每次从未排序的部分选择最小或最大的元素放置到已排序部分的末尾。时间复杂度O(n^2) 空间复杂度O(1)插入排序Insertion Sort将未排序的元素逐个插入到已排序部分的合适位置直到整个序列有序。时间复杂度O(n^2) 空间复杂度O(1)希尔排序Shell Sort是插入排序的改进版本通过将序列分成多个子序列进行排序然后逐步缩小子序列的长度最终完成排序。 时间复杂度O(n log n)~O(n^2) 空间复杂度O(1)归并排序Merge Sort采用分治法将序列分成两个子序列分别进行排序然后将排好序的子序列合并成一个有序序列。时间复杂度O(n log n) 空间复杂度O(n)快速排序Quick Sort采用分治法通过选择一个基准元素将序列分成小于基准的部分和大于基准的部分然后对这两部分分别进行递归排序。时间复杂度O(n log n) 空间复杂度O(log n) ~ O(n)堆排序Heap Sort利用堆这种数据结构进行排序通过构建最大堆或最小堆来实现排序。时间复杂度O(n log n) 空间复杂度O(1)
23.外部排序辨析
外部排序是一种在数据量过大无法全部加载到内存中进行排序时使用的排序方法。 它通常涉及将数据分成适当大小的块然后在内存中对每个块进行排序最后将排序后的块合并成一个有序序列。 外部排序的核心思想是尽量减少对外部存储的访问次数以提高排序效率。
多路归并排序 基本思想将数据分成多个块每个块都能够全部加载到内存中进行排序。然后利用归并排序的思想将多个有序块合并成一个更大的有序块直到整个数据集合排序完成。优点适用于大规模数据的排序且可以利用多个磁盘进行并行排序。缺点需要额外的磁盘空间来存储排序后的块且合并过程可能会产生额外的磁盘读写开销。 置换-选择排序 基本思想将数据分成多个块并在内存中维护一个“缓冲区”用于存储每个块中的一部分数据。然后在缓冲区中选择最小或最大的元素输出到外部存储直到所有块中的数据都被输出。优点不需要额外的磁盘空间来存储排序后的块适用于数据集合无法全部加载到内存中的情况。缺点可能需要多次访问外部存储造成较高的磁盘读写开销。 多路平衡归并排序 基本思想类似于多路归并排序但是在归并过程中需要保持各个块之间的平衡以提高归并的效率。优点能够更好地利用外部存储的空间减少归并过程中的磁盘读写开销。缺点实现较为复杂需要维护块之间的平衡。 外部快速排序 基本思想类似于快速排序但是在划分过程中需要将数据分成适当大小的块并在内存中对每个块进行排序。然后利用归并操作将排序后的块合并成一个有序序列。优点基于快速排序具有较好的平均时间复杂度。缺点可能会产生较大的磁盘读写开销特别是在数据分布不均匀的情况下。
