学习嵌入式的第二十一天——数据结构——链表

单向链表特点：

存储的内存空间不连续 。为了弥补顺序存储存劣势。

优势
插入，删除   O(1)
动态存储 ，在程序运行期间决定大小。

劣势：
不能随机访问   O(N) 

节点-> 数据域+指针域 

顺序表(数组) 只有数据域

链表的操作代码：

#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;
}