数据结构b复习

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

1、数据结构B（C语言描述）复习提纲（2011.11.20）duanwh@126.com第1章基础知识1.数据是计算机加工处理的对象。(1)数值数据(2)非数值数据（数据结构主要是研究非数值数据）2.数据元素是组成数据的成分数据。(1)简单类型(2)结构类型（由若干数据项组成）3.逻辑结构：数据元素之间的逻辑关系（面向问题的，从用户角度）。★★★(1)集合结构(2)线性结构(3)树形结构(4)图结构4.存储结构：数据在计算机内的组织方式，是逻辑数据的存储映像（面向计算机的）。两种基本的存储结构：★★★(1)顺序存储(2)链接存储5.数据结构主要包括三个方面：逻辑

2、结构，存储结构，在该数据结构上执行的相关运算及其实现。★★★6.算法定义：算法是对特定问题求解步骤的一种描述。7.算法的五个特征。(1)输入：算法有零个或多个输入。(2)输出：算法至少有一个输出。★★(3)确定性：算法的每一条指令都有确定的定义，没有二义性。(4)能行性：算法的每条指令都足够基本，它们可以通过执行有限次已经实现的基本运算来实现。(5)有穷性：算法能在执行有限步后终止。★★8.衡量一个算法性能的4个标准：(1)正确性。(2)简明性。(3)健壮性。(4)效率。9.时间复杂度和空间复杂度123OOnO()(<

3、()()2nO

4、向变量的指针(2)指向数组的指针(3)指向结构的指针(4)动态分配存储空间16.单链表的基本操作★★★17.带表头结点的单链表，相较于普通的单链表，可以简化操作。★★18.双向链表的插入和删除操作(1)插入操作(2)删除操作第3章堆栈和队列19.堆栈和队列是特殊的线性表，它们存取元素只能在线性表的端点进行。★★★插入删除遵循的原则堆栈栈顶栈顶LIFO后进先出队列队尾队首FIFO先进先出20.栈的顺序存储实现（程序）21.循环队列程序实现（程序，循环队列可以解决假溢出现象）★★(1)是否空IsEmpty：q.Front==q.Rear;(2)是否满IsFull

5、：(q.Rear+1)%q.MaxQueue==q.Front;(3)入队Append：q->Elements[q->Rear=(q->Rear+1)%q->MaxQueue]=x;(4)出队Serve：q->Front=(q->Front+1)%MaxQueue22.栈的应用(1)后缀表达式的求解（给出结果即可）(2)将中缀表达式转换为后缀表达式（给出结果即可）第4章线性表23.线性表的存储结构有两种：(3)顺序存储结构（顺序表）(4)链接存储结构（链表）。数据结构B复习提纲第2页24.平均情况下★★★(1)在顺序表中插入元素需要移动元素的平均个数是：n−

6、11nEi=∑(n−i−1)=n+1i=−12(2)在顺序表中删除元素需要移动元素的平均个数是：n−11n−1Ed=∑(n−i−1)=ni=0225.线性表的链接表示：★★★(1)单链表（单链表增加结点删除结点可能涉及到修改first指针）(2)带表头结点的单链表（对于删除和增加结点的时候不必修改first指针）(3)单向循环链表（多项式是用带表头结点的单循环链表表示的）(4)双向循环链表：双向循环链表的插入和删除操作的核心步骤。注意：单链表进行插入和删除操作的时候要用到两个指针，修改结点指针域的时候要注意顺序。26.顺序表的优点和缺点。（顺序存储结构和链式

7、存储结构的比较）★★★优点：(1)存储空间利用率高(2)可随机存取元素。缺点是(1)遇到插入删除操作的时候需要大量移动元素，效率低。(2)需要按事先估计的最大元素个数分配连续的存储空间，难以临时扩大27.对称矩阵的压缩存储(1)对称矩阵可只存储上三角（或下三角）中的元素（包括对角线上的元素），这样原2有n个元素的堆成矩阵，只需要num=n(n+1)/2个元素的存储空间，从而提高了存储效率。★★(2)ijk的相互表示28.稀疏矩阵的三元组表示★★★(1)行三元组表示(2)列三元组表示29.稀疏矩阵的快速转置法中，num数组和k数组的求法。★★★Col0123…

8、n-1num[col]k[col]第5章字符串和广义