前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

资料获取

单链表的读取

在线性表的顺序存储结构中，我们要计算任意-一个元素的存储位置是很容易的。但在单链表中，由于第i个元素到底在哪?没办法-开始就知道，必须得从头开始找。因此，对于单链表实现获取第i个元素的数据的操作GetElem,在算法上，相对要麻烦一些。

获得链表第i个数据的算法思路:

1.声明一个结点p指向链表第一个结点，初始化j从1开始; 2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j 累加1; 3.若到链表末尾p为空，则说明第i个元素不存在; 4.否则查找成功，返回结点p的数据。.

/*初始条件:顺序线性表L已存在，1≤i≤ListLength (L) */
/*操作结果:用e返回L中第i个数据元素的值*/
Status GetElem ( LinkList L,int i, ElemType*e) 
{
    int j;
  LinkList P; /*声明一结点 p*/
  P= L->next;   /*让p指向链表L的第一个结点*/
  j=1;  /*j为计数器*/
  while (p && j<i) /*p不为空或者计数器j还没有等于i时，循环继续*/
  {
    p= p->next; /*让p指向下一个结点*/
        ++j;
    }
  if (!pHI j>i )
    return ERROR; /*第i个元素不存在*/
  *e = p->data; /*取第i个元素的数据*/
  return OK;
}

说白了，就是从头开始找，直到第i个元素为止。由于这个算法的时间复杂度取 决于i的位置，当i=1时，则不需遍历，第一个就取出数据了，而当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度是O(n)。

由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是‘工作指针后移”， 这其实也是很多算法的常用技术。

单链表的插入与删除

单链表的插入

先来看单链表的插入。假设存储元素e的结点为s,要实现结点p、p->next 和s . 之间逻辑关系的变化，只需将结点s插入到结点p和p->next之间即可。可如何插入呢?

根本用不着惊动其他结点，只需要让s->next和p->next的指针做一点改 变即可。

s->next=p->next; p->next=s;

就是说让p的后继节节点改成s的后继节点，再把s变成p的后继节点

这段话需要多去体会，看不懂的可以再往前复习一下！很久好理解的

如果先p->next = s;再s->next= p->next行不行呢？

不行哦，因为第一句会使得p->next给覆盖成s的地址了。那么s->next = p->next，其实就等于s->next = s

这一点要是不懂的话一定要自己画个图，然后再写上过程

对于单链表的表头和表尾的特殊情况，操作是相同的

单链表第i个数据插入结点的算法思路:

1.声明一结点p指向链表第一个结点，初始化j从1开始; 2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一-结点，j累加1; 3.若到链表末尾p为空，则说明第i个元素不存在; 4.否则查找成功，在系统中生成-一个空结点s; 5.将数据元素e赋值给s->data; 6.单链表的插入标准语句s->next=p->next p->next=s; 7.返回成功。

代码实现：

#include <stdio.h>
/*初始条件:顺序线性表L已存在，1≤i≤ListLength (L)，
/*操作结果: 在L中第1个位置之前插入新的数据元素 e,L的长度加 1*/
Status ListInsert(LinkList *L, int i, ElemType e)
{
    int j;
    LinkList p, s;
    p = *L;
    j = 1;
    while (p && j < i)  //寻找第i个结点，通过让p指针一直向后指，直到找到目标元素为止
    {
        p = p->next;
        ++j;
    }
    if(!p || j > i)
        return ERROR;
    s = (LinkList)malloc(sizeof(Node));//生成新的结点
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

实际代码是执行不通的，主要是学习这个思想

核心思想就是工作指针后移

单链表的删除

删除结点只需要将删除结点的前驱指针绕过，指向它的后继结点即可

我们所要做的，实际上就是一步，p->next=p->next>next, 用q来取代p->next,即是

q = p->next;p->next=q->next

解读这两句代码，也就是说让p的后继的后继结点改成p的后继结点。

单链表第i个数据删除结点的算法思路

1.声明一结点p指向链表第一一个结点， 初始化j从1开始

2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点, j累加1

3.若到链表末尾p为空，则说明第i个元素不存在

4.否则查找成功，将欲删除的结点p->next赋值给q

5.单链表的删除标准语句p->next=q->next

6.将q结点中的数据赋值给e,作为返回

7.释放q结点

8.返回成功

代码实现

初始条件:顺序线性表L已存在，1≤i≤ListLength (L) 操作结果: 删除L中的第i个数据元素，并用e返回其值，L中的长度减1

Status ListDelete (LinkList *L, int i, ElemType *e)
{
    int j;
  LinkList p,q;
  P = *L;
    j = 1;
  while (p->next && j< i) /*遍历寻找第 i个元素*/
    {
        P = P->next;
    ++j;
    }
    if (!(p->next) || j > i)
    return ERROR; /*第i个元素不存在*/    
  q = p->next;
  p->next = q->next;  /*将q的后继赋值给p的后继*/
  *e= q->data;  /*将q结点中的数据给e*/
  free (q) ;  /*让系统回收此结点，释放内存*/
  return OK;
}

代码看不懂的，可以再回去画一遍图

分析一下刚才我们讲解的单链表插入和删除算法，我们发现，它们其实都是由两部分组成:第一部分就是遍历查找第i个元素;第二部分就是插入和删除元素。

从整个算法来说，我们很容易推导出:它们的时间复杂度都是O(n)。 如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置,插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是O(n)。 而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为0(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是0(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。