channed list

线性表的链式表示和实现

链式存储结构
- 结点在存储器中的位置是任意的，逻辑上相邻的元素在物理上并不一定相邻
线性表的链式表示又称为非顺序映像或链式映像
链表的分类：单链表、双链表、循环链表:

结点只有一个指针域的链表，称为单链表和线性链表

结点有两个指针域的链表，称为双链表(一个指向后继一个指向前驱)

首尾相接的链表称为循环链表

头指针、头结点和首元结点：

头指针：指向链表中第一个结点的指针

首元节点：链表中存储第一个数据元素a1的结点

头结点：链表首元结点之前附设的一个结点

以上，链表可以分为带头结点的和不带头结点的链表，如此可以引发一些讨论：

如何表示空表？

无头结点时，头指针为空则表示空表；有头结点时，头结点的指针域为空时为空表

在链表中设置头结点有什么好处？

便于对首元结点的处理：
首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一样，无需进行特殊处理

便于空表和非空表统一处理
无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了

头结点的数据域内装的是什么？

可以为空也可以为表长度等附加信息，但此结点不能计入链表的长度值

单链表的定义和表示（带头结点）

单链表由表头唯一确定，因此单链表可以用头指针的名字来命名，比如头指针的名字为L，则把链表称为表L
结点的定义：

typedef struct Lnode{
    ElemType data;
    struct Lnode *next;
}Lnode, *LinkedList
//定义一个列表
LinkList L;     //头指针可以唯一地确定一个链表
Lnode *p;       //定义结点指针p,也可写成LinkList p

为了统一链表的操作，通常给一下定义：

typedef struct{
    //数据域
    //数据域
    //数据域
}ElemType;

tydedef struct Lnode{
    ElemtType data;
    struct Lnode *next;
}Lnode, *LinkList;

通用算法中预定义了一些常量和类型作为函数结果状态的表示，如下：

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0 
#define INFEASIBLE -1
#define OVERFLOW -2

// Status是函数的类型，其值是函数结果状态值，
typedef int Status
typedef char Elemtype

单链表的初始化（带头结点的单链表）

算法思路：

为头结点分配存储空间，初始化头指针
将头结点的next成员变量置为空

Status InitList_L(LinkList &L)  //C语言中用二级指针
{
    L = new Lnode;   //L = (LinkList)malloc(sizeof(Lnode))
    L -> next = NULL;
    return OK;
}

C语言代码参考如下：

Status InitList_L(LinkList *L)  //L是一个二级指针
{
    (*L) = (LinkList)malloc(sizeof(Lnode));
    (*L) -> next = NULL
    return OK;
}

额外补充简单算法：

判断链表是否为空

算法思路：判断头结点的指针域是否为空

int ListEmpty(LinkList *L)  //L是头指针的二级指针
{
    if((*L) -> next)        //非空
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

单链表的销毁

算法思路：从头指针开始，依次释放所有结点

Status DestroyList(Li nkList *L) //L是头结点的二级指针
{
    LinkList P;
    for(;(*L) != NULL;)
    {
        p = (*L);
        (*L) = (*L) -> next;
        free(p);
    }
    return OK;
}

单链表的清空

算法思路：依次释放所有结点，并将头结点指针域设置为空

Status ClearList(LinkList *L)
{
    Lnode* p, q;
    p = (*L) -> next;
    for(;q;)
    {
        q = p -> next;
        free(p);
        p = q;
    }
    (*L) -> next = NULL;
    return OK;
}

求单链表的表长

算法思路：从首元结点开始，依次计数所有结点

int GetLength(LinkList *L)
{
    int i = 0;
    Lnode *q = (*L);
    for(;q -> next != NULL;)
    {
        q = q -> next;
        i++
    }
    return i;
}

单链表的取值(取单链表的第i个元素)

算法思路：顺序存取

bool ListInsert(Sqlist &L, int i, Elemtype e){
    if(i<1 || i>L.length+1)
        return false;
    if(L.length >= Maxsize)
        return false;
    for(int j = L.length; j>=i; j--)
        a[j] = a[j-1];
    L.data[i-1] = e;
    L.length++;
    return true;
}