线性表的链式存储
解决顺序存储的缺点，插入和删除，动态存储问题。
特点：
线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素，存储单元可以是连续的，也可以不连续。可以被存储在任意内存未被占用的位置上。
所以前面的顺序表只需要存储数据元素信息就可以了。在链式结构中还需要一个元素存储下一个元素的地址。
为了表示每个数据元素，ai与其直接后继数据元素ai+1之间的逻辑关系，对ai来说，除了存储其本身的信息外，还需要存一个指示器直接后续的信息。把存储元素信息的域叫数据域，把存储直接后继位置的域
叫指针域。这两部分信息组成数据元素ai的存储映像，叫结点(Node);

顺序表和链表优缺点
存储方式：
顺序表是一段连续的存储单元
链表是逻辑结构连续物理结构（在内存中的表现形式）不连续
时间性能，
查找顺序表O(1)
链表 O(n)
插入和删除
顺序表 O(n)
链表O(1)
空间性能
顺序表需要预先分配空间，大小固定
链表，不需要预先分配，大小可变，动态分配
循环链表
简单的来说，就是将原来单链表中最有一个元素的next指针指向第一个元素或头结点，链表就成了一个环，头尾相连，就成了循环链表。circultlar linker list.
注意非空表，和空表。多数会加入头结点。
原来结束的条件是
p->next != NULL> p-next != Head

#include <stdio.h>
#include "linklist.h"

int main(int argc, char** argv)
{
  LinkList* ll = CreateLinkList();
  DATATYPE data[] = {
      {"zhangsan", 'm', 20, 80},  {"lisi", 'f', 23, 84},
      {"wangmaizi", 'f', 32, 90}, {"guanerge", 'm', 50, 91},
      {"liubei", 'm', 51, 92},
  };

  // InsertHeadLinkList(ll, &data[0]);
  // InsertHeadLinkList(ll, &data[1]);
  // InsertHeadLinkList(ll, &data[2]);

  // ShowLinkList(ll);
  printf("-----------insert tail--------------------\n");
  InsertTailLinkList(ll, &data[0]);
  InsertTailLinkList(ll, &data[1]);
  InsertTailLinkList(ll, &data[2]);
  ShowLinkList(ll);
  printf("-----------insert pos--------------------\n");
  InsertPosLinkList(ll, &data[3], 1);
  ShowLinkList(ll);

  char want_name[] = "zhang1san";
  LinkNode* tmp = FindLinkList(ll, want_name);
  if (NULL == tmp)
  {
    printf("cant find %s\n", want_name);
  }
  else
  {
    printf("name:%s score:%d\n", tmp->data.name, tmp->data.score);
  }

  printf("-----------del--------------------\n");
  DeleteLinkList(ll, "lisi");
  ShowLinkList(ll);
  printf("-----------modify--------------------\n");
  ModifyLinkList(ll, "wangmaizi", &data[4]);
  ShowLinkList(ll);
  // system("pause");

  DestroyLinkList(ll);
  return 0;
}

#ifndef _LINKLIST_H_
#define _LINKLIST_H_
typedef struct person
{
  char name[32];
  char sex;
  int age;
  int score;
} DATATYPE;

typedef struct node
{
    //数据域 需要存储的数据
  DATATYPE data;
  //指针域 指示当前元素的下一个元素的地址
  struct node *next;
} LinkNode;

typedef struct list
{
    //第一个节点的地址
  LinkNode *head;
  //链表中有效元素的个数
  int clen;
} LinkList;

LinkList *CreateLinkList();
int InsertHeadLinkList(LinkList *list, DATATYPE *data);
int InsertTailLinkList(LinkList *list, DATATYPE* data);
int InsertPosLinkList(LinkList *list, DATATYPE* data,int pos);
int ShowLinkList(LinkList *list);
LinkNode *FindLinkList(LinkList *list, char *name);
int DeleteLinkList(LinkList *list, char *name);
int ModifyLinkList(LinkList *list, char *name, DATATYPE *data);
int DestroyLinkList(LinkList *list);
int IsEmptyLinkList(LinkList *list);
int GetSizeLinkList(LinkList *list);
#endif  // !1

#include "linklist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

LinkList *CreateLinkList()
{  // 1000
  LinkList *ll = malloc(sizeof(LinkList));
  if (NULL == ll)
  {
    perror("CreateLinkList malloc");
    return NULL;
  }

  ll->head = NULL;
  ll->clen = 0;
  return ll;
}

int InsertHeadLinkList(LinkList *list, DATATYPE *data)
{
  LinkNode *newnode = malloc(sizeof(LinkNode));
  if (NULL == newnode)
  {
    perror("InsertHeadLinkList malloc");
    return 1;
  }
  //新节点的初始化
  memcpy(&newnode->data, data, sizeof(DATATYPE));
  newnode->next = NULL;

  //链表非空的情况
  if (!IsEmptyLinkList(list))
  {
    newnode->next = list->head;
  }

  list->head = newnode;

  list->clen++;
  return 0;
}

int IsEmptyLinkList(LinkList *list)
{
  return 0 == list->clen;
}

int ShowLinkList(LinkList *list)
{
  LinkNode *tmp = list->head;
  while (tmp)
  {
    printf("name:%s sex:%c age:%d score:%d\n", tmp->data.name, tmp->data.sex,
           tmp->data.age, tmp->data.score);
    // tmp++
    tmp = tmp->next;
  }

  return 0;
}

int InsertTailLinkList(LinkList *list, DATATYPE *data)
{
  if (IsEmptyLinkList(list))
  {
    return InsertHeadLinkList(list, data);
  }
  else
  {
    LinkNode *tmp = list->head;
    // tmp 需要停在最后一个有效节点上
    while (tmp->next)
    {
      tmp = tmp->next;
    }

    LinkNode *newnode = malloc(sizeof(LinkNode));
    if (NULL == newnode)
    {
      perror("InsertTailLinkList malloc");
      return 1;
    }

    memcpy(&newnode->data, data, sizeof(DATATYPE));
    newnode->next = NULL;

    tmp->next = newnode;
  }
  list->clen++;
  return 0;
}

int InsertPosLinkList(LinkList *list, DATATYPE *data, int pos)
{
  int len = GetSizeLinkList(list);
  if (pos < 0 || pos > len)
  {
    fprintf(stderr, "InsertPosLinkList pos error\n");
    return 1;
  }
  // inserthead
  if (0 == pos)
  {
    return InsertHeadLinkList(list, data);
  }
  // inserttail
  else if (pos == len)
  {
    return InsertTailLinkList(list, data);
  }
  else  //中间插入
  {
    LinkNode *tmp = list->head;
    int off = pos - 1;
    // tmp 需要停在待插下标节点的前一位置
    while (off--)
    {
      tmp = tmp->next;
    }

    LinkNode *newnode = malloc(sizeof(LinkNode));
    if (NULL == newnode)
    {
      perror("InsertposLinkList malloc");
      return 1;
    }
    memcpy(&newnode->data, data, sizeof(DATATYPE));
    newnode->next = NULL;

    newnode->next = tmp->next;
    tmp->next = newnode;
  }
  list->clen++;
  return 0;
}

int GetSizeLinkList(LinkList *list)
{
  return list->clen;
}

LinkNode *FindLinkList(LinkList *list, char *name)
{
  LinkNode *tmp = list->head;
  while (tmp)
  {
    if (0 == strcmp(tmp->data.name, name))
    {
      return tmp;
    }
    // tmp++;
    tmp = tmp->next;
  }
  return NULL;
}

int DeleteLinkList(LinkList *list, char *name)
{
  if (IsEmptyLinkList(list))
  {
    fprintf(stderr, "DeleteLinkList empty list\n");
    return 1;
  }
  LinkNode *tmp = list->head;
  //删除的是第一个节点
  if (0 == strcmp(tmp->data.name, name))
  {
    list->head = list->head->next;
    free(tmp);
    list->clen--;
  }
  //非第一个节点
  else
  {
    while (tmp->next)
    {
      if (0 == strcmp(tmp->next->data.name, name))
      {
        //标记待删除的节点
        LinkNode *del = tmp->next;
        //链表的指针跨过待删节点
        tmp->next = tmp->next->next;
        free(del);
        list->clen--;
        break;
      }
      tmp = tmp->next;
    }
  }
  return 0;
}


int ModifyLinkList(LinkList *list, char *name, DATATYPE *data)
{

      LinkNode* tmp = FindLinkList(list, name);
      if(NULL == tmp)
      {
        printf("modify error\n");
        return 1;
      }
      memcpy(&tmp->data,data,sizeof(DATATYPE));
      return 0;
}


int DestroyLinkList(LinkList *list)
{
    LinkNode* tmp = list->head;
    //删除链表
    while(tmp)
    {
        list->head = list->head->next;
        free(tmp);
        tmp = list->head;

    }
    // 释放链表表头
    free(list);
    return 0;
}