常用数据结构及其运算——图、算法

2007 C C C 语言的特点，简单的C 程序介绍，C 程序的上机步骤。

1 、算法的概念2、简单的算法举例3、算法的特性4、算法的表示（自然语言、流程图、N-S 图表示） 1 、 C 的数据类型、常量与变星、整型数据、实型数据、字符型数据、字符串常量。

2、 C 的运算符运算意义、优先级、结合方向。

3、算术运算符和算术表达式，各类数值型数据间的混合运算。

4、赋值运算符和赋值表达式。

5、逗号运算符和逗号表达式。

1 、程序的三种基本结构。

2、数据输入输出的概念及在C 语言中的实现。

字符数据的输入输出，格式输入与输出。

1 、关系运算符及其优先级，关系运算和关系表达式。

2、逻辑运算符及其优先级，逻辑运算符和逻辑表达式。

3、if语句。

if语句的三种形式，if语句的嵌套，条件运算符。

4、switch 语句. 1 、while 语句。

2、do/while 语句。

3、for 语句。

4、循环的嵌套。

5、break 语句和continue 语句。

1 、一维数组的定义和引用。

2、二维数组的定义和引用。

3、字符数组。

4、字符串与字符数组。

5、字符数组的输入输出。

6、字符串处理函数1 、函数的定义。

2、函数参数和函数的值，形式参数和实际参数。

3、函数的返回值。

4、函数调用的方式，函数的声明和函数原型。

5、函数的嵌套调用。

6、函数的递归调用。

7、数组作为函数参数。

8、局部变量、全局变量的作用域。

9、变量的存储类别，自动变星，静态变量。

1 、带参数的宏定义。

2、“文件包含”处理。

1 、地址和指针的概念。

2、变量的指针和指向变量的指针变量。

3、指针变量的定义和引用。

4、指针变量作为函数参数。

5、数组的指针和指向数组的指针变量。

6、指向数组元素的指针。

7、通过指针引用数组元素。

8、数组名作函数参数。

9、二维数组与指针。

1 0、指向字符串的指针变星。

字符串的指针表示形式，字符串指针作为函数参数。

11 、字符指针变量和字符数组的异同。

数据结构与算法第一节数据结构及算法概述一、数据结构图、四类基本结构的示意图【要点】 1 .数据元素是数据的基本单位。

2 .数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

3 .4类基本的规律结构:集合、线性结构、树形结构和网状结构。

4 .4种数据存储方式：挨次、链式、索引和散列。

【例题•单选题】(2022年义省信用社聘请考试真题)下列说法不正确的是()OA.数据元素是数据的基本单位B.数据项是数据中不行分割的最小标志单位 C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成『正确答案』D『答案解析』数据元素是数据的基本单位，在计算机程序中通常被作为一个整体进 行考虑和处理。

一个数据元素可由若干个数据项组成。

数据项是不行分割的、含有独立 意义的最小数据单位。

因此D 选项不正确。

二、算法O ——O ——O ——O ——O ⑹树型结构⑹线性结构 (d)图形结构算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

算法的特性：有穷性、确定性、可行性、输入和输出。

【要点】评价算法优劣标准：正确性、可读性、健壮性、高效率与低存储量需求。

其次节线性表线性表是n (n≥0)个数据元素al, a2,…，an组成的有限序列,n=0时称为空表。

非空的线性表，有以下特征：L有且仅有一个开头结点al,没有直接前趋，有且仅有一个直接后继a2。

2.有且仅有一个终结结点an,没有直接后继，有且仅有一个直接前趋a-。

3.其余的内部结点ai (2WiWnT)都有且仅有一个直接前趋a-和一个直接后继3i+ι o线性表的链式存储包括单链表、循环链表和双链表。

head 头结点百结点尾结点【留意】与单链表的插入和删除操作不同的是，在双链表中插入和删除须同时修改两个方向上的指针。

第三节栈和队列一、栈栈是一种“特别的”线性表，这种线性表中的插入和删除运算限定在表的某一端进行。

不含任何数据元素的栈称为空栈。

基本数据结构及其运算1.数组：数组是一种线性数据结构，可以存储相同类型的一组元素。

数组的特点是连续存储，可以通过索引快速访问元素。

数组的常用运算包括访问指定索引的元素、插入和删除元素等。

2.链表：链表也是一种线性数据结构，但不同于数组的连续存储，链表是由一系列节点组成的，每个节点包含元素和指向下一个节点的指针。

链表的常用运算包括在指定位置插入和删除节点、遍历链表等。

3. 栈：栈是一种后进先出（LIFO）的数据结构，用于存储和管理函数调用、表达式求值等需要按照特定顺序操作的场景。

栈的基本运算包括入栈（push）和出栈（pop）。

4. 队列：队列是一种先进先出（FIFO）的数据结构，用于存储和管理需要按照特定顺序处理的元素。

队列的基本运算包括入队列（enqueue）和出队列（dequeue）。

5.树：树是一种非线性数据结构，由一组节点和边组成，用于表示层次关系。

树的根节点是唯一的，每个非叶子节点可以有多个子节点。

树的常用运算包括遍历树（前序、中序、后序遍历）、特定节点等。

除了上述基本的数据结构，还有其它常见的数据结构如哈希表、图等。

不同的数据结构适用于不同的应用场景，具有不同的性能特点和运算复杂度。

在进行数据结构的运算时，可以使用不同的算法和技术来提高效率，常见的包括递归、迭代、排序算法、算法等。

此外，还可以使用一些高级数据结构如红黑树、堆等来优化特定的问题。

总结起来，数据结构是计算机科学中非常重要的基础概念，它提供了存储和组织数据的方法。

不同的数据结构适用于不同的应用场景，通过不同的算法和技术可以提高数据结构的运算效率。

第⼀章数据结构和算法简介—算法的时间复杂度和空间复杂度-总结算法的时间复杂度和空间复杂度-总结通常，对于⼀个给定的算法，我们要做两项分析。

第⼀是从数学上证明算法的正确性，这⼀步主要⽤到形式化证明的⽅法及相关推理模式，如循环不变式、数学归纳法等。

⽽在证明算法是正确的基础上，第⼆部就是分析算法的时间复杂度。

算法的时间复杂度反映了程序执⾏时间随输⼊规模增长⽽增长的量级，在很⼤程度上能很好反映出算法的优劣与否。

因此，作为程序员，掌握基本的算法时间复杂度分析⽅法是很有必要的。

算法执⾏时间需通过依据该算法编制的程序在计算机上运⾏时所消耗的时间来度量。

⽽度量⼀个程序的执⾏时间通常有两种⽅法。

⼀、事后统计的⽅法这种⽅法可⾏，但不是⼀个好的⽅法。

该⽅法有两个缺陷：⼀是要想对设计的算法的运⾏性能进⾏评测，必须先依据算法编制相应的程序并实际运⾏；⼆是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本⾝的优势。

⼆、事前分析估算的⽅法因事后统计⽅法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本⾝的优劣。

因此⼈们常常采⽤事前分析估算的⽅法。

在编写程序前，依据统计⽅法对算法进⾏估算。

⼀个⽤⾼级语⾔编写的程序在计算机上运⾏时所消耗的时间取决于下列因素：(1). 算法采⽤的策略、⽅法；(2). 编译产⽣的代码质量；(3). 问题的输⼊规模；(4). 机器执⾏指令的速度。

⼀个算法是由控制结构（顺序、分⽀和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。

为了便于⽐较同⼀个问题的不同算法，通常的做法是，从算法中选取⼀种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执⾏的次数作为算法的时间量度。

1、时间复杂度（1）时间频度⼀个算法执⾏所耗费的时间，从理论上是不能算出来的，必须上机运⾏测试才能知道。

但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。

1.基本数据结构与算法1.1算法算法：是指解题方案的准确而完整的描述。

特征包括：（1）可行性；（2）确定性，（3）有穷性，（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1.3线性表及其顺序存储结构非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

结点个数n称为线性表的长度，当n=0时，称为空表。

线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

顺序表的运算：插入、删除。

1.4栈和队列a）栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。

栈按照“先进后出"（FILO）或“后进先出"（LIFO）组织数据，栈具有记忆作用。

用top表示栈顶位置，用bottom表示栈底。

栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。

b）队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。

数据结构笔记基础:数据结构与算法（一）数据结构基本概念数据（data)：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称数据元素(data element）：是数据的基本单位，在计算机中通常被当做一个整体进行考虑和处理数据对象(data object）：性质相同的数据元素的集合，是数据的一个子集数据结构(data structure)：相互之间存在一种或多种特定关系的数据元素的集合4类基本结构：集合、线性结构、树形结构、图形（网状)结构数据结构的形式定义为数据结构是一个二元组Data Structure = （D,S），其中D是数据元素的有限集，S是D上关系的有限集数据结构定义中的“关系"描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构数据结构在计算机中的表示（映像)称为物理结构（存储结构）计算机中表示信息的最小单位是二进制中的一位，叫做位（bit），一到若干位组成一个位串表示一个数据元素，这个位串称为元素或结点数据结构之间关系在计算机中的表示有两种：顺序映像、非顺序映像，并由此得到两种存储结构：顺序存储、链式存储,前者运用相对位置表示数据元素间的逻辑结构，后者借助指针任何一个算法的设计取决于数据（逻辑）结构，而实现依赖于存储结构数据类型是一个值的集合和定义在这个值集上的一组操作的总称数据类型分两种:原子类型、结构类型，前者不可分解（例如int、char、float、void ），后者结构类型由若干成分按某种结构组成,可分解，成分既可以是非结构的也可以是结构的（例：数组）抽象数据类型（Abstract Data Type )：是指一个数学模型及定义在该模型上的一组操作（P8）抽象数据类型格式如下:ADT抽象数据类型名｛数据对象：<数据对象的定义>数据关系：<数据关系的定义>数据操作：〈数据操作的定义>｝ADT抽象数据类型名基本操作格式如下：基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述>多形数据类型（polymorphic data type）:是指其值得成分不确定的数据类型(P9）抽象数据类型可由固有数据类型来表示和实现（二）算法（概念）和算法分析（时、空性能）算法（algorithm）：对特定问题求解步骤的一种描述算法5特性：有穷、确定、可行、输入、输出1、有穷性:算法必须在可接受的时间内执行有穷步后结束2、确定性:每条指令必须要有确切含义，无二义性,并且只有唯一执行路径，即对相同的输入只能得相同输出3、可行性：算法中的操作都可通过已实现的基本运算执行有限次来完成4、输入：一个算法有一到多个输入，并取自某个特定对象合集5、输出：一个算法有一到多个输出，这些输出与输入有着某些特定关系的量算法设计要求(好算法）：正确性、可读性、健壮性、效率与低存储需求健壮性是指对于规范要求以外的输入能够判断出这个输入不符合规范要求，并能有合理的处理方式.算法效率的度量:（1）事后统计：程序运行结束后借助计算机内部计时功能,缺点一是必须先运行依据算法编制的程序,二是受限于计算机软硬件，导致掩盖了算法本身的优劣（2）事前分析估计：消耗时间影响因素：算法策略、问题规模、编程语言、编译程序产生的机器码质量、机器执行指令的速度撇开各种影响因素只考虑问题的规模（通常用整数量n表示），记为问题规模的函数算法时间取决于控制结构（顺序,分支，循环)和固有数据类型操作的综合效果书写格式:T（n)= O(f(n））f（n）为n的某个函数时间复杂度：算法的渐近时间复杂度(asymptotic time complexity),它表示随问题规模的增大，算法执行时间的增长率和f（n）的增长率相同以循环最深层原操作为度量基准频度：该语句重复执行的次数算法的存储空间需求：空间复杂度（space complexity）：算法所需存储空间度量，记作S（n）= O（f（n）），其中n为问题规模的大小一、线性表（一）线性表基本概念线性表（linear_list）：n个数据元素的有限序列结构特点：存在唯一的被称作“第一个”、“最后一个"的数据元素，且除了第一个以外每个元素都有唯一前驱,除最后一个以外都有唯一后继在复杂线性表中存在:数据项-〉记录-〉文件，例如每个学生情况为一个记录，它由学号、性别。

数据结构与算法教学⼤纲数据结构与算法教学⼤纲“数据结构与算法”是理论和实际紧密结合的计算机类专业核⼼⾻⼲课程，⼴泛⽤于数据存储和信息处理中。

课程将系统介绍软件开发中常⽤的数据结构、存储结构和操作算法；简要介绍算法设计与分析中的设计策略，包括贪⼼法、分治法等。

通过学习，使你能解决实际复杂⼯程问题，成为程序分析和设计“达⼈”。

课程概述数据结构是⼀门⾯向设计，且处于计算机学科核⼼地位的技术基础和主⼲必修课，也是算法分析与设计、操作系统、编译技术、计算机图形与图像处理等专业课程的先修课程。

根据学科的最新发展，对所教授课程的教学内容进⾏必要的筛选、补充、更新和重组，使其既能反映该学科领域最基本最核⼼的知识，⼜能反映该学科最新的进展和动态，注重学⽣“计算思维”能⼒和创新实践能⼒的培养，并补充了后续课程和相关领域应⽤的实例。

计算机科学的重要基⽯是算法，数据结构⼜是算法研究的基础。

将数据结构的知识和算法分析与设计的基础知识相结合，以实际的应⽤案例为驱动，将各种数据结构与算法的知识融⼊到实际问题的解决中，对相关算法的核⼼思想进⾏深⼊剖析，并总结⽐较各类算法的特点和适⽤范围，重点培养学⽣利⽤数据结构知识分析和解决实际问题的能⼒，为后继课程的学习以及从事计算机软、硬件开发⼯作打下良好的基础。

课程⼤纲第⼀章引论第1讲数据结构的基本概念-1（总时长15分18秒）第2讲数据结构的基本概念-2（总时长11分12秒）第3讲数据结构的基本概念-3（总时长10分29秒）第4讲数据的逻辑结构和存储结构（总时长11分19秒）第5讲算法及其时间复杂度（总时长14分59秒）第6讲时间复杂度及应⽤（总时长10分44秒）在线练习1单元作业1第⼆章线性表第1讲线性表的概念及顺序存储（总时长17分44秒）第2讲单链表的概念及其基本操作（总时长12分27秒）第3讲建⽴单链表（总时长13分45秒）第4讲循环链表（总时长14分45秒）第5讲双向链表（总时长16分01秒）第6讲⼀元多项式的表⽰和运算（总时长16分08秒）实验内容单元作业2在线练习2第三章栈和队列第1讲栈的概念及其基本操作（总时长13分06秒）第2讲栈的概念及其基本操作—双端栈（总时长12分10秒）第3讲栈的应⽤—递归及汉诺塔问题（总时长16分27秒）第4讲栈的应⽤—迷宫实验（总时长07分40秒）第5讲队列的概念及基本操作（总时长16分31秒）第6讲队列的概念及应⽤—链队列（总时长11分10秒）第7讲表达式的求值问题（总时长15分01秒）第8讲递归与分治算法（总时长12分06秒）实验内容单元测试1单元作业3第四章串第1讲串的基本操作（总时长09分34秒）第2讲串的简单模式匹配（总时长13分18秒）第3讲串的KMP模式匹配算法（总时长09分15秒）第4讲模式串的next值计算思想（总时长07分52秒）第5讲模式串的next值计算实现（总时长08分19秒）第6讲模式串的nextval值（总时长11分57秒）单元作业4在线练习4综合实验剖析-马踏棋盘第1讲马踏棋盘1（总时长11分31秒）第2讲马踏棋盘2（总时长10分42秒）第五章多维数组和⼴义表第1讲数组的定义与顺序存储（总时长12分25秒）第2讲矩阵的压缩存储（总时长11分03秒）第3讲三元组矩阵的快速转置（总时长12分18秒）第4讲⼴义表（总时长11分53秒）实验内容在线练习5单元作业5课程习题解析（前三章）第1讲习题讲解1（引论，总时长08分50秒）第2讲习题讲解2（线性表，总时长10分37秒）第3讲习题讲解3（栈和队列，总时长09分54秒）第六章树第1讲⼆叉树的性质（总时长14分00秒）第2讲⼆叉树的顺序存储（总时长09分21秒）第3讲⼆叉树的遍历（总时长17分11秒）第4讲统计叶⼦结点（总时长06分02秒）第5讲计算⼆叉树的⾼度（总时长05分54秒）第6讲⼆叉树的恢复建⽴（总时长12分02秒）第7讲⼆叉树的⾮递归遍历（总时长13分19秒）第8讲线索⼆叉树（总时长12分00秒）第9讲线索⼆叉树的遍历（总时长10分57秒）第10讲树和森林（总时长12分21秒）第11讲树与森林的遍历（总时长11分22秒）第12讲哈夫曼树（总时长12分48秒）第13讲哈夫曼编译码（总时长12分48秒）第14讲哈夫曼编码算法（总时长09分30秒）第15讲解空间树及其相关算法（总时长11分37秒）实验内容单元测试2课程习题解析（第四章、第五章）第4讲习题讲解4（串，总时长09分41秒)第5讲习题讲解5（多维数组和⼴义表，总时长09分20秒）综合实验剖析-⽂件解压缩第3讲⽂件压缩（总时长13分34秒）第4讲⽂件解压（总时长09分04秒）第七章图第1讲图的基本概念（总时长13分33秒）第2讲图的存储（总时长15分27秒）第3讲图的深度优先遍历（总时长13分05秒第4讲图的⼴度优先遍历（总时长07分40秒）第5讲图的最⼩⽣成树-Prim算法思想（总时长11分40秒）第6讲图的最⼩⽣成树-Prim算法实现（总时长11分21秒）第7讲图的最⼩⽣成树-Kruskal算法（总时长09分25秒）第8讲图的拓扑排序思想（总时长10分38秒）第9讲图的拓扑排序实现（总时长09分35秒）第10讲图的关键路径思想（总时长12分26秒）第11讲图的关键路径实现（总时长07分19秒）第12讲图的单源最短路径-Dijkstra思想（总时长10分27秒）第13讲图的单源最短路径-Dijkstra实现（总时长07分39秒）第14讲贪⼼算法（总时长12分48秒）实验内容在线练习7单元作业7课程习题解析-⾮线性结构（第六章、第七章）第6讲习题讲解6（树，总时长07分52秒）第7讲习题讲解7（图，总时长09分25秒）第⼋章查找第1讲顺序查找（总时长10分21秒）第2讲折半查找（总时长12分07秒）第3讲⼆叉排序树的基本概念与查找（总时长10分00秒）第4讲⼆叉排序树的插⼊与⽣成（总时长09分05秒）第5讲⼆叉排序树的删除（总时长13分21秒）第6讲哈希表基本概念（总时长09分41秒）第7讲哈希函数（总时长08分30秒）第8讲哈希处理冲突（总时长13分58秒）实验内容在线练习8单元作业8第九章排序第1讲排序基本概念（总时长04分59秒）第2讲直接插⼊排序（总时长11分08秒）第3讲希尔排序（总时长10分43秒）第4讲冒泡排序（总时长09分31秒）第5讲快速排序（总时长13分22秒）第6讲选择排序（总时长08分45秒）第7讲树形排序（总时长08分01秒）第8讲堆排序（总时长15分54秒）第9讲归并排序（总时长08分15秒）第10讲基数排序（总时长11分45秒）在线练习9综合实验剖析-校园导游图第5讲校园导游图（总时长12分37秒）栈的经典案例递归算法（总时长14分39秒）迷宫问题（总时长11分49秒）课程习题解析-相关技术（第⼋章、第九章）第8讲习题讲解8（查找，总时长10分41秒）第9讲习题讲解9（排序，总时长10分27秒）预备知识⾼级语⾔程序设计。