c语言任意输入20个互不相等的整数,编写代码实现以下功能:1.求20个数的平均数并输出;2.将20个数中的奇数全部输出,没有奇数提示“无奇数”;3.将20个数由大到小排序并输出。

时间: 2024-10-16 07:21:05 浏览: 41

在C语言中,你可以通过以下步骤来实现这个功能:

#include <stdio.h>

int main() {
    int arr[20], i = 0;
    
    // 输入20个互不相等的整数
    printf("请输入20个互不相等的整数:\n");
    for (i = 0; i < 20; i++) {
        scanf("%d", &amp;arr[i]);
        while (i > 0 &amp;&amp; arr[i] < arr[i - 1]) { // 防止重复输入
            printf("已输入过的数值,请重新输入第%d个数:", i);
            scanf("%d", &amp;arr[i]);
        }
    }

    // 计算平均数并输出
    float sum = 0;
    for (i = 0; i < 20; i++) {
        sum += arr[i];
    }
    float avg = sum / 20;
    printf("20个数的平均值为 %.2f\n", avg);

    // 检查奇数并输出
    int has_odd = 0;
    for (i = 0; i < 20; i++) {
        if (arr[i] % 2 != 0) {
            printf("%d ", arr[i]);
            has_odd = 1;
        }
    }
    if (!has_odd) {
        printf("\n无奇数\n");
    }

    // 将数组升序排列
    for (i = 0; i < 19; i++) {
        for (int j = 0; j < 19 - i; j++) {
            if (arr[j] < arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

    // 输出排序后的数组
    printf("\n排序后的20个数从大到小:");
    for (i = 0; i < 20; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}
向AI提问 loading 发送消息图标

相关推荐

静态链表示意图:2.2 顺序表与链表的比较存储密度比较:顺序表:只存储数据元素、预分配存储空间链表:指针的结构性开销、链表的元素个数没有限制按位查找:顺序表:O(1),随机存取链表:O(n),顺序存取插入和删除:顺序表:O(n),平均移动表长一半的元素链表:不用移动元素,合适位置的指针——O(1)时间复杂度:顺序表:若线性表频繁查找却很少进行插入和删除操作链表:若线性表需频繁插入和删除时空间复杂度:顺序表:知道线性表的大致长度,空间效率会更高链表:若线性表元素个数变化较大或者未知2.3 栈        定义:限定仅在一端(栈顶)进行插入和删除操作的线性表,后进先出。栈示意图:        时间复杂度(插入与删除):顺序栈与链栈均为O(1)        空间复杂度:链栈多一个指针域,结构性开销较大,使用过程元素个数变化较大时,用链栈;反之顺序栈。        出栈元素不同排列的个数:   (卡特兰数)        共享栈: 两个栈共享一片内存空间, 两个栈从两边往间增长。卡特兰数的应用:存储结构:顺序栈初始化:top=-1链栈初始化:top=NULL栈的应用:        1) 括号匹配        2) 递归        3) 缀表达式 转 后缀表达式        4) 缀表达式:设两个栈(数据栈和运算符栈),根据运算符栈的优先级进行运算。2.4 队列        定义: 只允许在一端插入, 在另一端删除。具有先进先出的特点。队列示意图:        时间复杂度:均为O(1)        空间复杂度:链队列多一个指针域,结构性开销较大;循环队列存在浪费空间和溢出问题。使用过程元素个数变化较大时,用链队列;反之循环队列。        双端队列: 只允许从两端插入、两端删除的线性表。双端队列示意图: 存储结构:        链队列:队头指针指向队头元素的前一个位置,队尾指针指向队尾元素,先进先出。        循环队列:                1)队空:front=rear                2)队满:(rear+1)%QueueSize=front                3)队列元素个数:(队尾-队头+队长)%队长==(rear-front+QueueSize)%QueueSize队列的应用:        1) 树的层次遍历        2) 图的广度优先遍历2.4 数组与特殊矩阵一维数组的存储结构:二维数组的存储结构: 对称矩阵的压缩(行优先):下三角矩阵的压缩(行优先):  上三角(行优先):三对角矩阵的压缩(行优先):稀疏矩阵压缩:十字链表法压缩稀疏矩阵:2.5 串        串,即字符串(String)是由零个或多个字符组成的有限序列。串是一种特殊的线性表,数据元素之间呈线性关系。字符串模式匹配:        1)朴素模式匹配算法        2)KMP算法手算KMP的next数组示意图:next[2] :next[3]: next[4]: next[5]: C语言KMP的next数组代码示例:void Createnext(char *sub, int *next){ assert(sub != NULL && next != NULL); int j = 2; //模式串的next指针 int k = 0; //next数组的回溯值,初始化为next[1]=0 int lenSub = strlen(sub); assert(lenSub != 0); next[0] = -1; next[1] = 0; while (j < lenSub){ if (sub[j-1] == sub[k]){ next[j] = ++k; j++; } else{ k = next[k]; if (k == -1){ k = 0; next[j] = k; j++; } } }}nextValue:void nextValue(char *sub, int *next) { int lenSub = strlen(sub); for(int j=2;j<lensub; j++){ if(sub[j]==sub[next[j]]) next[j]=next[next[j]] }}备注:         1) 实现next有多种不同方式, 对应不同的next数组使用        2) 根据实现方式不同, next数组整体+1不影响KMP算法。第三章 树和二叉树3.1 树和森林        定义(树):n(n≥0)个结点(数据元素)的有限集合,当 n=0 时,称为空树。3.1.1 树的基本术语        结点的度:结点所拥有的子树的个数。        叶子结点:度为 0 的结点,也称为终端结点。        分支结点:度不为 0 的结点,也称为非终端结点。        孩子:树某结点子树的根结点称为这个结点的孩子结点。        双亲:这个结点称为它孩子结点的双亲结点。        兄弟:具有同一个双亲的孩子结点互称为兄弟。        路径:结点序列 n1, n2, …, nk 称为一条由 n1 至 nk 的路径,当且仅当满足结点 ni 是 ni+1 的双亲(1<=i<k)的关系。        路径长度:路径上经过的边的个数。        祖先、子孙:如果有一条路径从结点 x 到结点 y,则 x 称为 y 的祖先,而 y 称为 x 的子孙。        结点所在层数:根结点的层数为 1;对其余结点,若某结点在第 k 层,则其孩子结点在第 k+1 层。        树的深度(高度):树所有结点的最大层数。        树的宽度:树每一层结点个数的最大值。        树的度:树各结点度的最大值。        树的路径长度:  从根到每个结点的路径长度总和        备注: 在线性结构,逻辑关系表现为前驱——后继,一对一; 在树结构,逻辑关系表现为双亲——孩子,一对多。        森林: 森林是m(m≥0)棵互不相交的树的集合, m可为0, 即空森林。3.1.2 树的性质        结点数=总度数+1        度为m的树第 i 层至多有 个结点(i≥1)        高度为h的m叉树至多有 个结点        具有n个结点的m叉树的最小高度为 最小高度推理过程图:3.1.3 树与森林的遍历树的遍历:先根遍历(先根后子树)后根遍历(先子树后根)层序遍历森林的遍历:前序遍历(先根, 后子树)序遍历(先子树后根, 其实就是后序遍历树)区别与联系:         1) 树的前序遍历等价于其树转化二叉树的前序遍历!        2) 树的后序遍历等价于其树转化二叉树的序遍历!3.1.4 树的存储结构双亲表示法图:孩子表示法图:孩子兄弟表示法图(树/森林转化为二叉树):3.1.5 树转二叉树在树转为二叉树后, 有以下结论:        1) 树的叶子结点数量 = 二叉树左空指针数量(形象理解为树越宽, 兄弟越多, 越是向右长)        2) 树的非叶子结点数量 = 二叉树右空指针-1(非叶子必有儿子, 右指针由儿子提供, -1是根节点多了一个右空指针)3.2 二叉树3.2.1 二叉树的性质斜树:左斜树:所有结点都只有左子树的二叉树右斜树:所有结点都只有右子树的二叉树        满二叉树:所有分支结点都存在左子树和右子树,且所有叶子都在同一层上的二叉树        完全二叉树:在满二叉树,从最后一个结点开始,连续去掉任意个结点得到的二叉树完全二叉树特点:叶子结点只能出现在最下两层且最下层的叶子结点都集在二叉树的左面完全二叉树如果有度为 1 的结点,只可能有一个,且该结点只有左孩子深度为 k 的完全二叉树在 k-1 层上一定是满二叉树在同样结点个数的二叉树,完全二叉树的深度最小        性质:在二叉树,如果叶子结点数为 n0,度为 2 的结点数为 n2,则有: n0=n2+1证明: 设 n 为二叉树的结点总数,n1 为二叉树度为 1 的结点数,则有: n=n0+n1+n2        在二叉树,除了根结点外,其余结点都有唯一的一个分枝进入,一个度为 1 的结点射出一个分枝,一个度为 2 的结点射出两个分枝,所以有:n=n1+2n2+1        性质:二叉树的第 i 层上最多有个结点(i≥1)        性质:一棵深度为 k 的二叉树,最多有 个结点        性质:具有 n 个结点的完全二叉树的深度为 向下取整+1 (或向上取整)证明:设具有 n 个结点的完全二叉树的深度为 k,则:≤n  <对不等式取对数,有:k-1 ≤ <k即:<k ≤ +1由于 k 是整数,故必有k= +1         性质:对一棵具有 n 个结点的完全二叉树从 1 开始按层序编号,对于任意的序号为 i(1≤i≤n)的结点(简称结点 i),有:如果 i>1,则结点 i 的双亲结点的序号为 i/2,否则结点 i 无双亲结点如果 2i≤n,则结点 i 的左孩子的序号为 2i,否则结点 i 无左孩子如果 2i+1≤n,则结点 i 的右孩子的序号为2i+1,否则结点 i 无右孩子        性质:若已知一棵二叉树的前序序列和序序列,或者序序列和后序序列,能唯一确定一颗二叉树。 3.2.2 二叉树的遍历        从根结点出发,按照某种次序访问树所有结点,并且每个结点仅被访问一次。前序遍历(深度优先遍历)序遍历后序遍历层序遍历(广度优先遍历)3.2.3 二叉树的存储链式存储图:顺序存储图:3.2.4 线索二叉树        利用二叉树n+1个空指针, 将指针指向结点的前驱和后继。线索二叉树是加上线索的链表结构,  是一种物理结构存储结构:示例图:三种线索化的对比图: 各自特点:3.3 哈夫曼树和哈夫曼编码        带权路径长度(WPL):从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和        最优二叉树(哈夫曼树):给定一组具有确定权值的叶子结点,带权路径长度最小的二叉树特点:权值越大的叶子结点越靠近根结点只有度为 0 和度为 2 的结点,不存在度为 1 的结点构造过程共新建了n-1个结点, 因此总结点数为2n-1        前缀编码:在一组编码,任一编码都不是其它任何编码的前缀, 前缀编码保证了在解码时不会有多种可能。         度为m的哈夫曼树: 通过只有度为m和度为0解非叶子结点 3.4 并查集        存储结构: 双亲表示法        实现功能: 并查(并两个集合, 查根结点)        优化: 小树并到大树, "高树变矮树"(压缩路径)第四章 图        定义:顶点集V和边集E组成,记为G = (V, E)        注意:线性表可以是空表,树可以是空树,但图不可以是空,即V一定是非空集, 边集E可以为空        子图:若图G=(V, E),G'=(V', E'),如果V' 属于 V 且E' 属于E,则称图G'是G的子图4.1 图的基本概念图的分类:        无向边:表示为(vi,vj),顶点vi和vj之间的边没有方向        有向边(弧):表示为<vi,vj>,从vi 到vj 的边有方向, vi为弧尾, vj为弧头        稠密图:边数很多的图        稀疏图:边数很少的图        无向完全图:无向图任意两个顶点之间都存在边        有向完全图:有向图任意两个顶点之间都存在方向相反的两条弧度、入度和出度:        顶点的度:在无向图,顶点 v 的度是指依附于该顶点的边数,通常记为TD (v)        顶点的入度:在有向图,顶点 v 的入度是指以该顶点为弧头的弧的数目,记为ID (v);        顶点的出度:在有向图,顶点 v 的出度是指以该顶点为弧尾的弧的数目,记为OD (v);        握手定理: 路径:         回路(环):第一个顶点和最后一个顶点相同的路径        简单路径:序列顶点不重复出现的路径        简单回路(简单环):除第一个和最后一个顶点外,其余顶点不重复出现的回路。        路径长度:非带权图——路径上边的个数        路径长度:带权图——路径上边的权值之和         极大连通子图: 连通的情况下, 包含尽可能多的边和顶点, 也称连通分量        极小连通子图: 删除该子图任何一条b边, 子图不再连通, 如生成树无向连通图:        连通顶点:在无向图,如果顶点vi和顶点vj(i≠j)之间有路径,则称顶点vi和vj是连通的        连通图:在无向图,如果任意两个顶点都是连通的,则称该无向图是连通图        连通分量:非连通图的极大连通子图、连通分量是对无向图的一种划分连通分量示意图:有向强连通图、强连通分量:        强连通顶点:在有向图,如果从顶点vi到顶点vj和从顶点vj到顶点vi均有路径,则称顶点vi和vj是强连通的        强连通图:在有向图,如果任意两个顶点都是强连通的,则称该有向图是强连通图        强连通分量:非强连通图的极大连通子图强连通分量示意图: 子图与生成子图:常考点无向图:        所有顶点的度之和=2|E|        若G是连通图,则最少有 n-1 条边(树),若 |E|>n-1,则一定有回路        若G是非连通图,则最多可能有 条边 (n-1个完全图+1个孤点)        无向完全图共有条边有向图:        所有顶点的出度之和=入度之和=|E|        所有顶点的度之和=2|E|        若G是强连通图,则最少有 n 条边(形成回路)        有向完全图共有条边图的遍历:从图某一顶点出发访问图所有顶,并且每个结点仅被访问一次。深度优先遍历序列(dfs)广度优先遍历序列(bfs)    备注:  调⽤BFS/DFS函数的次数 = 连通分量数4.2 图的存储结构 邻接矩阵:一维数组:存储图顶点的信息二维数组(邻接矩阵):存储图各顶点之间的邻接关系特点:一个图能唯一确定一个邻接矩阵,存储稀疏图时,浪费空间。空间复杂度为: O()。示意图:性质 (行*列) :邻接表:顶点表:所有边表的头指针和存储顶点信息的一维数组边表(邻接表):顶点 v 的所有邻接点链成的单链表示意图:特点:空间复杂度为:O(n+e), 适合存储稀疏图。两者区别:十字链表法图:备注:         1) 十字链表只用于存储有向图        2) 顺着绿色线路找: 找到指定顶点的所有出边        3) 顺着橙色线路找: 找到指定顶点的所有入边        4) 空间复杂度:O(|V|+|E|)邻接多重表图:备注:        1) 邻接多重表只适用于存储无向图        2) 空间复杂度:O(|V|+|E|)四者区别: 4.3 最小生成树        生成树:连通图的生成树是包含全部顶点的一个极小连通子图, 可用DFS和BFS生成。        生成树的代价:在无向连通网,生成树上各边的权值之和        最小生成树:在无向连通网,代价最小的生成树        性质: 各边权值互不相等时, 最小生成树是唯一的。边数为顶点数-1生成森林示意图:4.3.1 Prim算法        从某⼀个顶点开始构建⽣成树;每次将代价最⼩的新顶点纳⼊⽣成树,直到所有顶点都纳⼊为⽌。基于贪心算法的策略。        时间复杂度:O(|V|2) 适合⽤于边稠密图。4.3.2 Kruskal 算法(克鲁斯卡尔)        每次选择⼀条权值最⼩的边,使这条边的两头连通(原本已经连通的就不选), 直到所有结点都连通。基于贪心算法的策略。        时间复杂度:O( |E|log2|E| ) 适合⽤于边稀疏图。4.4 最短路径        非带权图: 边数最少的路径(广度优先遍历)        带权图: 边上的权值之和最少的路径4.4.1 Dijkstra算法        时间复杂度:O(n2)        备注: Dijkstra 算法不适⽤于有负权值的带权图4.4.2 Floyd算法核心代码:        时间复杂度:O(n3)        备注: 可以⽤于负权值带权图, 不能解决带有“负权回路”的图三者区别:4.5 有向⽆环图(DAG)描述表达式 (简化前) :描述表达式 (简化后) :4.6 拓扑排序        AOV⽹(Activity On Vertex NetWork,⽤顶点表示活动的⽹): ⽤DAG图(有向⽆环图)表示⼀个⼯程。顶点表示活动,有向边表示活动Vi必须先于活动Vj进⾏如图:拓扑排序实现:        ① 从AOV⽹选择⼀个没有前驱(⼊度为0)的顶点并输出。        ② 从⽹删除该顶点和所有以它为起点的有向边。        ③ 重复①和②直到当前的AOV⽹为空或当前⽹不存在⽆前驱的顶点为⽌。逆拓扑排序(可用DFS算法实现):        ① 从AOV⽹选择⼀个没有后继(出度为0)的顶点并输出。        ② 从⽹删除该顶点和所有以它为终点的有向边。        ③ 重复①和②直到当前的AOV⽹为空备注: 上三角(对角线为0)矩阵, 必不存在环, 拓扑序列必存在, 但拓扑不唯一。(拓扑唯一, 图不唯一)4.7 关键路径        在带权有向图,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为⽤边表示活动的⽹络,简称AOE⽹示意图:        关键活动: 从源点到汇点的有向路径可能有多条,所有路径,具有最⼤路径⻓度的路径称为 关键路径,⽽把关键路径上的活动称为关键活动。        事件vk的最早发⽣时间: 决定了所有从vk开始的活动能够开⼯的最早时间。        活动ai的最早开始时间: 指该活动弧的起点所表⽰的事件的最早发⽣时间。        事件vk的最迟发⽣时间: 它是指在不推迟整个⼯程完成的前提下,该事件最迟必须发⽣的时间。        活动ai的最迟开始时间: 它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差。        活动ai的时间余量:表⽰在不增加完成整个⼯程所需总时间的情况下,活动ai可以拖延的时间。d(k)=0的活动就是关键活动, 由关键活动可得关键路径。示例图:第五章 查找        静态查找 :不涉及插入和删除操作的查找        动态查找 :涉及插入和删除操作的查找        查找⻓度: 在查找运算,需要对⽐关键字的次数称为查找⻓度        平均查找长度:衡量查找算法的效率公式:5.1 顺序查找(线性查找):        顺序查找适合于存储结构为顺序存储或链接存储的线性表。  基本思想:从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。        时间复杂度: O(n)。有序顺序查找的ASL图:        无序查找失败时的平均查找长度:  n+1次 (带哨兵的情况)5. 2 折半查找:        元素必须是有序的,顺序存储结构。判定树是一颗平衡二叉树, 树高 (由n=-1得来)。        基本思想:用给定值k先与间结点的关键字比较,间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该间结点关键字的比较结果确定下一步查找哪个子表。        公式:mid=(low+high)/2, 即mid=low+1/2*(high-low);           1)相等,mid位置的元素即为所           2)>,low=mid+1;                3)<,high=mid-1。        时间复杂度: 二叉判定树的构造:         备注:对于静态查找表,一次排序后不再变化,折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说,不建议使用。失败结点的ASL不是方形结点, 而是其父节点。5.3 分块查找        分块查找,⼜称索引顺序查找。        基本思想:将查找表分为若干子块, 块内的元素可以无序, 块间的元素是有序的, 即前一个快的最大元素小于后一个块的最大元素。再建立索引表, 索引表的每个元素含有各块的最大关键字和第一个元素的地址。索引表按关键字有序排列。示意图:备注:         1) 设索引查找和块内查找的平均查找⻓度分别为LI、LS,则分块查找的平均查找⻓度为ASL=LI + LS        2) 将长度为n的查找表均匀分为b块, 每块s个记录, 在等概率情况下, 若在块内和索引表均采用顺序查找, 则平均查找长度为:5.4 二叉排序树        又称二叉查找树(BST,Binary Search Tree), 是具有如下性质的二叉树:左子树结点值 < 根结点值 < 右子树结点值        二叉排序树的插入:  新插入的结点 一定是叶子。二叉排序树的删除        1) 情况一, 删除叶结点, 直接删除        2) 情况二, 待删除结点只有一颗子树, 让子树代替待删除结点        3) 情况三, 待删除结点有左, 右子树, 则令待删除的直接前驱(或直接后继(序遍历))代替待删除结点。示意图: (30为直接前驱, 60为直接后继)平均查找效率: 主要取决于树的高度。时间复杂度: 5.5 平衡二叉树        简称平衡树(AVL树), 树上任一结点的左子树和右子树的 高度之差不超过1。 结点的平衡因子=左子树高-右子树高。平衡二叉树的插: LL型:RR型:RL型:LR型:        平衡二叉树的删除: 同上考点:        假设以表示深度为h的平衡树含有的最少结点数。 则有 = 0, = 1, = 2,并且有=  +          时间复杂度: 5.6 红黑树        与AVL树相比, 插入/删除 很多时候不会破坏“红黑”特性,无需频繁调整树的形态。因为AVL是高度差严格要不超过1, 红黑树高度差不超过2倍, 较为宽泛。定义:        ①每个结点或是红色,或是黑色的        ②根节点是黑色的        ③叶结点(外部结点、NULL结点、失败结点)均是黑色的        ④不存在两个相邻的红结点(即红结点的父节点和孩子结点均是黑色)        ⑤对每个结点,从该节点到任一叶结点的简单路径上,所含黑结点的数目相同        口诀: 左根右,根叶黑 不红红,黑路同示例图:性质:        性质1:从根节点到叶结点的最长路径不大于最短路径的2倍 (红结点只能穿插 在各个黑结点间)        性质2:有n个内部节点的红黑树高度          结论: 若根节点黑高为h,内部结点数(关键字)最多有 , 最少有示例图:红黑树的插入操作:红黑树的插入示例图:         红黑树的删除: 和“二叉排序树的删除”一样! 具体还是算了吧, 放过自己。。。        时间复杂度: 5.7 B树        B树,⼜称多路平衡查找树,B树所被允许的孩⼦个数的最⼤值称为B树的阶,通常⽤m表示。 m阶B树的特性:        1)树每个结点⾄多有m棵⼦树,即⾄多含有m-1个关键字。        2)若根结点不是终端结点,则⾄少有两棵⼦树。        3)除根结点外的所有⾮叶结点⾄少有 棵⼦树,即⾄少含有个关键字。         4) 所有的叶结点都出现在同⼀层次上,并且不带信息, ( 指向这些结点的指针为空 ) 。        5) 最小高度:    (n为关键字, 注意区分结点)        6) 最大高度:         7) 所有⼦树⾼度要相同        8) 叶结点对应查找失败的情况, 即n个关键字有n+1个叶子结点示例图: B树的插入(5阶为例):B树的删除:        1) 若被删除关键字在终端节点,则直接删除该关键字 (要注意节点关键字个数是否低于下限 ⌈m/2⌉ − 1)        2) 若被删除关键字在⾮终端节点,则⽤直接前驱或直接后继来替代被删除的关键字 删除77:删除38:删除90:        3) 若被删除关键字所在结点删除前的关键字个数低于下限,且此时与该结点相邻的左、右兄弟结 点的关键字个数均=⌈m/2⌉ − 1,则将关键字删除后与左(或右)兄弟结点及双亲结点的关键字进⾏合并 删除49: 5.8 B+树⼀棵m阶的B+树需满⾜下列条件        1)每个分⽀结点最多有m棵⼦树(孩⼦结点)。        2)⾮叶根结点⾄少有两棵⼦树,其他每个分⽀结点⾄少有 ⌈m/2⌉ 棵⼦树。        3)结点的⼦树个数与关键字个数相等。        4)所有叶结点包含全部关键字及指向相应记录的指针,叶结点将关键字按⼤⼩顺序排列,并且相邻叶结点按⼤⼩顺序相互链接起来        5)所有分⽀结点仅包含它的各个⼦结点关键字的最⼤值及指向其⼦结点的指针。所有⾮叶结点仅起索引作⽤,        6) 所有⼦树⾼度要相同B+树示例图:B+树与B树的对比图:5.9 哈希表(Hash)        根据数据元素的关键字 计算出它在散列表的存储地址。        哈希函数: 建⽴了“关键字”→“存储地址”的映射关系。        冲突(碰撞):在散列表插⼊⼀个数据元素时,需要根据关键字的值确定其存储地址,若 该地址已经存储了其他元素,则称这种情况为“冲突(碰撞)”        同义词:若不同的关键字通过散列函数映射到同⼀个存储地址,则称它们为“同义词”        复杂度分析:对于无冲突的Hash表而言,查找复杂度为O(1) 5.9.1 构造哈希函数        1) 除留余数法 —— H(key) = key % p, 取⼀个不⼤于m但最接近或等于m的质数p        适⽤场景:较为通⽤,只要关键字是整数即可        2) 直接定址法 —— H(key) = key 或 H(key) = a*key + b        适⽤场景:关键字分布基本连续        3) 数字分析法 —— 选取数码分布较为均匀的若⼲位作为散列地        适⽤场景:关键字集合已知,且关键字的某⼏个数码位分布均匀        4) 平⽅取法(二次探测法)——取关键字的平⽅值的间⼏位作为散列地址        适⽤场景:关键字的每位取值都不够均匀。5.9.2 处理冲突拉链法示意图:开放定址法:        1) 线性探测法        2) 平⽅探测法        3) 双散列法        4) 伪随机序列法示意图:        删除操作: 采用开放定址法时, 只能逻辑删除。        装填因子: 表记录数 / 散列表长度 。        备注: 平均查找长度的查找失败包含不放元素的情况。(特殊: 根据散列函数来算: 2010真题)        聚集: 处理冲突的方法选取不当,而导致不同关键字的元素对同一散列地址进行争夺的现象第六章 排序        稳定 :如果a原本在b前面,而a=b,排序之后a仍然在b的前面;        内排序 :所有排序操作都在内存完成;        外排序 :由于数据太大,因此把数据放在磁盘,而排序通过磁盘和内存的数据传输才能进行。参考博客:超详细十大经典排序算法总结(java代码)c或者cpp的也可以明白_Top_Spirit的博客-CSDN博客6.1 直接插入排序动图演示:         优化: 折半插入排序6.2 希尔排序        又称缩小增量排序, 先将待排序表分割成若⼲形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”⼦表,对各个⼦表分别进⾏直接插⼊排序。缩⼩增量d,重复上述过程,直到d=1为⽌。建议每次将增量缩⼩⼀半。示例图:6.3 冒泡排序动图演示:6.4 快速排序算法思想:        1) 在待排序表L[1…n]任取⼀个元素pivot作为枢轴(或基准)        2) 通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n],使得L[1…k-1]的所有元素⼩于pivot,L[k+1…n]的所有元素⼤于等于 pivot,则pivot放在了其最终位置L(k)上,这个过程称为⼀次“划分”。        3) 然后分别递归地对两个⼦表重复上述过程,直每部分内只有⼀个元素或空为⽌,即所有元素放在了其最终位置上。示例图:  6.5 简单选择排序        算法思想: 每⼀趟在待排序元素选取关键字最⼩的元素加⼊有序⼦序列。动画演示:6.6 堆排序        ⼤根堆: 若满⾜:L(i)≥L(2i)且L(i)≥L(2i+1) (1 ≤ i ≤n/2 )        ⼩根堆: 若满⾜:L(i)≤L(2i)且L(i)≤L(2i+1) (1 ≤ i ≤n/2 )大根堆示例图:6.6.1 建立大根堆        思路:从开始, 把所有⾮终端结点都检查⼀遍,是否满足大根堆的要,如果不满⾜,则进⾏调整。若元素互换破坏了下⼀级的堆,则采⽤相同的方法继续往下调整(⼩元素不断“下坠”)小元素下坠示例图:          结论: 建堆的过程,关键字对⽐次数不超过4n,建堆时间复杂度=O(n)6.6.2 堆的插入与删除        插入: 将新增元素放到表尾, 而后根据大小根堆进行上升调整。        删除: 被删除的元素⽤堆底元素替代,然后让该 元素不断“下坠”,直到⽆法下坠为⽌排序动图演示:6.7 归并排序        该算法是采用分治法, 把两个或多个已经有序的序列合并成⼀个。2路归并图:        结论:n个元素进⾏k路归并排序,归并趟数= 6.8 基数排序 (低位优先)        基数排序是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组的数的最大的位数;动图演示:         时间复杂度: ⼀趟分配O(n),⼀趟收集O(r),总共 d 趟分配、收集,总的时间复杂度=O(d(n+r)) , 其把d为关键字拆 为d个部分, r为每个部分可能 取得 r 个值。基数排序适用场景:        ①数据元素的关键字可以⽅便地拆分为 d 组,且 d 较⼩        ②每组关键字的取值范围不⼤,即 r 较⼩        ③数据元素个数 n 较⼤如:内部排序总结:         基本有序:  直接插入(比较最少), 冒泡(趟数最少)6.9 外部排序        数据元素太多,⽆法⼀次全部读⼊内存进⾏排序, 读写磁盘的频率成为衡量外部排序算法的主要因素。示例图:多路归并:        结论: 采⽤多路归并可以减少归并趟数,从⽽减少磁盘I/O(读写)次数。对 r 个初始归并段,做k路归并,则归并树可⽤ k 叉树表示 若树⾼为h,则归并趟数 = h-1 = 。K越大, r越小, 读写磁盘次数越少。(缺点: k越大, 内部排序时间越大)6.9.1 败者树        使⽤k路平衡归并策略,选出⼀个最小元素需要对⽐关键字 (k-1)次,导致内部归并所需时间增加。因此引入败者树。示例图:        结论: 对于 k 路归并,第⼀次构造败者 树需要对⽐关键字 k-1 次 , 有了败者树,选出最⼩元素,只需对⽐关键字次6.9.2 置换-选择排序        使用置换-选择排序可以减少初始化归并段。示意图: 6.9.3 最佳归并树原理图:        注意:对于k叉归并,若初始归并段的数量⽆法构成严格的 k 叉归并树, 则需要补充⼏个⻓度为 0 的“虚段”,再进⾏ k 叉哈夫曼树的构造。示例图: 添加虚段数目: 难点:结束!  !  !注: 以上部分图片素材来自王道数据结构我要的图文并茂关注

大家在看

recommend-type

Allegro16.6约束规则设置详解-SCC

Allegro16.6约束规则设置详解_SCCAllegro16.6约束规则设置详解_SCCAllegro16.6约束规则设置详解_SCCAllegro16.6约束规则设置详解_SCC
recommend-type

xilinx fpga tpg ip 中文版

xilinx fpga tpg ip 中文版
recommend-type

Noise-Pollution-Monitoring-Device

基于物联网的噪声污染监测系统1 以下存储库包含在 IOT 的帮助下设计噪声污染监测系统所需的文件。 它使用 firebase 作为实时服务器,在 Python 脚本的帮助下上传数据,该脚本在虚拟端口的帮助下跟踪 Proteus 软件中设计的原型的读数。 部署 Web 应用程序以使用户了解正在上传的数据类型。 该存储库包括 Arduino hex 文件、Python 脚本、HTML CSS JS 代码、Proteus 电路软件原型和上述项目的报告。
recommend-type

lovense-link:一个简单的 CLI 来获取你喜欢的玩具的控制链接

洛文斯链接 让您从Lovenses API检索控件链接 具有 CLI 命令和 Web 界面 安装 npm i -g lovense-link 用 lovense-link 您需要一个来自以下地址的 API 密钥: : 重要提示:在我的应用程序 > API LAN 中激活API LAN 启用 API LAN 设置随机回调 URL(例如: : ) 学分 (c) 2020 Miiss Neko。 麻省理工学院执照
recommend-type

RK3588全套硬件设计参考文件,提供原理图和PCB文件!

RK3588全套硬件设计参考文件,是全套!包括资料文档、AIOT和NVR应用板卡Cadence设计原理图文件,PCB library。DDR部分Cadence原理图和PCB文件。文件大小为197MB。

最新推荐

recommend-type

hiddenite-shops:Minecraft Bukkit商店交易插件

Minecraft 是一款流行的沙盒游戏,允许玩家在虚拟世界中探索、建造和生存。为了增加游戏的可玩性和互动性,开发者们创造了各种插件来扩展游戏的功能。Bukkit 是一个流行的 Minecraft 服务器端插件API,它允许开发人员创建插件来增强服务器的功能。本文将详细介绍一个基于 Bukkit API 的插件——hiddenite-shops,该插件的主要功能是在 Minecraft 游戏中的商店系统中进行商品的买卖。 首先,我们需要了解 Bukkit 是什么。Bukkit 是一款开源的 Minecraft 服务器软件,它允许开发人员利用 Java 编程语言创建插件。这些插件可以修改、增强游戏的玩法或添加新的游戏元素。Bukkit 插件通常托管在各种在线代码托管平台如 GitHub 上,供玩家和服务器运营者下载和安装。 说到 hiddenite-shops 插件,顾名思义,这是一个专注于在 Minecraft 中创建商店系统的插件。通过这个插件,玩家可以创建自己的商店,并在其中摆放出售的商品。同时,玩家也可以在别人的商店中购物。这样的插件极大地丰富了游戏内的交易模式,增加了角色扮演的元素,使游戏体验更加多元化。 在功能方面,hiddenite-shops 插件可能具备以下特点: 1. 商品买卖:玩家可以把自己不需要的物品放置到商店中出售,并且可以设定价格。其他玩家可以购买这些商品,从而促进游戏内的经济流通。 2. 商店管理:每个玩家可以创建属于自己的商店,对其商店进行管理,例如更新商品、调整价格、装饰商店界面等。 3. 货币系统:插件可能包含一个内置的货币系统,允许玩家通过虚拟货币来购买和出售商品。这种货币可能需要玩家通过游戏中的某些行为来获取,比如采矿、钓鱼或完成任务。 4. 权限控制:管理员可以对商店进行监管,设定哪些玩家可以创建商店,或者限制商店的某些功能,以维护游戏服务器的秩序。 5. 交易记录:为了防止诈骗和纠纷,hiddenite-shops 插件可能会记录所有交易的详细信息,包括买卖双方、交易时间和商品详情等。 在技术实现上,hiddenite-shops 插件需要遵循 Bukkit API 的规范,编写相应的 Java 代码来实现上述功能。这涉及到对事件监听器的编程,用于响应游戏内的各种动作和事件。插件的开发人员需要熟悉 Bukkit API、Minecraft 游戏机制以及 Java 编程语言。 在文件名称列表中,提到的 "hiddenite-shops-master" 很可能是插件代码的仓库名称,表示这是一个包含所有相关源代码、文档和资源文件的主版本。"master" 通常指代主分支,是代码的最新且稳定版本。在 GitHub 等代码托管服务上,开发者通常会在 master 分支上维护代码,并将开发中的新特性放在其他分支上,直到足够稳定后再合并到 master。 总的来说,hiddenite-shops 插件是对 Minecraft Bukkit 服务器功能的一个有力补充,它为游戏世界中的经济和角色扮演提供了新的元素,使得玩家之间的交易和互动更加丰富和真实。通过理解和掌握该插件的使用,Minecraft 服务器运营者可以为他们的社区带来更加有趣和复杂的游戏体验。
recommend-type

【SSM框架快速入门】

# 摘要 本文旨在详细介绍SSM(Spring + SpringMVC + MyBatis)框架的基础与高级应用,并通过实战案例分析深入解析其在项目开发中的实际运用。首先,文章对SSM框架进行了概述,随后逐章深入解析了核心组件和高级特性,包括Spring的依赖注入、AOP编程、SpringMVC的工作流程以及MyBatis的数据持久化。接着,文章详细阐述了SSM框架的整合开发基础,项目结构配置,以及开发环境的搭建和调试。在高级应用
recommend-type

项目环境搭建及系统使用说明用例

### Postman 示例 API 项目本地部署教程 对于希望了解如何搭建和使用示例项目的用户来说,可以从以下几个方面入手: #### 环境准备 为了成功完成项目的本地部署,需要按照以下步骤操作。首先,将目标项目 fork 至自己的 GitHub 账户下[^1]。此过程允许开发者拥有独立的代码仓库副本以便于后续修改。 接着,在本地创建一个新的虚拟环境来隔离项目所需的依赖项,并通过 `requirements.txt` 文件安装必要的库文件。具体命令如下所示: ```bash python -m venv my_env source my_env/bin/activate # Linu
recommend-type

Windows Media Encoder 64位双语言版发布

Windows Media Encoder 64位(英文和日文)的知识点涵盖了软件功能、操作界面、编码特性、支持的设备以及API和SDK等方面,以下将对这些内容进行详细解读。 1. 软件功能和应用领域: Windows Media Encoder 64位是一款面向Windows操作系统的媒体编码软件,支持64位系统架构,是Windows Media 9系列中的一部分。该软件的主要功能包括录制和转换视频文件。它能够让用户通过视频捕捉设备或直接从电脑桌面上录制视频,同时提供了丰富的文件格式转换选项。Windows Media Encoder广泛应用于网络现场直播、点播内容的提供以及视频文件的制作。 2. 用户界面和操作向导: 软件提供了一个新的用户界面和向导,旨在使初学者和专业用户都容易上手。通过简化的设置流程和直观的制作指导,用户能够快速设定和制作影片。向导会引导用户选择适当的分辨率、比特率和输出格式等关键参数。 3. 编码特性和技术: Windows Media Encoder 64位引入了新的编码技术,如去隔行(de-interlacing)、逆向电影转换(inverse telecine)和屏幕捕捉,这些技术能够显著提高视频输出的品质。软件支持从最低320x240分辨率60帧每秒(fps)到最高640x480分辨率30fps的视频捕捉。此外,它还能处理最大到30GB大小的文件,这对于长时间视频录制尤其有用。 4. 支持的捕捉设备: Windows Media Encoder 64位支持多种视频捕捉设备,包括但不限于Winnov、ATI、Hauppauge等专业视频捕捉卡,以及USB接口的视频摄像头。这为用户提供了灵活性,可以根据需要选择合适的硬件设备。 5. 高级控制选项和网络集成: Windows Media Encoder SDK是一个重要的组件,它为网站开发者提供了全面的编码控制功能。开发者可以利用它实现从网络(局域网)进行远程控制,或通过API编程接口和ASP(Active Server Pages)进行程序化的控制和管理。这使得Windows Media Encoder能够更好地融入网站和应用程序中,提供了更广阔的使用场景,例如自动化的视频处理流水线。 6. 兼容性和语言版本: 本文件提供的版本是Windows Media Encoder 64位的英文和日文版本。对于需要支持多语言用户界面的场合,这两个版本的软件能够满足不同语言用户的需求。经过测试,这些版本均能正常使用,表明了软件的兼容性和稳定性。 总结来说,Windows Media Encoder 64位(英文和日文)是一款功能强大、易于操作的媒体编码软件。它在操作便捷性、视频编码品质、设备兼容性和程序化控制等方面表现突出,适合用于视频内容的创建、管理和分发。对于需要高质量视频输出和网络集成的用户而言,无论是个人创作者还是专业视频制作团队,该软件都是一种理想的选择。
recommend-type

【IEEE 14总线系统Simulink模型:从零到专家的终极指南】:构建、仿真及故障诊断

# 摘要 本文详细介绍了IEEE 14总线系统的Simulink模型构建、仿真分析以及故障诊断技术。第一章提供了系统概述,为后续章节打下基础。第二章深入探讨了Simulink模型的构建,涵盖了用户界面、工具模块、电路元件、负荷及发电机组建模方法,以及模型的参数化和优化。第三章讲述了如何进行IEEE 14总线系统的仿真以及如
recommend-type

树莓派改中文

### 树莓派修改系统语言为中文教程 要将树莓派的操作系统界面或设置更改为中文,可以按照以下方法操作: #### 方法一:通过图形化界面更改语言 如果已经启用了树莓派的桌面环境并能够正常访问其图形化界面,则可以通过以下方式更改系统语言: 1. 打开 **Preferences(首选项)** 菜单。 2. 进入 **Raspberry Pi Configuration(树莓派配置)** -> **Localisation(本地化)**。 3. 设置 **Change Locale(更改区域设置)** 并选择 `zh_CN.UTF-8` 或其他适合的语言编码[^1]。 完成上述步骤后,重启设
recommend-type

SenseLock精锐IV C# API使用与代码示例教程

根据给定文件信息,我们可以推断出以下知识点: 标题中提到了"SenseLock 精锐IV C# 使用说明及例子",说明此文档是关于SenseLock公司出品的精锐IV产品,使用C#语言开发的API调用方法及相关示例的说明。SenseLock可能是一家专注于安全产品或服务的公司,而精锐IV是其旗下的一款产品,可能是与安全、加密或者硬件锁定相关的技术解决方案。文档可能包含了如何将该技术集成到C#开发的项目中,以及如何使用该技术的详细步骤和代码示例。 描述中提到"SenseLock API调用 测试通过 还有代码 及相关文档",说明文档中不仅有SenseLock产品的C# API调用方法,而且这些方法经过了测试验证,并且提供了相应的代码样例以及相关的技术文档。这表明用户可以通过阅读这份资料来了解如何在C#环境中使用SenseLock提供的API进行软件开发,以及如何在开发过程中解决潜在的问题。 标签为"SenseLock C# API",进一步确认了该文件的内容是关于SenseLock公司提供的C#编程语言接口。标签的作用是作为标识和分类,方便用户根据关键词快速检索到相关的文件。这里的信息提示我们,此文件对于那些希望在C#程序中集成SenseLock技术的开发者来说非常有价值。 压缩包的文件名称列表显示有两个文件:一个是"精锐IV C# 使用.docx",这个文件很可能是一个Word文档,用于提供详细的使用说明和例子,这可能包括精锐IV产品的功能介绍、API接口的详细说明、使用场景、示例代码等;另一个是"32bitdll",这可能是一个32位的动态链接库文件,该文件是C#程序中可以被调用的二进制文件,用于执行特定的API函数。 总结一下,该压缩包文件可能包含以下几个方面的知识点: 1. SenseLock精锐IV产品的概述:介绍产品的功能、特性以及可能的应用场景。 2. C# API接口使用说明:详细解释API的使用方法,包括如何调用特定的API函数,以及每个函数的参数和返回值。 3. API调用示例代码:提供在C#环境中调用SenseLock API的具体代码样例,帮助开发者快速学习和应用。 4. 测试验证信息:说明API调用方法已经通过了哪些测试,保证其可靠性和有效性。 5. 32位动态链接库文件:为C#项目提供必要的可执行代码,用于实现API调用的功能。 该文档对于希望在C#项目中集成SenseLock精锐IV产品的开发者来说,是一份非常有价值的参考资料,能够帮助他们理解如何在软件开发中利用SenseLock提供的技术,并快速实现解决方案。
recommend-type

深入理解PgSQL绿色版:揭秘其优势与五大应用案例

# 摘要 PgSQL绿色版是一种轻量级、易于部署的数据库系统,旨在提供高性能、高稳定性的数据库服务,同时保持环境兼容性和可移植性。本文首先概述了PgSQL绿色版的基本概念,随后详细阐述了其核心优势,包括高效的数据存储结构和并发处理能力、简单的安装与部署流程,以及对多种操作系统的支持。通过分析不同应用场景如Web应用、数据分析、开源项目、嵌入式设备和大数据处理的案例,本文展示了PgS
recommend-type

ubuntu开机pcie bus error刷屏

### Ubuntu 开机 PCIE Bus Error 刷屏问题解决方案 在遇到 Ubuntu 开机时因 `PCIE Bus Error` 导致刷屏的问题时,可以通过调整系统的启动参数来解决问题。以下是具体的解决方法: #### 修改 Grub 文件配置 通过编辑 `/etc/default/grub` 文件中的启动参数可以有效缓解此问题。 1. **进入恢复模式** 如果系统无法正常启动到图形界面,则需要先通过 GRUB 菜单进入恢复模式。按下电源键启动计算机,在 BIOS 自检完成后迅速按住 Shift 键以调出 GRUB 启动菜单。选择带有 `(recovery mode)
recommend-type

RubyInstaller.zip: Windows平台Ruby安装方案

RubyInstaller是一个为Windows操作系统设计的Ruby语言环境的安装程序。在了解RubyInstaller之前,首先需要了解Ruby语言及其安装环境的特点。 Ruby是一种高级的、解释型的编程语言,以简洁和可读性强著称,由松本行弘(Yukihiro "Matz" Matsumoto)开发。它广泛应用于Web开发领域,特别是与Ruby on Rails框架的结合使用,可以快速开发出功能强大的Web应用程序。Ruby的特点还包括面向对象的编程范式,动态类型和反射能力。 在Windows平台上安装Ruby语言环境较为复杂,因为Ruby本身以及它所需要的许多库和扩展都是为类Unix系统设计的。这意味着在Windows上直接安装Ruby可能会遇到路径分隔符、文件权限等兼容性问题。因此,RubyInstaller的出现解决了这一问题,它为Windows用户提供了快捷安装Ruby及其开发环境的解决方案。 根据给定的文件信息,RubyInstaller项目提供了针对Ruby版本2.3及以下版本的安装程序。重要的是,描述中提到了对于Ruby版本2.4及以上版本的用户应该参考RubyInstaller2。RubyInstaller2是一个更新的项目,它支持更多的Ruby版本和更多的特性,如预编译的扩展和更新的工具链。这一点对于希望在Windows系统上安装Ruby的开发者来说至关重要,因为它涉及到选择正确的安装包以确保最大的兼容性和最佳的用户体验。 文件标题中提到的“构建配方”可能指的是RubyInstaller在安装过程中会配置的一些预设设置和脚本,这些设置能够帮助用户快速配置开发环境,而无需手动一个个步骤设置。通过使用“构建配方”,开发者可以节省时间,减少安装过程中可能发生的配置错误。 此外,标题中还提到了RubyInstaller是开源项目,使用的是3-clause BSD许可。这意味着该软件的源代码对所有人开放,用户可以在遵守BSD许可规定的前提下自由地使用、修改和分发软件。3-clause BSD许可通常要求保留原始作者的著作权声明和许可声明,不承担任何担保责任,并且不得使用原作者的名字为衍生作品背书。 文件的描述中还隐含了RubyInstaller的更新和维护情况。一般情况下,开源项目会有持续的社区支持,以解决新出现的问题并更新软件以兼容新的操作系统和依赖库。因此,用户需要关注RubyInstaller及其更新版本的公告,以确保他们使用的是最新且稳定的安全版本。 最后,从压缩包子文件的文件名称“rubyinstaller-master”可以看出,这是RubyInstaller项目的主分支。在软件开发中,"master"通常指主开发分支,意味着这是最稳定和最接近发布的版本。开发者在使用该项目时,应该确保他们下载的是来自可信任源的安装包,避免使用可能被篡改过的安装程序。 总结来说,RubyInstaller是为Windows用户提供了一个简便的方式来安装和配置Ruby编程语言环境的工具。它支持Ruby的早期版本,但用户应根据Ruby的最新版本选择合适的安装程序。作为一个开源项目,RubyInstaller允许用户自由地使用和修改源代码,并在遵守相应的许可协议下进行分发。对于任何开源项目,关注其安全更新和社区支持都是十分必要的。
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部