下载文档原格式
数据结构复习要点(整理版)数据结构复习要点(整理版)数据结构是计算机科学中非常重要的一门课程，它涉及到各种数据的存储和组织方式，对于编程和算法的理解都至关重要。
本文将整理常见的数据结构复习要点，帮助读者回顾和加深对数据结构的理解。
一、线性结构线性结构是最简单的数据结构之一，它包括线性表、栈、队列等。
线性表是具有相同数据类型的一组元素的有限序列，它可以分为顺序表和链表。
顺序表是一种用连续的存储单元依次存储线性表的元素的数据结构，而链表则是通过每个元素中存储下一个元素的地址来实现线性关系。
栈和队列是线性结构的特殊形式。
栈是一种先进后出（LIFO）的数据结构，它可以通过顺序栈或链栈来实现。
队列是一种先进先出（FIFO）的数据结构，它可以通过顺序队列或链队列来实现。
二、树形结构树形结构是一种非线性结构，它具有层次关系，由节点和边组成。
常见的树形结构包括二叉树、二叉搜索树、平衡二叉树和哈夫曼树。
二叉树是每个节点最多只有两个子节点的树，它可以是空树、只有一个根节点的树或者一个根节点连接两棵不相交的二叉树。
二叉搜索树是一种特殊的二叉树，它的左子树上所有节点的值小于根节点的值，右子树上所有节点的值大于根节点的值。
平衡二叉树是一种特殊的二叉搜索树，它的左子树和右子树的高度差不超过1，这样可以保证在最坏情况下的查找效率。
哈夫曼树是一种特殊的二叉树，它的叶子节点代表字符，而各节点的权值表示字符出现的频率，通过构造哈夫曼树可以实现数据的压缩编码。
三、图形结构图形结构是一种包含节点和边的非线性数据结构，它由顶点集合和边集合组成。
图形结构可以分为无向图和有向图，每个节点可以有一个或多个相邻节点。
图形结构的常见算法有深度优先搜索（DFS）和广度优先搜索（BFS）。
深度优先搜索是一种通过递归或栈实现的搜索算法，它先访问起始节点的一个邻接节点，再依次访问该节点的未被访问过的邻接节点，直到所有节点都被访问过。
广度优先搜索则是一种通过队列实现的搜索算法，它先访问起始节点的所有邻接节点，再依次访问这些邻接节点的邻接节点，以此类推，直到所有节点都被访问过。
数据结构复习资料(亲自整理)1、链表是一种存储数据的链式结构，每个数据之间都是相关联的。
2、线性结构是一个有序数据元素的集合，包括线性表、栈、队列、双队列、数组和串。
3、树是由n（n>=1）个有限节点组成一个具有层次关系的集合，而二叉树是每个结点最多有两个子树的有序树。
二叉树与树的主要差别在于，二叉树结点的最大度数为2，而树中结点的最大度数没有限制；二叉树的结点有左、右之分，而树的结点无左、右之分。
4、堆是一种可以被看做一棵树的数组对象，总是满足某个节点的值总是不大于或不小于其父节点的值，且堆总是一棵完全二叉树。
5、二叉排序树是一种满足以下递归定义的二叉树：若左子树非空，则左子树所有节点的值均小于它的根节点；若右子树非空，则右子树所有节点的值均大于于它的根节点；左右子树也分别为二叉排序树。
1、在已知前序遍历和中序遍历的情况下，可以通过画树的方法求得后序遍历。
具体步骤如下：首先根据前序遍历的特点，确定根节点；然后观察中序遍历，将左子树和右子树分别确定下来；接着对左子树和右子树分别进行递归，直到遍历完所有节点，最后得到后序遍历。
2、树和二叉树之间可以相互转换。
将树转换为二叉树的方法是：对于每个节点，将其第一个孩子作为其左孩子，将其兄弟作为其右孩子。
将二叉树转换为树的方法是：对于每个节点，将其右孩子作为其兄弟。
3、二叉树线索化是将二叉树中的空指针指向该节点在中序遍历中的前驱或后继节点的过程。
在线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1.4、邻接表是图的一种链式存储结构，用于表示图中每个节点的邻居节点。
每个节点都有一个链表，存储着与该节点相邻的节点。
邻接表是一种图的存储结构，对于每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边（对于有向图是以该顶点为尾的弧）。
邻接表中的表结点和头结点分别表示边和顶点，包含信息如下：表结点adjvex（邻接点）。
nextarc（指向下一个表结点）（权值等信息）；头结点data（顶点信息）和firstarc（指向第一个表结点）。
数据结构复习资料复习提纲知识要点归纳数据结构复习资料：复习提纲知识要点归纳一、数据结构概述1. 数据结构的定义和作用2. 常见的数据结构类型3. 数据结构与算法的关系二、线性结构1. 数组的概念及其特点2. 链表的概念及其分类3. 栈的定义和基本操作4. 队列的定义和基本操作三、树结构1. 树的基本概念及定义2. 二叉树的性质和遍历方式3. 平衡二叉树的概念及应用4. 堆的定义和基本操作四、图结构1. 图的基本概念及表示方法2. 图的遍历算法：深度优先搜索和广度优先搜索3. 最短路径算法及其应用4. 最小生成树算法及其应用五、查找与排序1. 查找算法的分类及其特点2. 顺序查找和二分查找算法3. 哈希查找算法及其应用4. 常见的排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序六、高级数据结构1. 图的高级算法：拓扑排序和关键路径2. 并查集的定义和操作3. 线段树的概念及其应用4. Trie树的概念及其应用七、应用案例1. 使用数据结构解决实际问题的案例介绍2. 如何选择适合的数据结构和算法八、复杂度分析1. 时间复杂度和空间复杂度的定义2. 如何进行复杂度分析3. 常见算法的复杂度比较九、常见问题及解决方法1. 数据结构相关的常见问题解答2. 如何优化算法的性能十、总结与展望1. 数据结构学习的重要性和难点2. 对未来数据结构的发展趋势的展望以上是数据结构复习资料的复习提纲知识要点归纳。
希望能够帮助你进行复习和回顾，加深对数据结构的理解和掌握。
在学习过程中，要注重理论与实践相结合，多进行编程练习和实际应用，提高数据结构的实际运用能力。
祝你复习顺利，取得好成绩！。
第一章数据结构概述基本概念与术语1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。
2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。
（补充：一个数据元素可由若干个数据项组成。
数据项是数据的不可分割的最小单位。
）3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
（有时候也叫做属性。
）4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
（1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。
数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。
依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。
2.线性结构：结构中的数据元素之间存在“一对一“的关系。
若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。
3.树形结构：结构中的数据元素之间存在“一对多“的关系。
若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。
4.图状结构：结构中的数据元素存在“多对多”的关系。
若结构为非空集，折每个数据可有多个（或零个）直接后继。
（2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。
想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。
逻辑结构可以映射为以下两种存储结构：1.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。
2.链式存储结构：借助指针表达数据元素之间的逻辑关系。
不要求逻辑上相邻的数据元素物理位置上也相邻。
数据结构复习提纲一、线性表线性表是最基本的数据结构之一，它是具有相同数据类型的 n 个数据元素的有限序列。
1、顺序表定义和特点：顺序表是用一组地址连续的存储单元依次存储线性表的数据元素。
存储结构：通常使用数组来实现。
基本操作：插入、删除、查找、遍历等。
时间复杂度分析：插入和删除操作在平均情况下的时间复杂度为O(n)，查找和遍历操作的时间复杂度为 O(n)。
2、链表定义和特点：链表是通过指针将各个数据元素链接起来的一种存储结构。
单链表：每个节点包含数据域和指针域，指针域指向链表的下一个节点。
双链表：节点包含两个指针域，分别指向前驱节点和后继节点。
循环链表：尾节点的指针指向头节点，形成一个环形结构。
基本操作：插入、删除、查找等。
时间复杂度分析：插入和删除操作在平均情况下的时间复杂度为O(1)，查找操作的时间复杂度为 O(n)。
二、栈和队列1、栈定义和特点：栈是一种限制在一端进行插入和删除操作的线性表，遵循“后进先出”的原则。
存储结构：顺序栈和链栈。
基本操作：入栈、出栈、栈顶元素获取等。
应用：表达式求值、括号匹配、函数调用等。
2、队列定义和特点：队列是一种在一端进行插入操作，在另一端进行删除操作的线性表，遵循“先进先出”的原则。
存储结构：顺序队列和链队列。
基本操作：入队、出队、队头元素获取等。
循环队列：解决顺序队列“假溢出”问题。
应用：层次遍历、消息队列等。
三、串1、串的定义和存储方式定长顺序存储堆分配存储块链存储2、串的基本操作串的赋值、连接、比较、求子串等。
3、模式匹配算法朴素的模式匹配算法KMP 算法：理解其原理和计算 next 数组的方法。
四、数组和广义表1、数组数组的定义和存储结构数组的地址计算特殊矩阵的压缩存储（如对称矩阵、三角矩阵、稀疏矩阵）2、广义表广义表的定义和表示广义表的递归算法1、树的基本概念定义、术语（如节点、度、叶子节点、分支节点、父节点、子节点、兄弟节点、层次等）树的性质2、二叉树定义和特点二叉树的性质完全二叉树和满二叉树3、二叉树的存储结构顺序存储链式存储4、二叉树的遍历先序遍历中序遍历后序遍历层序遍历5、二叉树的递归和非递归遍历算法实现线索化的目的和方法7、树、森林与二叉树的转换8、哈夫曼树定义和构造方法哈夫曼编码六、图1、图的基本概念定义、术语（如顶点、边、权、有向图、无向图、邻接矩阵、邻接表等）2、图的存储结构邻接矩阵邻接表十字链表邻接多重表3、图的遍历深度优先搜索（DFS）广度优先搜索（BFS）4、图的应用最小生成树（Prim 算法、Kruskal 算法）最短路径（Dijkstra 算法、Floyd 算法）拓扑排序关键路径七、查找1、查找的基本概念关键字、平均查找长度等2、顺序查找算法实现时间复杂度3、折半查找算法实现时间复杂度判定树4、分块查找5、二叉排序树定义和特点插入、删除操作查找算法6、平衡二叉树定义和调整方法7、 B 树和 B+树结构特点基本操作8、哈希表哈希函数的构造方法处理冲突的方法（开放定址法、链地址法等）八、排序1、排序的基本概念排序的稳定性2、插入排序直接插入排序折半插入排序希尔排序3、交换排序冒泡排序快速排序4、选择排序简单选择排序堆排序5、归并排序6、基数排序7、各种排序算法的时间复杂度、空间复杂度和稳定性比较。
第一章数据结构概述基本概念与术语1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。
2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。
（补充：一个数据元素可由若干个数据项组成。
数据项是数据的不可分割的最小单位。
）3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
（有时候也叫做属性。
）4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
（1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。
数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。
依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。
2.线性结构：结构中的数据元素之间存在“一对一“的关系。
若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。
3.树形结构：结构中的数据元素之间存在“一对多“的关系。
若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。
4.图状结构：结构中的数据元素存在“多对多”的关系。
若结构为非空集，折每个数据可有多个（或零个）直接后继。
（2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。
想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。
逻辑结构可以映射为以下两种存储结构：1.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。
2.链式存储结构：借助指针表达数据元素之间的逻辑关系。
不要求逻辑上相邻的数据元素物理位置上也相邻。
复习提纲第一章数据结构概述基本概念与术语（P3）1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科.2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合2．数据元素是数据的基本单位3．数据对象相同性质的数据元素的集合4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系.（2）数据的存储结构指数据元素及其关系在计算机内的表示( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等.5.时间复杂度分析--------------------------------------------------------------------------------------------------------------------1、名词解释：数据结构、二元组2、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。
3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。
4、以下程序段的时间复杂度为___O(N2)_____。
int i,j,x;for(i=0;i<n:i++) n+1for(j=0;j<n;j++) n+1x+=i;------------------------------------------------------------------------------------------------------------------第二章线性表1.顺序表结构由n(n>=0)个具有相同性质的数据元素a1,a2,a3……,an组成的有穷序列//顺序表结构#define MAXSIZE 100typedef int DataType;Typedef struct{DataType items[MAXSIZE];Int length;}Sqlist,*LinkList;//初始化链表void InitList(LinkList *L){(*L)=(LinkList)malloc(sizeof(LNode));if(!L){cout<<”初始化失败!”;return;}(*L)->next=NULL;}//插入数据void InsertList(LinkList L,int pos,DataType x){LinkList p=L,q;int i=0;while(p&&i<pos-1){p=p->next;i++;}if(!p||i>pos-1){cout<<”插入位置错误”;return;}InitList(&q);q->next=p->next;p->next=q;q->data=x;}//销毁链表void DestoryList(LinkList L){LinkList t;while(L){t=L;L=L->next;free(t);}}//遍历链表void TraverseList(LinkList L){LinkList t=L;while(L){t=t->next;cout<<t->data<<” ”;}cout<<endl;}//删除元素void DeleteList(LinkList L,int pos){LinkList p=L,q;int i=0;while(p&&i<pos-1){p=p->next;i++;}if(!p||i>pos-1){cout<<”删除位置错误!!”;return;}q=p->next;p->next=q->next;free(q):}第三章栈和队列1.栈（1）栈的结构与定义（2）顺序栈操作算法：入栈、出栈、判断栈空等（3）链栈的结构与定义2.队列（1）队列的定义----------------------------------------------------------------------------------------------------------------1、一个栈的入栈序列为“ABCDE”，则以下不可能的出栈序列是（）A. BCDAEB. EDACBC. BCADED. AEDCB2、栈的顺序表示仲，用TOP表示栈顶元素，那么栈空的条件是（）A. TOP==STACKSIZEB. TOP==1C. TOP==0D. TOP==-13、允许在一端插入，在另一端删除的线性表称为____队列____。
第1章绪论1.1 数据结构的基本概念数据元是数据的基本单位，一个数据元素可由若干个数据项完成，数据项是构成数据元素的不可分割的最小单位。
例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。
数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
数据类型是一个值的集合和定义在此集合上一组操作的总称。
•原子类型：其值不可再分的数据类型•结构类型：其值可以再分解为若干成分（分量）的数据类型•抽象数据类型：抽象数据组织和与之相关的操作抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。
抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。
通常用（数据对象、数据关系、基本操作集）这样的三元组来表示。
#关键词：数据，数据元素，数据对象，数据类型，数据结构数据结构的三要素：1.逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，独立于计算机。
分为线性结构和非线性结构，线性表、栈、队列属于线性结构，树、图、集合属于非线性结构。
2.存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构，包括数据元素的表示和关系的表示，依赖于计算机语言，分为顺序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、增加、删除快）。
3.数据的运算：包括运算的定义和实现。
运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
1.2 算法和算法评价算法是对特定问题求解步骤的一种描述，有五个特性：有穷性、确定性、可行性、输入、输出。
一个算法有零个或多个的输入，有一个或多个的输出。
时间复杂度是指该语句在算法中被重复执行的次数，不仅依赖于问题的规模n，也取决于待输入数据的性质。
一般指最坏情况下的时间复杂度。
空间复杂度定义为该算法所耗费的存储空间。
算法原地工作是指算法所需辅助空间是常量，即O(1)。
第2章线性表2.1 线性表的定义和基本操作线性表是具有相同数据类型的n个数据元素的有限序列。
数据结构复习资料(亲自整理)数据结构复习资料(亲自整理)引言：数据结构是计算机科学中的重要基础知识，掌握良好的数据结构能够提高程序的运行效率，同时也是进行算法设计和优化的关键。
本文将为大家提供一份亲自整理的数据结构复习资料，旨在帮助读者回顾和巩固数据结构的知识，并提供一些实践经验和应用场景。
一、数据结构的概念和基本知识1.1 数据结构的定义数据结构是指数据元素之间的相互关系和组织形式，它包括线性结构、树形结构、图形结构等多种形式。
数据结构可以用来描述程序的运行状态和过程中产生的数据，是程序设计的基础。
1.2 常见的数据结构类型介绍常见的数据结构类型，如数组、链表、栈、队列、树、图等，并分别阐述它们的特点、适用场景和基本操作。
1.3 数据结构的时间复杂度和空间复杂度分析详细解释时间复杂度和空间复杂度的概念，分析不同数据结构及其操作的时间和空间复杂度，并通过实例演示如何计算和评估复杂度。
二、线性结构2.1 数组(Array)介绍数组的定义和基本操作，包括初始化、插入、删除、查找等操作。
通过示例展示如何使用数组解决实际问题，并探讨数组的优缺点及应用场景。
2.2 链表(Linked List)介绍链表的概念和分类，包括单向链表、双向链表和循环链表。
详细说明链表的插入、删除和查找操作，并讨论链表的优缺点及适用场景。
2.3 栈(Stack)解释栈的概念和特点，包括栈的基本操作(push、pop、top等)。
演示如何使用栈来解决实际问题，如逆序输出、括号匹配等，同时介绍栈的应用领域。
2.4 队列(Queue)描述队列的定义和基本操作(enqueue、dequeue等)，并通过实例介绍队列的应用，如打印任务调度、消息传递等。
三、树形结构3.1 二叉树(Binary Tree)解释二叉树的定义和性质，包括满二叉树、完全二叉树和二叉查找树等。
介绍二叉树的遍历方式(前序、中序、后序)和常见操作，并给出实际应用案例。
3.2 堆(Heap)介绍堆的概念和特点，包括最大堆、最小堆和堆排序。
第一章数据结构概述基本概念与术语1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。
2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。
（补充：一个数据元素可由若干个数据项组成。
数据项是数据的不可分割的最小单位。
）3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
（有时候也叫做属性。
）4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
（1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。
数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。
依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。
2.线性结构：结构中的数据元素之间存在“一对一“的关系。
若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。
3.树形结构：结构中的数据元素之间存在“一对多“的关系。
若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。
4.图状结构：结构中的数据元素存在“多对多”的关系。
若结构为非空集，折每个数据可有多个（或零个）直接后继。
（2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。
想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。
逻辑结构可以映射为以下两种存储结构：1.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。
2.链式存储结构：借助指针表达数据元素之间的逻辑关系。
不要求逻辑上相邻的数据元素物理位置上也相邻。
5.时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n无关系T(n)=O(1)2.线性阶：算法的时间复杂度与问题规模n成线性关系T(n)=O(n)3.平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++时间复杂度的大小比较：O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n )<O(n!)<O(n n)6.算法与程序：（1）算法的5个特性1、输入：有零个或多个输入2、输出：有一个或多个输出3、有穷性：要求序列中的指令是有限的；每条指令的执行包含有限的工作量；整个指令序列的执行在有限的时间内结束。
（程序与算法的区别在于，程序不需要有有穷性）4、确定性：算法中的每一个步骤都必须是确定的，而不应当含糊、模棱两可。
没有歧义。
5、可行性：算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。
（2）.算法设计的要求：1、正确性（达到预期效果，满足问题需求）2、健壮性（能处理合法数据，也能对不合法的数据作出反应，不会产生不可预期的后果）3、可读性（要求算法易于理解，便于分析）4、可修改可扩展性5、高效率（较好的时空性能）补充内容：1、名词解释：数据结构、二元组数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。
二元组就是一种用来表示某个数据对象以及各个元素之间关系的有限集合。
2、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。
3、常见的数据存储结构一般有两种类型，它们分别是顺序存储结构、链式存储结构6.在一般情况下，一个算法的时间复杂度是问题规模的函数7.常见时间复杂度有：常数阶O（1）、线性阶O（n）、对数阶O（log 2 n）、平方阶O(n^2)、指数阶O(2^n)。
通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。
第二章线性表定义：线性表是n个数据元素的有限序列。
一个数据元素可由若干个数据项组成。
1.顺序表结构线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。
2.单链表（1）链表结点结构线性表中的数据元素可以用任意的一组存储单元来存储，用指针表示逻辑关系逻辑相邻的两元素的存储空间可以是不连续的。
（2）链表操作算法：初始化、插入、输出、删除、遍历初始化：p=(struct student *)malloc(sizeof(struct student));插入：p->next=head->next;head->next=p;输出：printf(“%d”,p->data);删除：q=p->next;p->next = q->next ;free(q);结点遍历：for(p=head;p;p=p->next);补充内容：1、线性表中，第一个元素没有直接前驱，最后一个元素没有直接后驱。
2、在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的操作语句为P->next = q->next ;free(q)3、在长度为N的顺序表中，插入一个新元素平均需要移动表中N/2个元素，删除一个元素平均需要移动（N-1）/2个元素。
4、若线性表的主要操作是在最后一个元素之后插入一个元素或删除最后一个元素，则采用顺序表存储结构最节省运算时间。
5、已知顺序表中每个元素占用3个存储单元，第13个元素的存储地址为336，则顺序表的首地址为300。
（第n个元素的地址即首地址+(n-1)*每个元素的存储空间，如a[12]（第13个元素）的地址=a[0]+12*3）6、设有一带头结点单链表L，请编写该单链表的初始化，插入、输出和删除函数。
（函数名自定义）结点定义：typedef int datype;//结点数据类型，假设为inttypedef struct node {//结点结构datype data;struct node *next;//双向链表还应加上*previous} Lnode, * pointer ; //结点类型,结点指针类型typedef pointer lklist;//单链表类型，即头指针类型1.初始化：lklist initlist() {pointer head;head=new node;//这是C++做法//head=( pointer)malloc(sizeof(Lnode));这是C语言做法head->next=NULL;//循环链表则是head->next=head;//双向链表应加上head->previos=NULL;return head;}2.插入：（C语言中需要把head转化为全局变量才能实现此程序）int insert(lklist head,datype x,int i){pointer q,s;q=get(head,i-1);//找第i-1个点if(q==NULL)//无第i-1点，即i<1或i>n+1时{cout<<”非法插入位置!\n”; //这是C++做法，即C语言中的printf(“非法插入位置!\n”);return 0;}s=new node;//生成新结点即C语言中的s=( pointer)malloc(sizeof(Lnode));s->data=x;s->next=q->next;//新点的后继是原第i个点q->next=s;//原第i-1个点的后继是新点return 1;//插入成功}3.删除：（C语言中需要把head转化为全局变量才能实现此程序）int delete(lklist head,int i) {pointer p,q;q=get(head,i-1);//找待删点的直接前趋if(q==NULL || q->next==NULL)//即i<1或i>n时{cout<<”非法删除位置!\n”;return 0;}p=q->next;//保存待删点地址q->next=p->next;//修改前趋的后继指针delete p;//释放结点即C语言中的free(p);return 1;//删除成1.不带头结点的单链表head为空的判定条件是(A )A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL2.带头结点的单链表head为空的判定条件是(B )A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL3.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B )A.s->next=p;p->next=s;B.s->next=p->next;p->next=sC.s->next=p->next;p=s;D.p->next=s;s->next=p;4.在一个单链表中，若删除p所指结点的后续结点，则执行(A )A.p->next=p->next->nextB.p=p->next;p->next=p->next->nextC.p->next=p->nextD.p=p->next->next5.从一个具有n个结点的有序单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（B ）个结点。
A. nB. n/2C. (n-1)/2D. O(n㏒2n)6.给定有n个元素的向量，建立一个有序单链表的时间复杂度（B）A.O(1)B.O(n)C.O(n2)D.O(n㏒2n)7.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B)A.O(1)B.O(n)C.O(n2)D.O(n㏒2n)8.在一个单链表中删除q所指结点时，应执行如下操作：q=p->next;p->next=( p->next->next );free(q);//这种题目靠一根指针是没有办法完成的，必须要借助第二根指针。
9.在一个单链表中p所指结点之后插入一个s所指结点时，应执行：s->next=( p->next )p->next=(s)操作。
10.对于一个具有n个节点的单链表,在已知所指结点后插入一个新结点的时间复杂度是(O（1）)；在给定值为x的结点后插入一个新结点的时间复杂度是（O(n)）。
