计算机应用基础课件1.2线性表.ppt
《计算机应用基础课件1.2线性表.ppt》由会员分享,可在线阅读,更多相关《计算机应用基础课件1.2线性表.ppt(63页珍藏版)》请在优知文库上搜索。
1、第第 1 章章 数据结构数据结构 1.1 基本数据结构与算法基本数据结构与算法 1.2 线性表线性表 1.3 栈和队列栈和队列 1.4 树和二叉树树和二叉树 1.5 查找查找 1.6 内部排序内部排序ABCDEFG姓名姓名 学号学号 成绩成绩 班级班级 李红李红 9761059 95 机机97.6 10658651.2 线性表1.线性表的定义线性表的定义1)定义:定义:具有具有相同数据类型相同数据类型的的n(n0)个数据元素组成的个数据元素组成的有限有限序序列。是最简单、最常用的数据结构。列。是最简单、最常用的数据结构。2)表示表示:L=(a0,a2,a3,ai-1,ai,ai+1,,.,an
2、-1)其中其中:n n为为线性表长度线性表长度(n=0n=0称为空表称为空表),表中相邻元素之间,表中相邻元素之间存在着顺序关系。存在着顺序关系。a a0 0 :表头表头元素;元素;a an-1 n-1:表尾表尾元素;元素;a ai-1i-1称为称为a ai i的直接的直接前驱前驱;a ai+1i+1 称为称为a ai i的直接的直接后继后继。表头表尾1.2 线性表1.线性表的定义线性表的定义1)定义:定义:具有具有相同数据类型相同数据类型的的n(n0)个数据元素组成的个数据元素组成的有限有限序序列。是最简单、最常用的数据结构。列。是最简单、最常用的数据结构。2)表示表示:L=(a0,a2,a
3、3,ai-1,ai,ai+1,.,an-1)3)线性结构特点线性结构特点:(1)(1)有且只有一个根结点有且只有一个根结点a a0,无前驱,无前驱 。(2)(2)有且只有一个终端结点有且只有一个终端结点a an-1n-1 ,无后继,无后继 。(3)(3)其他结点有且只有一个直接前驱和一个直接后继。其他结点有且只有一个直接前驱和一个直接后继。1.2 线性表1.线性表的定义线性表的定义1)定义:定义:具有具有相同数据类型相同数据类型的的n(n0)个数据元素组成的个数据元素组成的有限有限序序列。是最简单、最常用的数据结构。列。是最简单、最常用的数据结构。2)表示表示:3)线性结构特点线性结构特点:4
4、)线性表的分类线性表的分类 (1)简单线性表:简单线性表:数据元素是简单项数据元素是简单项(数字、字母、季节名等数字、字母、季节名等)。如如:(12,34,4,67,8):(12,34,4,67,8)(2)复杂线性表:复杂线性表:数据元素由数据元素由若干个数据项若干个数据项组成,此时数据元素称为组成,此时数据元素称为记录记录或结点或结点,如学生成绩表如学生成绩表.L=(a0,a2,a3,ai-1,ai,ai+1,.,an-1)学生健康情况登记表如下:姓姓 名名学学 号号性性 别别年龄年龄 健康情况健康情况王小林王小林790631 男男 18 健康健康陈陈 红红790632 女女 20 一般一般
5、刘建平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 神经衰弱神经衰弱.1.1.顺序表基本概念顺序表基本概念1.2.2 线性表的顺序存储结构1)顺序存储结构:顺序存储结构:用一用一组地址连续的存储空间组地址连续的存储空间依次存放线性表的各元素依次存放线性表的各元素 。顺序表:顺序表:采用顺序存储结构的线性表称为顺序表采用顺序存储结构的线性表称为顺序表(一维数组一维数组)表中的所有元素所占表中的所有元素所占存储空间连续存储空间连续表中各元素在存储空间中按表中各元素在存储空间中按逻辑顺序存放逻辑顺序存放 顺序存储结构特点顺序存储结构特点1.2 线性表1.1.顺序表基本
6、概念顺序表基本概念4.2.2 线性表的顺序存储结构1)顺序存储结构:顺序存储结构:2)第第i个元素地址个元素地址4.2 线性表其中其中:m:每个元素占:每个元素占m个存储单元个存储单元Loc(a0)第一个元素地址第一个元素地址(基址基址)mi)Loc(a)Loc(a0ian1.ai.a1a0bb+mb+i*mb+n*m存储地址存储地址存储状态存储状态空闲空闲数据元素在线性表中的位序数据元素在线性表中的位序12n i 从存取方式看从存取方式看,线性表的顺序存储线性表的顺序存储结构是可以结构是可以随机存随机存储储的存储结构的存储结构.1.1.顺序表基本概念顺序表基本概念1.2.2 线性表的顺序存储
7、结构1)顺序存储结构:顺序存储结构:2)第第i个元素地址个元素地址1.2 线性表2.顺序表的基本运算顺序表的基本运算 存取存取:访问线性表的第访问线性表的第i个元素,使用或改变数据元素个元素,使用或改变数据元素的值。的值。查找查找:在线性表中查找满足某种条件的数据元素。在线性表中查找满足某种条件的数据元素。插入插入:在线性表的第在线性表的第i个元素之前,插入一个同类型的个元素之前,插入一个同类型的元素。元素。(*)删除删除:删除线性表中第删除线性表中第i个元素。个元素。(*)求表长求表长:求出线性表中元素的个数。求出线性表中元素的个数。置空表置空表:建立一个空表。建立一个空表。清除表清除表:将
8、已有线性表变为空表,即删除表中所有元素。将已有线性表变为空表,即删除表中所有元素。1.1.顺序表基本概念顺序表基本概念1.2.2 线性表的顺序存储结构1)顺序存储结构:顺序存储结构:2)第第i个元素地址个元素地址1.2 线性表2.顺序表的基本运算顺序表的基本运算 顺序表的插入运算顺序表的插入运算:在线性表的第在线性表的第i i个元素之前插入一个元素之前插入一个新的元素,先移动,后插入。个新的元素,先移动,后插入。ai-1.a1a0an-1ai+1ai x ai-1.a1 a0 ai an an-1 ai+1 ai ai先移动先移动后插入后插入 x步骤:步骤:(1)将将ai an顺序向后移动顺序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 应用 基础 课件 1.2 线性