第2章线性表(修改)

第2章线性表●

本章要点

●

线性表的逻辑结构

●线性表的顺序存储

●

线性表的链式存储

●

顺序表和链表的比较●

本章难点

●

顺序存储结构、链式存储结构及基本运算的实现●

2.1线性表的逻辑结构●2.1.1线性表的类型定义线性表是一种线性结构，线性结构的数据元素之间是一种线性关系，线性关系的特点如下：

●在一个线性表中的数据元素的类型是相同的，数据元素一个接一个的排列。

●存在一个唯一的被称作“第一个”的数据元素。

●存在唯一的一个被称作“最后一个”的数据元素。

●除第一个之外，每个数据元素均只有一个前驱；除最后一个之外，每个数据元素均只有一个后继。一个线性表是n(n≥0)个同类型数据元素a1,a2,a3,…，an的有限序列。记作：（a1,a2,a3,…,an）从定义可以看出，线性表强调两个特性：（1）任何数据元素ai

(i=1,…，n)必须是同类型的数据，例如，如果是记录，则必须是含有相同数据项的记录；如果是整数，则必须都是整数，不能将不同性质的数据列在一个线性表内。（2）另一个是数据元素的有序性，数据元素在表中的位置决定了它的序号。按照这个次序，元素ai-1

称为ai

的直接前趋，ai

称为ai-1

的直接后继（i=1,2,3,…，n）。a1是表中第一个元素，它没有前趋；an是表中最后一个元素，它没有后继。表中数据元素的个数n称为线性表的长度。长度为0的线性表称为空表。称i为ai在线性表中的位序。●2.1.1线性表的类型定义

【例1】英文字母表（A，B，…，Z）是线性表，表中每个字母是一个数据元素（结点）

【例2】一副扑克牌的点数（2，3，…，10，J，Q，K，A）也是一个线性表，其中数据元素是每张牌的点数

【例3】学生成绩表中，每个学生及其成绩是一个数据元素，其中数据元素由学号、姓名、各科成绩及平均成绩等数据项组成。将数据元素称为记录，含有大量记录的线性表成为文件。举例其抽象数据类型的定义如下：

ADTList{

数据对象：Data＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：R1＝{<ai-1,ai>|ai-1,ai∈Data,i=2,...,n}}

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

●2.1.1线性表的类型定义数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的，每一种操作的具体实现只有在确定了线性表的存储结构之后才能完成。对于线性表，常用的运算有如下几种：(1)置空表（结构初始化）

init_seqlist(L)；

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

list_length(L);初始条件：线性表L已存在。操作结果：返回L中元素个数。●2.1.2线性表的基本操作⑶定位:访问线性表的第i个元素。

get_node(L,i);初始条件：线性表L已存在。操作结果：返回L中第i个元素的值或地址。⑷查找:在线性表中查找满足某种条件的数据元素。

location_list(L,x);

初始条件：线性表L已存在。操作结果：返回L中值为给定值x的数据元素。●2.1.2线性表的基本操作⑸插入:在线性表的第i个元素之前，插入一个同类型的元素。

insert_list(L,i,x);初始条件：线性表L已存在。操作结果：在L的第i个位置插入一个值为x的新元素。⑹删除:删除线性表中第i个元素。

delete_list(L,i);初始条件：线性表L已存在。操作结果：在L中删除序号为i的数据元素。⑺清除表:将已有线性表变为空表，即删除表中所有元素。

●2.1.2线性表的基本操作

一种数据结构只有在内存中正确表示出来，才能实现其基本操作。数据结构在内存中的表示通常有两种形式，即顺序存储表示和链式存储表示。线性表的顺序表示又称为顺序表。

2.2.1顺序表

用一组地址连续的存储单元依次存储线性表的数据元素，这种存储方式称为线性表的顺序存储结构。它以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系，即逻辑上相邻的数据元素在物理位置上也是相邻的。

●

2.2线性表的顺序存储线性表的顺序存储结构具有以下基本特点：(1)存储空间必须是连续的，预分配；(2)逻辑顺序与物理顺序一致，用物理上的相邻来表示逻辑上的线性关系。(3)任意相邻元素之间无空闲空间，且相距为L(4)已知基地址，可以计算出任意元素的存储地址a1a2…ai-1aiai+1…an…length-1线性表的顺序存储设a1的存储地址为Loc(a1)，称为基址，每个数据元素占d个存储单元，则第i个数据元素的地址为：

Loc(ai)＝Loc(a1)+(i-1)*d１≤i≤n

已知顺序表的首地址和每个元素所占地址单元的个数，就可求出第i个数据元素的地址。●2.2.1顺序表所以称顺序表为一种随机存取的结构知识点回顾:用typedef定义类型可以用typedef声明新的类型名来代替已有的类型名。例1：typedef

intCOUNT;COUNTI,j;例2：typedef

struct{intmonth;

intday;

intyear;}DATE;新类型名DATEDATEbirthday;DATE*p;说明：对于上结构体，typedef

后跟一个无命名的结构体类型例3：typedef

structNode{elemtypedata;

structNode*next;}ListNode,*LinkList;Typedef与#define区别如：Typedef

intCOUNT;和#defineCOUNTint

二者不同#define是在预编译时处理的，只能做简单的字符串替换。而typedef是在编译时处理的，它可以像定义变量的方法那样声明一个类型。如：COUNTI,j;顺序表的虚拟实现：在高级语言中，数组是采用顺序存储的，所以我们可以用数组类型来说明顺序表的存储方式。即顺序表类型定义

●2.2.1顺序表#defineMAXSIZE100//表空间的大小可根据实际需要而定，这里假设为100typedef

int

ElemType//ElemType的类型可根据实际情况而定，这里假设为int

typedef

struct{Elemtype

data[MAXSIZE];//最多有MAXSIZE个数据元素

intlength;//存放数据元素的实际个数

}SeqList;//定义了一个新类型：顺序表类型SeqListlist;

//定义一个变量：顺序表list为了能够对顺序表进行整体引用，通常将data和length封装成一个结构体作为顺序表的类型。知识点回顾：结构体中成员的表示表长＝list.length=n；表空标志list.length=0；表满标志list.length=MAXSIZE；即0<=length<=MAXSIZE数据元素list.data[0]～list.data[list.length-1]注意：下标要减1

根据C语言规则，定义一个指向SeqList类型的指针变量更方便，即定义一个指向顺序表SeqList的指针变量pslist

SeqList*pslist;存储空间的动态分配：sizeof()函数：返回各种数据类型所占用的存储空间大小malloc(unsignedsize)函数：每次调用时，要求一块内存空间声明格式：

void*malloc(unsigneg

intsize);

size表示所需内存空间大小，单位是字节。如果成功分配内存空间，函数返回第一个字节的指针。这时须另外加上类型的转换，使函数返回的指针符合所配置的类型。

fp=(数据类型*)malloc(sizeof(数据类型))

说明：如果内存空间不足，malloc()将会配置失败且返回一个空指针，需确定内存配置成功，即返回有效的指针，接着才能使用这块内存，否则将产生未知的结果。

获得线性表的存储空间：

pslist=(SeqList*)malloc(sizeof(SeqList));●2.2.1顺序表#defineMAXSIZE100typedef

int

ElemTypetypedef

struct{Elemtype

data[MAXSIZE];

intlength;}SeqList;SeqListlist,*pslist;

//定义一个顺序表list,一个指向顺序表的指针pslistpslist=(SeqList*)malloc(sizeof(SeqList));另一种存储表示（略）#defineLIST-INIT-SIZE100#defineLISTINCREMENT10Typedef

struct{

Elemtype*elem;

intlength;

int

listsize;}Seqlist;pslist是一个指针变量，存放的是顺序表的地址。表示方法：表长pslist->length；

//

等同于(*pslist).length

表空标志pslist->length=0；表满标志pslist->length=MAXSIZE；数据元素pslist->data[0]～pslist->data[pslist->length-1]a1a2…ai-1aiai+1…an…01…i-2i-1i…n-1MAXSIZE-1a1a2…ai-1aiai+1…an…pslist->datapslist->length-1●2.2.1顺序表注意：

①存放线性表结点的向量空间的大小MAXSIZE应仔细选值，使其既能满足表结点的数目增加的需求，又不致于预先定义过大而浪费存储空间。

②由于C语言中向量的下标从0开始，所以若L是SqList类型的指针变量，则a1和an分别存储在L.pslist[0]和L.pslist[length-1]中。

注意问题：参数：值传递和地址传递的区别参数传递的方向边界值的处理：在第一个元素前插入在最后一个元素后插入当删除或插入元素时，线性表的长度改变指定的数据元素的位置是否合法●2.2.2顺序表的基本运算⒈顺序表的初始化初始化即构造一个空表。算法分析将pslist设为指针参数，动态分配存储空间需考虑问题：（1）动态分配空间是否成功（2）表中length值设为0初始化算法实现：SeqList*init_SeqList(){SeqList*pSlist;

pSlist=(SeqList*)malloc(sizeof(SeqList));if(pSlist!=NULL)

pSlist->length=0;else

printf(“Outofspace!”);

return(pSlist);}main(){SeqList*pSlist;

pSlist=init_Seqlist();}●2.2.2顺序表的基本运算

⒉插入算法顺序表的插入是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素（如：x)，使长度为n的线性表（a1,…,ai－1,ai,…,an）变成长度为n+1的线性表：（a1,…,ai－1,x,ai,…,an）算法分析⑴将ai～an顺序向后移动，为新元素让出位置；⑵将x置入空出的第i个位置；⑶修改length指针（修改表长），使之仍指向最后一个元素。●2.2.2顺序表的基本运算j的取值范围：

i-1<=j<=length-1移动语句：For(j=length-1;j>=i-1;j--)data[j+1]=data[j];i-1n-1自下而上的向下移动j起始位置需考虑问题：

(1)分配时由于向量空间大小在声明时确定，当L-＞length=MAXSIZE时，表空间已满，不可再做插入操作；

(2)当插入位置i的值为i＞length+1或i＜1时为非法位置，不可做正常插入操作；

(3)移动元素时是整体自下而上的顺序；

(4)length值增1；插入算法实现：int

insert_list(SeqList*pslist,inti,Elemtypex){intj;if(pslist->length==MAXSIZE){printf(“表满\n”);return-1;}if(i<1||i>pslist->length+1){printf(“位置错”)；

return(0);}●2.2.2顺序表的基本运算

for(j=pslist->length-1;j>=i-1;j--)

pslist->data[j+1]=pslist->data[j];

/*结点向后移*/

pslist->data[i-1]=x;

/*插入新元素*/

pslist->length++;

/*length仍指向最后元素*/return1;}●2.2.2顺序表的基本运算时间复杂度分析：设在第i个位置插入的概率为Pi＝平均移动次数Eis(n)=＝

＝n/2

说明做插入操作时，需要移动一半的数据元素，时间复杂度为O(n)。●2.2.2顺序表的基本运算⒊删除运算与线性表插入运算相对，将线性表的第i个元素删除的操作是使长度为n的线性表（a1,…,ai-1,ai,ai+1,…,an

）变成长度为n-1的线性表（a1,…,ai-1,ai+1,…,an-1

）算法分析⑴将ai+1～an顺序向前移动。⑵修改length指针(修改表长)，使之仍指向最后一个元素。●2.2.2顺序表的基本运算in-1自上而下的向上移动j起始位置j的取值范围：

i<=j<=length-1移动语句：For(j=i;j<=length-1;j++)data[j-1]=data[j];需考虑问题：(1)如果需ai，应先返回ai的值。(2)检查要删除位置的有效性，1≤i≤n；(3)当表空时不能做删除，因表空时pslist->length的值为0，条件（i<1||i>pslist->length）也包括对表空的检查（符合i>length）；(4)移动元素时是整体自上而下的顺序；(5)length值减1；

删除算法实现int

delete_list(SeqList*pslist,inti){intj;if(i<1||i>pslist->length){printf(“不存在第i个元素\n”);return(0);}for(j=i;j<=pslist->length-1;j++)

pslist->data[j-1]=pslist->data[j];

pslist->length--;return1;}●2.2.2顺序表的基本运算时间复杂度分析：删除第i个位置的概率为Pi＝平均移动次数Ede(n)=＝＝说明删除运算时平均需要移动一半的数据元素，时间复杂度为O(n)。●2.2.2顺序表的基本运算⒋按值查找线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素，并返回查找成功与否标志。算法分析从第一个元素a1起依次和x比较，直到找到一个与x相等的数据元素，则返回它在顺序表中的存储下标或序号(二者差一)；如果没有找到，返回-1。●2.2.2顺序表的基本运算

顺序表按值查找算法实现int

location_seqlist(SeqList*pslist,elemtypex){inti;i=0;while(i<=pslist->length-1&&pslist->data[i]!=x)i++;if(i>pslist->length-1)return–1;elsereturni;/*返回存储位置*/}●2.2.2顺序表的基本运算时间复杂度分析：本算法的主要运算是比较，比较次数与x的位置有关，也与表长有关。●2.2.2顺序表的基本运算

找到找不到最好情况1次O(1)

n+1次O(1)最坏情况n次O(n)n+1次O(n)平均情况n/2次O(n)n+1次O(n)●2.2.2顺序表的基本运算⒌查找操作查找顺序表中第i个位置上的元素值，并将该元素的值返回。

查找操作算法实现Elemtype

Get_Node(SeqList*pslist,inti){

if(i>=1&&i<=pslist->length)

return(pslist->data[i-1]);else{printf(“Notexit.\n”);return(-1);}}

求表长算法实现int

list_length(SeqList*pslist){

return(pslist->length);//求pslist所指向顺序表的长度

}⒍求表长求线性表的长度，并返回长度值。●2.2.2顺序表的基本运算算法5和算法6的时间复杂度均为O(1)【例2.1】顺序表的划分。将顺序表(a1,a2,…，an)重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值都比a1大。。●2.2.3顺序表的应用12268111910…10118122619…划分前划分后算法分析从第二个元素开始⑴当前数据比a1大时，不改变其位置，继续比较下一个。⑵当前数据比a1小时，将其前面的元素依次向后移动一个位置，然后将其置入对应单元。●2.2.3顺序表的应用12268111910…将26和12比较，比12大，不用变化，再比较8和12，比12小，则12、26均向后移动需要一个变量来存放比较的位置，此算法用i来表示数组下标位置。1<=i<=length当需要移动元素时，需要一个变量表示移动的范围，用j表示。0<=j<=i-1基准(12)的位置会发生变化，也需要存储起来，用x来存储。x=data[0]移动元素时，当前正比较的值防止被覆盖也需要存储起来。Y=data[i]算法主体是循环结构，由i来控制，请同学们自己编写。●2.2.3顺序表的应用

voidpart(SeqList*L){int

i,j;

elemtype

x,y;x=L->data[0];for(i=1;i<=L->length-1;i++)if(L->data[i]<x){y=L->data[i];for(j=i-1;j>=0;j--)L->data[j+1]=L->data[j];L->data[0]=y;}}●2.2.3顺序表的应用【例2.2】顺序表的合并。已知顺序表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的顺序表LC，且LC中的数据元素仍按值非递减有序排列。

LA=(1，4，7，10)

LB=(2，3，9，12，16)

LC=(1，2，3，4，7，9，10，12，16)算法分析设LC为空表，依次扫描LA和LB，比较当前元素，将较小值的元素赋给LC，直到一个线性表扫描完毕，然后将未完的顺序表中余下部分赋给LC即可。三个顺序表都需要设个变量存当前的位置。

voidunion(SeqListLA,SeqList

LB,SeqList*LC){int

i,j,k;i=0;j=0;k=0;while(i<=LA.length-1&&j<=LB.length-1)if(LA.data[i]<LB.data[j])LC->data[k++]=LA.data[i++];elseLC->data[k++]=LB.data[j++];while(i<=LA.length-1)LC->data[k++]=LA.data[i++];while(j<=LB.length-1)LC->data[k++]=LB.data[j++];LC->length=LA.length+LB.length;}●2.2.3顺序表的应用从前面看到，顺序存储结构有特点：（1）逻辑顺序与物理顺序一致（2）随机存取但是，也存在一些缺点：（1）插入、删除等操作要移动元素（2）存储空间是预分配的，不灵活，浪费空间（3）表的存储空间难扩充●

2.3线性表的链式存储那么，有没有一种灵活的存储方式呢？回答是肯定的！——链式存储结构，但是有优点，同样也存在缺点线性表的链式存储方式：（1）是用一组任意的存储单元存储数据元素（这组存储单元可以是连续的，也可以是不连续的）。（2）为了表示线性关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储直接后继的存储位置（也可以是前驱）。这两部分信息组成数据元素的ai的存储映象，称为结点（Node）。它包括两个域：数据域和指针域。n个结点链结成一个链表，即为线性表的链式存储结构。又由于每个结点中只包含一个指针域，故又称为单链表。●

2.3线性表的链式存储●2.3.1线性链表线性表的链式存储结构的特点⑴存储空间不一定连续⑵逻辑关系由指针来体现(3)逻辑上相邻，物理上不一定相邻(4)非随机存取（顺序存取），即访问任何一个元素的时间不同。如磁带和CD注意：

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

●2.3.1线性链表存储地址数据域指针110E150120D110125A160140C120150FNULL160B140125头指针head链式存储结构例：有线性表h＝（A,B,C,D,E,F），其对应的链式存储结构如图所示。●2.3.1线性链表datanext虚拟实现：利用高级语言中的指针来实现。结点定义如下：typedef

structNode{elemtypedata;

structNode*next;}ListNode,*LinkList;结点（Node）

单链表中每个结点的存储地址是存放在其前趋结点next域中，而起始结点无前趋，故设头指针head指向起始结点。定义头指针变量：LinkListhead;

LinkNode*p;

LinkListhead;注意：

①LinkList和LNode*是不同名字的同一个指针类型（命名的不同是为了概念上更明确）

②LinkList类型的指针变量head表示它是单链表的头指针

③LNode*类型的指针变量p表示它是指向某一结点的指针●2.3.1线性链表ABCDE∧Fhead链表的逻辑结构nextdataPpdatapnext算法中各个域的表示如定义一个指针p：Linklistp(*p).data(*p).nextHead==NULL不带头结点的空表ABCDE∧head不带头结点的链表这种链表称为不带头结点的链表，但是首结点无前驱，很多操作需要单独考虑首结点。第一个结点的处理和其它结点不同，因为第一个结点加入时链表为空，它没有直接前驱结点，其地址就是整个链表的指针需要放在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。“第一个结点”问题在很多操作中都会遇到，如链表中插入结点时，将结点插在第一个位置和其它位置不同，删除结点时，删除第一个结点和其它结点的处理不同。

●2.3.3线性链表的基本运算说明：

起始结点和其他结点的不同处理：由于起始结点的位置是存放在表头指针中，而其余结点的位置是在其前趋结点的指针域中，插入起始结点时要将头指针指向起始结点。

空表和非空表的不同处理：若读入的第一个数据就是结束标志，则链表head是空表，尾指针r也为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，将其指针域置空。●2.3.3线性链表的基本运算头结点的数据域可以不存储任何信息，也可存储如线性表的长度等附加信息。指针域存放首元结点的地址head∧带头结点的空表ABCD∧Ehead附加头结点的链表头指针头结点首元结点Head－>next==NULL头结点是在链表的起始结点之前附加的一个结点，有两个优点：⑴由于起始结点的位置被存放在头结点的指针域中，故在链表的第一个位置上的操作与表中其他位置上操作一致，无须进行特殊处理。⑵无论链表是否为空，其头指针都是指向头结点的非空指针，故此空表和非空表的处理也统一了。●2.3.2动态内存分配

动态内存分配指在程序执行过程中动态地分配或回收存储空间，在需要时，由系统即时分配。⒈malloc()函数

void*malloc(unsigned

intsize)

在内存的动态存储区中分配一个长度为size的连续空间。例p=(long*)malloc(8)

/*开辟长度为8个字节的内存空间，并把起始地址赋给一个指向long型的指针变量p*/注意当函数未能成功分配存储空间（如内存不足）时，返回一个NULL指针，即调用该函数时检测返回值是否为NULL并执行相应的操作。●2.3.2动态内存分配例：动态分配程序

#include<stdio.h>

/*标准输入输出文件*/#include<stdlib.h>

/*动态分配文件*/main(){intcount,*array;

if(array=(int*)malloc(10*sizeof(int)))==NULL){printf(“error!”);exit(1);}for(count=0;count<10;count++)

array[count]=count;for(count=0;count<10;count++)printf(“%2d”,array[count]);}⑴分配10个整型的连续存储空间，并返回一个指向其起始地址的整型指针。⑵将整型指针地址赋给array。⑶检测返回值是否为NULL。●2.3.2动态内存分配

⒉free函数当分配的内存空间不用时，要释放存储空间。

voidfree(void*p)释放指针p所指向的内存区。参数p是先前调用malloc函数时返回的指针。注意

malloc函数是对存储区进行分配，free函数是释放已经不用的内存区域，这样就可以实现对内存区域进行动态分配并进行简单的管理。p1=malloc(10*sizeof(int));Free(p1);1.单链表的初始化创建一个带头结点的空链表。算法设计为单链表结构及表头结点申请空间，若申请成功，则返回线性表。●2.3.3线性链表的基本运算●2.3.3线性链表的基本运算创建一个带头结点的空链表

LinkList

init_NullList(){Lnode*pLlist;

pLlist=(LinkList)malloc(sizeof(ListNode));/*申请表头结点*/

if(pLlist!=NULL)

pLlist->next=NULL;else

printf(“outofspace!”);

return(pLlist);}●2.3.3线性链表的基本运算2.求表长求表长即求单链表中数据元素的个数。设L是带表头结点的单链表。算法设计设动态指针p和计数器count，p先指向头结点，即p=L，计数器count=0，p所指结点后面若还有结点，p向后移动，计数器count加1，直到p所指结点后面无结点，计数器count的值即为表长。

对于线性链表，可以从头指针(head)开始，沿各结点的指针扫描到链表中的所有结点。这个过程叫“遍历”。指针后移操作：

p=(*p).nextABCD∧Eheadp●2.3.3线性链表的基本运算带表头结点的单链表求表长

int

length_LinkList(LinkListL){Lnode*p;

intcount;p=L;

/*p指向头结点*/count=0;while(p->next!=NULL){p=p->next;count++;

/*p所指的是第count个结点*/}returncount;}此操作遍历了整个链表，时间复杂度：O(n)此处注意：p->next!=NULL与p!=NULL不同请同学们说出，哪儿不同？●2.3.3线性链表的基本运算3.查找操作⑴链表中按序号查找（查找指定位置的结点）按序号查找是线性表的一种常用运算，其功能是对给定的链表查找表中第i个结点，并用一个指针变量指向该结点。算法设计从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针；否则继续判断后一个，直到表结束为止。没有第i个结点时返回空。请同学们现在自己编写这个算法

当做遍历操作时候，while条件都要加上while(p->next！=NULL&&？？)或while(p->next！=NULL||？？)或while(p！=NULL&&？？)或while(p！=NULL||？？)i的合法位置为１－n，j的取值范围0-n若i<1，则while条件中j<i为永假，while不会执行。此时j==0;

(i可能与j相等)若i>n+1，则while条件中j<i-1为永真，while退出条件时p->next＝＝NULL，此时j=n;

(i与j肯定不相等)若1<=i<=n+1，执行while，退出while时为j==I;

(i与j肯定相等)

由此，可根据下面条件来判定位置是否合理，即是否找到第i个位置元素

if(i==j&&i!=0)●2.3.3线性链表的基本运算ListNode*Get_LinkList(LinlList

Llist,inti)/*在单链表Llist中查找第i个结点，找到返回其指针，否则返回空指针*/{intj=0;

ListNode*p;p=Llist;while(p->next!=NULL&&j<i){p=p->next;j++;}if(i==j&&i!=0)return(p);else

return(NULL);}按序号查找链表数据元素算法一还有其他的表示方法吗？Int

Getelem(linklist

l,intI,int*e){P=L->next;J=1;While(p&&j<i) {p=p->next;++j;}If(!p||j>i)return-1;E=p->data;Return1;}算法二：●2.3.3线性链表的基本运算⑵按值查找操作算法分析从链表的第一个结点起，判断当前结点值是否等于x，若是，返回该结点的指针；否则继续判断后一个，直到表结束，找不到时返回空。

ListNode*Locate_Linklist(LinkList

Llist,Elemtypex){ListNode*p;p=Llist->next;/*设置初值*/while(p!=NULL&&p->data!=x)p=p->next;/*未达到尾结点，又未找到值等于x的结点时，继续找*/

return(p);/*找到值为x的结点，返回它的地址*/}查找算法的时间复杂度均为O(n)算法

(1)分配时由于向量空间大小在声明时确定，当L-＞length=MAXSIZE时，表空间已满，不可再做插入操作；

(2)当插入位置i的值为i＞n+1或i＜1时为非法位置，不可做正常插入操作；

(3)移动元素时是整体自下而上的顺序；

(4)length值增1；4.插入操作在顺序表的插入算法中需考虑问题：链表的插入算法与顺序表插入算法相比较：（1）不存在“表满”（2）插入位置合理性判断1<=i<=n+1（3）不需要移动元素（4）不需要length设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p后面。a1a2an∧head…ai-1ai……xps①s->next=p->next;②p->next=s;●2.3.3线性链表的基本运算①②注意两个指针的操作顺序不能交换，否则p结点后面的结点将被断开，不能实现正确插入。在第i位置之前插入一个值为x的结点，算法如下：Int

insert_LinkList(LinkListhead,inti,Elemtypee){P=head;j=0;While(P&&j<i-1) {p=p->next; ++j; }If(!p||j>i-1)return-1;S=(linklist)malloc(sizeof(listnode));S->data=e;S->next=p->next;P->next=s;Return1;}●2.3.3线性链表的基本运算5.链表中删除结点在顺序表中删除算法需考虑问题：(1)如果需ai，应先返回ai的值(2)检查要删除位置的有效性，1≤i≤n(3)当表空时不能做删除(4)移动元素时是整体自上而下的顺序(5)length值减1；在链表中删除算法需考虑问题：(1)如果需ai，应先返回ai的值(2)检查要删除位置的有效性，1≤i≤n(3)当表空时不能做删除(4)不需要移动元素(5)不需要设Length值(6)删除的结点空间用free释放设s指向单链表中某个结点，删除s，首先要找到s的前驱结点p，指针操作由下：p->next=s->next;free(s);a1ai+1an∧headai-1ai……p●2.3.3线性链表的基本运算s删除链表中第i个结点的基本步骤如下：①找到第i-1个结点；若存在，继续进行，否则结束。②若存在第i个结点，则继续③，否则结束。③删除第i个结点，结束。●2.3.3线性链表的基本运算删除链表中第i个结点的算法如下：int

del_LinkList(LinkList

pList,inti){Listnode*p,*q;intj;p=pList;j=0;while((*p).next!=NULL&&j<i-1){p=(*p).next;++j;}if((*p).next==NULL||j>i-1)returnERROR;q=(*p).next;(*p).next=(*q).next;free(q);returnOK;}●2.3.3线性链表的基本运算通过前面的基本操作：⑴在单链表上插入、删除结点，必须知道其前驱结点。⑵单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。●2.3.3线性链表的基本运算练习：已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接后继结点的语句序列是—b.删除P结点的直接前驱结点的语句序列是__c.删除P结点的语句序列是_____d.删除首元结点的语句序列是______e.删除尾元结点的语句序列是______P=P—>next;P—>next=P;P—>next=P—>next—>next;P=P—>next—>next;While(P!=NULL)P=P—>next;While(Q—>next!=NULL){P=Q;Q=Q—>next；}(7)While(P—>next!=Q)P=P—>next;(8)While(P—>next—>next!=Q)P=P—>next;(9)While(P—>next—>next!=NULL)P=P—>next;(10)Q=P;(11)Q=P—>next;(12)P=L;(13)L=L—>next;(14)free(Q);由此可知：要删除的结点为Q结点练习：a.删除P结点的直接后继结点的语句序列是—

（11）（3）（14）b.删除P结点的直接前驱结点的语句序列是__(10)(12)(8)(11)(3)(14)c.删除P结点的语句序列是_____(10)(12)(7)(3)(14)d.删除首元结点的语句序列是______(12)(10)(11)(3)(14)e.删除尾元结点的语句序列是______(9)(11)(3)(14)或(10)/(11)(6)(3)(14)简述下列算法的功能

int

A(LinklistL)L为不带头结点的链表

{if(L&&L—>next){Q=L;L=L—>next;P=L;while(P—>next)P=P—>next;P—>next=Q;Q—>next=NULL;}return(1);}如果L的长度不小于2，则将首元结点删掉并插入到表尾。对于线性链表，可以从头指针(head)开始，沿各结点的指针扫描到链表中的所有结点。创建单链表无论对链表进行何种运算，第一步必须建立该线性表链式存储结构(即链表)，然后再对该链表进行需要的运算。链表的建立要经过以下步骤进行：算法设计初始状态，头指针head=NULL，尾指针r=NULL。按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到当前链表的表尾，直到读入结束标志。●2.3.3补充⑴在链表的头部插入结点建立单链表链表与顺序表不同，是一种动态管理存储结构。链表中的每个结点占用的存储空间不是预先分配，而是需要时生成的，因此建立单链表需从空表开始，每读入一个数据元素申请一个结点，然后插入在链表头部（头指针指向新结点）。例：建立线性表（35,47,28,86,79）●2.3.3补充35∧∧4728867935∧4735∧284735∧86284735∧在链表头部插入建立单链表●2.3.3补充建立单链表算法１

LinkListCreat_LinkList1(){LinkListL;

ListNode*p;

inta;

intflag;L=NULL;

scanf(“%d”,&a);while(a!=flag){p=(Lnode*)malloc(sizeof(Lnode));p->data=a;p->next=L;L=p;

scanf(“%d”,&a);}returnL;}●2.3.3补充⑵在单链表的尾部插入结点建立单链表在头部插入建立单链表简单，但读入的数据顺序与生成链表中元素的顺序相反，若希望次序一致，则用在尾部插入结点的方法。例：建立线性表（35,47,28,86,79）算法分析初始状态，头指针head=NULL，尾指针rear=NULL。按线性表中元素的顺序依次读入数据，不是结束标志时，申请结点，将新结点插入到rear所指结点后面，rear指向新结点。●2.3.3补充35∧∧3535353547∧4728∧472886∧47288679∧在链表尾部插入建立单链表headheadheadheadheadheadrearrearrearrearrearrear●2.3.3补充建立单链表算法２

LinkListCreat_LinkList2(){LinkListL;

ListNode*p,*rear;

inta;

intflag;L=rear=NULL;

scanf(“%d”,&a);while(a!=flag){p=(Lnode*)malloc(sizeof(Lnode));p->data=a;if(L==NULL)L=p;

/*处理第一个结点*/elserear->next=p;

/*其它结点的处理*/rear=p;

/*指向新的尾结点*/

scanf(“%d”,&a);}if(rear!=NULL)rear->next=NULL;returnL;}●2.3.3补充循环链表是另一种形式的链表结构。即将最后一个结点的指针域指向链表表头结点，使得链表头尾相连，就构成了单循环链表。在循环链表中，从表中的任意结点出发均可找到表中的其它结点。其操作基本与非循环链表相同，只是将原来判断指针是否为NULL改为是否指向头结点。head●2.3.4循环链表及运算a1a2anhead…a1a2an…head对于单链表，只能从头结点开始遍历整个链表，而对于单循环链表，则可以从表中任意结点开始遍历整个链表。不用头指针，改用指向尾结点的指针rb来标识，可以提高操作效率。例对两个单循环链表L1、L2的连接操作，是将L2的第一个结点接到L1的尾结点，若用头指针标识，则需要找到第一个链表的尾结点，时间复杂度为O(n)，若用尾指针ra、rb标识，则时间复杂度为O(1)，算法如下：●2.3.4循环链表及运算单循环链表的连接

LinkList

connect(LinkList

ra,rb){ListNode*p;p=ra->next;

ra->next=rb->next->next;

free(rb->next);

rb->next=p;

return(rb);}……●2.3.4循环链表及运算单链表的结点中只有一个指向其后继结点的指针域next。若已知某结点的指针p，其后继结点的指针则为p->next，而查找其前驱结点只能从该链表的头指针开始，顺着各结点的next域进行，即查找后继结点的时间复杂度为O(1)，查找前驱结点的时间复杂度为O(n)。如果也希望找前驱的时间复杂度为O(1)，则只能付出空间的代价，每个结点再加一个指向前驱的指针域，结点的结构如下：typedef

struct

dolnode{Elemtypedata;

struct

dolnode*prior,*next;}DulNode,*DulList;priordatanext●2.3.5双向链表及运算和单链表相似，双向链表通常也用头指针标识，也可以带头结点和做成循环结构。a1a2an…pheadhead●2.3.5双向链表及运算设p指向双向循环链表的某一结点，则表示*p结点之前驱结点的后继结点的指针，即与p相等。同样，表示*p结点之后继结点的前驱结点的指针，也与p相等，则

p->next->prior＝p->prior->next=p双向循环链表给运算带来的最大好处是可以很容易地找到结点的前驱和后继。在双向循环链表中查找一个结点，若该结点的序号i小于等于n/2，则可以从头指针开始，沿每个结点的next指针扫描，否则从尾指针开始，沿每个结点的prior指针扫描，平均每次访问n/4个结点，但是以增加每个结点的存储空间为代价。●2.3.5双向链表及运算在双向链表中插入结点操作：⑴s->prior=p->prior;⑵p->prior->next=s;⑶s->next=p;⑷p->prior=s;……px⑴⑵⑶⑷s●2.3.5双向链表及运算（4）放到最后面是最保险的请同学们写出当p指向第i-1个结点时的操作●2.3.5双向链表及运算算法：带头结点的双向链表L的第i个位置上插入值为x的元素。int

insert_DubList(DulList

L,int

i,Elemtypex){

if(!(p=GetElem_DuL(L,i)))returnERROR;if(!(s=(DulList)malloc(sizeof(DulNode)))returnERROR;s->data=x;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;return(1);}在双向链表中删除结点x…p⑴⑵操作：⑴p->prior->next=p->next;⑵p->next->prior=p->prior;⑶free(p);●2.3.5双向链表及运算●2.3.5双向链表及运算算法：删除双向链表L上的第i个数据结点。int

Del_DubList(DulList

L,inti){if(!(p=GetElem_DuL(L,i)))returnERROR;e=p->data;p->prior->next=p->next;p->next-<prior=p->prior;

free(p);return(1);}}●

2.4顺序表与链表的比较及应用举例2.4.1顺序表与链表的比较本章讨论了线性表的逻辑结构和两种存储结构：顺序表和链表。⒈顺序表的优点⑴方法简单，各种高级语言中都有数组，容易实现。⑵不用为表示结点间的逻辑关系增加额外的存储空间。⑶顺序表具有按元素序号随机访问的特点。⒉顺序表的缺点⑴做插入、删除时，平均移动一半元素，对n较大效率低。⑵需预先分配足够大空间，估计过大，大量闲置，分配过小，造成溢出。●2.4.1顺序表与链表的比较⒊链表的优点⑴对线性表的插入、删除不需要移动数据。⑵每个结点动态分配存储空间，不会出现大量存储空间空闲。⒋链表的缺点⑴因为不要求逻辑上相邻的元素物理上也相邻，所以必须为表示结点间的逻辑关系增加额外的存储空间。⑵因