C語言鏈表詳解

前言

 學習鏈表之前，先來看幾個術語：
  首節點：存放第一個有效數據的節點；
  尾節點：存放最后一個有效數據的節點；
  頭節點：頭節點的數據類型與首節點的數據類型相同，并且頭節點是首節點前面的那個節點，并不存放有效數據；頭節點的存在只是為了方便鏈表的操作。
  頭指針：指向頭節點的指針；
  尾指針：指向尾節點的指針。

鏈表的基本操作

 1. 節點的構造

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define LEN sizeof(struct stu)
struct stu
{
    //數據域
    char num[10];
    char name[20];
    float score;
    //指針域
    struct stu * next;
};

 2. 建立鏈表

//建立鏈表
struct stu * create(){
    //聲明頭指針,p1和p2兩個指針
    struct stu * head;
    struct stu * p1, *p2;

    //建立頭結點
    head = (struct stu *) malloc(LEN);
    head->next = NULL;  //頭指針指向的頭結點的指針域為空

    p1 = head;  //把頭指針的指向賦給指針p1，即p1指向頭結點
    p2 = (struct stu *)malloc(LEN); //分配第一個節點，并讓p2指向他
    printf("輸入節點信息：學號、姓名和成績\n");
    scanf("%s%s%f",p2->num, p2->name, &p2->score);
    getchar();

    //學號為字符串'0'作為結束輸入的條件
    while(strcmp(p2->num,"0") != 0){
        /*
            執行結束后
                1)p2的next域為NULL.
                2)第一個節點的next域指向第二個節點的數據域
                3)p1指針指向第二個節點的數據域
        */
        p2->next = p1->next;
        p1->next = p2;
        p1 = p2;

        //重新分配第三個節點，并讓p2指向他
        p2 = (struct stu *)malloc(LEN);
        printf("輸入節點信息：學號、姓名和成績\n");
        scanf("%s%s%f",p2->num, p2->name, &p2->score);
        getchar();
    }
    //執行結束后釋放p2指針，并返回頭指針
    free(p2);
    return head;
};

 3. 輸出鏈表

//輸出鏈表
void print(struct stu * head){
    struct stu * p; //聲明一個p指針
    printf("num name score\n");
    p = head->next; //指針p指向第一個節點

    //依次輸出各個節點直到最后一個節點
    while(p!=NULL){
        printf("%-10s %-20s %-4.1f\n",p->num, p->name, p->score);
        p=p->next;
    }
}

 4. 插入節點

//插入節點
void insert(struct stu * head, struct stu * p0){
    struct stu *p1, *p2;

    p1 = head->next;    //p1指向第一個節點
    p2 = head;          //p2為待插入節點的前面一個節點

    while((p1!=NULL) && (strcmp(p0->num, p1->num)==1)){ //當p0的學號大于p1的學號并且沒有到最后一個時不進行插入 
        p2=p1;
        p1=p1->next;
    }

    //下面進行插入操作 
    p0->next = p2->next;
    p2->next = p0;
}

 5. 刪除節點

int delete(struct stu *head, char num[]){
    //聲明兩個結構體類型的指針，p1和p2 
    struct stu *p1, *p2;
    p1 = head->next;    //p1指向第一個節點 
    p2 = head;          //p2指向p1的前驅結點

    //查找要刪除的節點的位置 
    while(p1!=NULL && strcmp(num, p1->num)!=0){
        p2=p1;
        p1=p1->next;
    }

    //要刪除的節點不存在 
    if(!p1){
        return 0;
    }

    //執行刪除操作，并釋放p1指針 
    p2->next = p1->next;
    free(p1);
    return 1;
}

 6. 主函數

//主函數
int main()
{
    struct stu * h, *p0;
    char num[10];
    printf("建立鏈表\n");
    h = create();
    p0 = (struct stu *)malloc(LEN);

    //測試插入節點的操作
    printf("輸入待插入的節點信息：學號、姓名和成績\n");
    scanf("%s%s%f",p0->num, p0->name, &p0->score);
    getchar();
    if(strcmp(p0->num,"0") != 0){
        insert(h, p0);
    }

    //測試刪除節點的操作
    printf("輸入待刪除節點的學號\n");
    scanf("%s",num);
    if(strcmp(num,"0") != 0){
        delete(h, num);
    }

    printf("輸出鏈表\n");
    print(h);
    return 0;
}

思路總結

 1. 創建節點：頭節點的指針域初始為空，將新創立的節點依次掛到上面。p1始終指向最后一個節點，p2始終為新建立的節點。
 2. 插入節點：先查找該節點要插入的位置，在插入節點。插入的語句為：

p0->next = p2->next;

 3. 刪除節點：查找要刪除的節點的位置，執行插入操作，語句：

p2->next = p1->next;

 4. 輸出鏈表：知道頭指針，就能知道整個鏈表