第二章线性表
2.1线性表概念及基本操作2.2线性表的顺序存储和实现2.3线性表的链式存储和实现
2.3.1线性链表
2.3.2循环链表
2.3.3双向链表
2.4一元多项式的表示及相加
第二章线性表
在本课程介绍的几种数据结构中，线性表是最常简单的，也是最常用的数据结构，线性表在实际应用大量使用，并不是一个陌生的概念。
基本内容:
1 线性表的概念；
2 线性表两类存储结构和它们的类型定义；
3 在这些存储结构下，线性表的基本操作的算法；
第二章线性表
学习要点：
1 了解线性表逻辑结构的特征;
2 重点掌握线性表的顺序存储结构和链式存储结构，它们如
何表达线性表中数据元素之间的结构关系；如何用C语言
描述它们的类型定义；
3 掌握在顺序存储结构下，线性表的基本操作的算法；
4 掌握在链式存储结构下，线性表的基本操作的算法；
5 能够从时间复杂度的角度，比较线性表两类存储结构
的不同特点及适用场合；
线性表是n 个类型相同数据元素的有限序列，
通常记作（a 1, a 2, a 3, …, a n ）。
姓名电话号码
蔡颖63214444陈红63217777刘建平63216666王小林63218888张力
63215555
...2. 1 线性表的概念
例1、数学中的数列（11，13，15，17，19，21）
例2、英文字母表（A, B, C, D, E Z ）。
例3、某单位的电话号码簿。一线性表的逻辑结构
电话号码簿是数据元素
的有限序列，每一数据
元素包括两个数据项，
一个是用户姓名，一个
是对应的电话号码。
2.1 线性表的概念
说明：
设A=（a 1, a 2, ... , a i -1, a i , a i+1, …, a n ）是一线性表
1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；
2）在表中a i-1领先于a i ，a i 领先于a i+1，称a i-1是a i 的直接前趋，a i+1是a i 的直接后继；
2.1 线性表的概念
3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；
4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；
5）a
i 是线性表的第i 个元素，称i 为数据元素a
i
的序号
，每一个元素在线性表中的位置，仅取决于它的序号；
2.1 线性表的概念
线性表的其他表示方式
二元组表示
L= < D,S >，其中D={ a 1,a 2,a 3,... a n }
S= {R} R={< a 1,a 2>,, < a 3,a 4> … < a n-1, a n > }
图示表示a i +1a 1a i-1a 2
a i a n
顶点：表示数据
边：表示是数据间的顺序结构关系
2.1 线性表的概念
设L=（a 1,a 2,...a i-1,a i ,a i+1,…, a n ）是一线性表1 初始化操作InitList(&L) 功能：建立空的线性表L ；2 销毁操作DetroyList(&L)功能：回收为线性表L 动态分配的存储空间；二线性表的基本操作
3 置空操作ClearList(&L)功能：L 中已存在，重新将其置成空表；
4 判空操作ListEmpty(L)
功能：判断线性表L 是否为空表，若为空表返回TRUE ，否则返
回FALSE ；
5 求表长操作ListLength(L)
功能：返回线性表L 的表长；
2.1 线性表的概念6 取元素操作：GetElem(L, i, &e)功能：将线性表L 中第i 个元素赋值给e ；7 查找操作LocateElem (L, e,compare() )功能：在线性表L 中查找与元素e 满足compare()的第1个元素，返回该元素在表中的序号（或位置），若表中不存在这样的元素，则返回0；8 插入操作ListInsert(&L, i, e )
功能：在线性表L 的第i 个元素之前插入一个新元素e;9 删除操作ListDelete(&L, i, &e )
功能：删除线性表L 的第i 个元素，并用e 返回；
10 遍历操作ListTraverse (&L,visit( ) )
功能：依次对线性表L 的每一个元素调用函数visit( )。若visit( )失败，则返回ERROR ，否则返回OK ；
2.1 线性表的概念
说明
1 上面列出的操作，只是线性表的一些常用的基本操作；
2 不同的应用，基本操作可能是不同的；
例如：上面列出的删除操作Delete( &L, i, &e ), 功
能是在线性表L 中删除第i 个元素，并用e 返回其值。在电话号码查询系统中，一旦某用户撤掉某部电话，则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与给定元素e 值相同的数据元素；
3线性表的复杂操作可通过基本操作实现；这有点类似于数中的情形，例如整数的基
本操作是+,-, ，/ 。如果要求某班同学的平均年龄则可利用+ / 实现，全班同学的平均年龄
=(age1+age2+age3+…)/全班同学的人数
关于如何用线性表的基本操作实现复杂操作将在后面讲解。
2.1 线性表的概念
现在我们已经知道什么是线性表及线性表的一些基
本操作，下一步要做的是什么？
例如，我们要在设计一个电话号码询系统，显然这个系统至少要具备下列功能：
·查询某人的电话号码；
·在电话号码薄中，插入一新用户姓名及电话号码；·在电话号码薄中，删除已撤销的用户姓名及电话号码；由上我们知道，电话号码薄可用线性表表示，上面列出的功能实际上就是对线性表的查找、插入、删除操作，为了在计算机上实现上述功能，我们应该做什么呢？显然，首先需要将电话号码薄上的信息存储到计算机中，然后才可能对这些信息进行加工处理，实现上述功能。
2.1 线性表的概念
强调
本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储数据结构？如何在计算机上实现对数据结构的各种操作，为此，我们将用计算机语言来描述数据的存储结构，用计算机语言来描述这些操作的算法，本课程我们用类C语言做为描述语言。
2.2 线性表的顺序存储和实现
如何在计算机中存储线性表？
如何在计算机中实现线性表的
基本操作？
2.3线性表的顺序存储和实现
一线性表的顺序存储结构——顺序表
1 线性表的顺序存储结构
2 顺序表的类型定义
二顺序表的基本操作算法
三利用基本操作实现线性表的其他操作
2.2 线性表的顺序存储和实现
为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；
2）线性表中数据元素的顺序关系；
在计算机内部可以采用不同的方式来存储一个线性表，其中最简单的方式就是本节要讲的线性表的顺序存储结构。
线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。用顺序表存储线性表时，数据元素之间的逻
辑关系，是通过数据元素的存储顺序反映出
来的a 1
a 2
a i-1
a i
a i+1a n
线性表（a 1,a 2,a 3,... a n ）的顺序存储结构用顺序存储结构存储的线性表
——称为顺序表
2.2 线性表的顺序存储和实现
一线性表的顺序存储结构——顺序表
1 线性表的顺序存储结构
2.2 线性表的顺序存储和实现
说明：
·在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映（表示）出来，所以只需存储数据元素的信息；
·假没线性表中每个数据元素占用k 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：
Loc(a
i ) = Loc( a
1
)+ ( i –1) k
这里Loc(a
i )是第i 个元素的存储位置, Loc( a
1
)是第
1个元素的存储位置，也称为线性表的基址；
2.2 线性表的顺序存储和实现
2、顺序表的类型定义
以上用自然语言描述了线性表的顺序存储结构，怎样将这种存储方式在计算机上实现？为此，我们用C语言对这种存储方式进行描述，我们知道C语言一维数组的机内表示也是顺序结构，因此，可借用C语言的一维数组实现线性表的顺序存储。
怎样在计算机上实现
线性表的顺序存储结构？
2.2 线性表的顺序存储和实现
顺序表的类型定义#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量#define LISTINCREMENT 10 // 线性表存储空间的分配增量typedef struct {ElemType * elem; //线性表存储空间基址int length; //当前线性表长度
int listsize; //当前分配的线性表存储空间大小//（以sizeof(ElemType)为单位）}SqList;
1、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2、何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1) 基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2) 基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 3、在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点，删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 4、为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 5、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。 1) 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2) 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3) 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。
《数据结构》 第二章线性表习题 一、单项选择题 1. 线性表是________。 A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的B．一定是不连续的 C．部分地址必须是连续的D．连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。 A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p; 7. 在一个长度为n的顺序表中向第i个元素(0< i