1 第第 3 章習(xí)題解答章習(xí)題解答 3.1與順序表相比線性鏈表有哪些優(yōu)點(diǎn)？又有哪些局限？若線性表為空，對應(yīng)的鏈表 是否一定沒有結(jié)點(diǎn)？ 3.1與順序表相比線性鏈表有哪些優(yōu)點(diǎn)？又有哪些局限？若線性表為空，對應(yīng)的鏈表 是否一定沒有結(jié)點(diǎn)？ 解答解答 與順序表相比線性鏈表的明顯優(yōu)點(diǎn)是： 1能夠靈活利用存儲空間，因為它不是依靠線性表中的數(shù)據(jù)元素在內(nèi)存中的相互 位置關(guān)系來表示數(shù)據(jù)元素間的邏輯關(guān)系， 因此它的存儲空間可以不連續(xù)， 從而有利于離散空 間的充分利用； 2由于在線性鏈表中是通過結(jié)點(diǎn)中的指針來指示數(shù)據(jù)元素之間的邏輯關(guān)系的，因此 在作插入、刪除等操作的時候避免了數(shù)據(jù)元素平移的操作，從而可以提高運(yùn)算實現(xiàn)的效率。 3由于線性鏈表所占的存儲空間完全由表結(jié)點(diǎn)的個數(shù)決定，當(dāng)需要增加或減少表中 的數(shù)據(jù)元素時， 表空間很容易擴(kuò)充和縮小。 當(dāng)然也就不會出現(xiàn)順序表中存在的表空間擴(kuò)充困 難或者是表空間利用不充分的問題。 線性鏈表的局限主要是：因為它是依靠跟在數(shù)據(jù)元素后邊的指針來表示數(shù)據(jù)元素 之間的邏輯關(guān)系的，因此每個數(shù)據(jù)元素除了本身的存儲空間之外還需要有存放指針的空間， 即它比順序表要付出更多的空間代價。 當(dāng)約定線性鏈表不帶表頭結(jié)點(diǎn)的情況下，線性表為空時，對應(yīng)的鏈表也沒有結(jié)點(diǎn)。 3.2鏈?zhǔn)綏：晚樞驐Ｔ诓僮魃系闹饕顒e是什么？為什么說對于空閑存儲空間的管理 適宜采用鏈?zhǔn)綏韺崿F(xiàn)？ 鏈?zhǔn)綏：晚樞驐Ｔ诓僮魃系闹饕顒e是什么？為什么說對于空閑存儲空間的管理 適宜采用鏈?zhǔn)綏韺崿F(xiàn)？ 解答解答 由順序棧和鏈?zhǔn)綏５慕Y(jié)構(gòu)特點(diǎn)可知，順序棧是順序存儲結(jié)構(gòu)，對其實現(xiàn)基本操作是在 連續(xù)的存儲空間上進(jìn)行的，因此順序棧的入棧、出棧、讀棧頂元素等操作主要是通過控制棧 頂指針的位置來實現(xiàn)的，也就是說，移動棧頂指針是實現(xiàn)順序棧的基本運(yùn)算的主要操作。 鏈?zhǔn)綏Ｊ且环N鏈?zhǔn)酱鎯Y(jié)構(gòu)，因此它具有鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本特點(diǎn)，它的基本運(yùn)算主 要是通過控制棧頂指針和修改棧頂結(jié)點(diǎn)的指針域的值來實現(xiàn)， 也就是說， 鏈?zhǔn)綏５幕具\(yùn)算 主要是通過改變棧頂指針和棧頂結(jié)點(diǎn)中的指針來實現(xiàn)的。 對于鏈?zhǔn)酱鎯Y(jié)構(gòu)來說，空閑的存儲空間為各鏈表所共享，當(dāng)有新元素要加入鏈表時， 需要從空閑空間取得結(jié)點(diǎn)， 再把新元素放入空閑結(jié)點(diǎn)， 然后把新結(jié)點(diǎn)加入到鏈表中； 相反地， 當(dāng)從鏈表中刪除元素時， 要釋放被刪除結(jié)點(diǎn)到空閑空間。 由于鏈表中結(jié)點(diǎn)的變化是由應(yīng)用需 要決定的， 具有明顯的隨機(jī)性， 因此在程序運(yùn)行過程中空閑存儲單元的物理位置不一定是連 續(xù)的， 顯然要統(tǒng)一管理這些空閑存儲單元適合采用鏈?zhǔn)浇Y(jié)構(gòu)； 又因為從空閑存儲空間取得結(jié) 點(diǎn)和向空閑存儲空間釋放空閑單元， 實際上是對空閑存儲空間鏈表執(zhí)行無條件的刪除和插入 操作，顯然這種不指定結(jié)點(diǎn)位置的插入、刪除操作在鏈頭進(jìn)行是最方便的?；谏鲜鲈?， 在鏈?zhǔn)酱鎯Ψ绞较?，對空閑存儲空間的管理適合采用鏈?zhǔn)綏韺崿F(xiàn)。 3.3鏈?zhǔn)疥犃信c順序隊列在基本操作上的主要差別是什么？你能舉出適宜采用鏈?zhǔn)疥?列結(jié)構(gòu)的應(yīng)用例子嗎？ 鏈?zhǔn)疥犃信c順序隊列在基本操作上的主要差別是什么？你能舉出適宜采用鏈?zhǔn)疥?列結(jié)構(gòu)的應(yīng)用例子嗎？ 解答解答 順序隊列是一種順序存儲結(jié)構(gòu)，它的數(shù)據(jù)元素入隊和出隊等基本運(yùn)算的主要操作是隊 尾指針和隊頭指針的平移；鏈?zhǔn)疥犃惺且环N鏈?zhǔn)酱鎯Y(jié)構(gòu)，它實現(xiàn)基本運(yùn)算的主要操作是 改變隊尾指針、隊尾結(jié)點(diǎn)中的指針和隊頭指針、隊頭結(jié)點(diǎn)中的指針。 由鏈?zhǔn)疥犃械慕Y(jié)構(gòu)特點(diǎn)可知， 對于需要采用隊列結(jié)構(gòu)而數(shù)據(jù)元素又不是存放在連續(xù)的存 2 儲空間中的情況適合采用鏈?zhǔn)疥犃薪Y(jié)構(gòu)。例如，一個大型實驗室的計算機(jī)管理系統(tǒng)，假設(shè)上 機(jī)者采用刷卡方式進(jìn)入和離開實驗室， 實驗室中的每個機(jī)位有唯一的編號， 由計算機(jī)系統(tǒng)為 新進(jìn)入實驗室的上機(jī)者分配機(jī)位并對上機(jī)者信息及其相應(yīng)的機(jī)位進(jìn)行管理， 若沒有空閑機(jī)位 則給出提示信息。當(dāng)有讀者離開實驗室時，系統(tǒng)收回該機(jī)位并將其管理起來。 上述管理要求中涉及到對現(xiàn)場上機(jī)者信息和座席信息的管理， 實現(xiàn)這些管理所采用的數(shù) 據(jù)結(jié)構(gòu)與管理的具體要求有關(guān)。如果對上機(jī)者信息的管理按照進(jìn)入實驗室的時間先后來組 織，對空閑機(jī)位的管理也按照收回的時間順序來組織，且以“先收回先分配”的原則使用空 閑機(jī)位， 那么可以對機(jī)位和上機(jī)者信息以結(jié)點(diǎn)形式進(jìn)行管理； 以機(jī)位編號為關(guān)鍵詞組織成存 儲結(jié)點(diǎn)， 結(jié)點(diǎn)中還包含有上機(jī)者信息和其它信息。 將僅含空閑機(jī)位編號的結(jié)點(diǎn)組織成鏈隊列， 把含有現(xiàn)場上機(jī)者信息的結(jié)點(diǎn)構(gòu)成鏈表； 當(dāng)有上機(jī)者來到時， 若鏈隊列不空則從隊列頭取得 一個空閑機(jī)位結(jié)點(diǎn)，同時把上機(jī)者信息填入結(jié)點(diǎn)，然后把該結(jié)點(diǎn)鏈入上機(jī)者鏈表的鏈頭；當(dāng) 有人下機(jī)離開實驗室時， 將相應(yīng)的結(jié)點(diǎn)從上機(jī)者鏈表中取下， 并將其置為空閑機(jī)位再鏈入空 閑機(jī)位隊列尾。這樣的資料組織方式，一方面可以滿足以時間為序的要求，另一方面避免了 經(jīng)常的資料移動，可以提高程序執(zhí)行的效率。 3.4仿照循環(huán)鏈表的結(jié)構(gòu)，對線性鏈表加上表頭結(jié)點(diǎn)會帶來什么好處？試寫出 實現(xiàn)帶表頭結(jié)點(diǎn)的線性鏈表的插入與刪除運(yùn)算的算法。 解答 3.4仿照循環(huán)鏈表的結(jié)構(gòu)，對線性鏈表加上表頭結(jié)點(diǎn)會帶來什么好處？試寫出 實現(xiàn)帶表頭結(jié)點(diǎn)的線性鏈表的插入與刪除運(yùn)算的算法。 解答 由循環(huán)鏈表的結(jié)構(gòu)特點(diǎn)可知， 線性鏈表帶有表頭結(jié)點(diǎn)的好處是： 實現(xiàn)運(yùn)算時可以使空表 和非空表的處理統(tǒng)一，從而使算法簡單。這是因為表頭結(jié)點(diǎn)不存放數(shù)據(jù)元素，無論線性表是 否為空，線性鏈表中的表頭結(jié)點(diǎn)總是存在的，因此對線性鏈表中第一個結(jié)點(diǎn)位置的插入、刪 除操作和在其它位置上的操作是一樣的，不必分別處理。在不帶表頭結(jié)點(diǎn)的情況下，因為對 表頭位置執(zhí)行插入、 刪除操作時都涉及鏈表頭指針的修改， 而在鏈表其它位置上的操作不需 要修改鏈表的頭指針。因此對空表和非空表要分別處理。 (1) 帶表頭結(jié)點(diǎn)的線性鏈表的插入運(yùn)算算法 void insertlist (linklist *hl, elemtype b, elemtype a ) /在帶表頭結(jié)點(diǎn)的線性鏈表 hl 的元素 b 之前插入元素 a，若表中不存在 b，插在鏈尾 snode *newp, *p ; newp=(snode*)malloc(sizeof(snode) ；/分配一個新結(jié)點(diǎn) if (!newp) printf(memory allocation failare!n) ； exit (1) ； newp-data=a ；/把 a 置為新結(jié)點(diǎn)的元素 p=hl-head ；/p 為當(dāng)前結(jié)點(diǎn)，初始指向表頭結(jié)點(diǎn) while ( p-next return -1；/空表，給出信息，返回特定值 else if (p-next=null)returnp-data ；/找到非空表的最后一個結(jié)點(diǎn)，返回其值 else/未找到最后結(jié)點(diǎn)，繼續(xù)查找 returnfindrear ( p-next) ； 3.6寫出實現(xiàn)線性鏈表以下操作的算法： (1) 統(tǒng)計出線性鏈表中結(jié)點(diǎn)值等于給定值的結(jié)點(diǎn)數(shù)； (2) 找出線性鏈表的最大結(jié)點(diǎn)值。 3.6寫出實現(xiàn)線性鏈表以下操作的算法： (1) 統(tǒng)計出線性鏈表中結(jié)點(diǎn)值等于給定值的結(jié)點(diǎn)數(shù)； (2) 找出線性鏈表的最大結(jié)點(diǎn)值。 解答解答 (1) 統(tǒng)計線性鏈表 hl 中結(jié)點(diǎn)值等于給定值 x 的結(jié)點(diǎn)數(shù)的算法 int count_node (linklist *hl, int x )/返回鏈表 hl 中結(jié)點(diǎn)值為 x 的結(jié)點(diǎn)數(shù) snode *p=hl-head ；/準(zhǔn)備從第一個結(jié)點(diǎn)開始查找 int count=0 ；/置結(jié)點(diǎn)個數(shù)計數(shù)初值為 0 while ( p )/逐個查找結(jié)點(diǎn)值 if ( p-data=x )count+ ；/若結(jié)點(diǎn)值為 x，計數(shù)加 1 p=p-next ； return count ；/返回結(jié)點(diǎn)個數(shù) (2) 找出線性鏈表 hl 的最大結(jié)點(diǎn)值的算法 elemtypefind_max (linklist *hl)/返回線性鏈表 hl 的最大結(jié)點(diǎn)值 snode *p ; elemtypevalue ; 4 if (hl-head=null)/鏈表空，給出信息，返回特定值 printf ( linked list is empty!n) ； return -1 ； p=hl-head ； value= p-data ；/ value存放最大結(jié)點(diǎn)值，初始為第一個結(jié)點(diǎn)值 while ( p )/依次比較鏈表各結(jié)點(diǎn)的值 if (p-data value)value=p-data ； /若遇有比 value 更大的結(jié)點(diǎn)值， 將其記入value p=p-next ； returnvalue ；/返回最大結(jié)點(diǎn)值 3.7寫出在線性鏈表 lh 的中查找結(jié)點(diǎn)值(元素值)為 x 的第 1 個結(jié)點(diǎn)，返回其指針的 遞歸算法。 解答 3.7寫出在線性鏈表 lh 的中查找結(jié)點(diǎn)值(元素值)為 x 的第 1 個結(jié)點(diǎn)，返回其指針的 遞歸算法。 解答 snode *findnode ( snode *lh-head, elemtype x)/給定線性鏈表的頭指針及查找值 snode *p=lh-head ；/p 為當(dāng)前結(jié)點(diǎn)，初始指向表頭結(jié)點(diǎn) if (p=null)returnnull ；/空表，返回空指針 else if (p-data=x)returnp ；/找到元素值為 x 的結(jié)點(diǎn)，返回其指針 else/未找到值為 x 的結(jié)點(diǎn)，繼續(xù)查找 returnfindnode ( p-next，x) ； 3.8假設(shè)線性鏈表的結(jié)點(diǎn)是按值以非遞減有序鏈接的，寫出向線性鏈表插入元素 x 后，使線性鏈表仍然保持有序的算法。 解答 3.8假設(shè)線性鏈表的結(jié)點(diǎn)是按值以非遞減有序鏈接的，寫出向線性鏈表插入元素 x 后，使線性鏈表仍然保持有序的算法。 解答 算法描述如下： void insert_node(linklist *hl, elemtype x ) /向有序鏈表 hl 插入新元素 x 并保持其的有序性 snode *p, *q ; snode *s= new snode ；/為 x 建立新結(jié)點(diǎn) s-data = x ； s-next = null ； /若 hl 為空或小于第 1 個結(jié)點(diǎn)值，把新結(jié)點(diǎn)插入到鏈頭 if (hl-head=null | xdata) s-next = hl-head ； hl-head = s ； else/在鏈中尋找新結(jié)點(diǎn)的插入位置 q= h-head ； p= q-next ； while ( p initlist (hp) ；/初始化正數(shù)鏈表和負(fù)數(shù)鏈表 initlist (hn) ； p= hl-head ；/p 指向 hl 的頭 while ( p )/從 hl 鏈頭開始判斷的每個結(jié)點(diǎn)值的正負(fù)性作并相應(yīng)處理 q= p ；/q 指向當(dāng)前要從 hl 鏈上拆下的結(jié)點(diǎn) p= p-next ；/使 p 始終指向 hl 鏈的第 1 個結(jié)點(diǎn) if (q-data 0)/當(dāng)前要處理的結(jié)點(diǎn)值為正數(shù)，將其接到正數(shù)鏈頭 q-next=hp-head ; hp-next=q ; else/當(dāng)前要處理的結(jié)點(diǎn)值為負(fù)數(shù)，將其接到負(fù)數(shù)鏈頭 q-next=hn-head ; he-next = q ； 3.12分別寫一個算法，對帶表頭結(jié)點(diǎn)和不帶表頭結(jié)點(diǎn)情況，實現(xiàn)將兩個非遞減有序的 線性鏈表合并為一個非遞減有序鏈表，合并后使原鏈表為空。 解答 分別寫一個算法，對帶表頭結(jié)點(diǎn)和不帶表頭結(jié)點(diǎn)情況，實現(xiàn)將兩個非遞減有序的 線性鏈表合并為一個非遞減有序鏈表，合并后使原鏈表為空。 解答 (1) 不帶表頭結(jié)點(diǎn)的非遞減有序線性鏈表合并的算法： void mergelist (linklist *ha, linklist *hb, linklist *hc ) /ha, hb 為非遞減有序線性鏈表，合并為非遞減有序線性鏈表 hc /p, q 指向待合并鏈的鏈頭結(jié)點(diǎn),r 指向已合并鏈的尾結(jié)點(diǎn) snode *r, *p= ha-head, *q= hb-head ； /p、q 初始分別指向 ha 和 hb 的鏈頭結(jié)點(diǎn) 7 initlist (hc) ；/鏈表 hc 初始化 hc-head = p ；/把 ha 設(shè)置為基本鏈，準(zhǔn)備把 hb 中的結(jié)點(diǎn)插入到 ha 的合適位置實現(xiàn)合并 if (!q )return ；/hb 是空表，返回 ha 結(jié)束合并 if (!p) hc-head= q；return ；/ha 是空表，返回 hb 結(jié)束合并 if ( p-data data )/ha 鏈頭結(jié)點(diǎn)值不大于 hb 的鏈頭結(jié)點(diǎn)值 r = p ；/使 ha 的鏈頭結(jié)點(diǎn)成為 hc 的鏈頭結(jié)點(diǎn) p = p-next ； else/hb 鏈頭結(jié)點(diǎn)值小于 ha 鏈頭結(jié)點(diǎn)值 hc-head = q； r = q ；/把 hb 的鏈頭結(jié)點(diǎn)鏈接到 hc 的鏈頭 q = q-next ； r-next = p ； while (p for ( i=1；in；i+)ai=i+1；/數(shù)組 a 初始化，報數(shù)人構(gòu)成圓圈 an=1； k=1； for (i=1；i=n；i+)/報數(shù)過程一直到 n 個人全部出列 for ( j=1；jhead ；/p初始指向多項式鏈表 a 頭結(jié)點(diǎn) q= b-head ；/q 初始指向多項式鏈表 b 頭結(jié)點(diǎn) if (!p ) c.head = b-head ；/多項式鏈表 a 空 if (!q ) c.head =a-head ；/多項式鏈表 b 空 while ( p c-head = newp ； else/新結(jié)點(diǎn)接到多項式鏈表的尾 r-next = newp ；r = newp ； if (!p r = c-head ； while (!r )/輸出和多項式 printf ( ( %f, %d ) , r-coef , r-exp ) ； r = r-next ； printf (n) ; sum= 0.0 ； while (!s )/求出和多項式的值 12 y= s-exp ； sum = sum + s-coef * pow (x, y) ； s = s-next ； printf ( polynomial sum ：%f n, sum ；/輸出和多項式的值 3.16別指出下列廣義表的表頭、表尾、表長度和表深度。 (1) (),(a)； (2) (a,(b,(c)； (3) (a,b),c,(d)； (4) (a,(a,b),c,(d,e),f),g)。 解答 3.16別指出下列廣義表的表頭、表尾、表長度和表深度。 (1) (),(a)； (2) (a,(b,(c)； (3) (a,b),c,(d)； (4) (a,(a,b),c,(d,e),f),g)。 解答 (1) 對于廣義表(),(a)：表頭是空子表()，表尾是子表(a)，表長度為 2，表深度為 2 ； (2) 對于廣義表(a,(b,(c)：表頭是原子 a，表尾是子表(b,(c)，表長度為 2，表 深度為 3 ； (3) 對于廣義表(a,b),c,(d)：表頭是子表（a,b） ，表尾是子表(c,(d)，表長度為 3， 表深度為 2 ； (4) 對于廣義表(a,(a,b),c,(d,e),f),g)：表頭是子表(a,(a,b)，表尾是子表 (c,(d,e),f),g)，表長度為 3，表深度為 4 。 3.17分別畫出下列廣義表的無附加表頭結(jié)點(diǎn)和帶附加表頭結(jié)點(diǎn)的存儲結(jié)構(gòu)示意圖。 (1) a(a,(b,(c,d),(e,f),(c,(d)； (2) b(a),(c,d),e,(b,(c,(d,(f)。 解答 3.17分別畫出下列廣義表的無附加表頭結(jié)點(diǎn)和帶附加表頭結(jié)點(diǎn)的存儲結(jié)構(gòu)示意圖。 (1) a(a,(b,(c,d),(e,f),(c,(d)； (2) b(a),(c,d),e,(b,(c,(d,(f)。 解答 根據(jù)附加表頭結(jié)點(diǎn)的約定即可以畫出。 3.18 寫出對廣義表實現(xiàn)以下運(yùn)算的算法； (1) 在廣義表的表頭元素之前插入一個元素 x ； (2) 清空并釋放廣義表。 (3) 從廣義表中找出原子結(jié)點(diǎn)值等于給定值 t 的算法，返回查找是否成功。 3.18 寫出對廣義表實現(xiàn)以下運(yùn)算的算法； (1) 在廣義表的表頭元素之前插入一個元素 x ； (2) 清空并釋放廣義表。 (3) 從廣義表中找出原子結(jié)點(diǎn)值等于給定值 t 的算法，返回查找是否成功。 解答解答 (1) 在廣義表表頭元素前插入一個元素 x 算法描述如下： void insertgl (glnode *first, elemtype x)/first 指向廣義表表頭結(jié)點(diǎn)，x 待插入的數(shù)據(jù)元素 glnode *p ; p= (glnode*)malloc(sizeof(glnode) ；/為 x 分配一個新結(jié)點(diǎn) p-flag=1；/設(shè)定新結(jié)點(diǎn)為原子結(jié)點(diǎn) p-value.data = x ；/置 x 到新結(jié)點(diǎn)的數(shù)據(jù)域 p-next = first-value.sublist ；/原第 1 個結(jié)點(diǎn)成為同層的后繼結(jié)點(diǎn) first-value.sublist = p ；/新結(jié)點(diǎn)成為第 1 個結(jié)點(diǎn) (2) 清空并釋放廣義表演算法描述如下： 13 void cleargl(glnode *first)/first 向廣義表表頭結(jié)點(diǎn) glnode *p, *q ; if ( first ) if (fist-flag= head | fist-flag= slist)/表頭結(jié)點(diǎn)或子表頭結(jié)點(diǎn), 遞歸釋放子表 p=first-value.sublist ； cleargl (p ) ； q = first-next ； if (q )cleagl (q) ；/遞歸釋放表尾 free (first) ；/釋放本結(jié)點(diǎn) first = null ； (3) 查找給定值的原子結(jié)點(diǎn)算法描述如下： glnode *find_value (glnode *first, elemtype x ) /在廣義表中查找元素值為 x 的結(jié)點(diǎn)，first 為指向表頭的指針，返回結(jié)點(diǎn)號 glnode *p, *q, *ret1, *ret2 ; if (!first )return null ；/廣義表空，返回空指針 /如果找到原子結(jié)點(diǎn)值，返回結(jié)點(diǎn)指針 if (first-flag=1 while ( h )/一直做到線性鏈表 hl 為空 p = h；q = p ；/p 當(dāng)前要比較的結(jié)點(diǎn),q 將指 p 的前一個結(jié)點(diǎn) min = p-data ；/min 為最小值 while ( p )/掃描全表 if (p-data next ； printf ( value:%d n, p-data ) ；/輸出當(dāng)前最小值 r-next = t-next ；/刪除最小元素結(jié)點(diǎn) free (t) ；/釋放被刪除的結(jié)點(diǎn) hl-head=h ； 3.3對帶表頭結(jié)點(diǎn)和不帶表頭結(jié)點(diǎn)的雙向鏈表實現(xiàn)以下運(yùn)算：3.3對帶表頭結(jié)點(diǎn)和不帶表頭結(jié)點(diǎn)的雙向鏈表實現(xiàn)以下運(yùn)算： (1) 在雙向鏈表的元素 b 之前插入一個元素 x；在雙向鏈表的元素 b 之前插入一個元素 x； (2) 從雙向鏈表中刪除元素 b 。 參考算法 從雙向鏈表中刪除元素 b 。 參考算法 (1) 假設(shè)雙向鏈表不帶表頭結(jié)點(diǎn)，實現(xiàn)所要求的插入運(yùn)算算法描述如下： void ins_dlklist (dlklist *hl, elemtype b, elemtype x) /在雙向鏈表 hl 的數(shù)據(jù)元素 b 之前插入一個包含數(shù)據(jù)元素 x 的新結(jié)點(diǎn) dnode *newp, p, q ; newp=(dnode*)malloc(sizeof(dnode) ；/為待插入元素分配一個新結(jié)點(diǎn) 15 if ( !newp )/檢查新結(jié)點(diǎn)是否分配成功 printf (memory allocation failare ! n) ； exit (1) ； newp-data= x ；/把 x 存入新結(jié)點(diǎn)的數(shù)據(jù)域 newp-llink=newp-rl