《数据结构》复习

《《数据结构》复习》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构》复习第一章绪论一、基本概念：数据、数据元素、数据项数据结构、逻辑结构、物理结构线性结构、非线性结构顺序存储结构、链式存储结构、散列存储结构、索引存储结构数据类型、抽象数据类型。算法、语句的频度、算法的时间复杂度、算法的渐进复杂度空间复杂度二、数据结构概念：数据结构包括数据的逻辑结构、数据的存储结构和数据的运算。数据的运算定义在数据的逻辑结构上，是通过算法来描述的。数据运算的实现依赖于数据的存储结构。数据结构分类方法：按数据元素间的逻辑关系分类：集合、线性、树状、图状或网状按元素间的逻辑关系和施加的运算分类（

2、抽象数据类型）：线性表、栈、队列、串、数据、广义表树、二叉树、图查找表文件三、算法的时间复杂度算法的时间复杂度T(n):算法的时间消耗算法的时间消耗：所有语句的执行次数（频度）之和算法的渐进时间复杂度（简称时间复杂度）：当n->∞时，T(n)的数量级。即为T(n)中阶最高的那一项，是算法中频度最大的语句频度。空间复杂度：除数据集合所需的空间外，为实现运算所需的辅助空间的数量（级）。第二章线性表一、线性表的逻辑特征数据元素在线性表中的相对位置是线性的，可以用一个连续的整数编码来标识，即数据元素在线性表中的位置只依赖于它们

3、自己的序号，与数据元素的具体内容无关。二、对线性表的基本操作1、初始化操作2、求线性表的长度3、取表中第i个元素:若1≤i≤LENGTH(L)，则函数值为给定线性表中第i个元素，否则为元素NULL。4、定位函数:返回元素x的位序。5、INSERT（L，i,b）:前插函数。在第i个元素前插入数据元素b。6、DELETE（L，i）:删除第i个数据元素。7、删除指针p指定的结点。三、线性表的顺序存储结构（向量结构）用一组连续的存储单元依次存储线性表的元素。特点：1、逻辑上相邻的数据元素ai和ai+1的存储位置也相邻。即以数据

4、元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。loc(ai)=loc(a1)+(i-1)*Lloc(a1)是第一个数据元素的存储位置，通常称为线性表的起始地址或基地址。2、只要确定了存储线性表的起始地址，就直接确定了线性表中任一数据元素的存储位置，并且通过该公式实现对线性表元素的随机存取（访问）。线性表顺序存储结构的C描述线性表顺序存储结构的操作1、定位操作：定位平均比较次数为(∑i)/n=(n+1)/2，算法的时间复杂度为O(n)。不成功，则要比较n+1。2、INSERT(v,i,b):前插操作

5、，在第i个数据元素之前插入一个元素b。所需移动元素次数的期望值（平均次数）为：Eis=∑pi(n-i+1)=(n(n+1)/2)/(n+1)=n/2(i=1,2,…,n+1)即：算法的时间复杂度为O(n).3、删除运算：在长度为n的线性表中删除第i个元素。删除第i个元素移动次数为n-i平均移动次数为Ede=(∑(n-i))/n=(n-1)/2(i=1,2,...,n)删除运算的时间复杂度为O(n)缺点：插入删除操作可能要移动大量元素。四、线性表的链式存储结构特点：用一组任意的存储单元存放线性表的数据元素（存储单元可以不

6、连续）。数据元素间的逻辑关系表示：存储一个指示其直接后继的信息。用独立结点来存储数据元素的信息和指示数据元素间的逻辑关系。实现的C语言描述单链表的特点1、头指针：指示线性链表中第一个结点。2、最后一个结点无后继，其指针域设为“空”（NIL），表示链表到此结束。3、结点指针域：把内存中可能不连续的数据元素顺序组成一个线性表。4、要访问任一元素，必须从头指针出发寻找，是顺序访问结构。5、增设一个头结点，作为线性表的第一个结点，可以简化插入、删除算法。线性链表的运算1、在相邻元素a和b之间插入一个值为x的数据元素的基本操作步

7、骤：生成一个数据域值为x的结点s;使x结点的指针域指向结点b:s->next=p->next;修改a结点的指针域指向结点x:p->next=s;2、在第i个元素前插入一个元素x的步骤：生成一个数据域值为x的结点s;查找第i-1个接点p使x结点的指针域指向结点p的后继接点:s->next=p->next;使p结点的指针域指向结点s:p->next=s;3、删除第i个结点。实现：修改前驱结点(第i-1结点)的指针域使其指向第i+1个结点。插入和删除运算的关键：寻找前驱结点。在两种运算中，WHILE循环平均比较次数：(∑i)

8、/(n+1)=(n+1)/2（I=1,2,n+1）循环体的执行次数:(∑（i-1）/(n+1)=n/2时间复杂度为Ｏ(n)。采用线性链表的优点：①有效利用存储资源，提高程序运行的可靠性。有多少数据元素，才申请多少相应的存储空间。不使用的单元可归还给系统。存储密度②插入和删除，不需移动元素。3、循环链表使最后一个结点的指针域又指向第