动态链表整理

• 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
  

• 主要涉及结构体，指针，以及函数的知识

• 本文章主要采用的是链式储存的方法

• 需要定义一个结构体，包括数据以及之战两部分

  struct node 
  { 
      int data; //储存当前结点的数值
      struct node * next; //存放下一个结点的地址
  }; 
  

• 为了方便之后操作我们可以用typedef对结构体类型重命名

  typedef struct node 
  { 
      int data; 
      struct node * next; 
  } Node; 
  

• 接下来我们试在主函数中，创建空链表

   Node * head = NULL; //指针指向空
  

• 最后要释放连接

  void freeList(Node ** pHead) 
  { 
      Node * p = *pHead; 
      Node * pre; 
      while (p != NULL) 
      { 
          pre = p; p = p->next;
          free(pre); 
      }
      *pHead = NULL; 
  }
  

• 大致思路为将前一个结点的指针指向新结点
• 新结点的指针应当指向空结点（成为尾节点）
• 注意：当原有链表为空时，要将主函数中的头结点指向新结点

//因为要对头结点进行修改，所以传入的时头节点的地址
//头结点地址，加入的数据
void push_back_list(Node ** phead, int data) 
{ 
    //动态链表要申请动态的内存 
    Node * newNode = (Node *)malloc(sizeof(Node)); 
    newNode->data = data; 
    newNode->next = NULL; 
    // 判断原链表是否为空链表 
    if (*phead == NULL) 
    {  
        *phead = newNode; 
    } 
    else 
    { 
        Node * temp = *pHead; 
        // 循环判断寻找尾结点
        while (temp->next != NULL) 
            temp = temp->next; // 原链表尾节点指向新节点 
        temp->next = newNode; 
    } 
}

• 主要依靠循环遍历

void printList(Node * head) 
{ 
    Node * p;
    for (p=head; p!=NULL; p=p->next) 
        printf("%d ", p->data); //等价于 `*p.`
    puts(""); 
}

int size_list(Node *phead)
{
    int cnt = 0;
    Node *p;
    for(p = phead; p != NULL; p = p->next)
        cnt ++;
    
    return cnt;
}

• 含n个结点的链表有n+1个位置可以插入，插到n位置需要n + 1次（找到插入位置之前的结点）
• 先将新结点的指针指向后结点再将前结点的指针指向新结点
  • 顺序反过来会产生环，而且会丢失数据
    

//头结点地址，插入位置，插入数据
void insert_list(Node **phead,int index, int date)
{
    if(index < 0 || index > size_list(*phead)) 
        return;

    Node *newNode;
    newNode = (Node*)malloc(sizeof(Node));
    newNode -> next = NULL;
    newNode -> data = date;
    
    //特判插入头结点时
    if(index == 0)
    {
        newNode->next = *phead;
        *phead = newNode;
        return;
    }

    Node *p;
    p = *phead;
    int i;
    for(i = 0; i < index - 1; i ++)
        p = p ->next;
    newNode->next = p->next;
    p->next = newNode;
}

• 将需要删除结点a的前一个结点的指针指向a后的一个结点

• 删除头结点时需特殊处理（不需要再找它前面的结点）

• 删除第一次出现的某个数思想类似，将循环稍加改动即可
  

//头结点地址以及需要删除的数字
//随删随释放内存
void delete_list(Node **phead, int date)
{
    Node *p = *phead; 

    while(p->next != NULL)
    {
        if(p->next->data == date)
        {
            Node *t = p->next;
            p ->next = t->next;
            free(t);
        }
        else p = p->next;
    }

    p = *phead;
    if(p->data == date)
    {
        *phead = p->next;
        free(p);
    }
}
t = t->next;
            free(t);
        }
        else p = p->next;
    }

    p = *phead;
    if(p->data == date)
    {
        *phead = p->next;
        free(p);
    }
}