数据结构课件-线性表

第二章线性表

第二章线性表2.1线性表概念及基本操作2.2线性表的顺序存储和实现2.3线性表的链式存储和实现

2.3.1线性链表

2.3.2循环链表

2.3.3双向链表2.4一元多项式的表示及相加第二章线性表

在本课程介绍的几种数据结构中，线性表是最简单的，也是最常用的数据结构，线性表在实际应用中大量使用，并不是一个陌生的概念。

线性表是n个数据元素的有限序列。通常记作（a1,a2,a3,…,an）。

姓名电话号码

蔡颖63214444陈红63217777刘建平63216666王小林63218888张力63215555...2.1线性表的类型定义例1、数学中的数列（11，13，15，17，19，21）

例2、英文字母表（A,B,C,D,E

Z）。

例3、某单位的电话号码簿。一线性表的逻辑结构

电话号码簿是数据元素的有限序列，每一数据元素包括两个数据项，一个是用户姓名，一个是对应的电话号码。说明：设A=（a1,a2,...,ai-1,ai

,ai+1,…,an）是一线性表1）均匀性：线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2）相邻性：每个元素至少有一个元素与之相邻。在表中ai-1

领先于ai

，ai

领先于ai+1，称ai-1

是ai

的直接前趋，ai+1

是ai

的直接后继；a1,无前驱，an无后继。3）有限性：线性表中元素的个数n称为线性表的长度，n=0时称为空表4）有序性：ai是线性表的第i个元素，称i为数据元素ai

的序号，每一个元素在线性表中的位置，仅取决于它的序号；

线性表的其他表示方式二元组表示

L=<D,S>，其中D={a1,a2,a3,...an}

S={R}R={<a1,a2>,<a2,a3>,<a3,a4>…<an-1,an>}

图示表示

ai+1a1ai-1a2aian顶点：表示数据边：表示是数据间的顺序结构关系L=（a1,a2,...ai-1,

ai

,ai+1,…,an）是一线性表

1初始化操作

InitList(&L)功能：建立空的线性表L；

2销毁操作

DestroyList

(&L)功能：回收为线性表L动态分配的存储空间；

3置空操作

ClearList

(&L)功能：L中已存在，重新将其置成空表；

4判空操作

ListEmpty(L)功能：判断线性表L是否为空表，若为空表返回TRUE，否则返回FALSE；

5求表长操作

ListLength(L)功能：返回线性表L的表长；二线性表的基本操作

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；说明1上面列出的操作，只是线性表的一些常用的基本操作；2不同的应用，基本操作可能是不同的；

例如：上面列出的删除操作Delete(&L,i,&e),功能是在线性表L中删除第i个元素，并用e返回其值。在电话号码查询系统中，一旦某用户撤掉某部电话，则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与给定元素e值相同的数据元素；3线性表的复杂操作可通过基本操作实现；

这有点类似于数中的情形，例如整数的基本操作是+,-,

，/。如果要求某班同学的平均年龄则可利用+/实现，全班同学的平均年龄=(age1+age2+age3+…)/全班同学的人数

关于如何用线性表的基本操作实现复杂操作将在后面讲解。例如，我们要设计一个电话号码查询系统，显然这个系统至少要具备下列功能：

1）查询某人的电话号码；

2）在电话号码薄中，插入一新用户姓名及电话号码；

3）在电话号码薄中，删除已撤销的用户姓名及电话号码；

看看这些操作可以做些什么？？现在我们已经给出了线性表及线性表的一些基本操作。

由上我们知道，电话号码薄可用线性表表示，上面列出的功能实际上就是对线性表的查找、插入、删除操作，为了在计算机上实现上述功能，我们应该做什么呢？显然，首先需要将电话号码薄上的信息存储到计算机中，然后才可能对这些信息进行加工处理，实现上述功能。

强调

本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储数据结构？如何在计算机上实现对数据结构的各种操作，为此，我们将用计算机语言来描述数据的存储结构，用计算机语言来描述这些操作的算法，本课程我们用类C语言做为描述语言。

2.2线性表的顺序表示和实现如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？？

2.2线性表的顺序表示和实现

一线性表的顺序存储结构——顺序表

1线性表的顺序存储结构

2顺序表的类型定义

二顺序表的基本操作算法三利用基本操作实现线性表的其他操作

为了存储线性表，至少要保存两类信息：

1）线性表中的数据元素；

2）线性表中数据元素的顺序关系；

在计算机内部可以采用不同的方式来存储一个线性表，其中最简单的方式就是本节要讲的线性表的顺序存储结构。

线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。用顺序表存储线性表时，数据元素之间的逻辑关系，是通过数据元素的存储顺序反映出来的a1a2ai-1aiai+1an

线性表（a1,a2,a3,...an）

的顺序存储结构用顺序存储结构存储的线性表——称为顺序表一线性表的顺序存储结构——顺序表1线性表的顺序存储结构说明：

1）在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映（表示）出来，所以只需存储数据元素的信息；

2）假设线性表中每个数据元素占用k个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：

Loc(ai)=Loc(a1)+(i–1)k

这里Loc(ai)是第i个元素的存储位置；Loc(a1)是第1个元素的存储位置，也称为线性表的基址；怎样在计算机上实现线性表的顺序存储结构？？2、顺序表的类型定义

以上用自然语言描述了线性表的顺序存储结构，怎样将这种存储方式在计算机上实现？为此，我们用C语言对这种存储方式进行描述，我们知道C语言一维数组的机内表示也是顺序结构，因此，可借用C语言的一维数组实现线性表的顺序存储。顺序表的类型定义

#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量

#defineLISTINCREMENT10//线性表存储空间的分配增量

typedef

struct{

ElemType*elem;//线性表存储空间基址

intlength;//当前线性表长度

int

listsize;//当前分配的线性表存储空间大小//（以sizeof(ElemType)为单位）

}SqList;SqList：类型名，

SqList类型的变量是结构变量，它的三个域分别是：

*elem：存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配；

length：存放线性表的表长；

listsize：用于存放当前分配（存放线性表元素）的存储空间的大小。顺序表图示a1a2ai-1aiai+1anL.lengthL.listsizeL.elemnLIST_INIT_SIZE存放线性表元素的一维数组设A=（a1,a2,a3,...an）是一线性表，L是SqList

类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：二、顺序表的基本操作的实现

现在，我们已为线性表设计好了一种存储结构，下面将看到用这种存储方式存储线性表时，线性表的各种基本操作的实现。

在介绍基本操作的的实现之前，先回顾一下本书算法中常用到的两个C函数。

1)

Malloc(intsize）也可以用p=newtype申请空间ifp==0分配失败功能：在系统内存中分配size个的存储单元，并返回该空间的基址。

使用方法：

...

intm=100,float*p;

p=(float*)malloc(m*sizeof(float));

执行语句p=(float*)malloc(m*sizeof(float))，计算机将按float

类型变量所占空间的大小（一般为32bit）分配m*sizeof(float)个的存储单元,并将其基址赋值给指针变量p;

01299p

p=(float*)malloc(m*sizeof(float))图示

调用free(p)2)

free(p)也可以用deletepointer释放空间

功能：将指针变量p所指示的存储空间，回收到系统内存空间中去；使用方法：...

intm=100;float*p;

p=(float*)malloc(m*sizeof(float));//一旦p所指示的内存空间不再使

//用，调用free()回收之

free(p);

01299p如何在顺序表上实现线性表的基本操作？如何建空表？如何求表长？如何插入？删除？？

设线性表用顺序表L存储，下面我们介绍用顺序表存储线性表时，各种基本操作的算法。当线性表用顺序表存储时，对线性表各种基本操作实际上就是对存储在内存中的顺序表进行操作。1初始化操作InitList_Sq(SqList&L)

参数：L是存放线性表的结构变量（称L为顺序表）。功能：建立空的顺序表L主要步骤：调用malloc()为顺序表分配一预定大小(LIST_INIT_SIZE）的空间,并将其基址赋值给

L.elem;

顺序表初始化01...LIST_INIT_SIZE-1L.elem

0LIST_INIT_SIZEL.lengthL.listsize初始化操作算法：StatusInitList_Sq(SqList&L){//构造一个空的顺序表L

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败

L.length=0;//空表长度为0

L.listsize=LIST_INIT_SIZE;//初始存储容量

returnOK;}//InitList_Sq

算法2.1销毁操作DestroyList_sq(SqList&L)

功能：回收为顺序表动态分配的存储空间

主要步骤：调用free()回收为顺序表动态分配的存储空间L.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1aiai+1an

nLIST_INIT_SIZE00=null销毁操作算法：

StatusDestroyList_Sq(SqList&L){

if(!L.elem)returnERROR;//若表L不存在

free(L.elem);//若表L已存在，回收动态分配的存储空间

L.elem=null;

L.length=0;

L.Listsize=0;

returnOK;

}//DestroyList_Sq

算法2.23、置空操作ClearList_Sq(SqList&L)

功能：若L已存在，重新将其置成空表；

算法：

StatusClearList_Sq(SqList&L){

If(!L.elem)returnERROR;//若表L不存在

L.length=0;//若表L已存在，将L置空

returnOK;

}//ClearList_Sq

算法2.3L.lengthL.listsizeL.elem0199a1a2ai-1aiai+1an

n

99n置空

0

4取元素操作GetElem_Sq(SqListL,inti,ElemType&e)

·功能：将顺序表中第i个元素赋值给e

·算法：

StatusGetElem_Sq(SqList&L,inti,ElemType&e){

if((i<1)||(i>L.length-1))returnERROR;//i非法

e=L.elem[i-1];//将顺序表中第i个元素赋值给e

returnOK;

}//GetElem_Sq

算法2.4

由于C语言的一维数组下标从0开始,故线性表的第一个元素放在L.elem[0]，第i个素放L.elem[i-1]中，最后一个元素放在L.elem[L.length-1]中。

取元素操作

nLIST_INIT_SIZEL.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1aiai+1ann

LIST_INIT_SIZE-1aie插入操作ListInsert_Sq(&L,i,e)

参数：L：顺序表

，

i插入位置，e被插入元素;因为插入操作对顺序表进行修改,所以用了引用参数&L;

功能：在顺序表L的第i个元素之前插入一个新元素e;使长度为n的线性表(a1，…ai-1，ai，…，an)变成长度为n+1的线性表

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

插入操作

a1a2

…ai-1

ai

…ana1a2

…ai-1

…ai

ean<ai-1,ai><ai-1,e>,<e,ai>表的长度增加

为初学者易于理解插入算法主要步骤，这里简化了书上的插入算法2.4，对插入算法中表空间已满的情况，只简单的返回出错（ERROR），在2.2的最后部分给出完整的插入算法。当然，应用中对各种情况的如何处理，要根据实际问题的需要来决定。注意插入操作主要步骤：1）i

是否合法，若合法转2），否则算法结束，并返回

ERROR；

2）L是否已满，若未满转3），否则算法结束，并返回ERROR；3）将顺序表ai

及之后的所有元素后移一个位置；

4)将新元素写入空出的位置；

5）表长+1；StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//在顺序表L中第i个位置之前插入新的元素e,

//i的合法值为1≤i≤L.length+1,当i=L.length+1时//e插在表尾

if(i<1||i>L.length+1)returnERROR;//i值不合法

if(L.length>=L.listsize)returnERROR;//顺序表已满

for(j=L.length-1;j>=i-1;--j)L.elem[j+1]=L.elem[j];

//插入位置及之后的元素后移一个位置

L.elem[i-1]=e;//插入e

++L.length;//表长增1

returnOK;

}//ListInsert_Sq

算法2.5a

插入操作算法为初学者易于理解插入算法，这里通过下标引用L.elem中的元素。StatusListInsert_Sq(SqList&L,intI,ElemTypee){

//在顺序表L中第i个位置之前插入新的元素e,

//i的合法值为1≤i≤L.length+1

if(i<1||i>L.length+1)returnERROR;//i值不合法

if(L.length>=L.listsize)returnERROR;//顺序表已满

q=&(L.elem[i-1]);//q为插入位置

for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素后移一个位置

*q=e;//插入e

++L.length;//表长加1

returnOK;

}//ListInsert_Sq

算法2.5b算法2.5b与算法2.5a唯一的不同是通过指针p引用L.elem中的元素。

插入位置

移动元素个数

1

n

2

n-1

in-i+1

n1

n+10

·算法时间复杂度分析

下面分析插入算法的时间复杂度。顺序表的插入算法2.5a或2.5b中，基本操作是移动元素，算法时间复杂度取决于移动元素的个数，即算法时间复杂度取决于算法中循环体执行次数。移动元素的个数不仅与表长有关，而且与插入位置有关。由此可见

·在顺序表中插入一个元素

，平均要移动表的一半元素。

·表长为n的顺序表，插入算法的时间复杂度为O（n）假设在线性表的任何位置插入元素的概率相同，即

pi=1/(n+1)则

若用pi表示在顺序表的第i个元素之前插入元素的概率，在长度为n的顺序表中插入一个元素，所需移动元素个数数学期望值为：6

删除操作ListDelete_sq(SqList&L,inti,ElemType&e)

·功能：删除顺序表L的第i(1≦i≦n)个元素，并用e返回

使长度为n的线性表：

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

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

(a1，…ai-1，ai+1，…，an)删除操作

ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的长度减少a1a2

…ai-1

ai

ai+1

…ana1a2

…ai-1

删除操作主要步骤：

1）i不合法或表空，算法结束，并返回

ERROR；否则转2）

2）将ai赋值给e;

3）将顺序表中ai后面的元素依次向前移动一个位置;

4）表长-1

删除操作算法StatusListDelete_Sq(SqList&L,inti,ElemType&e){

//在顺序表L中删除第i个元素，并用e返回其值

//i的合法值为1≤i≤L.length，//表空L.length=0则i>L.lengthif((i<1)||(i>L.length))returnERROR;//i值不合法或表空

e=L.elem[i-1];//被删除元素的值赋给e

for(j=i-1;j<=L.length-1;++j)L.elem[j-1]=L.elem[j]//被删除元素之后的元素前移

--L.length;//表长减1

returnOK;

}//ListDelete_Sq

算法2.6a为初学者易于理解插入算法，这里通过下标引用L.elem中的元素。

StatusListDelete_Sq(SqList&L,intI,ElemType&e){

//在顺序线性表L中删除第.i个元素，并用e返回其值

//i的合法值为1≤i≤L.length//表空L.length=0则i>L.length

if((i<1)||(i>L.Length))returnERROR;//i值不合法或表空

p=&(L.elem[i-1]);//p为被删除元素的位置

e=*p;//被删除元素的值赋给e

q=&(L.elem[L.length-1]);//表尾元素的位置

for(++p;p<=q;++p)*(p-1)=*p;//被删除元素之后的元素前移

--L.length;//表长减1

returnOK;

}//ListDelete_Sq

算法2.6b删除操作算法算法2.6b与算法2.6a唯一的不同是通过指针p引用L.elem中的元素。第二章习题一习题三1.

P162.102.

编写算法：1）判空操作statusListEmpty_Sq(SqListL)

2）求表长操作intListLength_Sq(SqListL)习题取自数据结构题集C语言版严尉敏等编清华大学出版社

实验一（学时：4）

电话号码查询系统功能：1建立电话号码簿（用顺序存储结构存储电话号码簿）2在电话号码簿中插入一元素（输入插入位置i,插入元素）3在电话号码簿中删除一元素（输入删除元素位置i）4显示电话号码簿电话号码簿

姓名电话号码

蔡颖63214444陈红63217777刘建平63216666王小林63218888张力63215555...三、利用基本操作实现线性表的其他操作

现在来回答2.1中提到的问题,如何利用已有基本操作实现线性表的其他操作。请看下例。

例：将两个有序线性表归并成一个有序线性表；

设线性表A、B分别用La、Lb的两个顺序表存储，两顺序表中元素按递增顺序排列，编写算法：将La、Lb归并得到顺序表Lc,Lc中的元素也按值递增顺序排列。实现上述功能的算法有三种方法：

1）将Lb并入La;

2）将La并入Lb;

3）将La,Lb并入Lc;(顺序表Lc中的空间是新分配的存储空间）我们采用第三种。基本思想：同时对La.elem,Lb.elem

进行扫描，在扫描过程中按两表当前元素的大小，依次将其插入到Lc的表尾；VoidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){

//已知顺序表La和Lb中的数据元素按值递增排列。

//归并La和Lb得到新的顺序表Lc,Lc的数据元素也按值递增排列。

InitList_Sq(Lc)；

i=j=1;k=0;

La_len=ListLength_Sq(La);Lb_len=ListLength_Sq(Lb);

While((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空

GetElem_Sq(La,i,ai);GetElem_Sq(Lb,j,bj);

if(ai<=bj){ListInsert_Sq(Lc,++k,ai);++i;}

else{ListInsert_Sq(Lc,++k,bj);++j;}

}

while(i<=La_len){

GetElem_Sq(La,i++,ai);ListInsert_Sq(Lc,++k,ai);

}

while(j<=Lb_len){

GetElem_Sq(Lb,j++,bj);ListInsert_Sq(Lc,++k,bj);

}

}//MergeList_Sq

算法2.7a用线性表的基本操作实现线性表的其它操作Lc.elemLc.lengthLc.listsize顺序表的归并图示（算法2.7a)0199La.elem358La.length3

100La.listsize0199Lb.elem2689Lb.length4

100Lb.listsize01992356889100建空表Lc

0La,Lb归并7voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){

//已知顺序表La和Lb的元素按值递增排列

//归并La和Lb得到新的顺序表Lc,Lc的元素也按值递增排列

pa=La.elem;pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;

pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));

if(!Lc.elem)exit(OVERFLOW);//存储分配失败

pa_last=La.elem+La.length-1;

pb_last=Lb.elem+Lb.length-1;

while(pa<=pa_last&&pb<=pb_last){//归并

if(*pa<=*pb)*pc++=*pa++;

else*pc++=*pb++;

}

while(pa<=pa_last)*pc++=*pa++;//插入La的剩余元素

while(pb<=pb_last)*pc++=*pb++;//插入Lb的剩余元素

}//MergeList_Sq

算法2.7b

当然，两线性表归并操作也可不调用基本操作：而是通过直接对顺序表进行操作实现。直接对顺序表进行操作实现顺序表的的其它操作Lc.elemLc.lengthLc.listsize顺序表的归并图示（算法2.7b)

0199La.elem358La.length3100La.listsize0199Lb.elem2689Lb.length4100Lb.listsize

017

2356889

077建空表LcLa,Lb归并顺序表的归并图示（算法2.7b)上述两个算法的时间复杂度为:

O(ListLength(La)+ListLength(La))如果将算法的策略改为:将Lb并入La或将La并入Lb;

算法的时间复杂度为:O(ListLength(La)*ListLength(La))但是节约了空间开销。现在给出完整的插入操作算法！StatusListInsert_Sq(SqList&L,int

i,

ElemTypee){//在顺序线性表L中第i个位置之前插入新的元素e,//i的合法值为1≤i≤ListLength_Sq(L)+1if(i<1||i>L.length+1)returnERROR;//i值不合法

if(L.length>=L.listxize){//当前存储空间已满，重新分配空间

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存储容量}

q=&(L.elem[i-1]);//q为插入位置

for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1

returnOK;}//ListInsert_Sq

算法2.8表空间已满情况的处理在插入数据前查看表空间是否已满L.listsizena1a2ai-1aiai+1anL.elem01n01n+10a1a2ai-1aiai+1anL.listsizen+10将新空间长度赋给L.listsize若满，调用realloc()分配一个更大的存储空间将数据复制到新的空间中L.lengthn顺序表插入对表空间已满情况的处理

顺序表是线性表最简单的一种存储结构

小结顺序表的特点：1通过元素的存储顺序反映线性表中数据元素之间的逻辑关系；2可随机存取顺序表的元素；3顺序表的插入删除操作要通过移动元素实现；2.3线性表的链式存储和实现2.3.1线性链表

一

线性链表的概念

二线性链表的基本操作算法

三静态链表四线性链表的其它操作2.3.2循环链表

2.3.3双向链表

一双向链表的概念

二双向链表的基本操作算法2.3线性表的链式存储和实现

线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。下面介绍线性表的三种链式存储结构,先从最简单的开始

用顺序表存储线性表时，线性表的插入删除操作要移动大量的元素，平均的来看要移动线性表中一半的元素，因此对于应用经常要进行进行插入，删除操作的线性表，一般不使用顺序表存储，下面我们来看线性表的另一种存储结构——链式存储结构。一线性链表的概念

1线性链表2.3.1线性链表a4a3a1a20101010241014101010121014101610181020102210241026用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。

用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的线性链表图示ai-1aia2a1ai+1nan

用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的。2线性链表图示一般来说，我们并不需要写出直接后继的实际地址，为直观起见，通常用如下所示的图表示链表，其中，箭头表示相应单元中保存的是它所指向结点的存储地址。结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；结点的数据域：结点中用于保存数据元素的部分;结点的指针域：结点中用于保存数据元素直接后继存储地址的部分;3线性链表有关术语存储数据元素存储后继结点存储地址结点数据域指针域头指针：用于存放线性链表中第一个结点的存储地址;

空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针;

头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点；

带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表；带头结点的线性链表图示

L是头指针头结点空指针ai-1aia2a1ai+1nanLai-1aia2a1ai+1nan线性链表的每个结点中只有一个指针域故也称为单链表怎样在计算机上实现线性链表？？

上面用自然语言描述线性表的一种链式存储结构——线性链表，怎样在计算机上实现线性链表？显然，可以用C语言的结构表示线性链表的结点，可以用指针存放直接后继的存储地址。

结点变量图示typedef

struct

Lnode{

ElemTypedata;

Struct

Lnode*next;

}LNode,*LinkList;LNode：结构类型名；

LNode类型结构变量有两个域：

data：用于存放线性表的数据元素，

next：用于存放元素直接后继结点的地址；

该类型结构变量用于表示线性链表中的一个结点；

LinkList：指针类型名；

LinkList类型指针变量用于存放LNode类型结构变量的地址；

数据域指针域

datanext

Lnode类型结构变量LLinkList类型指针变量L4线性链表的结点类型定义及指向结点的指针类型定义设L是LinkList类型变量，L用来保存线性链表中第一个结点的地址，则L为线性链表的头指针。ai-1aia2a1ai+1nanL以L为头指针的线性链表称为线性链表L二线性链表基本操作的算法

假设线性表用带头结点的线性链表L存储。下面讨论在这种存储方式下，线性表各种基本操作的算法。当线性表用线性链表存储时，对线性表各种基本操作实际上就是对存储在内存中的线性链表进行操作。如何在线性链表L上实现线性表的基本操作？如何建空表？如何插入？删除？？L∧算法：

StatusInitList_L(LinkList&L){

L=(LinkList)malloc(sizeof(Lnode));

If(!L)exit(OVERFLOW);

L->next=null;

ReturnOK;

}//InitList_L

算法2.91初始化操作InitList_L(LinkList&L)

功能：建空线性链表L

参数：L为线性链表的头指针主要步骤：调用malloc()分配一结点的空间,并将其地址赋值给L；2取元素操作GetElem_L(LinkListL,inti,ElemType&e)

·功能：将线性链表中第i个元素赋值给e取元素操作主要步骤：1）查找链表的第i个元素结点；

2)将第i个元素结点中的数据元素赋值给e;ai-1aia2a1ai+1nanLeai取元素元素操作图示·取元素操作算法：StatusGetElem_L(LinkListL,inti,ElemType&e){//L为带头结点的单链表的头指针。//当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORp=L->next;j=1;//初始化，p指向第一个结点，j为计数器

while(p&&j<i){p=p->next;++j;//顺指针向后查找，直到p指向第i个元素或p为空}if(!p||j>i)returnERROR;//第i个元素不存在

e=p->data;//取第i个元素

returnOK;}//GetElem_L

算法2.103插入操作ListInsert_L(LinkList&L,inti,ElemTypee)

功能：在线性链表L的第i个元素结点之前插入一个新元素结点；插入操作图示：插入前插入后

ai-1aia2a1ai+1nanLai-1aia2a1ai+1naneLai-1

线性表的操作

ListInsert(&L,i,e)

在单链表中的实现：

有序对<ai-1,ai>

改变为<ai-1,e>和<e,ai>

eaiai-1插入操作主要步骤：

1）查找链表L的第i-1个元素结点；

2）为新元素建立结点；

3）修改第i-1个元素结点的指针和新元素结点指针完成插入；插入操作算法：

StatusListInsert_L(LinkList&L,inti,ElemTypee){//在带头结点的线性链表L中第i元素结点之前插入元素ep=L;j=0while(p&&j<i-1){p=p->next;++j;}//寻找第i-1个元素结点

if(!p||j>i-1)returnERROR;//i小于1或者大于表长

s=(LinkList)malloc(sizeof(LNode));//分配新结点

s->data=e;s->next=p->next;p->next=s;//插入新结点

returnOK;}//LinstInsert_L

算法2.11s=(LinkList)malloc

(sizeof

(LNode));//生成新结点s->data=e;s->next=p->next;p->next=s;//插入

eai-1aiai-1sp4删除操作ListDelete_L(LinkList&L,inti,ElemType&e)

功能：在线性链表L中删除第i个元素，并且用e返回其值

删除前删除后ai-1aia2a1ai+1nanLai-1aia2a1ai+1nanL删除操作图示：线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对<ai-1,ai>和<ai,ai+1>

改变为<ai-1,ai+1>ai-1aiai+1ai-1

在单链表中删除第

i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq删除操作主要步骤：1）查找链表的第i-1个元素结点；

2）修改第i-1个元素结点指针，删除第i个元素结点；

3)将第i个元素结点中的数据元素赋值给e;

4）回收被删除结点空间；删除操作算法：StatusListDelete_L(LinkList&L,inti,ElemType&e){//在带头结点的单链表L中，删除第i个元素，并由e返回其值

p=L;j=0;while(p->next&&j<i-1){//寻找第i个结点，并令p指向其前趋

p=p->next;++j;}if(!p->next)||j>i-1)returnERROR;//表中无第i个结点(i不合法)

q=p->next;p->next=q->next;//删除结点

e=q->data;free(q);//回收（释放）结点空间

returnOK;}//LinstDelete_L

算法：2.12三、线性链表的其他操作例1：将两个有序线性链表归并成一个有序表。设线性表A、B分别用头指针为La、Lb的两个带头结点的线性链表存储，且两线性链表中元素按递增顺序排列，编写算法，将La、Lb归并得到线性链表Lc,Lc中的元素也按值递增顺序排列。（注意：线性链表Lc中的结点利用原La，Lb的结点）

实现上述功能的算法有以下三种:

1）将Lb并入La;

2）将La并入Lb;

3）将La,Lb并入Lc;我们采用第三种基本思想：设两个指针pa,pb分别对La,Lb进行扫描，在扫描过程中按

pa,pb所指结点的大小，将其插入到Lc的表尾。线性链表归并操作算法voidMergeList_L(LinkListLa,LinkListLb,LinkList&Lc){

//已知线性链表La和Lb的元素按值递增排列

//归并La和Lb得到新的线链性表Lc,Lc的元素也按值递增排列。

pa=La->next;pb=Lb->next;

Lc=pc=La;//用La的头结点作为Lc的头结点

while(pa&&pb){

If(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}

else{pc->next=pb;pc=pb;pb=pb->next;}

}

pc->next=pa?pa:pb;//插入剩余段

free(Lb);//释放Lb的头结点}//MergeList_L

算法2.17线性链表归并操作图示31n542n6LaLb归并31n6LaLcLb524例2建立线性链表voidCreateList_L(LinkList&1,intn){//输入n个元素的值，建立带表头结点的线性链表

L=（LinkList）malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表

for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新结点

scanf(&p->data);//输入元素值

p->next=L->next;L->next=p;//插入到表头/}}//CreateList_Lai-1aia2a1ai+1nanL第二章习题二习题四P132.1,2.2,2.3,2.14,2.17四静态链表1静态链表的概念上面我们讨论了用指针实现线性链表，下面我们简单讨论一下用一维数组来实现线性链表，用一维数组表示的线性链表，称为静态链表。2静态链表的类型定义

SLinkList：数组的类型名；SLinkList类型的数组变量是结构数组，每一数组分量包括两个域：data：用于存储线性表元素；

cur：

用于存储直接后继元素在数组中的位置（下标）；#defineMAXSIZE1000//链表的最大长度

typedef

struct{

ElemTypedata;

intcur;}component,SLinkList[MAXSIZE];S为slinklist型的变量，s[0].cur指示第一个结点在数组中的位置。设：i=s[0].cur，则s[i].data存储的是线性表的第一个数据元素，且s[i].cur指示第二个结点在数组中的位置。静态链表和动态链表的操作相似，以整型变量i代替动态指针p，用i=s[i].cur代替p=p->next。用户需要自己实现malloc和free这两个函数。使用静态链表时，将空闲的结点连在一起作为备用链。当插入元素时，取一个结点所需的空间（相当于malloc)，当删除一个元素时，将不用的空间连到备用链上（相当于free)。具体算法见后面的应用实例。静态链表图示012345678910

37

a405a3268

a1910a240a4a3a1a20101010241014101010121014101610181020102210241026线性链表图示数组下标地址静态链表与线性链表的区别？？3静态链表图示012345678910

1ZHAO2QIAN3SUN4LI9ZHOU6WU7ZHENG8WANG0SHI

5012345678910

1ZHAO2QIAN3SUN4LI5ZHOU6WU7ZHENG8WANG0

插入前4静态链表操作图示1)静态链表的插入插入SHI

插入后2）静态链表的删除012345678910

1ZHAO2QIAN4SUN

4LI5ZHOU6WU7ZHENG8WANG0012345678910

1ZHAO2QIAN3SUN4LI5ZHOU6WU7ZHENG8WANG0删除前删除sun删除后5静态链表应用实例例：有集合A和B，求（A-B）U（B-A）

思路：首先将A中的所有元素存入链表S，而后将B中的元素存入链表，同时对S表进行查找，若存在和B相同的元素，则从S表中删除，否则将此元素插入S表下面先给出三个要用到的函数：1）建立备用链；2）从备用链上取得一个结点的空间；3）将不用的空间连到备用链上。

voidInitSpace_SL(SLinkList&space){//

将一维数组space中各分量连成一个备用链，space[0].cur为头指针//’0’表示空指针for(i=0;i<MAXSIZE-1;++i)space[i].cur=i+1;space[MAXSIZE-1].cur=0;}//Initspace_SL

算法2.13int

Malloc_SL(SLinkList&space){//

若备用链非空，则返回分配的结点下标，否则返回0i=space[0].cur;if(space[0].cur)space[0].cur=space[i].cur;returni;}//Malloc_SL

算法2.14voidFree_SL(SLinkList&space,intk){//

将下标为k的空闲结点回收到备用链上space[k].cur=space[0].cur;space[0].cur=k;}//Free_SL

算法2.15voiddifference(SLinkList&space,int&S){//

在一维数组space中建立集合(A-B)U(B-A),s为头指针//space[0].cur为备用链的头指针

Initspace_SL(space);//建立备用链s=Malloc_SL(space);//生成s的头结点r=s;

scanf(m,n);for(j=1;j<=m;++j){i=Malloc_SL(space);

scanf(space[i].data);space[r].cur=i;r=i;}//for//建立集合A的链表space[r].cur=0;//尾结点的指针用0表示for(j=1;j<=n;++j){//依次输入B的元素，并在表中查找

Scanf(b);p=s;k=space[s].cur;While(k!=space[r].cur&&space[k].data!=b){//在表中查找P=k;k=space[k].cur;}//whileif(k==space[r].cur){//该元素不存在插入在r所指结点之后,且r的位置不变i=Malloc_SL(space);space[i].data=b;

space[i].cur=space[r].cur;space[r].cur=i;}//ifelse{//该元素已存在，则删除之

space[p].cur=space[k].cur;Free_SL(space,k);if(r==k)r=p;//若删除的元素是尾元素，则需要修改尾指针

}//else}//for}//difference

算法2.16假定集合A=（c,b,e,g,f,d)，B=(a,b,n,f)执行算法2.16的过程如下：01234567891082c3b4e5g6f7d0