数据结构与算法之双向/循环连表

引言：单项循环连表的指针方向只能往一个方向走

如果在单项循环连表要找到C的前驱，我们需要从起点L开始,需要一次新的遍历，这样以来，时间复杂度高达O(N)。但如果拿C的后继，则时间复杂度仅仅为O(1)，指针往后移便可以找到。单项连表只有后继的指针域。接下来进入双向连表：

双向连表创建

双向连表的结点结构：有前驱prior，后继next，data为数据域。

创建双向连表时尽量避免采用头插法，因为采用头插法创建的时候数据是倒序的，永远是往中间插入。

• 设计一个结构体      

//定义结点typedef struct Node{ 
   ElemType data;//数据域   
   struct Node *prior;。//前驱   
   struct Node *next;//后继
}Node;
typedef struct Node * LinkList;

创建双向链接:实例代码

Status createLinkList(LinkList *L){    
    //*L 指向头结点   
     *L = (LinkList)malloc(sizeof(Node));开辟一个空间   
     if (*L == NULL) return ERROR;//如果为空，不往下执行   
     (*L)->prior = NULL;//首先前驱赋空   
     (*L)->next = NULL;//后继赋空    
     (*L)->data = -1;//不会打印    //新增数据   
     LinkList p = *L;   
     for(int i=0; i < 10;i++){//这里使用尾插法       
     //1.创建1个临时的结点
     LinkList temp = (LinkList)malloc(sizeof(Node));     
     temp->prior = NULL;       
     temp->next = NULL;       
     temp->data = i;       
     //2.为新增的结点建立双向链表关系     
       //① temp 是p的后继   
         p->next = temp;      
       //② temp 的前驱是p       
         temp->prior = p;        
       //③ p 要记录最后的结点的位置,方便下一次插入    
        p = p->next;  
      }   
 return OK;
}

打印：showPrintf

//5.2 打印循环链表的元素
void display(LinkList L){ 
    LinkList temp = L->next;   
    if(temp == NULL){ 
       printf("打印的双向链表为空!\n");     
       return;  
     }     

     while (temp) {  
          printf("%d  ",temp->data);  
          temp = temp->next;   
     }   
     printf("\n");
}

main 函数:
int main(int argc, const char * argv[]) { 
   Status isStatus = 0;   
   LinkList L;   
   int temp,item,e;   
   isStatus = createLinkList(&L);   
   display(L);   

   return 0;
}

双向连表的插入

Status ListInsert(LinkList *L, int i, ElemType data){  
      //1. 插入的位置不合法 为0或者为负数    
     if(i < 1) return ERROR;  

      //2. 新建结点   
     LinkList temp = (LinkList)malloc(sizeof(Node));
     temp->data = data;   
     temp->prior = NULL;//此时前驱不知道设NULL   
     temp->next = NULL;//此时后继也不知道设NULL

    //3.将p指向头结点!   
     LinkList p = *L;

    //4. 找到插入位置i直接的结点   
     for(int j = 1; j < i && p;j++)      
     p = p->next;

    //5. 如果插入的位置超过链表本身的长度   
     if(p == NULL){      
          return  ERROR;  
      }

    //6. 判断插入位置是否为链表尾部; 
     if (p->next == NULL) {       
         p->next = temp;      
         temp->prior = p;  
        }else {       
     //1️⃣ 将p->next 结点的前驱prior = temp    
        p->next->prior = temp;       
     //2️⃣ 将temp->next 指向原来的p->next   
        temp->next = p->next;     
     //3️⃣ p->next 更新成新创建的temp    
        p->next = temp;       
     //4️⃣ 新创建的temp前驱 = p     
       temp->prior = p;  
    }   
   return  OK;
}

删除双向链表指定位置上的结点

Status ListDelete(LinkList *L, int i, ElemType *elem){  
  int k = 1;   
  LinkList p = (*L);  
  //1.判断双向链表是否为空,如果为空则返回ERROR;   
  if (*L == NULL) {      
      return ERROR;
    }   
  //2. 将指针p移动到删除元素位置前一个 
   while (k < i && p != NULL) {   
         p = p->next;        k++;  
        }   
     //3.如果k>i 或者 p == NULL 则返回ERROR  
     if (k>i || p == NULL) {     
       return  ERROR;   
     }    
    //4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数   
     LinkList delTemp = p->next;   
     *elem = delTemp->data;   
 //5. p->next 等于要删除的结点的下一个结点   
     p->next = delTemp->next;    
    //6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p; 
   if (delTemp->next != NULL) {       
         delTemp->next->prior = p;  
  }  
  //7.删除delTemp结点   
 free(delTemp);//释放  
  return OK;
}

删除双向链表指定的元素

Status LinkListDeletVAL(LinkList *L, int data){   
     LinkList p = *L;    
    //1.遍历双向循环链表   
     while (p) { 
       //2.判断当前结点的数据域和data是否相等,若相等则删除该结点   
     if (p->data == data) {          
        //修改被删除结点的前驱结点的后继指针,参考图上步骤1️⃣   
         p->prior->next = p->next;          
       //修改被删除结点的后继结点的前驱指针,参考图上步骤2️⃣         
     if(p->next != NULL){             
        p->next->prior = p->prior;           
        }         
        //释放被删除结点p         
       free(p);            //退出循环     
       break;   
     }       
     //没有找到该结点,则继续移动指针p      
      p = p->next;    
    }  
  return OK;
}

在双向链表中查找元素

int selectElem(LinkList L,ElemType elem){ 
       LinkList p = L->next;  
       int i = 1;    
       while (p) {  
          if (p->data == elem) {      
              return i;    
          }       
         
          i++;     
          p = p->next;  
      }   
     return  -1;
}

在双向链表中更新结点

Status replaceLinkList(LinkList *L,int index,ElemType newElem){ 
       LinkList p = (*L)->next;  
       for (int i = 1; i < index; i++) { 
            p = p->next;  
       }

    p->data = newElem;   
    return OK;
}

双向循环链表初始化

Status creatLinkList(LinkList *L){  
    *L = (LinkList)malloc(sizeof(Node));   
    if (*L == NULL) {      
         return ERROR;  
     }  
    (*L)->next = (*L);  
    (*L)->prior = (*L);
    //新增数据   
    LinkList p = *L;   
    for(int i=0; i < 10;i++){  
      //1.创建1个临时的结点       
       LinkList temp = (LinkList)malloc(sizeof(Node));    
       temp->data = i;       
      //2.为新增的结点建立双向链表关系     
      //① temp 是p的后继    
       p->next = temp;  
     
       //② temp 的前驱是p    
        temp->prior = p; 
     
      //③ temp的后继是*L      
        temp->next = (*L);    

       //④ p 的前驱是新建的temp       
         p->prior = temp;      
   
       //⑤ p 要记录最后的结点的位置,方便下一次插入   
         p = p->next; 
         
       }    
    return OK;
}

双向循环链表插入元素

/*当插入位置超过链表长度则插入到链表末尾*/
Status LinkListInsert(LinkList *L, int index, ElemType e){ 
   //1. 创建指针p,指向双向链表头  
      LinkList p = (*L);   
      int i = 1;   
        
     //2.双向循环链表为空,则返回error  
      if(*L == NULL) return ERROR;    
    
     //3.找到插入前一个位置上的结点p   
      while (i < index && p->next != *L) {     
           p = p->next;      
           i++;   
      }   

     //4.如果i>index 则返回error   
      if (i > index)  return ERROR;   
  
     //5.创建新结点temp   
        LinkList temp = (LinkList)malloc(sizeof(Node));   
    
     //6.temp 结点为空,则返回error   
      if (temp == NULL) return ERROR;    
   
     //7.将生成的新结点temp数据域赋值e.    
       temp->data = e;    
   
     //8.将结点temp 的前驱结点为p;   
       temp->prior = p;   
  
      //9.temp的后继结点指向p->next;  
       temp->next = p->next;  
      
      //10.p的后继结点为新结点temp;  
        p->next = temp;  
  
      //如果temp 结点不是最后一个结点  
        if (*L != temp->next) {      
              //11.temp节点的下一个结点的前驱为temp 结点     
             temp->next->prior = temp;    
            }else{    
                (*L)->prior = temp;    
       }   
     return OK;
}

遍历双向循环链表

Status Display(LinkList L){   
     if (L == NULL) {      
      printf("打印的双向循环链表为空!\n\n");    
    return ERROR;   
     }    
    printf("双向循环链表内容:  ");    
    LinkList p = L->next;  
    while (p != L) {     
          printf("%d  ",p->data);     
          p = p->next;  
     }   
     printf("\n\n");   
 return OK;
}

最后main函数

int main(int argc, const char * argv[]) {   
      LinkList L;  
      Status iStatus;  
      ElemType temp,item;   

     iStatus = creatLinkList(&L);  
     printf("双向循环链表初始化是否成功(1->YES)/ (0->NO):  %d\n\n",iStatus); 
     Display(L);  
     printf("输入要插入的位置和数据用空格隔开：");   
     scanf("%d %d",&temp,&item);   
     iStatus = LinkListInsert(&L,temp,item); 
     Display(L);    
     printf("输入要删除位置：");   
     scanf("%d",&temp);    
     iStatus = LinkListDelete(&L, temp, &item);  
     printf("删除链表位置为%d,结点数据域为:%d\n",temp,item);   
     Display(L); 
     return 0;
}