(c語言課件)第17部分動(dòng)態(tài)存儲(chǔ)空間管理與鏈表-閱讀頁
2025-03-23 19:18本頁面
【正文】 1/21/2023 23 教師：林友芳 北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 鏈接結(jié)構(gòu)實(shí)現(xiàn)原理 ? 鏈接結(jié)構(gòu)中的元素需要保存的信息 ? 與結(jié)點(diǎn)本身有關(guān)的信息 ? 找到其它元素所需要的信息 ? 這些信息可以組織成結(jié)構(gòu) ? 問題：如何找到其它元素？ ? 保存其它元素在內(nèi)存中的地址 ? 在結(jié)構(gòu)中設(shè)臵指針分量，用來保存其它元素的地址的分量指針分量 ? 問題：指針的類型？ ? 需要指向元素的結(jié)構(gòu)類型的指針類型 ? 如果需要指向的元素與本元素的類型相同的話，則需要定義自引用的結(jié)構(gòu)類型。 ? 指向結(jié)構(gòu)的指針稱為鏈接，形成的復(fù)雜數(shù)據(jù)結(jié)構(gòu)稱為鏈接結(jié)構(gòu) ? 最簡(jiǎn)單的鏈接結(jié)構(gòu) ? 線性鏈接形成的表， 鏈接表 。 1/21/2023 25 教師：林友芳 北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 最簡(jiǎn)單的鏈接結(jié)構(gòu)：?jiǎn)蜗蜴湵? ? 單向鏈接表就像鏈條，自引用結(jié)構(gòu)是鏈表中的一個(gè)鏈節(jié)，稱為鏈表結(jié)點(diǎn)，結(jié)點(diǎn)間由指針連接形成整個(gè)結(jié)構(gòu)。 ? 從指向表首結(jié)點(diǎn)的指針出發(fā)，沿鏈接可順序訪問表中各結(jié)點(diǎn)。通常把最后結(jié)點(diǎn)的指針臵空表示結(jié)束。 char Name[20]。 char Gender。 struct UserAccount *pNextUser。 用來保存下一個(gè)結(jié)點(diǎn)的地址 此處改成如下形式是否可行，為什么？ struct UserAccount NextUser。 //ID char szName[11]。 //下個(gè)用戶指針 }。 struct UserInfoNode { char szID[11]。 //姓名 USERPOINTER *pNextUser。 1/21/2023 33 教師：林友芳 北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 更好的方法：基本信息單獨(dú)說明 //用戶基本信息結(jié)構(gòu)聲明 struct UserInfo { char szID[11]。 //姓名， 11個(gè)字符 }。 //ID， 11個(gè)字符 char szName[11]。 1/21/2023 34 教師：林友芳 北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 更常見合理的聲明方法 方法 3： struct UserLinkNode { struct UserInfo Data。 // }。 或 typedef struct { USERINFO Data。 // } USERLINKNODE 。 //頭指針 struct UserLinkNode *pTail。 //鏈表中的結(jié)點(diǎn)計(jì)數(shù) }。 //頭指針 USERLINKNODE *pTail。 //鏈表中的結(jié)點(diǎn)計(jì)數(shù) } USERLINK。 ? 如果沒有記錄尾結(jié)點(diǎn)指針，則需要從頭結(jié)點(diǎn)開始找到最后一個(gè)結(jié)點(diǎn)。 if (pUsersnNumber = 0) { //如果還沒有元素 pUserspHead = pNewUser。 //頭尾指針指向同一個(gè)結(jié)點(diǎn) } else{//把結(jié)點(diǎn)信息附到鏈表尾部 pUserspTailpNext = pNewUser。 //修改尾結(jié)點(diǎn)指針 } pUserspTailpNext = NULL。//計(jì)數(shù)加 1 return 0。 if (pUsersnNumber = 0) { //如果還沒有元素 pUserspHead = pNewUser。 //頭尾指針指向同一個(gè)結(jié)點(diǎn) pNewUserpNext = NULL。 //加到頭部 pUserspHead = pNewUser。//計(jì)數(shù)加 1 return 0。 ? ppNext = q。 ^ ^ 功能示意 p p q q r r 插入前 插入后 1/21/2023 45 教師：林友芳 北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 去除鏈表中的某個(gè)結(jié)點(diǎn) ? 基本操作 ? ppNext = qpNext。 ? 如：如果刪除的是最后一個(gè)結(jié)點(diǎn)的話，需要修改尾指針 功能示意 p q r p r q 1/21/2023 46 教師：林友芳 北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 遍歷鏈表 ? 常見功能 ? 遍歷鏈表逐個(gè)訪問所有結(jié)點(diǎn)，進(jìn)行相應(yīng)的處理，如將所有用戶的某項(xiàng)指標(biāo)求和，輸出所有用戶的信息 ? 查找某個(gè)或某些符合給定條件的結(jié)點(diǎn)，進(jìn)行相應(yīng)處理 ? … 1/21/2023 47 教師：林友芳 北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 示例代碼 : 輸出所有元素 int ShowData(struct UserLink *pUsers) { struct UserLinkNode *pNode。 for ( pNode = pUserspHead。 //判斷當(dāng)前結(jié)點(diǎn)是否為空 pNode = pNodepNext //準(zhǔn)備處理下一個(gè)結(jié)點(diǎn) ) { //對(duì)每個(gè)結(jié)點(diǎn)出輸出信息 printf( %11s\t%11s\t\n, pNode, pNode, } return 0。 if (pHead == NULL) return 1。 //從第一個(gè)元素開始 pNode != NULL。 } 1/21/2023 49 教師：林友芳 北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 本章內(nèi)容 ? 動(dòng)態(tài)存儲(chǔ)分配及其函數(shù) ? 動(dòng)態(tài)存儲(chǔ)空間管理方法 ? 鏈表概念 ? 鏈表的定義和基本操作 1/21/2023 50 教師：林友芳 本章結(jié)束 1/21/2023 51
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1