C語(yǔ)言如何建立動(dòng)態(tài)鏈表問(wèn)題
C語(yǔ)言建立動(dòng)態(tài)鏈表
所謂建立動(dòng)態(tài)鏈表是指在程序執(zhí)行過(guò)程中從無(wú)到有地建立起一個(gè)鏈表,即一個(gè)一個(gè)地開辟結(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)鏈表和動(dòng)態(tài)鏈表的區(qū)別
靜態(tài)鏈表和動(dòng)態(tài)鏈表是線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的兩種不同的表示方式。
1、靜態(tài)鏈表是用類似于數(shù)組方法實(shí)現(xiàn)的,是順序的存儲(chǔ)結(jié)構(gòu),在物理地址上是連續(xù)的,而且需要預(yù)先分配地址空間大小。所以靜態(tài)鏈表的初始長(zhǎng)度一般是固定的,在做插入和刪除操作時(shí)不需要移動(dòng)元素,僅需修改指針。
2、動(dòng)態(tài)鏈表是用內(nèi)存申請(qǐng)函數(shù)(malloc/new)動(dòng)態(tài)申請(qǐng)內(nèi)存的,所以在鏈表的長(zhǎng)度上沒(méi)有限制。動(dòng)態(tài)鏈表因?yàn)槭莿?dòng)態(tài)申請(qǐng)內(nèi)存的,所以每個(gè)節(jié)點(diǎn)的物理地址不連續(xù),要通過(guò)指針來(lái)順序訪問(wèn)。
一、靜態(tài)鏈表
結(jié)構(gòu)體中的成員可以是各種類型的指針變量,當(dāng)一個(gè)結(jié)構(gòu)體中有一個(gè)或多個(gè)成員的基類型是本結(jié)構(gòu)體類型時(shí),則稱這種結(jié)構(gòu)體為“引用自身的結(jié)構(gòu)體”。如:
struct node { char ch; int num; struct node *p; }; struct node a; //聲明一個(gè)結(jié)構(gòu)體變量
p是一個(gè)可以指向struct node類型變量的指針成員。因此,a.p = &a 是合法的表達(dá)式,由此構(gòu)成的存儲(chǔ)結(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時(shí)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; //對(duì)結(jié)點(diǎn)的num成員賦值 stu[1].num = 20; stu[2].num = 30; head = &stu[0]; //頭指針指向第1個(gè)結(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]是最后一個(gè)結(jié)點(diǎn),其next成員不存放任何結(jié)點(diǎn)的地址,置為NULL //遍歷靜態(tài)鏈表 p = head; //使p指針也指向第1個(gè)結(jié)點(diǎn) do{ printf("%d\n", p->num); //輸出p所指向結(jié)點(diǎn)的數(shù)據(jù) p = p->next; //然后讓p指向下一個(gè)結(jié)點(diǎn) } while (p != NULL); //直到p的next成員為NULL,即完成遍歷 return 0; }
輸出結(jié)果為:
root@ubuntu:~/2017/1010$ ./static_link
10
20
30
二、動(dòng)態(tài)鏈表
到目前為止,凡是遇到處理“批量”數(shù)據(jù)時(shí),我們都是利用數(shù)組來(lái)存儲(chǔ)。定義數(shù)組必須(顯式的或隱含的)指明元素的個(gè)數(shù),從而也就限定了一個(gè)數(shù)組中存放的數(shù)據(jù)量。在實(shí)際應(yīng)用中,一個(gè)程序在每次運(yùn)行時(shí)要處理的數(shù)據(jù)的數(shù)目通常并不確定。如果數(shù)組定義的小了,就沒(méi)有足夠的空間存放數(shù)據(jù),定義大了又浪費(fèi)存儲(chǔ)空間。
對(duì)于這種情況,如果能在程序執(zhí)行過(guò)程中,根據(jù)需要隨時(shí)開辟存儲(chǔ)空間,不需要時(shí)再隨時(shí)釋放,就能比較合理的使用存儲(chǔ)空間。C 語(yǔ)言的動(dòng)態(tài)存儲(chǔ)分配提供了這種可能性。每次動(dòng)態(tài)分配的存儲(chǔ)單元,其地址不一定是連續(xù)的,而所需處理的批量數(shù)據(jù)往往是一個(gè)整體,各數(shù)據(jù)之間存在著接序關(guān)系。鏈表的每個(gè)節(jié)點(diǎn)中,除了要有存放數(shù)據(jù)本身的數(shù)據(jù)域外,至少還需要有一個(gè)指針域,用它來(lái)存放下一個(gè)節(jié)點(diǎn)元素的地址,以便通過(guò)這些指針把各節(jié)點(diǎn)連接起來(lái)。由于鏈表每個(gè)存儲(chǔ)單元都由動(dòng)態(tài)存儲(chǔ)分配獲得,故稱這樣的鏈表為“動(dòng)態(tài)鏈表”。
參考程序如下所示:
/***************************************************** Copyright (C) 2017-2018 All rights reserved. File name : dynamic_link.c Version : v1.0 Author : Zhengqijun Date : 2017年10月10日 星期二 15時(shí)31分59秒 Description : Funcion List : *****************************************************/ #include <stdio.h> #include <stdlib.h> /*所謂動(dòng)態(tài)鏈表,是指在程序執(zhí)行過(guò)程中從無(wú)到有地建立起一個(gè)鏈表,即一個(gè)一個(gè)地開辟結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù),并建立起前后相鏈的關(guān)系。*/ struct Student { int No; //學(xué)號(hào) struct Student *next; }; int main() { struct Student *p1, *p2; struct Student *head, *p; int n = 0; //結(jié)點(diǎn)個(gè)數(shù) head = NULL; p1 = (struct Student *)malloc(sizeof(struct Student)); printf("請(qǐng)輸入第1個(gè)學(xué)號(hào)\n"); scanf("%d", &p1->No); p2 = p1; //開始時(shí),p1和p2均指向第1個(gè)結(jié)點(diǎn) while (p1->No != 0) { n++; if (n == 1) { head = p1; } else { p2->next = p1; } p2 = p1;//p2是最后一個(gè)結(jié)點(diǎn) printf("請(qǐng)輸入學(xué)號(hào),輸入0終止:\n"); p1 = (struct Student *)malloc(sizeof(struct Student)); scanf("%d", &p1->No); }; p2->next = NULL;//輸入完畢后,p2->next為NULL //遍歷動(dòng)態(tài)鏈表 p = head; printf("\n學(xué)號(hào)為:\n"); while (p != NULL) { printf("%d\n", p->No); p = p->next; } return 0; }
輸出結(jié)果為:
root@ubuntu:~/2017/1010$ ./dynamic_link
請(qǐng)輸入第1個(gè)學(xué)號(hào)1請(qǐng)輸入學(xué)號(hào),輸入0終止:2請(qǐng)輸入學(xué)號(hào),輸入0終止:3請(qǐng)輸入學(xué)號(hào),輸入0終止:4請(qǐng)輸入學(xué)號(hào),輸入0終止:0學(xué)號(hào)為:1234
注意:動(dòng)態(tài)鏈表中,每個(gè)節(jié)點(diǎn)沒(méi)有自己的名字,只能靠指針維系節(jié)點(diǎn)之間的關(guān)系。一旦某個(gè)節(jié)點(diǎn)的指針“斷開”,后續(xù)節(jié)點(diǎn)就再也無(wú)法找尋!
總結(jié)
以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
相關(guān)文章
C++實(shí)現(xiàn)LeetCode(10.正則表達(dá)式匹配)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(10.正則表達(dá)式匹配),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07有關(guān)C++中隨機(jī)函數(shù)rand() 和srand() 的用法詳解
下面小編就為大家?guī)?lái)一篇有關(guān)C++中隨機(jī)函數(shù)rand() 和srand() 的用法詳解。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-01-01C/C++詳解實(shí)現(xiàn)二層轉(zhuǎn)發(fā)
數(shù)據(jù)鏈路層是開放系統(tǒng)互連 (OSI) 模型中的第二層,該層用于通過(guò) LAN 等單一網(wǎng)絡(luò)進(jìn)行通信的節(jié)點(diǎn),第二層數(shù)據(jù)包不能從一個(gè)網(wǎng)絡(luò)傳輸?shù)搅硪粋€(gè)網(wǎng)絡(luò)。而二層轉(zhuǎn)發(fā)是根據(jù)報(bào)文的目的MAC直接進(jìn)行轉(zhuǎn)發(fā),轉(zhuǎn)發(fā)過(guò)程中不用對(duì)報(bào)文的頭部做任何的修改2022-05-05C++中高性能內(nèi)存池的實(shí)現(xiàn)詳解
在 C/C++ 中,內(nèi)存管理是一個(gè)非常棘手的問(wèn)題,我們?cè)诰帉懸粋€(gè)程序的時(shí)候幾乎不可避免的要遇到內(nèi)存的分配邏輯。本文將通過(guò)C++實(shí)現(xiàn)高性能內(nèi)存池,感興趣的可以了解一下2022-10-10C語(yǔ)言 fseek(f,0,SEEK_SET)函數(shù)案例詳解
這篇文章主要介紹了C語(yǔ)言 fseek(f,0,SEEK_SET)函數(shù)案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08