数据结构 ④ 双向链表

• 概念

双向链表.png

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有一个数据域及两个指针，分别指向直接后继和直接前驱。

双向链表结构.png

• 代码实现

  • 结构

    typedef struct DuLNode{ //结点类型定义
     struct DuLNode *prior; //结点的前驱 
     int data; //结点的数据域
     struct DuLNode *next;//结点的后继
    }DuLNode;
    
    typedef DuLNode *DuLinkList;
    

  • 初始化

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

  • 插入

    /*
      插入
     */
    void insertDuLNode(DuLinkList *head,int place,int num){
        //校验合法
        if (place == 0)
        {
            printf("请从1开始插入\n");
            return;
        }
        DuLNode *prior = *head;
        for (int i = 1; i < place  && prior; i++)
        {
            prior = prior->next;
        }
        printf("前驱是-%d\n", prior->data);
        //非循环链表根据是否为NULL  判断是否越界。
        if (prior == NULL)
        {
            printf("索引越界，插入失败\n");
            return;
        }
        DuLNode *temp = (DuLNode *)malloc(sizeof(DuLNode));
        temp->next = NULL;
        temp->prior = NULL;
        temp->data = num;
        DuLNode *next = prior->next;
    
        if (next == NULL)
        {
            prior->next =  temp;
            temp->prior = prior;
        }else{
            temp->next = next;
            next->prior = temp;
            prior->next = temp;
            temp->prior = prior;
        }
        printf("插入成功-%d\n",temp->data);
    }
    

  • 删除

    /*
      删除
     */
    void deleteDuLNode(DuLinkList *head,int place){
        if (place == 0)
        {
            printf("请从1开始删除\n");
            return;
        }
        DuLNode *prior = *head;
        for (int i = 1; i < place && prior; i++)
        {
            prior = prior->next;
        }
        if (prior->next == NULL)
        {
            printf("索引越界,删除失败\n");
            return;
        }
       //4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
        DuLNode *delTemp = prior->next;
    
        //5. p->next 等于要删除的结点的下一个结点
        prior->next = delTemp->next;
        
        //6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
        if (delTemp->next != NULL) {
            delTemp->next->prior = prior;
        }
        
        //7.删除delTemp结点
        free(delTemp);
    }
    

  • 查询

    /*
       返回匹配value 的第一个结点
     */
    DuLNode* LocateElem(DuLinkList L,int value) {
    
         int i = 1;
        DuLinkList p=L->next; /* p指向第一个结点 */ 
        while(p != NULL) {
            i++;
            if(p->data == value) /* 满足关系 */
            return p;
            p=p->next;
        }
        printf("越界\n");
        return NULL;}