线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意存储单元存储线性表的数据元素。既然是任意存储的，那么每个数据元素不仅要存储自身的数据元素信息也要存储它后继元素的存储地址。

• 数据域 存储数据元素信息的域
• 指针域 存储直接后继位置的域
  数据域和指针域一起组成数据元素ai的存储映像，称为结点(Node)
  单链表即链表中的每个结点中只包含一个指针域
  
  单链表
  
  链表中第一个结点的存储位置叫做头指针，最后一个结点指针为空(NULL或^)
  
  完整的单链表
  
  单链表的第一个结点前附设一个结点，称为头结点
  
  带有头结点的单链表

头指针与头结点的异同
头指针 指链表指向第一个结点的指针，若链表有头结点则是指向头结点的指针。头指针具有标识作用，无论链表是否为空，头指针均不为空，头指针是链表的必要元素。
头结点为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可存放链表的长度)。这样对在第一元素结点前插入结点和删除第一结点其操作与其他结点操作统一。头结点不一定是链表必须要素

单链表存储示意图

带头结点的单链表

空链表

• 线性表的单链表存储结构定义

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

第i个元素与其后继元素关系

• 定义一个空结点*head = NULL

  
  
  准备条件

• 每次连接新的数据元素时都要动态分配一个node大小的内存空间，并把这块空间的首地址传给一个node指针型的变量s，*s的数据域是5。

  
  
  生成一个结点s

• 若head为空时把s结点变为head结点。

  
  
  head = p

• 若head不为空时，使head结点改成s的后继结点，代表每次新的元素到来时都是从头部插入的。

  
  
  s->next = head

• 每次元素插入结束时把s结点变为head结点，就是说每次都是从头部插入的。

  
  
  head = p

int main()
{
    node *head=NULL,*p;
    int num;

    printf("Enter some integers: ");
    scanf("%d",&num);
    while(num!=0){
        p=(node *)calloc(1,sizeof(node));
        p->data=num;
        if(head==NULL)
            head=p;
        else
            p->next=head;
        head=p;
        scanf("%d",&num);
    }
    for(p=head;p;p=p->next)
        printf("%-5d",p->data);
    printf("\n");
    return 0;
}

尾插法建立链式线性表(无首元)

• 首先创建两个空结点head和tail
• 创建一个p结点(开辟一个node大小的内存空间，空间首地址指向p,p结点的数据为num)。
• 若head为空，则把p结点变为head结点，第一次p结点为head结点并且也是tail结点。
• 若head结点不为空，则把tail的下一个结点指向p结点，即第二次是head结点指向p结点。每次插入元素后p结点变为tail结点。那么第三次插入元素时就是在第二个元素后面插入p结点

int main()
{
    node *head,*tail,*p;
    int num;

    head=tail=NULL;
    printf("Enter num: ");
    scanf("%d",&num);

    while(num!=0){
        p=(node *)calloc(1,sizeof(node));
        p->data=num;
        if(head==NULL)
            head=p;
        else
            tail->next=p;
        tail=p;
        scanf("%d",&num);
    }
    for(p=head;p;p=p->next)
        printf("%-4d",p->data);
    printf("\n");
    return 0;
}

尾插法建立链式线性表(有首元)
有一个头结点，也就是在while()外面先开辟一个node大小的内存空间，默认该结点的数据为0。还有一点不同是判断的时候要判断head结点的下一个结点是否为空。

int main()
{
    node *head,*tail,*p;
    int num;
    
    printf("Enter some integers: ");
    scanf("%d",&num);
    head=(node *)calloc(1,sizeof(node)); //初始化内存，设置为0 
    while(num!=0){
        p=(node *)calloc(1,sizeof(node));
        p->data=num;
        if(head->next==NULL) //head如何连接后一个元素 
            head->next=p;
        else
            tail->next=p; //第二个元素和后面元素的连接方式 
        tail=p;
        scanf("%d",&num);
    }
    for(p=head->next;p;p=p->next)
        printf("%-5d",p->data);
    printf("\n");
    return 0;
}

==================================================
题外话
结构体
这种类型是可以将多种数据类型组合起来的结构。
声明方式:

struct 结构体名称{
      成员1的类型  成员1的名称；
      成员2的类型  成员2的名称；
             ............
      成员3的类型  成员3的名称；
};

举例:

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

利用typedef定义这个结构体，即为结构体起别名node

typedef struct fact{
    int data;
    struct fact *next;
    }node;
等价于
typedef struct fact{
    int data;
    struct fact *next;
    };
typedef struct fact node;

malloc、calloc和realloc区别
三个函数的申明分别为:

 void* malloc(unsigned size);
 void* realloc(void* ptr, unsigned newsize);  
void* calloc(size_t numElements, size_t sizeOfElement); 

calloc 在初始化内存时设置初值为0。参数sizeOfElement为申请地址的单位元素长度 ，numElements为元素个数，即在内存中申请numElements*sizeOfElement字节大小的连续地址空间

malloc分配内存位于堆中，并且没有初始化内存的内容。因此基本上malloc之后，调用函数memset来初始化这部分的内存空间。在内存的动态存储区中分配一块长度为size字节的连续区域，参数size为需要内存空间的长度，返回该区域的首地址。

realloc对malloc申请的内存进行大小的调整

申请的内存最终需要通过函数free来释放
这三个函数都是在stdlib.h函数库中，它们的返回值都是请求系统分配的地址，如果请求失败就返回NULL。

最后说明一点，真的是实践出真理。如果不能完整的靠自己写出代码，那就不算自己懂。

============================补充内容===================================
这两天又把这部分认真看了看，实现了一下。并把每种方法封装成为一个子函数

头插法
头插法传入参数是一个指针变量和一个整形数
返回类型是指针类型，因为通过头插法建立的链表需要由head指针的首地址索引依次遍历才能找到其他链表元素。

Node* CreatLinkListHead(Node *head,int num)
{
    for(int i =0;i<num;i++)
    {
        Node *p = (Node *)malloc(sizeof(Node));
        p ->data = i+1;
        p->next = NULL;
        if(head == NULL)
        {
            head = p;
        }
        else
        {
            p->next = head;
            head = p;
        }
    }
    return head;
}

尾插法(无首元)
思想同头插法，但是有一点需要注意的是: tail = p应写在else的外面，即对head结点也适用。插入head结点后，head结点和tail结点都是p结点代替，这样当遇到非head结点时，tail->next才能找到位置否则容易出错。

//尾插法
Node* CreatLinkListTail(Node *head,int num)
{
    Node *p,*tail;
    head = tail = NULL;
    for(int i = 0;i<num;i++)
    {
        p = (Node *)malloc(sizeof(Node));
        p ->data = i+1;
        p->next = NULL;
        if(head == NULL)
        {
            head = p;
        }
        else
        {
            tail ->next = p;    
        }
        tail = p;
    }
    return head;
}

输出函数Output
从head结点依次遍历直到null

void Output(Node *head)
{
    Node *p;
    p = head;
    while(p){
        cout << p->data << " ";
        p = p->next;
    }
    cout <<endl;
}

注意事项
在使用malloc分配内存空间时，必须指定p->next = null。因为malloc函数不同于calloc函数会指定初始值为0，malloc函数的初始值是随机的，对数据的输出会造成一定的影响。