《数据结构与算法分析》课件第2章

第2章线性表2.1线性表的基本概念及运算2.2顺序表2.3链表

2.1线性表的基本概念及运算

线性表(LinearList)是最常用且最简单的一种数据结构。简单地讲，一个线性表是n个数据元素的有限序列(a1，a2，

…，an)。至于一个数据元素ai的具体含义，在不同的情况下可以不同。例如，英文字母表(A，B，C，…，Z)是一个线性表，表中的每一个英文字母为一个数据元素。表2-1所示的学生成绩登记表，是一个略为复杂一点的线性表的例子。

例2-1

利用线性表的基本运算实现清除线性表Ｌ中多余的重复结点。

实现该运算的基本思想是：从表Ｌ的第一个结点(i = 1)开始，逐个检查i位置以后的任意位置j，若两个结点相同，则将位置j上的结点从表Ｌ中删除；当j遍历了i后面的所有位置之后，i位置上的结点就成为当前表Ｌ中没有重复值的结点，然后将i向后移动一个位置。重复上述过程，直至i移到当前表Ｌ的最后一个位置为止。该运算可用如下形式的算法描述：

2.2顺序表

在计算机内，可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表的元素。

假设线性表的每个元素需占用c个存储单元，并以所占第一个单元的存储地址作为数据元素的存储位置，如图2-1所示，则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第

i个数据元素的存储位置Loc(ai)之间满足下列关系：

Loc(ai+1)=Loc(ai)+c

(2-1)图2-1线性表顺序存储结构示意图一般来说，线性表的第i个元素ai的存储位置为

Loc(ai)=Loc(a1)+(i－1)

c

1≤i≤n

(2-2)

其中，Loc(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。由于C语言中的向量(一维数组)也是采用顺序存储表示，因此可以用向量这种数据类型来描述顺序表。2.2.1顺序表的基本运算

1.插入运算

在线性表的第i(1≤i≤n+1)个位置上，插入一个新结点x，使长度为n的线性表

(a1，…，ai-1，ai，…，an)

变成长度为n+1的线性表

(a1，…，ai-1，x，ai，…，an)图2-2顺序表插入元素的过程下面我们给出一个完整的C程序，其中包括三个子函数：Create(建立顺序表)、Insert(插入元素)、Output(输出线性表)，并由主函数调用。

2.删除运算

线性表的删除运算是指将表的第i(1≤i≤n)个结点ai删去，使长度为n的线性表

(a1，…，ai-1，ai，ai+1，…，an)

变成长度为n－1的线性表

(a1，…，ai-1，ai+1，…，an)可以看出，数据元素ai-1，ai，ai+1的逻辑关系发生了变化。为了在存储结构上反映这个变化，同样需要移动元素，即若1≤i≤n-1，则必须将顺序表中在位置i+1，i+2，…，n上的结点，依次前移到位置i，i+1，…，n-1上，以填补删除操作造成的空缺；若i=n，则只要简单地删除终端结点，而无须移动。其删除过程如图2-3所示。图2-3顺序表删除元素的过程

3.算法分析

从上面两个算法可以看出，顺序表的插入与删除运算，其时间主要耗费在移动顺序表中的元素上，而所移动的元素个数不仅依赖于表长n，而且还与插入及删除的位置i有关。

为了不失一般性，假设pi是在第i个位置上插入一个元素的概率，则在长度为n的线性表中插入一个元素须移动元素次数的期望值(平均次数)为

(2-3)假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素须移动元素次数的期望值(平均次数)为

(2-4)为了不失一般性，假设在线性表中任何位置上插入或删除元素的概率相等，则

故

(2-5)

(2-6)2.2.2顺序表的应用实例——学生学籍档案管理

1．问题描述及要求

现有若干学生的学籍档案信息，要求编写一个应用软件对其进行日常管理，以实现学生档案信息的插入和删除，并能根据学生姓名查询。

2．数据结构

我们将所有学生的档案信息存放在一个顺序表中，其中的每个结点是一个学生的档案信息，并假设每个学生的数据包括以下内容：学号、姓名、性别、籍贯，则数据结构定义如下：

3．算法设计

根据问题的要求，整个软件分成四个子模块：按姓名的字典顺序插入学生数据，数据的删除，按姓名查询，打印学生档案。其程序结构如图2-4所示。图2-4程序结构示意图

2.3链表

链式存储是最常用的存储方法之一，它不仅可以用来表示线性表，而且还可以用来表示各种非线性的数据结构。本节将讨论几种用于存储线性表的链接方式：单链表、双链表和循环链表，统称为链表(Linkedlist)。2.3.1单链表

在顺序表中，我们是用一组地址连续的存储单元来依次存放线性表的结点，因此结点的逻辑次序和物理次序一致。而链表是用一组任意的存储单元来存放线性表的元素，这组存储单元既可以是连续的，也可以是不连续的。因此，为了正确地表示元素间的逻辑关系，在存储每个元素值的同时，还必须存储指示其后继元素的地址(或位置)信息。这两部分信息组成数据元素的存储映像，即结点。它包括两个域，存储数据元素信息的域称做数据域；存储后继元素存储位置的域称做指针域。指针域中存储的信息称做指针或链。结点的结构为图2-5线性单链表示意图图2-6单链表的一般图示法单链表是由头指针唯一确定的，因此单链表可以用头指针的名字来命名。例如，若头指针名是head，则把链表称为表head。用C语言描述单链表如下：实际上，以上定义的指针变量p所指向的结点变量是通过标准函数生成的，即

p = malloc(sizeof(linklist))；图2-7指针变量p(其值是结点地址)和结点变量

p(其值是结点内容)的关系2.3.2单链表的基本运算

1．单链表的建立

1)头插法建表

头插法建表是从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直至读入结束标志为止。例如，在空链表head中依次插入结点a、结点b、结点c之后，将结点d插入到当前链表的表头，其指针的修改情况如图2-8所示。其中序号①～④表明了结点插入时的操作次序。其算法描述如下：图2-8将新结点

s插入到单链表head的头上

2)尾插法建表

头插法建表虽然简单，但是生成的链表中结点的次序和输入的顺序相反。若希望两者次序一致，可利用尾插法建表。尾插法建表是将新结点插到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例如，在空链表head中插入结点a、结点b、结点c之后，将结点d插入到当前链表的表尾，其指针的修改情况如图2-9所示。图2-9将新结点

s插入到单链表head的尾上其中序号①～④表明插入结点时的操作顺序。其算法描述如下：这种带有头结点的单链表如图2-10所示，其中，#部分表示头结点的数据域不存储信息，但是在有的应用中，可利用该域来存放表的长度等附加信息。图2-10带头结点的单链表head

2．单链表的查找

1)按序号查找

在单链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，单链表不是随机存取结构。

2)按值查找

按值查找是从开始结点出发，顺着链逐个将结点的值和给定值key做比较，来完成结点的查找。

3．链表的插入

在线性表的顺序存储结构中，由于具有逻辑位置与物理位置一致的特点，使得在进行元素插入和删除运算时有大量的元素参加移动，而在单链表存储结构中，元素的插入或删除，只须修改有关的指针内容，无须移动元素。图2-11在*p之后插入*s

例2-2

在单链表上，将值为x的新结点插入在结点

p前。

分析：由题意知道该插入操作为前插操作。前插操作必须修改

p的前趋结点的指针域，需要确定其前趋结点的位置。但单链表中没有前趋指针，一般情况下必须从头指针起，顺链找到

p的前趋结点

q。前插过程如图2-12所示，其中的序号①～⑤表示插入结点时的操作顺序。图2-12在

p之前插入

s

例2-3

在单链表上实现线性表的插入运算Insert(L,x,i)。

分析：根据题意，该运算是生成一个值为x的新结点，并插入到链表中第i个结点之前，也就是插入到第i－1个结点之后。因此可以先用函数Get求得第i－1个结点的存储位置p：

P = Get(L,i－1)

4．链表的删除

要删除单链表中的结点 

p，就应修改 

p的前趋结点 

q的指针域。一般情况下，要从头指针开始顺着链找到 

p的前趋结点 

q，然后删去 

p。其删除过程如图2-13所示，其中的序号①～③表示删除结点的操作顺序。图2-13删除结点

p

例2-4

在单链表上实现线性表的删除运算Delete(L,i)。

要使删除运算简单，就必须得到被删除结点的前趋，即第i-1个结点 

p，然后删去 

p的后继。其算法描述如下：

例2-5

将两个递增单链表合并为一个递增单链表，要求不另外开辟空间。

此题的算法描述如下：2.3.3循环链表

循环链表(Circularlinkedlist)是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。显然，从表中任意结点出发均可找到表中其他结点，图2-14所示为单循环链表。图2-14单循环链表图2-15仅设尾指针rear的单循环链表

例2-6

在循环链表的第i个元素之后插入元素x。

此题的具体算法如下：2.3.4双向链表

用单链表表示线性表，从任意一个结点出发能通过next域找到它的后继结点，若要寻查结点的前趋，则须从表头指针出发。换句话说，在单链表中，Next(L，ai)的执行时间复杂度为O(1)，而Prior(L，ai)的执行时间复杂度为O(n)。如果在每个结点中增加一个指向直接前趋的指针，处理就灵活得多，它可以克服链表的这种单向性的缺点，这种链表称为双向链表(Doublelinkedlist)。顾名思义，在双向链表的结点中有两个指针域，其中一个指向直接后继，另一个指向直接前趋，其结构可描述如下：图2-16双向循环链表示意图图2-17双向链表上删除结点图2-18双向链表上的前插操作删除结点的算法描述如下：插入结点的算法描述如下：以上详细介绍了线性表及其两种存储结构，在实际应用中究竟如何选择，主要根据具体问题的要求和性质，再结合顺序和链式两种存储结构的特点来决定，通常从以下三个方面考虑。

(1)存储空间。

(2-7)

(2)运算时间。顺序存储结构是一种随机存取结构，便于元素的随机访问，即顺序表中每一个元素都可以在时间复杂度为O(1)的情况下迅速存取；而在链式存储结构中为了访问某一个结点，必须从头指针开始顺序查找，时间复杂度为O(n)。所以对于一个表，只进行查找操作而很少做插入和删除操作时，采用顺序存储结构为宜。

(3)程序设计语言。从计算机语言来看，绝大多数高级语言都提供了指针类型，但也有没有提供指针类型的，为此，可以采用静态链表的方法来模拟动态存储结构。如果问题规模较小，采用静态链表来实现可能会更加方便。2.3.5链表应用实例——多项式的表示及运算

1．问题描述及分析

在数学上，一个一元n次多项式可写成：

Pn(x)=p0+p1x+p2x2+ … +pnxn

(2-8)

它由n+1个系数唯一确定。因此，在计算机中，一元n次多项式Pn(x)可用一个线性表P来表示：

P=(p0，p1，p2，…，pn)

(2-9)

每一项的指数i隐含在其系数pi的序号里。假设Qm(x)是一元m次多项式，用线性表Q来表示：

Q=(q0，q1，q2，…，qm)

(2-10)

为了不失一般性，设m<n，则两个多项式相加的结果Rn(x)=Pn(x)+Qm(x)可用线性表R表示：

R=(p0+q0，p1+q1，p2+q2，…，pm+qm，…，pn)

(2-11)显然，我们可以对P、Q、R采用顺序存储结构表示，使得多项式算法定义十分简洁。至此，一元多项式的表示及相加问题似乎解决了。然而，由于在通常的应用中，多项式的次数可能较高且变化较大，使得顺序存储结构的最大长度很难确定。特别是在处理形如