在迴圈單連結串列的末尾插入節點有兩種情況。 第一種情況:將節點插入空連結串列中,第一種情況:將節點插入非空連結串列中。
首先,使用C語言的malloc
函式為新節點分配記憶體空間。
struct node *ptr = (struct node *)malloc(sizeof(struct node));
在第一情況中,條件head == NULL
將為true
。 因為,插入節點是一個迴圈單連結串列的唯一節點(只是插入到連結串列中)將僅指向自身。 還需要使head
指標指向此節點。 這將通過使用以下語句來完成。
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
在第二種情況下,條件head == NULL
將變為false
,該連結串列至少包含一個節點。 在這種情況下,需要遍歷連結串列才能到達連結串列的最後一個節點。 這將通過使用以下語句來完成。
temp = head;
while(temp->next != head){
temp = temp->next;
}
在迴圈結束時,指標temp
將指向連結串列的最後一個節點。 因為,插入連結串列的新節點將是連結串列的新的最後一個節點。 因此,現有的最後一個節點即temp
必須指向新節點ptr
。 這是通過使用以下語句完成的。
temp -> next = ptr;
連結串列的新的最後一個節點,即ptr
將指向連結串列的頭節點。
ptr -> next = head;
這樣,新節點將在開頭插入到迴圈單連結串列中。
演算法
第1步:IF PTR = NULL
提示 OVERFLOW
轉到第1步
[IF結束]
第2步:設定NEW_NODE = PTR
第3步:SET PTR = PTR - > NEXT
第4步:設定NEW_NODE - > DATA = VAL
第5步:設定NEW_NODE - > NEXT = HEAD
第6步:設定TEMP = HEAD
第7步:在TEMP - > NEXT!= HEAD 時重複第8步
第8步:SET TEMP = TEMP - > NEXT
[迴圈結束]
第9步:設定TEMP - > NEXT = NEW_NODE
第10步:退出
示意圖
C語言範例程式碼
void lastinsert(struct node*ptr, struct node *temp, int item)
{
ptr = (struct node *)malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("OVERFLOW\n");
}
else
{
ptr->data = item;
if (head == NULL)
{
head = ptr;
ptr->next = head;
}
else
{
temp = head;
while (temp->next != head)
{
temp = temp->next;
}
temp->next = ptr;
ptr->next = head;
}
}
}