8.1 基本概念 有n个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2， …，Kn }，相应的下标序列为1，2，…，n。 通过排序，要求找出当前下标序列1，2，…， n的一种排列p1，p2， …，pn，使得相应关键字满足如下的**非递减（或非递增）**关系，即：Kp1≤ Kp2≤…≤ Kpn ，这样就得到一个按关键字有序的记录序列：{Rp1，Rp2， …， Rpn}。 （1）内部排序与外部排序 内部排序：整个排序过程不需要访问外存便能完成 外部排序：参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，需要借助外存 （2）主关键字与次关键字 上面所说的关键字 Ki可以是记录i的主关键字，也可以是次关键字，甚至可以是记录中若干数据项的组合。 若Ki是主关键字，则任何一个无序的记录序列经排序后得到的有序序列是唯一的。若Ki是次关键字或是记录中若干数据项的组合，得到的排序结果将是不唯一的，因为待排序记录的序列中存在两个或两个以上关键字相等的记录。 （3）排序的稳定性 若两个记录A和B的关键 ...

7.1 图的基本概念 7.1.1 概念 图G由一个非空项点集V和一个顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=(V,E)G=(V, E)G=(V,E)。 7.1.2 有向图和无向图 在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。 在无向图中，一条边(x, y)与(y, x)表示的结果相同，用圆括号表示。 在有向图中，一条边< x,y >与< y,x >表示的结果不相同，用尖括号表示。 < x,y >表示从顶点x指向顶点y的边，x为始点，y为终点。有向边也称为弧, x为弧尾, y为弧头。则< x,y >表示为一条弧, 而< y,x >表示y为弧尾, x为弧头的另一条弧 。 7.1.3 完全图、稠密图和稀疏图 具有n个顶点，n(n-1)/2条边的图，称为完全无向图；具有n个顶点，n(n-1)条弧的有向图，称为完全有向图。 完全无向图和完全有向图都称为完全图。 当一个图接近完全图时，则称它为稠密图。相反地，当一个图中含有较少的边或弧时(e < n\logn) ...

6.1 树 6.1.1 树的定义 树(tree)是n(n≥0)个结点的有限集T。如果n=0，则称空树；如果n>0(非空树)，则： 有且仅有一个特定的结点，称为根(root) ； 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。 6.1.2 树的特点 在非空树中至少有一个结点——根，树中各子树是互不相交的集合。 6.1.3 相关术语 术语 解释 结点 表示树中的元素，包括数据项及若干指向其子树的分支 结点的度 分支个数 ( 结点拥有的子树个数 ) 树的度 树中所有结点的度的最大值 叶子结点 度为零的结点，即无后继的结点，也称为终端结点 分支结点 度大于零的结点，也称为非终端结点 从根到结点的路径 由从根到该结点所经分支和结点构成 结点的层次 一个结点在第n 层，则其子树的根结点在 n+1 树的深度（高度） 树中所有结点的层次的最大值 森林 是 m ( m≥0 ) 棵互不相交的树的集合 有序树 子树之间存在确定 ...

1.1 LTP介绍 LTP(Linux Test Project)，是基于 GPL 协议的开源社区合作项目。2000 年由 SGI 发起，IBM、OSDL 和 Bull 等公司共同参与，2001年后由 SUSE、富士通、Red Hat、Oracle 共同开发和维护。 通过功能测试、压力测试和回归测试来验证 Linux 系统的可靠性、稳定性和健壮性。整个项目约4000个测试用例，绝大部分用例采用 C 或 Shell。 LTP 不仅测试内核，还测试整体系统环境，对功能执行失败时的返回和处理也进行测试。 1.1.1 功能测试 主要对 man pages 中1、8命令和2系统调用所描述的功能进行验证。 1.1.2 回归测试 修改了旧代码后，重新进行测试已确认修改没有引入新的错误或导致其他代码产生错误。 1.1.3 压力测试 测试系统功能特性再大负荷压力下的稳定性和可靠性。 1.2 LTP 环境部署 1.2.1 下载 LTP LTP 项目目前位于 GitHub，项目地址：https://github.com/linux-test-project/ltp 。获取最新版可以执行以下命令： ...

Git是一款免费、开源的分布式版本控制系统，用于敏捷高效地处理任何或小或大的项目。本文为廖雪峰的Git教程的个人笔记，欢迎指正。 一、Git 基础 1.1 版本控制系统 版本控制系统系统分为集中式和分布式两种。 集中式是集中存放在中央服务器中，工作的时候，先用自己的电脑从中央服务器取得最新的版本，完工后，再把自己的工作推送到中央服务器。集中式版本控制工具有：CVS、SVN 等。 集中式的特点是需要联网才能工作，对网速的要求较高。如果中央服务器发生了宕机，所有人都没法工作。 分布式版本控制系统没有“中央服务器”，每个人的电脑上都是一个完整的版本库，工作的时候不需要联网。需要彼此的文件，只需要相互推送。实际使用中，分布式版本控制控制系统通常也有一台充当“中央服务器”的电脑，但仅仅是用来方便“交换”大家的修改，没有它大家一样能正常工作，只是交换修改不方便。分布式版本控制工具有：Git、Mercurial、Bazaar 等。 分布式的特点是不需要联网就能工作。不依赖中央服务器，安全性高。 1.2 安装 Git 测试是否正确安装了 Git： 如果像上图这样显示没有安装，通过相应包管理 ...

Step1: 打开设置：Preferences --> Java --> CodeStyle --> CodeTemplates Step2: 选择 Comments 标签，配置注释 Files 1234/** * @fileName: ${file_name} * @ * @date: ${date} ${time} */ Types 12345/** * @className ${file_name} * @author jitwxs * @date ${date} ${time} */ Methods 12345/** * @author jitwxs * @date ${date} ${time} * ${tags}*/ Step3: 选择 Code New Java files 123456789${filecomment} ...

一、文件名后缀 常用文件名后缀及其表示的文件类型如下表： 文件名后缀 文件类型 .c C 源文件 .i 预处理后的 C 源文件 .ii 预处理后的 C++ 源文件 .h C 或 C++ 头文件 .C .cc .cp .cpp .c++ .cxx C++ 源文件 .s 汇编程序文件 .S 必须预处理的汇编程序文件 .o 目标文件 .a 静态链接库 .so 动态链接库 二、程序的编译过程 2.1 预处理 在这一阶段，源码中的所有预处理语句得到处理。预处理之后源码中不再包含任何预处理语句。 例如： #include 语句所包含的文件内容替换掉语句本身 所有已定义的宏被展开 根据 #ifdef、#if 等语句的条件是否成立取舍相应的部分 GCC预处理阶段可以生成 .i 的文件，通过选项 -E 可以使编译器在预处理结束时就停止编译。 例如： 1gcc -E -o hello.i hello.c 2.2 编译 这一阶段，编译器对源码进行词法分析、语法分析、优化等操作，最后生成汇编代码。这是 ...

5.1 数组的定义 在 C 语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说： 1typedef elemtype array2[m][n]; 等价于： 12typedef elemtype array1[n];typedef array1 array2[m]; 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。 5.2 数组的存储方式 数组一般采用顺序存储，又分为行优先和列优先。数组的地址计算具有以下前提三要素： 开始结点的存放地址（即基地址）。 维数和每维的上、下界。 每个数组元素所占用的单元数 L。 设一般的二维数组是A[c1…d1, c2…d2]，这里c1,c2不一定是0。 行优先存储时的地址公式为：LOC(aij)=LOC(c1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L。其中，c1,c2为数组基地址，i-c1为aij之前的行数，d2-c2+1为总列数，j-c2为aij本行前面元素个数，L为单个元素长度。 列优先存储的通式为：LOC(aij) ...

4.1 串的基本概念 4.1.1 串的概念 串(String)是零个或多个字符组成的有限序列。一般记作 S=“a1a2a3…an”，其中S是串名，用双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符。串中所包含的字符个数称为该串的长度。 （1）主串和子串 串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。 （2）空白串和空串 长度为零的串称为空串(Empty String)，它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串(Blank String)。 空白串和空串的不同，如“ ”和“”分别表示长度为1的空白串和长度为0的空串。 （3）串相等 当且仅当两个串的值相等时,称这两个串是相等的,即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。 4.1.2 串的基本运算 （1）串赋值 strassign(S,T)，表示将T串的值赋给S串。 （2）联接 strcat(T1,T2)，表示将T1串和T2串联接起来， ...

3.1 栈 3.1.1 栈的定义 栈作为一种限定性线性表，是只允许在同一端进行插入和删除操作的线性表。 栈顶：通常将表中允许进行插入、删除操作的一端称为栈顶 (Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。 栈底：同时表的另一端被称为栈底 (Bottom)。 空栈：当栈中没有元素。 满栈：无法申请到栈区可用空间。 上溢：栈已满仍要入栈。 下溢：栈已空仍要出栈。 栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。具有先进后出（FILO）或后进先出（LIFO）的特点。 3.1.2 栈的顺序实现 3.1.2.1 结构定义 用一组连续的存储单元依次存放自栈底到栈顶的数据元素。设一个位置指针top（栈顶指针）动态指示栈顶元素在顺序栈中的位置，当top=-1时，表示空栈。 1234567typedef int datatype; # define MAXSIZE 100typedef struct{ datatype data[MAXSIZE]; int top; } seqstack; se ...