数据结构_(严蔚敏C语言版)_学 习、复习提纲

数据结构⽼师给的复习要点（严蔚敏版）第⼀章1. 怎样理解“算法+数据结构=程序”这个公式？举例说明。

算法是语句序列解决特定问题的固有程序⽚段。

数据结构是确定数据间的关系。

从具体问题抽象出⼀个合适的数学模型、然后设计⼀个解决此数学模型的算法，最后编写出程序。

寻求数学模型的是指就是数据结构要完成的⼯作。

参看书p1前两段的描述。

2. 数据结构的概念，它包含哪三⽅⾯的内容？数据结构：是⼀门研究⾮数值计算的程序设计问题中计算机的操作对象以及它们之间饿关系和操作的学科。

参看书p3包含三⽅⾯的内容:1、数据之间的逻辑关系2、数据在计算机中的存储⽅式3、在数据上定义的运算的集合。

3. 数据、数据元素、数据项的基本概念。

举例说明数据元素和数据项的联系与区别。

数据：描述客观事物的数字、字符以及所有能直接输⼊到计算机中并被计算机程序处理的符号的集合。

数据元素：数据的基本单位，在计算机程序中通常作为⼀个整体进⾏考虑或处理。

数据项：数据项是具有独⽴含义的最⼩标识单位，是数据元的⼀个具体值，是数据记录中最基本的、不可分的有名数据单位。

例1：class A{int c[123];int i;};class B{A a;}B b;b.a是数据项，B是数据元素例2：⼀本书的数⽬信息为⼀个数据元素，⽽数⽬信息中每⼀项（如书名、作者名等）为⼀个数据项4. 从逻辑结构来看，数据结构有哪四种基本结构，各⾃的特点是什么？1、集合（数据元素之间同属于⼀个集合，再⽆其他关系）2、线性结构（数据元素之间存在⼀对⼀的关系）3、树形结构（数据元素之间⼀对多的关系）4、图状结构或⽹状结构（数据元素之间多对多的关系）5. 从物理结构来看，数据结构有哪两种基本结构，各⾃的特点是什么？1、顺序存储结构特点：借助元素在存储器中的相应位置来表⽰数据元素之间的逻辑关系。

2、链式存储结构特定：借助元素在存储地址的指针表⽰数据元素之间的逻辑关系。

6. 算法的5个特征，4个评价标准是什么？特征:有穷性、确定性、可⾏性、输⼊、输出。

期末复习复习第一章绪论数据：计算机处理的信息总称数据项：最小单位数据元素：最基本单数据对象：元素集合数据结构：相互之间存在一种或多种特定关系的数据元素集合。

概念：数据元素之间的关系线性结构：一对逻辑结构非线性结构数据结构树：一对多图：多对多顺序存储结构链表存储结构存储结构。

索引。

基。

散列。

础知数据运算识算法描述：指令的有限有序序列有穷性确定性算法特性可行性算法输入输出时间复杂度算法分析空间复杂度、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。

1 2、算法分析的两个主要方面是空间复杂度和时间复杂度。

3、数据元素是数据的基本单位。

4、数据项是数据的最小单位。

5、数据结构是带结构的数据元素的集合。

6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。

线性表复习第二章定义逻辑关系：前趋后继节省空间基本特点随机存取插、删效率低顺序存储结构插入基本运算删除一个数据一个指针多占空特查找费插、删效率无法查找前趋结单链运算特点：单链表+前趋指针域链表存储双向结构链表插入运算删除特点：单链表的尾结点指针循环指向附加头结点。

链表运算：联接1 、一个指向后继结点的指针、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 2、线性表采用顺序存储，必须占用一片连续的存储单元、线性表采用链式存储，便于进行插入和删除操作3 、线性表采用顺序存储和链式存储优缺点比较。

4 5、简单算法复习栈和队列第三章．栈的概念：在一端操作的线性表LIFO栈的特点：先进后出存储结初始化push 进栈运算算法pop出栈队列概念：在两端操作的线性表FIFO队列特点：先进先出假溢出顺序队列front=rear队空：循环队列front=(rear+1)%MAXSIZE队满：队列front∧队空：链队列rear初始化判空顺序：进队基本运算链队：出队取队首元素1栈和队列的异同点。

、、2栈和队列的基本运算出栈和出队、3 、4基本运算复习串第四章．n(≥)个字符组成的有限序列1定义：由”c……cS=”cc n231串长度、空白串、空串。

数据结构期末复习要点第一章绪论1、掌握基本概念和术语，看教材P4—P6部分内容；2、看P10—P11关于类C的语法描述，算法设计写代码时可用到；3、掌握算法的特征（5个）和要求（5个）（P13—P14），能够结合具体算法分析算法的时间复杂度和空间复杂度（比如线性表的插入、删除操作，查找、排序等操作），理解O(n)、O(1)等时间复杂度的具体含义（P14—P17）。

第二章线性表1、看教材P21—P26，掌握有关线性表顺序存储的内容：（1）顺序表的随机存取（P21计算地址的公式）；（2）顺序表的表示（P22的Typedef）；（3）顺序表为空、为满的判定，插入和删除操作的特征以及时间复杂度的分析（P23—P25）；（4）有关顺序表的编程题。

2、看教材P27—P30，掌握有关线性表链式存储的内容：（1）单链表的表示（P28的Typedef）；（2）单链表为空的判定（带头结点、不带头结点）；（3）单链表插入、删除操作的特征（操作点的确定以和指针的修改）以及时间复杂度分析（P29—P30）；（4）有关单链表的编程。

3、为节约时间，循环链表、双向链表以及多项式加法可以不看；4、算法设计题要求写代码，在本章体现的可能性比较大。

第三章栈和队列1、顺序栈的表示，栈操作的特点以及为空、为满的判定（P46—P47）；2、栈的应用举例看个标题就足够了；3、链队列的表示以及入队、出队操作（P61—P62）；4、循环队列为空、为满的判定（P65的代码中）；5、离散事件模拟这节不用看；6、第四章只需要看P70就够了，掌握串的特点（元素受限），串长度、空串、串的位置、串相等几个概念即可。

第六章树和二叉树1、看教材P120，了解有关树的概念和术语；2、了解二叉树的链式存储结构（P127），掌握二叉树的性质（P123—P125），并会做题（参考课件或指导书相关内容）；3、掌握二叉树的各种遍历算法（P128—P129或课件）：（1）能够根据二叉树写出各种遍历序列；（2）能够由两种遍历序列（必须包含中序序列）恢复二叉树；（3）理解二叉树遍历算法的递归代码，能够读懂代码含义。

第5章数组和广义表5.1 复习笔记一、数组的定义1．二维数组类似于线性表，一个二维数组的逻辑结构形式表示为：2-Array＝（D，R）其中D＝{a ij|i＝c1，c1＋1，…，d l，j＝c2，c2＋1，…，d2，a ij∈D0}R＝{ROW，COL}ROW＝{<a ij，a i，j＋1>|c1≤i≤d1，c2≤j≤d2－1，a ij，a i，j＋1∈D}COL＝{<a ij，a i＋1，j>|c1≤i≤d1－1，c2≤j≤d2，a ij，a i＋1，j∈D}D0为某个数据对象，c1，c2，d1，d2均为整数。

【注意】①二维数组中含有（d1－c1＋1）×（d2－c2＋1）个数据元素，每个数据元素a ij都受行关系、列关系约束。

②a i，j＋1是a ij在行关系中的直接后继元素；而a i＋1，j是a ij在列关系中的直接后继元素。

③数组中所有的数据元素属于同一数据类型。

2．n维数组n 维数组的逻辑结构形式定义如下：n-Array ＝（D ，R ）其中 12120,1,,,1,2,,(0),n n i i i i j j j j j j i i j c c d i n n D a a D c d ⎧⎫=+=>⎪⎪=⎨⎬∈⎪⎪⎩⎭且和均为整数12{,},,n R R R R =11111111,1,i n i n i n i n i j j j j k k k j j i i i j j j j j j R a a c j d k n k c j d a a D ++=<>⎧⎫≤≤≤≤≠⎪⎪≤≤-⎨⎬⎪⎪∈⎩⎭ 且【注意】 ①n 维数组含有)1(1+-∏=i i ni c d 个数据元素，每个数据元素都受n 个关系的约束。

②在每个关系中，数据元素12(1)n j j j i i i a c j d ⋯≤≤-都有一个直接后继元素。

二、数组的顺序表示和实现1．二维数组的两种存储方式二维数组的顺序存储结构有两种存储方式：（1）以列序为主序的存储方式，如图5-1（a）所示；（2）以行序为主序的存储方式，如图5-1（b）所示。

1.复杂性分析对各种操作的时间复杂性的分析。

主要是链表，树，排序等简单一些的分析。

分析的时候,从简单的入手,学会方法。

后续的各种豆可能让你分析时间复杂度。

线性链表（顺序表和单链表）链表循环链表双向链表2.线性结构队列（循环队列)栈链表主要操作:找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除)。

栈：查找，插入（位置固定），删除(位置固定）队列：查找，插入（位置固定)，删除（位置固定）顺序表（可以视为一个数组）单链表：（删除）(插入）倒置：(查找）循环链表双向链表栈：(插入删除查找)队列(插入删除查找）循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。

3.二叉树基本概念二叉树是每个节点最多有两个子树的有序树。

二叉树常被用于实现二叉查找树和二叉堆。

值得注意的是,二叉树不是树的特殊情形。

二叉树是每个结点最多有两个子树的有序树。

通常根的子树被称作“左子树”(left subtree）和“右子树”（right subtree）。

二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

二叉树的每个结点至多只有二棵子树（不存在出度大于2的结点），二叉树的子树有左右之分,次序不能颠倒。

二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：1. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2；2。

树的结点无左、右之分，而二叉树的结点有左、右之分。

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：（1）空二叉树——如图（a)；（2)只有一个根结点的二叉树——如图（b);(3）只有左子树——如图（c）；（4)只有右子树-—如图（d）;(5）完全二叉树-—如图（e)注意:尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形性质（1）在非空二叉树中，第i层的结点总数不超过, i〉=1;(2）深度为h的二叉树最多有2^h—1个结点（h>=1），最少有h个结点；（3）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2,则N0=N2+1；(4）具有n个结点的完全二叉树的深度为(5）有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系: 若I为结点编号则如果I>1,则其父结点的编号为I/2;如果2*I<=N，则其左儿子(即左子树的根结点）的编号为2*I；若2＊I>N,则无左儿子；如果2＊I+1〈=N,则其右儿子的结点编号为2*I+1；若2*I+1〉N，则无右儿子。

数据结构-（严蔚敏C语⾔版）-学习、复习提纲期末复习第⼀章绪论复习1、计算机算法必须具备输⼊、输出、可⾏性、确定性、有穷性５个特性。

2、算法分析的两个主要⽅⾯是空间复杂度和时间复杂度。

3、数据元素是数据的基本单位。

数据结算法数据：计算机处理的信息总称数据项：最⼩单位数据元素：最基本单概念：数据元素之间的关系线性结构：⼀对⼀⾮线性结构树：⼀对多图：多对多顺序存储结构链表存储结构算法描述：指令的有限有有穷性确定性可⾏性时间复杂4、数据项是数据的最⼩单位。

5、数据结构是带结构的数据元素的集合。

6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。

第⼆章线性表复习1、在双链表中，每个结点有两个指针域，包括⼀个指向前驱结点的指针、⼀个指向后继结点的指针2、线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元定义节省空间随机存取插⼊3、线性表采⽤链式存储，便于进⾏插⼊和删除操作4、线性表采⽤顺序存储和链式存储优缺点⽐较。

5、简单算法第三章栈和队列复习1、栈和队列的异同点。

2、栈和队列的基本运算 3、出栈和出队 4、基本运算存储结栈的概念：在⼀端操作的线性运算算栈的特点：先进后出初始化进栈顺序队队列概念：在两端操作的线性假溢出链队列队列特点：先进先出基本运顺序：队空：队满：(1)队初始化判空进队第四章串复习第五章数组和⼴义表复习定义：由n(≥1)个字符组成的有限序列紧缩格式⾮紧缩格式以字节为单位的存储基本运(s) 串长度 (s12) 联接 (s12) ⽐较模式匹失败链接值匹配算法单字符链表串串变量的存储映像：串名、串值对应关系表顺序存储压缩存储⾏优先顺序存放列优先顺序存放稀疏矩应⽤表达式⼴义表定义：n(≥0)个元素的有限序表头：(A)= a 1 概念：长度、深度、原⼦、⼦表尾：(A)=(a23,…)表结特殊矩对称矩阵三⾓矩阵三元组存储：三元组原⼦结第六章树复习1、三个结点可以组成2种不同形态的树。

2、⼀个稀疏矩阵*n 采⽤三元组形式表⽰，若完成了其的转置运算要经过哪⼏步:⼆叉树概定义：递归定义，不为空双亲、孩⼦、叶⼦、兄弟、存储⽅顺序：满、完全⼆⼆叉树已知先根、中根序列画树；先根线索线索线索树的画法树、森林与⼆叉树的相互树、森⼆叉排树的应哈夫曼左中哈夫曼树的矩阵的⾏、列数值互换、矩阵元素所在⾏列值互换、元素在矩阵中排列的位置）重新排列3、若⼆叉树中每⼀层结点的个数都达到了最⼤，则称为⼀棵满⼆叉树。

第1章绪论1.1复习笔记一、数据结构的定义数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

二、基本概念和术语数据数据（data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，它是计算机程序加工的“原料”。

2.数据元素数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

3.数据对象数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。

4．数据结构数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。

（1）数据结构的基本结构根据数据元素之间关系的不同特性，通常有下列四类基本结构：① 集合。

数据元素之间除了“同属于一个集合”的关系外，别无其它关系。

② 线性结构。

数据元素之间存在一个对一个的关系。

③ 树形结构。

数据元素之间存在一个对多个的关系。

④ 图状结构或网状结构。

数据元素之间存在多个对多个的关系。

如图1-1所示为上述四类基本结构的关系图。

图1-1 四类基本结构的关系图（2）数据结构的形式定义数据结构的形式定义为：数据结构是一个二元组Data_Structure==（D，S）其中：D表示数据元素的有限集，S表示D上关系的有限集。

（3）数据结构在计算机中的表示数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。

它包括数据元素的表示和关系的表示。

① 元素的表示。

计算机数据元素用一个由若干位组合起来形成的一个位串表示。

② 关系的表示。

计算机中数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象。

并由这两种不同的表示方法得到两种不同的存储结构：顺序存储结构和链式存储结构。

a.顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

b.非顺序映象的特点是借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑关系。