数据结构考研讲义
- 格式:docx
- 大小:1.53 MB
- 文档页数:66
计算机考研基础讲义数据结构基础数据结构是计算机科学中的一门基础课程,它研究的是数据的存储方式和组织方式,以及对数据进行操作和处理的方法。
在计算机考研中,数据结构是一个重要的考点,掌握好数据结构的基础知识对于考研复习和实际编程都有很大的帮助。
本文将介绍数据结构的基础知识,包括常见的数据结构类型和其应用场景。
首先,我们来了解一下数据结构的基本概念。
数据结构可以分为线性结构和非线性结构两种。
线性结构中的元素是一对一关系,如数组、链表等;而非线性结构中的元素存在一对多或多对多关系,如树、图等。
数据结构还可以分为静态结构和动态结构两种。
静态结构指的是一旦创建后就不能再改变其结构,而动态结构则可以根据需要动态地插入、删除元素。
下面,我们来介绍一些常见的数据结构类型及其应用场景。
1. 数组(Array)数组是一种线性结构,元素在内存中是连续存储的,可以通过索引快速访问元素。
数组适用于元素数量固定并且需要频繁访问的场景。
例如,存储学生的成绩、记录时间序列数据等。
2. 链表(Linked List)链表也是一种线性结构,元素在内存中不一定连续存储,而是通过指针相连。
链表适用于需要频繁插入和删除元素的场景,因为插入和删除操作只需要改变指针指向,不需要移动元素。
例如,实现栈和队列、实现高效的内存分配等。
3. 栈(Stack)栈是一种特殊的线性结构,只允许在一端进行插入和删除操作。
栈遵循先进后出(LIFO)的原则,在函数调用、括号匹配、表达式求值等场景中广泛应用。
4. 队列(Queue)队列也是一种特殊的线性结构,允许在一端插入元素,在另一端删除元素。
队列遵循先进先出(FIFO)的原则,常用于处理大量数据的场景,如任务调度、消息传递等。
5. 树(Tree)树是一种非线性结构,由节点和边组成。
树的特点是每个节点最多有一个父节点和多个子节点,节点之间存在层次关系。
树在文件系统、数据库索引、图形算法等方面有广泛的应用。
6. 图(Graph)图也是一种非线性结构,由节点和边组成。
802数据结构考研大纲摘要:1.数据结构基本概念与原理2.线性表及其操作3.栈、队列与层次结构4.树与图结构5.算法设计与分析6.排序与查找算法7.数据压缩与存储8.复试科目及招生目录变化正文:一、数据结构基本概念与原理数据结构是计算机科学与技术领域中的一门基础课程,主要研究计算机数据的组织、存储、操作和处理。
本部分内容包括数据结构的基本概念、基本原理和基本方法。
要求掌握数据的逻辑结构、存储结构及其基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析。
二、线性表及其操作线性表是一种基本的数据结构,它具有线性特征,元素之间只有一对一的关系。
本部分内容主要涉及线性表的定义、操作及其应用,如插入、删除、查找等。
要求深刻理解线性表的原理,并能应用相关知识点解决实际问题。
三、栈、队列与层次结构栈、队列和层次结构是计算机中常见的数据结构。
栈与队列分别遵循后进先出(LIFO)和先进先出(FIFO)原则,层次结构则主要用于构建树形结构。
本部分内容要求掌握栈、队列的基本操作及其应用,了解层次结构的特点,并能解决相关问题。
四、树与图结构树与图是复杂度较高的数据结构,它们在计算机科学中有着广泛的应用。
树结构具有层次特点,图结构则由节点和边组成。
本部分内容主要研究树与图的遍历、查找、最短路径等问题,要求熟练掌握树与图的基本概念和算法。
五、算法设计与分析算法设计是计算机科学的核心内容,它关注如何高效地解决问题。
本部分内容要求掌握算法设计的基本方法,如贪心、分治、动态规划等,并能对算法进行高效性分析。
六、排序与查找算法排序和查找是计算机中常见的算法,它们在数据处理方面具有重要意义。
本部分内容要求掌握各种排序算法(如冒泡、快速、归并等)和查找算法(如顺序、二分、哈希等),并能根据实际需求选择合适的算法。
七、数据压缩与存储数据压缩与存储技术在计算机领域具有重要应用价值。
本部分内容要求掌握数据压缩的基本原理和方法,如霍夫曼编码、算术编码等,以及数据存储的技术和策略。
目录绪论30。
1 基本概念3第一章线性表51。
1 线性表的定义51。
2 线性表的实现51.2.2 线性表的链式存储结构8第二章栈、队列和数组162。
1 栈162。
2 队列212。
3 特殊矩阵的压缩存储232.3.1 数组232。
3。
2 特殊矩阵24第三章树与二叉树263。
1 树的概念261。
树的定义262.相关术语273.2 二叉树273。
2.1 定义与性质273.2。
2 二叉树的存储293.2.3 二叉树的遍历303。
2。
4 线索二叉树353。
3 树和森林393。
3。
1 树的存储结构393。
3.2 森林和二叉树的转换4013。
3。
3 树和森林的遍历403.4 哈夫曼(Huffman)树和哈夫曼编码42第四章图434.1 图的概念434。
2 图的存储及基本操作444。
2。
1 邻接矩阵444.2。
2 邻接表454.3 图的遍历474。
3。
1 深度优先搜索474。
3。
2 广度优先搜索484。
4 图的基本应用494。
4.1 最小生成树494.4。
2 最短路径504.4.3 拓扑排序534。
4。
4 关键路径54第五章查找565。
1 查找的基本概念565。
2 顺序查找法575。
3 折半查找法585.4 动态查找树表605.4。
1 二叉排序树605.4.2 平衡二叉树635.4.3B 树及其基本操作、B+树的基本概念665.5 散列表675.5。
2 常用的散列函数6825。
5.3 处理冲突的方法695。
5.4 散列表的查找705.5.5 散列表的查找分析71第六章排序726.1 插入排序726.1.1 直接插入排序726。
1.2 折半插入排序736.2 冒泡排序736。
3 简单选择排序746。
4 希尔排序756.5 快速排序766.6 堆排序786.7 二路归并排序806。
8 基数排序816。
9 各种内部排序算法的比较82绪论0。
1 基本概念1、数据结构数据结构是指互相之间存在着一种或多种关系的数据元素的集合.数据结构是一个二元组Data_Structure =(D,R),其中,D 是数据元素的有限集,R 是D 上关系的有限集.32、逻辑结构:是指数据之间的相互关系。
《数据结构》讲义间存在的关系———产生背景。
1.1 什么是数据结构计算机解题步骤:建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。
其中建立数学模型的实质:找出操作对象之间的关系。
例1. 图书馆书目检索——对应线性关系例2. 博奕树——对应树型关系例3. 交叉路口交通灯管理——对应图状结构。
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。
(地位)1.2 数据结构的基本概念和术语1. 数据(Data)数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
换句话说,数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述;是计算机加工处理的对象。
包括数值、字符、声音、图象等。
2. 数据元素(Data Element)数据元素是组成数据的基本单位, 是数据集合的个体,在计算机中通常作为一个逻辑整体进行考虑和处理。
一个数据元素可由若干个数据项组成(Data Item)。
3. 数据对象(Data Object)数据对象是性质相同的数据元素的集合,是数据的一个子集。
例如:整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={′A′,′B′,…,′Z′},表1-1所示的学籍表也可看作一个数据对象。
由此可看出,不论数据元素集合是无限集(如整数集)、有限集(如字符集),还是由多个数据项组成的复合数据元素(如学籍表),只要性质相同,都是同一个数据对象。
综上1~3所述,再分析数据概念:4. 结构(Data Structure)数据元素相互之间的关系称为结构( Structure ),有四种基本结构。
(1) 集合结构:结构中的数据元素之间除了同属于一个集合的关系外,无任何其它关系。
(2) 线性结构:结构中的数据元素之间存在着一对一的线性关系。
(3) 树形结构:结构中的数据元素之间存在着一对多的层次关系。
数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
换句话说,数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述;是计算机加工处理的对象。
包括数值、字符、声数据元素是组成数据的基本单位一个数据元素可由若干个数据项组成()数据对象是性质相同的数据元素的集合,是数据的一个子集。
…},字母字符数据对象是集合象。
由此可看出,不论数据元素集合是无限集(如整数集)Data Structure)数据元素相互之间的关系称为结构( Structure ),有四种基本结构。
集合结构:结构中的数据元素之间除了同属于一个集合的关系外,无任何其它关系。
线性结构:结构中的数据元素之间存在着一对一的线性关系。
图状结构或网状结构:结构中的数据元素之间存在着多对多的任意关系。
为数据结构的有限集,S是D上关系的有限集。
表示复数的虚部。
存储结构(又称物理结构)是逻辑结构在计算机中的存储映象,是逻辑结构在计算机中的实现,它包括据元素的表示和关系的表示形式化描述:要存入机器中,建立一从,使S(D逻辑结构与存储结构的关系为:数据结构的内容可归纳为三个部分:逻辑结构、存储结构和运算集合。
按某种逻辑关系组织起来的一批数据,按一定的映象方式把它存放在计算机的存储器中,并在这些数据上定义了一个运算的集合,(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称合,即该类型的取值范围,以及该类型中可允许使用的一组运算。
例如高级语言中的数据类型就是已经实现的从这个意义上讲,数据类型是高级语言中允许的变量种类,计算机中使用的是二进制数,汇编语言中则可给出各种数据的十进制表示,如二进制数据的抽象; 使用者在编程时可以直接使用据抽象,出现了数据类型,(Abstract Data Type))是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。
抽象数据类型的定义取决于客观存在的一组逻辑特性,而与其在计算机内如何表示和实现无关,即不论其内部结构如何变化,只要它的数学特性不变,都不影响其外部使用。
目录绪论 (3)0.1 基本概念 (3)第一章线性表 (4)1.1 线性表的定义 (4)1.2 线性表的实现 (4)1.2.2 线性表的链式存储结构 (6)第二章栈、队列和数组 (11)2.1 栈 (11)2.2 队列 (15)2.3 特殊矩阵的压缩存储 (17)2.3.1 数组 (17)2.3.2 特殊矩阵 (17)第三章树与二叉树 (20)3.1 树的概念 (20)1.树的定义 (20)2.相关术语 (20)3.2 二叉树 (21)3.2.1 定义与性质 (21)3.2.2 二叉树的存储 (22)3.2.3 二叉树的遍历 (23)3.2.4 线索二叉树 (25)3.3 树和森林 (29)3.3.1 树的存储结构 (29)3.3.2 森林和二叉树的转换 (30)3.3.3 树和森林的遍历 (30)3.4 哈夫曼(Huffman)树和哈夫曼编码 (31)第四章图 (32)4.1 图的概念 (32)4.2 图的存储及基本操作 (33)4.2.1 邻接矩阵 (33)4.2.2 邻接表 (33)4.3 图的遍历 (35)4.3.1 深度优先搜索 (35)4.3.2 广度优先搜索 (35)4.4 图的基本应用 (37)4.4.1 最小生成树 (37)4.4.2 最短路径 (37)4.4.3 拓扑排序 (39)4.4.4 关键路径 (40)第五章查找 (42)5.1 查找的基本概念 (42)5.2 顺序查找法 (43)5.3 折半查找法 (44)5.4 动态查找树表 (45)5.4.1 二叉排序树 (45)5.4.2 平衡二叉树 (47)5.4.3 B 树及其基本操作、B+树的基本概念 (49)5.5 散列表 (51)5.5.2 常用的散列函数 (51)5.5.3 处理冲突的方法 (52)5.5.4 散列表的查找 (52)5.5.5 散列表的查找分析 (53)第六章排序 (54)6.1 插入排序 (54)6.1.1 直接插入排序 (54)6.1.2 折半插入排序 (54)6.2 冒泡排序 (56)6.3 简单选择排序 (57)6.4 希尔排序 (58)6.5 快速排序 (59)6.6 堆排序 (61)6.7 二路归并排序 (63)6.8 基数排序 (64)6.9 各种内部排序算法的比较 (65)绪论0.1 基本概念1、数据结构数据结构是指互相之间存在着一种或多种关系的数据元素的集合。
数据结构是一个二元组Data_Structure =(D,R),其中,D 是数据元素的有限集,R 是D 上关系的有限集。
2、逻辑结构:是指数据之间的相互关系。
通常分为四类结构:(1)集合:结构中的数据元素除了同属于一种类型外,别无其它关系。
(2)线性结构:结构中的数据元素之间存在一对一的关系。
(3)树型结构:结构中的数据元素之间存在一对多的关系。
(4)图状结构:结构中的数据元素之间存在多对多的关系。
3、存储结构:是指数据结构在计算机中的表示,又称为数据的物理结构。
通常由四种基本的存储方法实现:(1)顺序存储方式。
数据元素顺序存放,每个存储结点只含一个元素。
存储位置反映数据元素间的逻辑关系。
存储密度大。
但有些操作(如插入、删除)效率较差。
(2)链式存储方式。
每个存储结点除包含数据元素信息外还包含一组(至少一个)指针。
指针反映数据元素间的逻辑关系。
这种方式不要求存储空间连续,便于动态操作(如插入、删除等),但存储空间开销大(用于指针),另外不能折半查找等。
(3)索引存储方式。
除数据元素存储在一组地址连续的内存空间外,还需建立一个索引表,索引表中索引指示存储结点的存储位置(下标)或存储区间端点(下标)。
(4)散列存储方式。
通过散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将散列函数的值解释成关键字所在元素的存储地址。
其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。
2 算法和算法的衡量1、算法是对特定问题求解步骤的一种描述,是指令的有限序列。
其中每一条指令表示一个或多个操作。
算法具有下列特性:⑴有穷性⑵确定性⑶可行性⑷输入⑸输出。
算法和程序十分相似,但又有区别。
程序不一定具有有穷性,程序中的指令必须是机器可执行的,而算法中的指令则无此限制。
算法代表了对问题的解,而程序则是算法在计算机上的特定的实现。
一个算法若用程序设计语言来描述,则它就是一个程序。
2、算法的时间复杂度:以基本运算的原操作重复执行的次数作为算法的时间度量。
一般情况下,算法中基本运算次数T(n)是问题规模n(输入量的多少,称之为问题规模)的某个函数f(n),记作:T(n) =Ο(f(n));也可表示T(n) =m(f(n)),其中m 为常量。
记号“O”读作“大O”,它表示随问题规模n 的增大,算法执行时间T(n)的增长率和f(n)的增长率相同。
注意:有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。
常见的渐进时间复杂度有:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<Ο(2n) <O(n!) <O(nn)。
3、算法的空间复杂度:是对一个算法在运行过程中临时占用的存储空间大小的量度。
只需要分析除输入和程序之外的辅助变量所占额外空间。
原地工作:若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作,空间复杂度为O(1)。
第一章线性表1.1 线性表的定义线性表是一种线性结构,在一个线性表中数据元素的类型是相同的,或者说线性表是由同一类型的数据元素构成的线性结构,定义如下:线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列,通常记为:(a1,a2,…ai-1,ai,ai+1,…an)其中n为表长,n=0 时称为空表。
需要说明的是:ai为序号为i 的数据元素(i=1,2,…,n),通常将它的数据类型抽象为ElemType,ElemType根据具体问题而定。
1.2 线性表的实现1.2.1 线性表的顺序存储结构1.顺序表线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素,用这种存储形式存储的线性表称其为顺序表。
因为内存中的地址空间是线性的,因此,用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单又自然的。
设a1的存储地址为Loc(a1),每个数据元素占d个存储地址,则第i个数据元素的地址为:Loc(ai)=Loc(a1)+(i-1)*d 1≤i≤n这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来,这也是顺序表具有按数据元素的序号随机存取的特点。
线性表的动态分配顺序存储结构:#define LIST_INIT_SIZE 100 //存储空间的初始分配量#define LISTINCREMENT 10 //存储空间的分配增量typedef struct{ElemType *elem; //线性表的存储空间基址int length; //当前长度int listsize; //当前已分配的存储空间}SqList;2.顺序表上基本运算的实现(1)顺序表的初始化顺序表的初始化即构造一个空表,这对表是一个加工型的运算,因此,将L设为引用参数,首先动态分配存储空间,然后,将length置为0,表示表中没有数据元素。
int Init_SqList (SqList &L){L.elem = (ElemType * )malloc(LIST_INIT_SIZE * sizeof(ElemType));if (!L.elem) exit (OVERFLOW); //存储分配失败L.length=0;L. listsize = LIST_INIT_SIZE; //初始存储容量return OK;}(2)插入运算线性表的插入是指在表的第i(i的取值范围:1≤i≤n+1)个位置上插入一个值为x 的新元素,插入后使原表长为n的表:(a1,a2,... ,ai-1,ai,ai+1,... ,an)成为表长为n+1 表:(a1,a2,...,ai-1,x,ai,ai+1,...,an ) 。
顺序表上完成这一运算则通过以下步骤进行:①将ai~an 顺序向下移动,为新元素让出位置;(注意数据的移动方向:从后往前依次后移一个元素)②将x 置入空出的第i个位置;③修改表长。
int Insert_SqList (SqList &L,int i,ElemType x){if (i < 1 || i > L.length+1) return ERROR; // 插入位置不合法if (L.length >= L.listsize) return OVERFLOW; // 当前存储空间已满,不能插入//需注意的是,若是采用动态分配的顺序表,当存储空间已满时也可增加分配q = &(L.elem[i-1]); // q 指示插入位置for (p = &(L.elem[L.length-1]); p >= q; --p)*(p+1) = *p; // 插入位置及之后的元素右移*q = e; // 插入e++L.length; // 表长增1return OK;}顺序表上的插入运算,时间主要消耗在了数据的移动上,在第i个位置上插入x ,从ai 到an 都要向下移动一个位置,共需要移动n-i+1个元素。
(3)删除运算线性表的删除运算是指将表中第i (i 的取值范围为:1≤i≤n)个元素从线性表中去掉,删除后使原表长为n 的线性表:(a1,a2,... ,ai-1,ai,ai+1,...,an)成为表长为n-1 的线性表:(a1,a2,... ,ai-1,ai+1,... ,an)。
顺序表上完成这一运算的步骤如下:①将ai+1~an 顺序向上移动;(注意数据的移动方向:从前往后依次前移一个元素)②修改表长。
int Delete_SqList (SqList &L;int i) {if ((i < 1) || (i > L.length)) return ERROR; // 删除位置不合法p = &(L.elem[i-1]); // p 为被删除元素的位置e = *p; // 被删除元素的值赋给eq = L.elem+L.length-1; // 表尾元素的位置for (++p; p <= q; ++p)*(p-1) = *p; // 被删除元素之后的元素左移--L.length; // 表长减1return OK;}顺序表的删除运算与插入运算相同,其时间主要消耗在了移动表中元素上,删除第i个元素时,其后面的元素ai+1~an 都要向上移动一个位置,共移动了n-i 个元素,顺序表的插入、删除需移动大量元素O(n);但在尾端插入、删除效率高O(1)。