第3章算法与数据结构

null软件技术基础软件技术基础自动化系：黄巧莉 Email：qlhuang@swu.edu.cnnull 设计程序首先要了解需要研究解决的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ，提出适当的计算模型并列出解决问题的方法和 步骤 新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤 ,模型一旦建立起来，就要选择合适的算法，并将解题步骤 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 述出来。 本章着重讨论解决问题的核心——算法以及算法的处理对象——数据的结构 程序＝算法＋数据结构第三章 算法与数据结构第三章 算法与数据结构3.1 算法 3.2 数据结构 3.3 查找与排序3.1 算法3.1 算法 解题过程的准确、完整的描述称作解该问题的算法 程序就是用计算机语言表述的算法 流程图就是图形化了的算法 3.1.1 算法的表示3.1.1 算法的表示 算法由操作与控制结构两要素组成。 1.操作 (1) 逻辑运算： “与”、“或”、“非”； (2) 算术运算： 加、减、乘、除； (3) 数据比较： 大于、小于、等于、不等于； (4) 数据传送： 输入、输出、赋值。2.控制结构2.控制结构算法的控制结构，决定了各操作的执行次序，用流程图 可以形象地表示出算法的控制结构。 任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成。null3.1.2 算法的描述3.1.2 算法的描述 算法设计一般是由粗到细的过程，一般可以使用下面几种类型的工具描述算法： 自然语言 专用工具 算法描述语言1.自然语言1.自然语言自然语言描述算法通俗易懂，但它有着难以克服的缺陷： (1) 易产生歧义性 (2) 语句繁琐冗长，很难清楚地表达算法的逻辑流程 (3) 当今的计算机尚不能处理用自然语言表示的算法2.专用工具2.专用工具常用的有流程图、PAD图和N-S图、伪代码等； 流程图：是采用不同的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作 PAD（问题分析）图：二维树形结构图表示程序的控制流 N－S图（盒图）：结构化控制结构的盒图表示常用流程图符号：常用流程图符号：3.算法描述语言3.算法描述语言为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。3.1.3 算法的定义3.1.3 算法的定义1.算法是由一套计算规则组成的一个过程； 2.组成算法的规则是确定的、可执行的； 3.每种算法必须有确定的结果，产生一个或多个输出； 4.每个算法必须有0个（自动生成初始数）或多个输入； 5.解答必须在有限步内得到,不能出现“死循环”。null 我们可以得出如下的结论：算法是一个过程，这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答。算法设计的原则算法设计的原则设计算法时，通常应考虑达到以下目标： 1．正确性 2. 可读性 3．健壮性 4．高效率与低存储量需求1．正确性1．正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次： a．程序中不含语法错误； b．程序对于几组输入数据能够得出满足要求的结果；nullc．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； d．程序对于一切合法的输入数据都能得出满足要求的结果； 通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。 2. 可读性2. 可读性 算法主要是为了人的阅读与交流， 其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试； 3．健壮性3．健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4．高效率与低存储量需求4．高效率与低存储量需求 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。3.1.4 算法效率的度量3.1.4 算法效率的度量通常有两种衡量算法效率的方法： 事后统计法 缺点：1.必须执行程序 2.与计算机软硬件环境因素关系很大，掩盖算法本质 事前分析估算法和算法执行时间相关的因素：和算法执行时间相关的因素：1．算法选用的策略 2．问题的规模 3．编写程序的语言 4．编译程序产生的机器代码的质量 5．计算机执行指令的速度null 一个特定算法的“运行工作量”的大小，依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。null 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作： T (n) = O(f(n)) 称T (n) 为算法的(渐近)时间复杂度。null如何估算 算法的时间复杂度？null算法 = 控制结构 + 原操作 （固有数据类型的操作） 算法的执行时间 = ∑原操作(i)的执行次数×原操作(i)的执行时间 算法的执行时间与原操作执行次数之和成正比null 从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。null例：两个矩阵相乘 void mult(int a[], int b[], int& c[] ) { // 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=1; i<=n; ++i) for (j=1; j<=n; ++j) { c[i,j] = 0; for (k=1; k<=n; ++k) c[i,j] += a[i,k]*b[k,j]; } //for } //mult 基本操作：乘法操作 时间复杂度： O(n3)3.1.5 算法的存储空间需求3.1.5 算法的存储空间需求算法的空间复杂度定义为: 表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。 S(n) = O(g(n))算法的存储量包括:算法的存储量包括:1．输入数据所占空间 2．程序本身所占空间 3．辅助变量所占空间null 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 　　若所需存储量依赖于特定的输入，则通常按最坏情况考虑。荷兰国旗问题荷兰国旗问题null3.1.6 常见算法3.1.6 常见算法1.枚举法（穷举法） 基本思想： 先依据题目的部分条件确定答案的大致范围； 在此范围内对所有可能的情况逐一验证，直到全部情况验证完； 若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。2.迭代法2.迭代法使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程。 使用迭代法构造算法的基本方法： 首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差， 然后用循环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差， 并认为最后一次迭代得到的近似值为问题的解。3.递归法3.递归法如果一个过程直接或间接地调用它自身，则称该过程是递归的。 例：求阶乘。递归过程必须有一个递归终止条件， 当n=0时定义为1，是阶乘递归定义的递归出口。递归是从函数本身出发，逐次上溯调用其本身求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值。4.递推法4.递推法所谓递推法，它的数学公式也是递归的。只是在实现计算时与递归相反。从给定边界出发逐步迭代到达指定计算参数。 例：求阶乘 f(n)＝n! ＝n×(n-1)! ＝n×f(n-1) 要计算10!，可以从递推初始条件f(0)=1出发，应用递推公式f(n)=n×f(n-1)逐步求出f(1)、f(2)…、f(9)、最后求出f(10)的值。 递推操作是提高递归函数执行效率最有效的方法，科技计算中最常见。5.分治法5.分治法解一个复杂的问题时，尽可能地把这个问题分解为较小部分，找出各个的解，然后再把各部分的解组合成整个问题的解，这就是所谓的分治法。6.回溯法6.回溯法在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，有许多可以用回溯法来求解。3.2 数据结构3.2 数据结构3.2.1 数据的结构关系 3.2.2 数据结构的研究 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 3.2.3 线性表 3.2.4 树和二叉树 3.2.5 图null3.2.1 数据的结构关系3.2.1 数据的结构关系数据及其关系构成数据结构。 DS＝（D，R），数据集合D，可以是单个数据集合，也可以是不同类型子集组成的大集合，甚至可以是数据结构。 关系集合R指数据间的结构关系。例如，用三个 4 位的十进制数表示一个含12位数的十进制数例如，用三个 4 位的十进制数表示一个含12位数的十进制数例如: 3214,6587,9345 ─ a1(3214),a2(6587),a3(9345) 则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1, a2、a2, a3 3214，6587，9345 ≠ 6587，3214，9345 a1 a2 a3 a2 a1 a3又例，在 2 行 3 列的二维数组中六个元素 {a1, a2, a3, a4, a5, a6} 之间存在两个关系：又例，在 2 行 3 列的二维数组中六个元素 {a1, a2, a3, a4, a5, a6} 之间存在两个关系：行的次序关系: row = {< a1, a2 >,< a2, a3>,< a4, a5 >,< a5, a6 >} 列的次序关系: col = {< a1, a4 >,< a2, a5 >,< a3, a6 >}null一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图。 程序中的数据运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。 每种逻辑结构都有一个运算集合。常用的运算有检索、插入、删除、更新、排序等。3.2.2 数据结构的研究内容3.2.2 数据结构的研究内容1．研究方法 首先研究它的逻辑结构有什么运算性质 用什么表示法表示这种逻辑结构 再按表示法和性质写出求解问题的算法2.数据的逻辑结构和物理结构2.数据的逻辑结构和物理结构　　数据结构应该包括数据的“逻辑结构”和数据的“物理结构”两个方面（层次）。 数据“逻辑结构”是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。 　数据物理结构是数据逻辑结构在计算机中的表示和实现，故又称数据“存储结构”。数据的存储结构数据的存储结构　　　—— 逻辑结构在存储器中的映象 　　　　“数据元素”的映象 ？ 　　　　“关系”的映象 ？数据元素的映象方法：数据元素的映象方法：用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2关系的映象方法： （表示x, y的方法）关系的映象方法： （表示x, y的方法）　　数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象与非顺序映象。对应两种不同的存储结构：顺序存储结构和链式存储结构。null顺序映象： 以相对的存储位置表示后继关系。 例如：令y的存储位置和x的存储位置之间差一个常量C，而C是一个隐含值，整个存储结构中只含数据元素本身的信息。null非顺序映象： 以附加信息(指针)表示后继关系，需要用一个和x在一起的附加信息指示y的存储位置。 例如：y的存储位置和x的存储位置没有特别的关系，表示y和x的关系，则通过附加信息－指针表示。null　　在不同的编程环境中，存储结构可有不同的描述方法。 　　当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述。null例如： 　　以三个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整数数组类型，定义长整数为: 　　typedef int Long_int [3]3.2.3 线性结构（线性表、栈和队列、串）3.2.3 线性结构（线性表、栈和队列、串）线性结构是n个数据元素的有限序列： (a1, a2 ,a3,…an) n为线性结构的长度(n≥0)，n=0称为空null数据元素呈线性关系，必存在唯一的称为“第一个”的数据元素；必存在唯一的称为“最后一个”的数据元素； 除第一个元素外，每个元素都有且只有一个前驱元素； 除最后一个元素外，每个元素都有且只有一个后继元素； 所有数据元素 ai 在同一个线性表中必须是相同的数据类型。1.线性表1.线性表线性表是一种最简单的线性结构。 一个线性表是ｎ个数据元素的有限序列。 例：字母表（A, B, C, ……, Z） 数字列（1，2，5，50，91） 　　学生健康情况登记表 null线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表。null线性表的基本运算主要有： (1)创建一个新表，包括无表元素的空表； (2)在两个确定的元素之间插入一个新的元素； (3)删除线性表中某个元素； (4)按某种要求查找线性表中的一个元素，需要时，还可找到元素进行值的更新； (5)计算表长。（1）顺序表和一维数组（1）顺序表和一维数组将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表。一维数组就是用顺序方式存储的线性表，其下标可看成元素的相对地址。顺序表——线性表的顺序存储表示顺序表——线性表的顺序存储表示用一组地址连续的存储单元 依次存储线性表的数据元素。 null以“存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量↑ 所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)×C ↑基地址null顺序映像的 C 语言描述 #define LIST_INIT_SIZE #define LISTINCREMENT typedef struct { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位) } SqList; // 俗称顺序表　　L.elem[i-1]的值为线性表中第i个数据元素，该顺序表最多可容纳L.listsize个数据元素。　　L.elem[i-1]的值为线性表中第i个数据元素，该顺序表最多可容纳L.listsize个数据元素。基本操作基本操作插入，在线性表(a1, a2…，ai，ai+1…，an)的第i个位置插入元素x。 删除：在表长为n的线性表(a1,a2,…ai-1,ai,ai+1…an)中删除第i个数据元素，通常还需将第i+1个至第n个元素向前推动一个位置， 即(a1, a2 ,…，ai-1,ai+1，…，an)。向顺序表中插入元素向顺序表中插入元素SeqList ListInsert(SeqList L,int i,ElemType x) {int j; if(L.length==MAXSIZE) printf("表满,不能插入\n"); else if(i<1||i>L.length+1) printf("插入位置不正确\n"); else { for(j=L.length-1;j>=i-1;j--) L.data[j+1]=L.data[j]; L.data[i-1]=x; L.length++; } return L; }从顺序表中删除元素从顺序表中删除元素SeqList ListDelete(SeqList L,int i) {int j;ElemType x; if (i<1||i>L.length) printf("删除位置不正确\n"); else {x=L.data[i-1]; for(j=i;j<=L.length-1;j++) L.data[j-1]=L.data[j]; L.length--; printf("%d已被删除\n",x); } return L; }顺序表的优点：顺序表的优点：无需为表示结点间的逻辑关系而增加额外的存储空间； 可以方便地随机存取表中的任一结点； 可以快速地求得表长。顺序表的缺点：顺序表的缺点：插入和删除运算不方便，除表尾的位置外，在表的其它位置上进行插入和删除操作都必须移动大量的结点，其效率较低； 顺序表要求占用连续的空间，存储分配有可能造成一定的浪费或空间的不足。(2)链表(2)链表 用一组地址任意的存储单元存放线性表中的数据元素。 元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素或数据元素的映象) 以“结点的序列”表示线性表  称作链表1）单链表1）单链表 由于此链表的每个结点中只包含一个指针域，故称为线性链表或单链表。null　　 以线性表中第一个数据元素存储地址作为线性表的地址，称作线性表的头指针。head为一“指针”变量，它的值为第一个结点的存储位置。若头指针为“空”（head＝NULL），则所表示的线性表为“空”表。终端结点无后继，故终端结点的指针域为空指针。 头指针变量具有标识单链表的作用，故常用头指针变量来命名单链表。如表head、head表。nullnull 线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，即指针为数据元素之间的逻辑关系的映象。由此，这种存储结构为非顺序映象或链式映象。 由于单链表可由头指针唯一确定，因此，可用C语言中“结构指针”来描述。结点和单链表的C语言描述结点和单链表的C语言描述Typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList; LinkList L； // L 为单链表的头指针“指针”的几个基本操作含义“指针”的几个基本操作含义LNode *p, *q; LinkList H; p、q和H均为以上定义的指针型变量 若p的值非空，则表明p指向某个结点 p->data表示p所指结点中的数据域 p->next表示p所指结点中的指针域null 假设p是指向线性表中第i个数据元素（结点ai）的指针，则p->next是指向第i+1个数据元素 （结点ai＋1）的指针。 p->data= ai p->next->data= ai＋1null 指针型变量只能作同类型的指针赋值与比较操作。并且，指针型变量的“值”除了由同类型的指针变量赋值得到外，都必须用C语言中的动态分配函数得到。 p=new LNode; p=(LinkList)malloc(sizeof(LNode)) delete p; free(p);“指针”的基本操作“指针”的基本操作指针指向结点 p = q 指针指向后继 p = q->next 指针移动 p = p->next 链指针改接 p->next = q 链指针改接后继 p->next = q->next单链表操作的实现单链表操作的实现GetElem(L, i, e) // 取第i个数据元素 ListInsert(&L, i, e) // 插入数据元素 ListDelete(&L, i, e) // 删除数据元素 ClearList(&L) // 重置线性表为空表 CreateList(&L, n) // 生成含 n 个数据元素的链表线性表的操作 GetElem(L, i, &e)线性表的操作 GetElem(L, i, &e)在单链表中的实现：j123null单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。 因此，查找第i个数据元素的基本操作为：移动指针，比较j和i。 令指针p始终指向线性表中第j个数据元素。nullStatus GetElem_L ( LinkList L, int i, ElemType &e ) 　{ 　　// 若1≤i≤LengthList(L)，则用 e 带回指针L指向头结点的单链表中 // 第 i 个元素的值且返回函数值为TRUE,否则返回函数值为FALSE。 p = L->next; j =1; // 变量初始化，p指向第一个结点，j为计数器 　　 while ( p && j< i ){ 　　　 // 顺结点的指针向后查找，直至 p 指到第i个结点或 p 为空止 　　　 p = p->next; ++j; 　　 } // while 　 if ( !p || j>i) return FALSE; // 链表中不存在第 i 个结点 　　 e = p->data; 　　　　　　// 取到第 i 个元素 　　 return TRUE; } // GetElem 算法的时间复杂度为：O (ListLength(L))。线性表的操作 ListInsert(&L, i, e)线性表的操作 ListInsert(&L, i, e)在单链表中的实现: 有序对 改变为 和 null 可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。 因此，在单链表中第i个结点之前进行插入的操作步骤为： 生成一个数据域为e的结点，然后插入； 结点e中的指针域指向结点ai； 修改结点ai-1中的指针域，令其指向结点e。null 因此，在单链表中第 i 个结点之前进行插入的基本操作为：找到线性表中第i-1个结点，然后修改其指向后继的指针。 假设指针p为指向结点ai-1的指针，指针s为指向结点e的指针，则上述指针修改用语句描述即为： s->next= p->next; p->next=s;spnullStatus ListInsert_L ( LinkList &L, int i, ElemType e ) 　{ 　　// 若1≤i≤LengthList(L)+1，则在指针L指向头结点的单链表 　　// 的第 i 个元素之前插入新的元素 e，且返回函数值为 TRUE, 　　// 否则不进行插入且返回函数值为 FALSE p=L; j=0; 　　 while(p && jnext; ++j; 　　 } // while 　　 if(!p||j>i-1) return FALSE; // 参数不合法，i小于1或者大于表长+1 　　 s=new LNode; 　　 if (!s) exit(1); 　　　　 　 // 存储空间分配失败 　　 s->data=e; 　　　　　　　　 // 创建新元素的结点 　　 s->next=p-> next; p->next=s; // 修改指针 　　 return TRUE; 　} // ListInsert_L 　　 算法时间复杂度为：O (ListLength(L))。线性表的操作 ListDelete (&L, i, &e)线性表的操作 ListDelete (&L, i, &e)在单链表中的实现: 有序对 和 改变为 null 在单链表中删除第 i 个结点的基本操作为：找到线性表中第i-1个结点，修改其指向后继的指针。假设指针p为指向结点ai-1的指针，则上述指针修改用语句描述即为： p->next = p->next->next; pnullStatus ListDelete_L (LinkList &L, int i, ElemType &e) 　{ // 若1≤i≤LengthList(L)，则删除指针L指向头结点的单链表 　　// 中第 i 个元素并以 e 带回其值，返回函数值为 TRUE， 　　// 否则不进行删除操作且返回函数值为 FALSE p = L; j = 0; 　　 while (p->next&&j < i-1){ //寻找第i个结点，并令p指向其前驱 　　　 p = p->next; ++j; 　　 } 　　 if (!(p->next) || j > i-1) 　　　 return FALSE; 　　　　　　　// 删除位置不合理 　　 q = p->next; p->next = q->next;　// 修改指针 　　 e = q->data; delete(q);　　　　// 释放结点空间 　　 return TRUE; } // ListDelete_L 　　 算法时间复杂度为：O (ListLength(L))。操作 ClearList(&L) 在链表中的实现操作 ClearList(&L) 在链表中的实现void ClearList(&L) { // 将单链表重新置为一个空表 while (L->next) { p=L->next; L->next=p->next; delete(p); } } // ClearList 算法时间复杂度：O(ListLength(L))如何从线性表得到单链表？如何从线性表得到单链表？ 链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。例如：逆位序输入 n 个数据元素的值， 建立带头结点的单链表。例如：逆位序输入 n 个数据元素的值， 建立带头结点的单链表。操作步骤：一、建立一个“空表”；二、输入数据元素an， 建立结点并插入；三、输入数据元素an-1， 建立结点并插入；ananan-1四、依次类推，直至输入a1为止。nullvoid CreateList_L(SLink &L, int n, ElemType A[]) 　{ 　　// 已知数组 A 中存有线性表的 n 个数据元素， 　　// 逆序建立带头结点的单链表。 　　L = new LNode; 　　if (!L) exit(1); 　　　　// 存储空间分配失败 　　L->next = NULL;　　// 先建立一个带头结点的空的单链表 　　for (i = n; i > 0; --i) 　　{ p = new LNode; 　　　if (!p) exit(1); 　　　　// 存储空间分配失败 　　　　p->data = A[i-1]; 　　　　　 　// 赋元素值 　　　　p->next = L->next; L->next = p; // 插入在头结点之后 　　} // for 　} // CreateList_L 算法的时间复杂度为:O (ListLength(L))。2）循环链表2）循环链表 循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为“NULL”，而是指向头一个结点，成为一个由链指针链结的环。3）双向链表3）双向链表 设有一个指向后继结点的指针和一个指向前驱结点的指针。双向链表的操作特点：双向链表的操作特点：“查询”和单链表相同 “插入”和“删除”时需要同时修改两个方向上的指针nulls->next = p->next; p->next = s; p->next->prior = s; s->prior = p;ps插入null删除p->prior ->next = p->next; p->next->prior = p ->prior;p2.栈2.栈栈(STACK)也是一种特殊的线性表，是一种“后进先出”的结构，它的运算规则受到一些约束和限定，故又称限定性数据结构。a1a2an… …null栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)。 栈的物理存储可以用顺序存储结构，也可以用链式存储结构。3.队列3.队列队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表 表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front) 队列的操作是按先进先出的原则进行的 队列的物理存储可以用顺序存储结构，也可以用链式存储结构。4 串4 串串(String)可以看作一维字符数组，但其长度不恒定，可以作删除、插入操作。 许多高级语言把串作为一种单独的类型，其元素不可作四则运算。 进行连接、删除、插入操作，用子串有时很方便。 子串(Substring)是串的一部分，具有串的一切特征。null3.3 查找与排序3.3 查找与排序查找与排序是计算机最频繁、最基本的操作，特别是大量数据的数据处理领域。数据的排序等于为计算机查找添加了“智能”，一点信息都没有的计算机只能蛮干（枚举所有可能）。3.3.1 查找3.3.1 查找1．基本概念 查找是在给定数据集中找到满足要求的数据。对于简单数据集合，查找的基本操作是遍历（枚举）和比较。对于结构式数据集合，关键是确定该 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 查找键（Key）。 关键字是数据元素中可以唯一标识一个数据元素的数据项，比如学号、身份证号等。null查找是根据给定的关键值，在一组数据中确定一个其关键字等于给定值的数据元素的过程。 确切定义：给定一个值K，在含有n个记录的文件中进行搜索，寻找一个其关键字等于给定的K值的记录，如找到，则输出记录或记录在文件中的相对位置称查找成功；否则输出查找不成功的信息称查找失败。null查找操作的时间性能分析 要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，因此通常以查找过程中关键字和给定值比较的平均次数作为比较查找算法的度量依据。null定义： 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值。其中: n 为表长， Pi 为查找表中第i个记录的概率，且 Ci为找到该记录时，曾和给定值比较过的关键字的个数。2．查找算法 2．查找算法 1）顺序查找 顺序查找的方法是：用待查关键字值与线性表中各结点的关键字值逐个比较，直到找出相等的关键字值；或找遍所有结点都找不到，即查找失败。nullST.elem顺序表的查找过程：假设给定值 e = 64, e=66 要求 ST.elem[i] = e, 问： i = ?66null假设查找表的顺序存储结构为typedef struct { ElemType *elem; // 数据元素存储空间基址，建表时 // 按实际长度分配，0号单元留空 int length; // 表的长度 } SSTable;nullint location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType)) { i = 1; p = L.elem; while (i<=L.length && !(*compare)(*p++,e)) i++; if ( i<= L.length) return i; else return 0; } //locationi<=L.lengthnull 顺序查找的优点是对线性表结点的逻辑次序无要求，对线性表的存储结构无要求，顺序查找的缺点是查找效率低，平均检索长度长，为n/2。当n较大时，不宜采用顺序查找，而必须寻求更好的查找方法。null2）二分法查找 要求线性表结点按关键字码值排好，且以顺序方式存储。 用要查找的码值X与中间位置结点的关键码值W相比较： (1)X=W，此时已经查找成功，查找结束。 (2)X>W,表明X在表的后半部分，取后半部分进行查找。 (3)Xk，则在R[1]到R[mid-1]中继续查找，若有R[mid].key=low; --j ) L.r[j+1] = L.r[j]; // 记录后移 　　　L.r[high+1] = L.r[0];　　　　// 插入 　　} 　} // BInsertSort二分插入排序的算法实现null 二分插入算法与直接插入算法相比，需要辅助空间与直接插入排序基本一致；时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，两种方法的元素的移动次数相同，关键字比较次数降为nlog2n量级，记录移动个数仍为n2量级。 因此二分插入排序的时间复杂度仍为O（n2）。二分法插入排序的效率分析3．选择排序 3．选择排序 基本思想是：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已排序的记录序列的最后，直到全部排完为止。null第一次从R[0]~R[n-1]中选取最小值，与R[0]交换， 第二次从R[1]~R[n-1]中选取最小值，与R[1]交换， 第三次从R[2]~R[n-1]中选取最小值，与R[2]交换， … 第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换， … 第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换， 总共通过n-1次，得到一个按排序码从小到大排列的有序序列。null例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图所示。nullvoid SelectSort (SqList &L) 　{// 对顺序表L作简单选择排序 　　for (i=1; i1 && change; --i){ 　　　change = FALSE; 　　　for (j=1; j L.r[j+1].key) 　　　　　{ L.r[j]←→L.r[j+1]; change = TRUE } 　　}// for i 　} // BubbleSortnull 从起泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n )/2，因此起泡排序算法的时间复杂度为O(n2)。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。起泡排序的效率分析null 快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行