C語言如何建立動態(tài)鏈表問題

更新時間：2022年12月23日 11:09:47 作者：馬馬也

這篇文章主要介紹了C語言如何建立動態(tài)鏈表問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

C語言建立動態(tài)鏈表

所謂建立動態(tài)鏈表是指在程序執(zhí)行過程中從無到有地建立起一個鏈表，即一個一個地開辟結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系。

代碼如下：

#include <stdio.h>
#include <stdib.h。
#define LEN sizeof(struct Student)
 
struct Student{
       long num;
       float score;
       struct Student * next;
};
 
int n;
 
struct Student * creat(void){
       struct Student * head;
       struct Student * p1, *p2;
       n = 0;
       p1 = p2 = (struct Student *)malloc(LEN);
       scanf("%ld,%f",&p1->num,&p1->score);
       head = null;
       while(p1->num != 0){
             n = n+1;
             if(n == 1)
                head = p1;
             else
                p2->next = p1;
             p2 = p1;
             p1 = (struct Student *)malloc(LEN);
             scanf("%ld,%f,&p1->num,&p1->score);
       }
       p2->next = null;
       return (head);
}

靜態(tài)鏈表和動態(tài)鏈表的區(qū)別

靜態(tài)鏈表和動態(tài)鏈表是線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的兩種不同的表示方式。

1、靜態(tài)鏈表是用類似于數(shù)組方法實(shí)現(xiàn)的，是順序的存儲結(jié)構(gòu)，在物理地址上是連續(xù)的，而且需要預(yù)先分配地址空間大小。所以靜態(tài)鏈表的初始長度一般是固定的，在做插入和刪除操作時不需要移動元素，僅需修改指針。

2、動態(tài)鏈表是用內(nèi)存申請函數(shù)（malloc/new）動態(tài)申請內(nèi)存的，所以在鏈表的長度上沒有限制。動態(tài)鏈表因為是動態(tài)申請內(nèi)存的，所以每個節(jié)點(diǎn)的物理地址不連續(xù)，要通過指針來順序訪問。

一、靜態(tài)鏈表

結(jié)構(gòu)體中的成員可以是各種類型的指針變量，當(dāng)一個結(jié)構(gòu)體中有一個或多個成員的基類型是本結(jié)構(gòu)體類型時，則稱這種結(jié)構(gòu)體為“引用自身的結(jié)構(gòu)體”。如：

struct node
{
　　char ch;
    int num;
　　struct node *p;
};
 
struct node a;	//聲明一個結(jié)構(gòu)體變量

p是一個可以指向struct node類型變量的指針成員。因此，a.p = &a 是合法的表達(dá)式，由此構(gòu)成的存儲結(jié)構(gòu)如下圖所示：

參考程序如下所示：

/*****************************************************
Copyright (C) 2017-2018 All rights reserved.
File name    ： static_link.c
Version      ： v1.0       
Author       ： Zhengqijun
Date         ： 2017年10月10日 星期二 15時12分30秒
Description  ： 
Funcion List ： 
*****************************************************/
 
#include <stdio.h>
 
/* 靜態(tài)鏈表 */
struct node
{
    int num;
    struct node *next;
};
 
int main()
{
    struct node stu[3];
    struct node *head, *p;
 
    stu[0].num = 10;		//對結(jié)點(diǎn)的num成員賦值
    stu[1].num = 20;
    stu[2].num = 30;
 
    head = &stu[0];		//頭指針指向第1個結(jié)點(diǎn)stu[0]
    stu[0].next = &stu[1];	//將結(jié)點(diǎn)stu[1]的地址賦值給stu[0]結(jié)點(diǎn)的next成員
    stu[1].next = &stu[2];	//將結(jié)點(diǎn)stu[2]的地址賦值給stu[1]結(jié)點(diǎn)的next成員
    stu[2].next = NULL;		//stu[2]是最后一個結(jié)點(diǎn)，其next成員不存放任何結(jié)點(diǎn)的地址，置為NULL
 
    //遍歷靜態(tài)鏈表
    p = head;			//使p指針也指向第1個結(jié)點(diǎn)
    
    do{
        printf("%d\n", p->num);	//輸出p所指向結(jié)點(diǎn)的數(shù)據(jù)
        p = p->next;		//然后讓p指向下一個結(jié)點(diǎn)
    } while (p != NULL);	//直到p的next成員為NULL，即完成遍歷
 
    return 0;
}

輸出結(jié)果為：

root@ubuntu:~/2017/1010$ ./static_link
10
20
30

二、動態(tài)鏈表

到目前為止，凡是遇到處理“批量”數(shù)據(jù)時，我們都是利用數(shù)組來存儲。定義數(shù)組必須（顯式的或隱含的）指明元素的個數(shù)，從而也就限定了一個數(shù)組中存放的數(shù)據(jù)量。在實(shí)際應(yīng)用中，一個程序在每次運(yùn)行時要處理的數(shù)據(jù)的數(shù)目通常并不確定。如果數(shù)組定義的小了，就沒有足夠的空間存放數(shù)據(jù)，定義大了又浪費(fèi)存儲空間。

對于這種情況，如果能在程序執(zhí)行過程中，根據(jù)需要隨時開辟存儲空間，不需要時再隨時釋放，就能比較合理的使用存儲空間。C 語言的動態(tài)存儲分配提供了這種可能性。每次動態(tài)分配的存儲單元，其地址不一定是連續(xù)的，而所需處理的批量數(shù)據(jù)往往是一個整體，各數(shù)據(jù)之間存在著接序關(guān)系。鏈表的每個節(jié)點(diǎn)中，除了要有存放數(shù)據(jù)本身的數(shù)據(jù)域外，至少還需要有一個指針域，用它來存放下一個節(jié)點(diǎn)元素的地址，以便通過這些指針把各節(jié)點(diǎn)連接起來。由于鏈表每個存儲單元都由動態(tài)存儲分配獲得，故稱這樣的鏈表為“動態(tài)鏈表”。

參考程序如下所示：

/*****************************************************
Copyright (C) 2017-2018 All rights reserved.
File name    ： dynamic_link.c
Version      ： v1.0       
Author       ： Zhengqijun
Date         ： 2017年10月10日 星期二 15時31分59秒
Description  ： 
Funcion List ： 
*****************************************************/
 
#include <stdio.h>
#include <stdlib.h>
 
/*所謂動態(tài)鏈表，是指在程序執(zhí)行過程中從無到有地建立起一個鏈表，即一個一個地開辟結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系。*/
struct Student
{
    int No;		//學(xué)號
    struct Student *next;
};
 
int main()
{
    struct Student *p1, *p2;
	struct Student *head, *p;
 
    int n = 0; //結(jié)點(diǎn)個數(shù)
 
    head = NULL;
    p1 = (struct Student *)malloc(sizeof(struct Student));
    printf("請輸入第1個學(xué)號\n");
    scanf("%d", &p1->No);
 
    p2 = p1; //開始時，p1和p2均指向第1個結(jié)點(diǎn)
    while (p1->No != 0)
    {
        n++;
        if (n == 1)
        {
            head = p1;
        }
        else
        {
            p2->next = p1;
        }
 
        p2 = p1;//p2是最后一個結(jié)點(diǎn)
        printf("請輸入學(xué)號，輸入0終止：\n");
        p1 = (struct Student *)malloc(sizeof(struct Student));
        scanf("%d", &p1->No);
    };
 
    p2->next = NULL;//輸入完畢后，p2->next為NULL
 
    //遍歷動態(tài)鏈表
	p = head;
    printf("\n學(xué)號為：\n");
 
    while (p != NULL)
    {
        printf("%d\n", p->No);
        p = p->next;
    }
 
    return 0;
}

輸出結(jié)果為：