第1章线性数据结构（一）

《第1章线性数据结构（一）》由会员分享，可在线阅读，更多相关《第1章线性数据结构（一）（70页珍藏版）》请在金锄头文库上搜索。

1、1 /70,第1章 线性数据结构（一）,教材: 1.1 数据结构概述 1.2 线性表 教学目标： 了解数据结构的有关概念 了解线性DS的概念、特点 掌握线性表的逻辑结构、物理结构以及操作,2 /70,学习要求,1. 掌握以下基本概念 数据元素、DS、逻辑结构、物理结构 2. DS的分类及特点、时间复杂度等 3. 线性DS的常用存储结构 顺序、链表、索引、散列存储结构 单向、双向、循环链表等 4. 线性DS的有关算法 增、删、改,3 /70,1.1 数据结构概述,一、基本概念 1. 数据（Data） 存储在计算机中、并被计算机处理的符号的集合,是客观事物的符号表示。 2. 数据元素（Elemen

2、t） 组成数据的基本单位 可由若干个数据项组成 数据集合中的个体,对应结点(节点)。,4 /70,二. 数据结构,1. 数据结构（Data Structure） 1) 研究数据及数据元素之间的关系. 2) 组成要素： DS=数据的逻辑结构+ 存储结构+ 数据的运算,5 /70,2. 数据的逻辑结构,1) 描述数据间的逻辑关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。 2) 定义: DS=（D，R） 其中： D：数据元素的有限集合； R：数据元素之间关系的集合。,6 /70,3.数据结构分类,线性表 堆栈 队列 串 数组,树 二叉树 图,线性结构,非线性结构,数据结构 DS,

3、7 /70,4. 数据的存储结构,又称物理结构 是指数据结构在计算机中的表示(又称映象),即数据在计算机中的存放方式。,8 /70,逻辑结构和物理结构的关系,1. 逻辑结构 从逻辑关系上观察数据，独立于计算机；可以在理论上、形式上进行研究、推理、运算等各种操作。 2. 存储结构 逻辑结构在计算机中的实现，依赖于计算机。 3. 任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。,9 /70,数据存储结构分类,顺序存储结构 链式存储结构 索引存储结构 散列存储结构,10 /70,(1) 顺序存储结构,把数据元素按某种顺序存放在一块连续的存储单元中。 结点结构: 特点:

4、1) 连续存放,逻辑上相邻,物理上也相邻。 2) 结构简单，易实现。 3) 插入、删除操作不便（需大量移动元素）,d1 d2 dn,数据域,11 /70,(2) 链式存储结构,数据元素存放在任意存储单元中，可连续存放，也可以不连续存放，用指针实现链表间的联系。 结点结构: 特点: 1) 插入、删除操作只要修改指针即可 2) 结构较复杂，需要额外存储空间。,d1,.,d2,dn NULL,12 /70,(3) 索引存储结构,存储两部分内容： 数据元素序列和索引表 索引表组成: 数据元素的某个数据项和该元素存储地址 结点结构: 序号： 1 2 3 4 5 6 7 数据项： 索引号： 特点： 非连续

5、存放 增 、删操作简单 检索速度快 数据元素长度可不等,12 21 35 2 45 5 10,4 3 2 7 1 6 5,数据项 索引顺序号,13 /70,(4) 散列存储结构,在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到它的存储地址，即D=F（E）。 特点： （1）数据元素间无内在联系 （2）存储形式不定 实例：哈希查找中的哈希表,14 /70,5. 数据运算,（1）数据运算 是指对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。 （2）每个数据结构都有一个运算的集合 （3）常见操作 检索、插入、删除、修改,15 /70,三、算法与算法分析,1.

6、 算法（Algorithm） 是对特定问题求解步骤的一种描述； 2. 算法和运算的关系 运算依赖于逻辑结构 算法依赖于存储结构 3. 研究算法追求的目标 时间和空间的适当和谐,16 /70,4. 算法的特性,有穷性 一个算法必须总是在执行有穷步后结束，且每一步都可在有穷时间内完成； 确定性 算法中的每一个指令必须有明确的含义，不能有二义性； 可行性 算法中描述的操作都是可通过已经实现的基本运算、执行有限次实现的； 输入 一个算法应有0个或多个输入； 输出 一个算法应有1个或多个输出。,17 /70,5. 算法的描述方式,(1) 自然语言 (2) 流程图 用特定图形符号进行算法描述 (3) 伪语

7、言 包括程序设计语言的三大基本结构及自然语言的一种语言 (4) 类语言 类似高级语言的语言，例如类PASCAL、类C语言。,18 /70,6.算法的评价标准,(1)时间复杂度 指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。常见的时间复杂度： O(1) O(logn) O(n ) O( n2) 常数阶 对数阶 线性阶 平方阶 (2) 空间复杂度 指算法在计算机上运行所占用的存储空间。度量同时间复杂度。,19 /70,时间复杂度举例,（a） O(1) X：=X+1 ； （b） O(n) FOR I：=1 TO n DO X：= X+1； （c） O( n2) FOR I

8、：= 1 TO n DO FOR J：= 1 TO n DO X：= X+1；,20 /70,1.2 线性表,是指数据元素之间的关系为一一对应的线性关系的数据结构。 例如，一星期七天的英文缩写表示： （Sun，Mon，The，wed，Thu，Fri，Sat）是一个线性表，其中的元素是字符串，表的长度为7。,21 /70,（一）线性表的逻辑结构,定义： 线性表是n（n0）个元素a1,a2,an 的有限序列;表中每个数据元素,除了第1个和最后1个外,有且仅有一个前趋元素和后继元素。,22 /70,形式定义： 含有n个数据元素的线性表是一种数据结构，表示为： Linear_list=( D , R

9、) 其中: D=ai | aiD0,i=1,2,3,n,n 0 R=N, N=| ai-1,ai D0 ,i=1,n D是数据元素的有限集合,R是D上逻辑关系的有限集合。关系N是一个有序偶对的集合。,23 /70,相互关系描述,1）L的长度为n（n 0），n=0时是空表； 2）除了第1个和最后一个元素外,每个元素有唯一的前趋和后继； 3）线性表中各元素间存在着线性关系； 4）均匀性；各元素数据类型必须相同； 5）有序性；各元素是有序的，不可交换次序。,24 /70,线性表的基本操作,Setnull(L) 置空表 Length(L) 求表长度,即表中元素个数 Get(L,i) 取表中第i个元素（

10、1i n） Prior(L,i) 取i的前趋元素 Next(L,i) 取i的后继元素 Locate(L,x) 返回指定元素在表中的位置 Insert(L,i,x) 插入元素 Delete(L,x) 删除元素 Empty(L) 判别表是否为空,25 /70,（二）线性表的顺序存储结构,1. 顺序存储结构 表中元素顺序存入连续的存储单元中。 2. 顺序表 采用顺序结构的线性表。 3. 顺序表的存储特点 由起始位置计算表中任一元素的地址 LOC(ai)=LOC(a1)+C*(i-1) 1i n C: 元素占用存储单元的长度,26 /70,4. C语言实现 采用一维数组 #define MAXLENG

11、TH 100 int list MAXLENGTH； int last = -1； /*表中最后一个元素的序号,-1空表*/,27 /70,线性表元素存储示意图,a1,a2,.,ai,.,元素序号 内存状态 存储地址,1,2,.,i,.,LOC(a1),28 /70,算法1-1 插入元素算法,算法步骤: step1 将第n至第i个元素后移一个存储位置; step2 将x插入到ai-1之后; step3 表的长度加1。,29 /70,算法1-1 插入算法,insert（int i，int x） /* last为全局变量*/ int k； if（last+1=MAXLENGTH） printf（“

12、线性表已满！n”); exit(-1); if (ilast+1) printf(“插入位置错误!n” ); exit(-2); else,30 /70, for (k=last-1;K=i-1;k-) listk+1=listk; list i-1 =x; +last; ,31 /70,算法1-1 插入算法主程序,#define MAXLENGTH 100 /* 例1-1主程序 */ int listMAXLENGTH=5,3,1,10,7,8,-1,4; int last=7; /* last为全局变量*/ main（） int x,j,loc; printf(“Enter x、locn”

13、); scanf(“%d,%d”,32 /70,printf(“n”); insert(loc,x); /* 调用插入函数 */ for (j=0;j last+1,j+) printf(“%d “,listj); printf(“n”); ,33 /70,算法1-2 线性表删除元素,算法步骤: step1 判别指定的位置是否合法； step2 若合法，则将位置i+1至n的元素前移一个存储位置; step3 表的长度 - 1。,34 /70,算法1-2 线性表删除算法,delete(int i) /*第i 个元素的下标为I-1 */ int k; if( i last ) printf(“表中

14、不存在位置为i的元素 n”); exit(-1); for(k= i-1;k=last-1;k+) listk=listk+1; last-; ,35 /70,算法1-2 线性表删除算法,#define MAXLENGTH 100 /* 例1-2主程序 */ int listMAXLENGTH=5,3,1,10,7,8,-1,4; int last=7; main（） int j,loc; printf(“Enter locn”); scanf(“%d”,36 /70,printf(“n”); delete(loc); /* 删除子函数 */ for (j=0;j last+1;j+) pri

15、ntf(“%d “,listj); printf(“n”); ,37 /70,顺序存储结构的特点,1. 数据连续存放、随机存取 2. 逻辑上相邻，物理上也相邻 3. 存储结构简单、易实现 4. 存储密度大，空间利用率高 5. 插入、删除操作移动数据,不方便 结论： 适合于表中元素变动较少的情况,38 /70,（三 ）线性表的链式存储结构,顺序存储结构容易实现，可以随机存取表中的任意元素。 顺序表缺点： 难于插入、删除操作； 需要预先分配空间，不管这些空间能否最大限度地利用。 链表存储结构在这两个方面恰好是优点： 容易插入、删除操作 不需要预分空间。,39 /70,1、链表的有关概念,结点（NODE） 表中元素的存储单元。 结点的结构： 结点的C语言描述： struct node int data ; struct node *next ; ; typedef struct node NODE；,40 /70,基本概念,1) 链表: 由结点组成的表。 2) 头结点: 为方便操作，在头指针和第一个结点之间设置的结点。 3) 首元结点: 链表的第一个结点 4) 头指针: 指向链表中头结点的指针。,