数据结构练习题解答(三)第三章链表

数据结构练习题解答（三）第三章链表3-2试编写一个算法，在带表头结点的单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回0。【解答】template<classType>ListNode<Type>*List<Type>::GetANode(inti){//取得单链表中第i个结点地址,i从0开始计数,i<0时返回指针0,i=0时返回表头结点地址。if(i<1)returnNULL;ListNode<Type>*p=first;intk=0;while(p!=NULL&&k<i){p=p→link;k++;}returnp;}3-3设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。【解答】#include<iostream.h>template<classType>classList;template<classType>classListNode{friendclassList<Type>;public:ListNode();//构造函数ListNode(constType&item);//构造函数private:Typedata;ListNode<Type>*link;};template<classType>classList{public:List(constTypefinishied);//建立链表voidBrowse();//打印链表voidMerge(List<Type>&hb);//连接链表private:ListNode<Type>*first,*last;};//各成员函数的实现template<classType>ListNode<Type>::ListNode():link(NULL){}//构造函数,仅初始化指针成员。template<classType>ListNode<Type>::ListNode(constType&item):data(item),link(NULL){}//构造函数,初始化数据与指针成员。template<classType>List<Type>::List(constTypefinishied){//创建一个带表头结点的单链表，finished是停止建表输入的标志，//是所有输入值中不可能出现的数值。first=last=newListNode<Type>();//创建表头结点Typevalue;ListNode<Type>*p,*q,*s;cin>>value;while(value!=finished){//循环建立各个结点s=newListNode<Type>(value);q=first;p=first→link;while(p!=NULL&&p→data<=value){q=p;p=p→link;}//寻找新结点插入位置q→link=s;s→link=p;//在q,p间插入新结点if(p==NULL)last=s;cin>>value;}}template<classType>voidList<Type>::Browse(){//浏览并输出链表的内容cout<<"\nTheListis:\n";ListNode<Type>*p=first→link;while(p!=NULL){cout<<p→data;if(p!=last)cout<<"→";elsecout<<endl;p=p→link;}}template<classType>voidList<Type>::Merge(List<Type>&hb){//将当前链表this与链表hb按逆序合并，结果放在当前链表this中。ListNode<Type>*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!=NULL)?pa:pb;//处理未完链的剩余部分while(p!=NULL){q=p;p=p→link;q→link=first→link;first→link=q;}}3-6设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。【解答1】template<classType>voidList<Type>::Inverse(){if(first==NULL)return;ListNode<Type>*p=first→link;,*pr=NULL;while(p!=NULL){first→link=pr;//逆转first指针pr=first;first=p;p=p→link;//指针前移}}【解答2】template<classType>voidList<Type>::Inverse(){ListNode<Type>*p,*head=newListNode<Type>();while(first!=NULL){p=first;first=first→link;//摘下first链头结点p→link=head→link;head→link=p;//插入head链前端}first=head→link;deletehead;//重置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<classType>voidList<Type>::siftToRight(ListNode<Type>*&p,ListNode<Type>*&pr,intk){if(p==NULL&&pr!=first){//已经在链的最右端cout<<"已经在链的最右端，不能再右移。"<<endl;return;}inti;ListNode<Type>*q;if(p==NULL)//从链头开始{i=1;pr=NULL;p=first;}//重置p到链头也算一次右移elsei=0;while(p!=NULL&&i<k){//右移k个结点q=p→link;p→link=pr;//链指针p→link逆转指向prpr=p;p=q;i++;//指针pr,p右移}cout<<"右移了"<<i<<"个结点。"<<endl;}(2)指针p左移k个结点template<classType>voidList<Type>::siftToLeft(ListNode<Type>*&p,ListNode<Type>*&pr,intk){if(p==NULL&&pr==first){//已经在链的最左端cout<<"已经在链的最左端，不能再左移。"<<endl;return;}inti=0;ListNode<Type>*q;while(pr!=NULL&&i<k){//左移k个结点q=pr→link;pr→link=p;//链指针pr→link逆转指向pp=pr;pr=q;i++;//指针pr,p左移}cout<<"左移了"<<i<<"个结点。"<<endl;if(i<k){pr=p;p=NULL;}//指针p移出表外，重置p,pr}3-9试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。要求每个字符串结点中只存放一个字符。【解答】//用单链表表示的字符串类string1的头文件string1.h#include<iostream.h>constintmaxLen=300;//字符串最大长度为300（理论上可以无限长）classstring1{public:string1();//构造空字符串string1(char*obstr);//从字符数组建立字符串~string1();//析构函数intLength()const{returncurLen;}//求字符串长度string1&operator=(string1&ob);//串赋值intoperator==(string1&ob);//判两串相等char&operator[](inti);//取串中字符string1&operator()(intpos,intlen);//取子串string1&operator+=(string1&ob);//串连接intFind(string1&ob);//求子串在串中位置(模式匹配)friendostream&operator<<(ostream&os,string1&ob);friendistream&operator>>(istream&is,string1&ob);private:ListNode<char>*chList;//用单链表存储的字符串intcurLen;//当前字符串长度}//单链表表示的字符串类string1成员函数的实现，在文件string1.cpp中#include<iostream.h>#include"string1.h"string1::string1(){//构造函数chList=newListNode<char>('\0');curLen=0;}string1::string1(char*obstr){//复制构造函数curLen=0;ListNod