ncre公共基础知识

《ncre公共基础知识》由会员分享，可在线阅读，更多相关《ncre公共基础知识（130页珍藏版）》请在金锄头文库上搜索。

1、公共基础知识,主要内容 算法与数据结构 程序设计基础 软件工程基础 数据库设计基础,算法与数据结构 算法的概念、基本特征、基本要素 算法复杂度（时间、空间） 数据结构的概念（逻辑结构、存储结构） 数据结构的图形表示 线性结构和非线性结构 线性结构（数组、栈、队列、线性链表） 非线性结构（二叉树） 查找技术（顺序查找、二分查找） 排序技术（交换类排序 插入类排序 选择类排序）,（一）算法 算法：对特定问题求解步骤的一种描述，是指 令的有限序列。即解题的方法及步骤。 其中每一条指令表示一个或多个操作。 1.算法的基本特征： 可行性（步骤可执行） 确定性（含义明确） 有穷性（步骤、时间有限） 输入

2、（0个或多个初始数据） 输出 （1个或多个执行结果）,2. 算法复杂度 空间复杂度：执行算法所占用的临时存储空间。 时间复杂度：设算法解决的问题的规模为n， 运行时间关于问题规模n的一个相对的数量级 就称为该算法的时间复杂度，记为： 0，0(n)，0(n2)等。,FOR i=1 TO N s=s*i & 语句频度：n ENDFOR 本程序段的时间复杂度是: O(n),（二）数据结构的基本概念 数据：描述客观事物并能被加工处理的符号集合。 数据元素：数据的基本单位。 （结点、记录） 数据项：数据最小单位。 （域、字段） 结构：数据元素间的相互关系。 数据结构：数据元素的组织形式和相互关系。,1.

3、数据的逻辑结构： 抽象的反映数据元素间的逻辑关系。 1)线性结构： 逻辑特征： 有且仅有一个头结点元素和一个尾结点元素，并且除端点外的所有数据元素都最多只有一个直接前趋和一个直接后继。 线性表、堆栈、列队、数组、链表等。(一对一),2)非线性结构： 逻辑特征： 该结构中一个数据元素可能有多个直接前趋和直接后继。 树、图、集合等。（一对多、多对多） 2.数据的存储结构： 数据的物理结构，反映数据元素在计算机 中的存储方法,是逻辑结构在存储器里的表示。 通过四种基本存储方法体现： 顺序存储、链式存储、索引存储、散列存储。,1)顺序存储方法： 把逻辑上相邻的数据元素存储在物理位置 上相邻的存储单元里

4、，元素间的逻辑关系由存 储单元的邻接关系体现。由此得到的存储结构 称为顺序存储结构。 顺序存储方法主要应用于线性的数据结构, 如线性表、数组等。 非线性的数据结构可以通过某种线性化的 方法来实现顺序存储。,2)链接存储方法： 不要求逻辑上相邻的元素其物理位置上亦相邻，元素间的逻辑关系是由附加的指针表示的，由此得到的存储称为链式存储结构。 链式存储结构要借助于程序语言的指针类型来描述元素的存储地址。 在此存储方法中，每个数据元素所占存储单元分成两部分：一部分为元素本身数据项；而另一部分为指针项，指出其后继或前趋元素的存储地址，从而形成一个链。,3)索引存储方法： 在存储元素信息的同时，建立附加的

5、索引表，索引表中的每一项称为索引项。 索引项的一般形式是：（关键字、地址）。 关键字是能唯一标识一个结点的数据项。 地址是指示数据元素所在存储位置的记录号。,索引项,4)散列存储方法： 根据元素的关键字直接计算出该元素的存储地址。即在数据元素的字段中有一个或几个字段的值，通过某一散列函数唯一地确定该元素的存储地址。 有时又称散列存储方法为: 关键字-地址转移法,2007.9 下列叙述中正确的是（ ） A）数据的逻辑结构与存储结构必定是一一 对应的。 B）由于计算机存储空间是向量式的存储结构， 因此，数据的存储结构一定是线性结构。 C）程序设计语言中的数组一般是顺序存储 结构，因此，利用数组只能

6、处理线性结构。 D）以上三种说法都不对。,（三）线性表及其顺序存储结构 1. 基本概念 线性表由一组数据元素构成，数据元素的位置 只取决于自己的序号，元素之间的相对位置是 线性的。（有限且有序） 在复杂线性表中，由若干项数据元素组成的数 据元素称为记录，而由多个记录构成的线性表 又称为文件。,2. 线性表的结构特征： （1）有且只有一个根结点a1，它无前件。 （2）有且只有一个终端结点an，它无后件。 （3）除根结点与终端结点外，其他所有结点 有且只有一个前件，也有且只有一个后件。 （4）结点个数n称为线性表的长度，当n=0 时，称为空表。,线性表的常见存储方式： 顺序存储结构 链式存储结构

7、常见线性表： 顺序存储结构的顺序表 链式存储结构的线性链表,(1) 顺序表：顺序存储结构 数据元素按逻辑次序，集中存放在地址连续的存储单元里。 通常顺序表用一个一维数组和一个指示当前表长的整数来表示。 顺序表的操作：建表、插入、删除、求表长 顺序表的特点： a.所有元素所占用的存储空间是连续的。 b.各数据元素按逻辑顺序依次存放。 c.可以根据逻辑顺序任意访问。,数据元素的内存地址的计算： 设顺序表中的每个元素占用K个存储单元,索引号为1(即逻辑顺序为1)的数据元素a1的内存地址为ADR(a1),则索引号为i的数据元素ai的内存地址为： ADR(ai)=ADR(a1)+(i-l)K,虽然顺序表

8、的空间利用率高，但若对顺序表进行插入、删除等操作，其运算效率低，需要大量的数据元素移位。 a.插入运算： 假设顺序表中已有n个数据元素，在第i个位置上（1in+1）插入一个新的数据元素x,构成一个n+1长的顺序表的实现方法是： 将原来表中第i个第n个元素后移一个位置，将要插入的元素x插入在第i个位置上，共需移动n-i+1个结点，然后将表长加1。 顺序表上插入运算的平均时间复杂度是O(n)。,b.删除运算 将表的第i个（1in）结点删去，当1in-1时，则必须将表中第i+1个第n个共n-i个结点向前移动一个位置，共需要移动n-i个元素。 顺序表上删除运算的平均时间复杂度也是O(n)。,（四）栈和

9、队列 1.栈及其基本运算 定义：栈是仅允许在表的一端进行插入和删除运算的线性表。 通常称插入、删除的这一端为栈顶，另一端称为栈底，栈底是封闭的，一切操作在栈顶进行。 当表中没有元素时称为空栈。 栈操作的原则： 由于栈中元素的插入和删除只能在栈顶进行，所以总是先进栈的元素后出栈，后进栈的元素先出栈，即先进后出（FILOFirst In Last Out）或后进先出（LIFOLast In First Out）,入栈运算：从当前栈顶部插入一个新元素。 具体操作：将栈顶指针加1，再将元素插入 到指针所指的位置。 出栈运算：从当前栈顶部取出栈顶元素。 具体操作：将当前栈顶元素取出，再将栈顶 指针减1。

10、 说明： 1)栈顶用TOP表示，栈底用BOTTOM表示。 2)TOP=0,表示空栈；TOP=Maxsize,表示栈满。 3)栈顶会随着入栈和出栈操作不断变化。,e,b,c,a,d,TOP,BOTTOM,进栈序列：a, b, c, d, e, f 出栈序列：f, e, d, c, b, a,2.队列及其基本运算 2.1 普通队列（顺序队列） 定义：队列是只允许在线性表的一端进行数据元素插入操作，而在另一端才能进行数据元素删除操作的线性表。 一般将允许插入的一端称为队尾，允许删除的另一端称为队头。 根据其特点，队列需要两个队列指针来说明: 队头指针Front,它总是指向队头元素的前一个位置；队尾指

11、针Rear,它总是指向队尾元素所在的存储位置。,由于队列元素的插入和删除分别在队尾和队 头进行，所以总是先入队列的元素先出队列， 即队列具有先进先出的特性，故队列遵循的原 则是：先进先出（FIFO） 注意： 队列中存储空间编号：0至 Maxsize-1,a0,a1,a2,ai-1,ai-2,顺序队列为空：Front=Rear 顺序队列满： Front= -1，Rear=Maxsize-1 假溢出： 队列的存储区中还有空间，但是却无法继续 做入队操作的现象。 解决方法： 1）所有元素整体平移 2）循环队列,a0,a1,a2,ai-1,ai-2,2.2 循环队列 定义：在逻辑上将顺序队列想象成为一

12、个首尾 相连的圆环。 Front指针：指向队头元素的前一个位置 Rear指针：指向队尾元素的位置 存储空间的编号：从0到Maxsize -1 基本操作：入队，出队,n-1,0,.,2,1,0,3,a,b,c,e,1,2,3,.,n-1,a,b,e,同样的问题： 当front=rear时，仍然无法判断当前队列为空 或是已满。 解决方案： 1）加设标记位s（s=0为空，s=1为满）。 2）用变量x 统计当前队列中的元素个数。 3）牺牲一个存储空间，令队满的条件为: front=(rear+1) mod n （n=队列长度）,循环队列常用判别和计算公式： 设循环队列的存储空间为m 队列为空：fron

13、t=rear 队列满：front=(rear +1) mod m 出队：front=(front +1) mod m 入队：rear=(rear -1) mod m 元素个数= (m-front+rear) mod m 或 元素个数=rear-front (rearfront) 元素个数=m-front+rear (rearfront),(五) 线性链表（数据项，指针） 线性链表是采用链式存储结构方式进行存储的线性表。 用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可连续，也可以不连续，可以大大提高存储器的使用效率。 在链表中元素的逻辑次序与物理存储次序不一定相同，为了能正确表示数

14、据元素间的逻辑关系，在存储每个元素值的同时，还必须存储其直接后继（或直接前趋）的存储位置，这一部分称为链。,线性链表有单向链表，双向链表和循环链表等。 对链表的访问要从链表的头部开始,顺链操作。 a.单向链表： 单向链表的每个数据元素都是由二部分组成： 数据域（data）：存储元素值 指针域（next）：存储直接后继元素存储地址 其结构如下：,一个线性表a1,a2,，an，对应的单向链表可用逻辑示意图1表示。其中,L为链表的头指针,用以确定线性表中第一个元素对应的存储位置。 单向链表可以用头指针的名字来命名。 链表的终点元素无直接后继,故其指针域为空NULL，在图中用表示。,图1,插入删除一个

15、数据元素，仅仅需要修改该结点的前一个和后一个结点的指针域。,插入运算：,优点：插入、删除操作时移动的元素少。 缺点：所有的操作都必须顺链操作，无法 随机访问。,b.在双链表中，知道任一结点的指针，就可以访问整个链表的所有结点。,c.循环链表首尾相接,最后一个结点的指针域指向头结点；若改成双链可构成双向循环链表。,顺序表与链表的比较： a.顺序存储的访问是按逻辑顺序随机访问，而链式存储的访问是顺链按结点进行的单向顺序访问。 b.顺序存储下插入、删除平均移动一半元素，效率不高，而链式存储下插入、删除效率高。 c.顺序存储空间利用率高，链式存储需额外增加地址指针的存储，增加空间耗费。,（六）非线性结

16、构 逻辑特征：一个结点元素可能有多个直接前趋和多个直接后继。 主要的非线性结构：树结构、二叉树和图结构。 一、树结构 树结构是结点之间有分支、层次关系结构,类似于自然界中的树，也有根、树叶及联系它们的支干，不过是一种倒生树。 树是一个或多个结点元素（简称结点）组成的有限集合T，且满足如下条件： (1)根结点(root):有且仅有一个结点没有前趋,(2)其余所有结点有且只有一个直接前趋结点。 (3)包括根结点在内，每个结点可以有多个直接后继结点。,概念： (1)叶子：没有后继的结点 (或终端结点) (2)分支结点：非叶子结点，或非终端结点。 (3)结点的度：一个结点的子结点数目。 (4)树的度：树中各结点的度的最大值。 (5)子结点：某结点的子树的根称为该结点的子结点。 (6)父结点：相对于某结点的子树的根，称该结点为子树的根的父结点。 (7)兄弟：具有同一父结点的子结点互称兄弟。,(8)结点的层次：根结点的层次为1，其他任何结点的层数等于它的父结点的层数加1。 (9)树的深度：一棵树中，结点的最大层