无头单链表

//单链表结构的定义
typedef int SLNDataType;//数据类型
typedef struct SListNode {
  SLNDataType val;//结点数据域
  struct SListNode* next;//结点指针域
}SLNode;

//单链表结点的创建
SLNode* CreateNode(SLNDataType x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));//为新结点申请空间
  if (newnode == NULL)//申请失败
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->val = x;//新结点数据域
  newnode->next = NULL;//新结点指针域
  return newnode;
}

//单链表的打印
void SLTPrint(SLNode* phead)
{
  SLNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->val);
    cur = cur->next;
  }
  if (cur == NULL)
    printf("NULL\n");
}

//单链表的尾插
void SLTPushBack(SLNode** pphead, SLNDataType x)
{
    assert(pphead);
  SLNode* newnode = CreateNode(x);
  //链表为空
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else//链表不为空
  {
    SLNode* tail = *pphead;
    while (tail->next)//找尾结点
    {
      tail = tail->next;
    }
    tail->next = newnode;//尾插
  }
}

//单链表头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
    assert(pphead);
  SLNode* newnode = CreateNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
    //SLNode* newnode = CreateNode(x);
  链表为空
  //if (*pphead == NULL)
  //{
  //  *pphead = newnode;
  //}
  //else//链表不为空
  //{
  //  SLNode* tmp = *pphead;
  //  *pphead = newnode;
  //  (*pphead)->next = tmp;
  //}
}

//单链表尾删
void SLTPopBack(SLNode** pphead)
{
  assert(pphead);
  assert(*pphead);//链表不能为空
  if ((*pphead)->next == NULL)//链表只有一个结点
  {
    free(*pphead);
    *pphead = NULL;
  }
  else//链表有多个结点
  {
    SLNode* tail = *pphead;
    SLNode* prev = NULL;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    prev->next = NULL;
    free(tail);
    tail = NULL;
  }
}

//单链表头删
void SLTPopFront(SLNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  //SLNode* tmp = *pphead;
  //*pphead = (*pphead)->next;
  //free(tmp);
  //tmp = NULL;
  SLNode* tmp = (*pphead)->next;
  free(*pphead);
  *pphead = tmp;
}

//单链表查找（返回找到的结点）
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
  if (phead == NULL)
    return NULL;
  else
  {
    SLNode* cur = phead;
    while (cur)
    {
      if (cur->val == x)
        return cur;
      cur = cur->next;
    }
    return cur;//return NULL;
  }
}

//单链表任意位置插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
  assert(pphead);
  assert(pos);//必须在有效结点处插入
  assert(*pphead);//如果pos是有效结点，那么链表一定不为空
  SLNode* newnode = CreateNode(x);
  if (*pphead == pos)//插入位置在头结点处
  {
    //头插
    SLTPushFront(pphead, x);
  }
  else
  {
    SLNode* cur = *pphead;
    while (cur->next != pos)//找插入位置的前一结点
    {
      cur = cur->next;
    }
    newnode->next = cur->next;
    cur->next = newnode;
  }
}

//单链表任意位置删除
void SLTErase(SLNode** pphead, SLNode* pos)
{
  assert(pphead);
  assert(pos);//删除的必须是有效结点
  assert(*pphead);//链表不能为空
  if (*pphead == pos)//删除的结点是头结点
  {
    //头删
    SLTPopFront(pphead);
  }
  else
  {
    SLNode* cur = *pphead;
    while (cur->next != pos)//找删除结点的前一结点
    {
      cur = cur->next;
    }
    cur->next = pos->next;
    free(pos);
    pos = NULL;
  }
}

//单链表任意位置后插入
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{
  assert(pos);//必须是有效结点
  SLNode* newnode = CreateNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

//单链表任意位置后删除
void SLTEraseAfter(SLNode* pos)
{
  assert(pos);//必须是有效结点
  assert(pos->next);//如果pos是最后一个结点，那么pos的后一位置为空
  SLNode* tmp = pos->next;
  pos->next = tmp->next;
  free(tmp);
  tmp = NULL;
}

//单链表任意位置插入（不提供链表头结点）
void SLTInsertNohead(SLNode* pos, SLNDataType x)
{
  assert(pos);
  SLTInsertAfter(pos, x);//先在pos位置后插入
  pos->next->val = pos->val;
  pos->val = x;
}