全国计算机等级考试二级ACCESS公共基础知识1

等级考基础《数据结构与算法》2012年2月20日1.1数据结构的研究对象数据结构的研究内容：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。归纳为三部分：逻辑结构、存储结构和运算集合。按某种逻辑关系把一批数据组织起来，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义一个运算的集合。逻辑结构是数据结构的抽象，存储结构是数据结构的实现存储结构的二种类型:顺序存储结构—通过在存储器中的相对位置，表示数据的逻辑结构。非顺序存储结构（链式存储结构）--由指针表示数据间的逻辑关系。集合线性表树图1.3常用的数据结构(1)线性结构：结构中的数据元素之间存在着一对一的线性关系。线性表、栈、队、字符串、(2)树形结构：结构中的数据元素之间存在着一对多的层次关系。---(3)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。---非线性结构1．4算法与算法分析1.4算法与算法分析一算法的概念算法是对特定问题求解步骤的一种描述算法的基本特征：1）可行性：组成算法的操作必须能够在计算机上实现。2）确定性：算法的每一步操作必须清晰无二义性。3）有穷性：算法必须在有限步内结束；4）有足够的情报：0个或多个输入；1个或多个输出；算法描述的方法很多，如自然语言、框图、类C等例:求两个正整数m，n中的最大数MAX的算法（1）若mn则max=m（2）若m=n则max=n1、正确性：(1)没有语法错误；(2)对于几组输入数据能够得出满足要求的结果；(3)对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果。(4)对于一切合法的输入数据都能产生满足要求的结果。2、可读性：便于阅读、理解、调试、修改；3、健壮性：对不合法的输入能作出正确的反映与处理；4、高效性：执行时间短（时间复杂度）、需求存储空间省（空间复杂度）评价算法标准1时间复杂度T（n）以求解问题的基本操作的执行次数作为算法时间的度量。1．4算法与算法分析O（n3）称为矩阵相乘算法时间复杂度；O（n3）表示矩阵相乘算法执行时间与n3成正比,即O（n3）与n3同一数量级；例n阶矩阵相乘的算法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]}乘法加法执行次数均为n3矩阵相乘的基本运算：乘法加法；数据结构中常用的时间复杂度频率计数有7个：O(1)常数型O(n)线性型O(n2)平方型O(n3)O(2n)指数型O(log2n)对数型O(nlog2n)1．4算法与算法分析2算法空间复杂度用执行算法所需的内存空间的大小作为算法所需空间的度量。设执行算法所需的内存空间是问题规模n的某个函数g(n),则算法空间复杂度记作：S（n）=O(g(n))表示算法内存空间的增长率与g(n)的增长率相同例计算解法1先计算x的幂,存于power[]中,再分别乘以相应的系数#defineN100floatevaluate(floatcoef[],floatx,intn){floatpower[N],f;inti;for(power[0]=1,i=1;i=n;i++)power[i]=x*power[i-1];for(f=0,i=0;i=N;i++)f=f+coef[i]*power[i];return(f);}nnxaxaxaaxf...)(2210问题规模为n,算法时间复杂度:O(n)空间复杂度：O(N)线性表线性表是最简单、最常用的数据结构。栈、队列、串是特殊的线性表，数组和广义表是线性表的扩展--线性结构线性表是n个数据元素的有限序列，通常记作（a1,a2,a3,…,an）。姓名电话号码蔡颖63214444陈红63217777刘建平63216666王小林63218888张力63215555...2.1线性表的概念例、英文字母表（A,B,C,D,EZ）。某单位的电话号码簿。一线性表的逻辑结构2.1线性表的概念设A=（a1,a2,...,ai-1,ai,ai+1,…,an）是一线性表，1）同一线性表中的元素必须是同一类型的；2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的前件，ai+1是ai的后件；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个前件，有且仅有一个后件；4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；用一组连续的内存单元依次存放线性表的数据元素。a1a2ai-1aiai+1an线性表（a1,a2,a3,...an）的顺序存储结构用顺序存储结构存储的线性表——称为顺序表2.2线性表的顺序存储和实现一线性表的顺序存储结构2.2线性表的顺序存储和实现说明：元素之间的逻辑关系，通过元素的存储顺序表示出来.设线性表中每个数据元素占t个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：Loc(ai)=Loc(a1)+(i–1)t其中Loc(a1)基地址，随机存取a1a2ai-1aiai+1ant个单元Loc(a1)Loc(ai)2.2线性表的顺序存储和实现插入位置移动元素个数1n2n-1in-i+1n1n+10插入算法时间复杂度分析算法时间复杂度取决于移动元素的个数，移动元素的个数不仅与表长有关，而且与插入位置有关。a1a2ai-1aiai+1an01i-1i-2n-1..2.2线性表的顺序存储和实现由此可见在顺序表中插入一个元素，平均要移动表的一半元素。表长为n的顺序表，插入算法的时间复杂度为O（n）Eis=11nipi(n–i+1)假设在线性表的任何位置插入元素的概率相同，即pi=1/(n+1)设pi为在第i个元素之前插入元素的概率，在长度为n的顺序表中插入一个元素，所需移动元素个数数学期望值为：ninnEisni21)1(1111删除算法时间复杂度分析假设在线性表的任何位置删除元素的概率相同，即pi=1/n删除所需移动元素个数的数学期望值：)1(21)(11ninnEdsni2.2线性表的顺序存储和实现顺序表是线性表最简单的一种存储结构小结顺序表的特点：1通过元素的存储顺序反映线性表中数据元素之间的逻辑关系；2可随机存取顺序表的元素；3顺序表的插入、删除操作要通过移动元素实现；2.3线性表的链式存储和实现线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除需要存储自身的信息外，还要保存直接前趋元素或直接后继元素的存储位置。ai+1a1ai-1a2aian一线性链表的概念1线性链表2.3.1线性链表a4a3a1a20101010241014101010121014101610181020102210241026用一组任意的存储单元存储线性表中的数据元素，对每个数据元素保存自身信息和直接后继元素的存储位置。用链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的ai-1aia2a1ai+1nan结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；结点的数据域：保存数据元素;结点的指针域：保存数据元素直接后继的存储地址;线性链表有关术语2.3.1线性链表存储数据元素存储后继结点存储地址结点数据域指针域2.3.1线性链表头指针：存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针;头结点：链表的第一个元素结点前的附加结点；带头结点的线性链表：第一个元素结点前增加一个附加结点的线性链表称为带头结点的线性链表；head是头指针ai-1aia2a1ai+1nan头结点空指针head线性链表的每个结点中只有一个指针域故也称为单链表插入结点(存a)q=(LNODE*)malloc(sizeof(LNODE));q-deta=‘a’;q-next=p-next;p-next=q;headzyxpyxzpheadaq插入操作功能：在线性链表的第i个元素结点之前插入一个新元素结点e；插入操作图示：2.3.1线性链表插入前插入后ai-1aia2a1ai+1nanheadai-1aia2a1ai+1nanehead4）删除结点q=p-next;p-next=q-next;free(q);headzyxqyxzqheadpp2.3.1线性链表删除前删除后ai-1aia2a1ai+1nanheadai-1aia2a1ai+1nanheadppqq2.3.1线性链表小结线性链表是线性表的一种链式存储结构线性链表的特点1通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；2插入、删除操作通过修改结点的指针实现；3不能随机存取元素；1循环链表的概念循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点（首尾相连的单链表）2循环链表图示2.3.2循环链表(a)非空表（b）空表headheada1an循环链表说明在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；对循环链表，有时不给出头指针，而是给出尾指针aa1ana-next给出尾指针的循环链表2.3.4循环单链表，虽然从任一结点出发沿着指针链能找到其前件，但时间耗费是O(n)。如果希望从表中快速确定某一个结点的前件，另一个解决方法是在链表的每个结点里再增加一个指向其前件的指针域prior。这样形成的链表中就有两条方向不同的链，称为双向链表。线性表小结线性表的顺序存储结构—顺序表，链式存储结构----线性链表,循环链表,双向链表.不同的存储结构，线性表的同一操作的算法是不同的:在顺序存储结构下，线性表的插入、删除操作，通过移动元素实现;在线性链表存储结构下，线性表的插入、删除操作，通过修改指针实现。3.1栈栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除3.1.1栈的概念一什么是栈?3.1栈将表中允许进行插入、删除操作的一端称为栈顶(Top)，栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。表的另一端称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作称为进栈或入栈，删除操作称为出栈或退栈。栈an…a2a1进栈出栈栈顶栈底进栈出栈(a)栈的示意图(b)铁路调序栈的表示3.1栈栈的示意图出栈进栈栈的特点后进先出第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素栈顶栈底ana2a1B例:如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是?A)e3,e1,e4,e2B)e2,e4,e3,e1C)e3,e4,e1,e2D)任意顺序小结1栈是限定仅能在表尾一端进行插入、删除操作的线性表；2栈的元素具有后进先出的特点；3栈顶元素的位置由一个称为栈顶指针的变量指示，进栈、出栈操作要修改栈顶指针；3.1栈3．2队列3.2.1队列的概念一什么是队列队列是限定仅能在表头进行删除，表尾进行插入的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除3．3队列a1a2a3an入队列队头队尾出队列队列的示意图队列的特点先进先出第一个入队的元素在队头，最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素rearfrontJ1rearfrontJ2（a)空队列(b)J1,J2相继入队列(c)J1出队(d)J3,J4,J5和J6相继入队之后,J2出队rearfront0123453.3队列rearfrontJ5J4J3front,rear为整数又有J7入队,怎么办？J2J63.3队列3.循环队列frontrearJ6J4J5312405rear540312frontJ6J7J8J9J4J5frontrear540312(b)队空(a)队满J7rear3.3队列判分队空、队满方法：1）另设一个标志S以区分