《《数据结构（C++版）（第二版）》-李根强-电子教案 第02章》由会员分享，可在线阅读，更多相关《《数据结构（C++版）（第二版）》-李根强-电子教案 第02章（54页珍藏版）》请在金锄头文库上搜索。
1、1,第2章 线性表,本章学习内容,2.6 算法应用举例,2.5 顺序表与链表的比较,2.4 一元多项式的表示及相加,2.3 线性表的链式存储结构,2.2 线性表的顺序存储结构,2.1 线性表的定义及其运算,2,2.1 线性表的定义及其运算,2.1.1 线性表的定义,在实际应用中，线性表是最常用而且是最简单的一种数据结构。例如，一副扑克牌的点数是一个线性表，可表示为（2,3,4,5,6,7,8,9,1 0,J,Q,K,A），一些城市的名字是一个线性表，可表示为（Changsha,Beijing,Shanghai,Guangzhou,Wuhan）。,1线性表的定义,线性表（linear list）
2、是n（n0）个数据元素a1，a2，an组成的有限序列。其中n 称为数据元素的个数或线性表的长度，当n=0时称为空表，当n0时称为非空表。通常将非空的线性表记为（a1，a2，an），其中的数据元素ai（1in）是一个抽象的符号，其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。,3,2线性表的特征,从线性表的定义可以看出线性表的特征：,（1）有且仅有一个开始结点（表头结点）a1，它没有直接前驱，只有一个直接后继；,（2）有且仅有一个终端结点（表尾结点）an，它没有直接后继，只有一个直接前驱；,（3）其他
3、结点都有一个直接前驱和直接后继；,（ 4）元素之间为一对一的线性关系。,因此，线性表是一种典型的线性结构，用二元组表示为： linear_list=(A,R) 其中 A=ai 1in,n0,aielemtype R=r r= 1in-1,对应的逻辑结构图如下所示。,4,2.1.2 线性表的运算,给出了线性表的逻辑结构后，就可以直接定义它的一些基本运算，但这些运算要实现，还必须依赖于具体的存储结构。,常见线性表的运算有：,（1）置空表 setnull(&L)：将线性表L置成空表。,（2）求长度 Length(L)：求给定线性表L的长度。,（3）取元素 Get（L,i）：若1ilength(L)，
4、则取第i个位置上的元素，否则取得的元素为NULL。,（4）求直接前驱 Prior(L,x)：求线性表L中元素值为x的直接前驱，若x为第一个元素，前驱为NULL。,（5）求直接后继 Next（L,x）：求线性表L中元素值为x的直接后继，若x为最后一个元素，后继为NULL。,（6）定位函数 Locate(L,x)：在线性表L中查找值为x的元素位置，若有多个值为x，则以第一个为准，若没有，位置为0。,（7）插入 Insert(&L,x,i)：在线性表L中第i个位置上插入值为x的元素。,（8）删除 Dele（&L,i）：删除线性表L中第i个位置上的元素。,5,2.1.3 线性表的抽象数据类型描述,上述
5、这些操作可用抽象数据类型描述为：,ADT Linearlist is Data: 一个线性表L定义为L=(a1,a2,an)，当L=()时定义为一个空表。 Operation: void setnull(&L) /将线性表L置成空表 int Length(L) /求给定线性表L的长度 elemtype Get(L,i) /取线性表L第i个位置上的元素 elemtype Prior(L,x) /求线性表L中元素值为x的直接前驱 elemtype Next(L,x) /求线性表L中元素值为x的直接后继 int Locate(L,x) /在线性表L中查找值为x的元素位置 void Insert(&L
6、,x,i) /在线性表L中第i个位置上插入值为x的元素 void Dele(&L,i) /删除线性表L中第i个位置上的元素 END Linearlist,6,【例2-1】假设线性表L=(23,56,89,76,18)，i=3，x=56，y=88，则对L的一组操作及结果如下：,Length(L) /所得结果为5 Get(L,i) /所得结果为89 Prior(L,x) /所得结果为23 Next(L,x) /所得结果为89 Locate(L,x) /所得结果为2 Insert(&L,y,i) /所得结果为(23,56,88,89,76,18) Dele(&L,i+1) /所得结果为(23,56,
7、88,76,18),7,2.2 线性表的顺序存储结构,2.2.1 顺序表结构,线性表的顺序存储结构，也称为顺序表。其存储方式为：在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度，然后让线性表中第一个元素存放在连续存储空间的第一个位置，第二个元素紧跟在第一个之后，其余依此类推。,显然，利用顺序表来存储线性表，表中相邻的元素存储在计算机内的位置也相邻，故可以借助数据元素在计算机内的物理位置相邻来表示线性表中数据元素之间线性逻辑关系。,假设线性表中元素为(a1,a2,.,an)，设第一个元素a1的内存地址为LOC(a1)，而每个元素在计算机内占d个存储单元，则第i个元素a
8、i的地址为LOC(ai)=LOC(a1)+(i-1)d （其中1in）。,8,从上面的公式可知，该存储结构类似于高级语言中的一维数组存储结构（即向量结构），适合于随机访问，于是可用C+语言描述为：,const int maxsize=Maxlen；/Maxlen表示线性表允许的最大长度,class sequenlist public: elemtype amaxsize; /表示线性表(a1,a2,an,aMaxlen), elemtype表示某种具体数据类型 int len; /len表示线性表的实际长度 int length(sequenlist L ); /求顺序表L的长度 void I
9、nsert(sequenlist ,9,在上述描述中，a为一个数组类型，第一个元素为a0而非a1，因为C+中数组的下标是从0开始而非1开始。存储空间从a0amaxsize-1，而不是从a1amaxsize，不能使用amaxsize。为了与我们的a1对应，建议从a1开始使用元素，将a0存储单元浪费掉，这样给我们的操作带来较大方便（以后使用不再声明），当然，一般情形下，不应该浪费a0存储单元，这可根据具体情形来定。,2.2.2 顺序表运算,实现顺序表上的基本运算，我们都将以函数的形式描述。 下面仅讨论插入、删除、求长度、置空表、定位算法、取元素等，其他算法读者自己可类似分析。,1求顺序表的长度le
10、ngth(L) 算法的语句如下： int sequenlist : length(sequenlist L ) return L.len; 该算法的语句频度为1，时间复杂度为O(1)。,10,2插入运算Insert(&L,x,i) 要将x插入到顺序表L的第i个位置，可分三种情形考虑： （1）i位置超过表长，发生溢出，不能插入； （2）i值非法，不能插入； （3）i值合法，进行插入。,算法描述为：,void sequenlist :Insert(sequenlist /表长度增加1 ,11,分析该算法的执行效率：,该算法花费的时间，主要在于循环中元素的后移（其他语句花费的时间可以忽略），即从插入
11、位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值x。但是，插入的位置是不固定的，当插入位置i=1时，全部元素都得移动，需n次移动，当i=n+1时，不需移动元素，故在i位置插入时移动次数为n-i+1。假设在每个位置插入的概率相等，为 ，则平均移动元素的次数为 ，故时间复杂度为O(n)。,从上面的分析可知，顺序表上的插入算法平均要移动一半元素，故当n较大时，算法的效率相当低。,3删除运算Dele(&L,i),删除算法描述为：,void sequenlist :Dele(sequenlist /表长度减1 ,12,该算法的运行时间主要花费在元素前移上，和刚才的插入算法类似，平均移动次数为
12、 ，故时间复杂度为(n)。顺序表上的删除运算平均移动元素次数也将近为表长的一半，当n较大时，算法的效率相当低。,从顺序表插入、删除运算可知，当n较大时，算法效率都相当低。若有大量运算为插入、删除运算，则不宜选用顺序表，必须选用另外的存储结构。,从顺序表插入、删除运算可知，当n较大时，算法效率都相当低。若有大量运算为插入、删除运算，则不宜选用顺序表，必须选用另外的存储结构。,4置空表setnull( &L ),算法如下：,void sequenlist :setnull(sequenlist ,该算法的时间复杂度为O(1)。,13,5定位算法Locate(L,x),算法如下：,int seque
13、nlist:Locate(sequenlist L , elemtype x) int j=0; while(jL.len) ,该算法的时间复杂度为O(n)。,6取元素Get(L,i),算法如下：,elemtype sequenlist :Get(sequenlist L,int i) if(i=L.len) return NULL; else return L.ai; ,该算法的时间复杂度为O(1)。,14,2.2.3 顺序表存储空间的动态分配,上面介绍的线性表顺序存储，是预先给定大小为maxsize的存储空间，程序在编译阶段就会知道该类型变量的大小，在程序开始运行前，就会为它分配好存储空间
14、，故是一种存储空间的静态分配。而动态分配是在定义线性表的存储类型时，不是定义好一个数组空间，而是只定义一个指针，待程序运行后再申请一个用于存储线性表的空间，并把该空间的首地址赋给这个指针。访问动态存储分配的线性表中的元素和访问静态存储分配的线性表中的元素的情况完全相同，既可以采用指针方式，也可以采用数组下标方式。,若将前面线性表的顺序存储结构类型中的数组形式改为指针形式，则得到动态分配形式如下：,class sequenlist public: elemtype *a; int len; ;,15,在此时，只有线性表置空表算法需要修改，其他算法都与静态分配相同。,这时的置空表算法应改为：,vo
15、id sequenlist :setnull(sequenlist ,16,2.3 线性表的链式存储结构,线性表的链式存储结构，也称为链表。其存储方式是：在内存中利用存储单元（可以不连续）来存放元素值及它在内存中的地址，各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到计算机内存中后不一定相邻，从一个元素找下一个元素必须通过地址（指针）才能实现，故不能像顺序表一样可随机访问，而只能按顺序访问。常用的链表有单链表、循环链表和双向链表、多重链表等。,2.3.1 单链表结构,在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。 线性链表中的结点结构可描述为 。 其中data域用来存放结点本身的信息，类型由具体问题而定，本书中，我们也将其设定为elemtype类型，表示某一种具体的已知类型，next域用来存放下一个元素地址。,17,【例2-2】设有一个线性表(a1,a2,a3,a4,a5,a6)，在内存中的存放形式见下图。首先用头指针存放第一个元素的地址，然后每个结点的指针域存放下一个元素地址，最后一个结点的指针域为空，表示没有后继元素，设为NULL或。,我们用上图来描述单链表，是内存中的存放形式，但看起来不太直观，如果我们用下图来描述单链
