前言

为了克服顺序表的缺点，可以采用链式方式存储线性表。通常将采用链式存储结构的线性表称为线性链表。

在顺序表中，用一组地址连续的存储单元来依次存放线性表的节点，因此节点的逻辑顺序和物理顺序是一致的。而链表则不然，链表是用一组任意的存储单元来存放线性表的节点，这组存储单元可以是连续的，也可以是非连续的，甚至是零散分布和内存的任何位置上。

示意图

为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后续的地址信息，这两部分信息组成的存储映像称为结点（Node）

结点表示图

LinkListNode.PNG

结点包括两个域：数据域用来存储结点的值，指针域用来存储数据元素的直接后续的地址。

单链表中每个节点的存储地址存放在其前驱结点的指针域中，由于线性表中的第一个结点无前驱，所以应设一个头结点H指向第一个结点。由于线性表的最后一个结点没有直接后继，则指定单链表的最后一个结点的指针域为“空”（NULL）。这里称为H。在H结点的数据域中，我们可以存放整个表的长度值。那么一个单链表的存储示意图为

单链表表示图

我们理解的逻辑图：

LinkListExample.PNG

实际中可能的存储地址图：

LinkListAdd.PNG

线性表链式存储的表示

可以理解为将不同的地址连起来存储我们需要的值，用来节约内存空间，消除碎片。

1、定义一个节点（使用结构体）

LinkList.h

#ifndef _LINKLIST_H_
#define _LINKLIST_H_
typedef struct Node
{
    int data;
    Node *next;
}Node,*LinkList;

LinkList init(LinkList L);   //初始化表 
int length(LinkList L);   //得到总长度
int get_int(LinkList L,int loc);   //根据下标得到存储的值
void get_all(LinkList L);   //得到所有存储的值 
void add(LinkList L,LinkList element);   //新增
bool del(LinkList L,int loc);   //根据下标删除
bool update(LinkList L,int loc,int new_element);   //更新
bool empty(LinkList L);   //判断是否为空 
bool clear(LinkList L);   //清空表
LinkList destory(LinkList L);   //销毁表 
void insert(LinkList L,int loc,int element);   //插入数据 
 #endif

这里面我们首先定义了一个结构体作为节点，表示每个位置前面图中的结点，这里有两个内容，data是用来存放数据的（头结点中存放表长度），next表示下一个结点的地址（没有就为NULL），下面那些是我们需要完成的方法。

2、完成相应的方法

LinkList.cpp

#include <stdio.h>
#include "LinkList.h"
#include <malloc.h>

LinkList init(LinkList L)   //初始化表
{
    L = (LinkList)malloc(sizeof(Node));   //头指针 
    L->next = NULL;
    L->data = 0;
    printf("init success!!\n");
    return L;
}
int length(LinkList L)   //得到总长度
{
    return L->data; 
} 
int get_int(LinkList L,int loc)   //根据下标得到存储的值
{
    if(loc < 0 || loc > L->data-1)
    {
        printf("the loc don't exists!!\n");
        return -1; 
    }
    LinkList p = L;
    int i=0;
    while(p->next != NULL && i<=loc)
    {
        p = p->next;
        i++;
    }
    return p->data;
}
void get_all(LinkList L)   //得到所有存储的值 
{
    if(L->data == 0)
    {
        printf("the list is null\n");
        return;
    }
    
    LinkList p = L;
    while(p->next != NULL )
    {
        p = p->next;
        printf("%7d",p->data);
    }
}
void add(LinkList L,int data)   //新增
{
    LinkList element = (LinkList)malloc(sizeof(Node));
    element->data = data;
    element->next = NULL;
    
    LinkList p = L;
    while(p->next != NULL){
        p = p->next;
    }
    p->next = element;
    L->data++;
}
bool del(LinkList L,int loc)   //根据下标删除
{
     LinkList p = L,q;
     int i=0;
     while(p->next != NULL && loc > i)
     {
        p = p->next;
        i++;
     }
     q = p->next;
     p->next = q->next;
     q->next = NULL;
     q->data = NULL;
     q = NULL; 
     L->data--;
     printf("del success!\n");
     return true;
}
bool update(LinkList L,int loc,int new_element)   //更新
{
     LinkList p = L;
     int i=0;
     while(p->next != NULL && loc >= i)
     {
        p = p->next;
        i++;
     }
     p->data = new_element;
     return true;
}
bool empty(LinkList L)   //判断是否为空 
{
   if(L->data == 0 && L->next == NULL){
       printf("is empty!\n");
       return true;
   }
   return false;
}
bool clear(LinkList L)   //清空表
{
    LinkList p = L,q;
    int i=0;
    while(p->next != NULL)
    {
        p = p->next;
        p->data = NULL;
        L->data--;
        i++;
    }
    L->next = NULL;
    printf("total clear data is %4d",i);
    return true;
}
LinkList destory(LinkList L)   //销毁表
{
    clear(L);
    L = NULL;
    printf("destory Successed!!  \n");
    return L;
}
void insert(LinkList L,int loc,int data)   //插入数据 
{
   LinkList p=L,q;
   int i = 0;
   while(p->next != NULL && i<loc)
   {
       p = p->next;
       i++;
   }
   q = p->next;
   
   LinkList element = (LinkList)malloc(sizeof(Node));
   element->data = data;
   element->next = q;
   p->next = element;
}

3、运行查看结果

LinkListMain.cpp

#include <stdio.h>
#include "LinkList.cpp"
int main()
{
    LinkList L;
    L = init(L);
    empty(L);
    
    for(int i=0;i<15;i++)
    {
        add(L,i);
    }
    
    empty(L);
    printf("length is %d \n",length(L));
    printf("the 10 is %d \n",get_int(L,10));
    
    get_all(L);
    del(L,3);
    del(L,3);
    del(L,3);
    printf("length is %d \n",length(L));
    get_int(L,10);
    get_all(L);
    printf("\n");
    update(L,5,1000);
    insert(L,3,33333);
    get_all(L);
    clear(L);
    destory(L);
    return 0;
}

运行结果：

init success!!
is empty!
length is 15
the 10 is 10
      0      1      2      3      4      5      6      7      8      9     10     11     12     13     14
del success!
del success!
del success!
length is 12
      0      1      2      6      7      8      9     10     11     12     13     14
      0      1      2  33333      6      7   1000      9     10     11     12     13     14
total clear data is   13
total clear data is    0
destory Successed!!

--------------------------------
Process exited with return value 0
Press any key to continue . . .

链式表的优缺点

优点：新增和删除效率高
缺点：查找和修改效率低

这样，线性表的链式存储就了解完了，我们用自己写的这个来完成各小任务吧

题目1

有两个单链表LA和LB，其元素均为非递减有序排列，编写算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。例如，LA=(2,2,3)，LB=(1,3,3,4)，则LC=(1,2,2,3,3,4)。

算法分析

1、原来的两个都是非递减有序排列，也就是不需要我们排序了。
2、我们将下标从第一个结点开始，将LA和LB进行比较，小的先放入LC
，大的与另外的下一位比较，小的放入，依次进行下去。
3、最后将LA或者LB中多的放入LC中即可

实现

LinkList MergeLinkList(LinkList La,LinkList Lb,LinkList Lc)
{
    LinkList pa,pb,pc;
    pa = La->next;
    pb = Lb->next;
    Lc->data = La->data + Lb->data;
    pc = Lc;
    while(pa != NULL && pb != NULL)
    {
        if(pa->data <= pb->data)
        {
            pc->next = pa;
            pc=pc->next;
            pa = pa->next;
        }else{
            pc->next = pb;
            pc=pc->next;
            pb = pb->next;
        }
    }
    
    if(pa != NULL)
       pc->next = pa;
    else
       pc->next = pb;   
    return Lc;
} 

算法性能分析

时间复杂度为：O(n)，空间复杂度不考虑，题目有前提条件