第2章數(shù)據(jù)結(jié)構(gòu)-線性表

數(shù)據(jù)結(jié)構(gòu)

(Python語言描述)

李粵平

線性表是同一類型數(shù)據(jù)的一個(gè)有限序列，數(shù)據(jù)之間在邏輯上存在著線性關(guān)系。線性結(jié)構(gòu)是最常用、最簡單的一種數(shù)據(jù)結(jié)構(gòu)。而其基本特點(diǎn)是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種結(jié)構(gòu)中：①存在一個(gè)唯一的被稱為“第一個(gè)”的數(shù)據(jù)元素；②存在一個(gè)唯一的被稱為“最后一個(gè)”的數(shù)據(jù)元素；③除第一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接前驅(qū)；④除最后一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接后繼第2章

線性表—順序表和鏈表2.1線性表的定義線性表的定義線性表(LinearList)：是由n(n≧0)個(gè)數(shù)據(jù)元素(節(jié)點(diǎn))a1，a2，…an組成的有限序列。該序列中的所有節(jié)點(diǎn)具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長度。當(dāng)n=0時(shí)，稱為空表。當(dāng)n>0時(shí)，將非空的線性表記作：(a1，a2，…an)a1稱為線性表的第一個(gè)(首)節(jié)點(diǎn)，an稱為線性表的最后一個(gè)(尾)節(jié)點(diǎn)。a1，a2，…ai-1都是ai(2≦i≦n)的前驅(qū)，其中ai-1是ai的直接前驅(qū);ai+1，ai+2，…an都是ai(1≦i≦n-1)的后繼，其中ai+1是ai的直接后繼。線性表

線性表中的數(shù)據(jù)元素ai所代表的具體含義隨具體應(yīng)用的不同而不同，在線性表的定義中，只不過是一個(gè)抽象的表示符號?！艟€性表中的節(jié)點(diǎn)可以是單值元素(每個(gè)元素只有一個(gè)數(shù)據(jù)項(xiàng))。判斷以下結(jié)構(gòu)是否為線性結(jié)構(gòu)結(jié)構(gòu)1結(jié)構(gòu)2結(jié)構(gòu)3結(jié)構(gòu)42.2

順序表

順序存儲(chǔ)：把線性表的節(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡稱順序表。順序存儲(chǔ)的線性表的特點(diǎn)：

◆線性表的邏輯順序與物理順序一致;

◆數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來體現(xiàn)。設(shè)有非空的線性表：(a1，a2，…an)。順序存儲(chǔ)如圖2-1所示。線性表的順序存儲(chǔ)結(jié)構(gòu)

在具體的機(jī)器環(huán)境下：設(shè)線性表的每個(gè)元素需占用L個(gè)存儲(chǔ)單元，以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足下列關(guān)系：

LOC(ai+1)=LOC(ai)+L

線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：

LOC(ai)=LOC(a1)+(i-1)*L

Loc(a1)Loc(ai)+(i-1)*L圖2-1

線性表的順序存儲(chǔ)表示2.2.1

順序表的基本操作

順序存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長度等。以下將對幾種主要的操作進(jìn)行討論。順序線性表初始化

為數(shù)組分配連續(xù)的存儲(chǔ)空間，時(shí)間復(fù)雜度O(1).

2

順序線性表的插入

在線性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)個(gè)位置上插入一個(gè)新節(jié)點(diǎn)e，使其成為線性表：

L=(a1，…ai-1，e，ai，ai+1，…，an)

實(shí)現(xiàn)步驟(1)

將線性表L中的第i個(gè)至第n個(gè)節(jié)點(diǎn)后移一個(gè)位置。(2)將節(jié)點(diǎn)e插入到節(jié)點(diǎn)ai-1之后。(3)線性表長度加1。

時(shí)間復(fù)雜度分析

在線性表L中的第i個(gè)元素之前插入新節(jié)點(diǎn)，其時(shí)間主要耗費(fèi)在表中節(jié)點(diǎn)的移動(dòng)操作上，因此，可用節(jié)點(diǎn)的移動(dòng)來估計(jì)算法的時(shí)間復(fù)雜度。

設(shè)在線性表L中的第i個(gè)元素之前插入節(jié)點(diǎn)的概率為Pi，不失一般性，設(shè)各個(gè)位置插入是等概率，則Pi=1/(n+1)，而插入時(shí)移動(dòng)節(jié)點(diǎn)的次數(shù)為n-i+1。總的平均移動(dòng)次數(shù)：Einsert=∑pi*(n-i+1)(1≦i≦n)∴Einsert=n/2。即在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半節(jié)點(diǎn)。當(dāng)表長n較大時(shí)，算法的效率相當(dāng)?shù)汀Ｒ虼怂惴ǖ钠骄鶗r(shí)間復(fù)雜度為O(n)。3順序線性表的刪除

在線性表L=(a1，…ai-1，ai，ai+1，…，an)中刪除節(jié)點(diǎn)ai(1≦i≦n)，使其成為線性表：

L=(a1，…ai-1，ai+1，…，an)

實(shí)現(xiàn)步驟(1)

將線性表L中的第i+1個(gè)至第n個(gè)節(jié)點(diǎn)依此向前移動(dòng)一個(gè)位置。(2)線性表長度減1。

時(shí)間復(fù)雜度分析

刪除線性表L中的第i個(gè)元素，其時(shí)間主要耗費(fèi)在表中節(jié)點(diǎn)的移動(dòng)操作上，因此，可用節(jié)點(diǎn)的移動(dòng)來估計(jì)算法的時(shí)間復(fù)雜度。

設(shè)在線性表L中刪除第i個(gè)元素的概率為Pi，不失一般性，設(shè)刪除各個(gè)位置是等概率，則Pi=1/n，而刪除時(shí)移動(dòng)節(jié)點(diǎn)的次數(shù)為n-i。則總的平均移動(dòng)次數(shù)：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。即在順序表上做刪除運(yùn)算，平均要移動(dòng)表上一半節(jié)點(diǎn)。當(dāng)表長n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算法的平均時(shí)間復(fù)雜度為O(n)。4順序線性表的查找定位刪除

在線性表L=(a1，a2，…，an)中刪除值為x的第一個(gè)節(jié)點(diǎn)。實(shí)現(xiàn)步驟(1)在線性表L查找值為x的第一個(gè)數(shù)據(jù)元素。(2)將從找到的位置至最后一個(gè)節(jié)點(diǎn)依次向前移動(dòng)一個(gè)位置。(3)線性表長度減1。

時(shí)間復(fù)雜度分析

時(shí)間主要耗費(fèi)在數(shù)據(jù)元素的比較和移動(dòng)操作上。首先，在線性表L中查找值為x的節(jié)點(diǎn)是否存在;其次，若值為x的節(jié)點(diǎn)存在，且在線性表L中的位置為i，則在線性表L中刪除第i個(gè)元素。設(shè)在線性表L刪除數(shù)據(jù)元素概率為Pi，不失一般性，設(shè)各個(gè)位置是等概率，則Pi=1/n。

◆比較的平均次數(shù)：Ecompare=∑pi*i(1≦i≦n)∴Ecompare=(n+1)/2。

◆刪除時(shí)平均移動(dòng)次數(shù)：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。平均時(shí)間復(fù)雜度：Ecompare+Edelete=n，即為O(n)有序線性表的定義和實(shí)現(xiàn)有序線性表是指線性表中的元素是按照值或關(guān)鍵字的大小先后有序排列。有序線性表的運(yùn)算除了繼承一般線性表的所有運(yùn)算外，還有按值或關(guān)鍵字進(jìn)行插入、刪除和查找元素等的特殊運(yùn)算。查找元素的方法：二分查找。時(shí)間復(fù)雜度為O(log2n)。而一般線性表為O(n)。有關(guān)線性表的順序存儲(chǔ)，下列表述正確的是：順序就是線性表的元素按值排好序線性表元素從前往后存儲(chǔ)的地址是遞增的線性表元素從前往后存儲(chǔ)的地址是遞減的線性表元素從前往后存放在連續(xù)的地址空間ABCD2.3單鏈表

2.3.1

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線性表簡稱線性鏈表。存儲(chǔ)鏈表中節(jié)點(diǎn)的一組任意的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。鏈表中節(jié)點(diǎn)的邏輯順序和物理順序不一定相同。

為了正確表示節(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)節(jié)點(diǎn)值（值域）的同時(shí)，還必須存儲(chǔ)指示其直接后繼節(jié)點(diǎn)的地址（指針域），稱為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的節(jié)點(diǎn)結(jié)構(gòu)。每一個(gè)節(jié)點(diǎn)只包含一個(gè)指針域的鏈表，稱為單鏈表，否則稱為多鏈表。為操作方便，總是在鏈表的第一個(gè)節(jié)點(diǎn)之前附設(shè)一個(gè)表頭節(jié)點(diǎn)(head)指向第一個(gè)節(jié)點(diǎn)。表頭節(jié)點(diǎn)的值域可以不存儲(chǔ)任何信息。datanext圖2-2

鏈表節(jié)點(diǎn)結(jié)構(gòu)data：值域，存放節(jié)點(diǎn)的值。next：指針域，存放節(jié)點(diǎn)的直接后繼的地址。

3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfat

hat?head

圖2-3

帶頭節(jié)點(diǎn)的單鏈表的邏輯狀態(tài)、物理存儲(chǔ)方式

單鏈表是由表頭唯一確定，因此單鏈表可以用表頭的名字來命名。例1、線性表L=(bat，cat，eat，fat，hat)其帶表頭節(jié)點(diǎn)的單鏈表的邏輯狀態(tài)和物理存儲(chǔ)方式如圖2-3所示。單鏈表的各種不同形式一般形式的單鏈表循環(huán)單鏈表帶附加表頭結(jié)點(diǎn)的單鏈表單鏈表的各種不同形式帶表頭附加結(jié)點(diǎn)的空表帶附加表頭結(jié)點(diǎn)的循環(huán)單鏈表帶表頭附加結(jié)點(diǎn)的循環(huán)空表雙向鏈表的各種不同形式一般形式的雙向鏈表循環(huán)雙向鏈表只有一個(gè)結(jié)點(diǎn)的循環(huán)雙向鏈表雙向鏈表的各種不同形式帶附加表頭結(jié)點(diǎn)的循環(huán)雙向空表帶附加表頭結(jié)點(diǎn)的循環(huán)雙向鏈表比較線性表順序存儲(chǔ)與鏈接存儲(chǔ)順序存儲(chǔ)通常直接用數(shù)組實(shí)現(xiàn)，因此各元素的存儲(chǔ)空間是連續(xù)的，可以直接用下標(biāo)訪問。例如，A[3]。鏈接存儲(chǔ)結(jié)構(gòu)中，表的各元素存儲(chǔ)空間不一定是連續(xù)的。要依賴節(jié)點(diǎn)里面的引用（指針）來記錄下一節(jié)點(diǎn)。一般來說，訪問表的元素要從表頭元素開始，逐個(gè)往后尋找current=current.next有關(guān)線性表的鏈?zhǔn)酱鎯?chǔ)，下列表述正確的是：線性表元素從前往后存儲(chǔ)的地址肯定不連續(xù)線性表元素從前往后存儲(chǔ)的值是連續(xù)的線性表元素從前往后存儲(chǔ)的地址不一定是連續(xù)的線性表元素從前往后存儲(chǔ)的地址是遞增的ABCD鏈表結(jié)構(gòu)中常見的引用（指針）操作①

q=ppa……操作前pa……q操作后②

q=p.nextbpa……操作前操作后qbpa……③

p=p.nextbpa……操作前操作后pba……④

q.next=pc…pbqa……操作前操作后qb……ac…p2.3.2線性單鏈表的基本操作1

建立單鏈表頭插入法建表尾插入法建表2

單鏈表的查找按序號查找對于單鏈表，不能象順序表中那樣直接按序號i訪問節(jié)點(diǎn)，而只能從鏈表的頭節(jié)點(diǎn)出發(fā)，沿鏈域next逐個(gè)節(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)節(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。設(shè)單鏈表的長度為n，要查找表中第i個(gè)節(jié)點(diǎn)，僅當(dāng)1≦i≦n時(shí)，i的值是合法的。按值查找不帶表頭的鏈表，在頭部插入節(jié)點(diǎn)p建立鏈表。下面代碼是正確的是：head=p.next;p=head.nextp=p.next;head=pp.next=head;head=pa1=ak.next;head=a1.nextABCDheada1akp帶表頭的鏈表，在頭部插入節(jié)點(diǎn)p建立鏈表。下面代碼是正確的是：head.next=p;p.next=headp.next=head.next;head.next=phead=p;p.next=headak.next=a1;head.next=akABCDheada1akp在尾部插入節(jié)點(diǎn)p建立鏈表。下面代碼是正確的是：head.next=p;p.next=headp.next=tail.next;tail=ptail.next=p;tail=pai.next=ak;tail=akABCDheada1akpaitail…NoneNone3

單鏈表的插入插入運(yùn)算是將值為p的新節(jié)點(diǎn)插入到表的第i個(gè)節(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的節(jié)點(diǎn)e，新節(jié)點(diǎn)p的后繼設(shè)置為e的后繼（ai所在的節(jié)點(diǎn)），新節(jié)點(diǎn)p作為e的直接后繼節(jié)點(diǎn)。4

單鏈表的刪除刪除單鏈表中的第i個(gè)節(jié)點(diǎn)。為了刪除第i個(gè)節(jié)點(diǎn)ai，必須找到節(jié)點(diǎn)的存儲(chǔ)地址。該存儲(chǔ)地址是在其直接前趨節(jié)點(diǎn)ai-1的next域中，因此，必須首先找到ai-1的存儲(chǔ)位置p，然后令p.next指向ai的直接后繼節(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。將新節(jié)點(diǎn)p插入到ai-1與ai之間。下面代碼是正確的是：p.next=e.next;e.next=pp=p.next;e.next=pe=p.next;p=ee.next=p;p.next=e.nextABCDai-1akepai將節(jié)點(diǎn)f刪除。下面代碼是正確的是：e.next=f;f.next=ee=e.next;f.next=ef.next=e.nexte.next=f.nextABCDai-1eaif2.3.3鏈表與順序表的比較空間

順序表在初始化時(shí)需要分配好存儲(chǔ)空間，即順序表存儲(chǔ)空間大小時(shí)固定的。當(dāng)線性表長度變化較大時(shí)，即不知道需要存儲(chǔ)多少元素，這時(shí)就難以確定存儲(chǔ)空間的大小，存儲(chǔ)空間分小了，不能夠存儲(chǔ)足夠的元素，容易造成溢出。存儲(chǔ)空間分大了，又會(huì)造成空間浪費(fèi)。采用線性存儲(chǔ)時(shí)，按需分配，不用去考慮表的存儲(chǔ)空間開多大比較合適。時(shí)間

順序表查找元素操作時(shí)間復(fù)雜度為O(1)，因?yàn)轫樞虮硎怯靡唤M連續(xù)的存儲(chǔ)單元來存儲(chǔ)數(shù)據(jù)元素，所以在插入和刪除元素的時(shí)候，需要向后或者向前移動(dòng)一個(gè)元素的位置，時(shí)間復(fù)雜度為O(n)。而單鏈表，由于是用一組任意的存儲(chǔ)單元來存儲(chǔ)數(shù)據(jù)元素，所以在查找元素操作的時(shí)間復(fù)雜度為O(n)，插入和刪除元素操作不需要移動(dòng)表中的元素，需要用改變指針的指向即可，因此時(shí)間復(fù)雜度為O(1)。2.4

雙鏈表

雙鏈表(DoubleLinkedList):指的是構(gòu)成鏈表的每個(gè)節(jié)點(diǎn)中設(shè)立兩個(gè)指針域：一個(gè)指向其直接前趨的指針域prior，一個(gè)指向其直接后繼的指針域next。這樣形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙鏈表。和單鏈表類似，雙向鏈表一般增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便。將頭節(jié)點(diǎn)和尾節(jié)點(diǎn)鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向循環(huán)鏈表。雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。2.4.1雙鏈表的節(jié)點(diǎn)及其類型定義datanextprior圖2-4雙向鏈表節(jié)點(diǎn)形式……非空雙向鏈表head?a2a1an?空雙向鏈表head??圖2-5帶頭節(jié)點(diǎn)的雙向鏈表形式雙向鏈表結(jié)構(gòu)具有對稱性，設(shè)p指向雙向鏈表中的某一節(jié)點(diǎn)，則其對稱性可用下式描述：(p.prior).next=p=(p.next).prior2.4.2雙向鏈表的基本操作雙向鏈表的插入

將值為e的節(jié)點(diǎn)插入雙向鏈表中。插入前后鏈表的變化如圖2-6所示。注意：

與單鏈表的插入和刪除操作不同的是，在雙向鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針域的指向。Sep…………aiai+1Sep…………aiai+1圖2-6雙向鏈表的插入在鏈表任意位置插入新節(jié)點(diǎn)

將新節(jié)點(diǎn)插入鏈表中第i個(gè)位置，首先要遍歷到鏈表的第i-1個(gè)位置的節(jié)點(diǎn)，然后需要進(jìn)行兩部分的操作:第一部分是將第i-1個(gè)位置節(jié)點(diǎn)的后繼指針指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的前驅(qū)指針指向第i-1個(gè)位置的節(jié)點(diǎn)；第二部分是將新節(jié)點(diǎn)的后繼指針指向第i個(gè)位置的節(jié)點(diǎn)，第i個(gè)位置節(jié)點(diǎn)的直接前驅(qū)指針指向新節(jié)點(diǎn)。新節(jié)點(diǎn)插入成功，算法結(jié)束。foriinrange(index-1):

pre=pre.next#第index個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)next=pre.next#將新節(jié)點(diǎn)的后繼指針指向鏈表中第index+1個(gè)節(jié)點(diǎn)newNode.next=next#鏈表中第index+1個(gè)節(jié)點(diǎn)的前驅(qū)指針指向新節(jié)點(diǎn)next.prev=newNode

對于單鏈表，由于每個(gè)節(jié)點(diǎn)只存儲(chǔ)了后繼指針，到了尾部就停止了向后的操作也就是說，按照這樣的方式，只能索引后繼結(jié)點(diǎn)不能索引前驅(qū)結(jié)點(diǎn)。

這會(huì)帶來什么問題呢？

例如不從頭節(jié)點(diǎn)出發(fā)，就無法訪問到全部節(jié)點(diǎn)。事實(shí)上要解決這個(gè)問題只需要：

將單鏈表中尾部節(jié)點(diǎn)的后繼指針由空改為指向頭節(jié)點(diǎn)。

這種頭尾相接的單鏈表成為單循環(huán)鏈表，簡稱循環(huán)鏈表。2.5

循環(huán)鏈表2.5.1循環(huán)鏈表的基本操作循環(huán)鏈表的尾插入法情況一：鏈表為空，將頭、尾指針指向新節(jié)點(diǎn)。情況二：鏈表不為空，將尾節(jié)點(diǎn)的直接后繼指針指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的直接后繼指針指向頭節(jié)點(diǎn)，如下圖所示。循環(huán)鏈表的刪除節(jié)點(diǎn)情況一：鏈表為空，無法刪除節(jié)點(diǎn)，拋出異常。情況二：鏈表不為空且鏈表只有一個(gè)節(jié)點(diǎn)，將頭、尾指向空。情況三：鏈表不為空且鏈表有多個(gè)節(jié)點(diǎn)，將鏈表中倒數(shù)第二個(gè)節(jié)點(diǎn)的直接后繼指向頭節(jié)點(diǎn)，將尾指點(diǎn)的直接后繼指向空。如下圖所示。有序線性表節(jié)點(diǎn)的關(guān)鍵字有序的線性表稱為有序線性表有序線性表與一般線性表主要差異在于節(jié)點(diǎn)插入操作首先要找到合適位置的節(jié)點(diǎn)插入到該節(jié)點(diǎn)的前方或者與該節(jié)點(diǎn)合并（更新值域）例題

一元多項(xiàng)式的表示和相加一元多項(xiàng)式p(x)=p0+p1x+p2x2+…

+pnxn，由n+1個(gè)系數(shù)唯一確定。則在計(jì)算機(jī)中可用線性表(p0

，p1

，p2

，…

，pn

)表示。既然是線性表，就可以用順序表和鏈表來實(shí)現(xiàn)。兩種不同實(shí)現(xiàn)方式的元素類型定義如下：(1)順序存儲(chǔ)表示的類型ClassNode:def__init__(self): self.cof=None#系數(shù)部分self.exp=None#指數(shù)部分(2)鏈?zhǔn)酱鎯?chǔ)表示的類型ClassNode:def__init__(self): self.cof=None#系數(shù)部分self.exp=None#指數(shù)部分self.next=None#后繼的引用一元多項(xiàng)式的相加不失一般性，設(shè)有兩個(gè)一元多項(xiàng)式：P(x)=p0+p1x+p2x2+…

+pnxn，Q(x)=q0+q1x+q2x2+…

+qmxmR(x)=P(x)+Q(x)

R(x)由線性表R((p0+q0)，(p1+q1)，(p2+q2)，…

，(pm+qm)，…

，

pn)唯一表示。兩種存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)方式⑴

順序存儲(chǔ)表示的相加用順序表示的相加非常簡單。訪問第5項(xiàng)可直接訪問：L.a[4].cof，

L.a[4].exp(2)

鏈?zhǔn)酱鎯?chǔ)表示的相加

當(dāng)采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)，根據(jù)節(jié)點(diǎn)類型定義，凡是系數(shù)為0的項(xiàng)不在鏈表中出現(xiàn)，從而可以大大減少鏈表的長度。一元多項(xiàng)式的相加一元多項(xiàng)式相加的實(shí)質(zhì)是：

指數(shù)不同：是鏈表的合并。

指數(shù)相同：系數(shù)相加，和為0，去掉節(jié)點(diǎn)，和不為0，修改節(jié)點(diǎn)的系數(shù)域。算法之一：就在原來兩個(gè)多項(xiàng)式鏈表的基礎(chǔ)上進(jìn)行相加，相加后原來兩個(gè)多項(xiàng)式鏈表就不在存在。當(dāng)然再要對原來兩個(gè)多項(xiàng)式進(jìn)行其它操作就不允許了。一元多項(xiàng)式的相加算法之二：對兩個(gè)多項(xiàng)式鏈表進(jìn)行相加，生成一個(gè)新的相加后的結(jié)果多項(xiàng)式鏈表，原來兩個(gè)多項(xiàng)式鏈表依然存在，不發(fā)生任何改變，如果要再對原來兩個(gè)多項(xiàng)式進(jìn)行其它操作也不影響。下面哪些情形是單鏈表形成了圈？NoneNone微軟面試題（初級難度）如何用最少個(gè)數(shù)的額外變量去判斷一個(gè)單鏈表形成圈？請給出需要額外變量的個(gè)數(shù)和你算法的時(shí)間復(fù)雜度。微軟面試題（中級難度）如何用最少個(gè)數(shù)的額外變量去判斷兩條單鏈表是否相交？請給出需要額外變量的個(gè)數(shù)和你算法的時(shí)間復(fù)雜度。