自考02331数据结构重点总结(最终修订)
- 格式：doc
- 大小：1.61 MB
- 文档页数：21
下载文档原格式
合集下载
【2331】数据结构各章考试复习要点(打印版)
【2331】数据结构考试要点概论- 基本概念和术语（一）数据（Data）数据是信息的载体。
它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。
随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。
数据元素（Data Element）数据元素是数据的基本单位。
数据元素也称元素、结点、顶点、记录。
一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。
数据项是具有独立含义的最小标识单位。
数据结构（Data Structure）数据结构指的是数据之间的相互关系，即数据的组织形式。
1．数据结构一般包括以下三方面内容：①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。
对机器语言而言，存储结构是具体的。
一般，只在高级语言的层次上讨论存储结构。
③数据的运算，即对数据施加的操作。
数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。
最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。
所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。
只有确定了存储结构之后，才考虑如何具体实现这些运算。
为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。
【例1．1】学生成绩表，见下表。
注意：在表中指出数据元素、数据项、开始结点和终端结点等概念（1）逻辑结构表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。
自考数据结构重点知识
第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，可以由若干个数据项组成。
数据项是具有独立含义的最小标识单位。
数据结构的定义：逻辑结构：从逻辑结构上描述数据，独立于计算机。
线性结构：一对一关系。
线性结构：多对多关系。
存储结构：是逻辑结构用计算机语言的实现。
顺序存储结构：如数组。
链式存储结构：如链表。
索引存储结构：稠密索引：每个结点都有索引项。
稀疏索引：每组结点都有索引项。
散列存储结构：如散列表。
数据运算。
对数据的操作。
定义在逻辑结构上，每种逻辑结构都有一个运算集合。
常用的有：检索、插入、删除、更新、排序。
数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
原子类型：由语言提供。
结构类型：由用户借助于描述机制定义，是导出类型。
抽象数据类型ADT:是抽象数据的组织和与之的操作。
相当于在概念层上描述问题。
优点是将数据和操作封装在一起实现了信息隐藏。
程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。
算法取决于数据结构。
算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。
评价算法的好坏的因素：算法是正确的；执行算法的时间；执行算法的存储空间（主要是辅助存储空间）；算法易于理解、编码、调试。
时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。
渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。
评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。
算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n〃2)、立方阶O(n”)、……k次方阶O(n”)、指数阶O(2M)。
空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。
算法的时间复杂度和空间复杂度合称算法复杂度。
02331自考数据结构 第二章 线性表
return ;
}
if ( L -> length >= ListSize ){
printf (" overflow ");
return ;
}
for ( j - L -> length -1; j >= i -1; j --)
L ->data [ j +1]= L -> data [ j ]; //从最后一个元素开始逐一后移
线性表的基本运算
上述运算仅仅是线性表的基本运算，不是其全部运 算。因为对不同问题的线性表，所需要的运算可能不同。 因此，对于实际问题中涉及其他更为复杂的运算，可用 基本运算的组合来实现。
线性表的基本运算
【例2.1】假设有两个线性表 LA 和 LB 分别表示两个 集合 A 和 B ，现要求一个新集合 A = A∪B 。
线性表的逻辑定义
数据元素“一个接一个的排列”的关系叫做 线性关系，线性关系的特点是“一对一”，在计 算机领域用“线性表”来描述这种关系。另外， 在一个线性表中数据元素的类型是相同的，或者 说线性表是由同一类型的数据元素构成的，如学 生情况信息表是一个线性表，表中数据元素的类 型为学生类型；一个字符串也是一个线性表：表 中数据元素的类型为字符型等等。
,
a2
i
,…,
ai-1
,
a．aii++1．1 , ．…,
an
)
an
线性表n的-1逻辑结an构和存储结构都发…生了相应的变化， 与插入运算相反，插…入是向后移动元素，而删除运算则
是向前移M动AX元-1 素，除非i=n 时直接删除终端元素，不需移
动元素。
删除前
删除后
数据结构知识点总结(2023版)
数据结构知识点总结数据结构知识点总结：一、数据结构概述数据结构定义及分类●线性结构●非线性结构●数组●链表●栈●队列●树●图●散列表二、线性结构⒈数组●定义●数组的操作：插入、删除、查找、更新●二维数组⒉链表●定义●特点●单链表●双链表●循环链表●链表的操作：插入、删除、查找、更新⒊栈●定义●特点●栈的顺序存储结构●栈的链式存储结构●栈的应用⒋队列●特点●队列的顺序存储结构●队列的链式存储结构●队列的应用三、非线性结构⒈树●定义●结点●树的类型：二叉树，多叉树，满二叉树，完全二叉树●二叉树的存储结构：顺序存储，链式存储●二叉树的遍历：先序遍历，中序遍历，后序遍历●二叉树的应用：赫夫曼树，二叉搜索树⒉图●定义●图的存储结构：邻接矩阵，邻接表●图的遍历：深度优先搜索，广度优先搜索●最短路径算法四、散列表（哈希表）●定义●散列函数●冲突解决方法：拉链法，开放地质法附件：无法律名词及注释：⒈数据结构：指在计算机科学中，数据组织、管理和存储的方式。
⒉线性结构：数据元素之间存在一对一关系的结构。
⒊非线性结构：数据元素之间存在一对多或多对多关系的结构。
⒋数组：一种线性结构，由相同数据类型的元素组成，通过下标进行访问。
⒌链表：一种线性结构，由一系列结点构成，每个结点中包含数据和指向下一个结点的指针。
⒍栈：一种特殊的线性结构，只能在一端进行插入和删除操作的数据结构。
⒎队列：一种特殊的线性结构，只能在一端进行插入操作，在另一端进行删除操作的数据结构。
⒏树：一种非线性结构，由结点和边组成，每个结点可以有多个子结点。
⒐图：一种非线性结构，由一组顶点和一组边组成，顶点之间可以有多种关系。
⒑散列表：一种根据关键字直接访问数据的数据结构，通过散列函数将关键字映射到相应的存储位置。
数据结构必考知识点总结
数据结构必考知识点总结在准备考试时，了解数据结构的基本概念和相关算法是非常重要的。
以下是一些数据结构的必考知识点总结：1. 基本概念数据结构的基本概念是非常重要的，包括数据、数据元素、数据项、数据对象、数据类型、抽象数据类型等的概念。
了解这些概念有助于更好地理解数据结构的本质和作用。
2. 线性表线性表是数据结构中最基本的一种，它包括顺序表和链表两种实现方式。
顺序表是将数据元素存放在一块连续的存储空间内，而链表是将数据元素存放在若干个节点中，每个节点包含数据和指向下一个节点的指针。
了解线性表的概念和基本操作是非常重要的。
3. 栈和队列栈和队列是两种特殊的线性表，它们分别具有后进先出和先进先出的特性。
栈和队列的实现方式有多种，包括数组和链表。
掌握栈和队列的基本操作和应用是数据结构的基本内容之一。
4. 树结构树是一种非线性的数据结构，它包括二叉树、多路树、二叉搜索树等多种形式。
了解树的基本定义和遍历算法是必考的知识点。
5. 图结构图是一种非线性的数据结构，它包括有向图和无向图两种形式。
了解图的基本概念和相关算法是非常重要的，包括图的存储方式、遍历算法、最短路径算法等。
6. 排序算法排序是一个非常重要的算法问题，掌握各种排序算法的原理和实现方式是必不可少的。
常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。
7. 查找算法查找是另一个重要的算法问题，包括顺序查找、二分查找、哈希查找、树查找等。
了解各种查找算法的原理和实现方式是必考的知识点之一。
8. 算法复杂度分析算法的时间复杂度和空间复杂度是评价算法性能的重要指标，掌握复杂度分析的方法和技巧是非常重要的。
9. 抽象数据类型ADT是数据结构的一种概念模型，它包括数据的定义和基本操作的描述。
了解ADT的概念和实现方式是非常重要的。
10. 动态存储管理动态存储管理是数据结构中一个重要的问题，包括内存分配、内存释放、内存回收等。
了解动态存储管理的基本原理和实现方式是必考的知识点之一。
自学考试《数据结构》各章复习要点总结
星形测针的校正
测头的测力和测针的长度
测力影响测量精度 选择适合测针长度的测头，注意测力和测针长度（重量）的协调。 自动更换测针组的校正必须成组校正
测针长度与触发角度
测量元素的分析
单击此处添加文本具体内容
PART.02
元素的测针半径补偿
点的半径补偿方向，以坐标系的轴向和测头回退方向为准。
测量元素的分析
测针校正的方法
量块、环规、球 测头校正有多种方法：可以利用量块、环规进行测量，改变测针直径直到测量出准确结果。 最好的校正是使用标准球，既可以测准直径，又可以得出测针的位置关系。
为什么测针的等效直径小于名义值
只有接触后才能触发。 触发后的计数锁存的时间。 测量机停止时惯性。 测针变形。 测针越长，等效直径越小。 校正测针的速度要与测量速度一致。
面、线的测头补偿。 圆、圆柱、圆锥的半径补偿。 曲线、曲面的半径补偿。 测量误差和测点的数量
测量元素的分析
测量距离 小平面的距离。 测孔还是测圆柱。
坐标系
单击此处添加文本具体内容
PART.03
测量公差（如：位置度）的需要。 程序测量的需要。 准确测量的需要。 辅助测量。
零件坐标系
为什么建零件坐标系
几个难题
小圆弧
小于1/4圆，会出现很大的测量误差，分辨力、重复性原因。增加测量点。 改变方法，测量轮廓。 拟合的方法。（根据具体情况，探讨）
拟合法测量小圆弧
几个难题
同轴度
基准与被测的关系。 测量方法的限制。 按照实际使用的情况处理。
同轴度测量
窄平面的平行和垂直度 窄平面对矢量方向影响大的因素。 输入参考长度的选择。 转换测面为测线。
回转体零件坐标系
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。
测头的测力和测针的长度
测力影响测量精度 选择适合测针长度的测头，注意测力和测针长度（重量）的协调。 自动更换测针组的校正必须成组校正
测针长度与触发角度
测量元素的分析
单击此处添加文本具体内容
PART.02
元素的测针半径补偿
点的半径补偿方向，以坐标系的轴向和测头回退方向为准。
测量元素的分析
测针校正的方法
量块、环规、球 测头校正有多种方法：可以利用量块、环规进行测量，改变测针直径直到测量出准确结果。 最好的校正是使用标准球，既可以测准直径，又可以得出测针的位置关系。
为什么测针的等效直径小于名义值
只有接触后才能触发。 触发后的计数锁存的时间。 测量机停止时惯性。 测针变形。 测针越长，等效直径越小。 校正测针的速度要与测量速度一致。
面、线的测头补偿。 圆、圆柱、圆锥的半径补偿。 曲线、曲面的半径补偿。 测量误差和测点的数量
测量元素的分析
测量距离 小平面的距离。 测孔还是测圆柱。
坐标系
单击此处添加文本具体内容
PART.03
测量公差（如：位置度）的需要。 程序测量的需要。 准确测量的需要。 辅助测量。
零件坐标系
为什么建零件坐标系
几个难题
小圆弧
小于1/4圆，会出现很大的测量误差，分辨力、重复性原因。增加测量点。 改变方法，测量轮廓。 拟合的方法。（根据具体情况，探讨）
拟合法测量小圆弧
几个难题
同轴度
基准与被测的关系。 测量方法的限制。 按照实际使用的情况处理。
同轴度测量
窄平面的平行和垂直度 窄平面对矢量方向影响大的因素。 输入参考长度的选择。 转换测面为测线。
回转体零件坐标系
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。
自考02331数据结构重点总结
自考02331数据结构重点总结(最终修订)第一章概论1.瑞士计算机科学家沃思提出：算法+数据结构=程序。
算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。
由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。
2.数据是信息的载体。
数据元素是数据的基本单位。
一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。
数据对象是具有相同性质的数据元素的集合。
3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。
数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。
数据的逻辑结构分类:线性结构和非线性结构。
线性表是一个典型的线性结构。
栈、队列、串等都是线性结构。
数组、广义表、树和图等数据结构都是非线性结构。
②数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。
数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。
③数据的运算。
最常用的检索、插入、删除、更新、排序等。
4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储（1）顺序存储：通常借助程序设计语言的数组描述。
（2）链接存储：通常借助于程序语言的指针来描述。
（3）索引存储：索引表由若干索引项组成。
关键字是能唯一标识一个元素的一个或多个数据项的组合。
（4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。
5.算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。
算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。
计算机科学与技术自考本科02331自考数据结构(题库含答案)
02331数据结构一、单选题1.下列程序段的时间复杂度为( D )s=0；for(i=1；i<n ；i++)for(j=1；j<n ；j++)s+=i*j ；A.O(1)B.O(n)C.O(2n)D.O(n 2)2.假设某个带头结点的单链表的头指针为head ，则判定该表为空表的条件是( B )A.head==NULL ；B.head->next==NULL ；C.head!=NULL ；D.head->next==head ；3.栈是一种操作受限的线性结构，其操作的主要特征是( B )A.先进先出B.后进先出C.进优于出D.出优于进4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front 和rear 。
若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( B )A.(rear-front-1)％nB.(rear-front)％nC.(front-rear+1)％nD.(rear-front+n)％n5.判断两个串大小的基本准则是( D )52A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( C )A.1012B.1017C.1034D.10367.高度为5的完全二叉树中含有的结点数至少为( A )A.16B.17C.31D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( C )A.5B.8C.11D.189.下列关键字序列中，构成大根堆的是( D )A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l ，2，7D.9，8，6，7，5，1，2，310.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( B )A.1539B.1549C.1551D.155512.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的 ( A )。
自考02331数据结构真题及答案(2009-2018)
自考02331数据结构真题及答案(2009-2018)自考02331数据结构真题及答案(2009-2018)数据结构是计算机科学与技术领域中的一门基础课程，通过研究数据的组织、存储和管理方式，以及不同数据结构之间的相互关系和运算方法，提高算法效率和问题解决能力。
在自考02331数据结构课程中，真题及其答案对于学生来说是很重要的复习资料。
本文将提供自考02331数据结构真题及答案的综合整理，希望对广大自考学子的备考有所帮助。
一、2009年自考02331数据结构真题及答案1. (1) 数据除了数值外还可以是什么类型的？答：数据除了数值类型外还可以是字符型、字符串型、布尔型等。
(2) 数据的逻辑结构和物理结构分别指什么？答：数据的逻辑结构指数据之间的关系及其运算规律，如线性结构、树形结构、图形结构等；数据的物理结构指数据在计算机内存中的存储方式，如顺序存储、链式存储等。
2. 用C语言编写一个递归函数，计算n的阶乘。
答：以下是一个计算n的阶乘的递归函数的C语言代码：```cint factorial(int n) {if(n == 0 || n == 1) {return 1;}return n * factorial(n-1);}```二、2018年自考02331数据结构真题及答案1. 请给出二叉树的定义，并用C语言实现二叉树的结点结构。
答：二叉树是一种特殊的树结构，每个结点最多有两个子结点。
以下是用C语言实现二叉树结点结构的代码：```ctypedef struct BinaryNode {int data; // 结点存储的数据struct BinaryNode* left; // 左子结点指针struct BinaryNode* right; // 右子结点指针} BinaryNode;```2. 请解释线性表的顺序存储和链式存储，并分别给出其对应的存储结构。
答：线性表是一种数据元素之间存在一对一关系的数据结构。
02331数据结构
02331数据结构《02331 数据结构》在当今数字化的时代，数据结构作为计算机科学中的重要基石，对于解决各种实际问题起着至关重要的作用。
02331 数据结构这一特定的课程或者领域，涵盖了丰富而深入的知识体系，让我们一同来探索它的奥秘。
数据结构是什么？简单来说，它是组织和存储数据的方式，以便于能够高效地访问、操作和管理这些数据。
就好比我们整理自己的房间，如果东西随意堆放，找起来会非常麻烦，但如果我们把书籍放在书架上，衣服放进衣柜，杂物放进抽屉，那么就能迅速找到我们需要的东西。
在计算机中，数据结构就是为了让数据的存储和操作变得有序和高效。
在02331 数据结构中，常见的数据结构包括数组、链表、栈、队列、树和图等。
数组是一种最简单也最常见的数据结构。
它就像一排连续的格子，每个格子都有固定的位置和编号。
优点是可以通过索引快速访问元素，但缺点是插入和删除元素比较麻烦，因为可能需要移动大量的数据。
链表则与数组不同，它的元素不是连续存储的，每个元素都包含了指向下一个元素的指针。
这使得链表在插入和删除元素时非常方便，只需要修改指针的指向即可，但访问特定位置的元素就需要从头开始遍历。
栈和队列是两种特殊的线性结构。
栈遵循“后进先出”的原则，就像往一个桶里放东西，最后放进去的会最先被拿出来。
而队列则是“先进先出”，就像排队买票，先到的先买。
树是一种分层的数据结构，其中最常见的是二叉树。
二叉树的每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉搜索树则是一种特殊的二叉树，它的左子树中的节点值都小于根节点的值，右子树中的节点值都大于根节点的值。
这使得在二叉搜索树中查找、插入和删除元素的效率很高。
图是一种更为复杂的数据结构，用于表示对象之间的关系。
图由顶点和边组成，边可以有权重，表示顶点之间的连接强度或距离。
学习 02331 数据结构，不仅仅是了解这些数据结构的定义和特点，更重要的是要学会如何在实际问题中选择合适的数据结构。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
自考02331数据结构重点总结(最终修订)第一章概论1.瑞士计算机科学家沃思提出：算法+数据结构=程序。
算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。
由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。
2.数据是信息的载体。
数据元素是数据的基本单位。
一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。
数据对象是具有相同性质的数据元素的集合。
3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。
数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。
数据的逻辑结构分类:线性结构和非线性结构。
线性表是一个典型的线性结构。
栈、队列、串等都是线性结构。
数组、广义表、树和图等数据结构都是非线性结构。
②数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。
数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。
③数据的运算。
最常用的检索、插入、删除、更新、排序等。
4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储（1）顺序存储：通常借助程序设计语言的数组描述。
（2）链接存储：通常借助于程序语言的指针来描述。
（3）索引存储：索引表由若干索引项组成。
关键字是能唯一标识一个元素的一个或多个数据项的组合。
（4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。
5.算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。
算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。
目前常用的描述算法语言有两类：类Pascal和类C。
6.评价算法的优劣：算法的"正确性"是首先要考虑的。
此外，主要考虑如下三点：①执行算法所耗费的时间，即时间复杂性；②执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。
以上几点最主要的是时间复杂性，时间复杂度常用渐进时间复杂度表示。
7.算法求解问题的输入量称为问题的规模,用一个正整数n表示。
8.常见的时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(n k)、指数阶0(2n)和阶乘阶0(n!)。
9.一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数,它包括存储算法本身所占的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。
第二章线性表1.数据的运算是定义在逻辑结构上的，而运算的具体实现是在存储结构上进行的。
2.只要确定了线性表存储的起始位置，线性表中任意一个元素都可随机存取，所以顺序表是一种随机存取结构。
3.常见的线性表的基本运算:(1)置空表InitList（L）构造一个空的线性表L。
(2)求表长ListLength（L）求线性表L中的结点个数，即求表长。
(3)GetNode（L，i）取线性表L中的第i个元素。
(4)LocateNode（L，x）在L中查找第一个值为x的元素，并返回该元素在L中的位置。
若L中没有元素的值为x，则返回0值。
(5)InsertList（L，i，x）在线性表L的第i个元素之前插入一个值为x的新元素，表L的长度加1。
(6)DeleteList（L，i）删除线性表L的第i个元素，删除后表L的长度减1。
4.顺序存储方法：把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。
顺序表（SequentialList）：用顺序存储方法存储的线性表称为顺序表。
顺序表是一种随机存取结构,顺序表的特点是逻辑上相邻的结点其物理位置亦相邻。
顺序表中结点a i的存储地址:LOC（a i）=LOC（a1）+（i-1）*c 1≤i≤n，5.顺序表上实现的基本运算：（1）插入：该算法的平均时间复杂度是O(n)，即在顺序表上进行插入运算，平均要移动一半结点（n/2）。
在第i个位置插入一个结点的移动次数为n-i+1（2）删除：顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是O(n)。
删除第i个结点移动次数为n-i6.采用链式存储结构可以避免频繁移动大量元素。
一个单链表可由头指针唯一确定，因此单链表可以用头指针的名字来命名。
①生成结点变量的标准函数p=(ListNode*)malloc(sizeof(ListNode))；//函数malloc分配一个类型为ListNode 的结点变量的空间,并将其首地址放入指针变量p中②释放结点变量空间的标准函数free(p)；//释放p所指的结点变量空间③结点分量的访问方法二：p-﹥data和p-﹥next④指针变量p和结点变量*p的关系:指针变量p的值——结点地址,结点变量*p的值——结点内容7.建立单链表:（1）头插法建表：算法：p=(ListNode*)malloc(sizeof(ListNode));①//生成新结点p->data=ch;②//将读入的数据放入新结点的数据域中p->next=head;③head=p;④（2）尾插法建表：算法：p=(ListNode*)malloc(sizeof(ListNode));①//生成新结点p->data=ch; ②//将读入的数据放入新结点的数据域中if(head==NULL)head=p;//新结点插入空表elserear->next=p;③//将新结点插到*r之后rear=p;④//尾指针指向新表尾（3）尾插法建带头结点的单链表：头结点及作用：头结点是在链表的开始结点之前附加一个结点。
它具有两个优点:⒈由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;⒉无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。
头结点数据域的阴影表示该部分不存储信息。
在有的应用中可用于存放表长等附加信息。
具体算法：r=head;// 尾指针初值也指向头结点while((ch=getchar())!='\n'){s=(ListNode*)malloc(sizeof(ListNode));//生成新结点s->data=ch; //将读入的数据放入新结点的数据域中r->next=s;r=s;}r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空以上三个算法的时间复杂度均为O(n)。
8.单链表上的查找：（带头结点）（1）按结点序号查找：序号为0的是头结点。
算法：p=head;j=0;//从头结点开始扫描while(p->next&&j<i){//顺指针向后扫描，直到p->next为NULL或i=j为止p=p->next;j++;}if(i==j)returnp;//找到了第i个结点elsereturnNULL;//当i<0或i>0时，找不到第i个结点时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=O(n)（2）按结点值查找：具体算法：ListNode*p=head->next;//从开始结点比较。
表非空，p初始值指向开始结点while(p&&p->data!=key)//直到p为NULL或p->data为key为止p=p->next;//扫描下一结点returnp;//若p=NULL，则查找失败，否则p指向值为key的结点时间复杂度为：O(n)9.插入运算：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到a i-1与a i之间。
s=(ListNode*)malloc(sizeof(ListNode));②s->data=x;③s->next=p->next;④p->next=s;⑤算法的时间主要耗费在查找结点上，故时间复杂度亦为O(n)。
10.删除运算r=p->next;②//使r指向被删除的结点a i p->next=r->next③;//将a i从链上摘下free(r);④//释放结点a i的空间给存储池算法的时间复杂度也是O（n）.p指向被删除的前一个结点。
链表上实现的插入和删除运算，无须移动结点，仅需修改指针。
11.单循环链表—在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。
判断空链表的条件是head==head->next;12.仅设尾指针的单循环链表:用尾指针rear表示的单循环链表对开始结点a1和终端结点a n查找时间都是O(1)。
而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。
判断空链表的条件为rear==rear->next;13.循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。
具体算法：LinkListConnect(LinkListA,LinkListB) {//假设A，B为非空循环链表的尾指针LinkListp=A->next;//①保存A表的头结点位置A->next=B->next->next;//②B表的开始结点链接到A表尾free(B->next);//③释放B表的头结点B->next=p;//④returnB;//返回新循环链表的尾指针循环链表中没有NULL指针。
涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。
而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
14.双向链表:双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。