数据结构 ⑤ 双向循环链表

双向循环链表.png

双向循环链表的实现

• 初始化

  /*
    初始化
   */
  void DuLinkListInit(DuLinkList *Head){
    *Head = (DuLinkList)malloc(sizeof(DuLNode));
    if (*Head == NULL)
    {
        printf("初始化失败\n");
    }
    (*Head)->next = (*Head);
    (*Head)->prior = (*Head);
    (*Head)->data = -1;
    printf("初始化成功\n");
  }
  

• 插入

  /*
    插入
   */
  void insertDuLNode(DuLinkList *head,int place,int num){
    //校验合法
    if (place == 0)
    {
        printf("请从1开始插入\n");
        return;
    }
     //1. 创建指针p,指向双向链表头
      DuLNode *p = (*head);
  
      int i = 1;
      
      //2.双向循环链表为空,则返回error
      if(*head == NULL){
          printf("插入失败 链表为空\n");
      }
     
      //3.找到插入前一个位置上的结点p
      while (i < place && p->next != *head) {
          p = p->next;
          I++;
      }
      
      //4.如果i>index 则返回error
      if (i < place) {
          printf("插入失败 %d\n", place);
          return;
      }
      
      //5.创建新结点temp
      DuLNode *temp = (DuLNode *)malloc(sizeof(DuLNode));
      
      //6.temp 结点为空,则返回error
      if (temp == NULL) {
          printf("插入失败");
      }
      
      //7.将生成的新结点temp数据域赋值e.
      temp->data = num;
      
      //8.将结点temp 的前驱结点为p;
      temp->prior = p;
      //9.temp的后继结点指向p->next;
      temp->next = p->next;
      //10.p的后继结点为新结点temp;
      p->next = temp;
      
      //如果temp 结点不是最后一个结点
      if (*head != temp->next) {
          
          //11.temp节点的下一个结点的前驱为temp 结点
          temp->next->prior = temp;
      }else{
  
          (*head)->prior = temp;
          
      }
      printf("插入成功-%d\n",temp->data);
  }
  
  

• 删除

  /*
    删除
   */
  void deleteDuLNode(DuLinkList *head,int place){
     
      int i = 1;
      DuLinkList temp = (*head)->next;
      
      if (*head == NULL) {
        printf("删除失败\n");
          return;
      }
      
      if(temp->next == *head){
          free(*head);
          (*head) = NULL;
          printf("删除成功\n");
          return;
      }
      
      //1.找到要删除的结点
      while (i < place && temp != (*head)) {
          temp = temp->next;
          I++;
      }
     
     if (temp == *head){
          printf("删除失败%d\n",temp->data);
  
          return;
      }else{
        printf("删除%d\n",temp->data);
      }
  
      //2.修改被删除结点的前驱结点的后继指针 
      temp->prior->next = temp->next;
      //3.修改被删除结点的后继结点的前驱指针 
      temp->next->prior = temp->prior;
      //4. 删除结点temp
      free(temp);
      printf("删除成功\n");
      return ;
  }