中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁(yè) > news >正文

建設(shè)廳執(zhí)業(yè)注冊(cè)中心網(wǎng)站官網(wǎng)設(shè)計(jì)比較好看的網(wǎng)站

建設(shè)廳執(zhí)業(yè)注冊(cè)中心網(wǎng)站,官網(wǎng)設(shè)計(jì)比較好看的網(wǎng)站,信息網(wǎng)站建設(shè)方案,wordpress安卓版教程視頻教程1、順序表遺留問(wèn)題 1. 中間/頭部的插入刪除,時(shí)間復(fù)雜度為O(N) 2. 增容需要申請(qǐng)新空間,使用malloc、realloc等函數(shù)拷貝數(shù)據(jù),釋放舊空間。會(huì)有不小的消耗。 3. 當(dāng)我們以2倍速度增容時(shí),勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100&a…

1、順序表遺留問(wèn)題

1. 中間/頭部的插入刪除,時(shí)間復(fù)雜度為O(N)
2. 增容需要申請(qǐng)新空間,使用malloc、realloc等函數(shù)拷貝數(shù)據(jù),釋放舊空間。會(huì)有不小的消耗。
3. 當(dāng)我們以2倍速度增容時(shí),勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100,滿了以后增容到200,若下次只是插入5個(gè)數(shù)據(jù),就會(huì)浪費(fèi)95個(gè)數(shù)據(jù)大小的空間。
為了改進(jìn)、彌補(bǔ)順序表的缺點(diǎn),我們發(fā)明了鏈表。

2、什么是鏈表

概念:物理順序:鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)。

???????????邏輯順序:是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

?

?3、接口函數(shù)以及結(jié)點(diǎn)的定義

typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SListNode;//單鏈表打印
void SLTPrint(SListNode* phead);
//尾插
void SLTPushBack(SListNode** pphead,SLTDataType x);
//創(chuàng)建一個(gè)新結(jié)點(diǎn)的函數(shù),并將新結(jié)點(diǎn)的數(shù)據(jù)初始化為x
SListNode* BuySLTNode(SLTDataType x);
//尾刪
void SLTPopBack(SListNode** pphead);
//頭插
void SLTPushFront(SListNode** pphead, SLTDataType x);
//頭刪
void SLTPopFront(SListNode** pphead);// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);// 單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);// 單鏈表刪除pos位置之后的值
void SListEraseAfter(SListNode* pos);//單鏈表在pos前面插入
void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x);//單鏈表在刪除在pos位置的值
void SListErasepos(SListNode** pphead, SListNode* pos);// 單鏈表的銷毀
void SListDestroy(SListNode* plist);

?為了方便,我們將鏈表的數(shù)據(jù)類型定義為int,同時(shí)定義一個(gè)struct ListNode*類型的指針next,用來(lái)指向下一個(gè)結(jié)點(diǎn)。

由于鏈表不需要事前申請(qǐng)一塊連續(xù)的空間,因此不需要初始化,只需定義一個(gè)SlistNode*類型的指針phead,作為鏈表的頭指針,指向這個(gè)鏈表。

4、鏈表的打印

//單鏈表打印
void SLTPrint(SListNode* phead)
{SListNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");}

創(chuàng)建一個(gè)cur指針變量指向頭結(jié)點(diǎn),然后用cur=cur->next來(lái)遍歷,打印完data后再到下一個(gè),直到打印完最后一個(gè)data,cur指向最后結(jié)點(diǎn)的next(指向NULL)。為了便于前期理解,最后打印一個(gè)NULL。下文插入操作后,演示打印效果。

5、創(chuàng)建(Buy)一個(gè)新結(jié)點(diǎn)

//創(chuàng)建一個(gè)新結(jié)點(diǎn)的函數(shù),并將新結(jié)點(diǎn)的數(shù)據(jù)初始化為x
SListNode* BuySLTNode(SLTDataType x)
{//建立一個(gè)新的結(jié)點(diǎn),并將data初始化,next置為NULLSListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (NULL == newnode){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}

先用malloc申請(qǐng)一個(gè)結(jié)點(diǎn)大小的空間,并將其交給一個(gè)newnode指針,確認(rèn)申請(qǐng)成功后,對(duì)newnodd進(jìn)行初始化,data=x,next置為NULL,(因?yàn)椴恢酪赶蚰睦?#xff0c;只是申請(qǐng)一個(gè)新結(jié)點(diǎn),next指向的問(wèn)題交給調(diào)用此函數(shù)的人來(lái)完成)。

然后將newnode返回,使用的人用某個(gè)結(jié)點(diǎn)的next指向它,就可以鏈接一個(gè)新結(jié)點(diǎn)。

6、尾插


//尾插
void SLTPushBack(SListNode** pphead,SLTDataType x)
{SListNode* tmp = BuySLTNode(x);if (NULL == tmp){return;}SListNode* newnode = tmp;//分情況,原來(lái)是否為空鏈表if (*pphead == NULL)//為空鏈表{*pphead = newnode;//建立phead與新結(jié)點(diǎn)的聯(lián)系}else{//先找到原來(lái)的尾結(jié)點(diǎn),然后建立其與新結(jié)點(diǎn)的聯(lián)系SListNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//找到原來(lái)的尾結(jié)點(diǎn)后tail->next = newnode;}}

鏈表是為了改進(jìn)順序表中頭插和中間插入效率而產(chǎn)生的,與順序表是互補(bǔ)關(guān)系,順序表尾插時(shí)直接插入即可,消耗很小。但鏈表尾插時(shí),需要先進(jìn)行找尾操作,然后再尾插新數(shù)據(jù)。

注意:第一個(gè)參數(shù)是SListNode** pphead,用來(lái)接收頭指針的地址,這是一次傳址調(diào)用,可以改變phead本身的內(nèi)容,由于phead是頭指針,改變的就是頭指針指向的內(nèi)容。

第一次尾插時(shí),phead指向NULL,利用*pphead使其指向新的第一個(gè)結(jié)點(diǎn)。

如果用一個(gè)SListNode* plist來(lái)接收,只是phead的形參,即一份臨時(shí)拷貝,用plist接收newnode,只是在尾插函數(shù)內(nèi)部起作用,而對(duì)外部的phead無(wú)影響,結(jié)果變成尾插一大頓,phead仍然指向NULL。

若phead不為NULL,則創(chuàng)建一個(gè)tail指針進(jìn)行找尾操作。找尾過(guò)程中,tail->next為NULL,則此時(shí)tail指向尾結(jié)點(diǎn),將newnode賦給tail->next即完成尾插。

?上圖為尾插1234后的結(jié)果。

還有一點(diǎn)要注意:assert的使用,不能見(jiàn)到指針就用assert,有時(shí)傳入的數(shù)據(jù)就是一個(gè)NULL,比如插入第一個(gè)元素時(shí)phead就是NULL,如果使用assert(phead),就會(huì)報(bào)錯(cuò)導(dǎo)致無(wú)法插入。

而對(duì)于pphead即phead的地址,是一定不為NULL,就可以進(jìn)行assert(pphead)的操作。

注意*pphead與pphead的區(qū)別

7、尾刪


//尾刪
void SLTPopBack(SListNode** pphead)
{assert(pphead);//先檢查pphead,再檢查*pphead,若pphead為NULL,*pphead就會(huì)產(chǎn)生錯(cuò)誤assert(*pphead);//若原來(lái)為空鏈表,則無(wú)法刪除SListNode* cur = *pphead;//分情況,原來(lái)鏈表中有一個(gè)  還是  多個(gè)元素if (NULL == cur->next){free(cur);cur = NULL;*pphead = NULL;}else//  多個(gè)元素先找到倒數(shù)第二個(gè){SListNode* pretail = *pphead;while (pretail->next->next != NULL){pretail = pretail->next;}free(pretail->next);pretail->next = NULL;}}

先用assert確保phead不為NULL,即確保刪除的不是空鏈表。

如果鏈表只有一個(gè)元素,free后,將phead置為NULL,使其成為空鏈表

當(dāng)鏈表中有多個(gè)元素時(shí),需要先找到尾結(jié)點(diǎn)的前一個(gè)元素pretail,方法是遍歷,直到pretail->next->next為NULL,這里通過(guò)兩個(gè)next,可以找到尾結(jié)點(diǎn)的那個(gè)next中的NULL,因此多個(gè)元素時(shí)使用這種方法,若只有一個(gè)元素則next的next會(huì)對(duì)NULL->,產(chǎn)生對(duì)于野指針解引用的錯(cuò)誤。

總結(jié):鏈表進(jìn)行尾插尾刪操作時(shí),要先進(jìn)行找尾,此過(guò)程需要遍歷,效率較低,因此進(jìn)行尾部操作時(shí)不如順序表。

刪除空鏈表時(shí)會(huì)報(bào)錯(cuò)。?

8、頭插

//頭插
void SLTPushFront(SListNode** pphead, SLTDataType x)
{//先創(chuàng)造一個(gè)新結(jié)點(diǎn)SListNode* tmp = BuySLTNode(x);if (NULL == tmp){return;}SListNode* newnode = tmp;//分情況討論,原來(lái)鏈表是否為空//if (NULL == *pphead)//{//	//如果為空,直接將phead與新結(jié)點(diǎn)連接即可//	*pphead = newnode;//}//else//{//	//不為空,建立新結(jié)點(diǎn)與原來(lái)頭結(jié)點(diǎn)的聯(lián)系//	//將phead與原來(lái)頭結(jié)點(diǎn)的聯(lián)系變?yōu)榕c新結(jié)點(diǎn)的聯(lián)系//	//原來(lái)A->B,現(xiàn)在A->C->B,先建立C->B,再建立A->C//	newnode->next = *pphead;//	*pphead = newnode;//}//是否為空都按不為空處理,next要么存原來(lái)頭結(jié)點(diǎn)地址,要么為	NULLnewnode->next = *pphead;*pphead = newnode;
}

鏈表的頭插很簡(jiǎn)單,先buy一個(gè)新結(jié)點(diǎn),然后將newnode->next指向原來(lái)的頭結(jié)點(diǎn),無(wú)論原來(lái)是否為NULL,再用phead指向這個(gè)新結(jié)點(diǎn)。

9、頭刪

//頭刪
void SLTPopFront(SListNode** pphead)
{assert(*pphead);SListNode* first = *pphead;*pphead = (*pphead)->next;free(first);first = NULL;
}

創(chuàng)建first指針指向頭結(jié)點(diǎn),然后將phead指向下一個(gè)結(jié)點(diǎn),不論是否為NULL,然后free掉first。

10、查找?

//  單鏈表查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{SListNode* cur = phead;while (NULL != cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}

利用cur遍歷鏈表,如果找到x就返回cur,即存有x的結(jié)點(diǎn)的地址,沒(méi)找到就繼續(xù)遍歷,cur==NULL時(shí)仍然未找到,則返回NULL。

?11、指定位置pos后方插入數(shù)據(jù)

//  單鏈表在指定位置后方插入   不用遍歷
void SListInsertAfter(SListNode* pos,SLTDataType x)
{assert(pos);SListNode* newnode = BuySLTNode(x);if (NULL == newnode){perror("ButSLTNode fail");return;}newnode->next = pos->next;pos->next = newnode;}

將newnode->next連接pos的next,不論正負(fù),然后將newnode賦給pos的next,此過(guò)程中不需要遍歷,解決了順序表在中間位置插入效率低的問(wèn)題。

12、刪除指定位置pos后方的數(shù)據(jù)

//  刪除后面的   不用遍歷  
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos->next != NULL);SListNode* del = pos->next;pos->next = del->next;free(del);del = NULL;//del為形參,是否置空影響不大,到函數(shù)外自動(dòng)銷毀,一般由使用者進(jìn)行置空}

必須保證pos->next不為NULL,因?yàn)槭莿h除pos位置的下一個(gè)元素,則至少有2個(gè)元素,若只有一個(gè),next為NULL,再解引用會(huì)變?yōu)橐爸羔槨?/p>

用del保存要?jiǎng)h除的位置,將pos的next與要?jiǎng)h除元素的下一個(gè)元素連接,不論是否為NULL,然后free掉del,完成刪除,也不需要遍歷。

總結(jié):鏈表的優(yōu)點(diǎn)在于頭部以及中間位置的插入和刪除不需要遍歷,這里中間位置,實(shí)際是pos的下一個(gè)元素。

任意位置后方進(jìn)行插入/刪除,不涉及phead的改變,因此只需要傳入phead即可。

?13、在指定位置pos的前方插入元素

在前方插入刪除涉及phead,因此傳入&phead

//單鏈表指定位置之前插入元素,需要找prev
void SListInsertBefore(SListNode** pphead,SListNode* pos,SLTDataType x)
{assert(*pphead);//不能為空,否則Find找不到posassert(pos);SListNode* newnode = BuySLTNode(x);SListNode* prev = *pphead;if (pos == *pphead){newnode->next = pos;*pphead = newnode;}else//找到pos前一個(gè)位置{SListNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}}

若鏈表中只有一個(gè)元素,則會(huì)改變phead的指向,這里調(diào)用頭插SLTPushFront也可以。

>=2個(gè)元素時(shí),先找到prev,然后插入。

需要進(jìn)行遍歷找到prev。?

如果要找的位置pos是NULL,直接報(bào)錯(cuò)即可,是使用該函數(shù)的人的問(wèn)題,函數(shù)只要完成應(yīng)該完成的任務(wù)即可。

注意:假設(shè)傳入的是plist,而不是它的地址,仍然用pphead接收,后續(xù)*pphead就會(huì)發(fā)生錯(cuò)誤。因此可assert(pphead)。pphead實(shí)際上一定不為空,因此只要傳入plist地址就要assert

14、刪除指定位置pos的數(shù)據(jù)

//在指定位置pos的刪除
void SListErasepos(SListNode** pphead, SListNode* pos)
{assert(pphead);assert(*pphead);assert(pos);SListNode* cur = *pphead;if (cur == pos){*pphead = pos->next;free(cur);cur = NULL;}else{SListNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}}

?

?如果pos指向第一個(gè)結(jié)點(diǎn),即為頭刪,也可以使用SLTPopFront頭刪函數(shù)

接收Find的ret在erase后可以置為NULL,在函數(shù)外部完成,內(nèi)部為形參。在內(nèi)部改變需要傳pos的二級(jí)指針。

而對(duì)于pphead則只能傳二級(jí)指針,在函數(shù)內(nèi)部修改phead的指向。

銷毀時(shí),利用tmp指針變量銷毀當(dāng)前位置,然后next找到下一個(gè)位置,遍歷銷毀。

總結(jié):尾插尾刪頭插頭刪都需要pphead,insertafter和eraseafter僅需要pos,查找和打印僅需要phead,insertbefore、erasepos需要pphead、pos。

pos? phead? pphead? *pphead 的assert問(wèn)題。

鏈表的優(yōu)點(diǎn)缺點(diǎn),某些位置是否需要遍歷。

面試題:不告知phead,只知道pos,怎么在pos指向的數(shù)據(jù)之前插入數(shù)據(jù)?

例如原來(lái)為? 1? ?2,pos指向2,可以在2的位置后插入3,然后將2、3兩個(gè)data交換,結(jié)果為132,當(dāng)然,此時(shí)pos指向的是3。

如果是刪除不給phead刪除pos當(dāng)前位置,則將pos位置的值改為下一個(gè)位置的值,然后刪除掉下一個(gè)位置的數(shù)據(jù)。(不能刪除尾結(jié)點(diǎn))

http://www.risenshineclean.com/news/12223.html

相關(guān)文章:

  • 手機(jī)能看的你們知道的免費(fèi)seo網(wǎng)站的工具
  • siteground建站教程品牌seo是什么意思
  • 中山藍(lán)圖科技網(wǎng)站建設(shè)深圳網(wǎng)站優(yōu)化公司
  • jquery動(dòng)畫特效網(wǎng)站四川seo整站優(yōu)化吧
  • 電子商務(wù)公司設(shè)計(jì)網(wǎng)站建設(shè)掌門一對(duì)一輔導(dǎo)官網(wǎng)
  • 站長(zhǎng)工具國(guó)產(chǎn)搜索熱度查詢
  • 金昌市建設(shè)局網(wǎng)站外鏈服務(wù)
  • 滕州手機(jī)網(wǎng)站建設(shè)案例google關(guān)鍵詞排名
  • 北京海淀區(qū)疫情最新情況解釋seo網(wǎng)站推廣
  • 革命幻燈片 wordpress365優(yōu)化大師軟件下載
  • 遵義網(wǎng)站推廣百度新聞下載安裝
  • 電子商務(wù)網(wǎng)站設(shè)計(jì)分析怎么做大量微信群推廣代發(fā)廣告
  • 濰坊做電商的網(wǎng)站建設(shè)品牌營(yíng)銷推廣要怎么做
  • b2b網(wǎng)站模塊重慶seo整站優(yōu)化效果
  • 廣州市建設(shè)局官方網(wǎng)站代運(yùn)營(yíng)哪家公司最靠譜
  • 高端網(wǎng)站建設(shè) 磐石網(wǎng)絡(luò)專注徐州seo排名公司
  • 為網(wǎng)站做seo需要什么軟件百度做推廣一般要多少錢
  • 來(lái)年做那些網(wǎng)站致富人工智能培訓(xùn)班收費(fèi)標(biāo)準(zhǔn)
  • 合肥做公司網(wǎng)站一般多少錢蘇州百度推廣排名優(yōu)化
  • 新的網(wǎng)站設(shè)計(jì)公司宜昌今日頭條新聞
  • 手機(jī)網(wǎng)站開(kāi)發(fā)書籍百度搜索引擎首頁(yè)
  • 旅游網(wǎng)站排名查詢百度推廣投訴中心
  • 做網(wǎng)站需要公司授權(quán)嘛成都最新熱門事件
  • wordpress 排版代碼seo技術(shù)優(yōu)化服務(wù)
  • 機(jī)票網(wǎng)站開(kāi)發(fā)百度網(wǎng)址大全官方網(wǎng)站
  • 俄語(yǔ)學(xué)習(xí)網(wǎng)站下載谷歌瀏覽器
  • 做企業(yè)網(wǎng)站需要買什么百度有幾個(gè)總部
  • 短視頻培訓(xùn)機(jī)構(gòu)seo入門到精通
  • 網(wǎng)站上文章字體部分復(fù)制怎么做seo關(guān)鍵詞排名優(yōu)化怎么樣
  • 武安市網(wǎng)站建設(shè)青島運(yùn)營(yíng)網(wǎng)絡(luò)推廣業(yè)務(wù)