【数据结构与算法】单向链表的实现（下）

// 头插数据
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

// 尾插数据
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySLTNode(x);
  // 链表为空
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    // 找尾节点
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

// 尾删数据
void SListPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);// 判断是否为空链表
  // 只有一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    SLTNode* prev = NULL;
    while (tail->next)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    tail = NULL;
    prev->next = NULL;
    //SLTNode* tail = *pphead;
    //while (tail->next->next)
    //{
    //  tail = tail->next;
    //}
    //free(tail->next);
    //tail->next = NULL;
  }
}

// 头删数据
void SListPopFront(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead); // 判断是否为空链表
  SLTNode* newHead = (*pphead)->next; // 新的头节点
  free(*pphead); // 释放旧的头节点
  *pphead = newHead;
}

// 查找数据
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  // 循环遍历链表
  while (cur)
  {
    if (cur->data == x)
    {
      return cur; // 找到了
    }
    cur = cur->next; // 继续往后找
  }
  return NULL; // 没找到
}

// 在pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  // 头插
  if (*pphead == pos)
  {
    SListPushFront(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
      assert(prev);
      // 暴力检查，如果prev为空，那么就说明pos不在链表中，参数pos传错了
    }
    SLTNode* newnode = BuySLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}

// 在pos位置之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

// 删除pos位置的数据
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  // 头删数据
  if (*pphead == pos)
  {
    SListPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
      assert(prev);
      // 暴力检查，如果prev为空，那么就说明pos不在链表中，参数pos传错了
    }
    prev->next = pos->next;
    free(pos);
  }
}

// 删除pos位置之后的数据
void SListEraseAfter(SLTNode* pos)
{
  assert(pos);
  // pos位置执行NULL
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    SLTNode* next = pos->next;
    pos->next = next->next;
    free(next);
  }
}

#include "SList.h"
#include "SList.h"
// 测试头插、头删
void TestSList1()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPrint(plist); // 4->3->2->1->NULL
  SListPopFront(&plist);
  SListPrint(plist); // 3->2->1->NULL
  SListPopFront(&plist);
  SListPrint(plist); // 2->1->NULL
  SListPopFront(&plist);
  SListPrint(plist); // 1->NULL
  SListPopFront(&plist);
  SListPrint(plist); // NULL
  SListDestory(&plist);
}
// 测试尾插、尾删
void TestSList2()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPrint(plist); // 1->2->3->4->NULL
  SListPopBack(&plist);
  SListPrint(plist); // 1->2->3->NULL
  SListPopBack(&plist);
  SListPrint(plist); // 1->2->NULL
  SListPopBack(&plist);
  SListPrint(plist); // 1->NULL
  SListPopBack(&plist);
  SListPrint(plist); //NULL
  SListDestory(&plist);
}
// 测试查找、插入
void TestSList3()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 2);
  SListPrint(plist); // 1->2->3->4->2->2->NULL
  SLTNode* pos = SListFind(plist, 2);
  int i = 1;
  while (pos)
  {
    printf("第%d个pos节点:%p->%d\n", i++, pos, pos->data);
    pos = SListFind(pos->next, 2);
  }
  pos = SListFind(plist, 3);
  if (pos)
  {
    pos->data *= 10; // 修改
    printf("该数据已修改为原来的10倍\n");
  }
  else
  {
    printf("链表中没有该数据\n");
  }
  SListPrint(plist); // 1->2->30->4->2->2->NULL
  pos = SListFind(plist, 2);
  if (pos)
  {
    SListInsert(&plist, pos, 20);
  }
  SListPrint(plist); // 1->20->2->30->4->2->2->NULL
  pos = SListFind(plist, 1);
  if (pos)
  {
    SListInsert(&plist, pos, 10);
  }
  SListPrint(plist); // 10->1->20->2->30->4->2->2->NULL
  SListDestory(&plist);
}
// 测试删除
void TestSList4()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPrint(plist); // 1->2->3->4->NULL
  SLTNode* pos = SListFind(plist, 4);
  SListInsertAfter(pos, 40);
  SListPrint(plist); //1->2->3->4->40->NULL
  pos = SListFind(plist, 3);
  SListErase(&plist, pos);
  SListPrint(plist); // 1->2->4->40->NULL
  pos = SListFind(plist, 4);
  SListEraseAfter(pos);
  SListPrint(plist); // 1->2->4->NULL
  SListDestory(&plist);
}
int main()
{
  //TestSList1();
  //TestSList2();
  //TestSList3();
  TestSList4();
  return 0;
}