数据结构（Chapter Two -03）—线性表的链式表示

本文介绍: 线性表的链式表示

在这一部分（数据结构(Chapter Two -01)—线性表及顺序表-CSDN博客）里面，我们知道线性表包括顺序表和链表结构。前面写了顺序表的基本操作，那这部分就写一写线性表叭！

链表特点：不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理地址上也相邻。

优点：插入和删除不需要移动元素（顺序表的缺点是需要移动）

缺点：不可以随机存取。需要额外的存放地址的指针域，浪费空间。

我们可以发现顺序表和链表的缺点和优点似乎恰好相反。来一个单链表结点的结构：

我们可以看到指针域是存放下一个结点的地址的，每一个结点（除第一个）的读取都需要靠前一个结点读取，这就导致了缺点（不能随机读取）。

typedef struct LNode{    //定义单链表结点类型
    ElemType data;      //数据域
    struct LNode* next; //指针域
}LNode,*LinkList;
//头插法构建单链表
LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
    LNode *s;
    int x;                           
    L = (LinkList) malloc(sizeof(LNode));//创建头结点，L指向的那片区域是头结点
    L->next = NULL;                   //初始为空链表
    scanf("%d",&x);                   //输入结点的值
    while(x!=9999){                   //输入9999表示结束
        s=(LNode*)malloc(sizeof(LNode));//创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s;                   //将新结点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}
//尾插法构建单链表
LinkList List_TailInsert(LinkList &L){//正向建立单链表
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s,*r =L;                   //r表示尾指针
    scanf("%d",&x);                   //输入结点的值
    while(x!=9999){                   //输入9999表示结束
        s=(LNode*)malloc(sizeof(LNode));
        s->data =x;
        r->next =s;
        r=s;                           //r指向新的表尾结点
        scanf("%d",&x);
    }
    r->next = NULL;                    //尾结点指针设置为空
    return L;
}