线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构

非线性结构：不满足线性结构的数据结构

链表（单向链表的建立、删除、插入、打印）

1、链表一般分为：　

　　单向链表

    双向链表

    环形链表

2、基本概念

链表实际上是线性表的链式存储结构，与数组不同的是，它是用一组任意的存储单元来存储线性表中的数据，存储单元不一定是连续的，

且链表的长度不是固定的，链表数据的这一特点使其可以非常的方便地实现节点的插入和删除操作

链表的每个元素称为一个节点，每个节点都可以存储在内存中的不同的位置，为了表示每个元素与后继元素的逻辑关系，以便构成“一个节点链着一个节点”的链式存储结构，

除了存储元素本身的信息外，还要存储其直接后继信息，因此，每个节点都包含两个部分，第一部分称为链表的数据区域，用于存储元素本身的数据信息，这里用data表示，

它不局限于一个成员数据，也可是多个成员数据，第二部分是一个结构体指针，称为链表的指针域，用于存储其直接后继的节点信息，这里用next表示，

next的值实际上就是下一个节点的地址，当前节点为末节点时，next的值设为空指针

1 struct link
2 {
3    int data;
4    struct link *next;
5 };

像上面这种只包含一个指针域、由n个节点链接形成的链表，就称为线型链表或者单向链表，链表只能顺序访问，不能随机访问，链表这种存储方式最大缺点就是容易出现断链，

一旦链表中某个节点的指针域数据丢失，那么意味着将无法找到下一个节点，该节点后面的数据将全部丢失

3、链表与数组比较

数组（包括结构体数组）的实质是一种线性表的顺序表示方式，它的优点是使用直观，便于快速、随机地存取线性表中的任一元素，但缺点是对其进行 插入和删除操作时需要移动大量的数组元素，同时由于数组属于静态内存分配，定义数组时必须指定数组的长度，程序一旦运行，其长度就不能再改变，实际使用个数不能超过数组元素最大长度的限制，否则就会发生下标越界的错误，低于最大长度时又会造成系统资源的浪费，因此空间效率差

4、单向链表的建立

#include <stdio.h>
#include <stdlib.h>

struct link *AppendNode (struct link *head);
void DisplyNode (struct link *head);
void DeletMemory (struct link *head);

struct link
{
    int data;
    struct link *next;
};

int main(void)
{
    int i = 0;
    char c;
    struct link *head = NULL;    //链表头指针
    printf("Do you want to append a new node(Y/N)?");
    scanf_s(" %c", &c);           
    while (c == 'Y' || c == 'y')
    {
        head = AppendNode(head);//向head为头指针的链表末尾添加节点
        DisplyNode(head);        //显示当前链表中的各节点的信息
        printf("Do your want to append a new node(Y/N)");
        scanf_s(" %c", &c);       
        i++;
    }
    printf("%d new nodes have been apended", i);
    DeletMemory(head);    //释放所有动态分配的内存