资源简介

(共22张PPT)
第14课线性表
第15课数据结构与算法
数据结构：数据之间的相互关系及数据的组织方式。
复习巩固
先进后出
先进先出
队列
数组
栈
线性结构
特殊的线性表
复习巩固
打印机打印文件
浏览网页
线性结构是最基本、最简单，也是最常用的一种数据结构。（一对一）
线性表是一种最基础的线性结构，是由n个相同类型元素组成的有限序列。
（n=0时为空表）
1 线性表的概念
线性表有且仅有一个开始结点和一个终端结点。
线性表所有结点都最多只有一个前驱节点和一个后继节点。
a0 a1 …… ai-1 ai ai+1 …… an-1
A B C D E F …… Z
首节点
尾节点
无前驱节点
无后继节点
学号 姓名 语文 数学 英语
1 小明 95 100 98
2 小张 96 98 95
3 小林 92 95 100
4 小王 88 90 97
5 小赵 89 85 95
……
是线性表吗？
春 夏 秋 冬
数据的存储方式(物理结构）
数据自身的逻辑关系(结构）
线性表的存储方式一般有顺序存储结构和链式存储结构两种。
链式存储方式
顺序表
顺序存储结构
链表
A B C D E F G
A
B
C
D
E
F
G
二、线性表的存储结构
顺序表
顺序存储结构
小明 小张 小林 小王 小赵
二、线性表的存储结构
学号 姓名 语文 数学 英语
1 小明 95 100 98
2 小张 96 98 95
3 小林 92 95 100
4 小王 88 90 97
5 小赵 89 85 95
……
逻辑上相邻的两个数据在物理上也相邻
链表
链式存储方式
二、线性表的存储结构
学号 姓名 语文 数学 英语
1 小明 95 100 98
2 小张 96 98 95
3 小林 92 95 100
4 小王 88 90 97
5 小赵 89 85 95
……
数据分散地存储在物理空间中
小明
小张
小林
小王
小赵
需要存储两个部分：
数据信息和后继元素的位置信息（指针）
三、数据组织与算法
线性表的常用操作：
学号 姓名 语文 数学 英语
1 小明 95 100 98
2 小张 96 98 95
3 小林 92 95 100
4 小王 88 90 97
5 小赵 89 85 95
……
访问元素
插入元素
删除元素
查找学生
增加学生
删除学生
访问元素
a0 … a45 a46 a47 a48 … a900
小明 ….. 小林 小王 小赵 小军 ….. 小刘
顺序表常用数组的方法来实现
数据元素
数组下标
小明
…
…
小张
小林8
小王
小赵
1154
a0
a45
a46
a47
a48
a900
a47
小明
…..
小林
小王
小赵
小刘
小军
a0 … a45 a46 a47 a48 … a900
数据组织与算法在数组或链表中插入某个元素，分别采用怎样的算法？小明小张小林小王小赵head小明小张小林小王小赵null将元素“小海”插入到元素“小王”的前面小海小海小海设计两个不同的算法，在数组或链表中删除某个元素，比较两种算法的效率。小明小张小林小王小赵head小明小张小林小王小军null删除数组或链表中的元素“小张”小军小赵（ ）
方法一：……
方法二：……
方法三：……
算法效率
时间效率
储存量需求
空间效率
算法的执行时间
算法在执行过程中
需要的最大存储空间
四、算法效率
队列
数组
栈
线性表
线性结构
（一对一）
非线性结构
图（多对多）
树（一对多）
数据结构
逻辑结构
存储结构（物理结构）
链式存储方式
顺序存储结构
1.线性表是一个__________。
A. 有限序列，可以为空
B. 有限序列，不能为空
C. 无限序列，可以为空
D. 无限序列，不能为空
A
2.下面关于线性表的叙述中，错误的是 _________。
A. 线性表采用顺序存储，必须占用一片连续的存储单元
B. 线性表采用顺序存储，便于进行插入和删除操作
C. 线性表采用链接存储，不必占用一片连续的存储单元
D. 线性表采用链接存储，便于进行插入和删除操作
B
3.用链式存储方式来存储线性表的优点是______。
（A）便于随机读取
（B）花费的存储空间较顺序存储少
（C）便于插入和删除
（D）数据元素的物理顺序与逻辑顺序相同
C
21
24
36
57
77
87
99
14
a
4.若长度为8的一维数组，第一个元素为a[0],删除第3个数据元素后，需要向前移动________个数据元素，删除后数组元素a[5]的值是___________；然后在将66插入到数组中，使数组仍然按照从小到大排列，请问需要______移动步骤？
课堂练习
5
87
3
5.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( )
A. n-i+1 B. n-i
C. i D. i-1
A
6.若长度为n的顺序存储结构线性表， 在第i个位置删除一个元素，需要依次向后移动 _____个元素。
A. n-i+1 B. n-i
C. i D. i-1
B
7.一个顺序表所占存储空间的大小与______无关。
A．顺序表长度 B．结点类型
C．结点中各数据域的类型 D．结点的存放次序
D
8.以顺序存储结构实现的线性表简称为 __________，它要求存储空间必须是_________，并以下标来体现元素之间的关系，在顺序表中访问第i个元素的时间复杂度为 O（1） ，因此，顺序表也称为随机存取的数据结构。 以链式存储结构实现的线性表称为_________。其存储空间可以是_____________，以指针来体现元素之间的关系。在链表中访问第i个元素的时间复杂度为 O（n），因此，链表也称为顺序访问的数据结构。
顺序表
连续的
不连续的
链表

展开更多......

收起↑