数据结构导论串讲笔记

数据结构详细笔记数据结构是计算机科学中非常重要的一个概念，它可以帮助我们更有效地组织和管理数据。

在本文中，我将详细介绍各种常见的数据结构及其特点和应用场景。

一、线性表线性表是最简单也是最常见的数据结构之一。

它是由一系列具有相同类型的元素组成的序列，其中每个元素都有一个前驱元素和一个后继元素，除了第一个元素没有前驱元素，最后一个元素没有后继元素。

常见的线性表有数组、链表和栈。

1. 数组数组是一种在内存中连续存储的数据结构，可以通过下标来访问其中的元素。

它的优点是访问速度快，缺点是插入和删除操作比较慢。

2. 链表链表是通过指针将一组零散的内存块连接起来形成的数据结构，它的节点可以不连续存储。

链表的优点是插入和删除操作比较快，缺点是访问速度相对较慢。

3. 栈栈是一种后进先出（LIFO）的线性表，它只允许在表的一端进行插入和删除操作。

常见的应用场景有函数调用、括号匹配等。

二、队列队列是一种先进先出（FIFO）的线性表，类似于现实生活中的排队。

它有两个指针，分别指向队头和队尾。

常见的队列有普通队列、双端队列和优先队列。

1. 普通队列普通队列是最基本的队列形式，只能在队头删除元素，在队尾插入元素。

常见的应用场景有任务调度、消息队列等。

2. 双端队列双端队列是允许从两端插入和删除元素的队列。

它可以作为栈和队列的结合体，常见的应用场景有回文判断、迷宫问题等。

3. 优先队列优先队列是一种按照元素优先级进行插入和删除操作的队列。

常见的应用场景有任务调度、图像压缩等。

三、树树是一种非线性的数据结构，它由若干个具有层次关系的节点组成。

树的每个节点可以有多个子节点，但每个子节点只能有一个父节点。

常见的树有二叉树、二叉搜索树和平衡树。

1. 二叉树二叉树是每个节点最多有两个子节点的树结构。

它的遍历方式有前序遍历、中序遍历和后序遍历。

常见的应用场景有表达式计算、文件系统等。

2. 二叉搜索树二叉搜索树是一种特殊的二叉树，它的左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。

数据结构串、数组和广义表知识点总结
数据结构是计算机科学中研究数据如何组织、存储、管理和操作的学科。

三个常见的数据结构串、数组和广义表都是用于存储和操作数据的。

1. 串：
- 串是由0个或多个字符组成的有限序列。

它是一维数组的特例。

- 串的操作包括插入、删除、修改和查找等常见操作。

- 串可以通过数组、链表或动态分配的内存来实现。

2. 数组：
- 数组是一种线性数据结构，它由一组连续的内存空间组成，
存储相同类型的数据。

- 数组的操作包括插入、删除、修改和查找等常见操作。

- 数组的访问时间复杂度为O(1)，但插入和删除的时间复杂度
较高。

3. 广义表：
- 广义表是由若干元素组成的有序集合，每个元素可以是原子
或者是一个广义表。

- 广义表可以通过链表来实现，每个节点包含两个指针，一个
指向元素，一个指向下一个节点。

- 广义表的操作包括插入、删除、修改和查找等常见操作。

- 广义表可以表示任意层次的嵌套结构，具有灵活性和扩展性。

总结：
- 串、数组和广义表都是常见的数据结构，用于存储和操作数据。

- 串是字符的有限序列，可以通过数组或链表来实现。

- 数组是一维线性数据结构，存储相同类型的数据，具有常数时间复杂度的访问操作。

- 广义表是由元素组成的有序集合，可以通过链表来实现，能够表示任意层次的嵌套结构。

数据结构高分笔记
数据结构是计算机科学中非常重要的一个领域，其目的是使计算机能够高效地处理数据。

数据结构包括数据的存储结构和数据之间的关系，其中数据的存储结构是指数据在计算机中的表现形式，而数据之间的关系则是指数据之间的关联和相互作用。

在数据结构中，常见的数据结构包括线性表、栈、队列、树、图等等。

其中，线性表是一种常见的数据结构，它的特点是支持常见的操作，如插入、删除、查找等等。

栈和队列是线性表的特殊形式，它们支持一些特殊的操作，如入栈、出栈、前驱、后继等等。

树和图则是更加复杂的数据结构，它们可以用来表示各种类型的数据，如层次结构、图形等等。

数据结构的学习需要扎实的数学基础和敏锐的逻辑思考能力。

在学习数据结构的过程中，不仅要掌握数据结构和算法的基本概念和原理，还需要熟练掌握一些经典的算法和数据结构，如二叉树、排序算法、哈希表等等。

同时，还需要不断地实践和探索，通过不断地练习和实践，加深对数据结构和算法的理解。

数据结构是计算机科学中非常重要的一个领域，对于从事计算机科学和软件开发等领域的学生和从业者来说，掌握数据结构和算法是非常重要的。

通过不断地学习和实践，才能够更好地理解和应用数据结构和算法，提高编程效率和代码质量。

张东1145105494简介：1、算法+数据结构=程序2、数据结构3、数据、数据元素（基本单位）、数据项（最小单位）4、数据结构在计算机中的映像是存储结构；数据元素在计算机中的映像是结点；数据项在计算机中的映像是数据域；逻辑结构在计算机中的映像是关系。

5、四种存储方式6、抽象数据类型1）按不同特性分类●原子类型●固定聚合类型●可变聚合类型2）基本操作●init 构造●destroy 销毁●get 返回●put 改变●isasc 升序●isdesc 降序●Max 最大●min 最小7、时间复杂度技巧1）对于循环程序（for），最大执行次数即为for的乘积。

简言之，程序有多少for出现，就是n的多少次方2）对于顺序结构，可用“求和取最大值“法则3）对于循环程序（while），一般结果是O(log M N)4）若是一般的赋值语句，时间复杂度必为O(1)5）对于选择结构的程序，一般时间复杂度为O(1)加：自加自减++ ——x=2；y=x++;y=++x;第二章线性表1、表长相当于元素个数2、线性表一般下标是1—n，故当n=0时，表示线性表为空表3、list 表示线性表elem 元素length 表示求长度（线性表）locate 定位（位置）insert 插入（元素之前）delete 删除void 空类型（写程序必写）顺序结构（链表相反）优势：随机存取劣势：在做插入或删除时需要移动大量的元素malloc 分配一个连续空间realloc 将已分配的空间进行重新分配顺序表插入时所需移动的元素次数期望值是n/2删除时所需移动的元素次数期望值是（n-1）/2删除：模板语句：q=&(L.elem[i-1]) 表示顺序表中插入元素或者删除元素的地址加：逻辑运算符：！非&&与（一假即假）||或（一真即真）逻辑值：真（1）假（0）比较运算符：< >= <= == !=若在if或者while后面的括号中出现逻辑表达式或者比较表达式，那么结果只能为真或假。

数据结构与算法笔记数据结构与算法笔记一、数据结构数据结构是计算机程序设计中非常重要的一个概念，它是指一组数据的组织方式。

常见的数据结构有链表、栈、队列、树、图等。

1.链表链表是一种动态数据结构，它由节点组成，每个节点包含数据和指向下一个节点的引用。

链表可以分为单向链表、双向链表和循环链表。

2.栈栈是一种先进后出的数据结构，它只支持在栈顶进行插入、删除和读取操作。

栈可以用数组或链表实现。

3.队列队列是一种先进先出的数据结构，它支持在队尾插入元素，在队头删除元素和对头元素进行读取操作。

队列可以用数组或链表实现。

4.树树是一种非线性数据结构，它由节点和边组成。

树的节点包含数据和指向它的子节点或父节点的引用。

常见的树有二叉树、二叉搜索树和AVL树等。

5.图图是一种非线性数据结构，它由节点和边组成，节点之间的边可以有多个。

图可以分为有向图和无向图，如果图中的边有权重，则称为带权图。

二、算法算法是一组解决问题的规则和步骤，它们可以用于开发计算机程序，用于数据处理、数学计算、自然语言处理、图形处理和人工智能等领域。

常见的算法有排序、搜索、动态规划、回溯和贪心等。

1.排序排序是将一组数据按照一定规则进行排列的过程。

常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。

2.搜索搜索是一种算法，它在一个数据集合中查找一个特定的值。

常见的搜索算法有线性搜索、二分搜索、哈希搜索和广度优先搜索等。

3.动态规划动态规划是一种算法，它通过将问题分解成子问题来解决复杂问题。

常见的动态规划算法有背包问题、最长公共子序列、最短路径和编辑距离等。

4.回溯回溯是一种算法，它通过扩展现有解来解决问题。

回溯法通常用于解决组合、排列和子集等问题。

5.贪心贪心是一种算法，它在每个阶段选择最佳的解决方案。

贪心算法通常用于求解最优解问题。

三、总结数据结构和算法是计算机科学中最重要的两个基础学科。

掌握好数据结构和算法是每个程序员必须的基本功。

程序员数据结构详细笔记1.数据结构中对象的定义,存储的表示及操作的实现.2.线性:线性表、栈、队列、数组、字符串（广义表不考）树：二叉树集合：查找，排序图(不考)能力：分析，解决问题的能力过程：●确定问题的数据。

●确定数据间的关系。

●确定存储结构（顺序－数组、链表－指针）●确定算法●编程●算法评价（时间和空间复杂度，主要考时间复杂度）一、数组1、存放于一个连续的空间2、一维～多维数组的地址计算方式已知data[0][0]的内存地址，且已知一个元素所占内存空间s求data[i][j]在内存中的地址。

公式：（add+(i*12+j)*S)(假设此数组为data[10][12])注意：起始地址不是data[0][0]时候的情况。

起始地址为data[-3][8]和情况；3、顺序表的定义存储表示及相关操作4、顺序表操作中时间复杂度估计5、字符串的定义（字符串就是线性表），存储表示模式匹配算法（简单和KMP（不考））6、特殊矩阵：存储方法（压缩存储（按行，按列））三对角：存储于一维数组三对角问题：已知Aij能求出在一维数组中的下标k;已知下标k求Aij。

7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分，不考）算法●数组中元素的原地逆置；对换●在顺序表中搜索值为X的元素；●在有序表中搜索值为X的元素；（折半查找）●在顺序表中的第i个位置插入元素X；●在顺序表中的第i个位置删除元素X；●两个有序表的合并；算法？线性表数据结构定义：Typedef struct {int data[max_size];int len;}linear_list;●模式匹配●字符串相加●求子串●（i,j）<=>K 注意：不同矩阵所用的公式不同；●稀疏矩阵的转置（两种方式，后种为妙）●和数组有关的算法--------------------------------------------------------------------------------例程：求两个长整数之和。

数据结构1．数据结构的分类：1．按逻辑结构分类：{集合；线性结构【一维数组；队列；栈】；非线性结构【树；图；多维数组】}按存储结构分类：{顺序存储；链式存储；索引存储；散列存储}2．树和二叉树1．树树的度数的总和加1等于树的结点数之和。

N=K+1.树的遍历：{前序遍历【先根结点，后子结点】；后序遍历【先叶子结点，后根结点】；层次遍历【按树的结构层次遍历】}2．二叉树的重要特性；（1）在二叉树的第i层上最多有2的（i－1）次方个结点。

（2）深度为k的二叉树最多有2的k次方－1个结点。

（3）对于任何一棵二叉树，其叶子结点数为N0，度为2的结点数为N 2，则N0=N2+1。

（4）如果对一棵有n个结点的完全二叉树的结点按层序编号（从第一层到|_log2n_|＋1层，每层从左到右），则对任一结点i（1≦i≦n），有：如果i＝1，则结点i无父结点，是二叉树的根；如果i>1，则父结点是|_i/2_|。

如果2i>n，则结点i为叶子结点，无左结点；否则，其左子结点为2i。

如果2i＋1>n，则结点i无右子结点，否则，其右子结点为2i。

二叉树的遍历:{前序遍历【根－左－右】；中序遍历【左－根－右】；后序遍历【左－根右】；层次遍历【按层次遍历】}树到二叉树之间的转换：规则：同层结点中只保留左子树结点，其余兄弟结点均转换为右子树。

依次类推。

方法：只保留父结点与其下的左子结点的连线，其他所有结点连线删除。

水平连接同根的兄弟结点，然后整理成二叉树。

注意：二叉树的中序遍历和树的后序遍历是对应的。

可以依次检验转换是否正确。

3．查找二叉树（二叉排序树）一颗查找二叉树，或者是一颗空树，或者满足以下递归条件：（1）查找树的左、右子树各是一颗查找树。

（2）若查找树的左子树非空，则其左子树的各节点值均小于根节点的值。

（3）若查找树的右子树非空，则其右子树上的各节点值均大于根节点的值。

查找二叉树的插入结点操作，分以下几种情况进行相应处理：（1）如果相同键值的结点已经在二叉树中，则不再插入。

第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）表示数据元素之间的逻辑关系。

一、数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

它是计算机程序加工的“原料”。

二、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

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

数据项是数据的不可分割的最小单位。

三、数据对象：是性质相同的数据元素的集合，是数据的一个子集。

四、数据机构：是相互之间存在一种或多种特定关系的数据元素的集合。

在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。

根据数据元素之间关系的不同特性，通常有下列4类基本结构：（1）集合------------数据元素仅有同属一个关系的关系（2）线性结构----------结构中数据元素之间存在一个对一个的关系（3）树形结构------------结构中的数据元素之间存在一个对多个的关系（4）图状结构或网状结构-----------结构中的数据元素之间存在多个对多个的关系五、元素在存贮结构（1）物理结构（存储结构）：它包括数据元素的表示和关系。

（2）逻辑结构六、位bit：在计算机中表示信息的最小单位是二进制的一位七、元素element/节点node：位串八、数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串九、数据元素之间的关系在计算机中有两种不同的表示方法，顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构（借助元素在存储器中的相对位臵来表示数据元素之间的逻辑关系）和链式存储结构（借助指示元素存储地址的指针表示数据元素之间的逻辑关系）。

类C语言语句：（1）预定义常量和类型：#define TRUE 1 FALSE 0#define OK 1 ERROR 0#define INFEASIBLE -1 OVERFLOW -2(2)数据元素类型ElemType(3)赋值语句：简单赋值变量名=表达式；串联赋值变量名1=变量名2=…=变量名k=表达式；成组赋值（变量名1，…，变量名k）=（表达式1，…，表达式k）；结构名=结构名；结构名=（值1，…，值k）；变量名[]=表达式；变量名[起始下标..终止下标]= 变量名[起始下标..终止下标]；交换赋值：变量名<->变量名；条件赋值：变量名=条件表达式？表达式T：表达式F；（4）选择语句有条件语句1 if（表达式）语句；条件语句2 if（表达式）语句；else语句；开关语句1 switch(表达式){case值1：语句序列1；break;…case值n：语句序列n；break;default:语句序列n+1;}开关语句2 switch(表达式){case条件1：语句序列1；break;…case条件n：语句序列n；break;default:语句序列n+1;}(6)循环语句有：for语句 for（赋初值表达式序列；条件；修改表达式序列）语句；while语句 while（条件）语句；do-while语句 do{语句序列；}while（条件）；（7）结束语句有函数结束语句 return表达式；return；case结束语句 break；异常结束语句 exit（异常代码）；（8）输入和输出语句有：输入语句 scanf（[格式串]，变量1，…，变量n）；输出语句 printf（[格式串]，表达式1，…，表达式n）；通常省略格式串。

数据结构串的知识点归纳数据结构串是一种线性表结构，它是由零个或多个数据元素组成的有限序列。

数据结构串的存储结构有两种：顺序存储结构和链式存储结构。

下面将从串的定义、顺序存储结构、链式存储结构、串的基本操作等几个方面进行详细介绍。

一、串的定义串是由零个或多个字符组成的有限序列。

在串中，字符的个数称为串的长度。

如果串的长度为0，则称为空串。

串中的字符可以是字母、数字、标点符号和其他特殊符号等。

二、顺序存储结构顺序存储结构是将串中的字符按照其在串中的顺序依次存放在一块连续的存储空间中。

在顺序存储结构中，我们可以使用一维数组来表示串。

数组的下标表示字符在串中的位置，数组的元素存储字符的ASCII码值或字符本身。

通过这种方式，我们可以方便地对串进行插入、删除、查找等操作。

三、链式存储结构链式存储结构是将串中的字符按照其在串中的顺序分别存放在一系列结点中，并通过指针将这些结点链接起来。

在链式存储结构中，我们可以使用单链表、双链表或循环链表等数据结构来表示串。

每个结点包含一个字符和一个指向下一个结点的指针。

通过这种方式，我们可以方便地对串进行插入、删除、查找等操作。

四、串的基本操作1. 串的赋值：将一个串赋值给另一个串，即将被赋值串的字符复制给另一个串。

2. 串的连接：将两个串连接成一个新串，即将一个串的字符依次复制到另一个串的后面。

3. 串的比较：比较两个串是否相等或大小关系。

4. 串的求子串：从一个串中截取一段连续的子串。

5. 串的插入：将一个串插入到另一个串的指定位置。

6. 串的删除：从一个串中删除指定位置的字符或一段连续的子串。

7. 串的替换：将一个串中的子串替换为另一个串。

8. 串的查找：在一个串中查找指定字符或子串的位置。

9. 串的长度：获取一个串的长度。

10. 串的清空：将一个串清空，使其变成空串。

五、应用场景串作为一种基本的数据结构，在实际应用中有着广泛的应用场景。

例如，字符串匹配算法中常用的KMP算法和Boyer-Moore算法，都是基于串的操作实现的。

数据结构整理笔记在计算机科学领域，数据结构是一个至关重要的概念。

它不仅影响着程序的运行效率，还决定了我们如何有效地组织和存储数据，以便能够快速准确地进行操作和处理。

数据结构可以简单地理解为数据的存储和组织方式。

就好像我们整理自己的房间一样，不同的物品需要有不同的放置方式，以便于我们能够快速找到和使用它们。

在计算机中，数据也需要以合适的结构进行存储，以便程序能够高效地运行。

常见的数据结构有数组、链表、栈、队列、树和图等。

数组是一种最简单也最常见的数据结构。

它就像是一排整齐排列的盒子，每个盒子都有一个固定的位置（索引）。

我们可以通过这个索引快速地访问和修改数组中的元素。

数组的优点是访问速度快，因为只要知道索引，就能立即找到对应的元素。

但它的缺点也很明显，就是插入和删除元素比较麻烦，因为可能需要移动大量的其他元素来腾出空间或者填补空缺。

链表则与数组不同。

链表中的元素并不是连续存储的，而是通过指针相互连接。

这就像是一串珠子，每个珠子都知道下一个珠子在哪里。

链表的插入和删除操作相对简单，只需要修改指针的指向即可。

但访问特定位置的元素就比较慢，因为需要从链表的开头依次遍历。

栈是一种特殊的线性表，它遵循“后进先出”的原则。

想象一下一个只能从顶部放入和取出物品的桶，最后放入的物品会最先被取出。

栈在程序中常用于函数调用、表达式求值等场景。

队列则遵循“先进先出”的原则，就像在排队买票，先来的人先得到服务。

队列常用于任务调度、消息传递等方面。

树是一种分层的数据结构，其中最常见的是二叉树。

二叉树的每个节点最多有两个子节点，分别称为左子节点和右子节点。

树结构在搜索、排序等操作中表现出色，比如二叉搜索树可以快速地查找特定的值。

图是一种更为复杂的数据结构，它由节点和边组成，可以用来表示各种关系。

比如社交网络中人与人的关系、地图中地点之间的连接等。

在实际应用中，选择合适的数据结构取决于具体的问题和需求。

如果需要频繁地随机访问元素，数组可能是一个好的选择；如果需要频繁地插入和删除元素，链表可能更合适；如果需要按照特定的顺序处理元素，栈或队列可能有用；对于需要高效搜索和排序的数据，树结构可能是最佳选择；而对于表示复杂的关系，图则是不二之选。

数据结构复习笔记在计算机科学领域中，数据结构是一门极其重要的基础课程。

它不仅是编程的基石，更是解决各种复杂问题的关键工具。

通过对数据结构的学习和掌握，我们能够更加高效地组织和处理数据，从而提高程序的性能和效率。

接下来，就让我为大家梳理一下数据结构的重要知识点。

首先，我们来谈谈线性表。

线性表是一种最简单的数据结构，它是由一组相同类型的数据元素组成的有限序列。

常见的线性表有顺序表和链表。

顺序表就像是一排紧密排列的座位，每个元素都按照顺序依次存放，查找方便但插入和删除操作比较麻烦，因为需要移动大量的元素。

而链表则像是一条由珠子串成的链子，每个珠子（节点）包含数据和指向下一个节点的指针，插入和删除操作很灵活，只需要修改指针即可，但查找就相对较慢。

栈和队列也是常见的数据结构。

栈是一种“后进先出”的结构，就像一个桶，最后放进去的东西最先被取出来。

比如我们在浏览器中后退网页的操作，就可以用栈来实现。

队列则是“先进先出”，如同排队买票，先到的先服务。

在操作系统中，打印任务的处理就常常使用队列。

接着说说树这种数据结构。

树是一种分层的数据结构，其中每个节点最多有两个子节点的称为二叉树。

二叉树又分为满二叉树、完全二叉树等。

二叉查找树是一种特殊的二叉树，左子树的所有节点值都小于根节点，右子树的所有节点值都大于根节点。

这使得查找、插入和删除操作的时间复杂度都可以达到 O(logn)，效率很高。

平衡二叉树则是为了避免二叉查找树退化成链表而出现的，它能始终保持左右子树的高度差不超过 1，保证了较好的性能。

另外，图也是非常重要的数据结构。

图由顶点和边组成，可以分为有向图和无向图。

图的存储方式有邻接矩阵和邻接表等。

图的遍历算法有深度优先遍历和广度优先遍历。

在实际应用中，图常用于解决路径规划、网络优化等问题。

在学习数据结构的过程中，算法的设计和分析也是至关重要的。

时间复杂度和空间复杂度是衡量算法性能的重要指标。

常见的时间复杂度有 O(1)、O(n)、O(logn)、O(nlogn)、O(n^2) 等。

数据结构知识点总结作者：于泽萍一、绪论二、线性表1.线性表是一种线性结构（逻辑结构）2.线性表长度指元素的个数3.线性表的表示方式：顺序表示和链式表示4.顺序表示（1）顺序存储的线性表是顺序表（随机存取）A.用数组存储B.有变量表示顺序表长度（长度可变）（2）顺序表的存储结构#define MAXSIZE 100 //顺序表可能达到做大长度Typedef struct{ElemType *elem;int length; //当前长度}SqList;（3）顺序表特点：A.逻辑结构和物理结构一致B.每个元素所花时间相等（4）顺序表优缺点：优点：A.存储密度大[ 结点本身所占存储量/结点结构所占存储量]B随机存取表中任一元素缺点：A.插入删除某一元素，需要移动大量元素B.浪费空间C.静态存储形式，元素个数不能扩充（5）顺序表基本操作A初始化B.查找：按位置查找快C.插入：平均移动次数（n+1）/2 O(n)D.删除：平均移动次数（n-1）/2 O(n)8.链式表示（顺序存取）（1）单链表1）设立头结点的优点：便于开始结点的处理；便于空表和非空表的统一处理2）存储结构typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;（2）循环链表（首尾相连）最后一个结点的指针域存第一个结点的地址 （3）双向链表五、树和二叉树1.定义树：只有一个根结点；除根结点以外的其余结点可分为m （m>0）个互不相交的有限集（根的子树）结点：树的一个独立单元 结点的度：直接后继的个数树的度：树内个结点度的最大值max 叶子：度为0的结点 非终端结点（分支结点）：度不为0的结点，除根以外，非终端结点也称内部结点 双亲和孩子：孩子是直接后继 兄弟：双亲相同的结点祖先：从根到该结点所经分支上的所有结点，不包括本身 子孙：以某结点为根的子树中任意结点都成为该结点的子孙 层次：根是第一层堂兄弟：其双亲在同一层的结点（和兄弟不同） 树的深度：树中结点的最大层次有序树和无序树：有序树区分孩子先后 森林：m(m>=0)棵互不相交树的集合2.二叉树（多叉树可转化成二叉树，计算机擅长） （1）定义二叉树：只有一个根结点；除根结点以外的其余结点分为2个互不相交的子集T1（左子树）和T2（右子树）满二叉树：深度为k 且含有12 k个结点的二叉树（一定是完全二叉树）完全二叉树：深度为k ，有n 个结点的二叉树，当且仅当每一个节点都与深度为k 的满二叉树中编号从1到n 的结点一一对应（度为1结点为0或1个；只有最后一层不满，且全部集中在左边）完全二叉树特点：叶子结点只能在层次最大的两层出现；对任一结点，若其右分支下的子孙的最大层次是L ，则其左分支下的子孙最大层次必为L 或L+1。