双向链表基本操作

我不是女神ヾ 2022-08-02 00:22 177阅读 0赞

**双向链表**的情况与单链表类似，只是增加了一个前置链（即指向前一结点的指针域）  
算法等，与单链表很相似。只是需要安置好前向指针域。

**注意点：**在写关于链表的插入删除操作时，一定要注意该结点是不是最后一个结点，以免**出现 p->next == NULL，p->next->next 未定义的情况**，从而导致程序在特定条件下（比如你删除最后一个节点）出错。  
也就是需要注意，**最后一个节点和其他节点的操作不同，需要分开写。**

**以下是代码：**

#include <iostream>
    
    using namespace std;
    
    typedef struct BNode{
        int data;
        struct BNode *pre,*next;
    }BListNode;
    
    /**双链表创建*/
    BListNode * Create_BList(int n)
    {
        int i = 1;
        int elem;
        BListNode *head, *temp, *curr;
        /**curr：代表一个当前节点，它的下一节点是你正要创建的。*/
        /**temp：代表你正要创建的节点。*/
        head = new BListNode;
        head->data = n;
        head->pre = NULL;
        head->next = NULL;
        curr = head;
    
        while(i <= n)
        {
            cout << "Please input one elem" << endl;
            cin >> elem;
            temp = new BListNode;
            temp->data = elem;
            temp->pre = curr;
            temp->next = NULL;
            curr->next = temp;
            curr = temp;
    
            i++;
        }
    
        return head;
    }
    
    /**双链表输出*/
    void Output_BList(BListNode *head)
    {
        BListNode *temp;
        temp = head->next;
        if(NULL == temp)
            cout << "The BList is NULL" << endl;
    
        cout << "The BList is" << endl;
        while(NULL != temp)
        {
            cout << temp->data << ' ';
            temp = temp->next;
        }
        cout << endl;
    }
    
    /**删除元素i，不知道它是第几个结点*/
    BListNode * Delete_node(BListNode *head,int i)
    {
        BListNode *pre_temp, *temp;
        temp = head->next;
        pre_temp = head;   /**这一步必须要有，防止删除的节点是第一个节点*/
        if(NULL == temp)
            cout << "The BList is NULL" << endl;
        while(NULL != temp)
        {
            if(temp->data != i)
            {
                pre_temp = temp;
                temp = temp->next;
            }
            else{
                    if(NULL == temp->next)  /**如果删除的元素是最后一个，需要加这一步，不然按下面写，temp->next->pre会没有定义，从而出错*/
                    {
                        pre_temp->next = NULL;
                        delete temp;
                        break;
                    }
                    pre_temp->next = temp->next;
                    temp->next->pre = temp->pre;
                    delete temp;
                    break;
            }
        }
        if(NULL == temp)
            cout << "There is no i to be delete" << endl;
    
        return head;
    }
    
    /**插入一个节点：在第i个节点后，插入elem*/
    BListNode * Insert_node(BListNode *head,int i,int elem)
    {
        int j = 0;
        BListNode *temp, *p;
        temp = head;         /**这里讲temp = head 并且 j = 0，保证了节点可以插入在第一个节点前*/
        while(NULL != temp)
        {
            if(j >= i)
                break;       /**指针停留在第i个节点前*/
            j++;
            temp = temp->next;
        }
        if(NULL == temp->next)   /**当第i个节点是最后一个节点时*/
        {
            p = new BListNode;
            p->data = elem;
            p->next = NULL;
            p->pre = temp;
            temp->next = p;
    
            return head;
        }
        p = new BListNode;
        p->data = elem;
        p->next = temp->next;
        p->pre = temp->next->pre;
        temp->next->pre = p;
        temp->next = p;
    
        return head;
    }
    
    int main()
    {
        BListNode *p;
        p = Create_BList(5);
        Output_BList(p);
    
        Delete_node(p,2);   /**注意可以这样写，和 p = Delete_node(p,2);效果相同*/
        cout << "删除结点后" << endl;
        Output_BList(p);
    
        Insert_node(p,0,6);
        cout << "插入结点后" << endl;
        Output_BList(p);
    
        return 0;
    }

**结果如下：**  
![这里写图片描述][20150703151031591]

/*点滴积累，我的一小步O(∩\_∩)O~*/

[20150703151031591]: /images/20220731/39d85f7a33514dc9a8c8e1fa5786a5b1.png