在迴圈雙向連結串列開頭插入節點

2019-10-16 22:02:46

在迴圈雙向連結串列的開頭插入節點有兩種情況。 連結串列為空或連結串列中包含多個元素。

使用以下語句為新節點ptr分配記憶體空間。

ptr = (struct node *)malloc(sizeof(struct node));

在第一種情況下,條件head == NULL變為true,因此該節點將被新增為連結串列中的第一個節點。此新新增節點的prevnext指標將僅指向自身。 這可以通過使用以下語句來完成。

head = ptr;  
ptr -> next = head;   
ptr -> prev = head;

在第二種情況下,條件head == NULL變為false。 在這種情況下,需要在連結串列的末尾進行一些指標調整。 為此,需要通過遍歷連結串列來到達連結串列的最後一個節點。 遍歷連結串列可以使用以下語句完成。

temp = head;   
while(temp -> next != head)  
{  
    temp = temp -> next;   
}

在迴圈結束時,指標temp將指向連結串列的最後一個節點。 由於要插入的節點將是連結串列的第一個節點,因此temp需要將新節點ptr的地址包含在其下一部分中。 可以使用以下語句完成所有指標調整。

temp -> next = ptr;  
ptr -> prev = temp;  
head -> prev = ptr;  
ptr -> next = head;  
head = ptr;

以這種方式,新節點插入連結串列的開頭。 該演算法及其C語言實現如下。

演算法

第1步:IF PTR = NULL
    提示:記憶體溢位
    轉到第13步
    [IF結束]

第2步:設定NEW_NODE = PTR
第3步:SET PTR = PTR - > NEXT
第4步:設定NEW_NODE - > DATA = VAL
第5步:設定TEMP = HEAD
第6步:在TEMP - > NEXT!= HEAD 時重複第7步
第7步:SET TEMP = TEMP - > NEXT
[迴圈結束]

第8步:設定TEMP - > NEXT = NEW_NODE
第9步:設定NEW_NODE - > PREV = TEMP
第10步:設定NEW_NODE - > NEXT = HEAD
第11步:SET HEAD - > PREV = NEW_NODE
第12步:SET HEAD = NEW_NODE
第13步:退出

示意圖

C語言實現範例程式碼,如下所示 -

#include<stdio.h>  
#include<stdlib.h>  
void beg_insert(int);
struct node
{
    int data;
    struct node *next;
    struct node *prev;
};
struct node *head;
void main()
{
    int choice, item;
    do
    {
        printf("Enter the item which you want to insert?\n");
        scanf("%d", &item);
        beg_insert(item);
        printf("Press 0 to insert more ?\n");
        scanf("%d", &choice);
    } while (choice == 0);
}
void beg_insert(int item)
{
    struct node *ptr = (struct node *)malloc(sizeof(struct node));
    struct node *temp;
    if (ptr == NULL)
    {
        printf("OVERFLOW");
    }
    else
    {
        ptr->data = item;
        if (head == NULL)
        {
            head = ptr;
            ptr->next = head;
            ptr->prev = head;
        }
        else
        {
            temp = head;
            while (temp->next != head)
            {
                temp = temp->next;
            }
            temp->next = ptr;
            ptr->prev = temp;
            head->prev = ptr;
            ptr->next = head;
            head = ptr;
        }
        printf("Node Inserted");
    }
}

執行上面範例程式碼,得到以下結果 -

Enter the item which you want to insert?
12
Node Inserted
Press 0 to insert more ?
0

Enter the item which you want to insert?
23
Node Inserted
Press 0 to insert more ?
1