数据结构第二章 线性表-跟完全对应

　1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。

　2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。

　3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

　4. 结合线性表类型的定义增强对抽象数据类型的理解。

【重点和难点】

　　链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。

【知识点】

　　线性表、顺序表、链表、有序表

【学习指南】

　　正如课程概况中所提，学习数据结构的目标是为了编出质量更高的程序，因此重在"实践"。本章讨论的线性表是学习的第一种也是最简单的一种数据结构，是整个课程的基础，特别是熟练掌握链表的操作对以后各章的学习将有很大帮助。本章要求必须完成的算法设计题为：2.11，2.21，2.19，2.22，2.24，2.27，2.28，2.38。其中 2.11 和 2.19 可以在学完顺序表之后练习，其余都建议在学完全章的内容之后进行。

【课前思考】

1. 抽象数据类型的定义由哪几部分组成？

2. 按数据元素之间的逻辑关系不同，数据结构有哪几类？

3. 你能举出几个你熟悉的"序列"的例子来吗？

课时安排：

第一课时：线性结构、线性表的逻辑结构、线性表的抽象数据类型定义

第二课时：线性表的顺序存储结构

结构的表示：定义、元素地址计算方法、特点、实现

            基本操作：

插入：定义和分析、算法、算法图示、算法时间复杂度分析

删除：定义和分析、算法、算法图示、算法时间复杂度分析

第三四课时：顺序存储结构的优缺点

线性表的链式存储结构

单链表

      定义、c语言实现、指针、头结点、

基本操作

    查找：定义、算法描述、算法评价

    插入：定义、算法描述、算法评价

    删除：定义、算法描述、算法评价

    例子：动态建立单链表：算法描述、算法评价

                单链表的特点

第五六课时：链式存储结构的优缺点

        循环链表

双向链表

双向循环链表

从第二章开始，我们将开始讨论第一章里面提到的四种数据结构。这一章我们讨论一种最简单的线性结构—线性表。

线性结构

什么是线性结构？线性结构数据元素之间存在什么样的关系，简单地说，线性结构是一个数据元素的有序（次序）集合。

这里的 "有序" 仅指在数据元素之间存在一个 "领先" 或 "落后" 的次序关系，而非指数据元素 "值" 的大小可比性。

它有四个基本特征：

　1．集合中必存在唯一的一个"第一元素"；

2．集合中必存在唯一的一个"最后元素"；

3．除最后元素之外，其它数据元素均有唯一的"后继"；

4．除第一元素之外，其它数据元素均有唯一的"前驱"。

线性表的逻辑结构

线性表的类型定义

线性表是一种最简单的线性结构。

通常可以下列" n 个数据元素的序列"表示线性表 (Linear_List)

通常可以这样表示

　线性表中的数据元素可以是各种各样的，只要是属于同一个集合即可。

　　例如，26个小写英文字母是一个线性表

　　　　　(a,b,…,z)

同一花色的13张扑克牌

　　(2,3,4,5,6,7,8,9,10,J,Q,K,A)

可以构成一个线性表。

　例   英文字母表（A,B,C,…..Z)是一个线性表

特征：

1．序列中数据元素的个数 n 为线性表的一个属性，定义为线性表的表长；n=0 时的线性表被称为空表。

2.由于线性表是一个序列，所以每一个元素在线性表中都有一个固定的位置，称为线性表中第i个元素，称 i 为在线性表中的位序。

3.1ai的直接前驱是ai-1，a1无直接前驱

ai的直接后继是ai+1，an无直接后继

4.元素同构，是属于同一个对象的，也就是具有相同的特性，且不能出现缺项

线性表的抽象数据类型定义

其抽象数据类型的定义如下：（ppt上没有，但书上有，可以讲）

ADT List {

数据对象：D＝{ai |ai ∈ ElemSet, i=1,2,...,n, n≥0 }          线性表由n个元素构成，其中n≥0。

数据关系：R1＝{ | ,∈D, i=2,...,n }           其中数据元素之间的关系表现为n个有序对。

基本操作：                                线性表的操作有多种类型，总的来说可以归纳为四类。　　{结构初始化}

InitList( &L )

　　 操作结果：构造一个空的线性表 L 。

任何数据结构在被使用之前都必须进行"初始化" ，它类似于编程中使用的变量都必须先有定义。

{销毁结构}

DestroyList( &L )

　　 初始条件：线性表 L 已存在。

操作结果：销毁线性表 L 。

任何数据结构不再使用时都必须进行"结构销毁" ，其实质为"释放"它所占有的存储空间。

{引用型操作}

　　ListEmpty( L )        判定线性表是否为空表。

初始条件：线性表L已存在。

　　　操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。

ListLength( L )         求得线性表的长度，即线性表中所含数据元素的个数。

　　初始条件：线性表 L 已存在。

　　　操作结果：返回 L 中元素个数。

PriorElem( L, cur_e, &pre_e ) 求线性表中某个元素的前驱。若该元素cur_e是线性表 L 中第一个数据元素，则它的前驱 pre_e 为"空元素"。

　　初始条件：线性表 L 已存在。

　　　操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，

　　　　　　　　否则操作失败，pre_e 无定义。

NextElem( L, cur_e, &next_e ) 求线性表中某个元素的后继。若该元素 cur_e 是线性表 L 中最后一个数据元素，则它的后继 next_e 为"空元素"。

　初始条件：线性表 L 已存在。

　　　操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，

　　　　　　　　否则操作失败，next_e 无定义。

GetElem( L, i, &e ) 求线性表中第i个元素

　　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)。

　　　操作结果：用 e 返回 L 中第 i 个元素的值。

　此操作的结果是求得线性表 L 中和位序 i 相对应的数据元素，因此，只有当 i 的值在线性表的长度范围内才有意义。

LocateElem( L, e, compare( ) )

　　　初始条件：线性表 L 已存在，compare( ) 是元素判定函数。

　　　操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。

　　　　　　　　若这样的元素不存在，则返回值为0。

这是和上一个操作"相对"的操作，通常称为"定位函数"，定位到满足某个判定条件的元素，这是一种广义的定位函数写法，以 compare() 作为判定的条件，参数 e 和线性表中数据元素具有相同类型。较多场合是以"相等"作为判定条件，此时可省略函数参数，且操作结果为：

若线性表中存在多个满足条件的数据元素，则返回第一个这样的元素在表中的位序，

若线性表中不存在满足条件的数据元素，则返回函数值为0。

ListTraverse(L, visit( )) 对线性表进行遍历

　初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。

　　操作结果：依次对 L 的每个元素调用函数 visit( )。

　　　　　　　一旦 visit( ) 失败，则操作失败。

visit() 亦为函数参数，常见的情况是"依次输出表中元素的值"，同样在这种情况下，通常的写法也是省略函数参数。

这些操作有个共同特性，线性表不会发生任何改变，无论是数据元素还是元素之间的关系都没有发生改变，所以把这些操作叫做引用型的操作

{加工型操作}

以下四个操作的结果或修改表中的数据元素，或修改元素之间的关系，被称为"加工型"的操作，

　　ClearList( &L )

　　　初始条件：线性表 L 已存在。

　　　操作结果：将 L 重置为空表。

值得注意的是，在进行了 DestroyList(L) 操作之后，线性表 L 不再存在，即不能在以后的程序中再引用它，而在对线性表L进行 ClearList(L) 操作之后，仅是删除表中所有元素，在以后的程序中仍可对它进行某些"合法"操作，如判空、插入等

PutElem( &L, i, &e )

　　　初始条件：线性表L已存在，1≤i≤LengthList(L)。

　　　操作结果：L 中第 i 个元素赋值同 e 的值

　和GetElem操作相同，i 的值必须在线性表的长度范围内。

ListInsert( &L, i, e )

　　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。

　　　操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。

　可在线性表中任意一个元素之前插入一个新的数据元素，i=1 意为在第一个元素之前插入一个新的数据元素，i=LengthList(L)+1 则为在最后一个元素之后插入一个新的数据元素。换句话说，操作结果是使新插入的数据元素成为插入之后的线性表中第 i 个数据元素，显然，插入位置 i 的合法值应为

　　　1≤i≤LengthList(L)+1。

ListDelete( &L, i, &e )

　　　初始条件：线性表 L 已存在且非空，1≤i≤LengthList(L)。

　　　操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。

被删除的元素必须是当前线性表中存在的元素，因此被删元素的位序应满足条件1≤i≤LengthList(L)。

线性表的顺序存储结构

2.2线性表的顺序存储结构-顺序表

若要在实际的程序设计中真正引用线性表的基本操作，首先必须实现线性表类型。即在计算机中确定它的存储结构并在此存储结构上实现类型中定义的所有基本操作。

本节将讨论它的顺序存储结构以及在顺序存储结构中基本操作的实现。    

2.2.1线性表顺序存储的表示

何谓顺序存储表示？顺序存储是指以数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

⏹定义：对线性表来说，它指的是，"用一组地址连续的存储单元依次存放线性表中的数据元素"，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。如下图所示。

⏹元素地址计算方法：

LOC(ai)=LOC(a1)+(i-1)*L

LOC(ai+1)=LOC(ai)+L

其中：

■L—一个元素占用的存储单元个数

■LOC(ai)—线性表第i个元素的地址

⏹特点：

实现逻辑上相邻—物理地址相邻

实现随机存取

⏹实现：在高级语言程序设计中，由于数组也是采用连续的地址单元来存放数据元素，所以可用一维数组实现顺序表。具体图示和c语言的编程实现见ppt。

2.2.2 顺序表中基本操作的实现

　　从顺序表的存储结构定义容易看出，由于顺序表的"长度"是个"显值"，且由于第i个元素恰好存储在数组的第 i 个分量(数组下标为 i-1)中，因此其"求长"、"判空"以及"存取第 i 个数据元素"等操作都很容易实现。下面重点讨论顺序表类型定义中五个操作的实现：初始化操作、元素定位操作、插入元素操作、删除元素操作、销毁结构操作。

插入元素操作（ppt上面有，需要详细讲的）

首(a1,a2,∧, ∧,ai-1,ai, ∧, ∧,an)改变为 （a1，a2, ∧, ∧,ai-1,x,ai, ∧, ∧,an）

先分析，"插入元素"使线性表的逻辑结构发生什么变化？

　　假设在线性表的第i个元素之前插入一个元素e，使得线性表

　即：

　　(1) 改变了表中元素之间的关系，使< ai-1,ai > 改变为和< x,ai >

　(2) 表长增1

　　由于顺序表是以"存储位置相邻" 表示"元素之间的前驱和后继关系"，则必须"移动元素"来体现"元素之间发生的变化"。需将第i至第n共（n-i+1)个元素后移.

见ppt算法ch2_1.txt

算法时间复杂度的分析：

　　算法中的基本操作是"移动元素"，for 循环的执行次数在最坏的情况下pos=1（即插入在第一个元素之前时)为 移动元素的次数为n。最好的情况是pos=n+1(即插入到线性表的最末端)，无需移动元素。两者的概率一样，平均次数为n/2，可见n越大，效率越低。

　删除元素操作（ppt上面有，需要详细讲的）

首(a1,a2,∧, ∧,ai-1,ai, ∧, ∧,an)改变为 （a1，a2, ∧, ∧,ai-1,ai+1, ∧, ∧,an）

同样首先分析，"删除元素"使线性表的逻辑结构发生什么变化？

　　假设删除线性表中第i个元素，使得线性表

即：

1)改变了表中元素之间的关系

(2) 表长减1

　　对顺序表而言，需要改变从第 i+1 个元素起到第 n 个元素的存储位置，即进行"从第 i+1 到第 n 个元素往前移动一个位置"。

见ppt算法ch2_2.txt

此算法的时间复杂度为：O (ListLength(L))

算法时间复杂度的分析：

　　算法中的基本操作是"移动元素"，for循环的执行次数在最坏的情况下(pos=1即删除第一个元素时)移动n-1次，最好的情况(pos=n)下移动0次，概率一样，平均移动次数为(n-1)/2。可见n越大，效率越低。

第5个学时：

⏹回顾 前面所学习的内容；

⏹然后从数据结构的角度去分析，做几个练习。同时加上演示效果。

⏹完成一个对整体线性表的演示。

第6个学时：

顺序存储结构的优缺点

线性表的链式存储结构

　　前面已经提到，由于在顺序表中插入或删除一个数据元素，平均约需移动表中一半元素。因此，对于需要经常进行插入和删除操作、表中元素相对不稳定的线性表，不应该采用顺序存储表示，而应该采用链式存储表示。

何谓"链式存储表示"？

线性表的链式存储结构的表示：链式存储表示指的是以"附加信息(指针)" 表示数据元素之间的逻辑关系。

特点：

⏹用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的）)

⏹每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息。

⏹利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素。

为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。

因为线性表的最后一个数据元素没有后继，因此最后一个结点中的"指针"是一个特殊的值 "NULL" （在图上用∧表示），通常称它为"空指针"。

⏹结点    

数据域：元素本身信息（设域名为data）

指针域：指示直接后继的存储位置（设域名为next）。称做指针或链。

单链表（线性链表）

由分别表示a1，a2。。an的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表，如下图所示：

为了便于处理一些特殊情况，在第一个结点之前附加一个"头结点"，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点，该头节点中的数据域没有意义，如下图所示。

通常称这类单链表为"带头结点的单链表"。

值得注意的是，若线性表为空，在不带头结点的情况下，头指针为空(NULL)，但在带头结点的情况下，链表的头指针不为空，而是其头结点中指针域的指针为空，如下图所示。

单链表（线性链表）的实现：

    在高级程序设计中是怎样描述或表示线性链表的。

    在c语言中就是用结构指针来描述链表结构的。

            typedef struct node {

     datatype data;

     struct node  *link;

}JD;

    JD   *h,*p;

(*p)表示p所指向的结点。若 p 的值非空，则表明 p 指向某个结点

(*p).datap->data表示p指向结点的数据域

(*p).linkp->link表示p指向结点的指针域。若非空，则表明其有"后继"结点。

　    指针型变量只能作同类型的指针赋值与比较操作。

并且，指针型变量的"值"除了由同类型的指针变量赋值得到外，都必须用 C 语言中的动态分配函数得到。例如，p = new LNode; 表示在运行时刻系统动态生成了一个 LNode 类型的结点，并令指针 p "指向"该结点。

反之，当指针 p 所指结点不再使用，可用 delete p; 释放此结点空间。注意：一旦执行了delete p; 的语句，(*p)不再存在，自然 p->data 和 p->link 也就没有意义了。

第7、8个学时：

单链表（线性链表）的基本运算：

查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL

算法描述：见ch2_3.txt

算法评价：

    While循环中语句频度为：若找到结点X，为结点X在表中的序号

                        否则，为n

    T(n)=O(n)

    插入：

插入效果示例见ppt

算法见pptch2_4.txt

算法时间复杂度的分析：

　　在插入算法中，修改指针的时间复杂度仅为O(1)

    删除:

        见ppt

例：动态建立单链表算法：

见ppt

　由于链表是一种动态存储管理的结构，链表中每个结点占用的存储空间不需预先分配划定，而是在运行时刻由系统应需求即时生成，因此，建立链表的过程是一个动态生成的过程。即从 "空表"起，依次建立结点，并逐个插入链表。

单链表的特点

⏹它是一种动态结构，整个存储空间为多个链表共用

⏹不需预先分配空间

⏹指针占用额外存储空间

⏹不能随机存取，查找速度慢

第9、10个学时：

链式存储结构的优缺点

从对链表的各种操作的讨论可知，链式存储结构的优势在于：

优势：

(1) 能有效利用存储空间；因为它是动态存储分配的结构，不需要预先为线性表分配足够大的空间，而是向系统"随用随取"，并且在删除元素时可同时释放空间。

(2) 用"指针"指示数据元素之间的后继关系，便于进行"插入"、"删除"等操作；插入或删除时只需要修改指针，而不需要进行大量元素的移动。

劣势：

而其劣势则是不能随机存取数据元素。同时，它还丢失了一些顺序表有的长处，如线性表的"表长"和数据元素在线性表中的"位序"，在上述的单链表中都看不见了。又如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。　当插入位置在表尾时不需要移动元素，所需时间是个常量，由于链表进行插入操作只需要修改指针本是个优点，然而为了查找插入位置却要遍历整个表，所需时间反而多。

为了更突出链表的优势，需改进单链表结构的定义。除了保留指向头结点的指针外，还应增设"尾指针"和"表长"两个属性，同时，我们从上面讨论的链表基本操作的实现算法中可以看出，在对链表进行操作时，经常需要一个指针在链表中巡游，由此可以设想，如果将这个在操作中进行巡游的"指针"以及它所指结点的数据元素在线性表中的"位序"纳入链表结构中，作为链表定义中的两个成员，必然会对链表的操作带来很多方便。

循环链表

　　循环链表(Circular Linked List)是线性表的另一种形式的链式存储表示。

它的特点是表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且将头指针设成指向最后一个结点。空的循环链表由只含一个自成循环的头结点表示。

    头指针指向表尾的好处是既能立即找到链表的尾结点，也容易找到链表中的第一个结点。

    循环链表的操作和单链表基本一致，差别仅在于，判别链表中最后一个结点的条件不再是"后继是否为空"，而是"后继是否为头结点"

双向链表

单链表具有单向性的缺点

单链表具有单向性的缺点

　　顾名思义，双向链表(Double Linked List)的特点是其结点结构中含有两个指针域，其一指向数据元素的"直接后继"，另一指向数据元素的"直接前驱"，用 C 语言描述如下：。

typedef struct node {

     datatype element;

     struct node *prior,*next;

}JD;

很明显，在双向链表中不仅能直接找到结点的前驱，也能即刻找到结点的后继。

假设指针p指向双向链表中某个结点，则

　　p->prior->next = p

　　p->next->prior = p

与单链表类似，双向链表也是由指向头结点的头指针唯一确定，若将头尾结点链接起来则构成双向循环链表。空的双向循环链表则由只含一个自成双环的头结点表示

。

非空双向循环链表

详见PPT

在双向链表上进行操作基本上和单向链表相同，但可以在两个方向上操作，例如，查找结点也是要从头指针指示的头结点开始，但插入和删除时必须同时修改两个方向上的指针，它们的算法分别如下所示。

删除：

    见ppt

插入：

    见ppt