在雙向鏈表中搜索特定節點

只需要遍曆鏈表就可以搜索鏈表中的特定元素。執行以下操作以搜索特定操作。

• 將頭指針複製到臨時指針變數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