北京治疗白癜风哪里医院好 http://pf.39.net/bdfyy/bjzkbdfyy/第二章：线性表（链式表示）
学习数据结构--第二章：线性表(顺序存储、插入、删除)这篇文章讲到线性表的顺序表示也就是顺序表，顺序表虽然可以随机存储，但是在初始化的时候需要申请一大块连续的存储空间，且在执行插入和删除操作时，也需要大量的移动元素，时间复杂度比较高，下面讲线性表的另一种存储结构：链式存储
1.单链表的定义
线性表的链式存储又称：单链表，通过一组任意的存储单元来存储线性表中的数据元素。
数据元素存储在任意位置，不一定连续，通过指针实现线性逻辑关系。
我们把单链表中这样数据加地址的组合叫做单链表的一个结点，一个结点存储数据元素的数据域和下一个结点(数据元素)的地址的指针域组成。
单链表有两种创建方式
无头结点的单链表有头节点的单链表
有头节点的单链表，它的头节点的数据域一般不存储数据，它的指针域存储第一个结点的地址。优点：
链表的第一个位置和其他位置的操作统一(比如插入操作：无头节点的链表，在表中插入结点的时候两边都有结点，而在表头插入结点的时候左边是没有结点的，而有头节点就都是一样的。)空表和非空表的操作统一在这里插入图片描述2.单链表的基本操作2.1头插法建立在这里插入图片描述
//头插法LinkListList_HeadInsert(LinkListL){LNode*s;intx;L=(LinkList)malloc(sizeof(LNode));L-next=NULL;scanf("%d",x);while(x!=){s=(LNode*)malloc(sizeof(LNode));s-data=x;s-next=L-next;L-next=s;scanf("%d",x);}returnL;}
时间复杂度：O(n)
2.2尾插法建立在这里插入图片描述
LinkListList_TailInsert(LinkListL){intx;L=(LinkList)malloc(sizeof(LNode));LNode*s,*r=L;//注意这里重新定义一个指针r，作为尾指针，同时初始化为了头节点scanf("%d",x);while(x!=){s=(LNode*)malloc(sizeof(LNode));s-data=x;r-next=s;r=s;//修改尾指针，指向新插入的结点scanf("%d",x);} r-next=NULL; returnL;}
时间复杂度：O(n)
2.3按序号查找按值查找
按照和按序号查找都要遍历单链表。
按序号查找
LNode*GetElem(LinkListL,inti){intj=1;//标识当前结点的序号LNode*p=L-next;//当前所查找的结点，初始化为头节点的下一个结点，因为头节点不保存数据if(i==0){//序号不合法returnL;}if(i1){//序号不合法returnNULL;}while(pji){//当结点不为空，且序号小于j的时候,继续循环p=p-next;j++;}returnp;}
时间复杂度：O(n)
按序值查找
LNode*LocateElem(LinkListL,ElemTypee){//初始化一个指针指向头节点的下一个结点LNode*p=L-next;//判断结点不为空，且数据不为ewhile(p!=NULLp-data!=e){//如果结点不为空，且值不为e，则指针继续向下移动p=p-next;}returnp;}
时间复杂度：O(n)
2.4插入结点
插入有两种方式，前插法和后插入法，比如插入位置为i,前插法就是在i的位置之前插入,后插法就是在i的位置之后插入，所以前插法要找i-1位置，而后插法要找i的位置。所以如果i的位置是已知的，这样两种方法就会产生区别，前插法仍然需要遍历链表O(n)，而后插法直接使用这个位置即可O(1)。后插法是可以实现前插法的，插入之后交换两个结点的位置即可。下面演示前插法：
插入结点首先要知道插入的位置，假如插入位置为i，则需要知道i-1结点的位置。接着修改新结点的指针指向i-1结点的下一个位置，然后修改i-1结点的指针指向新插入结点。
注意下面的代码，不能交换位置。
s-next=p-next;p-next=s;
why???这个顺序是不能交换的，如果交换会出现i结点地址丢失的问题。p-next=s;这时已经将p结点中存储的i结点的地址给覆盖了，成了新结点的地址，接着再s-next=p-next;这相当于讲s结点的指针指向了他自己。这样就把后面的链表给丢弃了。
2.5删除结点
结点的位置未知
假如要删除链表中第i号结点的位置，修改第i-1号结点的指针，让其指向第i+1号结点的位置。这是要注意要使用一个指针指向第i个结点，因为修改之后我们会失去第i个结点的位置，这样后面就无法释放i结点的空间。
结点的位置已知*p
这时可以先交换p结点和后一个结点的数据，然后删除后一个结点即可，注意要有一个指针指向后一个结点，方便之后释放空间。
在这里插入图片描述2.6求表长
有头节点和无头节点的链表判断是不一样的。
3.特殊链表3.1双链表
在使用单链表的时候，我们知道当前结点i的指针，在执行插入，删除等需要知道它的前驱结点的操作，我们需要通过按序号查找的方式查找到他的前驱结点。这样时间复杂度是O(n)。
在这里插入图片描述
如果节点中有一个直接指向它的前驱结点的指针，那么我们就可以直接找到它的前驱节点了。所以这样就出现了双链表。
3.1双链表插入操作
前插法和后插法的时间复杂度都是O(1)。这个插入顺序是可以调的，但是第一个和第二步，必须在第四步之前，因为第二步我们需要i+1结点的位置。
在单链表中，在表头、表中和表尾的插入步骤相同。但是注意在双链表中，在表头和表中跟在表尾插入是不一样的步骤。在双链表的表尾进行插入的时候要注意表尾后面没有下一个结点，所以不能修改下一个结点指向前驱的指针，否则会出现错误。
3.1双链表删除操作
首先找到要删除的结点(q)的前驱结点的指针，设为p，接着直接修改指针，释放空间即可。时间复杂度为O(1)。同样在表尾进行删除的时候也是不一样的。
3.2循环链表3.2.1循环单链表
假设我们使用单链表，我们只知道尾指针，但是需要知道头指针，这时候是无法知道的。这是如果将单链表的最后一个结点的指针指向头节，这样就可以找到的头指针，这样的链表形成一个环，叫做循环单链表。这样就只设置一个尾指针就行了，而且效率更高：因为如果只有头指针，我们想找到尾指针，需要遍历单链表，但是如果有一个尾指针，我们找头指针直接就可以找到。在循环单链表插入和删除操作，在每一个位置都是一样。
在这里插入图片描述3.2.1循环双链表
我们需把链表最后一个结点的指针修改为头节点，且需要修改头节点的前驱指针指向最后一个结点。这时每一个位置的插入和删除操作都是一样。
3.2.3循环链表判空
我们发现在循环链表中，我们利用了每一个结点的指针，也就是说在循环链表中，没有空指针了，这时该怎么判空呢？？请看下图：
3.3静态链表
静态链表：就是使用数组来实现的链式存储结构的链表。
单链表：静态链表：
静态链表中每个结点既有自己的数据部分，还需要存储下一个结点的位置，所以静态链表的存储实现使用的是结构体数组，包含两部分：数据域和游标（存放的是下一个结点在数组中的位置下标）。
#defineMaxSize50typedefstructDNode{ElemTypedata;intnext;}SLinkList[MaxSize];理木客
支持一下？(???o??)
