数据结构——期末复习.ppt

《数据结构——期末复习.ppt》由会员分享，可在线阅读，更多相关《数据结构——期末复习.ppt（65页珍藏版）》请在第壹文秘上搜索。

1、数据结构期末复习数据结构期末复习主要知识点主要知识点算法的时间复杂度计算方法算法的时间复杂度计算方法单链表单链表堆栈和队列的概念和应用堆栈和队列的概念和应用串的概念和应用串的概念和应用树的概念和应用树的概念和应用图的概念和应用图的概念和应用查找和排序查找和排序算法满足以下性质算法满足以下性质: (1)输入性输入性(2)输出性输出性 (3)有限性有限性 (4)确定性确定性 (5)可执行性可执行性算法设计满足以下目标算法设计满足以下目标: (1)正确性正确性 (2)可读性可读性 (3)健壮性健壮性 (4)高时间效率高时间效率 (5)高空间效率高空间效率算法的时间复杂度计算方法算法的时间复杂度计算方

2、法常见的时间复杂度表示：常见的时间复杂度表示：O(1)，O(n)，O(n2) ，O(n3)，O(lbn) ，O(lgn)算法时间复杂度定义算法时间复杂度定义:T(n)=O(f(n),当且仅当存在正常数当且仅当存在正常数c和和n0，对所有的对所有的n(n n0)满足满足T(n)cf(n) 。T（n）为算法的）为算法的基本语句执行次数，称为时间复杂度，随基本语句执行次数，称为时间复杂度，随n增大与增大与f（n）增）增长接近相同，级，用长接近相同，级，用O(f（n）)表示其复杂度即可称同一个表示其复杂度即可称同一个数量。数量。推导大推导大O阶的方法阶的方法:(1)用常数用常数1取代运行时间中的所有加

3、法常数。取代运行时间中的所有加法常数。(2)在修改后的运行次数函数中，只保留最高阶项。在修改后的运行次数函数中，只保留最高阶项。(3)如果最高阶项在且不是如果最高阶项在且不是1，则去除与这个项相乘的常数，则去除与这个项相乘的常数最后得到的结果就是大最后得到的结果就是大O阶阶 例例1 求和算法，求求和算法，求1+2+3.+99+100=5050。int i,sum=0,n=100; /执行了执行了1次次 for(i=1;i=n;i+) /执行执行n+1次次 sum=sum+i; /执行执行n次次 printf(“%d”,sum); /执行了执行了1次次 该算法一共执行了该算法一共执行了1+n+1

4、+n+1=2n+3次次在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数：数量必须表示成输入规模的函数：该算法的该算法的时间复杂度为时间复杂度为 T(n)=O(n) 称为线性阶称为线性阶注意：分析这类算法的复杂度关键是分析循环结构的运行情况注意：分析这类算法的复杂度关键是分析循环结构的运行情况 例例2 求和算法，求求和算法，求1+2+3.+99+100=5050。int sum=0,n=100; /执行

5、了执行了1次次sum=(1+n)*n/2 /执行执行1次次printf(“%d”,sum); /执行了执行了1次次 该算法一共执行了该算法一共执行了1+1+1=3次次在求时间复杂度的时候只需要分析影响一个算法时在求时间复杂度的时候只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数：表示成输入规模的函数：该算法的该算法的时间复杂度为时间复杂度为 T(n)=O(1) 称为常数阶称为常数阶注意：不管这个常数是多少，我们都记做注意：不管这个常数是多少，我们都记做O(1) ，而，而不是不是O(3)。 例例3 求和算法，求求

6、和算法，求1+2+3.+99+100+.=int i,j,x=0,sum=0,n=100; /执行了执行了1次次 for(i=1;i=n;i+) for(j=1;j=n;j+) x+; /执行执行n*n次次 sum=sum+x; printf(“%d”,sum); /执行了执行了1次次 在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要分在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数：必须表示成输入规模的函数：该算法的该算法的时间复杂度为时间复杂

7、度为 T(n)=O(n2) 称为平方阶称为平方阶注意：循环的时间复杂度等于循环体的复杂度乘以该循环的次数注意：循环的时间复杂度等于循环体的复杂度乘以该循环的次数 例例1-3 设数组设数组a和和b在前边部分已赋值，求如下两个在前边部分已赋值，求如下两个n阶矩阶矩阵相乘运算算法的时间复杂度。阵相乘运算算法的时间复杂度。for(i=0;in;i+) for(j=0;jn;j+) cij=0; /基本语句基本语句1 for(k=0;kn;k+) cij=cij+aik*bkj; /基本语句基本语句2 该算法的该算法的时间复杂度为时间复杂度为 T(n)=O(n3) 例例1-4 设设n为如下算法处理的数据

8、个数，求如下算法的为如下算法处理的数据个数，求如下算法的时间复杂度。时间复杂度。 for(i=1;i=n;i=2*i) printf(“i=%dn”，i)；解解: :设基本语句的执行次数为设基本语句的执行次数为T(n), ,有有2 2T T( (n n) ) n,即有即有T(n) lbn。所以该算法的时间复杂度为所以该算法的时间复杂度为T(n)=O(lb n)。 称为对数阶称为对数阶 例例1-5:下边的算法是用冒泡排序法对数字下边的算法是用冒泡排序法对数字a中的中的n个整数个整数类型的数据元素类型的数据元素(a0an-1)，从小到大进行排序，求该算从小到大进行排序，求该算法的时间复杂度。法的时

9、间复杂度。void BubbleSort(int a,int n) int i,j,flag=1; int temp; for(i=1;in&flag=1;i+) flag=0; for(j=0;jaj+1) flag=1; temp=aj; aj=aj+1; aj+1=temp; 解解:该算法基本语句执行次数与原始数据序列大小情况有关该算法基本语句执行次数与原始数据序列大小情况有关系，此时，按系，此时，按最坏情况统计最坏情况统计。设基本语句的执行次数为设基本语句的执行次数为T(n),最坏情况下有最坏情况下有 T(n)n+4*n2/2因因T(n) n+2* n2 c* n2,其中其中c为常数，

10、所以该算法的时间复杂度为为常数，所以该算法的时间复杂度为T(n)=O(n2)。 算法的时间复杂度是衡量一个算法好坏的重要指标。一算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有般来说，具有多项式时间复杂度多项式时间复杂度的算法，是的算法，是可接受、可实际可接受、可实际使用使用的算法的算法;具有具有指数时间复杂度指数时间复杂度的算法，是只有当的算法，是只有当n足够足够小小时才可使用的算法。时才可使用的算法。 例例1-6 下面的算法是在一个有下面的算法是在一个有n个数据元素的数组个数据元素的数组a中删中删除第除第i个位置的数组元素，要求当删除成功时数组元素个数个位置的数组元素，要求当删

11、除成功时数组元素个数减减1，求该算法的时间复杂度。其中数组下标从，求该算法的时间复杂度。其中数组下标从0至至n-1。int Delete(int a, int &n,int i) int j; if(i=n) return 0; /删除位置错误，失败返回删除位置错误，失败返回 for(j=i+1;jnext=p-next;p-next=s;注：两条语句顺序不能颠倒，即注：两条语句顺序不能颠倒，即“先勾右链，再勾左链先勾右链，再勾左链”单链表单链表2).删除带头结点单链表第一个数据元素结点删除带头结点单链表第一个数据元素结点pa0a1an-1headdata next核心操作语句为：核心操作语句

12、为：p=head；s=p-next; *x=s-datap-next=p-next-next; free(s);3).在不带头结点单链表第一个数据元素前插入结点在不带头结点单链表第一个数据元素前插入结点a0a1an-1headxs(a) 插入前插入前a0a1an-1headxs(b) 插入后插入后核心操作语句为：核心操作语句为：s-next=head;head=s;4).在不带头结点单链表其他数据元素前插入结点在不带头结点单链表其他数据元素前插入结点pai-1a0aian-1headdata nextxs核心操作语句为：核心操作语句为：s-next=p-next;p-next=s;5).删除不

13、带头结点单链表第一个数据元素结点删除不带头结点单链表第一个数据元素结点a0a1an-1headdata next6).删除不带头结点单链表其他数据元素结点删除不带头结点单链表其他数据元素结点pai-1a0aian-1headdata nextai+1核心操作语句为：核心操作语句为：s=head-next;head=head-next; free(s);核心操作语句为：核心操作语句为：s=p-next; *x=s-datap-next=p-next-next; free(s);1、在带头结点的单链表、在带头结点的单链表head中，若中，若p所指结点不是最后结点所指结点不是最后结点，在，在p之后插

14、入之后插入s所指结点，则执行的核心代码是（所指结点，则执行的核心代码是（ ）。）。A.s-next=p；p-next=s；B.s-next=p-next；p-next=s；C. s-next=p-next；p=s；D. p-next=s；s-next=p；2、在带头结点的单链表、在带头结点的单链表head中，若删除中，若删除p所指结点的后继结所指结点的后继结点，则执行的核心代码是（点，则执行的核心代码是（ ）。）。A.p-next=p-next-next；B.p=p-next；p-next=p-next-next；C. p-next=p-next；D. p=p-next-next；习题练习习题

15、练习BA4、单链表中，增加一个头结点的目的是为了（、单链表中，增加一个头结点的目的是为了（ ）。）。A.使单链表至少有一个结点。使单链表至少有一个结点。 B.标识表结点中首结点的位置。标识表结点中首结点的位置。C. 方便运算的实现。方便运算的实现。 D. 说明单链表是线性表的链式存储。说明单链表是线性表的链式存储。5、带头结点的单链表、带头结点的单链表head为空的判定条件是（为空的判定条件是（ ）。）。A. head=NULL B. head-Next=NULL C. head-next=head D. head!=NULLCB6、已知已知head为带头结点的单链表，为带头结点的单链表，p为

16、其中非首元的结点，分为其中非首元的结点，分别写出以下操作的序列：别写出以下操作的序列：（1）将）将s结点插入结点插入p结点之后；结点之后；（2）删除）删除p的直接后继结点；的直接后继结点；（3）删除尾元结点；）删除尾元结点；s-Next=p-Next; p-Next=s;q= p-Next; p-Next= p-Next-Next; free(q);p=head;While(p-Next-Next!=NULL) p=p-Next;q= p-Next;p-Next= p-Next-Next;free(q);堆栈和队列的基本概念和应用堆栈和队列的基本概念和应用堆栈的数据元素及逻辑关系与线性表完全相同，但是操作受限。堆栈的数据元素及逻辑关系与线性表完全相同，但是操作受限。(1)(1)定义定义: :限定只能在固定一端进行插入和删除操作的线性表。限定只能在固定一端进行插入和删除操作的线性表。特点：后进先出。特点：后进先出。故又称故又称后进先出表后进先出表(2)允许进行插入和删除操作的一端称为允许进行插入和删除操作的一端称为栈顶栈顶，另一端称为，另一端称为栈底。栈底。队列的基本概念队列的基本概念堆