当前位置：文档之家 › 第二章数据结构及其运算

第二章数据结构及其运算

  • 格式：ppt
  • 大小：1.21 MB
  • 文档页数：49

下载文档原格式

  / 49

合集下载

数据结构和算法课件_第2章精品文档

数据结构和算法课件_第2章精品文档

表的长度减少
例如：SeqListDelete (L, 5, e)
for ( j=pos; j<L.len; ++j) L.list[j-1] = L.list[j];
jjj
21 18 30 75 42 56 87 63
0
5
L.len-1
21 18 30 75 56 87 63
详细算法描述如下：
void SeqListDelete(SeqList L,int i) {int j; if(L.len<=0) error(“下溢错误”)； if(i>L.len||i<0) error(“删除位置错”)； else {for(j=i;j<=L.len-1;j++)
n
n div 8 n mod 8
1348 168
4
168 21
0
21
2
5
2
0
2
要求：输入一个非负十进制整数，输出任意进制数 void Conversion() { InitStack(s);
scanf("%d,%d",&N,&R); N1=N; while (N1)
{ Push(s,N1%R); N1 = N1/R; }
{ printf(“overflow!”);exit(0);} s++; s.stack[s]=x; }
栈满条件：s== s.Maxsize-1 进栈操作：s.stack[++ s]=x; 当栈满时再做进栈运算必定产生空间溢出， 简 称“上溢”;
退栈操作示例
ElemType SeqStackPop(SeqStack s) { if (s==-1）
第二章基本数据结构及其运算

第二章基本数据结构及其运算

第二章基本数据结构及其运算本章主要介绍计算机中常见的基本数据结构及其运算。

数据结构是计算机存储、组织和管理数据的方式，它对算法的设计和效率有很大影响。

基本数据结构包括线性表、栈、队列、树、图等，以及它们的各种运算。

1.线性表线性表是最简单、最常用的数据结构之一、线性表的定义是n个数据元素的有限序列：a1, a2, …, an。

其中，a1是第一个元素，an是最后一个元素。

线性表的特点是数据元素之间是一对一的关系，每个元素只有一个直接前驱和一个直接后继。

线性表的运算主要包括：-插入：在指定位置插入一个元素；-删除：删除指定位置上的元素；-查找：根据索引查找元素；-修改：根据索引修改元素的值；-遍历：依次访问线性表中的每个元素。

2.栈栈是一种特殊的线性表，具有“先进后出”（Last In First Out, LIFO）的特点。

在栈中，最后插入的元素是第一个被访问的元素，最先插入的元素是最后一个被访问的元素。

栈的运算主要包括：-入栈：将一个元素插入到栈的顶部；-出栈：从栈顶删除一个元素；-栈顶元素：查看栈顶的元素，不改变栈的内容。

栈的应用场景有很多，例如函数调用、表达式求值、迷宫求解等。

3.队列队列也是一种特殊的线性表，具有“先进先出”（First In First Out, FIFO）的特点。

在队列中，最先插入的元素是第一个被访问的元素，最后插入的元素是最后一个被访问的元素。

队列的运算主要包括：-入队：将一个元素插入到队列的末尾；-出队：从队列的头部删除一个元素；-队首元素：查看队列的头部元素，不改变队列的内容。

队列的应用场景有很多，例如任务调度、缓冲区管理、广度优先等。

4.树树是一种非线性的数据结构，它由n（n>=0）个节点组成的有限集合。

特点是每个节点最多有一个直接前驱和多个直接后继。

树的运算主要包括：-插入节点：在树中插入一个新节点；-删除节点：从树中删除一个指定节点；-查找节点：在树中查找一个指定节点；-遍历树：按照其中一种规则，依次访问树中的每个节点。

第2章 C语言数据结构及其运算

第2章 C语言数据结构及其运算

第二章数据结构及其运算考试要求：1.C的数据结构及其定义：基本类型，构造类型，指针类型，空类型2.C运算符的种类，运算优先级和结合性。

3.不同类型数据之间的转换与运算。

4.C表达式类型和求值规则：赋值表达式，算术表达式，关系表达式，逻辑表达式，条件表达式，逗号表达式。

0（整型） 1.2(实型) 244 1.414 …a‟（字符型）7070.5100 100 060 59.9Student1234561000 2 字节问：为什么要分数据类型？答：2. 不同的数据类型存储格式不同1. 不同的数据类型所实施的操作不同.第2.1节数据类型简单语句复合语句1. C的数据类型分为：基本类型，构造类型，指针类型，空类型。

2. 基本类型又包括：整型，字符型，实型（单精度型，双精度型），枚举型3. 构造类型又包括：数组类型，结构体类型和共用体类型。

C语言中的数据有常量和变量之分，但是它们都属于以上这些类型。

2.1.1 常量与变量1.常量28 168 5.1 3.14 ‘a’…y‟在程序运行中，其值不能被改变的量叫做常量。

常量可以划分为不同的类型，如12，0，-3为整型常量；4.6，-3.15为实型常量；‘a’,‟p‟为字符型常量。

也可以用一个标示符来代表一个常量。

如：#define pi 3.1415 符号常量#define afsj 1682变量area=2其值可以改变的量叫做变量。

一个变量应该有一个名字，在内存中占据一定的存储单元。

该存储单元中存放变量的值。

注意变量名和变量值。

变量名的命名规则和标示符的命名规则相同。

int a;(为a分配了一个存储单元)a=2;简单说标示符就是一个名字。

在C语言中，要求对所有用到的变量作强制定义，也就是“先定义，后使用”。

2.1.2 基本类型整型包括整形常量，整型变量。

整型常量就是整常数。

在C 中使用的整常数有：八进制，十六进制和十进制。

1. 整型整型常量1) 八进制整常数必须以0（零）开头，用0做八进制的前缀。

基本数据结构及其运算

基本数据结构及其运算


…
…… …
0200 高等数学 MA 樊映川 高教 18.00
…
…
…… …
4
树状模型问题
井字棋的博弈树
5
数据结构讨论的范畴
❖ 对于任何双人完备博弈，都可以用一个博 弈树来描述，并通过对博弈树的搜索策略 寻找最佳解。
❖ 博弈树上每个结点对应一个棋局，根代表 棋局的开始，叶子代表棋局的结束。
❖ 对国际象棋来说，博弈树有10102个结点。 围棋更复杂，有10768个结点。中国象棋有 10160个结点。
6
网状模型问题
地图着色问题
B F
A
C
D
E
A
B
E
C
F
D
7
网状模型问题
A
0# C
B
1#
D 2#
E
1#
3#
F
2#
A 0#
1# B
E
C 2#
3#
2# F
D 1#
8
2.1 数据结构的基本概念
1. 数据 (Data)：
2. 数据元素 (Data Element) ：
一个数据元素一般用来描述一个具体的实体，如一 个学生，一本书,春,夏,秋,冬等。
第二章 基本数据结构及其运算
目录
§2.1 数据结构的基本概念 §2.2 线性表及其顺序存储结构 §2.3 线性链表及其运算 §2.4 数组 §2.5 树与二叉树 §2.6 图
1
2.1 数据结构的基本概念
数据结构讨论的范畴
那些不能用数学函数、公式、方程等描述的非 数值性问题的求解。
解决这类问题的基本方法：
16

2.1 数据结构的基本概念
第02章 基本数据结构及其运算

第02章 基本数据结构及其运算


在计算机中存放线性表，一种最简单 的方法是顺序存储，也称为顺序分配。顺 序存储的线性表通常称为顺序表。
线性表的顺序存储结构具有以下两个 基本特点：
① 线性表中所有元素所占的存储空间 是连续的。
② 线性表中各数据元素在存储空间中 是按逻辑顺序依次存放的。
在计算机中的顺序存储结构如图 2.8所示。
在程序设计语言中，通常定义一个一 维数组来表示线性表的顺序存储空间。
int m,*n,i； /*m为顺序表空间容量,n 为指向线性表长度的指针,
i为插入元素的序号*/
{ if (*n==m) /*顺序表空间已满,上溢 错误,返回*/
{ printf("overflow \n")； return； }
if (i＞*n–1) i=*n+1； /*在线性表的 最后插入*/
例2.3 n维向量 X = (x1,x2,…,xn) 也是一种数据结构。即X = (D,R)，其 中数据元素的集合为：
D = {x1,x2,…,xn} 关系为：
R = {(x1,x2),(x2,x3),…,(xn – 1,xn)}
例如，m×n的矩阵
是一个数据结构。在这个数据结构中， 矩阵的每一行
首先举一个例子来说明如何在顺序存 储结构的线性表中删除一个元素。
一般来说，设长度为n的线性表为：
现要删除第i个元素，删除后得到长度 为n – 1的线性表为：
则删除前后的两线性表中的元素满足 如下关系：
在线性表顺序存储的情况下，要删除 一个元素，由于数据元素的移动而消耗较 多的处理时间，其效率也是很低的，特别 是在线性表比较大的情况下更为突出。
通常，一个数据结构中的元素结点可 能是在动态变化的。
数据结构中的结点（即数据元素）个 数在动态地变化，而且，各数据元素之间 的关系也有可能在动态地变化。
第二章基本数据结构及其运算

第二章基本数据结构及其运算


用这种方法查找，每次比较都可抛弃子表一半的 元素，查找效率较高 从该例可看出，数据元素在表中的排列顺序对查 找效率有很大的影响
例2、学生情况登记表信息查询 成绩在90分及以上的学生情况登记表
学 号 970156 970157 970158 970159 970160 970161 970162 970163 970164 … 姓 名 性 别 年龄 20 张小明 男 19 李小青 女 19 赵 凯 男 21 李启明 男 18 刘 华 女 19 曾小波 女 18 张 军 男 20 王 伟 男 19 胡 涛 男 … … … 成绩 86 83 70 91 78 90 80 65 95 … 学 号 姓 名 性别 男 女 男 女 年龄 21 19 19 17 成绩 91 90 95 93 970159 李启明 970161 曾小波 970164 胡 970168 梅 涛 玲
数据结构主要研究和讨论三方面问题：
1、数据元素之间的固有逻辑关系，称为数据的逻辑结构 2、数据元素及其关系在计算机中的存储方式，称为数据的 物理结构或存储结构
3、施加在数据结构上的操作，称为数据结构的运算。数据处 理的本质就是对数据结构施加各种运算，常见的运算有：查找、 排序、插入、删除等。
主要目的是提高数据处理的效率：
§2.1.3 数据结构的图形表示
D中的数据元素用中间标有元素值的方框表示， 称为数据结点（结点）；R中的关系用一条有向线段 从前件结点指向后件结点。
例：设数据元素的集合为D = {di |1≤ i≤ 7的整数}，画 出对应于下列关系所构成的数据结构的图形
①、R1={(d1,d3),(d1,d7),(d4,d5),(d3,d6),(d2,d4)} ②、R2={(di,dj)|i+j=5} ③、R3={(d2,d3)(d3,d1),(d1,d4),(d4,d6),d6,d5),(d5,d7)}
第二章 基本数据结构及其运算

第二章 基本数据结构及其运算


√ 35 √ 16 √ 78 √ 85 √ 43 √次
16 √ 21
查找33
√ 29 √ 33 √ 35
无序表 有序表 算，从而提高数据处理的效率。
2019/1/14
计算机软件技术基础 第二章 数据结构及其运算（上）
4
2.1.2 什么是数据结构
1. 数据：反映客观事物的信息的集合。
2019/1/14 计算机软件技术基础 第二章 数据结构及其运算（上） 2
2.1.1 两个例子
• 数据处理：对数据集合中的各元素以各种方式 进行运算，包括插入、删除、查找、更改等运 算，也包括对数据元素进行分析。
• 无序表的顺序查找：35 16 78 85 43 29 33 21 54 46；
• 有序表的对分查找：16 21 29 33 35 43 46 54 78 85
的每一个子集称为在集合M上的一个二元关系，简 称为集合在M上的一个关系。
2019/1/14 计算机软件技术基础 第二章 数据结构及其运算（上） 11
举例
• 设集合M为
M {a, b, c, d , e, f }
则下列各二元组的集合为在集合M上的一个关系：
R1 {( a , b), (b, c ), (c , d ), (d , e ), (e , f )} R2 {( a , e ), (a , a ), (c , f ), (d , b), (e , a ), ( f , c ), (b, d )} R3 {( a , a ), (b, b), (c , c ), (d , d ), (e , e ), ( f , f ), (c , f ), (e , a )} R4 {( a , b), (b, e ), (c , d ), (d , f ), (a , e ), (c , f )}
《数据结构与算法分析》课件第2章

《数据结构与算法分析》课件第2章


图2-10 带头结点的单链表head
2．单链表的查找 1) 按序号查找 在单链表中，即使知道被访问结点的序号i，也不能像顺 序表中那样直接按序号i访问结点，而只能从链表的头指针出 发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点 为止。因此，单链表不是随机存取结构。
2) 按值查找 按值查找是从开始结点出发，顺着链逐个将结点的值和 给定值key做比较，来完成结点的查找。
2.3.1 单链表 在顺序表中，我们是用一组地址连续的存储单元来依次
存放线性表的结点，因此结点的逻辑次序和物理次序一致。 而链表是用一组任意的存储单元来存放线性表的元素，这组 存储单元既可以是连续的，也可以是不连续的。因此，为了 正确地表示元素间的逻辑关系，在存储每个元素值的同时， 还必须存储指示其后继元素的地址(或位置)信息。
typedef int datatype; #define MAXSIZE 1024
//datatype 可为任何类型，假设为 int //线性表可能的最大长度，假设为 1024
typedef struct {
datatype data[MAXSIZE];
int last;
}SequenList;
2.2.1 顺序表的基本运算 1. 插入运算 在线性表的第i(1≤i≤n+1)个位置上，插入一个新结点x，
n 1
EIS = pi (n i 1) i1
(2-3)
假设qi是删除第i个元素的概率，则在长度为n的线性表 中删除一个元素须移动元素次数的期望值(平均次数)为
n
EDE = qi (n i)
(2-4)
i1
为了不失一般性，假设在线性表中任何位置上插入或删
除元素的概率相等，则
二章数据结构与算法

二章数据结构与算法

第二章 数据结构与算法
2.7 查找技术
1.顺序查找
❖ 顺序查找又称为顺序搜索，顺序查找一般是指在线性表中 查找指定的元素，其基本方法如下：
❖
从线性表的每一个元素开始，因此将线性表中的元素与
被查元素进行比较，若相等则表示找到；若线性表中所有
的元素都与被查元素进行了比较但都不相等，则表示线性
表中没有要找的元素。
大约要与线性表中一如果线性表中的第一个元素就是别
查找元素，则只需做依次比较就查找成功，查找效率很高；
但如果被查的元素是线性表中的最后 一个元素，或者被查
元素根本不在线性表中，则为了查找这个元素需要与线性
表中所有的元素进行比较，这是顺序查找的最坏情况。在
平均情况下，利用顺序查找发在线性表中查找一个元素，
R语言—第二章 数据结构与基本运算

R语言—第二章 数据结构与基本运算


析
与
分
据
数
分 析
与
建
2
模
数 据
上面，我们用c()函数首先生成了向量z,c()函数的具体使用方 法详见2.2.1。is.na()返回的结果是前面5个元素都为FALSE， 最后一个是TRUE。这说明前面5个都不是缺失值，最后一个才 是缺失值。
分 析
• 有些统计资料是不完整的。当一个元素或值在统计的时候是 “不可得到”(Not Available）或“缺失值”(missing value)时， 相 关 位 置 可 能 会 被 保 留 并 且 赋 予 一 个 特 定 的NA(not available)值。任何NA的运算结果都是NA. • is.na()函数用来检测数据是否缺失，如果数据缺失，返回 值为TRUE；否则返回FALSE。例如： > z<-c(1:5,NA) #生成向量z > z #返回向量z的结果 [1] 1 2 3 4 5 NA > is.na(z) #识别z向量的值是否有缺失值 [1] FALSE FALSE FALSE FALSE FALSE TRUE
> sqrt(2)^2==2 [1] FALSE
在处理R里的数据时，尤其是在判断时，需要特别注意精度问题。
数 据
分 析
6
与
TRUE
据
建
模
[1] 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
析
与
2.2.1 向量
1 向量赋值
析
与
分
向量是由相同基本类型元素组成的序列，相当于一维数组。如： > x<- c(1,3,5,7,9) #用c（）构建向量
数据结构和算法2

数据结构和算法2


locate(L, x) insert(L, i, b) delete(L, i) empty(L) clear(L)
抽象数据类型线性表的定义 • 逻辑结构 • 基本操作
数据结构---第二章 线性表
3
2.2 线性表的顺序存储结构
起始地址为b、最多可容纳maxlen个元素的线性表
b
a1
c个存储单元
b+c
首元结点
4016
a1
a2
头结点 首元结点
头结点的作用：
插入和删除第一个数据 元素时不必对头指针进 行特殊处理。
an ^ an ^
空表： L=NULL H
^
数据结构---第二章 线性表
7
[插入]
H பைடு நூலகம்1
p^.next:=s; p
b
s s^.next:=p^.next;
ai-1
ai
an ^
PROC insert(H:linkisttp; i:integer; b:elemtp); p:=H; j:=0; WHILE (pnil) AND (j<i-1) DO [ p:=p^.next; j:=j+1]; IF (p=nil) OR (j>i-1) THEN ERROR(‘插入位置不合理’) ELSE [ new(s); s^.data:=b; s^.next:=p^.next; p^.next:=s; ]
• 缺点 – 插入、删除操作需要移动大量的元素 – 预先分配空间需按最大空间分配，利用不充分 – 表容量难以扩充
数据结构---第二章 线性表
6
2.3 线性表的链式存储结构
2.3.1 线性链表（单链表）
结点的物理表示 data next

基本数据结构及其运算习题

第二章基本数据结构及其运算一、单项选择题1．数据的基本单位是( B )A．数据B．数据元素C．数据项D．数据结构2．在数据结构中，构成数据元素的最小单位称为（D）A．字符B．关键字C．数据元素D．数据项3．数据在计算机内的存储形式称为数据的（ D ）A．算法描述B．数据类型C．逻辑结构D．物理结构4．数据的逻辑结构可分为（C）A．顺序结构和链式结构B．简单结构和复杂结构C．线性结构和非线性结构D．动态结构和静态结构5．顺序表中的每个元素占m个字节，第一个元素的存储地址为LOC(1)，则任意1个元素i的地址为( B )A．LOC(1)+i*m B．LOC(1)+(i-1)*mC．LCO(1)+(i+1)*m D．(i-1)*m 6．线性表若采用链表存储，其（D）A．所有结点的地址必须是连续的B．部分结点的地址必须是连续的C．所有结点的地址一定不连续D．所有结点的地址连续、不连续都可以7．线性表在采用链式存储时，其地址（ C ）A．必须是连续的B．一定是不连续的C．连续不连续都可以D．部分是连续的8．下列不属于线性结构的是( C )。

A．单链表B．队列C．二叉树D．数组9．链表不具有的特点是( A)A．可随机访问任一元素B．插入删除不需要移动元素C．不必事先估计存储空间D．所需空间与线性表的长度成正比10．数据结构反映了数据元素之间的结构关系，链表是一种( D)。

A．顺序存储线性表B．非顺序存储非线性表C．顺序存储非线性表D．非顺序存储线性表11．在单链表表示的线性表中，可以从( A )。

A．第一个结点访问到所有结点B．某个结点访问到所有结点C．某个结点访问到该结点的所有前趋结点D．最后一个结点访问到所有结点12．在一个单链表中，已知指针q所指向的结点是指针p所指向的结点的前驱结点，若在指针q和p所指向的两个结点之间插入指针s指向的结点，则执行( C )。

A．s->link=p->link; p->link=s;B．p->link=s->link; s->link=p;C．q->link=s; s->link=p;D．p->link=s; s->link=q;13．长度为n的顺序存储的线性表，设在任何位置上删除一个元素的概率相等，则删除一个元素时平均要移动的元素个数是（A）A．(n-1)/2 B．n/2 C．n-1D．n+114．设长度大于1带头结点的循环单链表head的尾结点由rear 指向，则head和rear满足关系（B）A．rear->link= =NULLB．rear= =head->linkC．.rear->link= =headD．rear= =head15．在链式存储的线性表中，插入一个元素时（D）A．需要移动元素和修改指针B．不需要移动元素和修改指针C．需要移动元素，但不需要修改指针D．不需要移动元素，但需要修改指针16．设循环队列中有m个单元，队列满的条件是( A ) A．rear=front B．(rear+1)%m=frontC．rear%m=front D．rear+1=front17．栈和队列都是( C)。

第2章 基本数据结构及其运算

系，是用户按使用需要建立的。

数据结构研究的内容研究数据结构的目的2.线性表的存储地址（续）3.线性表在顺序存储下的插入运算 3.3.3.线性表在顺序存储下的插入运算（续）线性表在顺序存储下的插入算法应用举例。

4.线性表在顺序存储下的删除运算 4.4.线性表在顺序存储下的删除运算（续） 4.线性表在顺序存储下的删除算法应用举例基本数据结构及其运算1.计算表达式“A+B*C-D/E”的值。

的变化。

与栈类似，在程序设计语言中，用一维数组作为队列的顺在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行人队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。

存储空间划分的一个个占若干字节的小块。

结构如下图所示。

图所示。

存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号个存储所示的逻辑状在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。

各数据元素之间的前后件关系是由各结点的指针域来指示的。

指向线性表中第一个结点的HEAD=NULL(或0)时称为空表。

基本数据结构及其运算一、线性链表的基本概念（续）在实际应用中，带链的栈可以用来收集计算机存储空间中2.带链的栈（续） 2.下图是带链的队列及其运算。

第二章基本数据结构及其运算线性链表及其运算一、线性链表的基本概念二、线性链表的基本运算中包含元素x的结点之前插入一个新元素b。

其插入过程如下：q->next=p中删除包含元素x的结点。

其删除过程如下：在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。

另外，由于可利用栈是用于收集计算机中所有的空闲结点，因此，当从线性链表中删除一个元素后，该元素的存储结点就变为空闲，应将该空闲结点送回到可利用栈。

线性链表存在的结构示意图循环链表的优点在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点；而线性单链表则做不到这一点。

数据结构第二章学习小结

数据结构第⼆章学习⼩结⼀、数据结构第⼆章知识点2.1-2.32.1 线性表的定义与特点2.2 案例引⼊1.⼀元多项式的运算：顺序表2.稀疏多项式的运算：链式表3.图书信息管理系统：查找/插⼊/删除等操作2.3 线性表的类型定义ADT定义2.4 线性表的顺序表⽰与实现1.顺序存储结构（随机存取）2.基本操作实现算法：初始化/取值/查找/插⼊/删除3.补充：讨论时间复杂度O（n）和空间复杂度S（n），默认是最坏情况下插⼊，删除等操作时间复杂度都为O（n）：查找第i个元素，时间复杂度为O（1）；查找值为x时，时间复杂度为O（n）。

若顺序表长度很⼤，注意内存分配空间是否⾜够2.5 线性表的链式表⽰和实现1.链式存储结构（顺序存取）2..基本操作实现算法：创建/初始化/取值/查找/插⼊/删除（头插法，尾插法）3.循环链表（带头尾指针，只带尾指针），双向链表4.补充程序退出时回收空间（链表/结点）创建头结点⽅便删除/插⼊等操作指针作为形参，若修改了指针的直接空间，要加&。

若是间接空间，可以不加&。

2.6-2.92.6顺序表和链表的⽐较顺序表适⽤于长度变化不⼤，插⼊删除操作较少链表适⽤于长度变化较⼤，插⼊删除操作较多2.7 线性表的应⽤线性表合并（书）有序表合并（书）线性表或有序表求交集的ADT定义ADT List{数据对象： D={ai I ai∈ElemSet, i=1, 2, ..., n, n>=0}数据关系： R={ <ai-1, ai>|ai-1, ai∈D, i=1, 2, ..., n}基本操作：InitList(&L)操作结果：构造⼀个空的线性表 L。

ListLength(L)初始条件：线性表 L 已存在。

操作结果：返回 L 中数据元素个数。

GetElem(L, i, &e)初始条件：线性表 L 巳存在，且1<=i<=ListLength(L)。

软件技术-2 常用数据结构及其运算

常用的时间复杂度：
最坏情况下的时间复杂性：
平均情况下的时间复杂性：
• 空间复杂性：实现算法所需的辅助单元空 间和问题规模的函数。记为 S(n)。
一个算法所占用的存储空间包括算法程序所 占用的存储空间、输人的初始数据所占用的空间 以及算法执行过程中所需要的额外空间。
其中额外空间包括程序执行过程中的工作单
else {for (j=n ; j>=i ; j--) v[j+1]=v[j]; v[i]=b; n=n+1;
} }
4）运算时间分析 平均性态：平均移动元素的次数=n/2 最坏情况：移动元素的次数=n
【例2-1】
在线性表 (12，13，21，24，28，35，30，67，34）
第5个元素之前插入一个元素27。
数据的逻辑结构按关系分为线性结构（关 系是线性的）和非线性结构（关系是非线 性的）。
数据的三种逻辑结构形式
• 线性结构 数据元素间存在一对一的关系
• 树形结构 数据元素间存在一对多的关系
• 图状结构和网状结构 数据元素间存在多对多的关系
逻辑结构的层次图
•数据的物理结构
数据的物理结构是指数据的逻辑结构在 计算机中的映象，即存储表示。映象包括数 据元素的映象和数据关系的映象。数据元素 的映象是结点，即在计算机内用一结点表示 一个数据元素（结点是数据结构讨论的基本 单位）。关系的映象有两种，顺序映象和非 顺序映象。
...
...
last-1 last ...
1 2 ...
伪代码表示的删除算法
用一维数组[1:m],m>n存放线性表 DeleteList(V,n,i) {if (i<1)or(i>n) then {return} for j=i to n-1 V[j] V[j+1] end(j) nn-1 return }
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2.6 数组运算与矩阵运算
• 一、数组运算 • Matlab定义了数组运算，数组运算是指对数组中的每个元 素进行相同的运算。数组运算可以通过Matlab提供的运算 符和数组运算函数实现。
1.用数组运算符进行数组运算 • A+B 数组加法运算 • A- B 数组减法运算 • A.*B 数组相乘，A和B相同位置元素的乘积作为结果数组的元素 • A./B 数组相除，A和B相同位置元素相除作为结果数组的元素 • A.\B 与A./B相同
2.4 高维数组
• 二、多维数组的访问 • 对于高维数组的访问，有下列约定：
可以通过全下标方式访问。对于三维数组来说，第一维下标称为“行 下标”，第二维下标称为“列下标”，第三维下标一般称为“页下 标。” 可以通过单下标方式访问。高维数组的单下标是按照后维优先的次序 排列的，对于三维数组来说，先排列“页”，页内先排列“列”，列 内再排列“行”，即第1行第1列第1页的元素单下标为1，然后先变化 行下标，再变化列下标，最后变化页下标。 数组的维数通过ndims函数获取。 例2.4.2 数组的尺寸通过size函数获取 数组的所有维中的最大长度通过length函数获取。
2.2 一维数组
3、线性分隔法 【说明】 linspace函数的调用格式为：x=linspace(a, b, n) 数组的第一个元素值为a，最后一个元素值为b，数组中共有n个元
素， 这n个元素线性均匀分布于a和b之间，即数组元素依次为
a ba * i, n 1 i 0, 1,..., n 1
1、cat •
•
• •
格式：
C = cat(dim, A, B)
C = cat(dim, A1, A2, A3, A4, ...)
说明： A，B，A1，A2等为被串接数组，要求这些数组同维； dim表示串接方向，1表示行，2表示列，3表示页，以此类推。
2.5 数组操作
2、fliplr
•
• • • • •
一维数组
一、一维数组的创建
1．逐个元素输入法 例子：a=[1,2,3] 2．冒号运算符法 【说明】 冒号运算符的格式是： startv : step : endv startv是初值，即数组的第一个元素值。 endv是终值，即数组的最后一个元素值。 step称为步长，即数组元素每次增加的值； 步长setp可以省略不写，此时默认步长为1； setp可以为负值，此时要求startv>endv 例子：b=1:1:5; b=1: :5; b=5:-1:5
2.5 数组操作
7．diag • 功能：产生对角阵，即矩阵的某个对角线元素不全为0，其他元素为0。 • 格式： X = diag(v,k) 生成length(v)+k阶方阵，并在第k条对角线放置元素v X = diag(v) 生成length(v)阶方阵，并在主对角线放置元素v v = diag(X,k) 返回方阵X的第k条对角线元素构成的列向量 v = diag(X) • 说明： v为行向量，表示对角线元素； 返回方阵X的主对角线元素构成的列向量
例2.2.1
2.3 二维数组
• 一、二维数组的建立 1．逐个输入数组元素值 如果数组内元素数量少，可以直接从键盘逐个输入元素的 值，需要遵循的规则是： 整个数组必须用中括号“[ ]”括起来 数组的行与行之间用分号“;”分隔，或者用回车符分隔 每行之间的元素必须用逗号“,”或者空格分隔 分隔符必须是英文字符，即在英文状态下输入分号、 括号、方括号、逗号等
功能：沿着垂直中线，左右（Left-Right）对称交换数组元素（不超 过2维）
格式：B = fliplr(A) 功能：沿着水平中线，上下（Up-Down）对称交换数组元素（不超过2 维） 格式：B = flipud(A) 功能：逆时针旋转二维数组。 格式：B = rot90(A) 逆时针旋转矩阵90度
2.3 二维数组
• 【说明】有关空数组
某一维长度为0的数组称为空数组; 空数组用[ ]表示，表示数组中没有元素，但可以表示计 算结果为“空”; 仅仅能用isempty函数正确判断数组是否为空; 可以通过给数组元素赋值空数组来缩小数组的大小; 尽量不要用空数组参与逻辑运算和关系运算;
2.1 引 言
数组（Array）可以是一维的行（或列），也可以是二维 或多维的。用户可以操作整个数组，也可以操作数组中的 某个或者某些元素。 MATLAB会根据表达式的运算结果，自动确定变量的类型 和大小。 变量的数据类型可以用以下函数来查看：
isa（var，’type’） %变量var的数据类型名称如果是type，则返回1，否则返回0 class （var） %查看变量var的数据类型 whos var %查看变量var的详细情况
2.5 数组操作
6．eye • 功能：产生单位矩阵，即主对角线元素都为1而其他元素都为0的二维 数组 • 格式： Y=eye(n) Y=eye(n,m) Y=eys(size(A)) Y=eye(m,n,classname) • 说明：classname是字符串，表示元素的数据类型名称，可取 'double', 'single', 'int8', 'uint8', 'int16‘, 'uint16'， 'int32', 'uint32', 'int64', 'uint64'。
例2.3.4
2.4 高维数组
• 一、高维数组的创建
• 可以采用下列方法创建高维数组：
直接通过全下标方式进行元素赋值； 用低维数组合成高维数组； 用数组生成函数（ones/zeros/rand等）生成高维数组； 用数组操作函数（repmat/reshape等）构造高维数组。
例2.4.1
2.5 数组操作
• 一、标准数组的生成 • 数学中定义了很多标准数组或者矩阵，如全1数组、全零数组、对角 阵等，在Matlab中有相应的函数用来生成这些标准数组。 1．ones • 功能：生成全1数组，即数组中的元素都为1。 • 格式： Y=ones(n) 生成n×n的全1矩阵 Y=ones(m1,m2,„,mk) 生成1×m2ׄ×mk的全1数组 Y=ones(size(A)) 生成和数组A同样尺寸的全1数组 2．zeros • 功能：生成全0数组，即数组中的元素都为0。 • 格式：同ones函数
2.5 数组操作
3．rand • 功能：生成均匀分布随机数组。 • 格式： Y=rand(1,5) 设置随机发生器的初始状态为v 其他同ones函数 4．randn • 功能：产生正态分布随机数组。 • 格式：同rand函数 5．magic • 功能：产生魔方矩阵,不适用于高维数组。 • 格式： M=magic(n) 产生n×n的魔方矩阵
2.5 数组操作
7、tril • 功能：提取矩阵的下三角元素，生成下三角阵。 • 格式：L = tril(X) L = tril(X,k) • 说明：X为待提取的矩阵；k为三角阵的分界线位置，含义同diag 8、triu • 功能：提取矩阵的上三角元素，生成上三角阵。 • 格式：L = triu(X) L = triu(X,k) • 说明：X为待提取的矩阵；k为三角阵的分界线位置，含义同diag函数。 例2.5.2 例2.5.3
2.6 数组运算与矩阵运算
• • • • • • A.^p 数组各元素求p次幂 A#B A、B数组对应元素间进行关系运算，#代表关系运算符 A@B A、B数组对应元素间进行逻辑运算，@代表逻辑运算符 A. ′ 数组转置，非共轭转置 s◎A 标量s与数组A运算， s与A的每个元素进行运算， ◎代表某个运算符
2.3 二维数组
• 二、二维数组的访问 • 二维数组的访问遵循以下约定：
用下标方式访问数组元素，下标要用一对圆形括号()引起来； 用双下标方式访问数组元素，格式为(r,c)，其中r为二维数组的行下标， c为二维数组的列下标，下标之间用逗号分隔； 用单下标方式访问二维数组，二维数组的单下标是按照列优先规则排序 的，即二维数组被看作是从第一列开始从左到右依次将各列首位连接而 成的一维数组，单下标表示元素在这个一维数组中的位置； 单下标和双下标具有对应关系，其值可以通过ind2sub和sub2ind函数进 行转换； 可以访问二维数组的某个元素及其子数组，可以对元素和子数组赋值。 例2.3.3
2.2 一维数组
• 二、一维数组的访问 • 一维数组的访问遵循以下约定： 用下标方式访问数组元素，下标要用一对圆括号()引起来; 下标代表的是元素在数组中的位置序号，从1开始，最大 值为数组中元素的个数; 下标可以是常量，也可以是变量; 可以访问数组中的单个元素，也可以访问数组中的某些元 素，即数组的子数组。
• 数据结构是程序设计的重要基础，使用合理的数据结构去 描述问题，能够缩短程序代码、简化程序结构、便于程序维护。 • 在MATLAB里共有六种基本数据类型，每一种类型可以构 成一维、二维和多维的数组。这六种是：
双精度型（double）： 双精度数值类型，是最常用的类型； 字符型（char）：字符数组，每个字符占16位 ； 稀疏型（sparse）：双精度稀疏矩阵，只存储矩阵中的非0元素； 细胞型（cell）：细胞，可以存放任意类型数据 结构体（struct）：不同类型的数据集合 存储型（storage）：用于图像处理
k为对角线位置，k=0 表示主对角线，k>0表示在主对角线上方的第k条 对角线，k<0表示在主对角线下方的第(-k)条对角线。
例2.5.1
2.5 数组操作
•
•
二、 数组操作
对数组的操作包括数组的扩展、收缩、重排、元素交换和子数组访 问等。数组操作可以通过两种方式实现，一种是通过Matlab提供的运 算符（逗号，分号，括号等）来实现，另外一种是使用Matlab提供的 数组操作函数。下面介绍常用的数组操作函数。 功能：把大小相同的若干数组，沿着指定维的方向，串接成新数组。