【文章內(nèi)容簡介】 5 從左到右及從右到左遍歷一個單鏈表是可能的，其方法是在從左向右遍歷的過程中將連接方向逆轉(zhuǎn)，如右圖所示。在圖中的指針 p 指向當(dāng)前正在訪問的結(jié)點(diǎn)，指針 pr 指向指針 p 所指結(jié)點(diǎn)的左側(cè)的結(jié)點(diǎn)。此時，指針 p 所指結(jié)點(diǎn)左側(cè)的所有結(jié)點(diǎn)的鏈接方向都已逆轉(zhuǎn)。 (1) 編寫一個算法，從任一給定的位置 (pr, p)開始，將指針 p 右移 k 個結(jié)點(diǎn)。如果 p 移出鏈表，則將 p 置為 0，并讓 pr 停留在鏈表最右邊的結(jié)點(diǎn)上。 (2) 編寫一個算法，從任一給定的位置 (pr, p)開始，將指針 p 左移 k 個結(jié)點(diǎn)。如果 p 移出鏈表，則將 p 置為 0，并讓 pr 停留在鏈表最左邊的結(jié)點(diǎn)上。 第 3 章 鏈表 16 【解答】 (1) 指針 p 右移 k 個結(jié)點(diǎn) templateclass Type void ListType :: siftToRight ( ListNodeType *amp。 p, ListNodeType *amp。 pr, int k ) { if ( p == NULL amp。amp。 pr != first ) { //已經(jīng)在鏈的最右端 cout 已經(jīng)在鏈的最右端，不能再右移。 endl。 return。 } int i。 ListNodeType *q。 if ( p == NULL ) //從鏈頭開始 { i = 1。 pr = NULL。 p = first。 } //重置 p 到鏈頭也算一次右移 else i = 0。 while ( p != NULL amp。amp。 i k ) { //右移 k 個結(jié)點(diǎn) q = plink。 plink = pr。 //鏈指針 p→ link 逆轉(zhuǎn)指向 pr pr = p。 p = q。 i++。 //指針 pr, p 右移 } cout 右移了 i 個結(jié)點(diǎn)。 endl。 } (2) 指針 p 左移 k 個結(jié)點(diǎn) templateclass Type void ListType :: siftToLeft ( ListNodeType *amp。 p, ListNodeType *amp。 pr, int k ) { if ( p == NULL amp。amp。 pr == first ) { //已經(jīng)在鏈的最左端 cout 已經(jīng)在鏈的最左端，不能再左移。 endl。 return。 } int i = 0。 ListNodeType *q。 while ( pr != NULL amp。amp。 i k ) { //左移 k 個結(jié)點(diǎn) q = prlink。 prlink = p。 //鏈指針 prlink 逆轉(zhuǎn)指向 p p = pr。 pr = q。 i++。 //指針 pr, p 左移 } cout 左移了 i 個結(jié)點(diǎn)。 endl。 if ( i k ) { pr = p。 p = NULL。 } //指針 p 移出表外，重置 p, pr } 36 試寫出用單鏈表表示的字符串類及字符串結(jié)點(diǎn)類的定義，并依次實現(xiàn)它的構(gòu)造函數(shù)、以及計算串長度、串賦值、判斷兩串相等、求子串、兩串連接、求子串在串中位置等 7 個成員函數(shù)。要求每個字符串結(jié)點(diǎn)中只存放一個字符。 【解答】 //用單鏈表表示的字符串類 string1 的頭文件 include const int maxLen = 300。 //字符串最大長度為 300（理論上可以無限長） class string1 { public: string1 ( )。 //構(gòu)造空字符串 第 3 章 鏈表 17 string1 ( char * obstr )。 //從字符數(shù)組建立字符串 ~string1 ( )。 //析構(gòu)函數(shù) int Length ( ) const { return curLen。 } //求字符串長度 string1amp。 operator = ( string1amp。 ob )。 //串賦值 int operator == ( string1amp。 ob )。 //判兩串相等 charamp。 operator [ ] ( int i )。 //取串中字符 string1amp。 operator ( ) ( int pos, int len )。 //取子串 string1amp。 operator += ( string1amp。 ob )。 //串連接 int Find ( string1amp。 ob )。 //求子串在串中位置 (模式匹配 ) friend ostreamamp。 operator ( ostreamamp。 os, string1amp。 ob )。 friend istreamamp。 operator ( istreamamp。 is, string1amp。 ob )。 private: ListNodechar*chList。 //用單鏈表存儲的字符串 int curLen。 //當(dāng)前字符串長度 } //單鏈表表示的字符串類 string1 成員函數(shù)的實現(xiàn)，在文件 中 include include string1 :: string1( ) { //構(gòu)造函數(shù) chList = new ListNodechar ( 39。\039。 )。 curLen = 0。 } string1 :: string1( char *obstr ) { //復(fù)制構(gòu)造函數(shù) curLen = 0。 ListNodechar *p = chList = new ListNodechar ( *obstr )。 while ( *obstr != 39。\039。 ) { obstr++。 p = plink = new ListNodechar ( *obstr )。 curLen++。 } } string1amp。 string1 :: operator = ( string1amp。 ob ) { //串賦值 ListNodechar *p = 。 ListNodechar *q = chList = new ListNodechar ( pdata )。 curLen = 。 while ( pdata != 39。\039。 ) { p = plink。 q = qlink = new ListNodechar ( pdata )。 } return *this。 } 第 3 章 鏈表 18 int string1 :: operator == ( string1amp。 ob ) { //判兩串相等 if ( curLen != ) return 0。 ListNode char *p = chList, *q = 。 for ( int i = 0。 i curLen。 i++ ) if ( pdata != qdata ) return 0。 else { p = plink。 q = qlink。 } return 1。 } charamp。 string1 :: operator [ ] ( int i ) { //取串中字符 if ( i = 0 amp。amp。 i curLen ) { ListNode char *p = chList。 int k = 0。 while ( p != NULL amp。amp。 k i ) { p = plink。 k++。 } if ( p != NULL ) return pdata。 } return 39。\039。 } string1amp。 string1 :: operator ( ) ( int pos, int len ) { //取子串 string1 temp。 if ( pos = 0 amp。amp。 len = 0 amp。amp。 pos curLen amp。amp。 pos + len 1 curLen ) { ListNodechar *q, *p = chList。 for ( int k = 0。 k pos。 k++。 ) p = plink。 //定位于第 pos 結(jié)點(diǎn) q = = new ListNodechar ( pdata )。 for ( int i = 1。 i len。 i++ ) { //取長度為 len 的子串 p = plink。 q = qlink = new ListNodechar ( pdata )。 } qlink = new ListNodechar ( 39。\039。 )。 //建立串結(jié)束符 = len。 } else { = 0。 = new ListNodechar ( 39。\039。 )。 } return *temp。 } string1amp。 string1 :: operator += ( string1amp。 ob ) { //串連接 if ( curLen + maxLen ) len = maxLen curLen。 else len = 。 //傳送字符數(shù)