第3章链表 【解答】 (1)指针p右移k个结点 template<class Type> void List<Type> iftToRight( ListNode<Type> *& p, ListNode<Type> * pr, int k)i if(p= nUll & pr I= first)i ∥经在链的最右端 cout<<"已经在链的最右端,不能再右移。"<<endl; int 1; ListNode<Type>*q: if(p== NULL ∥从链头开始 fi=l: pr= NULL; p=first;) 重置p到链头也算一次右移 else i=0 while( p I= nUlL &&i<k)i ∥右移k个结点 q=p->link; p->link =pr 链指针p→link逆转指向pr ∥指针pr,p右移 } cout<<"右移了”<<i<<"个结点。"<<endl; (2)指针p左移k个结点 template<class Type> void List<Type siftToLeft( ListNode<Type> * p, ListNode<Type> * pr, int k)( if(p== nUll & pr== first ∥已经在链的最左端 cout<<"已经在链的最左端,不能再左移。"<<endl; return; while( pr I= NULL &&i<k)i ∥移k个结点 q=pr->ink; pr->link =p: 链指针pr->link逆转指向p p=pr; pr=q: H++; ∥指针pr,p左移 cout<<"左移了”<<i<<"个结点。"<<endl; if(i<k)( pr=p: p=NULL; J 指针p移出表外,重置p,pr 3-6试写出用单链表表示的字符串类及字符串结点类的定义,并依次实现它的构造函数、以及计算串 长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。要求每个字 符串结点中只存放一个字符 【解答】 ∥用单链表表示的字符串类 stringl的头文件 stringl. h #include <iostream. h>第 3 章 链表 27 【解答】 (1) 指针 p 右移 k 个结点 template<class Type> void List<Type> :: siftToRight ( ListNode<Type> *& p, ListNode<Type> *& pr, int k ) { if ( p == NULL && pr != first ) { //已经在链的最右端 cout << "已经在链的最右端，不能再右移。" << endl; return; } int i; ListNode<Type> *q; if ( p == NULL ) //从链头开始 { i = 1; pr = NULL; p = first; } //重置 p 到链头也算一次右移 else i = 0; while ( p != NULL && i < k ) { //右移 k 个结点 q = p->link; p->link = pr; //链指针 p→link 逆转指向 pr pr = p; p = q; i++; //指针 pr, p 右移 } cout << "右移了" << i << "个结点。" << endl; } (2) 指针 p 左移 k 个结点 template<class Type> void List<Type> :: siftToLeft ( ListNode<Type> *& p, ListNode<Type> *& pr, int k ) { if ( p == NULL && pr == first ) { //已经在链的最左端 cout << "已经在链的最左端，不能再左移。" << endl; return; } int i = 0; ListNode<Type> *q; while ( pr != NULL && i < k ) { //左移 k 个结点 q = pr->link; pr->link = p; //链指针 pr->link 逆转指向 p p = pr; pr = q; i++; //指针 pr, p 左移 } cout << "左移了" << i << "个结点。" << endl; if ( i < k ) { pr = p; p = NULL; } //指针 p 移出表外，重置 p, pr } 3-6 试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串 长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等 7 个成员函数。要求每个字 符串结点中只存放一个字符。 【解答】 //用单链表表示的字符串类 string1 的头文件 string1.h #include <iostream.h>