C語言鏈表詳解

前言

 學(xué)習(xí)鏈表之前，先來看幾個(gè)術(shù)語：
  首節(jié)點(diǎn)：存放第一個(gè)有效數(shù)據(jù)的節(jié)點(diǎn)；
  尾節(jié)點(diǎn)：存放最后一個(gè)有效數(shù)據(jù)的節(jié)點(diǎn)；
  頭節(jié)點(diǎn)：頭節(jié)點(diǎn)的數(shù)據(jù)類型與首節(jié)點(diǎn)的數(shù)據(jù)類型相同，并且頭節(jié)點(diǎn)是首節(jié)點(diǎn)前面的那個(gè)節(jié)點(diǎn)，并不存放有效數(shù)據(jù)；頭節(jié)點(diǎn)的存在只是為了方便鏈表的操作。
  頭指針：指向頭節(jié)點(diǎn)的指針；
  尾指針：指向尾節(jié)點(diǎn)的指針。

鏈表的基本操作

 1. 節(jié)點(diǎn)的構(gòu)造

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

 2. 建立鏈表

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

    //建立頭結(jié)點(diǎn)
    head = (struct stu *) malloc(LEN);
    head->next = NULL;  //頭指針指向的頭結(jié)點(diǎn)的指針域?yàn)榭?
    p1 = head;  //把頭指針的指向賦給指針p1，即p1指向頭結(jié)點(diǎn)
    p2 = (struct stu *)malloc(LEN); //分配第一個(gè)節(jié)點(diǎn)，并讓p2指向他
    printf("輸入節(jié)點(diǎn)信息：學(xué)號(hào)、姓名和成績(jī)\n");
    scanf("%s%s%f",p2->num, p2->name, &p2->score);
    getchar();

    //學(xué)號(hào)為字符串'0'作為結(jié)束輸入的條件
    while(strcmp(p2->num,"0") != 0){
        /*
            執(zhí)行結(jié)束后
                1)p2的next域?yàn)镹ULL.
                2)第一個(gè)節(jié)點(diǎn)的next域指向第二個(gè)節(jié)點(diǎn)的數(shù)據(jù)域
                3)p1指針指向第二個(gè)節(jié)點(diǎn)的數(shù)據(jù)域
        */
        p2->next = p1->next;
        p1->next = p2;
        p1 = p2;

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

 3. 輸出鏈表

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

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

 4. 插入節(jié)點(diǎn)

//插入節(jié)點(diǎn)
void insert(struct stu * head, struct stu * p0){
    struct stu *p1, *p2;

    p1 = head->next;    //p1指向第一個(gè)節(jié)點(diǎn)
    p2 = head;          //p2為待插入節(jié)點(diǎn)的前面一個(gè)節(jié)點(diǎn)

    while((p1!=NULL) && (strcmp(p0->num, p1->num)==1)){ //當(dāng)p0的學(xué)號(hào)大于p1的學(xué)號(hào)并且沒有到最后一個(gè)時(shí)不進(jìn)行插入 
        p2=p1;
        p1=p1->next;
    }

    //下面進(jìn)行插入操作 
    p0->next = p2->next;
    p2->next = p0;
}

 5. 刪除節(jié)點(diǎn)

int delete(struct stu *head, char num[]){
    //聲明兩個(gè)結(jié)構(gòu)體類型的指針，p1和p2 
    struct stu *p1, *p2;
    p1 = head->next;    //p1指向第一個(gè)節(jié)點(diǎn) 
    p2 = head;          //p2指向p1的前驅(qū)結(jié)點(diǎn)

    //查找要?jiǎng)h除的節(jié)點(diǎn)的位置 
    while(p1!=NULL && strcmp(num, p1->num)!=0){
        p2=p1;
        p1=p1->next;
    }

    //要?jiǎng)h除的節(jié)點(diǎn)不存在 
    if(!p1){
        return 0;
    }

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

 6. 主函數(shù)

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

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

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

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

思路總結(jié)

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

p0->next = p2->next;

 3. 刪除節(jié)點(diǎn)：查找要?jiǎng)h除的節(jié)點(diǎn)的位置，執(zhí)行插入操作，語句：

p2->next = p1->next;

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