if（L.data[i]==e）{
returni+1;//下标为i的元素值等于e，返回其位序i+1
}
return0;//退出循环，说明查找失败
}
最好情况：
查找的元素就在表头，仅需比较一次，时间复杂度为O
（1）。
最坏情况：
查找的元素在表尾（或不存在）时，需要比较n次，时间复杂度为O（n）。
因此，线性表按值查找算法的平均时间复杂度为O（n）。
（4）按下标查找、随机访问。
给定下标之后（或给定取第几个元素）可以直接通过下标访问l.data[i]，l.data[i-1]；因此随机访问的时间复杂度为O
（1）。
2.4线性表的链式表示
顺序表的插入产出操作需要移动大量元素，而链式存储时不要求逻辑上相邻的元素物理上也相邻，插入删除操作时不需要移动元素，而只需要修改指针即可。
虽然提高了插入删除的效率，但也失去了随机存取的优点。
2.4.1单链表定义
typedefstructLNode{//定义单链表结点类型
ElemTypedata;//数据域
structLNode*next;//指针域
}LNode,*LinkList;//类型定义
利用单链表可以解决顺序表需要大量的连续存储空间的缺点，但是单链表附加指针域，也存在浪费存储空间的缺点。
由于单链表的元素是离散地分布在存储空间中的，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。
查找某个特定的结点时，需要从头开始遍历，依次查找。
通过“头指针”来标识一个单链表，不同的教材有两种标识方式，一种不带头结点的单链表，一种带头结点的单链表。
不带头结点的单链表，第一个结点为NULL时代表空表，带头结点的单链表，L->next=NULL时表示一个空表。
带头结点的单链表头结点的指针域指向线性表的第一个元素结点，如下图：
头结点和头指针的区分：
不管带不带头结点，头指针始终指向链表的一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。
引入头结点后，可以带来两个优点：
（1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。
（3）头结点的数据域不设任何信息，也可以记录表长等相关信息。
2.4.2单链表的基本操作
（1）头插法建立单链表
该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
采用头插法建立单链表，读入数据的顺序与生成的链表中元素的顺序是相反的。
//从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
LinkListCreateList1（LinkList&L）{
LNode*s;
intx;
L=（LinkList）malloc（sizeof（LNode））;//创建头结点
L->next=NULL;//初始为空链表
scanf（"%d",&x）;//输入结点的值
while（x!
=9999）{//输入9999表示结束
s=（LNode*）malloc（sizeof（LNode））;//创建新结点
s->data=x;
s->next=L->next;//将新结点插入表中，L为头指针
L->next=s;
scanf（"%d",&x）;
}
returnL;
}
（2）尾插法
头插法生成的链表中结点的次序和输入数据的顺序不一致。
若希望两者次序一致，可采用尾插法。
该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。
尾插法逻辑上更好理解。
//从表头到表尾正向建立单链表L，每次均在表尾插入元素
LinkListCreateList2（LinkList&L）{
intx;//设置元素类型为整型
L=（LinkList）malloc（sizeof（LNode））;
LNode*s,*r=L;//r为表尾指针
scanf（"%d",&x）;//输入结点的值
while（x!
=9999）{//输入9999表示结束
s=（LNode*）malloc（sizeof（LNode））;
s->data=x;
r-next=s;
r=s;//r指向新的表尾结点
scanf（"%d",&x）;
}
r->next=NULL;//尾结点指针置空
returnL;
}
（3）按值查找结点
//本算法直接查找单链表L（带头结点）中数据域值等于e的结点指针，否则返回NULL
LNode*LocateElem（LinkListL,ElemTypee）{
LNode*p=L->next;
while（p!
=NULL&&P->data!
=e）{//从第1个结点开始查找data域为e的结点
p=p->next;
}
returnp;//找到返回该结点指针，否则返回NULL
}
（4）链表插入
实现插入结点的代码片段如下：
第一步：
p=GetElem（L,i-1）//查找插入位置的前驱结点
第二步：
s->next=p->next;//上图中的操作步骤1
第三步：
p->next=s;//上图中的操作步骤2
扩展：
对某结点进行前插操作。
前插操作是指在某结点的前面插入一个新结点，后插操作的定义刚好与之相反，在单链表插入算法中，通常都是采用后插算法的。
通常的做法是，插入到后面，然后交换结点的值。
这种思想在删除时也常用，删除下一个交换节点值。
//将*s结点插入到*p之前的主要代码片段
s->next=p->next;//修改指针域，不能颠倒
p->next=s;
temp=p->data;//交换数据域部分
p->data=s->data;
s->data=temp;
小总结：
先把申请的空间插入进去，然后交换一下数据域部分。
（5）删除操作
假设结点*p为找到的被删除结点的前驱结点，为了实现这一操作后的逻辑关系的变换，仅需要修改*p的指针域，即将*p的指针域next指向*q的下一个结点。
//实现删除结点的代码片段如下：
p=GetElem（L,i-1）;//查找删除位置的前驱结点
q=p->next;//令q指向被删除结点
p->next=q->next;//将*q结点从链中“断开”
free（q）;//释放结点的存储空间。
扩展：
删除结点*p
要实现删除某一给定结点*p，通常的做法是先从链表的头结点开始顺序找到其前驱结点，然后再执行删除操作即可，算法的时间复杂度为O（n）。
其实，删除结点*p的操作可以用删除*p的后继结点操作来实现，实质就是将其后继结点的值赋予其自身，然后删除后继结点，也能使得时间复杂度为O
（1）。
q=p->next;//令q指向*p的后继结点
p->data=p->next->data;//用后继结点中的数据覆盖要删除结点的数据
p->next=q->next;//将*q结点从链中“断开”
free（q）;//释放后继结点的存储空间
2.4.3双向链表定义
单链表结点中只有一个指向其后继的指针，这使得单链表只能从头结点依次顺序地向后遍历。
若要访问某个结点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O
（1），访问前驱结点的时间复杂度为O（n）。
为了克服单链表的删除缺点，引入了双向链表，双向链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。
双链表中结点类型的描述如下：
typedefstructDNode{//定义双链表结点类型
ElemTypedata;//数据域
structDNode*prior,*next;//前驱和后继指针
}DNode,*DLinkList;
双链表仅仅是在单链表结点中增加了一个指向其前驱的prior指针，因此，在双链表中执行按值查找和按位查找的操作和单链表相同。
但双链表在插入和删除操作的实现上，和单链表有着较大的不同。
这是因为“链”变化时也需要对prior指针做出修改，其关键在于保证在修改的过程中不断链。
此外，双链表可以很方面地找到其前驱结点，因此不管前插入、后插入、前删除、后阐述，算法的时间复杂度均为为O
（1）。
（1）插入操作
第一步：
s->next=p->next;//将结点*s插入到结点*p之后
第二步：
p->next->prior=s;
第三步：
s->prior=p;
第四步：
p->next=s;
上面的代码的语句顺序不是唯一的，但也不是任意的，第一步和第二步必须在第四步之前，否则*p的后继结点的指针就丢掉了，导致插入失败。
（2）删除操作
删除双链表中结点*p的后继结点*q，其指针的变化过程如下图：
删除操作的代码片段如下：
p->next=q->next;//上图中的第一步
q->next->prior=p;//上图中的第二步
free（q）;//释放结点空间
2.4.4循环单链表
循环单链表和单链表的区别在于，表中最后一个结点指针不是NULL，而改为指向头结点，从而整个链表形成了一个环，如下图所示：
在循环单链表中，表尾结点*r的next域指向L，故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。
在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任一结点开始遍历整个链表。
有时对单链表常做的操作是在表头和表尾进行的，此时可以对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高。
其原因是若设的是头指针，对表尾进行操作需要O（n）的时间复杂度，而如果设的是尾指针r，r->next即为头指针，对于表头与表尾进行操作都只需要O
（1）的时间复杂度。
2.4.5循环双向链表
由循环单链表的定义不难推出循环双链表，不同的是在循环双链表中，头结点的prior指针还要指向表尾结点，如下图所示：
在循环双链表L中，某结点*p为尾结点时，p->next==L;当循环双链表为空表时，其头结点的prior和next域都等于L。
2.4.6静态链表
静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称为游标。
和顺序表一样，静态链表也要预先分配一块连续的内存空间。
静态链表和单链表的对应关系如下图：
静态链表结构类型的描述如下：
#defineMaxSize50//静态链表的最大长度
typedefstruct{//静态链表结构类型的定义
ElemTypedata;//存储数据元素
intnext;//下一个元素的数组下标
}SLinkList[MaxSize];
静态链表以next==-1作为其结束的标志。
静态链表的插入、删除操作与动态链表相同，
只需要修改指针，而不需要移动元素。
总体来说，静态链表没有单链表使用起来方便，但是在一些不支持指针的高级语言（如Basic）中，这又是一种非常巧妙的设计方法。
顺序表和静态链表的物理结构（即存储结构）是相同的，在计算机内存中以数组的形式实现，是用一组地址连续的存储单元依次存储数据元素的线性结构，但两者的数据结构（逻辑结构）是不同的。
静态链表不是顺序结构，这里的结构指的是逻辑结构，在逻辑结构层面，静态链表是链式结构。
在物理层面，都采用顺序形式保存数据，因此物理结构、存储结构与线性表的顺序存储相同。
2.5顺序表和链表的比较（数组与链表）
（1）存取方式
顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。
（2）逻辑结构和物理结构
采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相邻。
而采用链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻，其对应的逻辑关系是通过指针链接来表示的，静态链表也是链式存储方式。
注意区别存取方式和存储方式，存取方式指的插入删除。
（3）查找、插入和删除操作
对于按值查找，当顺序表在无序的情况下，两者的时间复杂度均为O（n）;而当顺序表有序时，可采用折半查找，此时时间复杂度为O（lgN）。
对于按序号查找，顺序表支持随机访问，时间复杂度为O
（1），而链表不支持随机访问，只能遍历链表，其平均时间复杂度为O（n）。
顺序表的插入、删除操作，平均需要移动半个表长的元素。
链表的插入、删除操作，只需要修改相关结点的指针域即可。
由于链表每个结点带有指针域，因而在存储空间上比顺序存储要付出较大的代价，存储密度不如顺序存储。
（4）空间分配
顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，如果再加入新元素将出现内存溢出，需
升级会员 