(C語言課件)第17部分 動態(tài)存儲空間管理與鏈表.ppt

1、2020/7/9,1,第十七 章動態(tài)存儲空間管理與鏈表,2020/7/9,2,一、動態(tài)存儲分配及常見函數(shù)說明,隱式和顯式,教師：林友芳,3,2020/7/9,1. 引例,要處理學(xué)生成績，需要用數(shù)組存放。但編程時并不知道運行時需要處理多少學(xué)生成績，每次處理的成績項數(shù)也可能不同。 int n; . scanf(%d, /* 不行！*/ . /* 讀入數(shù)據(jù)，然后處理 */ 不能用變量說明scores大?。ū仨氺o態(tài)確定）。,教師：林友芳,4,2020/7/9,2. 問題的本質(zhì)及解決方案,問題的本質(zhì) 程序運行中需要使用存儲，有時程序?qū)Υ鎯Φ男枨罅吭趯懗绦驎r不能確定。 可能解決方案 1）分析問題，定義適當(dāng)

2、大小的數(shù)組。若分析正確，一般都能處理。但數(shù)據(jù)很多時程序就不能用。 2）定義盡可能大的數(shù)組以滿足任何需要。浪費大量存儲資源。如有多個這種數(shù)組就更難辦。系統(tǒng)可能無法容納幾個大數(shù)組，但實際上它們并不同時需要很大空間。 解決的辦法是“動態(tài)存儲分配”。在程序運行中做存儲分配工作。,教師：林友芳,5,2020/7/9,3. 動態(tài)存儲分配,動態(tài)存儲分配 根據(jù)運行中的需要分配存儲，取得存儲塊使用，稱為動態(tài)存儲分配。在運行中根據(jù)需要動態(tài)進行。 動態(tài)存儲塊具有起始地址，地址可以存儲在指針里，因此可以借助于指針保存存儲空間地址。 用指針指向存儲塊，間接使用被指存儲。訪問動態(tài)分配存儲是指針的最重要用途。,教師：林友芳

3、,6,2020/7/9,4. 動態(tài)存儲釋放及存儲堆,動態(tài)釋放 不用的動態(tài)存儲塊應(yīng)交還系統(tǒng)，動態(tài)申請的內(nèi)存空間必須由程序代碼以顯式的方式主動釋放。 動態(tài)分配、釋放由動態(tài)存儲管理系統(tǒng)完成，這是程序運行系統(tǒng)的子系統(tǒng)，管理著稱作堆（英文heap）的存儲區(qū)。 大部分常規(guī)語言都有這種機制。,教師：林友芳,7,2020/7/9,5. C語言的動態(tài)存儲管理機制,用標準庫函數(shù)實現(xiàn) stdlib.h malloc.h 存儲分配函數(shù)malloc()，原型： void *malloc(size_t n); /*size_t是某整型*/ 功能 分配一塊不小于n的存儲，返回其地址。無法滿足時返回空指針值。,教師：林友芳,

4、8,2020/7/9,例,int n; double *data; . scanf(%d, if (data = NULL) . /* 分配未完成時的處理 */ .datai.*(data+j)./*正常處理*/,教師：林友芳,9,2020/7/9,malloc說明,malloc使用注意事項： 的返回值（void*）應(yīng)通過類型強制轉(zhuǎn)為特定指針類型后賦給指針變量。 分配存儲塊大小應(yīng)該用sizeof計算 動態(tài)分配必須檢查成功與否 動態(tài)分配的塊大小也是確定的。越界使用（尤其是越界賦值）是嚴重錯誤，可能導(dǎo)致程序或系統(tǒng)垮臺,教師：林友芳,10,2020/7/9,6. calloc,帶計數(shù)和清0的存儲分配

5、函數(shù)calloc，原型： void *calloc(size_t n, size_t size); size是元素大小，n是個數(shù)。 分配一塊存儲，足夠存n個大小為size的元素，并把元素全部清0； 無法分配時返回空指針值。前面的存儲分配問題也可用下面語句實現(xiàn) data = (double*)calloc(n, sizeof(double); 主要差別 malloc對所分配的區(qū)域不做任何事情，calloc對整個區(qū)域自動清0。,教師：林友芳,11,2020/7/9,7. 空間釋放函數(shù)：free,為保證動態(tài)存儲的有效使用，動態(tài)分配塊不再用時應(yīng)釋放。動態(tài)存儲塊的釋放只能通過調(diào)用free完成。Memor

6、y leak 函數(shù)原型 void free(void *p); 功能 free釋放p指的存儲塊。 注意 該塊必須是通過動態(tài)存儲分配得到的，不要對并非指向動態(tài)分配塊的指針用本操作 p值為空時什么也不做 執(zhí)行free(p)后p值未變，被指塊可能已變。不允許再間接訪問已釋放存儲塊,教師：林友芳,12,2020/7/9,8. 分配調(diào)整函數(shù)realloc,函數(shù)原型 void *realloc(void *p, size_t n); 功能 更改已有分配。p指原分配塊，n是新大小要求。 返回大小至少為n的存儲塊指針，新塊與原塊一致： 新塊小時保存原塊n范圍內(nèi)數(shù)據(jù)； 新塊大時原數(shù)據(jù)存在，新增部分不初始化。分配

7、成功后原塊可能改變。 無法滿足時返回空指針，原塊不變。 常用寫法(防止分配失敗導(dǎo)致原存儲塊丟失) ： q = (double*)realloc(p, m * sizeof(double); if (q = NULL) /*未成功，p仍指原塊，特殊處理*/ else p = q; /* 令p指向新塊，正常處理 */ .,2020/7/9,13,二、動態(tài)存儲空間管理,如果動態(tài)申請了許多同類型緩沖區(qū)，該如何管理？,教師：林友芳,14,2020/7/9,方法1：指針數(shù)組（地址數(shù)組）,設(shè)置一段內(nèi)存空間，例如數(shù)組，用來保存存儲空間的起始地址。 數(shù)組中每個元素用來保存某種類型的存儲空間的地址，等于每個元素都

8、是一個指針變量。 int *pnarr10; /定義一個長度為10的整型指針數(shù)組（整型地址數(shù)組） char *psz5; /定義一個長度為5的字符指針數(shù)組。,其中每個元素都用來保存某種類型的存儲空間的地址,教師：林友芳,15,2020/7/9,例如,設(shè)一個班最多有50人，但每個班的人數(shù)不定，為了表示這50用戶，可以定義如下指針數(shù)組 struct UserAccount *Accounts 50; 完成如下功能 初始化指針數(shù)組 將新生成的某個班用戶加入班級用戶集，并存放在空位置上。 將某個班指定用戶號的用戶刪除 給某個班所有女生發(fā)m元補助 將新生成的某個班用戶插入到指定位置i上，i后面的用戶順序

9、往后退。,教師：林友芳,16,2020/7/9,指針數(shù)組結(jié)構(gòu)示例,0 x0012ff6d,0 x0012ff80,0 x0012ce00,0 x0012fe12,長度為50,空指針，可能曾被刪除,后續(xù)元素或空或不空,Accounts,教師：林友芳,17,2020/7/9,功能實現(xiàn),初始化指針數(shù)組 void InitAccounts(struct UserAccount *Accounts, int nLen) for (int i = 0; i nLen; i+) Accountsi = NULL; 尋找一個空位置返回，-1表示無空位置 int FindEmptyPlace(struct Us

10、erAccount *Accounts, int nLen) /可以有不同的搜索策略,教師：林友芳,18,2020/7/9,功能實現(xiàn)（續(xù)）,將新用戶放在空位置上，不成功返回-1，成功返回位置號 int AddNewAccountAtAnyEmptyPlace(struct UserAccount *Accounts, int nLen, struct UserAccount *pUser) int nPlace; if (nPlace = FindEmptyPlace(Accounts, nLen) = -1) return -1; AccountsnPlace = pUser; /完成放置操

11、作 return nPlace; /返回位置 ,教師：林友芳,19,2020/7/9,功能示例,0 x0012ff6d,0 x0012ff80,0 x0012ce00,0 x0012fe12,長度為50,Accounts,0 x0012ff30,0 x0012ff30,新找到的空位,新結(jié)點,孫悟空報到,教師：林友芳,20,2020/7/9,功能實現(xiàn)（續(xù)）,將指定用戶號的用戶刪除，返回該用戶原來所在位置 int DeleteAccountByNumber(struct UserAccount *Accounts, int nLen, char *pszUserNO) int i; for (i

12、= 0; i szUserNO) = 0) free(Accountsi); /釋放空間 Accountsi = NULL; /將當(dāng)前位置置空 return i; return -1; ,用戶結(jié)構(gòu)體指針數(shù)組 數(shù)組長度 用戶號,字符串比較函數(shù),教師：林友芳,21,2020/7/9,刪除功能示例,0 x0012ff6d,0 x0012ff80,0 x0012ce00,0 x0012fe12,Accounts,0 x0012ff30,NULL,把孫悟空位置找到,把孫悟空開除: DeleteAccountByNumber(Accounts, 50, “08120100”),釋放存儲空間,教師：林友芳,

13、22,2020/7/9,功能實現(xiàn)（續(xù)）,給指定性別的群體充值，返回充值人數(shù) int ChargeByGender(struct UserAccount *Accounts, int nLen, char cGender, double dAmount) int nCounter = 0; /計數(shù)器 for (int i = 0; i cGender = cGender) Accountsi-dBalance+= dAmount; nCounter+; return nCounter; ChargeByGender(Accounts, 50, F, 10.0);/婦女節(jié)發(fā)補助,教師：林友芳,23

14、,2020/7/9,方法2：鏈接結(jié)構(gòu),采用鏈式數(shù)據(jù)結(jié)構(gòu) 一環(huán)扣一扣，通過一個元素保存的其它元素的地址找到其它元素。 通過鏈接結(jié)構(gòu)實現(xiàn)動態(tài)數(shù)據(jù) 增加元素：在鐵鏈的某個位置加一鐵環(huán) 刪除元素：去掉鐵鏈的某一鐵環(huán) 問題 鐵鏈中的每一鐵環(huán)是一樣的嗎？ 普通的鐵鏈是單向的還是雙向的？ 有沒有一些特殊的鐵鏈，比如有多個分叉的？ 鐵鏈可以跟銅鏈拴一起嗎？ 鐵鏈的頭部可以拴在柱子上嗎？,教師：林友芳,24,2020/7/9,鏈接結(jié)構(gòu)實現(xiàn)原理,鏈接結(jié)構(gòu)中的元素需要保存的信息 與結(jié)點本身有關(guān)的信息 找到其它元素所需要的信息 這些信息可以組織成結(jié)構(gòu) 問題：如何找到其它元素？ 保存其它元素在內(nèi)存中的地址 在結(jié)構(gòu)中設(shè)置

15、指針分量，用來保存其它元素的地址的分量指針分量 問題：指針的類型？ 需要指向元素的結(jié)構(gòu)類型的指針類型 如果需要指向的元素與本元素的類型相同的話，則需要定義自引用的結(jié)構(gòu)類型。,教師：林友芳,25,2020/7/9,鏈接結(jié)構(gòu),一個結(jié)構(gòu)元素可以通過指針引用同類或不同類的結(jié)構(gòu)元素，多個結(jié)構(gòu)元素通過指針建立聯(lián)系。 指向結(jié)構(gòu)的指針稱為鏈接，形成的復(fù)雜數(shù)據(jù)結(jié)構(gòu)稱為鏈接結(jié)構(gòu) 最簡單的鏈接結(jié)構(gòu) 線性鏈接形成的表，鏈接表。 每個自引用結(jié)構(gòu)有一個鏈接指針分量。,教師：林友芳,26,2020/7/9,最簡單的鏈接結(jié)構(gòu)：單向鏈表,單向鏈接表就像鏈條，自引用結(jié)構(gòu)是鏈表中的一個鏈節(jié)，稱為鏈表結(jié)點，結(jié)點間由指針連接形成整個結(jié)

16、構(gòu)。 所有結(jié)點（結(jié)構(gòu)）由動態(tài)分配創(chuàng)建。 從指向表首結(jié)點的指針出發(fā)，沿鏈接可順序訪問表中各結(jié)點。該指針代表整個表。通常把最后結(jié)點的指針置空表示結(jié)束。,教師：林友芳,27,2020/7/9,更復(fù)雜的引用鏈接結(jié)構(gòu),教師：林友芳,28,2020/7/9,單向鏈表結(jié)構(gòu)示例,struct UserAccount char UserNO15; char Name20; char ID19; char Gender; double Balance; struct UserAccount *pNextUser; ;,用來保存下一個結(jié)點的地址,此處改成如下形式是否可行，為什么？ struct UserAccoun

17、t NextUser;,教師：林友芳,29,2020/7/9,普通單向鏈表示意圖,2020/7/9,30,三、鏈表,教師：林友芳,31,2020/7/9,1. 需求,設(shè)有某系統(tǒng)的用戶信息結(jié)構(gòu)體，其中 用戶ID長度為10 用戶姓名長度不超過10 需要處理的用戶數(shù)據(jù)不定， 假設(shè)某程序需要以鏈表方式處理用戶的數(shù)據(jù),教師：林友芳,32,2020/7/9,普通單向鏈表示意,教師：林友芳,33,2020/7/9,鏈表結(jié)點結(jié)構(gòu)聲明,方法1: struct UserInfoNode char szID11;/ID char szName11;/姓名 struct UserInfoNode *pNextUser

18、; /下個用戶指針 ; 方法2： typedef struct UserInfoNode USERNODE, *USERPOINTER; struct UserInfoNode char szID11;/ID char szName11;/姓名 USERPOINTER *pNextUser;/下個用戶指針 ;,教師：林友芳,34,2020/7/9,更好的方法：基本信息單獨說明,/用戶基本信息結(jié)構(gòu)聲明 struct UserInfo char szID11;/ID，11個字符 char szName11;/姓名，11個字符 ; 或 typedef struct char szID11;/ID，1

19、1個字符 char szName11;/姓名，11個字符 USERINFO;,教師：林友芳,35,2020/7/9,更常見合理的聲明方法,方法3： struct UserLinkNode struct UserInfo Data;/數(shù)據(jù) struct UserLinkNode *pNextUser; / ; struct UserInfo UserInfoArr100; 或 typedef struct USERINFO Data;/數(shù)據(jù)結(jié)點 struct UserLinkNode *pNextUser; / USERLINKNODE ;,教師：林友芳,36,2020/7/9,增加一個鏈表描述

20、信息結(jié)點,LinkInfoNode,關(guān)于鏈表整體描述信息結(jié)點,教師：林友芳,37,2020/7/9,描述結(jié)點結(jié)構(gòu)說明示例,struct UserLink struct UserLinkNode *pHead; /頭指針 struct UserLinkNode *pTail; /尾指針 int nNumber;/鏈表中的結(jié)點計數(shù) ; 或 typedef struct USERLINKNODE *pHead; /頭指針 USERLINKNODE *pTail; /尾指針 int nNumber;/鏈表中的結(jié)點計數(shù) USERLINK;,教師：林友芳,38,2020/7/9,可以增加一個不用的頭結(jié)點,

21、LinkInfoNode,目的在于寫程序方便，簡化一些鏈表操作，數(shù)據(jù)結(jié)構(gòu)課程中會有進一步的闡述,不用的頭結(jié)點,教師：林友芳,39,2020/7/9,關(guān)于后面的操作的假定,鏈表為單向鏈表 沒有設(shè)置空的頭結(jié)點 設(shè)置有信息描述結(jié)點，記錄如下信息 頭結(jié)點 尾結(jié)點 鏈表中結(jié)點個數(shù),教師：林友芳,40,2020/7/9,在鏈表中增加一個節(jié)點,有幾種增加方式 將新結(jié)點作為最后一個元素增加到鏈表的尾部， 將新結(jié)點作為第一個元素增加到鏈表的頭部 將新結(jié)點按照某種次序要求插入到指定位置,教師：林友芳,41,2020/7/9,加到尾部,如果鏈表為空，則需要做一些初始化工作，將新的結(jié)點當(dāng)成頭結(jié)點和尾結(jié)點 如果鏈表不為

22、空，則將該結(jié)點作為尾結(jié)點的下一個結(jié)點，修改尾結(jié)點指針。 如果沒有記錄尾結(jié)點指針，則需要從頭結(jié)點開始找到最后一個結(jié)點。,pHead,pTail,pNewNode,NULL,教師：林友芳,42,2020/7/9,示例代碼，加到尾部,int AddUserToTail( struct UserLink *pUsers, /鏈表描述信息指針 struct UserLinkNode *pNewUser/新結(jié)點指針) if (pUsers = NULL | pNewUser = NULL) return -1; if (pUsers-nNumber pHead = pNewUser; pUsers-pTa

23、il = pUsers-pHead; /頭尾指針指向同一個結(jié)點 else/把結(jié)點信息附到鏈表尾部 pUsers-pTail-pNext = pNewUser; /加到尾到 pUsers-pTail = pNewUser;/修改尾結(jié)點指針 pUsers-pTail-pNext = NULL;/最后一個結(jié)點的后繼置空 pUsers-nNumber+;/計數(shù)加1 return 0; ,教師：林友芳,43,2020/7/9,加到頭部,如果鏈表為空，則需要做一些初始化工作，將新的結(jié)點當(dāng)成頭結(jié)點和尾結(jié)點 如果鏈表不為空，需要將新結(jié)點的下一個結(jié)點置為原來的頭結(jié)點，并把新結(jié)點作為頭結(jié)點,pHead,pTail

24、,pNewNode,教師：林友芳,44,2020/7/9,示例代碼，加到頭部,int AddUserToHead( struct UserLink *pUsers, /鏈表描述信息指針 struct UserLinkNode *pNewUser/新結(jié)點指針) if (pUsers = NULL | pNewUser = NULL) return -1; if (pUsers-nNumber pHead = pNewUser; pUsers-pTail = pUsers-pHead; /頭尾指針指向同一個結(jié)點 pNewUser-pNext = NULL; else/把結(jié)點信息附到鏈表頭部 pUsers-pNewUser-pNext = pUsers-pHead ; /加到頭部 pUsers-pHead = pNewUser;/修改頭結(jié)點指針 pUsers-nNumber+;/計數(shù)加1 return 0; ,教師：林友芳,45,2020/7/9,在鏈表中插入一個新結(jié)點,基本操作 q-pNext = p-pNext; p-pNext = q; 其它用于保持鏈表指針完整性的操作。,功能示意,p,p,q,q,r,r,插入前,插入后,教師：林友芳,46,2020/7/9,去除鏈表中的某個結(jié)點,基本操作 p-pNext = q-pNext; 外