一、算法
2、算法的描述: 1）流程图 2）伪代码——类似程序设计语言
3、算法的基本结构 ——算法代码化的过程: 1）顺序结构 2）分支结构 3）循环结构
一、算法
算法的时间复杂度是指（ ）。
A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数
第2章 数据结构
۩ 算法 ۩ 数据结构概述 ۩ 线性结构 ۩ 栈和队列 ۩树 ۩图
第2章 数据结构
数据结构是讨论非数值类问题的 对象描述、信息组织方法及其相应的 操作。
数据结构的研究内容
电子计算机的主要用途： 早期： 主要用于数值计算。
数学模型→选择计算机语言→编出程序→测试→最终解答
后来： 处理逐渐扩大到非数值计算领域
一、算法
算法的空间复杂度是指（ ）。
A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中的所需要的存储空间
一、算法
4、算法效率衡量方法与准则 :
时间复杂度：Windows程序设计中，指执行时间的
长短。
空间复杂度：指存储空间的大小。
一、算法
5、算法与数据结构的关系:
思考：
数据处理的最小单位是（ ）。 A. 数据 B. 数据元素 C. 数据项 D. 数据结构
补充——数据项
数据项，是数据的最小单位，数据项定 义的内容包括：
item
名称、编号（I）、别名、简述 类型、长度 取值范围
数据项定义举例
数据项名：年级 别名： 取值及含义：〔Ｆ｜Ｍ｜Ｊ｜Ｓ〕
Ｆ－freshmen，一年级 Ｍ－sophomore，二年级 Ｊ－junior，三年级 Ｓ－senior，四年级 注释：F，M，J，S可分别用1，2，3，4代替
设有六个比赛项目，规定每个选手至多可参加三个项
目，有五人报名参加比赛（如下表所示）。要求设计比
赛日程表，使得在尽可能短的时间内完成比赛。
姓名
项目1
项目2
项目3
丁一
跳高
跳远
100米
马二
标枪
铅球
张三
标枪
100米
200米
李四
铅球
200米
跳高
王五
跳远
200米
（1）设用如下六个不同的编码代表不同的项目：
跳高 跳远 标枪 铅球 100米 200米
不同联系
系主任 1
负责
班级 1
包含
1
N
系
学生
一对一联系 一对多联系
产品 M
组成 N
零件
多对多联系
习题：将下述表达式用图形的形式表示出来
（1）Data_Structure=(D,S)，其中，
D={ 01，02，03，04，05 }
S={ }
集合结构
（2） S=(D, R) D={ a, b, c, d, e, f }
链式存储结构——借助指示元素存储地址的指针表示数据元素 之间的逻辑关系
索引存储结构——在存储结点的同时，还建立附加的索引表， 索引表中的每一项称为索引项，形式为：关键字，地址。 散列存储结构——根据结点的关键字直接计算出该结点的存 储地址。 说明：四种存储方法可结合起来对数据结构进行存储映像。
第2章 数据结构
R={ <a,e>, < b,c >, < c,a >, < e,f >, < f,d > }
解: 上述表达式可用图形表示为：
b
c
a
e
f
d
线性结构
（3） Data_Structure=（D，S），其中，
D={ 01，02，03，04，05 ，06，07 } S={（01，02），（01，03），（01，04），（02， 05），（02，06），（03，07） }
算法 数据结构概述
线性结构
栈和队列 数组 树 图
三、线性结构
线性表 1.线性表的定义
线性表是n(n>=0)个数据元素的有限序列，表中 各个元素具有相同的属性。
记做：(a1,a2,…….ai-1,ai,ai+1,…,an-1,an ) 其中，ai-1称为ai 的直接前趋元素，ai+1是ai的直 接后继元素 线性表的长度：表中的元素个数 n
Data_Structure =（D，R） 其中，D是数据元素的有限集，R是D上关系的有 限集。
二、数据结构概述
[例1] 线性数据结构 =（D，R） D = {1，2，3，4，5，6，7，8，9，10}
R = {<1，2>，<2，3>，<3，4>，<4，5>，<5， 6>，<6，7>，<7，8>，<8，9>，<9，10>}
三、线性结构
线性表的顺序表示和实现
顺序表的表示： 采用顺序存储结构存储的线性表
顺序存储定义：把逻辑上相邻的元素存储在物理 位置上相邻的存储单元中。
简言之：逻辑相邻，物理也相邻
顺序存储方法：用一组地址连续的存储单元依次 存放线性表的数据元素。
线性表顺序存储结构的特点
1、逻辑上相邻的物理元素，其物理位置上也相邻 2、若已知线性表中第1个元素的存储位置，则线性表中任 意一
<习题2> 数据在计算机存储器内表
示时，物理地址与逻辑地址相同并且是
连续的，称之为：
A. 存储结构
B. 逻辑结构
C. 顺序存储结构 D. 链式存储结构
【答案】C
三、线性结构
<习题3>一个向量第一个元素的存储 地址是100，每个元素的长度为2，则第 5个元素的地址是（ ）。 A. 110 B. 108 C. 100 D. 120
计算机科学家沃斯（N.Wirth）提出的: “算法+数据结构=程序”
计算机内的数值运算依靠方程式，而非数值 运算则要依靠数据结构。
同样的数据对象，用不同的数据结构来表示， 运算效率可能有明显的差异。
第2章 数据结构
算法
数据结构概述
线性结构 栈和队列 数组 树 图
二、数据结构概述
特性相同的数据元素构成的集合中，如果在数据 元素之间存在一种或多种特定的关系，则称之为数 据结构 。
【答案】B
三、线性结构
<习题4> 线性表若采用链式存储结 构时，要求内存中可用存储单元的地址:
A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以
出生年月 1989.12 1989.07 1991.02 1990.10 1991.01 1990.03 1991.01 1991.02 1989.12
三、线性结构
2. 线性表的顺序表示和实现 顺序表——线性表的顺序存储表示 顺序表，随机存取
三、线性结构
3. 线性表的链式表示和实现
单链表——线性表的链式存储表示 数据域（data）和指针域（next）
指针域 43 13 1
NULL 37 7 19 25
答：头指针是指向链表中第一 个结点的指针，因此关键是要 寻找第一个结点的地址。
H
31
ZHAO 7
称：头指针H的值是31
例：现有一个有5个元素的线性表 L={23，17，47，05， 31}，若它以链式结构存储在下列100～119号地址空间
中，每个结点由数据（占2个字节）和指针（占2个字节） 组成，如下图所示。
结点：数据元素的存储映象
数据域 指针域
数据元素
直接后继位置
链表：n个结点链接成起来形成一个链表，即为线性表的
链式存储结构。
指针域为空
L
a1
a2
… ai-1
ai
… an ^
头结点 L
^
三、线性结构
数据结构是讨论非数值类问题的对 象描述、信息组织方法及其相应的操作
<例1.1 电话号码查询问题>
设有一个电话号码薄，有N个人的姓名和电话号 码。要求设计一个程序，按人名查找号码，若不存在 则给出不存在的信息。
下面叙述正确的是（ ）。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（ 或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限 个步骤之后终止 D. 以上3种描述都不对
二、数据结构概述
3、按数据结构在计算机内的存储方式来划分
顺序存储结构——借助元素在存储器的相对位置来表示数据元 素之间的逻辑关系。
用一组任意的存储单元存储线性表的元素
例：一个线性表的逻辑结构为： （ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG）， 其存储结构用单链表表示如下，请问其头指针的值是多少？
存储地址 1 7 13 19 25 31 37 43
数据域 LI
QIAN SUN WANG WU ZHAO ZHENG ZHOU
[例3] 树形结构 =（D，R） D = {a，b，c，d，e，f，g，h，i，j，k，l} R = {<a，b>，<a，c>，<a，d>，<b，e>，<b，f>， <b，g>，<c，h>，<c，i>，<c，j>，<d，k>，<d，l>}
二、数据结构概述
四类基本的数据结构 集合结构。各元素间没有直接的关联。 线性结构。该结构的数据元素之间存在着一对一的关 系。 树型结构。该结构的数据元素之间存在着一对多的关 系。 图形结构。该结构的数据元素之间存在着多对多的关 系，也称作网状结构。
2、线性表顺序存储结构的特点：