C語(yǔ)言設(shè)計(jì)實(shí)例教程動(dòng)態(tài)組織數(shù)據(jù)

會(huì)計(jì)學(xué)1C語(yǔ)言設(shè)計(jì)實(shí)例教程動(dòng)態(tài)組織數(shù)據(jù)2023/1/172主要內(nèi)容1.建立鏈表的過(guò)程

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

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

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

5.循環(huán)鏈表

第1頁(yè)/共57頁(yè)2023/1/1737.1建立鏈表的過(guò)程看雜志時(shí)碰到有篇文章3頁(yè)不夠放，4頁(yè)又空著太多。怎么辦？編輯往往先給這篇文章（稱做a）排3頁(yè)(且稱這3頁(yè)為a.part1)，接著排其他文章，等什么時(shí)候有空的頁(yè)面還夠安排a剩下的部分(稱它為a.part2)時(shí)，就把a(bǔ).part2排進(jìn)去。第2頁(yè)/共57頁(yè)2023/1/1747.1建立鏈表的過(guò)程這樣文章a在排版時(shí)被分成了不連續(xù)的兩塊，讀者怎樣找到第二部分呢？編輯在a.part1的末尾加進(jìn)了一個(gè)線索“下接X(jué)X頁(yè)”，讀者順著線索很容易就找到了a.part2。所以a.part1放的不僅有文章本身，還有指示下一部分在哪的線索。通過(guò)這個(gè)線索，a.part1和a.part2就聯(lián)系在一起了。第3頁(yè)/共57頁(yè)2023/1/175那a.part2的后面還有沒(méi)有另外一部分呢？雜志的每篇文章的最后都有一個(gè)特殊的符號(hào)，看到這個(gè)符號(hào)就知道這已經(jīng)是最后了。厚厚的一本書(shū)中，又怎樣找到文章a呢？翻翻目錄就知道了，那里有文章a所在頁(yè)碼的信息。第4頁(yè)/共57頁(yè)2023/1/176文章a......a.part1......a.part2文章axx頁(yè)目錄下接xx頁(yè)完a.part1和a.part2組成了由兩個(gè)結(jié)點(diǎn)構(gòu)成的鏈表：目錄的頁(yè)碼指向鏈表a的第一個(gè)結(jié)點(diǎn)，此頁(yè)碼信息稱為頭指針，通過(guò)它能找到整個(gè)鏈表；a.part1后面的線索就是指針域，指示下一個(gè)邏輯塊在哪；a.part2的指針域指示后面不再有結(jié)點(diǎn)，稱為尾結(jié)點(diǎn)。第5頁(yè)/共57頁(yè)2023/1/177鏈表的基本概念?什么是鏈表

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

第6頁(yè)/共57頁(yè)2023/1/178什么是鏈表？鏈表——一種重要且常用的數(shù)據(jù)結(jié)構(gòu)，可動(dòng)態(tài)地組織數(shù)據(jù)。鏈表不要求兩個(gè)元素在物理上相鄰，只要在元素結(jié)構(gòu)中加一個(gè)指針項(xiàng)，用來(lái)指向下一個(gè)元素的地址便可。鏈表的基本概念第7頁(yè)/共57頁(yè)2023/1/179鏈表的基本概念

什么是鏈表?

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

第8頁(yè)/共57頁(yè)2023/1/17102.3.1鏈表的基本概念鏈表的存儲(chǔ)結(jié)構(gòu)鏈表中的每個(gè)數(shù)據(jù)元素稱為結(jié)點(diǎn)

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

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

指針域——存放直接后繼的地址,即指向后繼結(jié)點(diǎn)鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)個(gè)數(shù)據(jù)元素按其邏輯順序鏈接在一起的鏈表中數(shù)據(jù)元素的邏輯順序與其物理存儲(chǔ)順序不一定相同；第9頁(yè)/共57頁(yè)2023/1/1711

head:

頭指針，類型為指向結(jié)構(gòu)體的指針，存放鏈表第一個(gè)元素的地址；

結(jié)點(diǎn)：鏈表中的每一個(gè)元素稱為一個(gè)結(jié)點(diǎn)；

NULL：表示空指針，經(jīng)常用來(lái)表示；

表尾：鏈表的最后一個(gè)結(jié)點(diǎn)，不指向任何元素；鏈表中各個(gè)元素的地址并不連續(xù)DA0012B4152C14302160head2160001241521430鏈表第10頁(yè)/共57頁(yè)2023/1/1712利用結(jié)構(gòu)體類型來(lái)實(shí)現(xiàn)鏈表structstudent{intnum;floatscore;

structstudent

*next;};78.51001numscorenext901002第11頁(yè)/共57頁(yè)2023/1/1713準(zhǔn)備工作

malloc(intsize)

——

在內(nèi)存中分配長(zhǎng)度為size的連續(xù)空間

p=(structstudent*)malloc(sizeof(structstudent))建立、輸出——?jiǎng)討B(tài)鏈表malloc函數(shù)的返回值是一個(gè)指向分配空間的起始地址的指針。如果分配不成功，malloc函數(shù)返回NULLif(!(p=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);第12頁(yè)/共57頁(yè)2023/1/1714準(zhǔn)備工作

free(void*p)

——

釋放p指向的內(nèi)存區(qū)動(dòng)態(tài)鏈表——

在執(zhí)行的過(guò)程中從無(wú)到有建立一個(gè)鏈表，即一個(gè)個(gè)開(kāi)辟結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立前后鏈的關(guān)系靜態(tài)鏈表——

所有結(jié)點(diǎn)都是在程序中定義的，不是臨時(shí)開(kāi)辟的，也不能用完后釋放建立、輸出——?jiǎng)討B(tài)鏈表第13頁(yè)/共57頁(yè)2023/1/1715例.建立有1個(gè)學(xué)生數(shù)據(jù)單鏈表typedef

structstudent{intnum;floatscore;student*next;}student;

student*head,*p;head=NULL;p=(student*)malloc(sizeof(student));scanf(“%d,%f”,&p->num,&p->score);p->next=NULL;head=p;headpp110195.510287第14頁(yè)/共57頁(yè)2023/1/1716鏈表創(chuàng)建就像穿一條珠鏈：一根線頭能將整串珠鏈提起，稱頭指針head。開(kāi)始時(shí)沒(méi)有任何珠子，只有一根空線頭head；第一顆珠子（頭結(jié)點(diǎn)）接到head上，且其后有一根線頭（指針域next）可接下一顆珠子；每次把新加入的珠子pNew（結(jié)點(diǎn)）接到最后一顆珠子q后的線頭上。指針q指向每次最新接入的珠子,新珠子接到q的線頭上：q->next=pNew。當(dāng)不需接入珠子時(shí)，把最后一顆珠子后的線頭q->next打上結(jié)：q->next=NULL。第15頁(yè)/共57頁(yè)2023/1/1717鏈表置空：head=NULL循環(huán)：插入結(jié)點(diǎn)設(shè)置尾結(jié)點(diǎn)：q->next=NULL圖7.5“鏈表創(chuàng)建”的PAD圖第16頁(yè)/共57頁(yè)2023/1/1718循環(huán)體中每插入一個(gè)結(jié)點(diǎn)需要做以下操作：準(zhǔn)備新結(jié)點(diǎn)pNew：分配空間，為新結(jié)點(diǎn)賦值pNew插入鏈表pNew成為新的尾結(jié)點(diǎn)：q=pNew圖7.6“對(duì)鏈表插入一個(gè)結(jié)點(diǎn)”的PAD圖新結(jié)點(diǎn)pNew插入鏈表時(shí)有兩種情況：若鏈表為空，則放到head后；否則，插入到尾結(jié)點(diǎn)q之后。第17頁(yè)/共57頁(yè)2023/1/1719與數(shù)組不同，鏈表中每個(gè)元素的存儲(chǔ)空間都需在使用前在程序中顯式地分配，并用指針指向所分配空間的首地址，用完以后再顯式地釋放每個(gè)元素占用的空間.需要?jiǎng)討B(tài)地分配和釋放內(nèi)存空間。

malloc(intsize)free(void*p)在TurboC中的頭文件是stdlib.h，在VC中是malloc.h文件。第18頁(yè)/共57頁(yè)2023/1/17207.2鏈表結(jié)點(diǎn)的查找由于單鏈表中結(jié)點(diǎn)只能通過(guò)前一個(gè)結(jié)點(diǎn)的指針域找到，得到結(jié)點(diǎn)的前驅(qū)很重要。第19頁(yè)/共57頁(yè)2023/1/1721圖7.9通過(guò)指針p遍歷鏈表各結(jié)點(diǎn)pheadNULLpheadNULL(a)p=head，從頭開(kāi)始遍歷鏈表(b)p=p->next，p指向下一個(gè)結(jié)點(diǎn)pheadNULL(c)p==NULL時(shí)遍歷完鏈表第20頁(yè)/共57頁(yè)2023/1/1722單鏈表只能從鏈表頭head開(kāi)始訪問(wèn)鏈表的各個(gè)結(jié)點(diǎn)，且只有前一個(gè)結(jié)點(diǎn)的指針域才能找到后一個(gè)結(jié)點(diǎn)。查找第i個(gè)結(jié)點(diǎn)：每訪問(wèn)過(guò)一個(gè)結(jié)點(diǎn)就讓p指向下一個(gè)結(jié)點(diǎn)p=p->next，在訪問(wèn)完最后一個(gè)結(jié)點(diǎn)之前，沿著指針域的指向順序遍歷，直到找到第i個(gè)結(jié)點(diǎn)為止。第21頁(yè)/共57頁(yè)2023/1/1723問(wèn)題：輸入數(shù)據(jù)的同時(shí)，將數(shù)據(jù)插入到鏈表中，并且保持鏈表中數(shù)據(jù)有序分析：第一個(gè)：接到head后面第二個(gè)：查找合適的插入位置插入，并保持鏈表的前后鏈第三個(gè)……第N個(gè)……7.3鏈表結(jié)點(diǎn)的插入第22頁(yè)/共57頁(yè)2023/1/1724

A

C

Ehead

Bqpq->next=s;s->next=p;ss->next=q->next;q->next=s;或者鏈表的插入第23頁(yè)/共57頁(yè)2023/1/1725printf(“請(qǐng)輸入待插入字符\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ù)，新生成一個(gè)新的結(jié)點(diǎn)SBs尋找合適的插入位置AheadCqps插入到p

和q之間鏈表的插入第24頁(yè)/共57頁(yè)2023/1/1726考慮插入結(jié)點(diǎn)時(shí)的幾種特殊情況插入后為第一個(gè)結(jié)點(diǎn)插入后為最后一個(gè)結(jié)點(diǎn)

A

C

Eheadsp

A

C

Eheadsq鏈表的插入第25頁(yè)/共57頁(yè)2023/1/17277.4鏈表結(jié)點(diǎn)的刪除在數(shù)組操作中，無(wú)論是插入元素還是刪除元素都有大量的數(shù)據(jù)需要移動(dòng)鏈表中刪除鏈表結(jié)點(diǎn)只要對(duì)個(gè)別結(jié)點(diǎn)的指針做一些調(diào)整即可。刪除結(jié)點(diǎn)時(shí)要保證不破壞鏈表原來(lái)的連接關(guān)系，并且先要找到結(jié)點(diǎn)的前驅(qū)。第26頁(yè)/共57頁(yè)2023/1/1728鏈表的刪除ABCDEABCDE從動(dòng)態(tài)鏈表中刪去一個(gè)結(jié)點(diǎn)，只要撤銷原來(lái)的鏈接關(guān)系，把它從鏈表中分離開(kāi)來(lái)即可第27頁(yè)/共57頁(yè)2023/1/1729sppreNULLhead圖

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

輸入104表示要求刪除學(xué)號(hào)為104的結(jié)點(diǎn)……q->next=p->next;第29頁(yè)/共57頁(yè)2023/1/1731printf("請(qǐng)輸入想刪除的字符\n");scanf("%c",&ch);p=head;while(p&&p->data!=ch){q=p;p=p->next;}if(p==NULL)printf("鏈表中無(wú)此字符\n");elseif(p==head)head=p->next;elseq->next=p->next;例.

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

p走到表尾P->data=ch

找到要?jiǎng)h除的結(jié)點(diǎn)第30頁(yè)/共57頁(yè)2023/1/17327.5循環(huán)鏈表【例7-9】

猴子選大王。給一群猴子都做了編號(hào)，編號(hào)是1，2，3...n,這群猴子（n個(gè)）按照1~n的順序圍坐一圈，從第1開(kāi)始數(shù)，每數(shù)到第m個(gè)，該猴子就要離開(kāi)此圈，依次下來(lái)，直到圈中只剩一只猴子，即為大王?！痉治觥恳詎=8,m=3為例，猴子選大王的過(guò)程：第31頁(yè)/共57頁(yè)2023/1/1733圖7.15猴子選大王猴子出圈的順序：?起始位置12345678第32頁(yè)/共57頁(yè)2023/1/1734圖7.15猴子選大王猴子出圈的順序：12345678第33頁(yè)/共57頁(yè)2023/1/1735圖7.15猴子選大王猴子出圈的順序：12345678第34頁(yè)/共57頁(yè)2023/1/1736圖7.15猴子選大王猴子出圈的順序：31245678第35頁(yè)/共57頁(yè)2023/1/1737圖7.15猴子選大王猴子出圈的順序：31245678第36頁(yè)/共57頁(yè)2023/1/1738圖7.15猴子選大王猴子出圈的順序：31245678第37頁(yè)/共57頁(yè)2023/1/1739圖7.15猴子選大王猴子出圈的順序：36124578第38頁(yè)/共57頁(yè)2023/1/1740圖7.15猴子選大王猴子出圈的順序：36124578第39頁(yè)/共57頁(yè)2023/1/1741圖7.15猴子選大王猴子出圈的順序：36124578第40頁(yè)/共57頁(yè)2023/1/1742圖7.15猴子選大王猴子出圈的順序：36124578第41頁(yè)/共57頁(yè)2023/1/1743圖7.15猴子選大王猴子出圈的順序：36124578第42頁(yè)/共57頁(yè)2023/1/1744圖7.15猴子選大王猴子出圈的順序：36124578第43頁(yè)/共57頁(yè)2023/1/1745圖7.15猴子選大王猴子出圈的順序：36152478第44頁(yè)/共57頁(yè)2023/1/1746圖7.15猴子選大王猴子出圈的順序：36152478第45頁(yè)/共57頁(yè)2023/1/1747圖7.15猴子選大王猴子出圈的順序：36152478第46頁(yè)/共57頁(yè)2023/1/1748圖7.15猴子選大王猴子出圈的順序：36152478第47頁(yè)/共57頁(yè)2023/1/1749圖7.15猴子選大王猴子出圈的順序：36152478第48頁(yè)/共57頁(yè)2023/1/1750圖7.15猴子選大王猴子出圈的順序：36152478第49頁(yè)/共57頁(yè)2023/1/1751圖7.15猴子選大王猴子出圈的順序：36152847第50頁(yè)/共57頁(yè)2023/1/1752圖7.15猴子選大王猴子出圈的順序：36152874第51頁(yè)/共57頁(yè)2023/1/175