线性表-链式存储结构

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

线性表的链式存储结构是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的也可以是不连续的。

　　以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在的链式结构中，除了要存储数据元素信息外还要存储它的后继元素的存储地址。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素的存储映像，称为结点（Node)。

　　2、头节点和头指针

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

头节点：
1）头结点是为了操作的统一和方便设立的，放在第一个元素的结点之前，其数据域一般无意义（也可以用来存放链表长度）。
2）头节点不一定是链表的必要元素。

带头结点的单链表：
   头指针head指向头结点，头结点的值域不包含任何信息，指针域存储指向第一个结点的指针。从头结点的后继结点开始存储数据信息。
   头指针head始终不等于NULL,head->next等于NULL时链表为空。
不带头结点的单链表：
   头指针head直接指向开始结点。当head等于NULL时，链表为空。

3、带头结点的单链表实现

C语言中可以用结构指针来描述单链表：

typedef int ElemType;
typedef struct Node 
{
    ElemType data;     //数据域
    struct Node* next; //指针域
}Node;            //结点由存放数据元素的数据域和存放后继结点地址的指针域组成    
typedef struct Node *LinkList;

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#define ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 1
typedef int ElemType;

typedef struct Node
{
    ElemType data;     //数据域
    struct Node* next; //指针域
}Node;       //结点由存放数据元素的数据域和存放后继结点地址的指针域组成    
typedef struct Node *LinkList;

//初始化带头结点的链表
int InitList(LinkList *L) //struct Node **L
{
    *L = (LinkList)malloc(sizeof(Node)); //L是指向头节点的二级指针
    if (*L == NULL)
        return ERROR;

    (*L)->next = NULL;
    (*L)->data = 0;
    return OK;
}

//将L重置为空表 将整表删除
int ClearList(LinkList *L)
{
    LinkList p, q;
    p = (*L)->next; //p指向第一个结点
    while (p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL; //头结点指针域为空
    return OK;
}

//判断链表是否为空
int ListEmpty(LinkList L)
{
    if (L->next)
        return FALSE;
    return TRUE;
}

//获取链表长度
int ListLength(LinkList L)
{
    int length = 0;
    LinkList q = L;
    while (q->next != NULL)
      {  q = q->next;
        length++;
　　　}
    return length;
}

//当第i个元素存在时，其值赋给e并返回OK
int GetElem(LinkList L, int i, ElemType *e)
{
    LinkList p = L->next; //初始化p指向第一个结点，j为计数器
    int j = 1;
    while (p&&j < i) //顺指针向后查找，直到p指向第i个数据元素或p为空
    {
        p = p->next; //p指向第二个结点 j为2   ……  p指向第i个结点 j为i
        ++j;
    }
    if (!p || j > i) return ERROR; //第i个元素不存在
    *e = p->data; //取第i个元素

    return OK;
}

//在L中第i个位置之前插入数据元素e,L的长度加1
int ListInsert(LinkList *L, int i, ElemType e)
{
    LinkList p, s; //struct Node *p,*s
    int j = 1;
    p = *L;
    while (p &&j < i) //寻找第i-1个结点
    {
        p = p->next;//此时p指向第一个结点 退出循环时p指向i-1个结点
        ++j;
    }
    if (!p || j > i) //第i个元素不存在
        return ERROR;

    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next; //将p的后继节点附s的后继
    p->next = s;    //将s赋给p的后继
    return OK;
}

//删除L中第i个数据元素，并用e返回，L的长度减1
int ListDelete(LinkList *L, int i, ElemType *e)
{
    LinkList p, q;
    int j = 1;
    p = *L;
    while (p->next && j < i) 
    {
        p = p->next;  //此时p指向第一个结点 p->next已是第二个结点的地址。
        ++j;         //退出循环时p指向i-1个结点    p->next已是i结点的地址
    }
    if (!(p->next) || j > i)
        return ERROR;

    q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);
    return *e;
}
void main()
{
    LinkList L = (LinkList)malloc(sizeof(Node));
    L->next = NULL;
    L->data = 0;

    for (int i = 1;i <= 10;i++)
        ListInsert(&L, i, i * i);
    LinkList p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }

    printf("
");
    int e;
    ListDelete(&L, 3, &e);
    p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }

    system("pause");
}

4、创建链表

//随机产生n个元素的值，建立带表头结点的单链线性表L （头插法）
void CreateListHead(LinkList *L, int n)
{
    LinkList p;
    srand(time(0)); //初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL; //建立带头结点的空链表

    for (int i = 0;i < n;++i)
    {
        p = (LinkList)malloc(sizeof(Node)); //生成新结点
        p->data = rand() % 100 + 1; //随机生成100内的数字

        p->next = (*L)->next;
        (*L)->next = p;
    }
}

//随机产生n个元素的值，建立带表头结点的线性表L （尾插法）
void CreateListTail(LinkList *L, int n)
{
    LinkList p, r;
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));//建立一个单链表
    r = *L; //r为指向尾部的结点
    for (int i = 0;i < n;i++)
    {
        p = (Node *)malloc(sizeof(Node)); //生成新结点
        p->data = rand() % 100 + 1;
        r->next = p;//指向新结点p
        r = p; //将当前新结点定义为表尾终端结点
    }
    r->next = NULL; //表示当前链表结束
}

5、单链表结构与顺序存储结构的优缺点：
1)若线性表需要频繁查找，很少进行插入和删除操作，采用顺序存储结构合适。例如用户注册信息，绝大多数都是读取数据。
2)若需要频繁的插入和删除，采用单链表合适。

存储分配方式：顺序存储结构：一段连续的存储单元依次存储线性表的数据元素

　　　　　　链式存储结构：用一组任意的存储单元存放线性表的元素
时间性能：顺序存储结构：查找O(1)，插入和删除O(n)

　　　　　　　链式存储结构：查找O(n)，插入和删除O(1)
空间性能：顺序存储结构：需要预先分配存储空间，较大浪费

　　　　　　链式存储结构：较小溢出利用零碎空间

：