《《数据结构（C语言版）》电子教案－赵坚 数据结构02》由会员分享，可在线阅读，更多相关《《数据结构（C语言版）》电子教案－赵坚 数据结构02（77页珍藏版）》请在金锄头文库上搜索。
1、2019/5/24,1,本章主题：线性表的有关概念和基本运算 教学目的：掌握线性表的概念和类型定义 教学重点：线性表的顺序存储结构和链式存储结构 教学难点：线性表的基本运算,第2章 线性表,2019/5/24,2,线性表（Linear list）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。 通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。,本章学习导读,2019/5/24,3,线性表由一组具有相同属性的数
2、据元素构成。数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。 1 . 线性表的定义 线性表L是n（n0）个具有相同属性的数据元素a1，a2，a3，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。 当n=0时称为空表，即不含有任何元素。 常常将非空的线性表(n0)记作： (a1，a2，an) 这里的数据元素 ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。,2.1 线性表的基本概念,2019/5/24,4,例1、26个英文字母组成的字母表 （A，B，C、Z） 例2、从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，
3、188） 例3、,2019/5/24,5,从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1； 其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,2019/5/24,6,2 . 线性表的基本运算 数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现则是建立在存储结构上的。 (1) 初始化线性表Initlis
4、t(L) 将线性表L置为空表。 (2) 求线性表的长度Getlen(L) 求解并返回线性表所含元素的个数n。若线性表为空，则返回整数0。 (3) 按序号取元素Getelem(L,i) 读取线性表L第i个数据元素，要求满足1iGetlen(L)。,2019/5/24,7,(4) 按值查找Locate(L,x) 在线性表L中查找值为的数据元素，若查找成功则返回第一个值为x的元素的序号或地址; 否则，在L中未找到值为的数据元素，返回一特殊值（例如0），表示查找失败。 (5) 插入元素Inselem (L,i,x) 在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1
5、, ., n 的数据元素的序号变为 i+1,i+2, ., n+1，要求1iGetlen(L)+1，插入后原表长增1。 (6) 删除元素Delelem(L,i) 在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,., n 的元素变为序号i, i+1,.,n-1，要求1iGetlen(L)，删除后表长减。,2019/5/24,8,2.2 线性表的顺序结构及运算实现,线性表有两种基本的存储结构：顺序存储结构和链式存储结构。,1.线性表的顺序存储结构,顺序表具有以下两个基本特点： (1) 线性表的所有元素所占的存储空间是连续的。 (2) 线性表中各数据元素在存储空间中是按逻辑顺序
6、依次存放的。 由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间（字节数）相同。因此，要在此结构中查找某一个元素是很方便的，即只要知道顺序表首地址和每个数据元素在内存所占字节的大小，就可求出第i个数据元素的地址。,2019/5/24,9,假设线性表中的第一个数据元素的存储地址（首地址）为LOC(a1)，每一个数据元素占k个字节，则各元素的存储地址有如下关系： LOC（a2）=LOC(a1)k LOC（a3）=LOC(a2)k LOC（ai）=LOC(ai-1)k （2in） 因此，线性表中第i个元素ai在计算机中的存储地址为： LOC(ai)= LOC(a1)+(i-1
7、) k （1in） 即在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的序号惟一确定。一般来说，长度为n的线性表 (a1，a2， an)在计算机中的结构如下：,2019/5/24,10,2019/5/24,11,在具体实现时，一般用高级语言中的数组来对应连续的存储空间。设最多可存储MaxLen个元素，在C语言中可用数组dataMaxLen来存储数据元素，为保存线性表的长度需定义一个整型变量length。线性表的第l，2，n个元素分别存放在此数组下标为0，1，length-1数组元素中，如下图所示,2019/5/24,12,这样，一个线性表的顺序存储结构需要
8、两个分量。为体现数组data和length之间的内在联系，通常将它们定义在一个结构类型中。此处的元素类型用ElemType来表示。 综上所述，在C语言中，可用下述类型定义来描述顺序表： #define MaxLen 100 /线性表的容量 typedef int ElemType /在实际应用中，将ElemType定义成实际类型 typedef struct ElemType dataMaxLen; /定义存储表中元素的数组 int length; /线性表的实际长度 sqList; sqList L; /定义表结构的变量,2019/5/24,13,2.2.2 线性表在顺序存储结构下的运算实现
9、 本节将讨论采用顺序存储结构之后，如何实现线性表的基本运算，并讨论各算法时间复杂度。 1初始化顺序表initlist(L)的实现 顺序表的初始化即构造一个空表，顺序表L是否为空取决于其元素个数是否为0，因此，只要将表L中的表长度置为0，就可以实现建空表的功能。 void initlist(sqList *L) L-length=0; 2求线性表长度Getlen(L)的实现 求线性表的长度算法如下： int Getlen(sqList *L) return L-length; 该算法的时间复杂度为O(1),2019/5/24,14,3按序号取元素Getelem(L,i)的实现 按前面的约定，序号
10、为i的元素存储在数组下标为i-1的数组元素中，所以可直接从该数组元素中取得值。i的有效值应大于等于1和小于等于线性表的实际长度。 ElemType Getelem(sqLlist *L,int i) if(iL-length) printf(“error”); exit(1); return L-datai-1; 4查找运算locate(L,x)的实现 要 确定值为x的元素在L表中的位置，需要依次比较各元素。当查询到第一个满足条件的数据元素时，返回其序号，否则返回0，表示查找失败。,2019/5/24,15,查找操作的具体实现算法如下： int Locate(sqList *L,ElemTyp
11、e x) int i; i=0; while(ilength ,5顺序表的插入算法inselem(L,i,x)的实现 顺序表的插入是指在表的第 i个位置上插入一个值为 x的新元素，插入后使原表长为 n的表：(a1，a2， ，ai-1，ai，ai+1， ，an)，成为表长为 n+1的表：,由算法可知，对于表长为n的顺序表，在查找过程中，数据元素比较次数最少为1，最多为 n，元素比较次数的平均值为 (n+1)/2，时间复杂度为 O(n)。,2019/5/24,16,(a1，a2，ai-1，x，ai，ai+1，an ), i 的取值范围为1in+1 。下图表示一个顺序表中的数组在进行插入运算前后，数
12、据元素在数组中的下标变化。,序号 元素,序号 元素,插入x,插入前,插入后,2019/5/24,17,void Inselem(sqList *L,int i,Elemtype x) if (iL-length+1) printf(“Error!”) ; /插入位置出错 exit(1); if(L-length=MaxLen) printf(“overflow!”) ; /表已满 exit(1); for(j=L-length;j=i;j-) L-dataj+1=L-dataj; /数据元素后移 L-datai=x; /插入x L-length+; /表长度加1 ,2019/5/24,18,假
13、设表中任何位置插入概率是均等的,即Pi=1/ (n+1) ,则：,该算法的时间主要花费在移动数据元素上，移动个数取决于插入位置 i和表的长度n。所以可以用数据元素的移动操作来估计算法的时间复杂度。在第 i个位置上插入 x ，共需要移动 n-i+1个元素， i 的取值范围为 ：1i n+1，即有 n+1个位置可以插入。 当i=n+1时，不需要移动结点；当i=1时需要移动n个结点 。由此可以看出，算法在最好的情况下时间复杂性为O(1)，最坏的时间复杂性是O(n)。 由于插入的位置是随机的，因此，需要分析执行该算法移动数据元素的平均值。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：,
14、2019/5/24,19,由此可以看出，在线性表上做插入操作需要移动表中一半的数据元素，当n较大时，算法的效率是比较低的，所以在线性表上进行插入操作的时间复杂度为(n)。 6顺序表的删除运算Delelem(L,i)的实现 顺序表的删除运算是指将表中第 i 个元素从线性表中去掉，原表长为 n 的线性表(a1，a2， ，ai-1，ai，ai+1，an) 。进行删除以后的线性表表长变为 n-1的表 (a1，a2， ，ai-1，ai+1， ，an)， i 的取值范围为：1in 。 图2-5表示一个顺序表的数组在进行删除运算前后，其数据元素在数组中的下标变化。,2019/5/24,20,图2-5 线性表
15、中的删除运算示意图,2019/5/24,21,在线性表上完成上述运算通过以下两个操作来实现： (1) 线性表中第i个至第n个元素（共n-i+1个元素）依次向前移动一个位置。将所删除的元素ai覆盖掉，从而保证逻辑上相邻的元素物理位置也相邻。 (2)修改线性表长度，使其减1。 线性表的删除算法如下： void Delelem(sqList *L,int i) /删除线性表中第i个位置上的元素 if(iL-length) /检查空表及删除位置的合法性 printf (不存在第i个元素);exit(0); for(j=i;jlength-1;j+) L-dataj-1=L-dataj; /向前移动元素 L-length-; ,2019/5/24,22,删除算法的时间性能分析： 与插入运算相同，删除运算的时间也主要消耗在移动表中数据元素上，删除第i个元素时，其后面的元素 ai+1an 都要向前移动一个位置，共移动了 n-i 个元素，所以在等概率的情况下，在线性表中删除数据元素所需移动数据元素的期望值，即平均移动数据元素的次数为：,由此可以看出，在线性表上删除数据元素时大约需要移动表中一半的元素，显然该算法的时间复杂度为(n)。,通常情况下，我们认为在线性表中任何位置删除元素是等概率的，即pi =
