您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計疑難解答

C 語言帶頭節點單鏈表查找元素並返回序號的實現

編輯：程式設計疑難解答

需求分析

建立帶頭節點的單鏈表。
查找元素 x，找到返回節點序號（從 1 開始），未找到返回 0。
封裝為函數 int findNode(LinkList head, ElemType x)。

完整代碼實現

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *LinkList;

// 初始化帶頭節點的空鏈表
LinkList initList() {
    LinkList head = (LinkList)malloc(sizeof(Node));
    if (!head) exit(EXIT_FAILURE);
    head->next = NULL;
    return head;
}

// 尾插法創建鏈表（演示用）
LinkList createList(LinkList head, ElemType arr[], int n) {
    Node *tail = head;
    for (int i = 0; i < n; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

// 核心查找函數：返回序號(1-based)，未找到返回 0
int findNode(LinkList head, ElemType x) {
    Node *p = head->next;  // 跳過頭節點，指向第一個數據節點
    int pos = 1;           // 序號從 1 開始
    
    while (p != NULL) {
        if (p->data == x) {
            return pos;    // 找到，返回當前序號
        }
        p = p->next;
        pos++;
    }
    return 0;              // 遍歷結束未找到
}

// 釋放鏈表內存
void freeList(LinkList head) {
    Node *p = head;
    while (p) {
        Node *tmp = p;
        p = p->next;
        free(tmp);
    }
}

// 測試主函數
int main() {
    LinkList list = initList();
    ElemType data[] = {10, 20, 30, 40, 50};
    createList(list, data, 5);
    
    int targets[] = {30, 60, 10, 50};
    for (int i = 0; i < 4; i++) {
        int pos = findNode(list, targets[i]);
        if (pos > 0) {
            printf("元素 %d 位於第 %d 個節點\n", targets[i], pos);
        } else {
            printf("元素 %d 未找到\n", targets[i]);
        }
    }
    
    freeList(list);
    return 0;
}

關鍵點解析

關鍵點	代碼體現	說明
頭節點處理	`Node *p = head->next`	頭節點不存數據，遍歷從第一個數據節點開始
序號計數	`int pos = 1`	業務邏輯通常從 1 開始計數，0 表示未找到
返回值語義	`return pos` / `return 0`	正數表示位置，0 表示失敗，符合 C 語言慣例
邊界條件	`while (p != NULL)`	空鏈表直接返回 0，單節點正常判斷

變體：返回節點指針而非序號

Node* findNodePtr(LinkList head, ElemType x) {
    Node *p = head->next;
    while (p) {
        if (p->data == x) return p;
        p = p->next;
    }
    return NULL;  // 未找到返回 NULL
}

返回指針更靈活（可直接修改節點），但調用方需自行計算位置或判斷 NULL。

遞歸版本（教學參考）

int findNodeRecursive(Node *node, ElemType x, int pos) {
    if (!node) return 0;
    if (node->data == x) return pos;
    return findNodeRecursive(node->next, x, pos + 1);
}

// 調用：findNodeRecursive(head->next, x, 1);

注意：遞歸深度受限於棧大小，長鏈表慎用。

擴展：查找所有匹配節點

void findAllNodes(LinkList head, ElemType x, int positions[], int *count) {
    Node *p = head->next;
    int pos = 1;
    *count = 0;
    while (p) {
        if (p->data == x) {
            positions[(*count)++] = pos;
        }
        p = p->next;
        pos++;
    }
}