计算机应用基础课件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顺序向后移动顺序

9、向后移动,为新元素让出位置为新元素让出位置(2)将将x置入置入”空出空出”的第的第i个位置个位置举例：举例：(在第在第4个和第个和第5个元素之间插入元素个元素之间插入元素91)6741262148916 0 1 2 3 4 5 6 7 86741262148916 0 1 2 3 4 5 6 7 86741262148916 0 1 2 3 4 5 6 7 8212191插入程序举例插入程序举例(在在8 8个数中任意位置插入一个数个数中任意位置插入一个数)：#define N 8#define N 8main()main()int aN+1=12,34,45,6,78,9,10,91,i,j,

10、x;int aN+1=12,34,45,6,78,9,10,91,i,j,x;printf(“input the location to be inserted:”);printf(“input the location to be inserted:”);scanf(“%d,%d”,&i,&x);scanf(“%d,%d”,&i,&x);ai-1=x;ai-1=x;for(j=0;j=N;j+)for(j=0;j=N;j+)printf(“%d,”,aj);printf(“%d,”,aj);for(j=i-1;j=for(j=i-1;j=i-1;j-);j=i-1;j-)aj+1=aj;aj

11、+1=aj;在第在第i i个位置上作插入个位置上作插入x,x,则需将第则需将第i i个至第个至第n n个元素移动，即个元素移动，即共需移动共需移动(n-i+1)(n-i+1)个元素。个元素。插入运算时间性能分析：插入运算时间性能分析：插入运算，时间主要消耗在数据移动上。在长度为插入运算，时间主要消耗在数据移动上。在长度为n n的线性的线性表中插入一个元素，则表中插入一个元素，则平均移动元素次数平均移动元素次数(期望值期望值)：?)1(11niiisinpEp pi i：在第：在第i i个位置上作插入的概率。个位置上作插入的概率。等差数列求和公式等差数列求和公式:(首项首项+末项末项)项数项数)

12、/211)1(11niinn11npi(n-i+1)2n线性表线性表(a0,a1,a2)平平局移动元素个数局移动元素个数:()*(3+2+1+0)=1.5在一线性表在一线性表(a0,a1,a2)中插入任意一数中插入任意一数i，求平局移动元，求平局移动元素次数素次数:i 移动次数移动次数(n-i+1)1(插入到第个数插入到第个数a0前前)3 2(插入到第插入到第2个数个数a1前前)23(插入到第插入到第3个数个数a2前前)1(插入到第插入到第3个数个数a2后后)0 1.1.顺序表基本概念顺序表基本概念1.2.2 线性表的顺序存储结构1)顺序存储结构：顺序存储结构：2)第第i个元素地址个元素地址1

13、.2 线性表2.顺序表的基本运算顺序表的基本运算 2)2)顺序表删除运算：顺序表删除运算：定义：定义：指将表中第指将表中第i个元素从线性表中去掉。个元素从线性表中去掉。原表长为原表长为n n：(a0，a1，ai-1，ai，ai+1，an-1)新表长为新表长为n-1n-1：(a0，a1，ai-1，ai+1，an-1)步骤：步骤：(1)将将ai+1 an-1，顺序向前移动顺序向前移动(2)表长表长减一减一举例：举例：(删除第五个元素删除第五个元素21)6741262148916 0 1 2 3 4 5 6 7 867412648916 0 1 2 3 4 5 6 7 8时间性能分析：时间性能分析：

14、时间消耗与插入运算相同，时间消耗与插入运算相同，平均移动元素次数：平均移动元素次数：niniidlninninqE1121)(1)(q qi i:在第在第i i个位置上作插入的概率。设个位置上作插入的概率。设q qi i=1/n=1/n 共需移动共需移动(n-i)(n-i)个元素。个元素。67 i 移动次数移动次数(n-i)1(删除第删除第1个数个数a0)22(删除第删除第2个数个数a1)13(删除第删除第3个数个数a2)0线性表线性表(a0,a1,a2)平平局移动元素个数局移动元素个数:(1/3)*(2+1+0)=1在一线性表在一线性表(a0,a1,a2)中删除任意一数中删除任意一数i，求平

15、局移动元，求平局移动元素次数素次数:niniidlninninqE1121)(1)(作业作业：有一数组，存储十个数，：有一数组，存储十个数，编程序删除其中任意一个数。编程序删除其中任意一个数。1.1.顺序表基本概念顺序表基本概念3.3.顺序表优点和缺点顺序表优点和缺点优点：优点：逻辑上相邻元素逻辑上相邻元素存储位置也相邻存储位置也相邻,无需增加额外存无需增加额外存储空间可方便储空间可方便随机存取随机存取表中任一元素。表中任一元素。缺点：缺点：插入和删除运算不方便插入和删除运算不方便,必须移动大量结点必须移动大量结点,效率效率较低不适合元素经常变动的大的线性表。较低不适合元素经常变动的大的线性表

16、。1.2.2 线性表的顺序存储结构1.2 线性表2.顺序表的基本运算顺序表的基本运算1.1.链式存储结构特点链式存储结构特点:1.2.3 线性表的链式存储结构存储空间可以存储空间可以不连续不连续。不要求逻辑上相邻的元素在物理位置上也相邻。不要求逻辑上相邻的元素在物理位置上也相邻。数据元素间逻辑关系由数据元素间逻辑关系由指针域指针域确定。确定。1.2 线性表即即 链表存储结构是一种链表存储结构是一种动态动态数据结构，其特点是它数据结构，其特点是它包含的据对象的个数及其相互关系可以包含的据对象的个数及其相互关系可以按需要改按需要改变变，存储空间是程序，存储空间是程序根据需要根据需要在程序运行过程中在程序运行过程中向系统申请向系统申请获得，链表也不要求逻辑上相邻的元获得，链表也不要求逻辑上相邻的元素在物理位置上也相邻，它没有顺序存储结构所素在物理位置上也相邻，它没有顺序存储结构所具有的弱点。具有的弱点。zhang33531082548#namesumnext结构体结构体元素元素结构体元素结构体元素的地址的地址结构体元素的结构体元素的成员是地址型成员是地址型数据数据struct student