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

数据结构期末复习,主要知识点,,算法的时间复杂度计算方法,单链表,堆栈和队列的概念和应用,串的概念和应用,树的概念和应用,图的概念和应用,查找和排序,算法满足以下性质: (1)输入性(2)输出性 (3)有限性 (4)确定性 (5)可执行性,算法设计满足以下目标: (1)正确性 (2)可读性 (3)健壮性 (4)高时间效率 (5)高空间效率,算法的时间复杂度计算方法,常见的时间复杂度表示： O(1)，O(n)，O(n2) ，O(n3)，O(lbn) ，O(lgn),算法时间复杂度定义:T(n)=O(f(n)),当且仅当存在正常数c和n0，对所有的n(n≥ n0)满足T(n)≤c×f(n) T（n）为算法的基本语句执行次数，称为时间复杂度，随n增大与f（n）增长接近相同，级，用O(f（n）)表示其复杂度即可称同一个数量推导大O阶的方法:,(1)用常数1取代运行时间中的所有加法常数 (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+n+1=2n+3次 在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数： 该算法的时间复杂度为 T(n)=O(n) 称为线性阶 注意：分析这类算法的复杂度关键是分析循环结构的运行情况,例2 求和算法，求1+2+3………+99+100=5050int sum=0,n=100; //执行了1次 sum=(1+n)*n/2 //执行1次 printf(“%d”,sum); //执行了1次,该算法一共执行了1+1+1=3次 在求时间复杂度的时候只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数： 该算法的时间复杂度为 T(n)=O(1) 称为常数阶 注意：不管这个常数是多少，我们都记做O(1) ，而不是O(3)。

例3 求和算法，求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次,在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数： 该算法的时间复杂度为 T(n)=O(n2) 称为平方阶 注意：循环的时间复杂度等于循环体的复杂度乘以该循环的次数,例1-3 设数组a和b在前边部分已赋值，求如下两个n阶矩阵相乘运算算法的时间复杂度for(i=0;in;i++) for(j=0;jn;j++) { c[i][j]=0; //基本语句1 for(k=0;kn;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; //基本语句2 },该算法的时间复杂度为 T(n)=O(n3),例1-4 设n为如下算法处理的数据个数，求如下算法的时间复杂度。

for(i=1;i=n;i=2*i) printf(“i=%d\n”，i)；,解:设基本语句的执行次数为T(n),有2T(n) ≤ n,即有T(n) ≤lbn 所以该算法的时间复杂度为T(n)=O(lb n) 称为对数阶,例1-5:下边的算法是用冒泡排序法对数字a中的n个整数类型的数据元素(a[0]~a[n-1])，从小到大进行排序，求该算法的时间复杂度void BubbleSort(int a[],int n) { int i,j,flag=1; int temp; for(i=1;ia[j+1]) { flag=1; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } },解:该算法基本语句执行次数与原始数据序列大小情况有关系，此时，按最坏情况统计 设基本语句的执行次数为T(n),最坏情况下有 T(n)≈n+4*n2/2 因 T(n) ≈n+2* n2 ≤c* n2, 其中c为常数，所以该算法的时间复杂度为 T(n)=O(n2)算法的时间复杂度是衡量一个算法好坏的重要指标一般来说，具有多项式时间复杂度的算法，是可接受、可实际使用的算法;具有指数时间复杂度的算法，是只有当n足够小时才可使用的算法。

例1-6 下面的算法是在一个有n个数据元素的数组a中删除第i个位置的数组元素，要求当删除成功时数组元素个数减1，求该算法的时间复杂度其中数组下标从0至n-1int Delete(int a[], int //删除成功返回 },解:该算法与要删除元素位置i有关，此时一般按i所有取值情况下的平均执行次数来统计 假设删除任何位置上的数据元素都是等概率的,设Pi为删除第i个位置上数据元素的概率，则有Pi=1/n，设E为删除数组元素的平均次数，则有,因T(n)=E≤(n+1)/2 ≤ c*n,其中c为常数，所以该算法的等概率平均时间复杂度为 T(n)= O(n)插入效率：,删除效率：,顺序表操作的效率分析,单链表操作的效率分析 单链表的插入和删除操作不需移动数据元素，只需比较数据元素因此，当在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：,删除一个数据元素时比较数据元素的平均次数为：,另外，单链表求数据元素个数操作的时间复杂度为O(n)1、在数据结构中，从逻辑上可以把数据结构分为（ ） A．动态结构和静态结构。

B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2、数据结构在计算机内存中的表示是指（ ） A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系C,A,习题练习,3、在数据结构中，与所使用的计算机无关的是数据的 （ ）结构 A．逻辑 B．存储 C．逻辑和存储 D．物理 4、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ） A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 5、在决定选取何种存储结构时，一般不考虑（ ） A．各结点的值如何 B．结点个数的多少 C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便A,C,A,6、算法分析的目的是（ ），算法分析的两个主要方面是（ ） （1） A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易读性和文档性 （2） A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性。

C,A,7、下面程序段的时间复杂度是 s ＝0； for（ i ＝0； i＜n； i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝ s ； 8、下面程序段的时间复杂度是 for（ i ＝0； i＜n； i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝ 0； 9、下面程序段的时间复杂度是 i ＝ 0； while（i＜＝n） i ＝ i * 2；,O（n2）,O（n*m）,O（log2n）,1).在带头结点单链表第一个数据元素前插入结点,带头结点单链表和不带头结点单链表的比较,核心操作语句为： p=head；s-next=p-next; p-next=s;,注：两条语句顺序不能颠倒，即“先勾右链，再勾左链”,单链表,2).删除带头结点单链表第一个数据元素结点,核心操作语句为： p=head；s=p-next; *x=s-data p-next=p-next-next; free(s);,3).在不带头结点单链表第一个数据元素前插入结点,核心操作语句为： s-next=head; head=s;,4).在不带头结点单链表其他数据元素前插入结点,核心操作语句为： s-next=p-next; p-next=s;,5).删除不带头结点单链表第一个数据元素结点,6).删除不带头结点单链表其他数据元素结点,核心操作语句为： s=head-next; head=head-next; free(s);,核心操作语句为： s=p-next; *x=s-data p-next=p-next-next; free(s);,1、在带头结点的单链表head中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行的核心代码是（ ）。

s-next=p；p-next=s； s-next=p-next；p-next=s； C. s-next=p-next；p=s； D. p-next=s；s-next=p； 2、在带头结点的单链表head中，若删除p所指结点的后继结点，则执行的核心代码是（ ） p-next=p-next-next； p=p-next；p-next=p-next-next； C. p-next=p-next； D. p=p-next-next；,习题练习,B,A,4、单链表中，增加一个头结点的目的是为了（ ） 使单链表至少有一个结点 标识表结点中首结点的位置 C. 方便运算的实现 D. 说明单链表是线性表的链式存储 5、带头结点的单链表head为空的判定条件是（ ） A. head==NULL B. head-Next==NULL C. head-next==head D. head!=NULL,C,B,6、已知head为带头结点的单链表，p为其中非首元的结点，分别写出以下操作的序列： （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)定义:限定只能在固定一端进行插入和删除操作的线性表特点：后进先出故又称后进先出表,,(2)允许进行插入和删除操作的一端称为栈顶，另一端称为栈底队列的基本概念,堆栈的基本概念,(1)定义:只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表（又称先进先出表）一个队列。