3.线性表之链式存储结构（单链表）

//《大话数据结构》 相关代码
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status是函数的返回类型，其值是函数结果状态代码，如OK等

//3.6 线性表的链式存储结构
typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;
typedef struct Node *LinkList;

//3.7单链表的读取
//GetElem(L,i,*e);　  将线性表L中的第i个位置元素值返回给e
//初始条件：顺序线性表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还没有等于1时，循环继续
    {
        p=p->next;  //让p指向下一个结点
        ++j;
    }
    if(!p || j>i)
        return ERROR;   //第i个元素不存在
    *e=p->data;
    return OK;
}


//3.8单链表的插入与删除
//ListInsert(*L,i,e);　  在线性表L中的第i个位置插入新元素e
//初始条件：顺序线性表L已存在，1<=i <=ListLength(L)
//操作结果：在L中第i个位置之前插入新的数据元素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->next;
        ++j;
    }
    if(!p || j>i)
        return ERROR;   //第i个元素不存在
    s=(LinkList)malloc(sizeof(Node));    //生成新结点
    s->data = e;
    s->next=p->next;        //将p的后继结点赋给s的后继结点
    p->next=s;              //将p的后继结点赋给s
    return OK;
}

//ListDelete(*L, i, e) 单链表的删除算法
//初始条件：顺序线性表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;
    //遍历寻找第i-1个结点
    while(p->next && j < i)
    {
        p=p->next;
        ++j;
    }
    //第i个结点不存在
    if(!(p->next) || j > i)
        return ERROR;
    q=p->next;
    //将q的后继扶植给p的后继
    p->next=q->next;
    //将q结点中的数据给e
    *e=q->data;
    //让系统回收此结点，释放内存
    free(q);
    return OK;
}

//3.9单链表的整表创建
//头插法，随机产生n个元素的值，建立带表头节点的单链线性表L
void CreateListHead(LinkList *L, int n)
{
    LinkList p;
    int i;
    //初始化随机种子
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    //先建立一个带头结点的单链表
    (*L)->next = NULL;
    for(i=0; i<n; i++)
    {
        //生成新结点
        p=(LinkList)malloc(sizeof(Node));
        //随机生成100以内的数字
        p->data=rand() % 100 +1;
        p->next=(*L)->next;
        //插入到表头
        (*L)->next=p;
    }
}

//尾插法，随机产生n个元素的值，建立带表头结点的单链线性表L
void CreateListTail(LinkList *L, int n)
{
    LinkList p,r;
    int i;
    //初始化随机种子
    srand(time(0));
    *L=(LinkList)malloc(sizeof(Node));
    //r为指向尾部的结点
    //注意L与r的关系，L是指整个单链表，而r是指指向尾结点的变量，r会随着循环不断地变化结点
    //而L则是随着循环增长为一个多节点的链表。
    r=*L;
    for(i=0; i<n; i++)
    {
        //生成新结点
        p=(Node *)malloc(sizeof(Node));
        //随机生成100以内的数字
        p->data=rand() % 100 + 1;
        //将表尾终结点的指针指向新节点
        r->next = p;
        //将当前的新结点定义为表尾终端结点
        r=p;
    }
    //表示当前链表结束
    r->next=NULL;
}

//3.10单链表的整表删除
//初始条件：顺序线性表L已存在，操作结果将L重置为空表
Status ClearList(LinkList *L)
{
    LinkList p,q;
    //p指向第一个结点
    p=(*L)->next;
    //每到表尾
    while(p)
    {
        q=p->next;
        free(p);
        p=q;
    }
    //头结点指针域为空
    (*L)->next=NULL;
    return OK;
}

3.11 单链表结构与顺序存储结构优缺点
存储分配方式：
    顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
    单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能：
    查找：
        顺序存储结构O(1)
        单链表O(n)
    插入和删除:
        顺序存储结构需要平均移动表长一半的元素,时间为O(n)
        单链表在找出某位置的指针后，插入和删除时间仅为O(1)
    空间性能:
        顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
        单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制