- 博客(48)
- 收藏
- 关注
RSS订阅原创 C编程题2
1.写一个用矩阵法求定积分的通用函数，求#include<stdio.h>#include<math.h>float integral(float a,float b,int n){int i;float x,h,s;h=(b-1)/n;x=a;s=0;for(i=1;i<=n;i++){ x=x+h; s=s+sin(x)*h;}...
2018-04-11 13:36:27
747
原创 数据结构题目和知识点
查找：1.有序表折半查找成功/不成功时最多的比较次数: log2(n+1)2.判定树外部结点是：一次失败查找过程终止的结点3.分开查找线性表m个元素时，每块分为根号m个结点4.具有n层结点的AVL树至少有（）个结点：N0=0;N1=1;N2=2;Nn=N(n-1)+N(n-2)+15.对于二叉排序树进行（）可以得到从小到达的结点序列：中序遍历6.衡量查找算法好坏的主要标准是：关键字的平均比较...
2018-04-02 10:49:40
2247
原创 C编程题
1.在键盘上输出一个正整数，要求将其十位数和个位数对调。#include<stdio.h>int main(){int a,i,j;printf("请输入一个正整数：");scanf("%d",&a);while(a<=0||a!=(int)a) {printf("输入错误\n请输入一个正整数：");scanf("%d",&a);}i
2018-03-25 14:24:30
2767
原创 基数排序
前面所讨论的排序算法均是基于关键字之间的比较来实现的，而基数排序是通过“分配”和“收集”过程来实现排序。基数排序是一种借助于多关键字排序的思想对单关键字排序的方法。一般地，记录R[i]的关键字R[i].key是由d位数字组成，即kd-1，kd-2，…k0，每一个数字表示关键字的一位。其中kd-1为最高位，k0是最低位，每一位的值都在0≤ki＜r范围内，其中r称为基数。基数排序有两种：最低位优先（L...
2018-03-16 10:51:07
1707
原创 归并排序
归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。Merge()实现了一次归并 :void Merge(RecType R[],int low,int mid,int high) { RecType *R1; int i=low,j=mid+1,k=0; //k是R1的下标,i、j分别为第1、2段的下...
2018-03-16 10:45:36
407
原创 选择排序
选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。两种选择排序方法：（1）简单选择排序（或称直接选择排序）（2）堆排序一、直接选择排序基本思想：第i趟排序开始时，当前有序区和无序区分别为R[0..i-1]和R[i..n-1]（0≤i＜n-1），该趟排序则是从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]...
2018-03-16 10:39:46
1127
原创 插入排序、交换排序
一、排序的基本概念 所谓排序，是要整理表中的记录，使之按关键字递增（或递减）有序排列。其确切定义如下：输入：n个记录,R0,R1,…,Rn-1,其相应的关键字分别为k0,k1,…,kn-1。输出：Ri,0,Ri,1,…,Ri,n-1,使得ki,0≤ki,1≤…≤ki,n-1 (或ki,0≥ki,1≥…≥ki,n-1)。算法的稳定性当待排序记录的关键字均不相同时，排序的结果是惟一的，否则排序的结果不...
2018-03-15 17:21:49
1256
原创 哈希表查找
一、哈希表的基本概念哈希表（Hash Table）又称散列表，是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。哈希表存储的基本思路是：设要存储的对象个数为n，设置一个长度为m（m≥n）的连续内存单元。以线性表中每个对象的关键字ki（0≤i≤n-1）为自变量，通过一个称为哈希函数的函数h(ki)，把ki映射为内存单元的地址（或称下标）h(ki)，并把该对象存储在这...
2018-03-15 11:16:01
11599
2
原创 树表的查找
顺序查找、二分(折半)查找和索引查找都是静态查找表，其中二分查找的效率最高。静态查找表的缺点是当表的插入或删除操作频繁时,为维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消二分查找的优点（二分查找和分块查找只适用于静态查找表）。若要对动态查找表进行高效率的查找，可以使用树表。以二叉树或树作为表的组织形式，称为树表。一、二叉排序树 二叉排序树（简称BST）又称二叉查找...
2018-03-14 19:25:16
4992
原创 线性表的查找
一、查找的基本概念被查找的对象是由一组记录组成的表或文件,而每个记录则由若干个数据项组成,并假设每个记录都有一个能唯一标识该记录的关键字。在这种条件下,查找的定义是：给定一个值k,在含有n个记录的表中找出关键字等于k的记录。若找到，则查找成功，返回该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息。 若在查找的同时对表做修改运算（如插入和删除），则相应的表称之为动态查找表，否则称之...
2018-03-14 12:25:48
12104
原创 拓扑排序
一、拓扑排序设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列v1，v2，…，vn称为一个拓扑序列当且仅当该顶点序列满足下列条件：若<i，j>是图中的边（即从顶点i到j有一条路径），则在拓扑序列中顶点i必须排在顶点j之前。在一个有向图中找一个拓扑序列的过程称为拓扑排序。 例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业，假设这些课程的名称与相应代号有...
2018-03-13 19:21:11
432
原创 最短路径
一、路径的概念在一个无权图中，若从一顶点到另一顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。对于带权图，考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义...
2018-03-13 15:44:45
390
原创 生成树和最小生成树
一、生成树的概念 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的(n-1)条边。如果在一棵生成树上添加一条边，必定构成一个环。一棵有n个顶点的生成树(连通无回路图)有且仅有(n-1)条边，如果一个图有n个顶点和小于(n-1)条边，则是非连通图。如果它多于(n-1)条边，则一定有回路。但是，有(n-1)条边的图不一定都是生成树。最小生成树：图的所有生成树中具有边上的权值...
2018-03-13 15:29:22
6546
原创 图的遍历
一、 图的遍历的概念从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。如果给定图是连通的无向图或者是强连通的有向图，则遍历过程一次就能完成，并可按访问的先后顺序得到由该图所有顶点组成的一个序列。根据搜索方法的不同，图的遍历方法有两种：一种叫做深度优先搜索法（DFS）；另一种叫做广度优先搜索法（BFS）。 二、 深...
2018-03-12 14:50:33
531
原创 图的存储结构
一、邻接矩阵存储方法邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n（n＞0）个顶点的图，顶点的顺序依次为0～n-1，则G的邻接矩阵A是n阶方阵，其定义如下：（1）如果G是无向图，则： A[i][j]=1：若(i,j)∈E(G) 0:其他（2）如果G是有向图，则： A[i][j]=1：若<i,j>∈E(G) 0:其他（3）如果G是带权无向图，则：...
2018-03-12 14:26:15
9263
2
原创 图
一、图的基本概念1. 图的定义 图（Graph）G由两个集合V（vertex）和E（Edge）组成，记为G=(V，E)。其中V是顶点的有限集合，记为V(G)，E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。 说明：对于n个顶点的图，对每个顶点连续编号，即顶点的编号为0－n-1。通过编号唯一确定一个顶点。在图G中，如果代表边的顶点对是无序的，则称G为无向图，无向图中代表边的...
2018-03-12 14:12:24
2738
原创 哈夫曼树
一、 哈夫曼树的定义 设二叉树具有n个带权值的叶子节点，那么从根节点到各个叶子节点的路径长度与相应节点权值的乘积的和，叫做二叉树的带权路径长度。其中n表示叶子节点的数目，wi表示叶子节点ki的权值，li表示根到ki之间的路径长度（即从叶子节点到达根节点的分支数）。具有最小带权路径长度的二叉树称为哈夫曼树，也是最优树，由哈夫曼于1951提出。 二、 构造哈夫曼树 根据哈夫曼树的定义,一棵二叉树要...
2018-03-11 12:34:13
705
原创 线索二叉树
一、线索二叉树1.线索二叉树的概念 对于具有n个节点的二叉树，采用二叉链存储结构时，每个节点有两个指针域，总共有2n个指针域，又由于只有n-1个节点被有效指针所指向（n个节点中只有树根节点没有被有效指针域所指向），则共有2n-(n-1)=n+1个空链域。遍历二叉树的结果是一个节点的线性序列。可以利用这些空链域存放指向节点的前驱和后继节点的指针。这样的指向该线性序列中的“前驱”和“后继”的指针，称作...
2018-03-11 12:23:02
312
原创 C语言错题整理
1.如：int a=10,b=6,c; 如果c=a/b； 此时的c=1，因为整型的除法不是四舍五入，只保留小数位之前的数。2.A&&B：当A(非零值)是真，且B(非零值)是真，才会返回1，表示真；否则，返回0，表示假。 A||B:当A(非零值)是真，或者B(非零值)是真，会返回1，表示真；否则，返回0，表示假。 ！A，将A取反，假设A的值或者表达式为真...
2018-03-10 16:53:13
102556
5
原创 二叉树的构造
一、二叉树的构造 同一棵二叉树具有唯一先序序列、中序序列和后序序列。但不同的二叉树可能具有相同的先序序列、中序序列和后序序列。给定先序、中序和后序遍历序列可以唯一确定这棵二叉树的树形。仅由一个先序序列（或中序序列、后序序列），无法确定这棵二叉树的树形。定理1：任何n（n≥0）个不同节点的二又树，都可由它的中序序列和先序序列唯一地确定。由上述定理得到以下构造二叉树的算法：BTNode *Create...
2018-03-10 14:45:42
540
原创 二叉树的遍历
一、二叉树的遍历二叉树遍历的概念： 二叉树的遍历是指按照一定次序访问树中所有节点，并且每个节点仅被访问一次的过程。它是最基本的运算,是二叉树中所有其他运算的基础。1. 先序遍历过程先序遍历二叉树的过程是：① 访问根节点；②先序遍历左子树；③先序遍历右子树。2. 中序遍历过程中序遍历二叉树的过程是：① 中序遍历左子树；② 访问根节点；③中序遍历右子树。3. 后序遍历过程后序遍历二叉树的过程是：...
2018-03-10 14:40:42
316
原创 二叉树的存储结构和实现
一、二叉树存储结构 1）二叉树的顺序存储结构 二叉树的顺序存储结构中节点的存放次序是：对该树中每个节点进行编号，其编号从小到大的顺序就是节点存放在连续存储单元的先后次序。 若把二叉树存储到一维数组中,则该编号就是下标值加1（注意C/C++语言中数组的起始下标为0）。树中各节点的编号与等高度的完全二叉树中对应位置上节点的编号相同。 定义为：typedef ElemType SqBTree[MaxS...
2018-03-10 14:20:00
21851
原创 二叉树
一、二叉树概念二叉树是有限的节点集合。这个集合可以是空， 也可以由一个根节点和两棵互不相交的称为左子树和右子树的二叉树组成。注意：二叉树的定义是一种递归定义。在一棵二叉树中，如果所有分支节点都有左孩子节点和右孩子节点，并且叶节点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。下图所示就是一棵满二叉树。可以对满二叉树的节点进行连续编号，约定编号从树根为1开始，按照层数从小到大、同一层从左到右的次...
2018-03-09 18:10:38
3084
原创 树
一、 树的定义形式定义：树：T={D,R}。D是包含n个节点的有穷集合（n≥0）。当n=0时为空树，否则关系R满足以下条件: 有且仅有一个节点d0∈D，它对于关系R来说没有前驱节点，节点d0称作树的根节点。除节点d0外，D中的每个节点对于关系R来说都有且仅有一个前驱节点。D中每个节点对于关系R来说可以有零个或多个后继节点。递归定义：树是由n（n≥0）个节点组成的有限集合（记为T）。其中...
2018-03-09 14:03:58
2937
1
原创 广义表
一、广义表的定义广义表简称表，它是线性表的推广。一个广义表是n（n≥0）个元素的一个序列，若n=0时则称为空表。设ai为广义表的第i个元素,则广义表GL的一般表示与线性表相同： GL=(a1,a2,…,ai,…,an)其中n表示广义表的长度，即广义表中所含元素的个数，n≥0。如果ai是单个数据元素，则ai是广义表GL的原子；如果ai是一个广义表，则ai是广义表GL的子表。 广...
2018-03-08 15:51:08
40591
2
原创 稀疏矩阵
一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t 十分小时，即s<<t时,称该矩阵为稀疏矩阵。例如一100×100的矩阵，若其中只有100个非零元素，就可称其为稀疏矩阵。一、 稀疏矩阵的三元组表示(顺序)稀疏矩阵的压缩存储方法是只存储非零元素。由于稀疏矩阵中非零元素的分布没有任何规律,所以在存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标。稀疏矩阵中的每一个非零...
2018-03-07 14:53:42
1961
原创 特殊矩阵的压缩存储
特殊矩阵的主要形式有：（1）对称矩阵（2）上三角矩阵／下三角矩阵（3）对角矩阵它们都是方阵，即行数和列数相同。一、对称矩阵的压缩存储 若一个n阶方阵A[n][n]中的元素满足a i,j=a j,i（0≤i，j≤n-1），则称其为n阶对称矩阵。由于对称矩阵中的元素关于主对角线对称，因此在存储时可只存储对称矩阵中上三角或下三角中的元素，使得对称的元素共享一个存储空间。这样，就可以将n2个元素压...
2018-03-07 14:35:55
14936
原创 数组
一、数组的基本概念从逻辑结构上看，数组A是n（n＞1）个相同类型数据元素a1、a2、…、an构成的有限序列。其逻辑表示为：A=（a1，a2，…，an）。其中，ai（1≤i≤n）表示数组A的第i个元素。一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。推广到d（d≥3）维数...
2018-03-07 14:26:34
794
原创 递归
一、递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。若调用自身，称之为直接递归。若过程或函数p调用过程或函数q，而q又调用p，称之为间接递归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。 例如，以下是求n!（n为正整数）的递归函数。 int fun(int n) { if (n==1) //语句1 ...
2018-03-06 17:27:17
481
原创 函数复习（整理中）
1）pow()函数：float/double pow(float x, float y)功能为计算x的y次幂。返回值：x不能为负数且y为小数，或者x为0且y小于等于0，返回幂指数的结果。2）fabs()函数：float fabs(float x)功能为求浮点数x的绝对值。计算|x|, 当x不为负时返回x，否则返回-x3）abs()函数：int abs(int i)功能为求整数x的绝对值。4）sqr...
2018-03-06 15:53:42
224
原创 进制计算问题
一、转十进制二进制转十进制：如100=1*2的2次方+0*2的1次方+0*2的0次方=4即，每位分别乘上2的次方，从总位数减一开始。八进制转十进制：如八进制有0开头，0不算在位数中，每位分别乘上8的次方十六进制转十进制：如十六进制有0X开头，0不算在位数中，且a-f转换为相印的数字，每个字母的数算一位，每位分别乘上16的次方二、十进制转二、八、十六进制十进制转二进制：除二取余，余数从下到上反过来写...
2018-03-06 15:48:30
955
原创 串的模式匹配
设有主串s和子串t，子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串，把子串t称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。 一、Brute-Force算法（即简单匹配算法）从目标串s=“s0s1…sn-1”的第一个字符开始和模式串t=“t0t1…tm-1”中的第一个字符比较，若相等，则继续逐个比...
2018-03-06 11:40:41
3356
原创 链串
链串的组织形式与一般的链表类似。主要的区别在于，链串中的一个节点可以存储多个字符。通常将链串中每个节点所存储的字符个数称为节点大小。链串节点大小的选择与顺序串的格式选择类似。节点大小越大，则存储密度越大。但存储密度越大，一些操作（如插入、删除、替换等）有所不便，且可能引起大量字符移动，因此它适合于在串基本保持静态使用方式时采用。节点大小越小（如节点大小为1时），运算处理越方便，但存储密度下降。为简...
2018-03-06 11:26:33
2782
原创 串的基本概念和顺序串
一、 串的基本概念串（或字符串），是由零个或多个字符组成的有穷序列。含零个字符的串称为空串，用Ф表示。串中所含字符的个数称为该串的长度（或串长）。通常将一个串表示成“a1a2…an”的形式。其中最外边的双引号本身不是串的内容，它们是串的标志，以便将串与标识符（如变量名等）加以区别。每个ai（1≤i≤n）代表一个字符。当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。一个...
2018-03-05 19:01:21
6106
原创 队列的应用
一、采用队列求解迷宫问题使用一个队列qu记录走过的方块，该队列的结构如下: typedef struct { int i,j; //方块的位置 int pre; //本路径中上一方块在队列中的下标} Box; //方块类型typedef struct{ Box data[MaxSize]; int front,rear; //队头指针和队尾指针}...
2018-03-04 18:15:35
437
原创 队列
一、 队列的定义 队列简称队，它也是一种运算受限的线性表，其限制仅允许在表的一端进行插入，而在表的另一端进行删除。把进行插入的一端称做队尾（rear），进行删除的一端称做队首或队头（front）。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。 由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按...
2018-03-04 18:07:52
803
原创 栈的应用
一、表达式求值表达式求值问题是：用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。为了方便，假设该表达式都是合法的数学表达式，例如，exp="1+2*(4+12)"；在设计相关算法中用到栈，这里采用顺序栈存储结构。 例如: Exp = a*b + (c - d / e) *f前缀式: + * a b * - c / d e f中缀式: ...
2018-03-04 17:53:45
380
原创 栈
一、栈的定义 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的，栈顶的当前位置由一个称为栈顶指针的位置指示器指示。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。栈的主要特点是“后进先出”，即后进栈的元素先出栈。栈也称为后进先出表。栈的几种基本运算如下: Init...
2018-03-03 16:54:46
479
原创 有序表
一、有序表的定义所谓有序表，是指这样的线性表，其中所有元素以递增或递减方式有序排列。为了简单，假设有序表元素是以递增方式排列。从中看到，有序表和线性表中元素之间的逻辑关系相同，其区别是运算实现的不同。若以顺序表、单链表存储有序表，会发现基本运算算法中只有ListInsert()算法与前面对应的运算有所差异，其余都是相同的。有序顺序表的ListInsert()算法如下：void ListInsert...
2018-03-03 10:25:05
19319
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人