搜索
算法算法是解题方案的准确而完整的描述。具有可行性，确定性，有穷性，有足够的情报输入与输出。算法要素：数据的运算和操作+控制结构；运算与操作：算术，逻辑，关系，数据传输（赋值，输入，输出等）；控制结构：顺序，选择，循环；算法的常见描述方法:自然语言方式伪代码方式程序流程图方式N/S盒图方式算法描述-伪代码介于自然语言和程序语言之间的一种描述方法，与具体编程语言无关。KeeptrackofcurrentnumberofresourcesinuseIfanotherresourceisavailableAllocateadialogboxstructureIfadialogboxstructurecouldbeallocatedNotethatonemoreresourceisinuseInitializetheresourceStoretheresourcenumberatthelocationprovidedbythecallerEndifEndifReturnTRUEifanewresourcewascreated;elsereturnFALSE算法描述-程序流程图算法由若干张流程图描述，每张流程图由结点和有向边构成，该图描述了算法中所进行的操作以及这些操作执行的逻辑顺序。流程图的常用结点及控制结构描述如下：算法描述-N/S盒图方式算法设计基本方法列举法归纳法递推法递归法回溯法算法的复杂度空间复杂度：占用的存储空间大小时间复杂度：编译时间+运行时间(1)a=b;//O(1)---时间复杂度为常数值(2)for(inti=0;in;i++)a=b;//O(n)---时间复杂度为一阶值(3)for(inti=0;in;i++)for(intj=0;jn;j++)a=b;////O(n2)---时间复杂度为二阶值数据结构的基本概念数据结构(DataStructure)：是相互之间具有一种或多种关联的数据元素的集合。数据结构的研究内容1）数据的逻辑结构2）数据的存储结构3）数据的运算1）数据的逻辑结构数据的逻辑结构是用来描述数据元素在逻辑上的关联关系。例如：有一个包含了4个元素的数据集合：{小学，初中，高中，大学}。它是数据的组织形式，与数据在计算机内的存储方式无关。常用的数据的逻辑结构有：集合、线性结构、树状结构、图状结构等。数据的逻辑结构逻辑结构的4种形式(1)集合：数据元素间为松散的关系。在集合结构中各元素之间，除了“同属于某一个数据对象”的关系外，再无其他的关系，如图(a)所示。(2)线性结构：数据元素间为严格的一对一关系，除第一个元素外，其他元素只有一个前驱，除最后一个元素外，其他元素只有一个后继，如图(b)所示。(3)树状结构：数据元素之间为严格的一对多的关系，即一个元素只有一个前驱，但可以有多个后继，如图(c)所示。(4)图状结构：数据元素之间存在多对多的关系，也就是说元素间的逻辑关系可以是任意的。图状结构如图(d)所示。数据元素之间的前后位置关系称为前后件关系，也称为直接前驱和直接后继关系。2）数据的存储结构数据的逻辑结构在计算机存储器中的存储方式就是数据的存储结构（也称数据的物理结构）。基本的存储结构有：顺序存储结构、链式存储结构、索引存储结构、散列存储结构。3）数据结构的运算数据结构的运算一般包括：插入、删除、查找、分类、合并、分解、复制、修改等。2.数据结构的表示1）二元关系表示法2）图形表示法1）二元关系表示法形式：B=（D,R）其中，B表示数据结构，D表示数据元素的集合，R表示各数据元素之间前后件关系的集合。例1：求学历程B=（D,R）D={小学，初中，高中，大学}R={（小学，初中），（初中，高中），（高中，大学）}例2：我国的行政区划分B=（D,R）D={中国，省，自治区，直辖市，北京，天津，上海，重庆}R={（中国，省），（中国，自治区），（中国，直辖市），（直辖市，北京），（直辖市，天津），（直辖市，上海），（直辖市，重庆）}2）图形表示法每一个数据元素均表示为一个矩形框，称为结点；每一个前后件关系表示为一个带箭头的有向线段，从前件结点指向后件结点。例1：求学历程例2：我国的行政区划分3.线性结构和非线性结构如果一个数据结构中没有任何数据元素，则称该数据结构为空数据结构。对于一个非空的数据结构来说，如果满足以下三个条件：①有且只有一个根结点；②每个结点最多有一个前件结点，也最多有一个后件结点；③插入或删除任何一个结点后仍然同时满足前两个条件。则称这样的结构为线性结构，否则为非线性结构。实例解析【例1-9】设有数据逻辑结构：tree=(D,R)，其中：D={A,B,C,D,E,F,G,H,I,J}R={A,B,A,C,A,D,B,E,B,F,C,G,C,H,C,I,D,J}试分析该数据结构属于哪种逻辑结构?数据的树状结构示意图如图所示。数据的树状结构示意图像倒着画的一棵树，在这棵树中，最上面的一个结点没有前驱只有后继，称为树根结点，最下面一层的结点只有前驱没有后继，称为树叶结点。在一棵树中，每个结点有且只有一个前驱结点(除树根结点外)，但可以有任意多个后继结点(树叶结点可看做具有0个后继结点)。这种数据结构的特点是数据元素之间为1对N关系(N≥0)，即层次关系，因此本题所给定的数据结构为树状结构。【例1-10】设一个数据结构的逻辑结构如图所示，写出其二元组的描述。本题所给定的数据结构为图状结构，其二元组的描述为：Graph=（D，R）其中，D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}注意：在【例1-9】中尖括号A,B表示的是一条有向边，在【例1-10】中圆括号(1,2)表示的是一条无向边。【例1-11】设n为一个正整数，求下列各算法的时间复杂度。(1)voidprime(intn){i=2;while((n%i)!=0&&i*1.0sqrt(n))i++;if(i*1.0sqrt(n))printf(%d是一个素数＼n,n);elseprintf(%d不是一个素数＼n,n);(2)intsum1(intn){p=1;sum=0;for(i=1;i=n;i++){p*=i;sum+=p;}returnsum;(3)intsum2(intn){sum=0;for(i=1;i=n;i++){p=1;for(j=1;j=i;j++)p*=j;sum+=p;}returnsum;算法的时间复杂度是由嵌套最深层语句的执行次数决定的。(1)prime算法的嵌套最深层语句为：i++;它的执行次数由条件((n%i)!=0&&i*1.0sqrt(n))决定。显然执行次数小于sqrt(n)，所以prime算法的时间复杂度是O(n1/2)。(2)sum1算法的嵌套最深层语句为：p*=i;sum+=p;它们的执行次数均为n次，所以sum1算法的时间复杂度是O(n)。(3)sum2算法的嵌套最深层语句为：p*=j;它的执行次数为1+2+3+…+n＝n(n+1)/2次，所以sum2算法的时间复杂度是O(n2)。线性表及其存储结构1.线性表的基本概念2.线性表的顺序存储结构3.线性表的链式存储结构1.线性表的基本概念线性表(LinearList)：由n(n≥0)个数据元素组成的有序序列。注意：•数据元素的个数n称为线性表的长度。•当n=0时称为空表。•常常将非空的线性表(n0)记作：(a1，a2，…an)其中，ai(1≤i≤n)是线性表中的一个数据元素，也称作结点。2.线性表的顺序存储结构1）顺序表基本结构顺序表就是按照线性表各结点的逻辑次序把各点依次存放到一组连续的存储单元里。因此，在线性表的顺序存储结构中，前后相邻的两个数据元素在计算机的存储空间中也是前后相邻的。即，在顺序表中是用数据元素的前后位置关系来表示它们的逻辑关系的。有一个顺序表，它的每一个元素占内存2个字节，第1个元素的内存地址是1000，问该顺序表中第100个元素的地址是多少。答案：1000+（100-1）×2=11982）顺序表的运算顺序表的运算主要有：插入、删除、查找、排序、分解、合并和逆转。排序和查找将在后面介绍，这里介绍一下插入和删除运算。插入运算注：平均情况下，顺序表的插入运算需要移动表中一半的元素。删除运算注：平均情况下，顺序表的删除运算需要移动表中一半的元素有一个长度为n的顺序表，如果要在第i个和第i+1个元素之间插入一个新元素，请问要移动多少个元素？答案：n-i个3.线性表的链式存储结构1）线性链表基本结构线性链表是用任意的存储单元存储线性表的各个数据元素的。与顺序表不同，这组存储单元可以是连续的存储空间，也可以是不连续的，甚至是零散的。例如：线性表（A,B,C,D,E)的存储线性链表采用结点表示数据元素。每个结点有两个组成部分：单链表及其运算例：线性表（A,B,C,D,E）的单链表存储结构。单链表的运算主要有：查找、插入和删除运算。查找运算例如：在下面的链表中查找存在D吗？基本方法：从头指针指向的第一个结点开始沿着指针链依次向后搜索，逐个检查每个结点的数据域是否是指定元素，若是则返回该结点的地址，否则返回NULL。插入运算在单链表的第i个元素之后插入一个新元素x的基本方法是：①在单链表中查找到要插入的位置；②生成一个新结点存储新元素x；③将新结点插入到指定位置，更改相应元素指针域。删除运算要删除单链表中第i个元素的基本方法是：①在单链表中查找到要删除的元素；②更改相应元素的指针域，将第i-1个结点的指针域不再指向原来的第i个结点，改为指向第i+1个结点；③将要删除的结点移除。链表的特点数据元素不必连续存储不能随机访问数据元素插入、删除操作方便，不用移动数据元素栈及其存储结构1.栈的基本概念2.栈的顺序存储结构3.栈的链式存储结构栈的基本概念栈是一种特殊的线性表。栈是指一端封闭，只允许在另一端插入或删除元素的线性表。封闭的一端称为栈底，允许插入或删除元素的一端称为栈顶。向栈中插入元素的过程称为入栈运算或进栈运算；从栈中删除元素的过程称为出栈运算或退栈运算。栈中没有任何元素称为空栈。对于非空栈，处于栈顶的元素称为栈顶元素，处于栈底的元素称为栈底元素。栈是“先进后出”（firstinlastout,FILO）或“后进先出”（lastinfirstout,LIFO）表。进栈和出栈操作只能在栈顶进行。栈顶的位置在插入和删除中是动态变化的，通常设置一个变量指示栈顶的位置，称之为栈顶指针。栈底的位置是保持不变的。栈的示意图如下：栈又称为后进先出的线性表，简称LIFO（lastinfirstout）表。【例3-1】一个栈的进栈序列是A、B、C，试给出全部可能的输出序列和不可能的输出序列。栈的操作特点是后进先出，但不一定进栈顺序是A、B、C，出栈顺序就一定是C、B、A。因为可以调节输出的时机，如可以每次进栈一个元素就出栈，那么输出顺序就是A、B、C。因此输出序列有：A进，A出，B进，B出，C进，C出，输出序列为ABC。A进，A出，B进，C进，C出，B出，输出序列为ACB。A进，B进，B出，A出，C进，C出，输出序列为BAC。A进，B进，B出，C进，C出，A出，输出序列为BCA。A进，B进，C进，C出，B出，A出，输出序列为CBA。由A、B、C组成的数据项，除上述5种不同组合外，尚有CAB组合。但序列CAB是不可能的出栈序列。栈的顺序存储结构栈的顺序存储结构也称为顺序栈，它是一种运算受限的顺序表。对顺序栈可以有3种基本运算：入栈、出栈、读栈顶元素入栈运算向栈中插入元素的过程称为入栈运算。基本方法是：①将栈顶指针top向栈顶方向移动一个存储单元；②将要插入的元素插入到栈顶指针top指向的存储位置出栈运算指从栈顶删除一个元素并把它的值赋给某个变量。基本方法是：①将栈顶元素赋值给指定变量；②将栈顶指针top向栈底方向移动一个存储单元。读栈顶元素读栈顶元素就是将栈顶元素的值