数据结构知识点总结.docx

《数据结构知识点总结.docx》由会员分享，可在线阅读，更多相关《数据结构知识点总结.docx（32页珍藏版）》请在优知文库上搜索。

1、1数据结构概述数据结构是计算机科学中的一门基础课程，它研究数据组织和处理的方式。数据结构是一种逻辑上的组织形式，它描述了数据元素之间的关系，并定义了在这些数据元素上执行的操作。数据结构可以分为线性结构和非线性结构两种：1线性结构：数据元素之间的关系是一对一的关系，例如数组、链表、栈、队列等。2非线性结构：数据元素之间的关系是一对多的关系，例如树、图等。数据结构的设计和实现关系到程序的性能和可维护性，常用的数据结构包括：1数组：一组相同数据类型的数据按照一定的顺序排列，通过下标来访问。2链表：数据元素之间通过指针相连，可以是单向链表、双向链表或循环链表。3栈：一种先进后出的数据结构，只允许在栈顶

2、进行插入和删除操作。4队列：一种先进先出的数据结构，只允许在队尾插入元素，在队头删除元素。5树：由节点和边组成的数据结构，每个节点有零个或多个子节点，一般用于模拟具有层次关系的问题。6图：由节点和边组成的数据结构，每个节点有零个或多个相邻节点，用于模拟复杂的网络结构。2数据结构的相关概念、名词和术语在学习数据结构时，需要了解一些相关的概念、名词和术语，以下是一些常见的：1数据元素：组成数据结构的基本单位。2数据项：数据元素中的单个数据，例如一个人的身高、体重等。3结点：树和图中的基本单位，包含数据元素和指向其他结点的指针。4根结点：树中没有父结点的结点，是树的起点。5叶子结点：树中没有子结点的

3、结点，是树的终点。6父结点：有子结点的结点。7子结点：有父结点的结点。8树的度：树中一个结点所拥有的子树的个数。9树的深度：从根结点到最深叶子结点的路径长度。10链表：由结点按线性顺序连接而成的数据结构。11单向链表：每个结点只有一个指向下一个结点的指针。12双向链表：每个结点同时具有指向上一个结点和下一个结点的指针。13循环链表：尾结点的指针指向头结点，形成一个循环。14栈：一种先进后出的数据结构。15队列：一种先进先出的数据结构。16堆：一种可以快速找到最大或最小元素的树形数据结构。17散列表：一种通过将关键字映射到表中一个位置来访问记录的数据结构。18排序算法：对数据元素进行排序的算法，

4、例如冒泡排序、快速排序、归并排序等。3数据的逻辑结构、存储结构。在数据结构中，数据的逻辑结构和存储结构是两个基本概念。1.数据的逻辑结构：数据的逻辑结构指的是数据元素之间的逻辑关系，它决定了数据元素之间的组织方式和操作方式。常见的数据逻辑结构包括线性结构、树形结构和图形结构。线性结构包括线性表、栈和队列，其中线性表是一种有序的数据元素序列，栈是一种限定插入和删除操作只能在同一端进行的线性表，队列是一种插入操作只能在一端进行，删除操作只能在另一端进行的线性表。树形结构包括二叉树、多叉树和森林，其中二叉树是每个结点最多只有两个子节点的树形结构，多叉树是每个结点有多个子节点的树形结构，森林是多个互不

5、相交的树的集合。图形结构是由结点和边组成的非线性结构，结点表示数据元素，边表示数据元素之间的关系。图形结构包括有向图和无向图，其中有向图的边具有方向性，无向图的边没有方向性。1.数据的存储结构：数据的存储结构指的是数据元素在计算机内存中的存储方式，包括顺序存储和链式存储两种。顺序存储是指将数据元素存储在一段连续的存储空间中，数据元素之间的物理地址是连续的。顺序存储适用于线性表和一些简单的树形结构，如满二叉树。链式存储是指将数据元素存储在任意的存储空间中，通过指针来链接相邻的数据元素，数据元素之间的物理地址是不连续的。链式存储适用于线性表、树形结构和图形结构。4算法的概念，算法的效率评价。1.算

6、法的概念：算法是一组定义良好的指令，用于解决特定问题或执行特定任务的有限步骤序列。简单来说，算法就是解决问题的方法和步骤。在计算机科学中，算法是计算机程序的核心部分，它决定了程序的执行效率和正确性。因此，设计高效的算法对于计算机科学的发展至关重要。1.算法的效率评价：算法的效率评价是指对算法的执行效率进行度量和评估，常用的评价方法包括时间复杂度和空间复杂度。时间复杂度是指算法执行所需要的时间，通常用算法中基本操作的执行次数来度量。时间复杂度用大。记号表示,比如0(n)、O(nlogn),0(M2)等。其中，n表示输入数据的规模，时间复杂度越小，算法执行效率越高。空间复杂度是指算法在执行过程中所

7、需要的存储空间，通常用算法中数据存储量的大小来度量。空间复杂度也用大0记号表示，例如0(1)、0(n)、0(M2)等。其中，n表示输入数据的规模，空间复杂度越小，算法所需的存储空间越少。5线性表线性表是最基本、最常用的数据结构之一，它是n(n=0)个具有相同特性的数据元素的有限序列。在线性表中，数据元素的逻辑关系是一对一的关系，即除了第一个和最后一个元素，其余元素都有唯一的直接前驱和直接后继。线性表通常用1.来表示，其中1.O表示第一个元素，1.I表示第二个元素，以此类推，1.n-I表示第n个元素，n为线性表的长度。线性表的实现方式有两种，分别是顺序存储和链式存储。顺序存储是将线性表的元素顺序

8、地存放在一块连续的存储空间中，即用一组地址连续的存储单元依次存储线性表的元素。由于数据元素在存储空间中的位置是连续的，因此可以随机访问线性表中的任意元素。链式存储是将线性表的元素存放在任意的存储单元中，通过指针来链接相邻的元素，即每个元素都有一个指针指向下一个元素。由于数据元素在存储空间中的位置是不连续的，因此访问线性表中的元素需要通过指针进行遍历。线性表支持的基本操作包括：1初始化：初始化线性表，即创建一个空的线性表。2插入：将新的元素插入到线性表的指定位置上。3删除：删除线性表中指定位置的元素。4查找：查找线性表中指定位置的元素。5修改：修改线性表中指定位置的元素。6遍历：按照线性表元素的

9、顺序遍历整个线性表。6线性表的顺序存储结构和链式存储结构及其基本操作的实现。线性表是一种基本的数据结构，它包括顺序存储结构和链式存储结构两种形式。其中，顺序存储结构使用一段连续的存储空间来存储线性表中的元素，而链式存储结构则使用一组节点来存储线性表中的元素，每个节点包括数据域和指针域。1.顺序存储结构的基本操作（1）初始化线性表：即为线性表中的元素分配一段连续的存储空间，并将线性表的长度设置为0。（2）插入元素：在指定位置插入一个新元素，需要将该位置之后的元素向后移动一个位置，并修改线性表的长度。（3）删除元素：删除指定位置的元素，需要将该位置之后的元素向前移动一个位置，并修改线性表的长度。（

10、4）查找元素：在线性表中查找指定元素的位置，需要遍历整个线性表进行搜索。（5）修改元素：修改指定位置的元素。1.链式存储结构的基本操作（1）初始化线性表：即为线性表中的元素分配一组节点，并将头指针指向第一个节点。（2）插入元素：在指定位置插入一个新元素，需要先找到该位置的前驱节点，然后将新节点插入到其后面，并修改前驱节点的指针域和新节点的指针域。（3）删除元素：删除指定位置的元素，需要先找到该位置的前驱节点，然后将其指针域指向该位置的后继节点，并释放该位置的节点。（4）查找元素：在线性表中查找指定元素的位置，需要遍历整个链表进行搜索。（5）修改元素：修改指定位置的元素。7栈，栈的顺序存储和链式

11、存储及其基本运算的实现栈是一种常见的数据结构，它具有后进先出（1.lFO）的特点，即最后入栈的元素最先出栈。栈的基本运算包括入栈和出栈，其中入栈将一个元素放到栈顶，而出栈则将栈顶元素取出。1.栈的顺序存储栈的顺序存储可以使用数组实现。定义一个数组作为栈的存储空间，再定义一个指针top,指向栈顶元素的位置。初始时，top指向-1,表示栈为空。（1）初始化栈：将top置为-1,表示栈为空。（2）入栈操作：将元素压入栈顶，即将top加1,然后将元素存储在top所指向的位置。（3）出栈操作：将栈顶元素取出，即先将top指向的元素取出，然后将top减Io（4）获取栈顶元素：返回top指向的元素。1.栈的

12、链式存储栈的链式存储可以使用单向链表实现。定义一个节点表示栈的元素，包含一个数据域和一个指针域，指向下一个节点。再定义一个指针top,指向栈顶元素所在的节点。初始时，top指向空节点，表示栈为空。（I）初始化栈：将top置为空节点，表示栈为空。（2）入栈操作：新建一个节点，将元素存储在数据域中，然后将该节点的指针域指向top所指向的节点，最后将top指向新节点。（3）出栈操作：将top指向的节点取出，然后将top指向该节点的下一个节点。（4）获取栈顶元素：返回top指向的节点的数据域。8队列。队列的顺序存储（循环队列）和链式存储及其基本运算的实现。队列是一种常见的数据结构，它具有先进先出（Fl

13、Fo）的特点，即最先进入队列的元素最先出队列。队列的基本运算包括入队和出队，其中入队将一个元素加入队尾，而出队则将队头元素取出。1.队列的顺序存储（循环队列）队列的顺序存储可以使用数组实现，常见的是循环队列。定义一个数组作为队列的存储空间，再定义两个指针front和rear,分别指向队列的队头和队尾。初始时,front和rear均指向0,表示队列为空。（1）初始化队列：将front和rear均置为0,表示队列为空。（2）入队操作：将元素加入队尾，即将元素存储在rear所指向的位置，然后将rear加1。如果rear已经到达数组的末尾，还需要将rear置为0,实现循环队列的效果。（3）出队操作：将

14、队头元素取出，即先将front指向的元素取出，然后将front加1。如果front已经到达数组的末尾，还需要将front置为0,实现循环队列的效果。（4）获取队头元素：返回front指向的元素。1.队列的链式存储队列的链式存储可以使用单向链表实现。定义一个节点表示队列的元素，包含一个数据域和一个指针域，指向下一个节点。再定义两个指针front和rear,分别指向队列的队头和队尾所在的节点。初始时，front和rear均指向空节点，表示队列为空。（1）初始化队列：将front和rear均置为空节点，表示队列为空。（2）入队操作：新建一个节点，将元素存储在数据域中，然后将该节点的指针域指向空节点，

15、再将rear指向该节点。如果队列为空，还需要将front指向该节点。（3）出队操作：将front指向的节点取出，然后将front指向该节点的下一个节点。如果队列为空，返回错误信息。（4）获取队头元素：返叵front指向的节点的数据域。9串。串的基本运算的实现。串（String）是由零个或多个字符组成的有限序列，常见的表示方法是用单引号或双引号括起来的字符序列。在计算机中，串是一种基本数据类型，也是计算机程序中常用的数据类型之一。串的基本运算包括串的连接、求子串、串的比较、查找子串等。1.串的连接串的连接就是将两个串拼接起来，得到一个新的串。在程序中，可以使用循环或指针来实现串的连接。例如：c+QCopycodecharstl=hello”;charstr2=world*;charstr312;inti=0,j=0：while(strliI=0:)str3j+=strli+;)i=0;while(str2i!=0)str3j+=str2i+;)s3j=0;字符串末尾需要添加0表示结束1.求子串子串是原串中任意个连续字符组成的串。求子串的过程可以使用指针来实现，例如：charstr=l