《计算机软件技术基础》
（合肥工业大学
朱家诚）
2－1
第2章
21概述
常用数据结构及其运算
211什么是数据结构
数据结构是计算机应用方面的基础课程之一。要想有效地使用计算机，仅掌握计算机语言而缺乏数据结构和算法的有关知识是难以应付众多复杂的应用课题的。数据结构是研究非数据运算程序设计问题，也就是数据处理问题。即对数据集合中的各元素以各种方式进行运算，数据之间的关系、如何组织数据和如何高效地处理这些数据。
212有关数据结构的基本概念和术语
1．数据（data）数据是信息的载体，它可以用计算机表示并加工，如数、字符、符号等的集合。2．数据元素dataeleme
t数据元素是数据集合中的一个个体，是数据的基本单位。数据元素不一定是单个的数字或字符，它本身也可能是若干个数据项的集合。3．数据对象具有相同性质的数据元素的集合称为数据对象。4．数据结构是指同一数据对象中各数据元素间存在的关系SDR数据结构S是一个二元组，其中D是一个数据元素的非空有限集合，R是定义在D上的关系的非空有限集合。5．逻辑结构与物理结构逻辑结构是数据元素及其关系的数学特性——数据结构。物理结构是逻辑结构在计算机中的映象——存储结构。6．数据类型是指程序设计语言中允许的变量的类型。数据类型可分为基本数据类型和结构数据类型。7．数据结构与算法算法是解决某一特定类型问题的有限运算
f《计算机软件技术基础》
（合肥工业大学
朱家诚）
2－2
序列，算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表示形式有关，因此，数据结构的选择对数据处理的效率起着至关重要的作用。
数据结构＋算法＝程序213算法分析技术初步
1．时间复杂度常见的时间复杂度：这里用频度和时间复杂度这两个概念进行估算。常见的时间复杂度有：常量型、多项式型、对数型和指数型
2．空间复杂度空间复杂度是指在算法中所需的辅助空间单元。它们与问题尺寸
之间的关系。当与尺寸
无关时，空间复杂度：S
O1。时间与空间是一对矛盾，要节约空间往往就要消耗较多的时间。
22
线性表
在数据处理中，大量数据均以表格形式出现，称为线性表，它是一种最简单也是最常见的数据结构。
f《计算机软件技术基础》
（合肥工业大学
朱家诚）
2－3
221线性表定义和运算
（1）一维向量：（2）多维向量：（3）一般的表示形式为：
La1a2a
（4）结构特点：数据元素之间的关系是线性关系r