第01章算法与数据结构基础.pdf
- 格式:pdf
- 大小:11.22 MB
- 文档页数:76
算法与数据结构学习指导第一章第1章概述讲课提要【主要内容】1.数据结构的研究目的和研究内容2.数据结构中的几个重要概念和术语3.算法设计的基本要求以及算法复杂度的分析和计算方法【教学目标】1.了解数据结构的研究目的和研究内容2.掌握数据结构中的重要概念和术语3.掌握算法设计的基本要求以及算法复杂度的分析和计算方法【所需课时】2次课。
[第一次课]1.数据结构的研究目的和研究内容2.数据结构中的重要概念和术语[第二次课]3.算法设计的基本要求以及算法复杂度的分析和计算方法学习指导1.概念和术语数据:是能输入到计算机中并能被计算机程序处理的符号的总称。
数据元素:是数据的基本单位,它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。
一个数据元素可由若干数据项组成。
数据对象:是具有相同特征的数据元素的集合,是数据的一个子集。
数据结构:是数据元素的组织形式,或数据元素相互之间存在一种或多种特定关系的集合。
数据的逻辑结构:是指数据结构中数据元素之间的逻辑关系。
数据的存储结构:是数据的逻辑结构在计算机内存中的存储方式,又称物理结构。
数据类型:是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。
抽象数据类型:是指一个数学模型以及在该模型上定义的一套运算规则的集合。
算法:建立在数据结构基础上的,为解决问题而采取的步骤和方法。
2.逻辑结构的四种基本形态根据数据元素之间关系的不同特征,通常有下列四类基本结构:(1)集合:结构中的数据元素间除了“同属于一个集合”的关系外,别无其它关系。
(2)线性结构:结构中的数据元素之间存在一个对一个的关系。
(3)树型结构:结构中的数据元素之间存在一个对多个的关系。
(4)图型结构或网状结构:结构中的数据元素之间存在多个对多个的关系。
3.数据存储结构的基本组织方式数据存储结构有顺序和链式两种方式。
(1)顺序存储结构的特点:要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系,常用高级编程语言中的“一维数组”来描述或实现。
数据结构与算法第一节数据结构及算法概述一、数据结构图、四类基本结构的示意图【要点】 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 头结点百结点尾结点【留意】与单链表的插入和删除操作不同的是,在双链表中插入和删除须同时修改两个方向上的指针。
第三节栈和队列一、栈栈是一种“特别的”线性表,这种线性表中的插入和删除运算限定在表的某一端进行。
不含任何数据元素的栈称为空栈。