C語言設(shè)計實(shí)例教程動態(tài)組織數(shù)據(jù)課件

C

程序設(shè)計實(shí)例教程第七章動態(tài)組織數(shù)據(jù)

1數(shù)組：必須事先定義固定長度，靜態(tài)分配存儲空間。鏈表：無需事先知道數(shù)據(jù)的個數(shù)，可以動態(tài)分配存儲空間，插入刪除簡便學(xué)習(xí)的意義要想改變數(shù)組長度可以嗎？怎么解決2/7/20232主要內(nèi)容1.建立鏈表的過程

2.鏈表結(jié)點(diǎn)的查找

3.鏈表結(jié)點(diǎn)的插入

4.鏈表結(jié)點(diǎn)的刪除

5.循環(huán)鏈表

2/7/202337.1建立鏈表的過程這樣文章a在排版時被分成了不連續(xù)的兩塊，讀者怎樣找到第二部分呢？編輯在a.part1的末尾加進(jìn)了一個線索“下接XX頁”，讀者順著線索很容易就找到了a.part2。所以a.part1放的不僅有文章本身，還有指示下一部分在哪的線索。通過這個線索，a.part1和a.part2就聯(lián)系在一起了。2/7/20235那a.part2的后面還有沒有另外一部分呢？雜志的每篇文章的最后都有一個特殊的符號，看到這個符號就知道這已經(jīng)是最后了。厚厚的一本書中，又怎樣找到文章a呢？翻翻目錄就知道了，那里有文章a所在頁碼的信息。2/7/20236文章a......a.part1......a.part2文章axx頁目錄下接xx頁完a.part1和a.part2組成了由兩個結(jié)點(diǎn)構(gòu)成的鏈表：目錄的頁碼指向鏈表a的第一個結(jié)點(diǎn)，此頁碼信息稱為頭指針，通過它能找到整個鏈表；a.part1后面的線索就是指針域，指示下一個邏輯塊在哪；a.part2的指針域指示后面不再有結(jié)點(diǎn)，稱為尾結(jié)點(diǎn)。2/7/20237什么是鏈表？鏈表——一種重要且常用的數(shù)據(jù)結(jié)構(gòu)，可動態(tài)地組織數(shù)據(jù)。鏈表不要求兩個元素在物理上相鄰，只要在元素結(jié)構(gòu)中加一個指針項(xiàng)，用來指向下一個元素的地址便可。鏈表的基本概念2/7/20239鏈表的基本概念

什么是鏈表?

鏈表的存儲結(jié)構(gòu)

2/7/2023102.3.1鏈表的基本概念鏈表的存儲結(jié)構(gòu)鏈表中的每個數(shù)據(jù)元素稱為結(jié)點(diǎn)

每個結(jié)點(diǎn)至少包括2個域：

數(shù)據(jù)域——存放數(shù)據(jù)元素的值；

指針域——存放直接后繼的地址,即指向后繼結(jié)點(diǎn)鏈表正是通過每個結(jié)點(diǎn)的指針域?qū)個數(shù)據(jù)元素按其邏輯順序鏈接在一起的鏈表中數(shù)據(jù)元素的邏輯順序與其物理存儲順序不一定相同；2/7/202311利用結(jié)構(gòu)體類型來實(shí)現(xiàn)鏈表structstudent{intnum;floatscore;

structstudent

*next;};78.51001numscorenext9010022/7/202313準(zhǔn)備工作

malloc(intsize)——在內(nèi)存中分配長度為size的連續(xù)空間

p=(structstudent*)malloc(sizeof(structstudent))建立、輸出——動態(tài)鏈表malloc函數(shù)的返回值是一個指向分配空間的起始地址的指針。如果分配不成功，malloc函數(shù)返回NULLif(!(p=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);2/7/202314準(zhǔn)備工作

free(void*p)——釋放p指向的內(nèi)存區(qū)動態(tài)鏈表——在執(zhí)行的過程中從無到有建立一個鏈表，即一個個開辟結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立前后鏈的關(guān)系靜態(tài)鏈表——所有結(jié)點(diǎn)都是在程序中定義的，不是臨時開辟的，也不能用完后釋放建立、輸出——動態(tài)鏈表2/7/202315鏈表創(chuàng)建就像穿一條珠鏈：一根線頭能將整串珠鏈提起，稱頭指針head。開始時沒有任何珠子，只有一根空線頭head；第一顆珠子（頭結(jié)點(diǎn)）接到head上，且其后有一根線頭（指針域next）可接下一顆珠子；每次把新加入的珠子pNew（結(jié)點(diǎn)）接到最后一顆珠子q后的線頭上。指針q指向每次最新接入的珠子,新珠子接到q的線頭上：q->next=pNew。當(dāng)不需接入珠子時，把最后一顆珠子后的線頭q->next打上結(jié)：q->next=NULL。2/7/202317鏈表置空：head=NULL循環(huán)：插入結(jié)點(diǎn)設(shè)置尾結(jié)點(diǎn)：q->next=NULL圖7.5“鏈表創(chuàng)建”的PAD圖2/7/202318循環(huán)體中每插入一個結(jié)點(diǎn)需要做以下操作：準(zhǔn)備新結(jié)點(diǎn)pNew：分配空間，為新結(jié)點(diǎn)賦值pNew插入鏈表pNew成為新的尾結(jié)點(diǎn)：q=pNew圖7.6“對鏈表插入一個結(jié)點(diǎn)”的PAD圖新結(jié)點(diǎn)pNew插入鏈表時有兩種情況：若鏈表為空，則放到head后；否則，插入到尾結(jié)點(diǎn)q之后。2/7/2023197.2鏈表結(jié)點(diǎn)的查找由于單鏈表中結(jié)點(diǎn)只能通過前一個結(jié)點(diǎn)的指針域找到，得到結(jié)點(diǎn)的前驅(qū)很重要。2/7/202321圖7.9通過指針p遍歷鏈表各結(jié)點(diǎn)pheadNULLpheadNULL(a)p=head，從頭開始遍歷鏈表(b)p=p->next，p指向下一個結(jié)點(diǎn)pheadNULL(c)p==NULL時遍歷完鏈表2/7/202322單鏈表只能從鏈表頭head開始訪問鏈表的各個結(jié)點(diǎn)，且只有前一個結(jié)點(diǎn)的指針域才能找到后一個結(jié)點(diǎn)。查找第i個結(jié)點(diǎn)：每訪問過一個結(jié)點(diǎn)就讓p指向下一個結(jié)點(diǎn)p=p->next，在訪問完最后一個結(jié)點(diǎn)之前，沿著指針域的指向順序遍歷，直到找到第i個結(jié)點(diǎn)為止。2/7/202323

A

C

Ehead

Bqpq->next=s;s->next=p;ss->next=q->next;q->next=s;或者鏈表的插入2/7/202325printf(“請輸入待插入字符\n");scanf("%c",&ch);s=(student*)malloc(LEN);s->data=ch;s->next=NULL;

p=head;while(p&&ch>p->data){q=p;p=p->next;}q->next=s;s->next=p;接受輸入的數(shù)據(jù)，新生成一個新的結(jié)點(diǎn)SBs尋找合適的插入位置AheadCqps插入到p

和q之間鏈表的插入2/7/202326鏈表的刪除ABCDEABCDE從動態(tài)鏈表中刪去一個結(jié)點(diǎn)，只要撤銷原來的鏈接關(guān)系，把它從鏈表中分離開來即可2/7/202329sppreNULLhead圖

鏈表結(jié)點(diǎn)的刪除×刪除結(jié)點(diǎn)的語句為：{pre->next=s;free(p);}；鏈表結(jié)點(diǎn)刪除后，用free()釋放該結(jié)點(diǎn)占用的內(nèi)存空間。或pre->next=p->next2/7/202330……101102110headqp103……101103110headqp104例

輸入104表示要求刪除學(xué)號為104的結(jié)點(diǎn)……q->next=p->next;2/7/202331printf("請輸入想刪除的字符\n");scanf("%c",&ch);p=head;while(p&&p->data!=ch){q=p;p=p->next;}if(p==NULL)printf("鏈表中無此字符\n");elseif(p==head)head=p->next;elseq->next=p->next;例.

輸入104表示要求刪除學(xué)號為104的結(jié)點(diǎn)未找到結(jié)點(diǎn)刪除的是第一個結(jié)點(diǎn)刪除的是中間結(jié)點(diǎn)、P=NULL

p走到表尾P->data=ch

找到要刪除的結(jié)點(diǎn)2/7/2023327.5循環(huán)鏈表【例7-9】

猴子選大王。給一群猴子都做了編號，編號是1，2，3...n,這群猴子（n個）按照1~n的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第m個，該猴子就要離開此圈，依次下來，直到圈中只剩一只猴子，即為大王。【分析】以n=8,m=3為例，猴子選大王的過程：2/7/202333圖7.15猴子選大王猴子出圈的順序：?起始位置123456782/7/202334圖7.15猴子選大王猴子出圈的順序：123456782/7/202335圖7.15猴子選大王猴子出圈的順序：123456782/7/202336圖7.15猴子選大王猴子出圈的順序：312456782/7/202337圖7.15猴子選大王猴子出圈的順序：312456782/7/202338圖7.15猴子選大王猴子出圈的順序：312456782/7/202339圖7.15猴子選大王猴子出圈的順序：361245782/7/202340圖7.15猴子選大王猴子出圈的順序：361245782/7/202341圖7.15猴子選大王猴子出圈的順序：361245782/7/202342圖7.15猴子選大王猴子出圈的順序：361245782/7/202343圖7.15猴子選大王猴子出圈的順序：361245782/7/202344圖7.15猴子選大王猴子出圈的順序：361245782/7/202345圖7.15猴子選大王猴子出圈的順序：361524782/7/202346圖7.15猴子選大王猴子出圈的順序：361524782/7/202347圖7.15猴子選大王猴子出圈的順序：361524782/7/202348圖7.15猴子選大王猴子出圈的順序：361524782/7/202349圖7.15猴子選大王猴子出圈的順序：361524782/7/202350圖7.15猴子選大王猴子出圈的順序：361524782/7/202351圖7.15猴子選大王猴子出圈的順序：361528472/7/202352圖7.15猴子選大王猴子出圈的順序：361528742/7/202353圖7.15猴子選大王猴子出圈的順序：361528742/7/202354圖7.15猴子選大王猴子出圈的順序：361528472/7/202355猴子選大王的過程中，需要將其他的n-1個猴子從圈中刪除。采用單鏈表存儲每個猴子數(shù)據(jù)。為了便于循環(huán)報數(shù)，讓最后一只猴子挨著第一只坐，即最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)：q->next=head，形成了循環(huán)鏈表。猴子選大王的過程就是循環(huán)鏈表的結(jié)點(diǎn)不斷被刪除的過程。結(jié)點(diǎn)刪除后還是循環(huán)鏈表，只是縮小了。當(dāng)圈中只剩下一個結(jié)點(diǎn)：pre->next==pre時，pre就是要找的猴王。2/7/202356單循環(huán)鏈表最后一個結(jié)點(diǎn)的指針域的指針又指回第一個結(jié)點(diǎn)的鏈表怎么樣判斷鏈表為空？if(head->next==head)

循環(huán)鏈表的操作和