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

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

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

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

4、，在里面填寫后繼元素的元素的“地址地址”。請將其中的。請將其中的5張卡片按照地址大小排張卡片按照地址大小排成一列，然后再按元素線性關(guān)系填寫成一列，然后再按元素線性關(guān)系填寫“地址欄地址欄”形成一形成一個鏈表。個鏈表。l做好后，從鏈表首開始逐個尋找鏈點，體會鏈表的結(jié)構(gòu)做好后，從鏈表首開始逐個尋找鏈點，體會鏈表的結(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 長整型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訪問訪問v插入插入v刪除刪除鏈表的基本操作鏈

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

7、2從自然語言到算法語言從自然語言到算法語言l如何描述我們在鏈表上如何描述我們在鏈表上“逐個去找逐個去找”的動作的動作？v1、先找到鏈表首結(jié)點的地址、先找到鏈表首結(jié)點的地址v2、通過、通過“地址地址”，找到鏈點，找到鏈點v3、在鏈點中找到后繼元素的、在鏈點中找到后繼元素的“地址地址”v4、記錄這個地址，、記錄這個地址，回到回到2p = list-head;while( )p-data p = p-next;p-next 繼續(xù)完善描述繼續(xù)完善描述l我們需要的是找到第我們需要的是找到第i個節(jié)點個節(jié)點v1、先找到鏈表首結(jié)點的地址、先找到鏈表首結(jié)點的地址v2、通過、通過“地址地址”，找到鏈點，找到鏈點v

8、3、在鏈點中找到后繼元素的、在鏈點中找到后繼元素的“地址地址”v4、記錄這個地址，、記錄這個地址，回到回到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;計數(shù)，如果計數(shù)到i，就結(jié)束node_type *get_node( list, i )while(counter next;int counter ;nod

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

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

11、 = 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 = 1;p = list-head; 初始

12、化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)的原因插入操作插入操作 表尾插入表尾插入a

13、1ai-1aianlist-headwhile( counter next;new_node-next = p-next;p-next = new_node;p-next != NULL)NULL p插入操作插入操作else從插入算法中對鏈表操作的體會從插入算法中對鏈表操作的體會l1、鏈表操作往往從表頭開始，逐個找到、鏈表操作往往從表頭開始，逐個找到需要的鏈點需要的鏈點l2、鏈表操作的有向性、鏈表操作的有向性 不能回退；不能回退；l3、鏈表指針小心使用，謹防丟失。、鏈表指針小心使用，謹防丟失。l4、不能訪問空指針的成員、不能訪問空指針的成員l5、插入過程沒有對鏈點內(nèi)容進行搬移。、插入過程沒有對

14、鏈點內(nèi)容進行搬移。鏈表的創(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問題描述：刪除元素問題描述：刪除元素ai ;v問題分析：問題分析：輸入：鏈表，輸入：鏈表，location輸出：刪除元素后的鏈表。輸出：刪除元素后的鏈表。v算法實現(xiàn)分析算

15、法實現(xiàn)分析a1ai+1anheadtailai-1.aiai-1-next = ai-next;即即ai-1-next = ai-1-next-next;刪除操作刪除操作找到找到ai-1執(zhí)行刪除動作執(zhí)行刪除動作void deletel（list, location）注意，從鏈表上取下的鏈點注意，從鏈表上取下的鏈點ai-1需要用一個臨時指針記錄下來，需要用一個臨時指針記錄下來，否則可能丟失否則可能丟失a1ai+1anheadtailai-1.ai刪除操作刪除操作void deletel（list, location） while( counter next;p-next = p-next-nex

16、t;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 -;從鏈表刪除的鏈點，一般應(yīng)該釋放其空間刪除操作刪除操作l注意注意:v對被刪除刪除鏈點的處理對被刪除刪除鏈點的處理往往需要釋放其動態(tài)申請的空間往往需要釋放其動態(tài)申請的空間free（ ）如果希望刪除值為x的元素，如何實現(xiàn)？while( p-data = x & p != NULL) 可以嗎？while( p-ne

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

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

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

20、ist_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 list;read(x);上機練習(xí)題上機練習(xí)題例例2 2、檢查一個（單向）鏈表，刪除

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

22、-next = current-next;free(current);current = last-next;刪除刪除不刪除不刪除last = current;current = current-next;上機練習(xí)題上機練習(xí)題(3)(3)邊界：第一個元素需要刪除時邊界：第一個元素需要刪除時if(last = = NULL)list-header = current-next;free(current);current = list-header;ai+1a1.aicurrentlast上機練習(xí)題上機練習(xí)題del_over100(list_type * list)初始化初始化while(curr

23、ent != NULL)if(current-data 100)刪除刪除current;else走向下一個鏈點；走向下一個鏈點；體會體會llast指針的作用指針的作用l思考思考可不可以只用只用一個指針完成算法？可不可以只用只用一個指針完成算法？ 用雙向鏈表來完成本算法，有什么不同？用雙向鏈表來完成本算法，有什么不同？上機練習(xí)題上機練習(xí)題例例3、將一個單向鏈表反向連接、將一個單向鏈表反向連接算法分析算法分析（1）逐個進行的基本框架）逐個進行的基本框架（2）反向操作）反向操作方法一：方法一：header1header2目標目標上機練習(xí)題上機練習(xí)題a1方法二、直接在原鏈表的基礎(chǔ)上操作方法二、直接在原鏈表的基礎(chǔ)上操作a2a3a4a1a2a3a4ai-2ai-1aiai+1ai+2currentcontinuelastcurre