在雙向連結串列中搜尋特定節點

只需要遍歷連結串列就可以搜尋連結串列中的特定元素。執行以下操作以搜尋特定操作。

• 將頭指標複製到臨時指標變數ptr中。

  ptr = head;
  

• 宣告一個區域性變數i並將其賦值為0。

  i=0;
  

• 遍歷連結串列，直到指標ptr變為null。繼續將指標移動到下一個並將i增加1。
• 將連結串列中的每個元素與要搜尋的資料項進行比較。
• 如果資料項與某一節點值匹配，則從函式返回該值的位置i，否則將返回NULL。

演算法

第1步：IF HEAD == NULL
   提示 「UNDERFLOW」
  轉到第8步
  [IF結束]

第2步：設定PTR = HEAD
第3步：設定i = 0
第4步：重複第5步到第7步，同時PTR != NULL
第5步：IF PTR→data = item
返回 i 的值
[結束]

第6步：i = i + 1
第7步：PTR = PTR→NEXT
第8步：退出

C語言實現的範例程式碼 -

#include<stdio.h>  
#include<stdlib.h>  
void create(int);
void search();
struct node
{
    int data;
    struct node *next;
    struct node *prev;
};
struct node *head;
void main()
{
    int choice, item, loc;
    do
    {
        printf("1.Create\\n2.Search\\n3.Exit\\n4.Enter your choice?");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            printf("Enter the item\\n");
            scanf("%d", &item);
            create(item);
            break;
        case 2:
            search();
        case 3:
            exit(0);
            break;
        default:
            printf("Please enter valid choice\\n");
        }
    } while (choice != 3);
}
void create(int item)
{
    struct node *ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL)
    {
        printf("OVERFLOW");
    }
    else
    {
        if (head == NULL)
        {
            ptr->next = NULL;
            ptr->prev = NULL;
            ptr->data = item;
            head = ptr;
        }
        else
        {
            ptr->data = item;printf("Press 0 to insert more ?\\n");
            ptr->prev = NULL;
            ptr->next = head;
            head->prev = ptr;
            head = ptr;
        }
        printf("Node Inserted\\n");
    }

}
void search()
{
    struct node *ptr;
    int item, i = 0, flag;
    ptr = head;
    if (ptr == NULL)
    {
        printf("Empty List\\n");
    }
    else
    {
        printf("Enter item which you want to search?\\n");
        scanf("%d", &item);
        while (ptr != NULL)
        {
            if (ptr->data == item)
            {
                printf("item found at location %d ", i + 1);
                flag = 0;
                break;
            }
            else
            {
                flag = 1;
            }
            i++;
            ptr = ptr->next;
        }
        if (flag == 1)
        {
            printf("Item not found\\n");
        }
    }

}

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

1.Create
2.Search
3.Exit
4.Enter your choice?1

Enter the item
23

Node Inserted

1.Create
2.Search
3.Exit
4.Enter your choice?1

Enter the item
90

Node Inserted

1.Create
2.Search
3.Exit
4.Enter your choice?2

Enter item which you want to search?
90

item found at location 1