雍巧玲
(喀什大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,新疆 喀什 844000)
隨著社會(huì)的發(fā)展和科技的進(jìn)步,計(jì)算機(jī)已被廣泛應(yīng)用。由于計(jì)算機(jī)計(jì)算速度快,存儲(chǔ)容量大,使用方便,用途廣,給科技發(fā)展助力不少,不少高校設(shè)置了計(jì)算機(jī)相關(guān)專業(yè)及相關(guān)課程。其中,“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)專業(yè)課程中的一門核心基礎(chǔ)課程,課程內(nèi)容包含了數(shù)據(jù)的各種存儲(chǔ)結(jié)構(gòu)和組織數(shù)據(jù)的方式。在數(shù)據(jù)結(jié)構(gòu)中,雙向鏈表是一種典型的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu),也是教學(xué)當(dāng)中的重點(diǎn)案例。目前,在出版的一些數(shù)據(jù)結(jié)構(gòu)相關(guān)教材中,對(duì)于雙向鏈表中節(jié)點(diǎn)插入的講解示例中,大多數(shù)只展示了指針方向變化的一種順序[1-4]。在雙向鏈表中,每一個(gè)節(jié)點(diǎn)都帶有兩個(gè)指針域和一個(gè)數(shù)據(jù)域[5]。在鏈表中,每插入一個(gè)節(jié)點(diǎn),會(huì)有四個(gè)指針的指向發(fā)生變化,按照一定的操作順序,就能完成節(jié)點(diǎn)的插入工作。
在雙向鏈表中,一個(gè)節(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域、一個(gè)前驅(qū)和一個(gè)后繼,分別用data、prior和next表示?;陔p向鏈表的節(jié)點(diǎn)類型C語言模板如下[1]:
在雙向鏈表插入節(jié)點(diǎn)算法中,在第i個(gè)節(jié)點(diǎn)前(后)插入一個(gè)值為e的新節(jié)點(diǎn)s,第i個(gè)節(jié)點(diǎn)位置的定位可以在鏈表中從左向右方向查找到,也可以從右向左方向查找到。算法中,p為查找到的第i個(gè)節(jié)點(diǎn),將待插入節(jié)點(diǎn)s插入到p節(jié)點(diǎn)之前,同時(shí)要修改s與p節(jié)點(diǎn)的前驅(qū)和后繼域的位置。
在鏈表中插入一個(gè)節(jié)點(diǎn)需要對(duì)各指針域做出修改,在單向鏈表中插入一個(gè)節(jié)點(diǎn)只需要對(duì)p和s兩個(gè)節(jié)點(diǎn)的后繼域的指向分別做出更改,而在雙向鏈表中,需要對(duì)p和s兩個(gè)節(jié)點(diǎn)的前驅(qū)和后繼共四個(gè)指針的指向分別做出更改。四個(gè)指針的變動(dòng),有四步操作語句,雙向鏈表前插入節(jié)點(diǎn)的指針變換步驟的核心C語言代碼如下[5]:
在上述代碼語句中,①②③④分別代表四個(gè)指針的變化。指針改變的具體步驟解析如下。
步驟①:將插入節(jié)點(diǎn)s的前驅(qū)指向插入位置節(jié)點(diǎn)p的前驅(qū),即將指定節(jié)點(diǎn)的前驅(qū)指針作為新節(jié)點(diǎn)的前驅(qū)指針。
步驟②:將p的前驅(qū)的后繼域指向插入節(jié)點(diǎn)s,即調(diào)整新節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的后向指針。
步驟③:將插入節(jié)點(diǎn)s的后繼域指向了p節(jié)點(diǎn),即將指定節(jié)點(diǎn)p作為新節(jié)點(diǎn)的后向指針。
步驟④:將p節(jié)點(diǎn)的前驅(qū)域指向s節(jié)點(diǎn),即將新節(jié)點(diǎn)作為指定節(jié)點(diǎn)的前向指針。
通過測(cè)試,上述代碼的順序不唯一,但也不是任意的。
雙向鏈表中,節(jié)點(diǎn)后插入算法與節(jié)點(diǎn)前插入算法的不同之處是,節(jié)點(diǎn)前插入算法是將新節(jié)點(diǎn)插入指定節(jié)點(diǎn)p與前一節(jié)點(diǎn)之間,而節(jié)點(diǎn)后插入算法是將新節(jié)點(diǎn)插入指定節(jié)點(diǎn)p與后一個(gè)節(jié)點(diǎn)之間,其代碼執(zhí)行語句也有所不同,但是同樣需要對(duì)p和s兩個(gè)節(jié)點(diǎn)的前驅(qū)和后繼共四個(gè)指針的指向分別做出更改。四個(gè)指針的變動(dòng),有四步操作語句,雙向鏈表后插入節(jié)點(diǎn)的指針變換步驟的核心C語言代碼如下:
在上述代碼語句中,①②③④分別代表四個(gè)指針的變化。指針改變的具體步驟解析如下:
步驟①:將插入節(jié)點(diǎn)s的后繼指向插入位置節(jié)點(diǎn)p的后繼,即將指定節(jié)點(diǎn)的后向指針作為新節(jié)點(diǎn)的后向指針;
步驟②:將p的next的prior域指向插入節(jié)點(diǎn)s,即調(diào)整p的next節(jié)點(diǎn)的前驅(qū)指針;
步驟③:將插入節(jié)點(diǎn)s的前驅(qū)域指向p節(jié)點(diǎn),即將指定節(jié)點(diǎn)作為新節(jié)點(diǎn)的前向指針;
步驟④:將p的后繼域指向s節(jié)點(diǎn),即將新節(jié)點(diǎn)作為指定節(jié)點(diǎn)的后向指針。
通過測(cè)試,上述代碼的順序不唯一,但也不是任意的。
由2.2小節(jié)和2.3小節(jié)可知,編號(hào)①②③④分別代表雙向鏈表中插入新節(jié)點(diǎn)的指針變化的四個(gè)操作步驟,雙向鏈表插入節(jié)點(diǎn)的核心步驟的所有排列組合有24種,本節(jié)將對(duì)其分別做實(shí)驗(yàn)測(cè)試,其中,24種排列操作順序如表1所示。
表1 雙向鏈表插入節(jié)點(diǎn)步驟的24種排列順序
無論是節(jié)點(diǎn)前插入算法還是節(jié)點(diǎn)后插入算法,其4個(gè)操作步驟的排列順序都可由表1中的數(shù)據(jù)表示。本節(jié)需要注意的是,順序1分別代表2.2小節(jié)和2.3小節(jié)中出現(xiàn)的節(jié)點(diǎn)插入的順序,本文中也稱此順序?yàn)楣?jié)點(diǎn)插入的標(biāo)準(zhǔn)順序。
在本文中,實(shí)驗(yàn)對(duì)節(jié)點(diǎn)前、后插入算法的24種不同的順序分別進(jìn)行了測(cè)試,測(cè)試結(jié)果如下。
3.2.1 標(biāo)準(zhǔn)順序下的節(jié)點(diǎn)插入操作
對(duì)于表1中的順序1,無論是節(jié)點(diǎn)前插入算法還是節(jié)點(diǎn)后插入算法,均是教材中普遍出現(xiàn)的一種節(jié)點(diǎn)插入操作算法。在2.2小節(jié)和2.3小節(jié)中已給出其具體的C語言模板,其操作邏輯圖如圖1所示。
圖1 順序1節(jié)點(diǎn)插入操作圖
由圖1(a)可知,在元素a與b之間插入元素e,即在p節(jié)點(diǎn)之前插入s節(jié)點(diǎn)。在圖1中,由①②③④四條虛線箭頭和一個(gè)節(jié)點(diǎn)s完全替換a元素與b元素所屬節(jié)點(diǎn)之間的雙向?qū)嵕€箭頭,從而順利完成節(jié)點(diǎn)的前插入操作。由圖1(b)可知,p指向了a元素所屬節(jié)點(diǎn),由于指定的p節(jié)點(diǎn)的位置不同,導(dǎo)致圖1(a)與圖1(b)中的虛線順序有所不同,其目的都是改變指針指向完成節(jié)點(diǎn)的插入。
使用節(jié)點(diǎn)前插入算法構(gòu)建一個(gè)雙向鏈表,其中包含“a”“b”“c”三個(gè)字符元素。假設(shè)在第二個(gè)字符位置前插入元素“k”,插入元素之后,第二個(gè)位置的字符變更為“k”,原第二個(gè)位置及之后位置的字符依次往后順延一位,即原字符順序變?yōu)椤癮kbc”。在實(shí)驗(yàn)中,輸入“abc”三個(gè)字符構(gòu)成雙向鏈表,以“$”符為結(jié)束標(biāo)識(shí)符,然后輸入不同插入位置及插入元素“k”,插入節(jié)點(diǎn)后的鏈表結(jié)果如圖2所示。
圖2中的(a)—(c)分別代表第一、二和三個(gè)位置前插入元素“k”的實(shí)驗(yàn)結(jié)果,插入結(jié)果分別為“kabc”“akbc”“abkc”,由于本實(shí)驗(yàn)是節(jié)點(diǎn)前插入操作,所以無法實(shí)現(xiàn)在尾字符“c”之后插入元素節(jié)點(diǎn)。
使用節(jié)點(diǎn)后插入算法構(gòu)建一個(gè)雙向鏈表,其中包含“a”“b”“c”三個(gè)字符元素。假設(shè)在第二個(gè)字符位置后插入元素“k”,插入元素之后,原第三個(gè)位置的字符變更為“k”,原第三個(gè)位置及之后位置的字符依次往后順延一位,即原字符順序變?yōu)椤癮bkc”。在實(shí)驗(yàn)中,輸入“abc”三個(gè)字符構(gòu)成雙向鏈表,以“$”符為結(jié)束標(biāo)識(shí)符,然后輸入不同插入位置及插入元素“k”,插入節(jié)點(diǎn)后的鏈表結(jié)果如圖3所示。
圖2 節(jié)點(diǎn)前插入結(jié)果實(shí)現(xiàn)圖
圖3 節(jié)點(diǎn)后插入結(jié)果實(shí)現(xiàn)圖
圖3中的(a)—(c)分別代表第一、二和三個(gè)位置后插入元素“k”的實(shí)驗(yàn)結(jié)果,插入后的結(jié)果分別為“akbc”“abkc”“abck”,由于是節(jié)點(diǎn)后插入算法,所以無法實(shí)現(xiàn)在首字符“a”之前插入元素節(jié)點(diǎn)。
3.2.2 其他插入節(jié)點(diǎn)順序
參照標(biāo)準(zhǔn)順序1,在其基礎(chǔ)之上改變指針指向的運(yùn)算順序,在表1中,節(jié)點(diǎn)前插入算法除了順序1,還有順序2、3、7、8、9、10、11、12、13、15和16,共計(jì)12種操作順序可以完成節(jié)點(diǎn)的前插入操作,在節(jié)點(diǎn)后插入算法中除了順序1,還有順序2、3、4、5、6、7、8、9、13、14和15,但這些操作順序在眾多教材中出現(xiàn)的示例并不多。
通過實(shí)驗(yàn)測(cè)試,12種指針變化順序都能很好地完成新節(jié)點(diǎn)的插入操作,與標(biāo)準(zhǔn)順序1插入節(jié)點(diǎn)的效果一致。節(jié)點(diǎn)前插入算法插入節(jié)點(diǎn)結(jié)果實(shí)現(xiàn)圖與圖2完全一致,節(jié)點(diǎn)后插入算法插入節(jié)點(diǎn)結(jié)果實(shí)現(xiàn)圖與圖3完全一致。在本文中,經(jīng)過代碼的實(shí)現(xiàn)和測(cè)試,算法都能夠很好地完成其在雙向鏈表中的節(jié)點(diǎn)前插入操作和后插入操作。
從上述歸納的12種操作順序中可以分析得出,在節(jié)點(diǎn)前插入算法中,語句④必須在語句②之后,在節(jié)點(diǎn)后插入算法中,語句④必須在語句①之后,否則無法完成雙向鏈表中的節(jié)點(diǎn)插入操作。
3.2.3 非法操作順序
對(duì)于節(jié)點(diǎn)前插入算法,若語句④在語句②之前,則程序先執(zhí)行語句④“p->prior=s;”,后執(zhí)行語句②“p->prior->next=s;”。例如操作順序“①④②③”,先執(zhí)行語句“①④”,同時(shí)替換掉鏈L1,即鏈L1斷開。接著執(zhí)行語句②,由于鏈L1已斷開,無法找到“p->prior”節(jié)點(diǎn),即無法找到圖4(a)中a元素所屬節(jié)點(diǎn),將無法完成節(jié)點(diǎn)的插入操作。若想將a元素所屬節(jié)點(diǎn)與s節(jié)點(diǎn)相連接,則執(zhí)行語句“s->prior->next=s;”可以完成,但是這又違背了原代碼語句的描述。
其他節(jié)點(diǎn)前插入算法中,不能插入節(jié)點(diǎn)的操作順序的原理與以上所述一致。
對(duì)于節(jié)點(diǎn)后插入算法,若語句④在語句①之前,則程序先執(zhí)行語句④“p->next=s;”,后執(zhí)行語句①“s->next=p->next;”。例如操作順序“②③④①”,語句④在語句①之前,完成了p的后繼的指向,再執(zhí)行語句①時(shí),s的后繼只能指向自己,無法指向原p節(jié)點(diǎn)的后繼,即圖4(b)中b元素所屬的節(jié)點(diǎn),從而無法完成節(jié)點(diǎn)的插入操作。
其他節(jié)點(diǎn)后插入算法中,不能插入節(jié)點(diǎn)的操作順序的原理與以上所述一致。
圖4 雙向鏈表節(jié)點(diǎn)插入指針替換圖
本文描述了雙向鏈表中前、后插入節(jié)點(diǎn)的過程,其中,插入節(jié)點(diǎn)時(shí)四個(gè)指針的改變有不同的順序。經(jīng)過實(shí)驗(yàn)測(cè)試出,無論是節(jié)點(diǎn)前插入操作還是節(jié)點(diǎn)后插入操作,都有12種不同的操作順序,同時(shí)也有12種不成立的順序。從實(shí)驗(yàn)結(jié)果中分析出,節(jié)點(diǎn)前插入算法中,步驟②必須要在語句④之前,節(jié)點(diǎn)后插入算法中,步驟①必須要在語句④之前,否則指針指向會(huì)發(fā)生錯(cuò)誤,會(huì)丟失存儲(chǔ)的指針,從而導(dǎo)致算法無法完成節(jié)點(diǎn)插入。
在教學(xué)當(dāng)中,可以讓學(xué)生深入學(xué)習(xí)雙向鏈表的節(jié)點(diǎn)類定義,以及鏈表的創(chuàng)建、節(jié)點(diǎn)的插入、刪除等操作。在實(shí)驗(yàn)過程中,測(cè)試雙向鏈表插入節(jié)點(diǎn)的基準(zhǔn)運(yùn)算順序,同時(shí)也測(cè)試不同的運(yùn)算順序,讓學(xué)生對(duì)這一知識(shí)點(diǎn)有更深入的了解和學(xué)習(xí),可以拋出假設(shè)性問題,引起學(xué)生對(duì)這一知識(shí)點(diǎn)的好奇心和探究心理,激發(fā)學(xué)生的創(chuàng)新思維與學(xué)科交叉意識(shí),從而提升學(xué)生的學(xué)習(xí)興趣,并學(xué)以致用,讓學(xué)生在不斷探究的過程中收獲知識(shí),同時(shí)也可以加深其對(duì)知識(shí)點(diǎn)的記憶,從而達(dá)到由量變到質(zhì)變的效果。