当前位置：文档之家 › 数据结构课程教程第一章

数据结构课程教程第一章

  • 格式：ppt
  • 大小：679.00 KB
  • 文档页数：54

下载文档原格式

  / 54

合集下载

精品课件-数据结构教程(胡元义)-第1章

精品课件-数据结构教程(胡元义)-第1章
(4) 哈希(或散列)存储结构：此方法的基本思想是根据 数据元素的关键字通过哈希(或散列)函数直接计算出该数据元 素的存储地址。
第1章 绪论
顺序存储结构的主要优点是节省存储空间，即分配给数据 的存储单元全部用于存放数据元素的数据信息，数据元素之间 的逻辑关系没有占用额外的存储空间。采用这种存储结构可以 实现对数据元素的随机存取，即每个数据元素对应有一个序号， 并由该序号可以直接计算出数据元素的存储地址(例如对于数 组A其序号为数组元素的下标，数组元素A[i]可以通过*(A+i) 进行存取)。但顺序存储结构的主要缺点是不便于修改，对数 据元素进行插入、删除运算时，可能要移动一系列的数据元素。
第1章 绪论
(1) 分析阶段：分析实际问题，从中抽象出一个数学模 型。
(2) 设计阶段：设计出解决数学模型的算法。 (3) 编程阶段：用适当的编程语言编写出可执行的程序。 (4) 测试阶段：测试、修改直到得到问题的解答。 数据结构课程集中讨论软件开发过程中的设计阶段，同时 涉及分析阶段和编程阶段的若干基本问题。此外，为了构造出 好的数据结构及其实现，还需考虑数据结构及其实现的评价与 选择。因此，数据结构课程的内容包括了如表1.1所示的数据 表示和数据处理方面所对应的3个层次。
第1章 绪论
1.2.2 存储结构 数据的存储结构是数据结构在计算机中的表示方法，也即
数据的逻辑结构到计算机存储器的映像，包括数据结构中数据 元素的表示以及数据元素之间关系的表示。数据元素及数据元 素之间的关系在计算机中可以有以下四种基本存储结构：
(1) 顺序存储结构：借助于数据元素在存储器中的相对 位置来表示数据元素之间的逻辑关系。通常顺序存储结构是利 用程序语言中的数组来描述的。
第1章 绪论

大学《数据结构教程》(第5版) 李春葆 清华大学出版社课件第1章 绪论

大学《数据结构教程》(第5版) 李春葆 清华大学出版社课件第1章 绪论

存储结构
3）索引存储结构 P8 4）哈希（或散列）存储结构 P8
数据运算
数据的运算主要有修改、插入、删 除、查找、排序。
1.1.3 数据结构课程的内容
数据结构的内容可归纳为三个部分：逻辑 结构、存储结构和数据运算。
1.2 数据类型和抽象数据类型 1.2.1 数据类型 1.2.2 抽象数据类型
1.1.1 数据结构的研究内容
数据结构主要研究非数值计算问题。 （多种复杂的具有一定结构关系的数 据）
非数值计算问题：
例1-1 电话号码查询问题： 电话号码薄(a1,b1)(a2,b2)…..(an,bn) 其中：ai为某人姓名，bi为该人的电话号码； 要求：设计一个算法，给定一个姓名时能查出 此人的电话号码？
例如，若T(n)=n(n+1)/2,则有 T(n)/n2=1/2+1/n， 当n∞时，T(n)/n2=1/2故它的时间复杂度为Ｏ (n2), 即Ｔ(n)与n2 数量级相同。
显然,被称做问题的基本操作的原操作应是其 重复执行次数与算法的执行时间成正比的原 操作;
多数情况下，它就是最深层循环内的语句中 的原操作，它的执行次数和包含它的语句频 度相同。
语句的频度指的是该语句的重复执行的次数
一般情况下,对一个问题(或一类算法)只需选 择一种基本操作来讨论算法的时间复杂度即 可
【例1-7】
++x; s=0;
时间复杂度为O(1)。
没有循环语句，其基本运算次数与问题规 模无关，称为常数阶，记作O(1)。
【例1-8】
for(i =1;i<=n;++i) {
• 数据元素（Data Element）：是数据的基本单位。
• 数据项（Data Item）： 是组成数据元素的、有独立含 义、不可分割的最小单位。

《数据结构》教程c语言版

《数据结构》教程c语言版

《数据结构》第五版清华大学自动化系李宛洲2004年5月目录第一章数据结构--概念与基本类型 (6)1.1概述 (6)1.1.1数据结构应用对象 (6)1.1.2学习数据结构的基础 (7)1.1.2.1 C语言中的结构体 (7)1.1.2.2 C语言的指针在数据结构中的关联作用 (8)1.1.2.3 C语言的共用体(union)数据类型 (12)1.1.3数据结构定义 (15)1.2线性表 (17)1.2.1 顺序表 (18)1.2.2 链表 (20)1.2.2.1链表的基本结构及概念 (20)1.2.2.2单链表设计 (22)1.2.2.3单链表操作效率 (29)1.2.2.4双链表设计 (30)1.2.2.5链表深入学习 (32)1.2.2.6稀疏矩阵的三元组与十字链表 (36)1.2.3 堆栈 (41)1.2.3.1堆栈结构 (41)1.2.3.2基本操作 (42)1.2.3.3堆栈与递归 (44)1.2.3.4递归与分治算法 (45)1.2.3.5递归与递推 (49)1.2.3.6栈应用 (52)1.2.4 队列 (57)1.2.4.1队列结构 (57)1.2.3.2队列应用 (59)1.3非线性数据结构--树 (64)1.3.1 概念与术语 (64)1.3.1.1引入非线性数据结构的目的 (64)1.3.1.2树的定义与术语 (65)1.3.1.3树的内部节点与叶子节点存储结构问题 (66)1.3.2 二叉树 (66)1.3.2.1二叉树基本概念 (66)1.3.2.2完全二叉树的顺序存储结构 (68)1.3.2.3二叉树遍历 (69)1.3.2.4二叉树唯一性问题 (71)1.3.3 二叉排序树 (72)1.3.3.1基本概念 (72)1.3.3.2程序设计 (73)1.3.4 穿线二叉树 (79)1.3.4.1二叉树的中序线索化 (80)1.3.4.2中序遍历线索化的二叉树 (81)1.3.5 堆 (82)1.3.5.1建堆过程 (83)1.3.5.2在堆中插入节点 (85)1.3.6 哈夫曼树 (86)1.3.6.1最佳检索树 (86)1.3.6.2哈夫曼树结构与算法 (88)1.3.6.3 哈夫曼树应用 (90)1.3.6.4哈夫曼树程序设计 (92)1.3.7 空间数据结构----二叉树深入学习导读 (95)1.3.7.1k-d树概念 (96)1.3.7.2k-d树程序设计初步 (97)1.4非线性数据结构--图 (100)1.4.1图的基本概念 (100)1.4.2图形结构的物理存储方式 (103)1.4.2.1相邻矩阵 (103)1.4.2.2图的邻接表示 (104)1.4.2.3图的多重邻接表示 (106)1.4.3图形结构的遍历 (107)1.4.4无向连通图的最小生成树（minimum-cost spanning tree:MST） (110)1.4.5有向图的最短路径 (113)1.4.5.1单源最短路径（single-source shortest paths） (113)1.4.5.2每对顶点间最短路经（all-pairs shortest paths） (116)1.4.6拓扑排序 (117)第二章检索 (123)2.1顺序检索 (123)2.2对半检索 (124)2.2.1 对半检索与二叉平衡树 (124)2.2.2对半检索思想在链式存储结构中的应用---跳跃表 (127)2.3分块检索 (133)2.4哈希检索 (134)2.4.1哈希函数 (135)2.4.2闭地址散列 (136)2.4.2.1线性探测法和基本聚集问题 (136)2.4.2.2删除操作造成检索链的中断问题 (138)2.4.2.3随机探测法 (139)2.4.2.4平方探测法 (140)2.4.2.5二次聚集问题与双散列探测方法 (141)2.4.3开地址散列 (142)2.4.4哈希表检索效率 (142)第三章排序 (145)3.1交换排序方法 (145)3.1.1直接插入排序 (145)3.1.2冒泡排序 (147)3.1.3 选择排序 (148)3.1.4 树型选择排序 (149)3.2S HELL排序 (150)3.3快速排序 (152)3.4堆排序 (154)3.5归并排序 (156)3.6数据结构小结 (159)3.6.1 数据结构的基本概念 (159)3.6.2 数据结构分类 (159)3.6.2.1数据结构中的指针问题 (160)3.6.2.2线性表的效率问题 (161)3.6.2.3二叉树 (161)3.6.3排序与检索 (161)3.7算法分析的基本概念 (162)3.7.1基本概念 (162)3.7.2上限分析 (164)3.7.3下限分析 (164)3.7.4空间代价与时间代价转换 (165)第6章高级数据结构内容--索引技术 (167)6.1基本概念 (167)6.2线性索引 (168)6.2.1 线性索引 (168)6.2.2 倒排表 (169)6.32-3树 (170)6.3.1 2-3树定义 (172)6.3.2 2-3树节点插入 (173)6.4B+树 (178)6.4.1 B+树定义 (178)6.4.2 B+树插入与删除 (180)6.4.3 B+树实验设计 (182)第一章数据结构--概念与基本类型1.1概述1.1.1数据结构应用对象计算机应用可以分为两大类，一类是科学计算和工业控制，另一类是商业数据处理。

《数据结构教程》第一章 绪论

《数据结构教程》第一章 绪论

《数据结构教程》第一章绪论数据结构教程第一章绪论数据结构是计算机科学中的重要概念之一，它是计算机程序设计的基础。

本教程的第一章将介绍数据结构的基本概念和作用。

一、什么是数据结构？在计算机科学中，数据结构用于存储和组织数据，以便在计算机程序中进行高效的操作。

数据结构可以分为两种基本类型：线性数据结构和非线性数据结构。

1.1 线性数据结构线性数据结构是最简单的数据结构之一，它将数据元素按照线性顺序组织，可以使用一对一的关系连接数据元素。

常见的线性数据结构有数组、链表和栈。

1.2 非线性数据结构非线性数据结构是指数据元素之间存在多对多的关系，不是简单的一对一关系。

常见的非线性数据结构有树和图。

二、数据结构的作用数据结构的设计和选择对于程序的效率和性能具有重要影响。

合理选择数据结构可以提高算法的执行速度，降低计算机资源的占用。

2.1 提高数据的存储效率通过选择适当的数据结构可以减少内存的占用，提高数据的存储效率。

例如，链表数据结构可以动态地分配内存空间，减少内存的浪费。

2.2 提高数据的访问效率不同的数据结构在数据的访问效率上有所差异。

例如，对于需要频繁插入和删除操作的场景，链表数据结构比数组数据结构更加高效。

2.3 优化算法的执行速度数据结构和算法是相辅相成的，通过选择合适的数据结构可以优化算法的执行速度。

例如，在查找操作中使用二叉搜索树可以降低时间复杂度。

三、数据结构的分类根据数据结构的存储方式和操作特性，可以将数据结构分为线性数据结构和非线性数据结构。

3.1 线性数据结构线性数据结构是最常用的数据结构之一，它将数据元素按照线性顺序排列，每个元素有一个直接前驱和直接后继。

常见的线性数据结构有数组、链表和栈。

3.1.1 数组数组是一种最简单的数据结构，它将数据元素存储在连续的内存空间中。

数组的访问速度很快，但是插入和删除操作的效率较低。

3.1.2 链表链表是一种动态数据结构，它通过指针将数据元素链接在一起。

大学数据结构教案第一章

大学数据结构教案第一章

教学目标：1. 理解数据结构的基本概念和重要性。

2. 掌握数据结构的逻辑结构和物理结构。

3. 了解数据结构的学习方法和应用领域。

教学重点：1. 数据结构的概念和重要性。

2. 逻辑结构和物理结构的基本概念。

教学难点：1. 数据结构的逻辑结构和物理结构的理解。

2. 数据结构的学习方法和应用领域的掌握。

教学准备：1. 教学课件。

2. 相关教材和参考资料。

3. 实例分析。

教学过程：一、导入1. 通过一个简单的例子（如学生信息管理系统），引出数据结构的概念。

2. 提问：在学生信息管理系统中，我们如何存储和操作学生信息？二、讲授新课1. 数据结构的概念- 数据结构是计算机存储、组织数据的方式。

- 数据结构是计算机科学中的重要基础，是解决复杂问题的有力工具。

2. 数据结构的重要性- 提高数据存储和处理的效率。

- 优化算法设计和分析。

- 促进软件开发和工程实践。

3. 逻辑结构和物理结构- 逻辑结构：描述数据之间的逻辑关系，如线性结构、非线性结构等。

- 物理结构：描述数据在计算机中的存储方式，如数组、链表、树等。

4. 数据结构的学习方法- 理论与实践相结合。

- 注重算法设计和分析。

- 学习经典数据结构及其应用。

5. 数据结构的应用领域- 软件开发。

- 数据库系统。

- 网络通信。

- 图像处理。

三、实例分析1. 以学生信息管理系统为例，分析数据结构的实际应用。

2. 引导学生思考：如何设计合适的数据结构来存储和操作学生信息？四、课堂小结1. 总结本章内容，强调数据结构的基本概念和重要性。

2. 鼓励学生课后继续学习，掌握数据结构的逻辑结构和物理结构。

五、作业布置1. 阅读教材相关内容，理解数据结构的逻辑结构和物理结构。

2. 完成课后习题，巩固所学知识。

教学反思：1. 本节课通过实例分析，使学生更加直观地理解数据结构的概念和应用。

2. 在教学过程中，注重启发式教学，引导学生主动思考。

3. 在课后作业布置中，注重理论与实践相结合，提高学生的动手能力。

《数据结构》第一章重点知识梳理

《数据结构》第一章重点知识梳理
12
第一章 绪论
求绝对值 abs（表达式） 求不足整数值 floor（表达式） 求进位整数值 ceil（表达式） 判定文件结束 eof（文件变量） （10）逻辑运算 与运算&&：对于A&&B，当A的值为0时，不在对B求值。 或运算||：对于A||B，当A的值为非0时，不在对B求值。 四、算法和算法分析 1．算法 （1）算法的定义
由于算法的时间复杂度考虑的只是对于问题规模n的增长率，因此在难以精确计算基本操作 执行次数（或语句频度）的情况下，只需求出它关于n的增长率或阶即可。 4．算法的存储空间需求
类似于算法的时间复杂度，以空间复杂度（spacecomplexity）作为算法所需存储空间的量 度，记作S（n）=O（f（n））其中n为问题的规模。
18
的表示。
①元素的表示。计算机数据元素用一个由若干位组合 起来形成的一个位串表示。
图1-1四类基本结构的关系图。
5
第一章 绪论
②关系的表示。 计算机中数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象。 并由这两种不同的表示方法得到两种不同的存储结构：顺序存储结构和链式存储结构。 a．顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 b．非顺序映象的特点是借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑
数据元素（dataelement）是数据的基本单位，在计算机程序中通常作为一个整体进行考 虑和处理。
3
第一章 绪论
3．数据对象 数据对象（dataobject）是性质相同的数据元素的集合，是数据的一个子集。
4．数据结构 数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的集合。 （1）数据结构的基本结构 根据数据元素之间关系的不同特性，通常有下列四类基本结构： ①集合。数据元素之间除了“同属于一个集合”的关系外，别无其它关系。 ②线性结构。数据元素之间存在一个对一个的关系。 ③树形结构。数据元素之间存在一个对多个的关系。 ④图状结构或网状结构。数据元素之间存在多个对多个的关系。

数据结构(第1章)讲义


树
01
02
03
树的定义
树是一种递归定义的数据 结构，其中每个节点可以 有多个子节点，但只有一 个父节点。
树的性质
树具有层次性、有序性和 无环性等性质。
树的表示方法
树可以使用多种方式表示， 如嵌套结构、邻接矩阵等。
森林
森林的定义
森林是由若干棵树组成的集合， 其中每棵树都是一个独立的数据
结构。
森林的性质
社交网络
社交网络中需要处理大量的用户关系和信息，数 据结构在其中发挥着重要的作用。例如，使用图 数据结构可以表示用户之间的关系，使用哈希表 可以快速查找用户信息。
THANKS FOR WATCHING
感谢您的观看
05 排序与查找
排序算法
• 冒泡排序：通过重复地遍历待排序的数列，比较相邻的两个元素，若它们的顺 序错误则交换它们，直到没有需要交换的元素为止。
• 选择排序：在未排序的序列中找到最小（或最大）的元素，存放到排序序列的 起始位置，然后再从剩余未排序的元素中继续寻找最小（或最大）元素，然后 放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值 大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同 样从中间元素开始比较。 • 哈希查找：通过哈希函数将关键字转化为数组下标，然后在对应的数组下标位 置上进行查找。 • 二叉查找树查找：在二叉查找树中进行查找，从根节点开始，如果当前节点的 关键字等于目标值，则查找成功；如果当前节点的关键字大于目标值，则在左 子树中继续查找；如果当前节点的关键字小于目标值，则在右子树中继续查找 。
• 插入排序：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、 个数加一的有序数据。

数据结构 第一章概论


注意：常用DataType表示抽象元素类型。
H
13
1.3 算法和算法分析
数据的运算是通过算法描述的。
1.算法----求解一个特定任务的指令的有限序列。
例.求a[0..n-1]中n个数的平均值(假定n>0)。
float average(float a[ ],int n)
{ int i；float s=0.0； //累加器赋初值
8. }
其中:f(m,n)=1+m+2*m*n+m=2mn+2m+1
当m=n时,f(n)=2n2+2n+1
T(n)=O(f(n))=O(2n2+2n+1)=O(n2) 平方阶。
对嵌套层次的循环结构，时间的复杂度T(n)由最内 层循环体语句的频度f(n)决定。
H
22
例4 分析下面的算法
1. void sum(int n)
其中：D1，D3是有穷集，D2是无穷集。
5.抽象数据对象
ElemSet={某种同类型的数据元素}
H
8
6.数据结构(data structure)----
数据之间的相互关系，即数据的组织形式。 内容包括：数据逻辑结构、数据存储结构和数据运算。
数据逻辑结构：数据元素之间的逻辑关系。 数据存储结构：数据元素及其关系在存储器中的存储表示。 数据运算：定义在数据逻辑结构上的操作。如：查询，插入，
(4)
for (k=0；k<n；k++)
n2(n+1)
(5)
c[i][j]=c[i][j]+a[i][k]*b[k][j]； n3
}
}
算法所消耗的时间就是所有语句频度之和T(n):

数据结构-第一章 绪论

计算机专业学生的必修课程课程编号课程名称需要的先导课程编号c1程序设计基础无c2离散数学c1c3数据结构c1c2c4汇编语言c1c5算法分析与设计c3c4c6计算机组成原理c11c7编译原理c5c3c8操作系统c3c6c9高等数学无c10线性代数c9c11普通物理c9c12数值分析c9c10c1?课程先后关系的图形描形式
free(T); T=NULL; return OK; } ……
算法
❖ 定义:是对特定问题求解步骤的一种描述,是 指令的有限序列
❖ 5个特性 有穷性 确定性 可行性 输入 输出
❖ 算法与程序的区别 程序未必满足有穷性。
算法的设计要求
❖ 正确性(correctness) ❖ 可读性(readability) ❖ 健壮性(robustness) ❖ 效率(efficiency)与存储量需求
基本概念和术语(4)
❖ 数据的存储结构(物理结构) 数据逻辑结构在计算机中的表示 两种存储结构 ❖顺序存储结构 ❖链式存储结构
注意:数据的逻辑结构和存储结构的区别
两种存储结构示例
顺序存储结构
链式存储结构
基本概念和术语(5)
❖ 数据运算 是在数据的逻辑结构上定义的操作算法. ❖算法的设计取决于选定的数据逻辑结构. ❖算法的实现依赖于采用的存储结构.
数据结构
第一章 绪论
主讲人:刘波
本章教学目标、重点、难点
❖ 教学目标：了解数据结构这门课程的主要内容,作 用,掌握数据结构的基本概念及术语
❖ 教学重点
数据、数据元素、数据结构、数据类型、抽象数据类型 等概念术语的确定含义、特别是数据结构的三个方面以 及这三方面的相互关系；
描述算法的类C语言与C语言的区别； 算法设计的基本要求及算法的时间分析和空间分析的方

数据结构教案-详细版-第1章-绪论教案

引入数据对象以及数据元素两个基础概念。 2、数据逻辑结构类型和存储结构类型。 通过 DNA 双螺旋结构，引入逻辑结构类型
通过上面的高数成绩图引入链式存储结构 通过 XXXX 的行政结构图来引入树形结构等
通过地图引入图形结构
并对各种数据结构进行对比。
存储结构有四种：
• 顺序存储结构
• 链式存储结构
成熟的算法有以下五个特性： 确定性 可行性 有穷性 零个或多个输入 至少一个输出 一个好算法需要具备以下条件： 正确性 可读性 健壮性 高效率和低存储 先列举出这两方面所要求的特点，再对每个特点的具体含义进行讲解。
6、算法的时间复杂度和空间复杂度分析。 通过上文的喝茶的整个过程变形，洗茶具和烧水可以同步进行来引入算法的时间复杂度 的概念，空间复杂度。
P4=NEW STUD2(); P4.NO=2018009; ="张强"; P4.SCORE=95;
P5=NEW STUD2(); P5.NO=2018007; ="许兵"; P5.SCORE=76;
P6=NEW STUD2(); P6.NO=2018012; ="李萍"; P6.SCORE=88;
//尾结点的 NEXT 属性设置为 NULL
3、数据结构和数据类型的关系。
通过前文所述数据结构进行深度剖析，指出一个数据结构是指计算机处理的数据元素的
组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。并借此引
入抽象数据类型的概念。
4、抽象数据类型的作用和描述方法。
抽象数据类型（ADT）指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算
• 索引存储结构
• 哈希（散列）存储结构
例 1：对象数组
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

例1-1 书目检索自动化问题
线性表
按书名
001
高等数书学目卡樊片映川
S01
002 登录理号论：力学 罗远祥
L01
003
高等数学 华罗庚
S01
004 书名线：性代数 栾汝书
S02
…… 作者名…：…
……
……
分类号：
按作者名
高等数学 001，003…出…版单位：樊映川
理论力学 002，……出.. 版时间：华罗庚
顺序存储
存储地址 Lo
Lo+m
存储内容
元素1 元素2 ……..
Lo+(i-1)*m 元素i ……..
Lo+（n-1)*m 元素n
Loc(元素i)=Loc+（i-1)*m
h
1345
h
元素11400 元素21536
链式存储
元素31346 元素4 ∧
存储地址 1345 1346 ……. 1400 ……. 1536
指的是数据元素之间存在的关系
例，在 2 行 3 列的二维数组中六个元素
{a1, a2, a3, a4, a5, a6} 之间存在两个关系: 行的次序关系:
a1 a2 a3 a4 a5 a6
row = {<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}
列的次序关系:
col = {<a1,a4>,<a2,a5>,<a3,a6>}
线性代数 ……
0…0… 4，.. ……价格：
栾汝书 …….
001,… 002,…. 004,…. …….
L S ……
书目文件
索引表
按分类号
002,… 001,003, ……
计算机处理的对象之间存在着线性关系，称为线性 的数据结构。
例1-2 人机对奕问题
树
……..
……..
…...
…...
…...
…...
数据元素也可以由若干项构成。 例如： 描述一个学生的数据元素
其中每个项称为一个“数据项”
它是数据结构中讨论的最小单位
姓 名学 号班 号性别出生日期入学成绩 年月日
原子项
称之为组合项
数据结构：
有一个特性相同的数据元素的集合， 如果在数据元素之间存在一种或多种 特定的关系，则称为一个数据结构。
带结构的数据元素的集合
1.1 数据结构讨论的范畴 1.2 基本概念 1.3 算法和算法的量度
1.1 数据结构讨论的范畴
(数据结构在软件开发中的地位) 系统分析
系统设计 系统实现 系统维护
例如: 数值计算的程序设计问题
结构静力分析计算 ─━ 线性代数方程组
全球天气预报 ─━ 环流模式方程 (球面坐标系)
这些可以建模为数学方程（组）的 问题的计算方法是《数值计算》研 究的内容。
子位串：表示一个数据项。（以后称“数据域” ）
3．数据的两种存储结构
存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示
数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据
元素间的逻辑关系
数据的逻辑结构与存储结构密切相关
算法设计
取决于选定的逻辑结构
算法实现
依赖于采用的存储结构
线性结构 树形结构
图状结构
集合结构1.2 基本概念来自术语数据结构的形式定义：数据结构是一个二元组 Data_Structure=(D,S)
其中，D 是数据元素的有限集,S 是D上关系的有限集 例1-4 复数 Complex=(C,R) 例1-5 课题小组 Group=(P,R) P={T,G1,…,Gn,S11,…,Snm}1≤n≤3，1≤m≤2， R={R1,R2} R1={<T,Gi> |1≤i≤n, 1≤n≤3,} R2={<Gi,Sij> |1≤i≤n, 1≤j≤m,1≤m≤2,}
1.2 基本概念和术语
数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算机 存储器中的实现 位：在计算机中表示信息的最小单位，二进制数的一位
位串：由若干个位组合，表示一个数据元素。（以后称 “元素”或“结点”） 例：整数用一个字长（16位） 表示，字符用8位表示
数据:
所有能被输入到计算机中，且能被计算 机处理的符号(数值、字符等)的集合。
是计算机操作的对象的总称。 是计算机处理的信息的某种特定的符 号表示形式。
数据元素:
是数据（集合）中的一个“个 体”,在计算机中通常作为一个整 体进行考虑和处理。是数据结构中 讨论的基本单位。
如:整数“5”,字符“N”等。 ----是不可分割的“原子”
typedef struct { int num;
char name[20]; float score; }STUDENT; STUDENT stu1,stu2, *p;
数据类型：是一个值的集合和定义在这 个值集上的所有 的操作。如，整型。 数据类型可分为：非结构的原子类型和 结构类型。 原子类型的值是不可分解的 结构类型的值是由若干成分按某种结 构组成的。
数据类型在高级语言中指数据的取值范围 及其上可进行的操作的总称
例 C语言中，提供int, char, float, double等基 本数据类型，数组、结构体、共用体、枚举等构造数 据类型，还有指针、空(void)类型等。用户也可用 typedef 自己定义数据类型
例1-3 多岔路口交通灯的管理问题
图
C
AB AC AD
D
B
BA BC BD
DA DB DC
E A
EA EB EC ED
概括地说： 数据结构是一门研究非数值 计算的程序设计问题中的操 作对象以及它们之间关系和 操作等的学科.
1.2 基本概念
一、数据与数据结构 二、数据类型 三、抽象数据类型
一、数据与数据结构
存储内容 元素1 元素4 …….. 元素2 …….. 元素3
指针 1400 ∧ ……. 1536 ……. 1346
数据结构的三个方面： 数据的逻辑结构
线性结构
线性表 栈 队
非线性结构 树形结构 图形结构
数据的存储结构 顺序存储 链式存储
数据的运算：检索、排序、插入、删除、修改等
4.数据类型 抽象数据类型
若在 6 个数据元素{a1, a2, a3, a4, a5, a6} 之间存在如下的次序关系:
{<ai, ai+1>| i=1, 2, 3, 4, 5}
则构成一维数组的定义。
可见，不同的“关系”构成不同的“结构” 数据结构是相互之间存在着某种逻辑
关系的数据元素的集合。
从关系或结构分，数据结构可归结 为以下四类:（各关系可以用‘次序’ 关系加以描述）。