軟件技術(shù)基礎(chǔ) 線性結(jié)構(gòu)—鏈表

1、軟件技術(shù)基礎(chǔ)軟件技術(shù)基礎(chǔ)制作主講段景山鏈接存儲(chǔ)的線性表鏈接存儲(chǔ)的線性表l1.2、 鏈接存儲(chǔ)的線性表（鏈表）的定義鏈接存儲(chǔ)的線性表（鏈表）的定義l1.2.1、 鏈表的引入鏈表的引入v數(shù)組結(jié)構(gòu)的缺點(diǎn)數(shù)組結(jié)構(gòu)的缺點(diǎn):1、在插入、刪除時(shí)要移動(dòng)大量的節(jié)點(diǎn)、在插入、刪除時(shí)要移動(dòng)大量的節(jié)點(diǎn)2、表的大小固定。、表的大小固定。預(yù)先在申明數(shù)組時(shí)指定，無(wú)法更改預(yù)先在申明數(shù)組時(shí)指定，無(wú)法更改v原因：原因：都可歸因到：存放的連續(xù)性都可歸因到：存放的連續(xù)性v突破突破離散存放離散存放用指針來(lái)表示元素之間的關(guān)系。用指針來(lái)表示元素之間的關(guān)系。鏈接存儲(chǔ)的線性表鏈接存儲(chǔ)的線性表l用鏈表實(shí)現(xiàn)線性表（非連續(xù)存儲(chǔ)）用鏈表實(shí)現(xiàn)線性表（非連

2、續(xù)存儲(chǔ)）a1a2a3a4鏈表的定義鏈表的定義l1.2.2 鏈表的定義鏈表的定義l鏈點(diǎn)鏈點(diǎn)datalink元素域元素域鏈接域鏈接域元素域（數(shù)據(jù)元素域）：存放一個(gè)數(shù)據(jù)元素。元素域（數(shù)據(jù)元素域）：存放一個(gè)數(shù)據(jù)元素。鏈接域（關(guān)系域）：存放指向下一個(gè)元素的指針鏈接域（關(guān)系域）：存放指向下一個(gè)元素的指針表示表示/記錄元素間的關(guān)系。記錄元素間的關(guān)系。元素域元素域 + 鏈接域鏈接域 = 結(jié)點(diǎn)（鏈點(diǎn)）結(jié)點(diǎn)（鏈點(diǎn)）鏈表的要素鏈表的要素l鏈表鏈表a1a2an由鏈點(diǎn)及鏈點(diǎn)相互間的鏈接構(gòu)成head鏈表頭head鏈表尾tail鏈表長(zhǎng)度（結(jié)點(diǎn)數(shù)目）lengthtaillength算法動(dòng)手做算法動(dòng)手做l請(qǐng)準(zhǔn)備請(qǐng)準(zhǔn)備 6 張小

3、紙片在紙片的中間畫(huà)兩個(gè)格子。張小紙片在紙片的中間畫(huà)兩個(gè)格子。l在最左邊格子外面按序?qū)懮喜煌奶?hào)碼，代表每個(gè)鏈點(diǎn)在最左邊格子外面按序?qū)懮喜煌奶?hào)碼，代表每個(gè)鏈點(diǎn)的地址。寫(xiě)完地址后，像洗撲克牌那樣將小紙片交換位的地址。寫(xiě)完地址后，像洗撲克牌那樣將小紙片交換位置。在紙片中間一格填寫(xiě)置。在紙片中間一格填寫(xiě)“ax”表示元素值（目的是使表示元素值（目的是使x的大小關(guān)系盡量不要和地址大小關(guān)系一致）的大小關(guān)系盡量不要和地址大小關(guān)系一致）l做好卡片后，同組的同學(xué)交換卡片，完成后面的內(nèi)容做好卡片后，同組的同學(xué)交換卡片，完成后面的內(nèi)容l最右邊一格代表每個(gè)鏈點(diǎn)的指針變量，在里面填寫(xiě)后繼最右邊一格代表每個(gè)鏈點(diǎn)的指針變量

4、，在里面填寫(xiě)后繼元素的元素的“地址地址”。請(qǐng)將其中的。請(qǐng)將其中的5張卡片按照地址大小排張卡片按照地址大小排成一列，然后再按元素線性關(guān)系填寫(xiě)成一列，然后再按元素線性關(guān)系填寫(xiě)“地址欄地址欄”形成一形成一個(gè)鏈表。個(gè)鏈表。l做好后，從鏈表首開(kāi)始逐個(gè)尋找鏈點(diǎn)，體會(huì)鏈表的結(jié)構(gòu)做好后，從鏈表首開(kāi)始逐個(gè)尋找鏈點(diǎn)，體會(huì)鏈表的結(jié)構(gòu)鏈表的定義鏈表的定義l定義定義typedef struct node_typeelemtype data;struct node_type * next;node_type ;typedef struct list_typenode_type *head;node_type *tail;

5、/很少用很少用int length;list_type;datanext元素值的類型，如：int 整型char 字符型long 長(zhǎng)整型struct 復(fù)合型鏈表的定義鏈表的定義l鏈表組織：鏈表組織：list_type *list;list-head = &a1;a1-next = &a2;a2-next = &a3;an-next = NULL；list-tail = &an;list-length = n;a1a2anheadtailNULL，表示指針的值為“空”，即指針指向空處鏈表的基本操作鏈表的基本操作l1.2.3 鏈表的基本操作鏈表的基本操作v訪問(wèn)訪問(wèn)v插

6、入插入v刪除刪除鏈表的基本操作鏈表的基本操作l訪問(wèn)操作訪問(wèn)操作v問(wèn)題描述：訪問(wèn)鏈表的第問(wèn)題描述：訪問(wèn)鏈表的第i個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)v問(wèn)題分析：?jiǎn)栴}分析：輸入：鏈表，輸入：鏈表，i輸出：鏈點(diǎn)輸出：鏈點(diǎn)指向鏈點(diǎn)的指針指向鏈點(diǎn)的指針v算法實(shí)現(xiàn)分析：算法實(shí)現(xiàn)分析：a1a2anheadtailtemptemptemp算法動(dòng)手做算法動(dòng)手做l回到小紙片中，如何描述我們找到第回到小紙片中，如何描述我們找到第i個(gè)節(jié)個(gè)節(jié)點(diǎn)的動(dòng)作。點(diǎn)的動(dòng)作。v1、先、先得得到鏈表首結(jié)點(diǎn)（的地址）到鏈表首結(jié)點(diǎn)（的地址）v2、通過(guò)、通過(guò)“地址地址”，找到鏈點(diǎn)，找到鏈點(diǎn)v3、在鏈點(diǎn)中找到后繼元素的、在鏈點(diǎn)中找到后繼元素的“地址地址”v4、記錄這

7、個(gè)地址，回到、記錄這個(gè)地址，回到2從自然語(yǔ)言到算法語(yǔ)言從自然語(yǔ)言到算法語(yǔ)言l如何描述我們?cè)阪湵砩先绾蚊枋鑫覀冊(cè)阪湵砩稀爸饌€(gè)去找逐個(gè)去找”的動(dòng)作的動(dòng)作？v1、先找到鏈表首結(jié)點(diǎn)的地址、先找到鏈表首結(jié)點(diǎn)的地址v2、通過(guò)、通過(guò)“地址地址”，找到鏈點(diǎn)，找到鏈點(diǎn)v3、在鏈點(diǎn)中找到后繼元素的、在鏈點(diǎn)中找到后繼元素的“地址地址”v4、記錄這個(gè)地址，、記錄這個(gè)地址，回到回到2p = list-head;while( )p-data p = p-next;p-next 繼續(xù)完善描述繼續(xù)完善描述l我們需要的是找到第我們需要的是找到第i個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)v1、先找到鏈表首結(jié)點(diǎn)的地址、先找到鏈表首結(jié)點(diǎn)的地址v2、通過(guò)、通過(guò)“

8、地址地址”，找到鏈點(diǎn)，找到鏈點(diǎn)v3、在鏈點(diǎn)中找到后繼元素的、在鏈點(diǎn)中找到后繼元素的“地址地址”v4、記錄這個(gè)地址，、記錄這個(gè)地址，回到回到2p = list-head;while( )p-data p = p-next;p-next counter = 1;counter +;if( counter = i)break;p = list-head;while( )p = p-next;counter = 1;counter +;if( counter = i)break;計(jì)數(shù)，如果計(jì)數(shù)到i，就結(jié)束node_type *get_node( list, i )while(counter next;

9、int counter ;node_type * p;return p;if( p = = NULL) return NULL;p = list-head;counter = 1;a1aiai+1an pa2逐個(gè)“數(shù)”的動(dòng)作當(dāng)in時(shí)算法結(jié)果怎樣？思考訪問(wèn)操作訪問(wèn)操作l注意注意1、p = p-next ;沿鏈表前進(jìn)沿鏈表前進(jìn)2、循環(huán)結(jié)束條件、循環(huán)結(jié)束條件counter = = i 或或 node = = NULLcounter list-length思考如果希望獲得值為x的元素，如何實(shí)現(xiàn)？while( p-data = x & p != NULL)插入操作插入操作l鏈表插入操作鏈表插入操

10、作v問(wèn)題描述：?jiǎn)栴}描述：在元素在元素ai前插入新的元素前插入新的元素new_node ;v問(wèn)題分析：?jiǎn)栴}分析：輸入：鏈表，輸入：鏈表，location，x輸出：插入新元素后的鏈表。輸出：插入新元素后的鏈表。v算法實(shí)現(xiàn)分析算法實(shí)現(xiàn)分析算法動(dòng)手做算法動(dòng)手做l又回到小紙片，如果要向第又回到小紙片，如果要向第4個(gè)節(jié)點(diǎn)前放個(gè)節(jié)點(diǎn)前放入一個(gè)新的鏈點(diǎn)。如何描述這個(gè)過(guò)程。入一個(gè)新的鏈點(diǎn)。如何描述這個(gè)過(guò)程。head = 55p = 插入操作插入操作a1aianheadtailai-1.anewa1aianheadtailai-1.anew插入操作插入操作void insertl（list, new_node ,

11、 location） ai-1-next = anew ;anew-next = ai ;插入操作插入操作void insertl（list, new_node , location） ?a1ai-1aianpnewnodea2插入操作插入操作void insertl（list, new_node , location） a1ai-1aianpnewnodea2插入操作插入操作void insertl（list, new_node , location） while( counter next;new_node-next = p-next;p-next = new_node;counter =

12、 1;p = list-head; 初始化list-length +;插入操作插入操作a1插入操作插入操作 表首插入表首插入void insertl（list, new_node , location） while( counter next;new_node-next = p-next;p-next = new_node;counter = 1;p = list-head; 初始化if(location = 1)elsenew_node-next = list-head;list-head = new_node;list-length +;思考，教材算法中輸入?yún)?shù)的*，與本算法的異同，相應(yīng)的

13、原因插入操作插入操作 表尾插入表尾插入a1ai-1aianlist-headwhile( counter next;new_node-next = p-next;p-next = new_node;p-next != NULL)NULL p插入操作插入操作else從插入算法中對(duì)鏈表操作的體會(huì)從插入算法中對(duì)鏈表操作的體會(huì)l1、鏈表操作往往從表頭開(kāi)始，逐個(gè)找到、鏈表操作往往從表頭開(kāi)始，逐個(gè)找到需要的鏈點(diǎn)需要的鏈點(diǎn)l2、鏈表操作的有向性、鏈表操作的有向性 不能回退；不能回退；l3、鏈表指針小心使用，謹(jǐn)防丟失。、鏈表指針小心使用，謹(jǐn)防丟失。l4、不能訪問(wèn)空指針的成員、不能訪問(wèn)空指針的成員l5、插入過(guò)程

14、沒(méi)有對(duì)鏈點(diǎn)內(nèi)容進(jìn)行搬移。、插入過(guò)程沒(méi)有對(duì)鏈點(diǎn)內(nèi)容進(jìn)行搬移。鏈表的創(chuàng)建鏈表的創(chuàng)建create_list( list, x ) while( )new_node-data = x;new_node-next = NULL;new_node-next = list_head;list-head = new_node; new_node = malloc(sizeof(node_type);scanf( “%d”, &x );刪除操作刪除操作l鏈表的刪除操作鏈表的刪除操作v問(wèn)題描述：刪除元素問(wèn)題描述：刪除元素ai ;v問(wèn)題分析：?jiǎn)栴}分析：輸入：鏈表，輸入：鏈表，location輸出：刪除元素后

15、的鏈表。輸出：刪除元素后的鏈表。v算法實(shí)現(xiàn)分析算法實(shí)現(xiàn)分析a1ai+1anheadtailai-1.aiai-1-next = ai-next;即即ai-1-next = ai-1-next-next;刪除操作刪除操作找到找到ai-1執(zhí)行刪除動(dòng)作執(zhí)行刪除動(dòng)作void deletel（list, location）注意，從鏈表上取下的鏈點(diǎn)注意，從鏈表上取下的鏈點(diǎn)ai-1需要用一個(gè)臨時(shí)指針記錄下來(lái)，需要用一個(gè)臨時(shí)指針記錄下來(lái)，否則可能丟失否則可能丟失a1ai+1anheadtailai-1.ai刪除操作刪除操作void deletel（list, location） while( counter

16、next;p-next = p-next-next;counter = 1;p = list-head; 初始化if(location = 1)elselist-head = list-head-next;temp = p-next;free(temp);temp = list-head;free(temp);list-length -;從鏈表刪除的鏈點(diǎn)，一般應(yīng)該釋放其空間刪除操作刪除操作l注意注意:v對(duì)被刪除刪除鏈點(diǎn)的處理對(duì)被刪除刪除鏈點(diǎn)的處理往往需要釋放其動(dòng)態(tài)申請(qǐng)的空間往往需要釋放其動(dòng)態(tài)申請(qǐng)的空間free（ ）如果希望刪除值為x的元素，如何實(shí)現(xiàn)？while( p-data = x &

17、; p != NULL) 可以嗎？while( p-next-data = x & p-next != NULL) 可以嗎？l1.2.4 鏈表的特點(diǎn)鏈表的特點(diǎn)v、操作的順序性、操作的順序性有平均次查找過(guò)程。有平均次查找過(guò)程。v、離散存放、離散存放不受鏈表大小限制不受鏈表大小限制不進(jìn)行鏈點(diǎn)內(nèi)容的搬移不進(jìn)行鏈點(diǎn)內(nèi)容的搬移v查找操作：數(shù)組效率優(yōu)于鏈表查找操作：數(shù)組效率優(yōu)于鏈表v插入、刪除操作：鏈表效率優(yōu)于數(shù)組插入、刪除操作：鏈表效率優(yōu)于數(shù)組鏈表的特點(diǎn)鏈表的特點(diǎn)上機(jī)練習(xí)題上機(jī)練習(xí)題l例、讀入一組數(shù)建立鏈表，以負(fù)數(shù)作為例、讀入一組數(shù)建立鏈表，以負(fù)數(shù)作為輸入結(jié)束輸入結(jié)束l算法實(shí)現(xiàn)分析算法實(shí)現(xiàn)分析v

18、輸入：輸入：空鏈表空鏈表元素值從鍵盤(pán)輸入。（從文件讀入？）元素值從鍵盤(pán)輸入。（從文件讀入？）v輸出：創(chuàng)建好的鏈表輸出：創(chuàng)建好的鏈表例、讀入一組數(shù)建立鏈表，以負(fù)數(shù)作為輸入例、讀入一組數(shù)建立鏈表，以負(fù)數(shù)作為輸入結(jié)束結(jié)束建立建立框架：框架：上機(jī)練習(xí)指導(dǎo)上機(jī)練習(xí)指導(dǎo)main( )x 0; 初始化初始化while (x = 0)read( &x )；插入鏈表；插入鏈表；read( int * x)scanf( “data %d: “，x);上機(jī)練習(xí)題上機(jī)練習(xí)題每次插在表頭或者每次插在表尾？每次插在表頭或者每次插在表尾？決定每次插在表尾！決定每次插在表尾！new_node-next = list.

19、tail-next;list.tail-next = new_node;list.header = new_node;list.tail = new_node;上機(jī)練習(xí)指導(dǎo)上機(jī)練習(xí)指導(dǎo)list_type * create_list( )初始化；初始化；while( x = 0)read(&x);生成新元素生成新元素插入新元素插入新元素return list;上機(jī)練習(xí)指導(dǎo)上機(jī)練習(xí)指導(dǎo)list_type * create_list( )list_type *list;list-length = 0; list-header = NULL;list-tail = NULL;node_type

20、 * new_node;int x;list = malloc(sizeof(list_type);while( x = 0)new_node = (node_type *)malloc(size_of(struct node_type);new_node-data = x; 假設(shè)假設(shè)elemtype 就是整數(shù)類型就是整數(shù)類型new_node-next = NULL;if( list.length next = list.tail-next;list.tail-next = new_node;list.tail = new_node;list.legth +;read(x);return li

21、st;read(x);上機(jī)練習(xí)題上機(jī)練習(xí)題例例2 2、檢查一個(gè)（單向）鏈表，刪除其中數(shù)據(jù)大于、檢查一個(gè)（單向）鏈表，刪除其中數(shù)據(jù)大于100100的元素的元素算法實(shí)現(xiàn)分析算法實(shí)現(xiàn)分析（1 1）逐個(gè)檢查鏈表的算法框架）逐個(gè)檢查鏈表的算法框架while(current != NULL).current = current-next ;ai+1ai-1.aicurrent上機(jī)練習(xí)題上機(jī)練習(xí)題(2) (2) 刪除大于刪除大于100100的鏈點(diǎn)的鏈點(diǎn)if( current-data 100)if( current-data 100)刪除該鏈點(diǎn)刪除該鏈點(diǎn) 必須找到必須找到currentcurrent的前趨鏈

22、點(diǎn)才能刪除的前趨鏈點(diǎn)才能刪除ai+1ai-1.aicurrentlastlast-next = current-next;free(current);current = last-next;刪除刪除不刪除不刪除last = current;current = current-next;上機(jī)練習(xí)題上機(jī)練習(xí)題(3)(3)邊界：第一個(gè)元素需要?jiǎng)h除時(shí)邊界：第一個(gè)元素需要?jiǎng)h除時(shí)if(last = = NULL)list-header = current-next;free(current);current = list-header;ai+1a1.aicurrentlast上機(jī)練習(xí)題上機(jī)練習(xí)題del_o

23、ver100(list_type * list)初始化初始化while(current != NULL)if(current-data 100)刪除刪除current;else走向下一個(gè)鏈點(diǎn)；走向下一個(gè)鏈點(diǎn)；體會(huì)體會(huì)llast指針的作用指針的作用l思考思考可不可以只用只用一個(gè)指針完成算法？可不可以只用只用一個(gè)指針完成算法？ 用雙向鏈表來(lái)完成本算法，有什么不同？用雙向鏈表來(lái)完成本算法，有什么不同？上機(jī)練習(xí)題上機(jī)練習(xí)題例例3、將一個(gè)單向鏈表反向連接、將一個(gè)單向鏈表反向連接算法分析算法分析（1）逐個(gè)進(jìn)行的基本框架）逐個(gè)進(jìn)行的基本框架（2）反向操作）反向操作方法一：方法一：header1header2目標(biāo)目標(biāo)上機(jī)練習(xí)題上機(jī)練習(xí)題a1方法二、直接在原鏈表的基礎(chǔ)上操作方法二、直接在原鏈表的基礎(chǔ)上操作a2a3a4a1a2a3a4ai-2ai-1aiai+1ai+2currentcontinuelastc