《《数据结构——C语言描述（第二版）》-王路群-电子教案 第二章 线性表》由会员分享，可在线阅读，更多相关《《数据结构——C语言描述（第二版）》-王路群-电子教案 第二章 线性表（50页珍藏版）》请在金锄头文库上搜索。
1、教学要求 1了解：线性表的定义和基本运算。 2掌握：线性表的两种存储结构：顺序存储结构和链式存储结构的描述方式，以及这两种存储结构上的基本运算的实现算法。 3了解：线性表处理一元多项式的操作方法及其算法的实现。 4掌握：线性表的两种存储结构的特点及其具体实现。,第二章 线性表,主要内容,2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 一元多项式的表示及相加 2.5实训,2.1 线性表的逻辑结构,线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。例如：英文字母表（A，B，C，Z）是一个长度为26的线性表
2、，其中的每一个字母就是一个数据元素；再如，某公司2000年每月产值表（400，420，500，600，650）(单位：万元)是一个长度为12的线性表，其中的每一个数值就是一个数据元素。上述两例中的每一个数据元素都是不可分割的，在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record），例如，图2-1的某单位职工工资表就是一个线性表，表中每一个职工的工资就是一个记录，每个记录包含八个数据项：职工号、姓名、基本工资。,图2-1 职工工资表,矩阵也是一个线性表，但它是一个比较复杂的线性表。在矩阵中，我们可以把每行看成是一个数据元素，也可以把每列
3、看成是一个数据元素，而其中的每一个数据元素又是一个线性表。 综上所述，一个线性表是n0个数据元素a0，a1，a2，an-1的有限序列。如果n0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素，ai（0in-1）为线性表的第i个数据元素，它在数据元素ai-1之后，在ai+1之前。a0为线性表的第一个数据元素，而an-1是线性表的最后一个数据元素；若n=0，则为一个空表，表示无数据元素。因此，线性表或者是一个空表（n=0），或者可以写成：（a0，a1，a2， ai-1，ai，ai+1，an-1）。 抽象数据类型线性表的定义如下： LinearList=(D,R) 其中，D= ai
4、| aiElemSet,i=0,1,2, ，n-1 n1 R=| ai-1，aiD, i=0,1,2, ，n-1 Elemset为某一数据对象集；n为线性表的长度。,线性表的主要操作有如下几种： 1 Initiate(L) 初始化：构造一个空的线性表L。 2 Insert(L,i,x) 插入：在给定的线性表L中，在第i个元素之前插入数据元素x。线性表L长度加1。 3 Delete(L,i) 删除：在给定的线性表L中，删除第i个元素。线性表L的长度减1。 4 Locate(L,x) 查找定位：对给定的值x，若线性表L中存在一个元素ai与之相等，则返回该元素在线性表中的位置的序号i，否则返回Nul
5、l（空）。 5 Length(L) 求长度：对给定的线性表L，返回线性表L的数据元素的个数。 6 Get(L,i) 存取：对给定的线性表L，返回第i（0iLength(L)-1）个数据元素，否则返回Null。 7 Traverse(L) 遍历：对给定的线性表L，依次输出L的每一个数据元素。 8 Copy(L,C) 复制：将给定的线性表L复制到线性表C中。 9 Merge(A,B,C) 合并：将给定的线性表A和B合并为线性表C。 上面我们定义了线性表的逻辑结构和基本操作。在计算机内，线性表有两种基本的存储结构：顺序存储结构和链式存储结构。下面我们分别讨论这两种存储结构以及对应存储结构下实现各操作
6、的算法。,2.2 线性表的顺序存储结构,在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。,2.2.1 线性表的顺序存储结构,在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间大小相同，因此，要在该线性表中查找某一个元素是很方便的。假设线性表中的第一个数据元素的存储地址为Loc(a0)，每一个数据元素占d字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为： Loc(ai)= Loc(a0)+id,在程序设计语言中，通常利用数
7、组来表示线性表的顺序存储结构。这是因为数组具有如下特点：（1）数据中的元素间的地址是连续的；（2）数组中所有元素的数据类型是相同的。而这与线性表的顺序存储空间结构是类似的。,1一维数组,若定义数组An= a0，a1，a2，an-1，假设每一个数组元素占用d个字节，则数组元素A0，A1，A2，An-1的地址分别为Loc(A0)，Loc(A0)+d，Loc(A0)+2d，Loc(A0)+（n-1）d 。其结构如图2-2所示。,若定义数组Anm，表示此数组有n行m列，如下图2-3所示。,图2-3 二维数组,二维数组,在C语言中，二维数组的保存是按照行方式存储的，先将第一行元素排好，接着排第二行元素，
8、直至所有行的元素排完。如图2-4所示。,2.2.2 线性表在顺序存储结构下的运算,可用C语言描述顺序存储结构下的线性表（顺序表）如下： #define TRUE 1 #define FALSE 0 #define MAXNUM Elemtype ListMAXNUM ; /*定义顺序表List*/ int num=-1; /*定义当前数据元素下标，并初始化*/ 我们还可将数组和表长封装在一个结构体中： struct Linear_list Elemtype ListMAXNUM; /*定义数组域*/ int length; /*定义表长域*/ ,1. 顺序表的插入操作,序号 元素,序号 元素,
9、在长度为num(0numMAXNUM-2)的顺序表List的第i(0inum+1)个数据元素之前插入一个新的数据元素x时，需将最后一个即第num个至第i个元素（共num-i+1个元素）依次向后移动一个位置，空出第i个位置，然后把x插入到第i个存储位置，插入结束后顺序表的长度增加1，返回TRUE值；若i0或inum+1，则无法插入，返回FALSE。如图2-5所示。 在长度为num(0numMAXNUM-2)的顺序表List的第i(0inum+1)个数据元素之前插入一个新的数据元素x时，需将最后一个即第num个至第i个元素（共num-i+1个元素）依次向后移动一个位置，空出第i个位置，然后把x插入
10、到第i个存储位置，插入结束后顺序表的长度增加1，返回TRUE值；若i0或inum+1，则无法插入，返回FALSE。如图2-5所示。,序号 元素,序号 元素,插入x,图2-5 在数组中插入元素,其算法如下： 【算法2.1 顺序表的插入】 int Insert(Elemtype List,int *num,int i,Elemtype x) /*在顺序表List中，*num为表尾元素下标位置，在第i个元素前插入数据元素x，若成功，返回TRUE，否则返回FALSE。*/ int j; if (i*num+1) printf(“Error!”); /*插入位置出错*/ return FALSE; if
11、 (*num=MAXNUM-1) printf(“overflow!”); return FALSE; /*表已满*/ for (j=*num;j=i;j-) Listj+1=Listj; /*数据元素后移*/ Listi=x; /*插入x*/ (*num)+; /*长度加1*/ return TRUE; 注：顺序表List的最大数据元素个数为MAXNUM，num标识为顺序表的当前表尾（numMAXNUM-1）。,顺序表的删除操作,序号 元素,图2-6 在数组中删除元素,在长度为num(0numMAXNUM-1)的顺序表List，删除第i(0inum)个数据元素，需将第i至第num个数据元素的
12、存储位置（num-i+1）依次前移，并使顺序表的长度减1，返回TRUE值，若i0或inum，则无法删除，返回FALSE值，如图2-6所示。,其算法如下： 【算法2.2 顺序表的删除】 int Delete(Elemtype List,int *num,int i) /*在线性表List中，*num为表尾元素下标位置，删除第i个元素，线性表的元素减1，若成功，则返回TRUE；否则返回FALSE。*/ int j; if(i*num) printf(“Error!”); return FALSE; /*删除位置出错！*/ for(j=i+1;j=*num;j+) Listj-1=Listj; /*
13、数据元素前移*/ (*num)-; /*长度减1*/ return TRUE; 从上述两个算法来看，很显然，在线性表的顺序存储结构中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。而移动元素的次数取决于插入或删除元素的位置。 假设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的平均次数为,假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的平均次数为 如果在线性表的任何位置插入或删除元素的概率相等，即 则 可见，在顺序存储结构的线性表中插入或删除一个元素时，平均要移动表中大约一半的数据元素。若表长为n，
14、则插入和删除算法的时间复杂度都为O(n)。 在顺序存储结构的线性表中其他的操作也可直接实现，在此不再讲述。,例：将有序线性表La=2,4,6,7,9，Lb=1,5,7,8，合并为Lc=1,2,4,5,6,7,7,8,9。,分析：Lc中的数据元素或者是La中的数据元素，或者是Lb中的数据元素，则只要先将Lc置为空表，然后将La或Lb中的元素逐个插入到Lc中即可。设两个指针i和j分别指向La和Lb中的某个元素，若设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到Lc中的元素c为c= 当时 当时 ，很显然，指针i和j的初值均为1，在所指元素插入Lc后，i，j在La或Lb中顺序后移。,算法如
15、下： void merge(Elemtype La,Elemtype Lb,Elemtype *Lc) int i,j,k; int La_length,Lb_length; i=j=0;k=0; La_length=Length(La);Lb_length(Lb)=Length(Lb); /*取表La,Lb的长度*/ Initiate(Lc); /*初始化表Lc*/ While (i=La_length ,3顺序表存储结构的特点 线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。也就是说定位操作可以直接实现。高级程序设计语言提供的数组数据类型可以直接定义顺序存储结构的线性表，使其程序设计十分方便。 但是，顺序存储结构也有一些不方便之处，主要表现在： （1）数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间。 （2）插入与删除运算的效率很低。为了保持线性表中的数据元素的顺序，在插入操作和删除操作时需移动大量数据。这对于插入和删除操作频繁的线性表、以及每个数据元素所占字节较大的问题将导致系统的运行速度难以提高。 （3）顺序存储结构的线性表的存储空间不便于扩充。当一个线性表分配顺序存
