C語言數據結構之單鏈表操作實例分析

C語言數據結構之單鏈表操作實例分析

目錄

1. 引言
2. 單鏈表的基本概念
3. 單鏈表的存儲結構
4. 單鏈表的基本操作
   • 創建單鏈表
   • 插入節點
   • 刪除節點
   • 查找節點
   • 遍歷單鏈表
5. 單鏈表的應用實例
   • 實例1：學生信息管理系統
   • 實例2：多項式相加
6. 單鏈表的優缺點
7. 總結

引言

在計算機科學中，數據結構是組織和存儲數據的方式，以便能夠高效地訪問和修改數據。單鏈表是一種常見的數據結構，廣泛應用于各種算法和程序中。本文將詳細介紹單鏈表的基本概念、存儲結構、基本操作以及應用實例，并通過C語言代碼進行實例分析。

單鏈表的基本概念

單鏈表（Singly Linked List）是一種線性數據結構，由一系列節點組成，每個節點包含兩個部分：數據域和指針域。數據域用于存儲數據，指針域用于指向下一個節點。單鏈表的特點是每個節點只有一個指向下一個節點的指針，因此只能單向遍歷。

單鏈表的存儲結構

單鏈表的存儲結構可以用C語言中的結構體來表示：

struct Node {
    int data;           // 數據域
    struct Node* next;  // 指針域，指向下一個節點
};

在這個結構體中，data表示節點存儲的數據，next是指向下一個節點的指針。

單鏈表的基本操作

創建單鏈表

創建單鏈表的過程包括初始化頭節點和添加新節點。頭節點是單鏈表的起點，通常不存儲實際數據。

struct Node* createLinkedList(int data) {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = data;
    head->next = NULL;
    return head;
}

插入節點

在單鏈表中插入節點有多種方式，包括在鏈表頭部插入、在鏈表尾部插入以及在指定位置插入。

在鏈表頭部插入節點

void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

在鏈表尾部插入節點

void insertAtTail(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

在指定位置插入節點

void insertAtPosition(struct Node** head, int data, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;

    if (position == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Position out of range\n");
        return;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

刪除節點

刪除節點的操作包括刪除頭節點、刪除尾節點以及刪除指定位置的節點。

刪除頭節點

void deleteAtHead(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

刪除尾節點

void deleteAtTail(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }

    struct Node* temp = *head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }

    free(temp->next);
    temp->next = NULL;
}

刪除指定位置的節點

void deleteAtPosition(struct Node** head, int position) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = *head;
    if (position == 1) {
        *head = temp->next;
        free(temp);
        return;
    }

    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) {
        printf("Position out of range\n");
        return;
    }

    struct Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    free(nodeToDelete);
}

查找節點

查找節點可以通過遍歷鏈表來實現，找到指定數據的節點并返回其位置。

int searchNode(struct Node* head, int data) {
    struct Node* temp = head;
    int position = 1;

    while (temp != NULL) {
        if (temp->data == data) {
            return position;
        }
        temp = temp->next;
        position++;
    }

    return -1;  // 未找到
}

遍歷單鏈表

遍歷單鏈表是指依次訪問鏈表中的每個節點，并輸出其數據。

void printLinkedList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

單鏈表的應用實例

實例1：學生信息管理系統

假設我們需要實現一個簡單的學生信息管理系統，使用單鏈表來存儲學生的信息。每個學生的信息包括學號、姓名和成績。

struct Student {
    int id;
    char name[50];
    float grade;
    struct Student* next;
};

void insertStudent(struct Student** head, int id, char name[], float grade) {
    struct Student* newStudent = (struct Student*)malloc(sizeof(struct Student));
    newStudent->id = id;
    strcpy(newStudent->name, name);
    newStudent->grade = grade;
    newStudent->next = *head;
    *head = newStudent;
}

void printStudents(struct Student* head) {
    struct Student* temp = head;
    while (temp != NULL) {
        printf("ID: %d, Name: %s, Grade: %.2f\n", temp->id, temp->name, temp->grade);
        temp = temp->next;
    }
}

int main() {
    struct Student* head = NULL;
    insertStudent(&head, 1, "Alice", 95.5);
    insertStudent(&head, 2, "Bob", 88.0);
    insertStudent(&head, 3, "Charlie", 92.3);
    printStudents(head);
    return 0;
}

實例2：多項式相加

單鏈表可以用于表示多項式，每個節點存儲多項式的一項（系數和指數）。我們可以通過遍歷兩個多項式鏈表來實現多項式相加。

struct Term {
    int coefficient;
    int exponent;
    struct Term* next;
};

void insertTerm(struct Term** head, int coefficient, int exponent) {
    struct Term* newTerm = (struct Term*)malloc(sizeof(struct Term));
    newTerm->coefficient = coefficient;
    newTerm->exponent = exponent;
    newTerm->next = *head;
    *head = newTerm;
}

struct Term* addPolynomials(struct Term* poly1, struct Term* poly2) {
    struct Term* result = NULL;
    while (poly1 != NULL && poly2 != NULL) {
        if (poly1->exponent > poly2->exponent) {
            insertTerm(&result, poly1->coefficient, poly1->exponent);
            poly1 = poly1->next;
        } else if (poly1->exponent < poly2->exponent) {
            insertTerm(&result, poly2->coefficient, poly2->exponent);
            poly2 = poly2->next;
        } else {
            int sum = poly1->coefficient + poly2->coefficient;
            if (sum != 0) {
                insertTerm(&result, sum, poly1->exponent);
            }
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }

    while (poly1 != NULL) {
        insertTerm(&result, poly1->coefficient, poly1->exponent);
        poly1 = poly1->next;
    }

    while (poly2 != NULL) {
        insertTerm(&result, poly2->coefficient, poly2->exponent);
        poly2 = poly2->next;
    }

    return result;
}

void printPolynomial(struct Term* head) {
    struct Term* temp = head;
    while (temp != NULL) {
        printf("%dx^%d", temp->coefficient, temp->exponent);
        if (temp->next != NULL) {
            printf(" + ");
        }
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    struct Term* poly1 = NULL;
    insertTerm(&poly1, 5, 2);
    insertTerm(&poly1, 4, 1);
    insertTerm(&poly1, 2, 0);

    struct Term* poly2 = NULL;
    insertTerm(&poly2, 3, 1);
    insertTerm(&poly2, 1, 0);

    struct Term* result = addPolynomials(poly1, poly2);
    printPolynomial(result);
    return 0;
}

單鏈表的優缺點

優點

1. 動態內存分配：單鏈表可以根據需要動態分配內存，不需要預先分配固定大小的內存空間。
2. 插入和刪除操作高效：在單鏈表中插入和刪除節點的操作時間復雜度為O(1)，特別是在鏈表頭部進行操作時。
3. 靈活性：單鏈表可以輕松地擴展和縮減，適用于頻繁插入和刪除操作的場景。

缺點

1. 訪問效率低：單鏈表只能單向遍歷，訪問某個節點需要從頭節點開始依次遍歷，時間復雜度為O(n)。
2. 內存開銷：每個節點需要額外的指針域來存儲下一個節點的地址，增加了內存開銷。
3. 不支持隨機訪問：單鏈表不支持像數組那樣的隨機訪問，無法直接通過索引訪問某個節點。

總結

單鏈表是一種簡單而強大的數據結構，適用于需要頻繁插入和刪除操作的場景。通過本文的介紹，我們了解了單鏈表的基本概念、存儲結構、基本操作以及應用實例。雖然單鏈表在某些方面存在不足，但其靈活性和動態內存分配的特點使其在許多應用中仍然具有重要價值。掌握單鏈表的操作和應用，對于理解和實現更復雜的數據結構和算法具有重要意義。