2021年自学考试数据结构重点总结02331整理
- 格式：doc
- 大小：1.60 MB
- 文档页数：28
下载文档原格式
合集下载
【2331】数据结构各章考试复习要点(打印版)
【2331】数据结构考试要点概论- 基本概念和术语（一）数据（Data）数据是信息的载体。
它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。
随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。
数据元素（Data Element）数据元素是数据的基本单位。
数据元素也称元素、结点、顶点、记录。
一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。
数据项是具有独立含义的最小标识单位。
数据结构（Data Structure）数据结构指的是数据之间的相互关系，即数据的组织形式。
1．数据结构一般包括以下三方面内容：①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。
对机器语言而言，存储结构是具体的。
一般，只在高级语言的层次上讨论存储结构。
③数据的运算，即对数据施加的操作。
数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。
最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。
所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。
只有确定了存储结构之后，才考虑如何具体实现这些运算。
为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。
【例1．1】学生成绩表，见下表。
注意：在表中指出数据元素、数据项、开始结点和终端结点等概念（1）逻辑结构表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。
全国2021年10月数据结构试题及答案
全国2021年10月数据结构试题及答案课程代码：02331第一部份选择题(30分)一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。
1．算法指的是（）A．计算机程序 B．解决问题的计算方式C．排序算法 D．解决问题的有限运算序列2．线性表采用链式存储时，结点的存储地址（）A．必需是不持续的B．持续与否都可C．必需是持续的D．和头结点的存储地址相持续3．将长度为n的单链表链接在长度为m的单链表以后的算法的时间复杂度为（） A．O（1） B．O（n） C．O（m） D．O（m+n）4．由两个栈共享一个向量空间的益处是：（）A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front=(front+1)%(m-1)C．front=(front-1)%m D．front=(front+1)%m6．如下陈述中正确的是（）A．串是一种特殊的线性表 B．串的长度必需大于零C．串中元素只能是字母 D．空串就是空白串7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（）A．O（） B．O（n） C．O（n2） D．O（n3）8．一个非空广义表的表头（）A．不可能是子表 B．只能是子表C．只能是原子 D．可以是子表或原子9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表0 2 3 3 5对应的稀疏矩阵是（）10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )A．4 B．5 C．6 D．711．在含n个极点和e条边的无向图的邻接矩阵中,零元素的个数为( )A．e B．2e C．n2－e D．n2－2e12．假设一个有n个极点和e条弧的有向图用邻接表表示,则删除与某个极点vi相关的所有弧的时间复杂度是( )A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某种排序方式对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的转变情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方式是（）A．选择排序 B．希尔排序 C．归并排序 D．快速排序14．适于对动态查找表进行高效率查找的组织结构是（）A．有序表 B．分块有序表 C．三叉排序树 D．线性链表15．不定长文件是指（）A．文件的长度不固定 B．记录的长度不固定C．字段的长度不固定 D．关键字项的长度不固定第二部份非选择题（共70分）二、填空题（本大题共10小题，每小题2分，如有两个空格，每一个空格1分，共20分）不写解答进程，将正确的答案写在每小题的空格内。
数据结构知识点整理
数据结构知识点整理第一点：数据结构的基本概念与类型数据结构是计算机科学中的一个重要分支，它研究的是如何有效地存储、组织和管理数据，以便于计算机可以高效地进行数据的读取、插入、删除等操作。
数据结构的基本概念主要包括两个方面：数据的逻辑结构与数据的物理结构。
1.1 数据的逻辑结构数据的逻辑结构主要描述数据的逻辑关系，不涉及数据的存储方式。
常见的逻辑结构有：•线性结构：如线性表、栈、队列、串等。
线性结构的特点是数据元素之间存在一对一的关系，每个数据元素只有一个直接前驱和一个直接后继。
•非线性结构：如树、图等。
非线性结构的特点是数据元素之间存在一对多或者多对多的关系。
其中，树结构是一种重要的非线性结构，它具有层次性，每个数据元素（树节点）有零个或多个子节点。
1.2 数据的物理结构数据的物理结构主要描述数据在计算机内存中的存储方式，它直接影响了计算机对数据的访问效率。
常见的物理结构有：•顺序存储结构：如数组、链表等。
顺序存储结构将数据元素按照一定的顺序存放在计算机内存中，相邻的数据元素在内存中也是相邻的。
•链式存储结构：如单链表、双向链表、循环链表等。
链式存储结构通过指针将不连续的数据元素连接起来，每个数据元素只存储数据本身以及指向下一个数据元素的指针。
1.3 数据结构的应用场景不同的数据结构适用于不同的应用场景。
例如：•线性表：适用于顺序访问数据元素的场景，如学生成绩管理系统。
•栈和队列：适用于后进先出（LIFO）或先进先出（FIFO）的场景，如表达式求值、任务调度等。
•树结构：适用于具有层次关系的数据组织，如文件系统的目录结构、HTML文档的DOM树等。
•图结构：适用于表示复杂的关系，如社交网络、交通网络等。
第二点：常见数据结构算法与应用在计算机科学中，算法是解决问题的一系列清晰指令。
结合数据结构，算法可以有效地解决实际问题。
以下是一些常见的数据结构及其相关算法与应用。
2.1 线性表的算法与应用线性表是最基本的逻辑结构。
自学考试《数据结构》各章复习要点总结
星形测针的校正
测头的测力和测针的长度
测力影响测量精度 选择适合测针长度的测头，注意测力和测针长度（重量）的协调。 自动更换测针组的校正必须成组校正
测针长度与触发角度
测量元素的分析
单击此处添加文本具体内容
PART.02
元素的测针半径补偿
点的半径补偿方向，以坐标系的轴向和测头回退方向为准。
测量元素的分析
测针校正的方法
量块、环规、球 测头校正有多种方法：可以利用量块、环规进行测量，改变测针直径直到测量出准确结果。 最好的校正是使用标准球，既可以测准直径，又可以得出测针的位置关系。
为什么测针的等效直径小于名义值
只有接触后才能触发。 触发后的计数锁存的时间。 测量机停止时惯性。 测针变形。 测针越长，等效直径越小。 校正测针的速度要与测量速度一致。
面、线的测头补偿。 圆、圆柱、圆锥的半径补偿。 曲线、曲面的半径补偿。 测量误差和测点的数量
测量元素的分析
测量距离 小平面的距离。 测孔还是测圆柱。
坐标系
单击此处添加文本具体内容
PART.03
测量公差（如：位置度）的需要。 程序测量的需要。 准确测量的需要。 辅助测量。
零件坐标系
为什么建零件坐标系
几个难题
小圆弧
小于1/4圆，会出现很大的测量误差，分辨力、重复性原因。增加测量点。 改变方法，测量轮廓。 拟合的方法。（根据具体情况，探讨）
拟合法测量小圆弧
几个难题
同轴度
基准与被测的关系。 测量方法的限制。 按照实际使用的情况处理。
同轴度测量
窄平面的平行和垂直度 窄平面对矢量方向影响大的因素。 输入参考长度的选择。 转换测面为测线。
回转体零件坐标系
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。
测头的测力和测针的长度
测力影响测量精度 选择适合测针长度的测头，注意测力和测针长度（重量）的协调。 自动更换测针组的校正必须成组校正
测针长度与触发角度
测量元素的分析
单击此处添加文本具体内容
PART.02
元素的测针半径补偿
点的半径补偿方向，以坐标系的轴向和测头回退方向为准。
测量元素的分析
测针校正的方法
量块、环规、球 测头校正有多种方法：可以利用量块、环规进行测量，改变测针直径直到测量出准确结果。 最好的校正是使用标准球，既可以测准直径，又可以得出测针的位置关系。
为什么测针的等效直径小于名义值
只有接触后才能触发。 触发后的计数锁存的时间。 测量机停止时惯性。 测针变形。 测针越长，等效直径越小。 校正测针的速度要与测量速度一致。
面、线的测头补偿。 圆、圆柱、圆锥的半径补偿。 曲线、曲面的半径补偿。 测量误差和测点的数量
测量元素的分析
测量距离 小平面的距离。 测孔还是测圆柱。
坐标系
单击此处添加文本具体内容
PART.03
测量公差（如：位置度）的需要。 程序测量的需要。 准确测量的需要。 辅助测量。
零件坐标系
为什么建零件坐标系
几个难题
小圆弧
小于1/4圆，会出现很大的测量误差，分辨力、重复性原因。增加测量点。 改变方法，测量轮廓。 拟合的方法。（根据具体情况，探讨）
拟合法测量小圆弧
几个难题
同轴度
基准与被测的关系。 测量方法的限制。 按照实际使用的情况处理。
同轴度测量
窄平面的平行和垂直度 窄平面对矢量方向影响大的因素。 输入参考长度的选择。 转换测面为测线。
回转体零件坐标系
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。
数据结构考试重点必背
：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。
：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。
数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。
数据项：是数据元素中有独立含义的、不可分割的最小标识单位。
数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。
数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。
：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。
数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。
：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。
算法规则需满足以下五个特性：输入——算法有零个或多个输入数据。
输出——算法有一个或多个输出数据，与输入数据有某种特定关系。
有穷性——算法必须在执行又穷步之后结束。
确定性——算法的每个步骤必须含义明确，无二义性。
可行性——算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。
有穷性和可行性是算法最重要的两个特征。
：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。
算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。
：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。
健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结高时间效率：算法的执行时间越短，时间效率越高。
果。
高空间效率：算法执行时占用的存储空间越少，空间效率越高。
可读性：算法的可读性有利于人们对算法的理解。
：度量算法的时间效率，时间复杂度，（课本39页）。
：递归定义：即用一个概念本身直接或间接地定义它自己。
数据结构知识点总结
数据结构知识点总结在计算机科学中，数据结构是一门非常重要的基础学科，它研究的是数据的组织、存储和管理方式，以及如何对这些数据进行高效的操作和处理。
下面就让我们一起来梳理一下数据结构中的一些关键知识点。
一、线性表线性表是最基本的数据结构之一，它是由零个或多个数据元素组成的有限序列。
线性表有两种常见的实现方式：顺序表和链表。
顺序表是将数据元素存储在一段连续的内存空间中，通过数组来实现。
顺序表的优点是可以随机访问任意元素，时间复杂度为 O(1)；缺点是插入和删除操作需要移动大量元素，时间复杂度为 O(n)。
链表则是通过指针将各个数据元素链接起来，不要求内存连续。
链表分为单链表、双链表和循环链表等。
链表的优点是插入和删除操作方便，只需修改指针，时间复杂度为 O(1)；缺点是不能随机访问，需要从头开始遍历，时间复杂度为 O(n)。
二、栈和队列栈是一种特殊的线性表，它遵循“后进先出”（Last In First Out，LIFO）的原则。
可以将栈想象成一个只有一端开口的桶，先放入的元素被压在底部，后放入的元素在顶部，取出元素时只能从顶部取出。
栈的常见操作有入栈（push）和出栈（pop）。
队列则是遵循“先进先出”（First In First Out，FIFO）原则的线性表。
就像排队买票一样，先到的人先得到服务。
队列的常见操作有入队（enqueue）和出队（dequeue）。
三、数组和字符串数组是一种顺序存储的线性表，它的元素类型相同，并且存储在连续的内存空间中。
数组可以通过下标快速访问元素，但插入和删除操作的效率较低。
字符串是由字符组成的数组，在处理字符串时，常常需要进行字符串的比较、查找、拼接等操作。
常见的字符串算法有字符串匹配算法（如暴力匹配、KMP 算法等）。
四、树树是一种非线性的数据结构，它由节点和边组成。
常见的树结构有二叉树、二叉搜索树、AVL 树、红黑树等。
二叉树每个节点最多有两个子节点，分别称为左子节点和右子节点。
数据结构重点整理
数据结构重点整理简介数据结构是计算机科学中的重要概念，指的是组织和存储数据的方式。
本文整理了数据结构的重点内容，包括以下章节：1. 数组2. 链表3. 栈4. 队列5. 树6. 图7. 哈希表8. 堆9. 排序算法10. 查找算法1. 数组1.1 定义和基本操作- 数组是一种线性数据结构，用于存储一组相同类型的元素。
每个元素可以通过索引访问。
- 基本操作包括：创建数组、访问元素、修改元素、插入元素、删除元素、获取数组长度等。
1.2 复杂度分析- 时间复杂度：对于不同操作，如访问、插入、删除等，时间复杂度可能不同。
- 空间复杂度：数组的存储空间通常为固定大小，空间复杂度为O(n)。
2. 链表2.1 定义和基本操作- 链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
- 基本操作包括：创建链表、插入节点、删除节点、访问节点、反转链表等。
2.2 复杂度分析- 时间复杂度：链表的操作时间复杂度与操作位置有关，访问节点的时间复杂度为O(n)。
- 空间复杂度：链表的空间复杂度为O(n)。
3. 栈3.1 定义和基本操作- 栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
- 基本操作包括：入栈、出栈、获取栈顶元素、判断栈是否为空等。
3.2 应用场景- 括号匹配- 表达式求值- 浏览器的前进和后退功能4. 队列4.1 定义和基本操作- 队列是一种先进先出（FIFO）的数据结构，可以在队尾插入元素，在队头删除元素。
- 基本操作包括：入队、出队、获取队头元素、判断队列是否为空等。
4.2 应用场景- 广度优先搜索（BFS）- 缓存5. 树5.1 定义和基本操作- 树是一种非线性数据结构，由节点和边组成，每个节点可以有多个子节点。
- 基本操作包括：创建树、插入节点、删除节点、遍历树等。
5.2 常见的树结构- 二叉树：每个节点最多有两个子节点。
- 二叉搜索树：左子树的键值小于根节点，右子树的键值大于根节点。
自考02331数据结构重点总结
自考02331数据结构重点总结(最终修订)第一章概论1.瑞士计算机科学家沃思提出：算法+数据结构=程序。
算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。
由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。
2.数据是信息的载体。
数据元素是数据的基本单位。
一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。
数据对象是具有相同性质的数据元素的集合。
3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。
数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。
数据的逻辑结构分类:线性结构和非线性结构。
线性表是一个典型的线性结构。
栈、队列、串等都是线性结构。
数组、广义表、树和图等数据结构都是非线性结构。
②数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。
数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。
③数据的运算。
最常用的检索、插入、删除、更新、排序等。
4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储（1）顺序存储：通常借助程序设计语言的数组描述。
（2）链接存储：通常借助于程序语言的指针来描述。
（3）索引存储：索引表由若干索引项组成。
关键字是能唯一标识一个元素的一个或多个数据项的组合。
（4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。
5.算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。
算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。
数据结构重点整理
数据结构重点整理数据结构是计算机科学中的重要基石，它对于高效地存储、组织和处理数据起着关键作用。
接下来，让我们一同深入探讨数据结构中的一些重点内容。
首先，我们来谈谈数组。
数组是一种最简单、最基本的数据结构。
它是一组相同类型元素的有序集合，通过下标可以快速访问其中的元素。
数组的优点在于访问元素的时间复杂度为 O(1)，也就是说，无论数组的大小如何，只要知道元素的下标，就能在恒定的时间内获取到对应的值。
但数组的缺点也很明显，它的长度是固定的，一旦创建就无法改变，如果需要添加或删除元素，可能会比较麻烦。
链表则与数组不同。
链表中的元素在内存中不是连续存储的，而是通过指针相互连接。
链表分为单向链表、双向链表和循环链表等。
链表的优点是添加和删除元素相对容易，只需要修改指针即可，时间复杂度通常为 O(1)。
但访问链表中的元素就没有数组那么高效了，需要从头节点开始遍历，时间复杂度为 O(n)。
栈是一种特殊的线性表，它遵循“后进先出”的原则。
就像往一个桶里放东西，最后放进去的会最先被拿出来。
栈的应用非常广泛，比如函数调用时的栈帧、表达式求值等。
队列则是遵循“先进先出”原则的线性表，就像排队买东西，先到的先服务。
队列在很多场景中也有重要作用，比如操作系统中的任务调度、网络中的数据包传输等。
接下来是树结构。
二叉树是树结构中最常见的一种。
每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉搜索树是一种特殊的二叉树，它的左子节点的值小于父节点的值，右子节点的值大于父节点的值。
这样的特性使得在二叉搜索树中查找、插入和删除元素的平均时间复杂度为 O(log n)。
平衡二叉树则是对二叉搜索树的一种优化，通过自动调整树的结构，保持树的高度平衡，从而提高操作的效率。
此外，还有堆这种数据结构。
堆分为最大堆和最小堆。
最大堆中，每个节点的值都大于或等于其子节点的值；最小堆则相反，每个节点的值都小于或等于其子节点的值。
堆常用于实现优先队列，能够快速获取到最大或最小元素。
自考数据结构重点(珍藏版)
自考数据结构重点(珍藏版)自考数据结构重点(珍藏版)一、介绍数据结构是计算机科学中非常重要的概念，它涉及到组织、管理和存储数据的方法。
掌握数据结构的核心概念对于程序设计和算法的实现至关重要。
本文将介绍自考数据结构课程的重点内容，帮助您更好地理解和应用这些知识。
二、线性表1. 数组数组是最简单的一种数据结构，它是一种线性表的结构，其中的元素按照一定顺序排列。
我们可以通过数组下标来访问和修改对应位置的元素。
2. 链表链表是另一种常用的线性表结构，它由一系列节点组成。
每个节点包含数据和指向下一个节点的指针。
链表的优点是插入和删除操作的效率较高，但访问任意位置的元素需要遍历整个链表。
三、栈和队列1. 栈栈是一种具有后进先出（LIFO）特点的数据结构，主要包含入栈和出栈两种操作。
入栈将元素压入栈顶，出栈将栈顶元素移除。
2. 队列队列是一种具有先进先出（FIFO）特点的数据结构，主要包含入队和出队两种操作。
入队将元素插入队尾，出队将队头元素移除。
四、树树是一种自然且常用的数据结构，它具有层次结构和分支结构的特点。
1. 二叉树二叉树是树结构中最简单且常见的一种形式。
每个节点最多有两个子节点，分别是左子节点和右子节点。
2. 二叉搜索树二叉搜索树是一种特殊的二叉树，它的左子树中的值都小于根节点，右子树中的值都大于根节点。
这个特点使得二叉搜索树在查找和插入操作上有较高的效率。
五、图图是一种非线性的数据结构，它由节点和边组成。
图的节点可以表示不同的实体，边表示节点之间的联系。
1. 有向图和无向图有向图中的边有方向性，而无向图中的边没有方向性。
2. 最短路径算法最短路径算法用于计算两个节点之间的最短路径长度。
常见的最短路径算法包括迪杰斯特拉算法和弗洛伊德算法。
六、排序算法排序算法用于将一组数据按照特定顺序进行排列。
1. 冒泡排序冒泡排序通过交换相邻的元素来进行排序。
它重复地遍历数列，每次比较相邻的两个元素，将较大的元素移动到后面。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
自考数据构造重点（整顿）第一章概论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.顺序存储办法：把线性表数据元素按逻辑顺序依次存储在一组地址持续存储单元里办法。
顺序表（Sequential List）：用顺序存储办法存储线性表称为顺序表。
顺序表是一种随机存取构造,顺序表特点是逻辑上相邻结点其物理位置亦相邻。
5.顺序表上实现基本运算：（1）插入：该算法平均时间复杂度是O(n)，即在顺序表上进行插入运算，平均要移动一半结点（n/2）。
（2）删除：顺序表上做删除运算，平均要移动表中约一半结点（n-1）/2，平均时间复杂度也是O(n)。
6.采用链式存储构造可以避免频繁移动大量元素。
一种单链表可由头指针唯一拟定，因而单链表可以用头指针名字来命名。
①生成结点变量原则函数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)return p;//找到了第i个结点else return NULL;//当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;//扫描下一结点return p;//若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 ip->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)。
详细算法：LinkList Connect(LinkList A,LinkList B) {//假设A，B为非空循环链表尾指针LinkList p=A->next;//①保存A表头结点位置A->next=B->next->next;//②B表开始结点链接到A表尾free(B->next);//③释放B表头结点B->next=p;//④return B;//返回新循环链表尾指针循环链表中没有NULL指针。
涉及遍历操作时，其终结条件就不再是像非循环链表那样鉴别p或p-＞next与否为空，而是鉴别它们与否等于某一指定指针，如头指针或尾指针等。
在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前其他结点。
而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一长处使某些运算在单循环链表上易于实现。
14.双向链表：双（向）链表中有两条方向不同链，即每个结点中除next域存储后继结点地址外，还增长一种指向其直接前趋指针域prior。
①双链表由头指针head惟一拟定。
②带头结点双链表某些运算变得以便。
③将头结点和尾结点链接起来，为双（向）循环链表。
15.双向链表前插和删除本结点操作①双链表前插操作void DInsertBefore(DListNode *p,DataType x){//在带头结点双链表中，将值为x新结点插入*p之前，设p≠NULL DListNode *s=malloc(sizeof(DListNode));//①s->data=x;//②s->prior=p->prior;//③s->next=p;//④p->prior->next=s;//⑤p->prior=s;//⑥}②双链表上删除结点*p自身操作void DDeleteNode(DListNode *p){//在带头结点双链表中，删除结点*p，设*p为非终端结点p->prior->next=p->next;//①p->next->prior=p->prior;//②free(p);//③}与单链表上插入和删除操作不同是，在双链表中插入和删除必要同步修改两个方向上指针。