3_bg
书山有路勤为径，学海无涯苦作舟。

线性表包含的内容：

一、线性表的定义

零个或多个数据元素的有限序列。

二、线性表的顺序存储结构

用一段的地址连续的存储单元依次存储线性表的数据元素。

三、顺序存储结构的插入与删除

1、插入算法的思路

如果插入位置不合理，抛出异常；
如果线性表长度大于等于数据长度，抛出异常或动态增加容量；
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
将要插入元素填入位置i处；
表长加1。

2、删除算法的思路

如果删除位置不合理，抛出异常；
取出删除元素；
从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
表长减1。

3、线性表顺序存储结构的优缺点

优点:

无须为表示表中元素之间的逻辑关系而增加额外的存储空间；
可以快速地存取表中任一位置的元素。

缺点:

插入和删除操作需要移动大量元素；
当线性表长度变化较大时，难以确定存储空间的容量；
造成存储空间“碎片”。

四、线性表的链式存储结构

顺序存储结构有一个大缺点，就是插入和删除的时候需要移动大量元素，这显然耗费时间。而链式存储结构是一个很好的解决办法。

为了表示每个元素a(i)与其直接后继数据元素a(i+1)之间的逻辑关系，对数据元素a(i)来说，除了存储其本身的信息外，还需要存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。把这两部分信息组成数据元素a(i)的存储映像称为结点。

n个结点链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

链表的第一个结点的存储位置叫做头指针。
在单链表的第一个结点前附设一个节点，称为头结点。头结点不存储任何信息。

1、头指针与头结点的异同

头指针：

是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针；
具有标识作用，所以常用头指针冠以链表的名字；
无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点

是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）；
有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了；
头结点不一定是链表的必须要素

五、单链表的读取

1、获得链表中第i个数据的算法思路

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

2、实现代码

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：用e返回L中第i个数据元素的值
Status GetElem(LinkList L,int i,ElemType *e){
        int j;
        LinkList p;
        p = L->next;
        j = 1;
        while(p && j<i)    //p不为空或者j还没等于i时，循环继续
        {
                p = p->next;
                ++j;
       }
        if(!p || j>i)
                return ERROR；
        *e = p ->data;
        return OK;
}

六、单链表的插入和删除

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

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

2、单链表第i个数据插入结点的代码实现

Status ListInsert(LinkList *L, int i, ElemType e){
        int j;
        LinkList p,s;
        p = *L;
        j = 1;
        while( i && j < i){
                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;
}

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

声明一结点p指向链表第一个结点，初始化j从1开始；
当j <i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
若到链表末尾p为空，则说明第i个元素不存在；
否则查找成功，将欲删除的结点p->next赋值给q；
单链表的删除标准语句p->next = q->next;
将q结点中的数值赋值给e，作返回；
释放q结点；
返回成功

4、单链表第i个数据删除结点的代码实现

Status ListDelete(LinkList *L, int i, ElemType *e){
    int j;
    LinkList p , q;
    p = *L;
    j = 1;
    while(p -> next && j < i){
        p = p ->next;
        ++j;
   }
    if(!(p ->next) || j > i)
        return ERROR；
q = p ->next;
p ->next = q->next;
*e = q ->data;
free(q);
return OK;
}

七、单链表的整表创建

##１、整表创建思路

声明一结点p和计数器变量i；
初始化以空链表L；
让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
循环；
1、生成一新结点赋值给p；
2、随机生成一数字赋值给p的数据域p->data;
3、将p插入到头结点与前一新结点之间。

2、代码实现

void CreateListHead(LinkList * L,int n){
    LinkList p,r;
    int i;
    srand(time(0));    //初始化随机数种子
    * L = (LinkList)malloc(sizeof(Node));
    r = *L;
    for(i = 0; i<n; i++){
        p = (Node * )malloc(sizeof(Node));
        p ->data = rand()%100 + 1; //随机生成100以内的数字
        r- > next = p;
       r = p;
   }
   r->next = Null;   
}

八、单链表的整表删除

1、算法思路

声明一结点p和q；
将第一个结点赋值给p；
循环
1、将下一结点赋值给q；
2、释放p；
3、将q赋值给p。

2、实现代码

Status ClearList(LinkList *L){
   LinkList p,q;
   p = (* L) - >next;
    while(p){
        q = p -> next;
        free(p);
        p = q;
   }
    (* L) - > = NULL;
    return 0K;
}

九、单链表结构与顺序存储结构的优缺点

1、存储分配方式

顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；
单链表才用链式存储结构，用一组任意的存储单元存放线性表的元素

2、时间性能

查找
1、顺序存储结构O（1）
2、单链表O（n）
插入与删除
1、顺序存储结构需要平均移动表长一般的元素，时间为O（n）
2、单链表在找出某位置的指针后，插入和删除时间仅为O（1）
空间性能
1、顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢出
2、单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

十、静态链表

让数组的元素都是由两个数据域组成，data和cur，data存放数据元素，游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。这种用数组描述的链表叫做静态链表，这种描述方法叫游标实现法。

1、静态链表的插入操作

静态链表中需要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

在静态链表中，因为操作的是数组，数组是不存在像动态链表的结点申请和释放的，所以我们需要实现两个函数才可以做插入和删除操作，为了分辨数组中哪些分量未被使用，解决的方法是把未使用过即已被删除的游标链成一个备用链表，每当插入时，从备用链表上取第一个结点作为待插入的新结点。

int Malloc_SLL(StaticLinkList space){
    int i = space[0].cur;        //拿出备用分量的下标
    if(space[0].cur){
            space[0].cur = space[i].cur;    //数组中的下一个分量用来当备用分量
   }
    return i;
}

静态链表的插入操作的思路：
假设有新元素丙，要插入到乙丁之间。

获取空闲分量下标，放置丙元素；
通知丙元素下标改为乙元素下标。
通知乙元素下标改为放置丙元素的空闲分量的下标；

/* 在 L 中第 i 个元素之前插入新的数据元素 e */  
Status ListInsert(StaticLinkList L,int i;ElemType e){
    int j , k , l ;
    k = MAX_SIZE - 1；    //k是最后一个元素下标
    if(i < 1 || i > ListLength(L) + 1)
        return ERROR；
    j = Malloc_SSL(L);        //获取空闲的分量
    if(j){
        L(j).data = e;
        for(l = 1; l<= i - 1 ; l++){
            k = L[k].cur;        //k=999时，L[999].cur=1;再L[1]=2;直到获取到第i个元素之前的位置下标
       }
       L[j].cur = L[k].cur;
       L[k].cur = j;
       return OK;
   }
    return ERROR；
}

2、静态链表的删除操作

大体操作上与插入的类似，在删除元素时，需要回收结点到空闲链表的存放

Status ListDelete(StaticLinkList L,int i){
    int j, k ;
    if(i < 1 || i > ListLength(L)){
        return ERROR；
   }
    k = MAX_SIZE - 1；
    for(j = 1; j <= i - 1; j++){
        k = L[k].cur;
   }
    L[k].cur = L[j].cur;
    Free_SSL(L , j);
    return OK;
}

//将下标为k的空闲结点回收到备用链表
void Free_SSL(StaticLinkList space, int k){
        space[k].cur = space[0].cur;
        space[0].cur = k;
}

//获取L中数据元素个数
int ListLength(StaticLinkList){
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while(i){
        i = L[i].cur;
        j++:
   }
    return j;
}

3、静态链表的优缺点

优点

在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

缺点
1、没有解决连续存储分配带来的表长难以确定的问题；
2、失去了顺序存储结构随机存取的特性

十一、循环链表

将单链表中终端结点的指针端由空指针改为指针头结点，就使整个单链表形成一个环，这种头尾相接的单链表成为单循环链表，简称循环链表（circular linked）。

非空循环链表如下图所示。

循环链表和单链表的主要差异在于循环的判定条件，原来是判定p ->next是否为空，现在是p ->next不等于头结点来判定循环未结束。

十二、双向链表

双向链表是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

非空的循环的带头结点的双向链表如下图所示。

把结点s插入到p结点和p->next之间的几个步骤如下:

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

删除p结点

1
2
3

p->prior->next = p->next;
p->next->prior = p>prior;
free(p);