数据结构与算法 课件 第2章 线性表

第2章线性表

线性表是一种典型的线性结构，是简单而且常用的数据结构。线性表的顺序和链式存储结构以及基本运算的实现又是后面各章的基础。1【本章重点】①线性表的定义和线性表的基本运算；②顺序存储和链式存储的基本思想；③基于顺序表和单链表基本运算的实现；④基于顺序表和单链表基本运算的时间特性和空间特性。⑤顺序表和链表之间的比较。2【本章难点】①关于顺序表、单链表、循环链表和双向链表的算法设计及应用；②模块之间参数传递的问题。3【本章内容】线性表的逻辑结构线性表的顺序存储结构线性表的链式存储结构顺序表与链表的比较习题242.1线性表的逻辑结构线性表的定义

线性表是由n（n≥0）个元素组成的有限序列，n为线性表的长度。当n=0时称为空表，当n>0时称为非空表，记为L=(a1,…,ai-1,ai,ai+1,…,an)需要注意的几点（1）线性表中各元素具有相同的特性（2）i是元素ai在线性表中的位序，即位置序号，位序从1开始（3）对于一个非空线性表，有且仅有一个开始结点a1；有且仅有一个终端结点an；除第一个结点外，其余结点ai（2≤i≤n)均有且仅有一个直接前驱ai-1；除最后一个结点外，其余结点ai（1≤i≤n-1)均有且仅有一个直接后继ai+15线性表的基本运算（1）InitList(&L)线性表初始化

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

运算结果：构造一个空的线性表。（2）SetNull(L)置空表，

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

运算结果：将表L置为空表。（3）Length(L)求表长度

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

运算结果：返回表L中的数据元素个数。6每一种数据的逻辑结构，对应一组基本运算。这里只是给出抽象的运算，而运算的具体实现，只有在确定了数据的存储结构之后才能够考虑。（4）Get(L,i)取元素值

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

运算结果：返回表L中第i个数据元素ai的值或元素的位置信息。（5）Locate(L,x)定位，按值查找

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

运算结果：若表L中存在一个或多个值为x的元素，返回第一个查找到的数据元素的位序，否则返回一个特殊值。（6）Insert(L,x,i)插入

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

运算结果：在表L中第i个位置上插入值为x的元素，若插入成功，表长加1。（7）Delete(L,i)删除

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

运算结果：删除表L中第i个数据元素，若删除成功，表长减1。7函数的参数L是指向线性表结构体的指针。对线性表的基本运算可以分为三类，所对应的函数参数是不同的。（1）线性表初始化运算使得线性表从不存在到存在，显然指针L的指向发生了变化；（2）置空表、插入和删除运算使得线性表的内容发生了变化，但指针的指向并不会发生变化；（3）求表长度、取元素值和定位运算对于指针L和表的内容都没有发生变化。基本运算应用的举例【例2.1】将线性表A按元素值奇、偶数拆分成两个表，A表存放奇数，B表存放偶数。voidseparate(Linear_list*La,Linear_list*Lb)//已有线性表La和空线性表Lb{

inti=1,j=1,x; while(i<=Length(La)) { x=Get(La,i);//取ai

if(x%2==0) { Insert(Lb,x,j); j++; Delete(La,i);

}//ai是偶数，插入到B表末尾，并从A表中删除

elsei++;//ai是奇数，仍放在A表中

}}说明: （1）将偶数插入到B表，A表只保留奇数

（2）时间复杂度是O(Length(La))82.2线性表的顺序存储结构线性表的顺序存储结构又称为顺序表，是把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里。顺序表中元素地址的计算

假设顺序表中每个元素占用c个存储单元，其中的第一个单元的存储地址则是该元素的存储地址，顺序表中开始元素a1的存储地址是Loc(a1)，那么元素ai的存储地址Loc(ai)可通过下式计算：Loc(ai)=Loc(a1)+(i-1)*c（1≤i≤n）

其中Loc(a1)是顺序表的第一个元素a1的存储地址，称为顺序表的起始地址或基地址。可以对顺序表顺序存取或随机存取。9顺序表的结构类型定义#definemaxsize1024typedefintdatatype;typedefstruct{ datatypedata[maxsize];//采用一维数组存储线性表 intlast;//顺序表当前的长度}sequenlist;10线性表顺序存储的两种方式

由于线性表结点的位序从1开始，而C语言中数组的下标从0开始，关于线性表中数据元素的位序（逻辑位置）和存放它的数组下标（物理位置）之间的关系通常有两种处理方式。（1）从下标为0的数组元素开始存放，则结点的位序等于数组元素的下标加一。（2）从下标为1的数组元素开始使用，这样结点的位序和数组的下标是相等的，使用起来会更简单自然一些，下标为0的元素不用或用作其它用途。这里我们约定采用第一种方式。11位序=下标+1，下标=位序-1位序=下标若L是指向顺序表的指针，则a1~an分别存储在L->data[0]~L->data[L->last-1]中。L->data[i-1]是元素ai；L->last表示线性表当前的长度。基本运算在顺序表上的实现1、顺序表的初始化

在函数中建立一个空顺序表L，指针L从没有指向顺序表变为指向一个空表，显然指针L的指向发生了变化。如何将这一变化的结果带回到主调函数，我们给出以下三种方式，并进行比较。【算法2.1】通过函数返回值将结果带回到主调函数。sequenlist*InitList(){ sequenlist*L=(sequenlist*)malloc(sizeof(sequenlist));//分配顺序表的动态存储空间 L->last=0;//将表的长度置为0 returnL;}//时间复杂度为O(1)12在函数中定义的指针指向顺序表，指针作为函数的返回值。【算法2.2】采用指向指针的指针作为函数参数，通过函数的参数将结果带回到主调函数。voidInitList(sequenlist**L){ *L=(sequenlist*)malloc(sizeof(sequenlist));//第二级指针*L指向顺序表 *L->last=0;//将*L所指向的顺序表长度置0}//时间复杂度为O(1)13第一级指针L指向第二级指针*L，L的指向没有改变，而*L的指向发生了变化，函数运行结束，将*L的指向带回到主调函数。【算法2.3】采用指针的引用作为函数参数，通过函数的参数将结果带回到主调函数。voidInitList(sequenlist*&L)//指针的引用作为参数{ L=(sequenlist*)malloc(sizeof(sequenlist)); L->last=0;}//时间复杂度为O(1)14参数的类型使用了C++语言中的指针类型的引用，从而可以将指针所指向的结构体动态存储带回到主调函数。2、在顺序表中插入一个元素

在线性表的第i（1≤i≤n+1）个位置上插入一个新结点x，并且使表的长度加一，即使 (a1,…,ai-1,ai,…an)变为长度是n+1的线性表 (a1,…,ai-1,x,ai,…an)15【算法2.4】在顺序表的第i个位置上插入一个新结点x。intInsert(sequenlist*L,datatypex,inti)//将新结点插入顺序表的第i个位置。插入成功，返回1；不成功，返回0{ if(L->last==maxsize){print("表已满");return0;} elseif(i<1||i>L->last+1){print("非法插入位置");return0;} else{ for(j=L->last;j>=i;j--)L->data[j]=L->data[j-1];//结点后移 L->data[i-1]=x;//插入到L->data[i-1]中 L->last++;//表长度加1 return1;}}16

3、在顺序表中删除一个元素

将表的第i（1≤i≤n）个结点删去，并且使表的长度减一。即使 (a1,…,ai-1,ai,ai+1,…an)变成长度为n-1的线性表 (a1,…,ai-1,ai+1,…an)17【算法2.5】删除顺序表的第i个结点。intDelete(sequenlist*L,inti)//删除顺序表的第i个结点。删除成功，返回1；不成功，返回0{ intj; if((i<1)||(i>L->last)){print("非法删除位置");return0;} else{

for(j=i;j<=L->last-1;j++)L->data[j-1]=L->data[j];//结点前移

L->last--;//表长度减1

return1； }}18

【例2.2】有顺序表A和B，其表中元素按由小到大的顺序排列。编写一个算法将它们合并为顺序表C，并且表C中的元素也按由小到大的顺序排列。voidmerge(sequenlist*A,sequenlist*B,sequenlist*&C){//在函数中产生顺序表C，为了将C的指向带回到主调函数，参数采用指针的引用 if(A->last+B->last>maxsize)rintf("Error!\n"); else{ C=(sequenlist*)malloc(sizeof(sequenlist)); i=0; j=0; k=0; while(i<A->last&&j<B->last) if(A->data[i]<B->data[j]) C->data[k++]=A->data[i++]; else C->data[k++]=B->data[j++]; while(i<A->last) C->data[k++]=A->data[i++]; //将表A的剩余元素复制完 while(j<B->last) C->data[k++]=B->data[j++]; //将表B的剩余元素复制完 C->last=k; }}19顺序表的应用实例——一个完整的程序

问题的描述：首先建立一个顺序存储结构的线性表，然后删除顺序表中所有值为x的结点。202.3线性表的链式存储结构顺序存储结构的线性表具有顺序存取和随机存取表中元素的优点，同时，它也存在下列缺点：（1）插入、删除操作时需要移动大量元素，效率较低；（2）最大表长难以估计，太大了浪费空间，太小了容易溢出。链式存储结构的线性表可以克服上述缺点，但是只能顺序存取不能随机存取。链表分为单链表、双向链表和循环链表。21

线性表采用单链表来表示，在内存中用一组连续的或不连续的存储单元来存储线性表的数据元素，每个元素含有数据域（data）和一个指针域（next），这两部分信息组成了单链表中的一个结点。22单链表单链表的结点类型定义typedef结点数据域类型datatype;typedefstructnode{ datatypedata; structnode*next;}linklist;linklist*head,*p; //head为头指针，p为工作指针指针所指向的结点存储空间是在程序执行过程中生成和释放的，故称为动态存储空间。在C语言中，通过下面两个标准函数生成或释放结点。

生成结点：p=(linklist*)malloc(sizeof(linklist));

释放结点：free(p);必须通过指针来访问结点，即用*p表示结点。用p->data和p->next，或者(*p).data和(*p).next表示结点的数据域和指针域。23关于链表的头结点

单链表以及后面所讨论的循环链表和双向链表均可以带头结点或者不带头结点。24单链表的基本运算1、建立单链表

假设单链表结点的数据域类型是字符型，我们逐个输入字符，并以换行符“\n”作为输入结束标志。动态建立单链表通常有以下两种方法。（1）头插法建表

从空表开始，每次将输入的字符作为新结点插入到表头，链表中结点的次序与输入字符的顺序相反。用伪代码描述单链表的建立过程：

251 建立只有头结点的空表2 循环读取字符，若不是换行符，则执行循环体；若是换行符，则结束循环

2_1 产生新结点

2_2 将新结点插入到表头，即作为单链表当前的第一个结点3 返回单链表的头指针【算法2.6】头插法建立单链表linklist*CreateListF()//带头结点的头插法，返回单链表的头指针{ linklist*head,*p;charch;head=(linklist*)malloc(sizeof(linklist));//产生头结点①head->next=NULL; while((ch=getchar())!='\n')//输入abc{p=(linklist*)malloc(sizeof(linklist));//生成新结点②p->data=ch;//对结点的数据域赋值③p->next=head->next;//新结点的指针域指向原第一个结点④head->next=p;//修改头结点的指针域⑤}returnhead;}26（2）尾插法建表【算法2.7】尾插法建立单链表linklist*CreateListR()//带头结点的尾插法，返回单链表的头指针{ linklist*head,*p,*r;charch; head=(linklist*)malloc(sizeof(linklist)); //生成头结点① head->next=NULL;//建立空表 r=head;//r指针指向头结点

while((ch=getchar())!='\n')//输入abc { p=(linklist*)malloc(sizeof(linklist));//生成新结点② p->data=ch;//将输入的字符赋给新结点的数据域 r->next=p; //新结点插入表尾③ r=p; //r指针指向到表尾④ } r->next=NULL;//表尾结点的指针域置空⑤ returnhead;}//时间复杂度为O(n)272、单链表查找对单链表的查找只能从表头开始顺序查找。

（1）按序号查找

单链表的第一个结点的序号为1，第二个结点的序号为2，以此类推。

设单链表的长度为n，并且规定头结点的位序为0，要查找第i个结点，仅当1≤i≤n时，才能查找到；否则查找不到，返回NULL。

（2）按值查找

在单链表中查找是否存在给定查找值key的结点，若存在，则返回该结点的地址；否则返回NULL。283、单链表的插入

在单链表中插入结点，只需要修改指针的指向，不需要移动结点。

单链表只能做“后插”，不能做“前插”。算法2.11是在单链表的第i个结点之前插入一个新结点，必须先找到第i-1个结点并插入，即将“前插”变为“后插”。【例2.3】将值为x的新结点插入到递增有序单链表中，使插入后该链表仍然有序。

先查找插入位置，然后插入新结点。在查找过程中，若遇到某个结点的元素值大于等于x，则在该结点之前插入新结点。在单链表中必须利用前驱指针将“前插操作”变为“后插操作”。294、单链表的删除

在单链表中删除一个结点，必须先查找到该结点的直接前驱结点，然后删除该结点。【算法2.12】单链表的删除voidDelete(linklist*L,inti)//在带头结点的单链表中删除第i个结点{ p=Get(L,i-1);//调用算法2.9，找第i-1个结点① if(p!=NULL&&p->next!=NULL)//第i-1个结点和第i个结点均存在 { r=p->next;//r指向*p的后继结点② p->next=r->next;//删除结点*r③ free(r);//释放结点*r所占的存储空间 } elseprintf("第i个结点不存在");}30循环链表

循环链表的一种形式是单循环链表。其特点是单链表中最后一个结点的指针域指向头结点或开始结点，整个链表形成一个环，从表中任一结点出发均可找到表中其他结点。31【例2.4】在单循环链表上实现将两个线性表（a1,a2,…,am）和（b1,b2,…,bn）合并为一个循环链表（a1,…,am,b1,…,bn）的运算。（1）采用尾指针，为指针指向终端结点，在算法中没有循环，算法的时间复杂度为O(1)。（2）采用头指针，分别需要找到La表和Lb表的终端结点，需要两个循环的并列，算法的时间复杂度为O(Length(La)+Length(Lb))。32双向链表（双向循环链表）

双向链表结点的结构体类型定义：typedefstructdnode{datatypedata; //data为结点的数据域structdnode*prior,*next;//prior和next分别是结点的前驱和后继指针域}dlinklist;dlinklist*head;33双向链表将头结点和终端结点链接起来，构成顺时针和逆时针的两个环。

双向链表可以“后插”，也可以“前插”。【算法2.13】双向链表的后插voidDInsertAfter(dlinklist*p,datatypex){//在带头结点的非空双向链表中,将值为x的新结点插入*p之后

dlinklist*s=(dlinklist*)malloc(sizeof(dlinkl