清华大学：《数据结构及其应用》课程教学资源（试卷习题）试题4

3-2试编写一个算法,在带表头结点的单链表中寻找第i个结点。若找到,则函数返回第i个结点的 地址;若找不到,则函数返回0 【解答】 template LisiNode * List : GetANode( int i)i ∥取得单链表中第i个结点地址,i从0开始计数,i*p=first; int k=0; while(p I=NULL &&k template class List; template class Lisinode friend class LisKType> ListNode (i ListNode( const Type& item ) ∥构造函数 private Type data; template class List i List( const Type finishied ) ∥建立链表 void Browse ( ∥打印链表 void Merge( Lis/&hb ) ∥连接链表 rivate ListNode LisiNode: LisiNode ( link( NULl)& ∥构造函数,仅初始化指针成员 template ListNodesType>: ListNode( const Type item ): data( item ), link( NULL)

3-2 试编写一个算法，在带表头结点的单链表中寻找第 i 个结点。若找到，则函数返回第 i 个结点的 地址；若找不到，则函数返回 0。 【解答】 template ListNode * List :: GetANode ( int i ) { //取得单链表中第 i 个结点地址, i 从 0 开始计数, i * p = first; int k = 0; while ( p != NULL && k template class List; template class ListNode { friend class List; public: ListNode ( ); //构造函数 ListNode ( const Type& item ); //构造函数 private: Type data; ListNode *link; }; template class List { public: List ( const Type finishied ); //建立链表 void Browse ( ); //打印链表 void Merge ( List &hb ); //连接链表 private: ListNode *first, *last; }; //各成员函数的实现 template ListNode::ListNode ( ) : link ( NULL ) { } //构造函数, 仅初始化指针成员。 template ListNode :: ListNode ( const Type & item ) : data ( item ), link ( NULL ) { }

∥构造函数,初始化数据与指针成员 template LiskType>: List( const Type finishied ∥创建一个带表头结点的单链表, finished是停止建表输入的标志, ∥是所有输入值中不可能出现的数值 first last =new LisiNode( )i 建表头结点 Type walue; ListNode*p,*g,*s while walue I=finished)i 环建立各个结点 s= new LisINode( ralue )i q=frst;p=frst→link; while(Pl=NULL&&p→da ∥寻找新结点插入位置 q→lik=s;s→lnk=p 在q,P间插入新结点 if(p==nUll)last=s cin >> value: template void LisKType>:: Browse (i ∥浏览并输出链表的内容 cout void List : Merge( LisK& hb) ∥将当前链表this与链表hb按逆序合并,结果放在当前链表this中。 ListNode 'pa, 'pb,'g, pa=first-link; pb =hb. fin ∥检测指针跳过表头结点 ∥结果链表初始化 while (pa I= NULL & pb I= NULL)i 当两链表都未结束时 {q=pa;p=p→lnk;} ∥从p链中摘下 从pb链中摘下 q→lik= first→link; first→link=q; ∥链入结果链的链头 }

//构造函数, 初始化数据与指针成员。 template List :: List ( const Type finishied ) { //创建一个带表头结点的单链表，finished 是停止建表输入的标志， //是所有输入值中不可能出现的数值。 first = last = new ListNode( ); //创建表头结点 Type value; ListNode *p, *q, *s; cin >> value; while ( value != finished ) { //循环建立各个结点 s = new ListNode( value ); q = first; p = first→link; while ( p != NULL && p→data > value; } } template void List :: Browse ( ) { //浏览并输出链表的内容 cout *p = first→link; while ( p != NULL ) { cout void List :: Merge ( List& hb) { //将当前链表 this 与链表 hb 按逆序合并，结果放在当前链表 this 中。 ListNode *pa, *pb, *q, *p; pa = first→link; pb = hb.first→link; //检测指针跳过表头结点 first→link = NULL; //结果链表初始化 while ( pa != NULL && pb != NULL ) { //当两链表都未结束时 if ( pa→data <= pb→data ) { q = pa; pa = pa→link; } //从 pa 链中摘下 else { q = pb; pb = pb→link; } //从 pb 链中摘下 q→link = first→link; first→link = q; //链入结果链的链头 }

p=(pa I= NULL ) pa: pb; 处理未完链的剩余部分 while(p I= NULL )i q→link=irst→link;mrst→link=q; 3-6设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有结点的链 接方向逆转,如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。 h 【解答1】 template void Lisk: Immerse ()i if(first== NULL)return; Listooder·p=fst→lik;,spr=NULL; ile(p I= NULL)i 逆转st指针 =p;p=p→link 指针前移 【解答2】 template void Lis: Inverse()i ListNode ' p, head new ListNode(; while (first I= NULL)& p=first; first =first-link 摘下fst链头结点 p→link=head→link;head→lnk=p;/插入head链前端 first head-link; delete head ∥重置fst 3-7从左到右及从右到左遍历一个单链表是可能的,其方法是在从左向右遍历的过程中将连接方向逆 转,如右图所示。在图中的指针p指向当前正在访问的结点,指针p指向指针p所指结点的左侧的结 点。此时,指针p所指结点左侧的所有结点的链接方向都已逆转 (1)编写一个算法,从任一给定的位置(pr,p)开始,将指针p右移k个结点。如果p移出链表,则 将p置为0,并让p停留在链表最右边的结点上。 (2)编写一个算法,从任一给定的位置(p,p)开始,将指针p左移k个结点。如果p移出链表,则 将p置为0,并让pr停留在链表最左边的结点上 【解答】 (1)指针p右移k个结点

p = ( pa != NULL ) ? pa : pb; //处理未完链的剩余部分 while ( p != NULL ) { q = p; p = p→link; q→link = first→link; first→link = q; } } 3-6 设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链 接方向逆转，如下图所示。要求逆转结果链表的表头指针 h 指向原链表的最后一个结点。 【解答 1】 template void List :: Inverse ( ) { if ( first == NULL ) return; ListNode *p = first→link;, *pr = NULL; while ( p != NULL ) { first→link = pr; //逆转 first 指针 pr = first; first = p; p = p→link; //指针前移 } } 【解答 2】 template void List :: Inverse ( ) { ListNode *p, *head = new ListNode ( ); while ( first != NULL ) { p = first; first = first→link; //摘下 first 链头结点 p→link = head→link; head→link = p; //插入 head 链前端 } first = head→link; delete head; //重置 first } 3-7 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆 转，如右图所示。在图中的指针 p 指向当前正在访问的结点，指针 pr 指向指针 p 所指结点的左侧的结 点。此时，指针 p 所指结点左侧的所有结点的链接方向都已逆转。 (1) 编写一个算法，从任一给定的位置(pr, p)开始，将指针 p 右移 k 个结点。如果 p 移出链表，则 将 p 置为 0，并让 pr 停留在链表最右边的结点上。 (2) 编写一个算法，从任一给定的位置(pr, p)开始，将指针 p 左移 k 个结点。如果 p 移出链表，则 将 p 置为 0，并让 pr 停留在链表最左边的结点上。 【解答】 (1) 指针 p 右移 k 个结点

template void Lisk sifiToRight( ListNode*& p, ListNode * pr, int k)( f(p== null & pr I=first)i ∥已经在链的最右端 cout*q if(P== NULL ∥从链头开始 p=firs; 3 ∥重置p到链头也算一次右移 hile(p l=NULL &&i void Lisk sifiToLefi( ListNode*& p, LisnNode*& pr, int k)& if (p== NULL & pr==first )t ∥已经在链的最左端 cout*q; while (pr l=NULL &&i<k)i ∥左移k个结点 q=pr→lnk;pr→link=p; ∥链指针p→lmk逆转指向p 指针 左移 cout<<"左移了”<<i<<"个结点。”<<endl; if (i<k)ipr=p; P=NULL; 3 ∥指针p移出表外,重置p,P 3-9试写出用单链表表示的字符串类及字符串结点类的定义,并依次实现它的构造函数、以及计算串 长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。要求每个字 符串结点中只存放一个字符 【解答】 ∥用单链表表示的字符串类smg1的头文件 stringl. h const int maxLen = 300: ∥字符串最大长度为300(理论上可以无限长) class stringl i stringl ( ∥构造空字符串 ringl( char *obstr ) ∥从字符数组建立字符串 stringl ( ∥析构函数

template void List :: siftToRight ( ListNode *& p, ListNode *& pr, int k ) { if ( p == NULL && pr != first ) { //已经在链的最右端 cout *q; if ( p == NULL ) //从链头开始 { i = 1; pr = NULL; p = first; } //重置 p 到链头也算一次右移 else i = 0; while ( p != NULL && i void List :: siftToLeft ( ListNode *& p, ListNode *& pr, int k ) { if ( p == NULL && pr == first ) { //已经在链的最左端 cout *q; while ( pr != NULL && i const int maxLen = 300; //字符串最大长度为 300（理论上可以无限长） class string1 { public: string1 ( ); //构造空字符串 string1 ( char * obstr ); //从字符数组建立字符串 ~string1 ( ); //析构函数

int Length() const{ return curLen;}∥求字符串长度 ∥串赋值 int operator ==( string I& ob ) ∥判两串相等 char& operator [ int i); 取串中字符 取子串 stringl& operator += string l& ob ) int Find( string l& ob ); ∥求子串在串中位置(模式匹配) friend ostream& operator > istream& is, string l& ob )i ListNodeschar>schist: ∥用单链表存储的字符串 int curLen; ∥当前字符串长度 ∥单链表表示的字符串类 string l成员函数的实现,在文件 string1.cpp中 #include lh" string l∷; string l(){ ∥构造函数 chlist=new ListNodeschar>(0); stringl : stringl( char * obstr )i 复制构造函数 Len =0 ListNodeschar *p= chlist new ListNodechar>(*obstr ) while(*obstr I=0)i obstr++ p=p-link new ListNode(*obstr )i curLen++; string I& stringl : operator = stringl& ob)i 串赋值 ListNodeschar> *a= chlist new ListNodeschar(p-data ) while(p→ data=vo){ q=q→lnk= new ListNode(p→da); return *this int stringl operator == string l& ob)i 判两串相等

int Length ( ) const { return curLen; }//求字符串长度 string1& operator = ( string1& ob ); //串赋值 int operator == ( string1& ob ); //判两串相等 char& operator [ ] ( int i ); //取串中字符 string1& operator ( ) ( int pos, int len ); //取子串 string1& operator += ( string1& ob ); //串连接 int Find ( string1& ob ); //求子串在串中位置(模式匹配) friend ostream& operator > ( istream& is, string1& ob ); private: ListNode*chList; //用单链表存储的字符串 int curLen; //当前字符串长度 } //单链表表示的字符串类 string1 成员函数的实现，在文件 string1.cpp 中 #include #include "string1.h" string1 :: string1( ) { //构造函数 chList = new ListNode ( '\0' ); curLen = 0; } string1 :: string1( char *obstr ) { //复制构造函数 curLen = 0; ListNode *p = chList = new ListNode ( *obstr ); while ( *obstr != '\0' ) { obstr++; p = p→link = new ListNode ( *obstr ); curLen++; } } string1& string1 :: operator = ( string1& ob ) { //串赋值 ListNode *p = ob.chList; ListNode *q = chList = new ListNode ( p→data ); curLen = ob.curLen; while ( p→data != '\0' ) { p = p→link; q = q→link = new ListNode ( p→data ); } return *this; } int string1 :: operator == ( string1& ob ) { //判两串相等

if curLen I= ob curLen)return 0; ListNode "p=chList, g=ob.chlist; for( int i=0; i=0&& len >=0 & pos curLen & pos len -1 *4, "p=chList; for(intk=0;k (p-data ) len;汁+){ ∥取长度为len的子串 g-g q-link new ListNode(10); ∥建立串结束符 chlist new ListNodeschar (10);3 stringl& string l: operator+=( stringl&ab){∥串连接 ∥传送字符数 for(intk=0;k< curLen-1;k++;)p=p→lnk; Hthis串的串尾 for(k=0; k<len; k++)i ∥连接 new lis

if ( curLen != ob.curLen ) return 0; ListNode *p = chList, *q = ob.chList; for ( int i = 0; i = 0 && i *p = chList; int k = 0; while ( p != NULL && k = 0 && len >= 0 && pos *q, *p = chList; for ( int k = 0; k ( p→data ); for ( int i = 1; i ( p→data ); } q→link = new ListNode ( '\0' ); //建立串结束符 temp.curLen = len; } else { temp.curLen = 0; temp.chList = new ListNode ( '\0' ); } return *temp; } string1& string1 :: operator += ( string1& ob ) { //串连接 if ( curLen + ob.curLen > maxLen ) len = maxLen - curLen; else len = ob.curLen; //传送字符数 ListNode *q = ob.chList, *p = chList; for ( int k = 0; k ( q→data ); q = q→link; }

p-link new ListNodeschar>(w0; int stringl : Find( string l& ob)i /求子串在串中位置(模式匹配) int slen curLen, olen =obcurLen, i=slen -oblen: if( temp i, oblen )==ob) break; else i--: return 1: 3-12试设计一个实现下述要求的 Locate运算的函数。设有一个带表头结点的双向链表L,每个结点 有4个数据成员:指向前驱结点的指针pror、指向后继结点的指针next、存放数据的成员daa和访 问频度∫req。所有结点的freg初始时都为0。每当在链表上进行一次 Locate(L,x)操作时,令元素值为 x的结点的访问频度∫req加1,并将该结点前移,链接到与它的访问频度相等的结点后面,使得链表 中所有结点保持按访问频度递减的顺序排列,以使频繁访问的结点总是靠近表头。 【解答】 #include ∥双向循环链表结点的构造函数 DbINode(Type value, Db/Node "left, Db/Node *right DbINode (type value ) data( ralue ) freq (0), ILink( NULL), rLink( NULL)( DblLisk: DblList( Type unique val) le( unique val); ∥创建表头结点 cout value 每次新结点插入在表头结点后面 first-rLink =new Db/Node( value, first, first-rLink ) template if( p I=first)i ∥链表中存在x

p→link = new ListNode ( '\0' ); } int string1 :: Find ( string1& ob ) { //求子串在串中位置(模式匹配) int slen = curLen, oblen = ob.curLen, i = slen - oblen; string1 temp = this; while ( i > -1 ) if ( temp( i, oblen ) == ob ) break; else i-- ; return i; } 3-12 试设计一个实现下述要求的 Locate 运算的函数。设有一个带表头结点的双向链表 L，每个结点 有 4 个数据成员：指向前驱结点的指针 prior、指向后继结点的指针 next、存放数据的成员 data 和访 问频度 freq。所有结点的 freq 初始时都为 0。每当在链表上进行一次 Locate (L, x)操作时，令元素值为 x 的结点的访问频度 freq 加 1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表 中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。 【解答】 #include //双向循环链表结点的构造函数 DblNode (Type value, DblNode *left, DblNode *right ) : data ( value ), freq ( 0 ), lLink ( left ), rLink ( right ) { } DblNode (Type value ) : data ( value ), freq ( 0 ), lLink ( NULL ), rLink ( NULL ) { } template DblList :: DblList ( Type uniqueVal ) { first = new DblNode( uniqueVal ); first→rLink = first→lLink = first; //创建表头结点 current = NULL; cout > value; while ( value != uniqueVal ) { //每次新结点插入在表头结点后面 first→rLink = new DblNode( value, first, first→rLink ); cin >> value; } } template void DblList :: Locate ( Type & x ) { //定位 DblNode *p = first→rLink; while ( p != first && p→data != x ) p = p→rLink; if ( p != first ) { //链表中存在 x

∥该结点的访问频度加1 current -p: ∥从链表中摘下这个结点 current→lik→ rLink= current-rlink; ∥寻找从新插入的位置 while(p I=first & current-freq>p-freq current→·rLmk=p→ rlink; 插入在p之后 } ot find!\n" /段没找到

p→freq++; //该结点的访问频度加 1 current = p; //从链表中摘下这个结点 current→lLink→rLink = current→rLink; current→rLink→lLink = current→lLink; p = current→lLink; //寻找从新插入的位置 while ( p != first && current→freq > p→freq ) p = p→lLink; current→rLink = p→rLink; //插入在 p 之后 current→lLink = p; p→rLink→lLink = current; p→rLink = current; } else cout<<"Sorry. Not find!\n"; //没找到 }