…… 第 i 个元素
表
int last; };
……
位置类型：
typedef int position;
last
最后1个元素
……
maxlength-1
线性表 L:
空单元 LIST L;
表示：
存储池容量
L.elements[p] // L的第p个元素 st L的长度，最后元素的位置
图3-1 线性表的数组实现
L.elements[ q + 1] = L.elements[ q ] ;
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
1.1.1基本概念和术语
(3)数据元素之间的关系（逻辑结构）在计算机中有 两种表示方法：顺序映象(表示)和非顺序映象(表示)，从 而导致两种不同的存储结构：顺序结构和链式结构。
顺序映象（表示）的特点是借助数据元素在存储器 中的相对位置来表示数据元素之间的逻辑关系。
示。
图3-1 线性表的数组实现
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
3.2.2 线性表的数组实现
0
1 第1个元素 2 第2个元素
类型定义： # define maxlength 100 struct LIST {
elementtype elements
[maxlength];
1≤ i ≤ last
非顺序映象（表示）的特点是借助指示数据元素存 储地址的指针来表示数据元素之间的逻辑关系。
哈尔滨工业大学 计算机科学与技术学院返回
课堂讲义
1.1.2四种基本的数据结构
1.集合结构
结构中的数据元素之间除了“属于同一个集合”的关 系之外，别无其他关系。关系比较松散，可用其他结构来 表示。
2.线性结构
结构中的数据元素之间存在一个对一个的关系，即 线性关系，每个元素至多有一个直接前导和后继。
其中：① n为线性表中元素个数，称为线性表的长度； 当n=0时，为空表，记为（ ）。
② ai为线性表中的元素，类型定义为elementtype ③ a1为表中第1个元素，无前驱元素；an为表中最后一个
元素，无后继元素；对于…ai-1,ai,ai+1…(1<i<n)，称ai-1 为ai的直接前驱，ai+1为ai的直接后继。(位置概念！） ④ 线性表是有限的，也是有序的。
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
5.结点 数据元素在机内的位串表示，即数据元素在计算机内的 映象。 6.域/字段 当数据元素由若干个数据项组成时，位串中对应于各个 数据项的子串称为域/字段，是数据元素中数据项在计算机中 的映象。 7.信息表 计算机程序所作用的一组数据通常称为信息表，是数据 对象在计算机中的映象。
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
3.2.2 线性表的数组实现 操作：
0
1 第1个元素 2 第2个元素
……
1≤ i ≤ last 第 i 个元 …素…
last
最后1个元
…素…
maxlength-1
存储池容量
① void Insert ( elementtype x,
position p, LIST &L)
③for ( i=1; i<=n ; ++i ) for( j=1 ; j <=n ; ++j ) { ++x ; s += x; }
→ f(n) = 3n2+2n+1; T3(n) = O(f(n)) = O(n2)
平方阶
④for ( i=1; i<=n ; ++i ) for ( j=1 ; j <=n ; ++j ) { c[i][j] = 0; for ( k=1 ; k <= n; ++k ) c[i][j] += a[i][k] * b[k][j] ; }
重点： ▪熟练掌握顺序表和单链表上实现的各种算法及相关的时间复 杂性分析
难点： ▪使用本章所学的基本知识设计有效算法解决与线性表相关的应用问 题
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
3.1 抽象数据型线性表
[定义] 线性表是由n(n≥0)个相同类型的元素组成的有序集合。 记为： ( a1,a2,a3,……ai-1,ai,ai+1,…… an )
数学模型
操作：设L的型为LIST线性表实例，x 的型为elementtype的元素 实例，p 为位置变量。所有操作描述为： ① Insert(x, p, L) ② Locate(x, L) ③ Retrieve(p, L) ④ Delete(p, L) ⑤ Previous(p, L), Next(p, L) ⑥ MakeNull( L) ⑦ First( L) ⑧End(L)
О（1）< О（㏒㏒n） < О（㏒n） < О（n） < О（n㏒n） < О（n2） < О（n3） < О（2n）
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
设T1(n)=O( f(n) )，T2(n)=O( g(n) )，则 加法规则：T1(n)+T2(n) = O( max{ f(n), g(n) } ) 乘法规则：T1(n)*T2(n) = O( f(n)* g(n) ) 1. 表达式和赋值语句:O(1)
{ position q ;
if (st >= maxlength – 1)
表
error( “ 表满 ” ) ； else if (( p > st +1 ) || ( p < 1) )
error( “ 指定位置不存在 ” ) ；
else {
for ( q = st; q >= p; q -- )
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
1.1.1基本概念和术语
8.数据结构 数据结构指的是数据元素之间的相互关系，这种关 系是抽象的，即并不涉及数据元素的具体内容。是数据元 素及其相互间的关系的数学描述。
9.逻辑结构和存储结构 (1)逻辑结构 数据结构中描述的是数据元素之间的抽象关系(逻辑 关系)，称为逻辑结构。 (2)存储结构/物理结构 数据结构在计算机中的表示（映象）称为存储结构/ 物理结构。
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
3.1 抽象数据型线性表
举例：设计函数 Deleval（LIST &L, elementtype d) ，其功能 为删除 L 中所有值为 d 的元素。 void Deleval( LIST &L, elementtype d ) { position p ; p = First( L ) ; while ( p != Ennd( L ) ) { if ( same( Retrieve( p, L ), d ) ) Delete(p, L ) ; else p = Next(p, L ) ; } }
①s = 0 ;
n）
→ f(n) = 1; T2(n) = O(f(n)) = O(1)常量阶
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
②for ( i=1 ; i <= n ; ++i ) { ++x; s += x; } → f(n) = 3n+1; T1(n) = O(f(n)) = O(n) 线形阶
2. 语句序列:用加法规则,取耗时最多语句. 3. 条件语句:O(1) 4. FOR语句:O(N*M)N为循环次数,M为体内时间最多的语句 5. WHILE语句:找出与循环次数有关的变量,通过计算找出上下限.
例: x=n; y=0;
while (x>=(y+1)(y+1))
y=y+1;
时间复杂性为O（
课堂讲义
计算机系列课程之间的联系
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
数据结构涵盖的内容
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
二.基本概念和术语
1.数据 数据是用于描述客观事物的数值、字符，以及一切可以 输入到计算机中的并由计算机程序加以处理的符号的集合。其 范围随着计算机技术的发展而不断发展。 2.数据元素 数据的基本单位是数据元素，在计算机程序中通常作为 一个整体进行考虑和处理。 3.数据项 是数据的不可分割的最小单位，一个数据元素可由若干 个数据项组成。 4.数据对象 性质相同的元素的集合叫做数据对象。
哈尔滨工业大学 计算机科学与技术学院
课堂讲义
2.2 算法时间复杂性分析方法
定理2.1 若 A（n）=amnm+…+a1n+a0
是关于n的m次多项式，则 A（n）=О（nm）
*此定理说明，时间复杂性仅取决于多项式的最高次幂，而与最高次幂的 系数和其他低次项无关 •О（1）表示实践复杂性为常数 •常见的时间复杂性及其比较
算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规 则）的有限序列，其中每一条指令表示一个或多个操作。
算法的特征： ①有穷性、②确定性、 ③能行性、④输入、 ⑤输出
算法描述： ①自然语言；②程序设计语言；③类语言*；
常用的算法设计方法： ①递归法（Recursion）、②分治法(Divide-and Conquer)、 ③贪心法(Greedy)、④动态规划(Dynamic Programming)、 ⑤搜索与遍历、⑥回溯（Backtracking）、⑦解空间局部搜索 ⑧近似算法(Approximation)、⑨在线算法（On-Line）等
哈尔滨工业大学 计算机科学与技术学院
课堂讲义