(C語(yǔ)言課件) 動(dòng)態(tài)存儲(chǔ)空間管理與鏈表

1、2022-1-21第十七第十七 章章動(dòng)態(tài)存儲(chǔ)空間管理與動(dòng)態(tài)存儲(chǔ)空間管理與鏈表鏈表2022-1-22一、動(dòng)態(tài)存儲(chǔ)分配及常見(jiàn)函數(shù)說(shuō)明隱式和顯式北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳32022-1-21. 引例n要處理學(xué)生成績(jī)，需要用數(shù)組存放。但編程時(shí)并不知道運(yùn)行時(shí)需要處理多少學(xué)生成績(jī)，每次處理的成績(jī)項(xiàng)數(shù)也可能不同。nint n;n.nscanf(%d, &n);ndouble scoresn; /* 不行！*/n. /* 讀入數(shù)據(jù)，然后處理 */n不能用變量說(shuō)明scores大小（必須靜態(tài)確定）。北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳42022-1-22. 問(wèn)題的本質(zhì)及解決方案n

2、問(wèn)題的本質(zhì)n程序運(yùn)行中需要使用存儲(chǔ)，有時(shí)程序?qū)Υ鎯?chǔ)的需求量在寫程序時(shí)不能確定。n可能解決方案1）分析問(wèn)題，定義適當(dāng)大小的數(shù)組。若分析正確，一般都能處理。但數(shù)據(jù)很多時(shí)程序就不能用。2）定義盡可能大的數(shù)組以滿足任何需要。浪費(fèi)大量存儲(chǔ)資源。如有多個(gè)這種數(shù)組就更難辦。系統(tǒng)可能無(wú)法容納幾個(gè)大數(shù)組，但實(shí)際上它們并不同時(shí)需要很大空間。n解決的辦法是“動(dòng)態(tài)存儲(chǔ)分配”。在程序運(yùn)行中做存儲(chǔ)分配工作。北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳52022-1-23. 動(dòng)態(tài)存儲(chǔ)分配n動(dòng)態(tài)存儲(chǔ)分配n根據(jù)運(yùn)行中的需要分配存儲(chǔ)，取得存儲(chǔ)塊使用，稱為動(dòng)態(tài)存儲(chǔ)分配。在運(yùn)行中根據(jù)需要?jiǎng)討B(tài)進(jìn)行。n動(dòng)態(tài)存儲(chǔ)塊具有起始地址，地址可以存

3、儲(chǔ)在指針里，因此可以借助于指針保存存儲(chǔ)空間地址。n用指針指向存儲(chǔ)塊，間接使用被指存儲(chǔ)。訪問(wèn)動(dòng)態(tài)分配存儲(chǔ)是指針的最重要用途。北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳62022-1-24. 動(dòng)態(tài)存儲(chǔ)釋放及存儲(chǔ)堆n動(dòng)態(tài)釋放n不用的動(dòng)態(tài)存儲(chǔ)塊應(yīng)交還系統(tǒng)，動(dòng)態(tài)申請(qǐng)的內(nèi)存空間必須由程序代碼以顯式的方式主動(dòng)釋放。n動(dòng)態(tài)分配、釋放由動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)完成，這是程序運(yùn)行系統(tǒng)的子系統(tǒng)，管理著稱作堆（英文heap）的存儲(chǔ)區(qū)。n大部分常規(guī)語(yǔ)言都有這種機(jī)制。北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳72022-1-25. C語(yǔ)言的動(dòng)態(tài)存儲(chǔ)管理機(jī)制n用標(biāo)準(zhǔn)庫(kù)函數(shù)實(shí)現(xiàn)用標(biāo)準(zhǔn)庫(kù)函數(shù)實(shí)現(xiàn)nstdlib.hstdlib.hn

4、malloc.hmalloc.hn存儲(chǔ)分配函數(shù)存儲(chǔ)分配函數(shù)mallocmalloc() ()，原型：，原型：nvoid void * *malloc(size_tmalloc(size_t n); / n); /* *size_tsize_t是某整型是某整型* */ /n功能功能n分配一塊不小于分配一塊不小于n n的存儲(chǔ)，返回其地址。無(wú)法的存儲(chǔ)，返回其地址。無(wú)法滿足時(shí)返回空指針值。滿足時(shí)返回空指針值。北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳82022-1-2例intint n; double n; double * *data;data;. scanf(%d. scanf(%d, &

5、;n);, &n);data=(doubledata=(double* *)malloc(n)malloc(n* *sizeof(doublesizeof(double););if (data = NULL) if (data = NULL) . / . /* * 分配未完成時(shí)的處理分配未完成時(shí)的處理 * */ / .datai.datai.* *(data+j(data+j)./)./* *正常處理正常處理* */ /北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳92022-1-2malloc說(shuō)明nmalloc使用注意事項(xiàng)：n的返回值（void*）應(yīng)通過(guò)類型強(qiáng)制轉(zhuǎn)為特定指針類型后賦給指

6、針變量。n分配存儲(chǔ)塊大小應(yīng)該用sizeof計(jì)算n動(dòng)態(tài)分配必須檢查成功與否n動(dòng)態(tài)分配的塊大小也是確定的。越界使用（尤其是越界賦值）是嚴(yán)重錯(cuò)誤，可能導(dǎo)致程序或系統(tǒng)垮臺(tái)北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳102022-1-26. callocn帶計(jì)數(shù)和清帶計(jì)數(shù)和清0 0的存儲(chǔ)分配函數(shù)的存儲(chǔ)分配函數(shù)calloccalloc，原型：，原型：nvoid void * *calloc(size_tcalloc(size_t n, size_t size); n, size_t size);nsizesize是元素大小，是元素大小，n n是個(gè)數(shù)。是個(gè)數(shù)。n分配一塊存儲(chǔ)，足夠存分配一塊存儲(chǔ)，足夠存n n

7、個(gè)大小為個(gè)大小為sizesize的元素，并的元素，并把元素把元素全部清全部清0 0；n無(wú)法分配時(shí)返回空指針值。前面的存儲(chǔ)分配問(wèn)題無(wú)法分配時(shí)返回空指針值。前面的存儲(chǔ)分配問(wèn)題也可用下面語(yǔ)句實(shí)現(xiàn)也可用下面語(yǔ)句實(shí)現(xiàn)ndata = (doubledata = (double* *)calloc(n, sizeof(double)calloc(n, sizeof(double););n主要差別主要差別nmallocmalloc對(duì)所分配的區(qū)域不做任何事情，對(duì)所分配的區(qū)域不做任何事情，calloccalloc對(duì)整個(gè)區(qū)對(duì)整個(gè)區(qū)域自動(dòng)清域自動(dòng)清0 0。北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳112022-1-

8、27. 空間釋放函數(shù)：freen為保證動(dòng)態(tài)存儲(chǔ)的有效使用，動(dòng)態(tài)分配塊不再用時(shí)應(yīng)釋放。動(dòng)態(tài)存儲(chǔ)塊的釋放只能通過(guò)調(diào)用free完成。Memory leakn函數(shù)原型nvoid free(void *p);n功能nfree釋放p指的存儲(chǔ)塊。n注意n該塊必須是通過(guò)動(dòng)態(tài)存儲(chǔ)分配得到的，不要對(duì)并非指向動(dòng)態(tài)分配塊的指針用本操作np值為空時(shí)什么也不做n執(zhí)行free(p)后p值未變，被指塊可能已變。不允許再間接訪問(wèn)已釋放存儲(chǔ)塊北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳122022-1-28. 8. 分配調(diào)整函數(shù)分配調(diào)整函數(shù)reallocn函數(shù)原型nvoid *realloc(void *p, size_t n)

9、;n功能n更改已有分配。p指原分配塊，n是新大小要求。n返回大小至少為n的存儲(chǔ)塊指針，新塊與原塊一致：n新塊小時(shí)保存原塊n范圍內(nèi)數(shù)據(jù)；n新塊大時(shí)原數(shù)據(jù)存在，新增部分不初始化。分配成功后原塊可能改變。n無(wú)法滿足時(shí)返回空指針，原塊不變。n常用寫法(防止分配失敗導(dǎo)致原存儲(chǔ)塊丟失) ：nq = (double*)realloc(p, m * sizeof(double);nif (q = NULL) /*未成功，p仍指原塊，特殊處理*/ nelse p = q; /* 令p指向新塊，正常處理 */ .2022-1-213二、動(dòng)態(tài)存儲(chǔ)空間管理如果動(dòng)態(tài)申請(qǐng)了許多同類型緩沖區(qū)，該如何管理？北京交通大學(xué)計(jì)算機(jī)

10、與信息技術(shù)學(xué)院教師：林友芳142022-1-2方法1：指針數(shù)組（地址數(shù)組）n設(shè)置一段內(nèi)存空間，例如數(shù)組，用來(lái)保存存儲(chǔ)空間的起始地址。n數(shù)組中每個(gè)元素用來(lái)保存某種類型的存儲(chǔ)空間的地址，等于每個(gè)元素都是一個(gè)指針變量。nint *pnarr10; /定義一個(gè)長(zhǎng)度為10的整型指針數(shù)組（整型地址數(shù)組）nchar *psz5; /定義一個(gè)長(zhǎng)度為5的字符指針數(shù)組。0 x0012ff7d0 x0012ff800 x0012fe12其中每個(gè)元素都用來(lái)保存某種類型的存儲(chǔ)空間的地址北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳152022-1-2例如n設(shè)一個(gè)班最多有50人，但每個(gè)班的人數(shù)不定，為了表示這50用戶，可以

11、定義如下指針數(shù)組nstruct UserAccount *Accounts 50;n完成如下功能n初始化指針數(shù)組n將新生成的某個(gè)班用戶加入班級(jí)用戶集，并存放在空位置上。n將某個(gè)班指定用戶號(hào)的用戶刪除n給某個(gè)班所有女生發(fā)m元補(bǔ)助n將新生成的某個(gè)班用戶插入到指定位置i上，i后面的用戶順序往后退。北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳162022-1-2指針數(shù)組結(jié)構(gòu)示例0 x0012ff6dNULL0 x0012ff800 x0012ce000 x0012fe1208120001 張帥帥110108M0.1008120099 李美美350108F500.0008120002 趙小飛360108

12、M20.0008120007 羅小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12長(zhǎng)度為50空指針，可能曾被刪除后續(xù)元素或空或不空Accounts北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳172022-1-2功能實(shí)現(xiàn)n初始化指針數(shù)組void InitAccounts(struct UserAccount *Accounts, int nLen) for (int i = 0; i nLen; i+) Accountsi = NULL;n尋找一個(gè)空位置返回，-1表示無(wú)空位置int FindEmptyPlace(struct Us

13、erAccount *Accounts, int nLen) /可以有不同的搜索策略NULLNULL北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳182022-1-2功能實(shí)現(xiàn)（續(xù)）n將新用戶放在空位置上，不成功返回-1，成功返回位置號(hào)int AddNewAccountAtAnyEmptyPlace(struct UserAccount *Accounts, int nLen, struct UserAccount *pUser) int nPlace;if (nPlace = FindEmptyPlace(Accounts, nLen) = -1) return -1; AccountsnPla

14、ce = pUser; /完成放置操作 return nPlace; /返回位置北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳192022-1-2功能示例0 x0012ff6dNULL0 x0012ff800 x0012ce000 x0012fe1208120001 張帥帥110108M0.1008120099 李美美350108F500.0008120002 趙小飛360108M20.0008120007 羅小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12長(zhǎng)度為50Accounts08120100 孫悟空110105M600.

15、100 x0012ff300 x0012ff30新找到的空位新結(jié)點(diǎn)孫悟空?qǐng)?bào)到北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳202022-1-2功能實(shí)現(xiàn)（續(xù)）n將指定用戶號(hào)的用戶刪除，返回該用戶原來(lái)所在位置int DeleteAccountByNumber(struct UserAccount *Accounts, int nLen, char *pszUserNO) int i; for (i = 0; i szUserNO) = 0) free(Accountsi); /釋放空間 Accountsi = NULL; /將當(dāng)前位置置空 return i; return -1;用戶結(jié)構(gòu)體指針數(shù)組數(shù)

16、組長(zhǎng)度用戶號(hào)字符串比較函數(shù)北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳212022-1-2刪除功能示例0 x0012ff6d0 x0012ff300 x0012ff800 x0012ce000 x0012fe1208120001 張帥帥110108M0.1008120099 李美美350108F500.0008120002 趙小飛360108M20.0008120007 羅小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12Accounts08120100 孫悟空110105M600.100 x0012ff30NULL把孫悟空位置

17、找到把孫悟空開(kāi)除:DeleteAccountByNumber(Accounts, 50, “08120100”)釋放存儲(chǔ)空間北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳222022-1-2功能實(shí)現(xiàn)（續(xù)）n給指定性別的群體充值，返回充值人數(shù)int ChargeByGender(struct UserAccount *Accounts, int nLen, char cGender, double dAmount) int nCounter = 0; /計(jì)數(shù)器 for (int i = 0; i cGender = cGender) Accountsi-dBalance+= dAmount; nC

18、ounter+; return nCounter;ChargeByGender(Accounts, 50, F, 10.0);/婦女節(jié)發(fā)補(bǔ)助北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳232022-1-2方法2：鏈接結(jié)構(gòu)n采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)n一環(huán)扣一扣，通過(guò)一個(gè)元素保存的其它元素的地址找到其它元素。n通過(guò)鏈接結(jié)構(gòu)實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)n增加元素：在鐵鏈的某個(gè)位置加一鐵環(huán)n刪除元素：去掉鐵鏈的某一鐵環(huán)n問(wèn)題n鐵鏈中的每一鐵環(huán)是一樣的嗎？n普通的鐵鏈?zhǔn)菃蜗虻倪€是雙向的？n有沒(méi)有一些特殊的鐵鏈，比如有多個(gè)分叉的？n鐵鏈可以跟銅鏈拴一起嗎？n鐵鏈的頭部可以拴在柱子上嗎？北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳

19、242022-1-2鏈接結(jié)構(gòu)實(shí)現(xiàn)原理n鏈接結(jié)構(gòu)中的元素需要保存的信息n與結(jié)點(diǎn)本身有關(guān)的信息n找到其它元素所需要的信息n這些信息可以組織成結(jié)構(gòu)n問(wèn)題：如何找到其它元素？n保存其它元素在內(nèi)存中的地址n在結(jié)構(gòu)中設(shè)置指針?lè)至?，用?lái)保存其它元素的地址的分量指針?lè)至縩問(wèn)題：指針的類型？n需要指向元素的結(jié)構(gòu)類型的指針類型n如果需要指向的元素與本元素的類型相同的話，則需要定義自引用的結(jié)構(gòu)類型。北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳252022-1-2鏈接結(jié)構(gòu)n一個(gè)結(jié)構(gòu)元素可以通過(guò)指針引用同類或不同類的結(jié)構(gòu)元素，多個(gè)結(jié)構(gòu)元素通過(guò)指針建立聯(lián)系。n指向結(jié)構(gòu)的指針?lè)Q為鏈接，形成的復(fù)雜數(shù)據(jù)結(jié)構(gòu)稱為鏈接結(jié)構(gòu)n最簡(jiǎn)單

20、的鏈接結(jié)構(gòu)n線性鏈接形成的表，鏈接表。n每個(gè)自引用結(jié)構(gòu)有一個(gè)鏈接指針?lè)至俊１本┙煌ù髮W(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳262022-1-2最簡(jiǎn)單的鏈接結(jié)構(gòu)：?jiǎn)蜗蜴湵韓單向鏈接表就像鏈條，自引用結(jié)構(gòu)是鏈表中的一個(gè)鏈節(jié)，稱為鏈表結(jié)點(diǎn)，結(jié)點(diǎn)間由指針連接形成整個(gè)結(jié)構(gòu)。n所有結(jié)點(diǎn)（結(jié)構(gòu)）由動(dòng)態(tài)分配創(chuàng)建。n從指向表首結(jié)點(diǎn)的指針出發(fā)，沿鏈接可順序訪問(wèn)表中各結(jié)點(diǎn)。該指針代表整個(gè)表。通常把最后結(jié)點(diǎn)的指針置空表示結(jié)束。0北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳272022-1-200000000更復(fù)雜的引用鏈接結(jié)構(gòu)北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳282022-1-2單向鏈表結(jié)構(gòu)示例struct U

21、serAccount char UserNO15; char Name20; char ID19; char Gender; double Balance;struct UserAccount *pNextUser;用來(lái)保存下一個(gè)結(jié)點(diǎn)的地址此處改成如下形式是否可行，為什么？struct UserAccount NextUser;北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳292022-1-2普通單向鏈表示意圖08120001 張帥帥110108M0.1008120002 趙小飛360108M20.0008120007 羅小花410108F88.2008120099 李美美350108F500.

22、00NULLHeadTail2022-1-230三、鏈表北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳312022-1-21. 需求n設(shè)有某系統(tǒng)的用戶信息結(jié)構(gòu)體，其中n用戶ID長(zhǎng)度為10n用戶姓名長(zhǎng)度不超過(guò)10n需要處理的用戶數(shù)據(jù)不定，n假設(shè)某程序需要以鏈表方式處理用戶的數(shù)據(jù)北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳322022-1-2普通單向鏈表示意DataDataDataDataNULLHeadTail北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳332022-1-2鏈表結(jié)點(diǎn)結(jié)構(gòu)聲明方法1:struct UserInfoNodechar szID11;/IDchar szName11;/姓名

23、 struct UserInfoNode *pNextUser; /下個(gè)用戶指針;方法2：typedef struct UserInfoNode USERNODE, *USERPOINTER;struct UserInfoNodechar szID11;/IDchar szName11;/姓名 USERPOINTER *pNextUser;/下個(gè)用戶指針;北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳342022-1-2更好的方法：基本信息單獨(dú)說(shuō)明/用戶基本信息結(jié)構(gòu)聲明struct UserInfochar szID11;/ID，11個(gè)字符個(gè)字符char szName11;/姓名，姓名，11個(gè)字

24、符個(gè)字符;或typedef structchar szID11;/ID，11個(gè)字符個(gè)字符char szName11;/姓名，姓名，11個(gè)字符個(gè)字符 USERINFO;北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳352022-1-2更常見(jiàn)合理的聲明方法方法3：struct UserLinkNode struct UserInfo Data;/數(shù)據(jù)數(shù)據(jù) struct UserLinkNode *pNextUser; /;struct UserInfo UserInfoArr100;或typedef struct USERINFO Data;/數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn) struct UserLinkNode

25、 *pNextUser; / USERLINKNODE ;北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳362022-1-2增加一個(gè)鏈表描述信息結(jié)點(diǎn)NumberHeadTailDataDataDataDataNULLLinkInfoNoden關(guān)于鏈表整體描述信息結(jié)點(diǎn)北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳372022-1-2描述結(jié)點(diǎn)結(jié)構(gòu)說(shuō)明示例struct UserLinkstruct UserLinkNode *pHead; /頭指針頭指針 struct UserLinkNode *pTail; /尾指針尾指針int nNumber;/鏈表中的結(jié)點(diǎn)計(jì)數(shù)鏈表中的結(jié)點(diǎn)計(jì)數(shù);或typedef s

26、truct USERLINKNODE *pHead; /頭指針頭指針 USERLINKNODE *pTail; /尾指針尾指針int nNumber;/鏈表中的結(jié)點(diǎn)計(jì)數(shù)鏈表中的結(jié)點(diǎn)計(jì)數(shù) USERLINK;北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳382022-1-2可以增加一個(gè)不用的頭結(jié)點(diǎn)NumberHeadTailDataDataDataNULLLinkInfoNoden目的在于寫程序方便，簡(jiǎn)化一些鏈表操作，數(shù)據(jù)結(jié)構(gòu)課程中會(huì)有進(jìn)一步的闡述不用的不用的頭結(jié)點(diǎn)頭結(jié)點(diǎn)北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳392022-1-2關(guān)于后面的操作的假定n鏈表為單向鏈表n沒(méi)有設(shè)置空的頭結(jié)點(diǎn)n設(shè)置有信

27、息描述結(jié)點(diǎn)，記錄如下信息n頭結(jié)點(diǎn)n尾結(jié)點(diǎn)n鏈表中結(jié)點(diǎn)個(gè)數(shù)北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳402022-1-2在鏈表中增加一個(gè)節(jié)點(diǎn)n有幾種增加方式n將新結(jié)點(diǎn)作為最后一個(gè)元素增加到鏈表的尾部，n將新結(jié)點(diǎn)作為第一個(gè)元素增加到鏈表的頭部n將新結(jié)點(diǎn)按照某種次序要求插入到指定位置北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳412022-1-2加到尾部n如果鏈表為空，則需要做一些初始化工作，將新的結(jié)點(diǎn)當(dāng)成頭結(jié)點(diǎn)和尾結(jié)點(diǎn)n如果鏈表不為空，則將該結(jié)點(diǎn)作為尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，修改尾結(jié)點(diǎn)指針。n如果沒(méi)有記錄尾結(jié)點(diǎn)指針，則需要從頭結(jié)點(diǎn)開(kāi)始找到最后一個(gè)結(jié)點(diǎn)。pHeadpTailDataDataNULLpNe

28、wNode NULL 北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳422022-1-2示例代碼，加到尾部int AddUserToTail( struct UserLink *pUsers, /鏈表描述信息指針 struct UserLinkNode *pNewUser/新結(jié)點(diǎn)指針) if (pUsers = NULL | pNewUser = NULL) return -1;if (pUsers-nNumber pHead = pNewUser; pUsers-pTail = pUsers-pHead; /頭尾指針指向同一個(gè)結(jié)點(diǎn) else/把結(jié)點(diǎn)信息附到鏈表尾部 pUsers-pTail-p

29、Next = pNewUser; /加到尾到 pUsers-pTail = pNewUser;/修改尾結(jié)點(diǎn)指針 pUsers-pTail-pNext = NULL;/最后一個(gè)結(jié)點(diǎn)的后繼置空pUsers-nNumber+;/計(jì)數(shù)加1return 0;北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳432022-1-2加到頭部n如果鏈表為空，則需要做一些初始化工作，將新的結(jié)點(diǎn)當(dāng)成頭結(jié)點(diǎn)和尾結(jié)點(diǎn)n如果鏈表不為空，需要將新結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)置為原來(lái)的頭結(jié)點(diǎn)，并把新結(jié)點(diǎn)作為頭結(jié)點(diǎn)pHeadpTailDataDataNULLNULLpNewNode 北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林友芳442022-1-

30、2示例代碼，加到頭部int AddUserToHead( struct UserLink *pUsers, /鏈表描述信息指針 struct UserLinkNode *pNewUser/新結(jié)點(diǎn)指針) if (pUsers = NULL | pNewUser = NULL) return -1;if (pUsers-nNumber pHead = pNewUser; pUsers-pTail = pUsers-pHead; /頭尾指針指向同一個(gè)結(jié)點(diǎn) pNewUser-pNext = NULL; else/把結(jié)點(diǎn)信息附到鏈表頭部 pUsers-pNewUser-pNext = pUsers-pHead ; /加到頭部 pUsers-pHead = pNewUser;/修改頭結(jié)點(diǎn)指針 pUsers-nNumber+;/計(jì)數(shù)加1return 0;北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教師：林