第三章用户接口与作业管理习题(编辑修改稿)

第三章用户接口与作业管理习题(编辑修改稿)内容摘要：

5 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如右图所示。 在图中的指针 p 指向当前正在访问的结点，指针 pr 指向指针 p 所指结点的左侧的结点。 此时，指针 p 所指结点左侧的所有结点的链接方向都已逆转。 (1) 编写一个算法，从任一给定的位置 (pr, p)开始，将指针 p 右移 k 个结点。 如果 p 移出链表，则将 p 置为 0，并让 pr 停留在链表最右边的结点上。 (2) 编写一个算法，从任一给定的位置 (pr, p)开始，将指针 p 左移 k 个结点。 如果 p 移出链表，则将 p 置为 0，并让 pr 停留在链表最左边的结点上。 第 3 章 链表 16 【解答】 (1) 指针 p 右移 k 个结点 templateclass Type void ListType :: siftToRight ( ListNodeType *amp。 p, ListNodeType *amp。 pr, int k ) { if ( p == NULL amp。 amp。 pr != first ) { //已经在链的最右端 cout 已经在链的最右端，不能再右移。 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 个结点 q = plink。 plink = pr。 //链指针 p→ link 逆转指向 pr pr = p。 p = q。 i++。 //指针 pr, p 右移 } cout 右移了 i 个结点。 endl。 } (2) 指针 p 左移 k 个结点 templateclass Type void ListType :: siftToLeft ( ListNodeType *amp。 p, ListNodeType *amp。 pr, int k ) { if ( p == NULL amp。 amp。 pr == first ) { //已经在链的最左端 cout 已经在链的最左端，不能再左移。 endl。 return。 } int i = 0。 ListNodeType *q。 while ( pr != NULL amp。 amp。 i k ) { //左移 k 个结点 q = prlink。 prlink = p。 //链指针 prlink 逆转指向 p p = pr。 pr = q。 i++。 //指针 pr, p 左移 } cout 左移了 i 个结点。 endl。 if ( i k ) { pr = p。 p = NULL。 } //指针 p 移出表外，重置 p, pr } 36 试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等 7 个成员函数。 要求每个字符串结点中只存放一个字符。 【解答】 //用单链表表示的字符串类 string1 的头文件 include const int maxLen = 300。 //字符串最大长度为 300（理论上可以无限长） class string1 { public: string1 ( )。 //构造空字符串 第 3 章 链表 17 string1 ( char * obstr )。 //从字符数组建立字符串 ~string1 ( )。 //析构函数 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。 //当前字符串长度 } //单链表表示的字符串类 string1 成员函数的实现，在文件 中 include include string1 :: string1( ) { //构造函数 chList = new ListNodechar ( 39。 \039。 )。 curLen = 0。 } string1 :: string1( char *obstr ) { //复制构造函数 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 结点 q = = new ListNodechar ( pdata )。 for ( int i = 1。 i len。 i++ ) { //取长度为 len 的子串 p = plink。 q = qlink = new ListNodechar ( pdata )。 } qlink = new ListNodechar ( 39。 \039。 )。 //建立串结束符 = len。 } else { = 0。 = new ListNodechar ( 39。 \039。 )。 } return *temp。 } string1amp。 string1 :: operator += ( string1amp。 ob ) { //串连接 if ( curLen + maxLen ) len = maxLen curLen。 else len =。 //传送字符数。