第3章链表 第3章链表 单链表的结点类( List Node class)和链表类( ist class的类定义 前视的类定义 template class ListNode i ∥链表结点类的定义 friend class List: List类作为友元类定义 Type data; ListNode *link ∥链指针域 public: ListNode(): link(NULL)0 ∥仅初始化指针成员的构造函数 ListNode const Type& item ) data(item), link (NULL)& ∥初始化数据与指针成员的构造函数 ListNode .getNode const Type& item, ListNode *next= NULL 以tem和next建立一个新结点 ListNode* getLink O{ return link;}∥得结点的下一结点地址 Type getData(i return data; 3 取得结点中的数据 void setLink( ListNode *next)i link =next; 3 ∥修改结点的link指针 void setData( Type value)( data= value; ∥修改结点的data值 template class List i ∥单链表类定义 private: ListNode 'first,*curren ∥链表的表头指针和当前元素指针 public: List( const Type& value)( first=current new ListNode( value );3 ∥构造函数 -List () MakeEmpty () delete first;) ∥析构函数 Make Empty ( ∥将链表置为空表 int Length()const; ∥计算链表的长度 ListNode *Find( Type value ) ∥搜索含数据 value的元素并成为当前元素 ListNode *Locate( int 1); ∥搜索第i个元素的地址并置为当前元素 Type* GetData (; /取出表中当前元素的值 int Insert( Type value ) ∥将vaue插在表当前位置之后并成为当前元素 ∥将链表中的当前元素删去,填补者为当前元素 ListNodetype>* Firster (i current first; return first; ∥当前指针定位于表头结点 Type*First ( ∥当前指针定位于表中第一个元素并返回其值 Type"Next ( 将当前指针进到表中下一个元素并返回其值 int notnull(){ return current=NUL;}表中当前元素空否?空返回1,不空返回0 int NextNotNull (i return current I= NULL & current->link I= NULL; ∥当前元素下一元素空否?空返回1,不空返回0 };
第 3 章 链表 21 第 3 章 链表 单链表的结点类(ListNode class)和链表类(List class)的类定义。 template class List; //前视的类定义 template class ListNode { //链表结点类的定义 friend class List; //List 类作为友元类定义 private: Type data; //数据域 ListNode *link; //链指针域 public: ListNode ( ) : link (NULL) { } //仅初始化指针成员的构造函数 ListNode ( const Type& item ) : data (item), link (NULL) { } //初始化数据与指针成员的构造函数 ListNode * getNode ( const Type& item, ListNode *next = NULL ) //以 item 和 next 建立一个新结点 ListNode * getLink ( ) { return link; } //取得结点的下一结点地址 Type getData ( ) { return data; } //取得结点中的数据 void setLink ( ListNode * next ) { link = next; } //修改结点的 link 指针 void setData ( Type value ) { data = value; } //修改结点的 data 值 }; template class List { //单链表类定义 private: ListNode *first, *current; //链表的表头指针和当前元素指针 public: List ( const Type& value ) { first = current = new ListNode ( value ); } //构造函数 ~List ( ) { MakeEmpty ( ); delete first; } //析构函数 void MakeEmpty ( ); //将链表置为空表 int Length ( ) const; //计算链表的长度 ListNode * Find ( Type value ); //搜索含数据 value 的元素并成为当前元素 ListNode * Locate( int i ); //搜索第 i 个元素的地址并置为当前元素 Type * GetData ( ); //取出表中当前元素的值 int Insert ( Type value ); //将 value 插在表当前位置之后并成为当前元素 Type *Remove ( ); //将链表中的当前元素删去, 填补者为当前元素 ListNode * Firster ( ) { current = first; return first; } //当前指针定位于表头结点 Type *First ( ); //当前指针定位于表中第一个元素并返回其值 Type *Next ( ); //将当前指针进到表中下一个元素并返回其值 int NotNull ( ) { return current != NULL; } //表中当前元素空否？空返回 1, 不空返回 0 int NextNotNull ( ) { return current != NULL && current->link != NULL; } //当前元素下一元素空否？空返回 1, 不空返回 0 };
第3章链表 3-1线性表可用顺序表或链表存储。试问 (1)两种存储表示各有哪些主要优缺点? 、(2)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可能自 改变、在此情况下,应选用哪种存储表示?为什么? (3)若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时 应采用哪种存储表示?为什么? 【解答】 (1)顺序存储表示是将数据元素存放于一个连续的存储空间中,实现顺序存取或(按下标)直接存 取。它的存储效率高,存取速度快。但它的空间大小一经定义,在程序整个运行期间不会发生改变 因此,不易扩充。同时,由于在插入或删除时,为保持原有次序,平均需要移动一半(或近一半)元素, 修改效率不高 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放,且只要存储器中还有空间, 就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序,只需要保持 原来的逻辑顺序,因此不必移动数据,只需修改它们的链接指针,修改效率较高。但存取表中的数据 元素时,只能循链顺序访问,因此存取效率不高 (2)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可能自 动改变、在此情况下,应选用链接存储表示。 如果采用顺序存储表示,必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪 个表增长得快,必须平均分配空间。在程序运行过程中,有的表占用的空间增长得快,有的表占用的 空间增长得慢:有的表很快就用完了分配给它的空间,有的表才用了少量的空间,在进行元素的插入 时就必须成片地移动其他的表的空间,以空出位置进行插入:在元素删除时,为填补空白,也可能移 动许多元素。这个处理过程极其繁琐和低效 如果采用链接存储表示,一个表的存储空间可以连续,可以不连续。表的增长通过动态存储分配 解决,只要存储器未满,就不会有表溢出的问题:表的收缩可以通过动态存储释放实现,释放的空间 还可以在以后动态分配给其他的存储申请要求,非常灵活方便。对于n个表(包括表的总数可能变化) 共存的情形,处理十分简便和快捷。所以选用链接存储表示较好 (3)应采用顺序存储表示。因为顺序存储表示的存取速度快,但修改效率低。若表的总数基本稳 定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时采用顺序存储表示较好 3-2针对带表头结点的单链表,试编写下列函数。 (1)定位函数 Locate:在单链表中寻找第i个结点。若找到,则函数返回第i个结点的地址;若找 不到,则函数返回NUL (2)求最大值函数max:通过一趟遍历在单链表中确定值最大的结点。 (3)统计函数 number:统计单链表中具有给定值x的所有元素 (4)建立函数 create:根据一维数组an建立一个单链表,使单链表中各元素的次序与a[m]中各元 素的次序相同,要求该程序的时间复杂性为O(n (5)整理函数 tidyup:在非递减有序的单链表中删除值相同的多余结点 【解答】 (1)实现定位函数的算法如下: template ListNode *List : Locate( int i)& ∥取得单链表中第i个结点地址,i从1开始计数,i*p=first; int k=0; ∥从表头结点开始检测
第 3 章 链表 22 3-1 线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪些主要优缺点? (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自 动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时， 应采用哪种存储表示？为什么？ 【解答】 (1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存 取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变， 因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素， 修改效率不高。 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间， 就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持 原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据 元素时，只能循链顺序访问，因此存取效率不高。 (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自 动改变、在此情况下，应选用链接存储表示。 如果采用顺序存储表示，必须在一个连续的可用空间中为这 n 个表分配空间。初始时因不知道哪 个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的 空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入 时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移 动许多元素。这个处理过程极其繁琐和低效。 如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配 解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间 还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于 n 个表(包括表的总数可能变化) 共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。 (3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳 定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。 3-2 针对带表头结点的单链表，试编写下列函数。 (1) 定位函数 Locate：在单链表中寻找第 i 个结点。若找到，则函数返回第 i 个结点的地址；若找 不到，则函数返回 NULL。 (2) 求最大值函数 max：通过一趟遍历在单链表中确定值最大的结点。 (3) 统计函数 number：统计单链表中具有给定值 x 的所有元素。 (4) 建立函数 create：根据一维数组 a[n]建立一个单链表，使单链表中各元素的次序与 a[n]中各元 素的次序相同，要求该程序的时间复杂性为 O(n)。 (5) 整理函数 tidyup：在非递减有序的单链表中删除值相同的多余结点。 【解答】 (1) 实现定位函数的算法如下： template ListNode * List :: Locate ( int i ) { //取得单链表中第 i 个结点地址, i 从 1 开始计数, i * p = first; int k = 0; //从表头结点开始检测
第3章链表 while( l=NULL &&klink; k++1 ∥循环,p=NULL表示链短,无第i个结点 return p; ∥若pl=NULL,则k=i返回第i个结点地址 (2)实现求最大值的函数如下: template ListNode *List : Max (i ∥在单链表中进行一趟检测,找出具有最大值的结点地址,如果表空,返回指针NULL if first-> link nulL )return NULL ∥空表,返回指针NUIL ListNode*pmax=frst->link,p=fist->link->link;∥假定第一个结点中数据具有最大值 while(p I= NULL ∥循环,下一个结点存在 if( p->data >pma ∥指针pmax记忆当前找到的具最大值结点 ∥检测下一个结点 (3)实现统计单链表中具有给定值x的所有元素的函数如下 template int List : Count(Type& x)i ∥在单链表中进行一趙检测,找出具有最大值的结点地址,如果表空,返回指针NULL ListNode *p=first->link ∥从第一个结点开始检测 while(p I= NULL )i ∥循环,下一个结点存在 if(p->data =x)n++; ∥找到一个,计数器加1 ∥检测下一个结点 return n: (4)实现从一维数组A[m建立单链表的函数如下: template void List : Create( Type A[, int n)& ∥根据一维数组A[n]建立一个单链表,使单链表中各元素的次序与A[n]中各元素的次序相同 first=p= new ListNodelink =new ListNode(A[); ∥链入一个新结点,值为A ∥指针p总指向链中最后一个结点 p->link NULL 采用递归方法实现时,需要通过引用参数将已建立的单链表各个结点链接起来。为此,在递归地 扫描数组A[n]的过程中,先建立单链表的各个结点,在退出递归时将结点地址p(被调用层的形参) 带回上一层(调用层)的实参p->link template void List create( Type A[l, int n, int 1, ListNode*&p)i ∥有函数:递归调用建立单链表 if(i==n)p=NULL; else( p= new ListNode( A[]) ∥建立链表的新结点
第 3 章 链表 23 while ( p != NULL && k link; k++; } //循环, p == NULL 表示链短, 无第 i 个结点 return p; //若 p != NULL, 则 k == i, 返回第 i 个结点地址 } (2) 实现求最大值的函数如下： template ListNode * List :: Max ( ) { //在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULL if ( first->link == NULL ) return NULL; //空表, 返回指针 NULL ListNode * pmax = first->link, p = first->link->link; //假定第一个结点中数据具有最大值 while ( p != NULL ) { //循环, 下一个结点存在 if ( p->data > pmax->data ) pmax = p; //指针 pmax 记忆当前找到的具最大值结点 p = p->link; //检测下一个结点 } return pmax; } (3) 实现统计单链表中具有给定值 x 的所有元素的函数如下： template int List :: Count ( Type& x ) { //在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULL int n = 0; ListNode * p = first->link; //从第一个结点开始检测 while ( p != NULL ) { //循环, 下一个结点存在 if ( p->data == x ) n++; //找到一个, 计数器加 1 p = p->link; //检测下一个结点 } return n; } (4) 实现从一维数组 A[n]建立单链表的函数如下： template void List :: Create ( Type A[ ], int n ) { //根据一维数组 A[n]建立一个单链表，使单链表中各元素的次序与 A[n]中各元素的次序相同 ListNode * p; first = p = new ListNode; //创建表头结点 for ( int i = 0; i link = new ListNode ( A[i] ); //链入一个新结点, 值为 A[i] p = p->link; //指针 p 总指向链中最后一个结点 } p->link = NULL; } 采用递归方法实现时，需要通过引用参数将已建立的单链表各个结点链接起来。为此，在递归地 扫描数组 A[n]的过程中，先建立单链表的各个结点，在退出递归时将结点地址 p（被调用层的形参） 带回上一层（调用层）的实参 p->link。 template void List :: create ( Type A[ ], int n, int i, ListNode *& p ) { //私有函数：递归调用建立单链表 if ( i == n ) p = NULL; else { p = new ListNode( A[i] ); //建立链表的新结点
第3章链表 create(A, n, i+1, p->link ) ∥递归返回时p->link中放入下层p的内容 template void List : create( Type A[l, int n )i ∥外部调用递归过程的共用函数 first=current=new ListNodelink ) ∥递弟归建立单链表 (5)实现在非递减有序的单链表中删除值相同的多余结点的函数如下 template void List tidyup(i ListNode*p=first- ∥检测指针,初始时指向链表第一个结点 while( p I= nULL & p->link I= NULL ∥循环检测链表 if( p->data ==p->link->data )t ∥若相邻结点所包含数据的值相等 temp= p->first; p->link temp-> link ∥为删除后一个值相同的结点重新拉链 delete temp ∥删除后一个值相同的结点 ∥指针p进到链表下一个结点 3-3设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有 序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用 其它的存储空间。表中允许有重复的数据。 【解答】 #include template class List; template class ListNode friend class List: ∥构造函数 ListNode const Type& item ) ∥构造函数 private Type data; template class List i List( const Type finishied ) ∥建立链表 void Browse ( 印链表 void Merge( List &hb )i ∥连接链表 ListNode "first, 'last;
第 3 章 链表 24 create ( A, n, i+1, p->link ); //递归返回时 p->link 中放入下层 p 的内容 } } template void List :: create ( Type A[ ], int n ) { //外部调用递归过程的共用函数 first = current = new ListNode; //建立表头结点 create ( A, n, 0, first->link ); //递归建立单链表 } (5) 实现在非递减有序的单链表中删除值相同的多余结点的函数如下： template void List :: tidyup ( ) { ListNode * p = first->link, temp; //检测指针, 初始时指向链表第一个结点 while ( p != NULL && p->link != NULL ) //循环检测链表 if ( p->data == p->link->data ) { //若相邻结点所包含数据的值相等 temp = p->first; p->link = temp->link; //为删除后一个值相同的结点重新拉链 delete temp; //删除后一个值相同的结点 } else p = p->link; //指针 p 进到链表下一个结点 } 3-3 设 ha 和hb 分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有 序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用 其它的存储空间。表中允许有重复的数据。 【解答】 #include 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; };
第3章链表 ∥.成员函数的实现 template ListNode: ListNode(: link( NULL )0 ∥构造函数,仅初始化指针成员。 template ListNode ListNode const Type item ) data( item ) link( NULL)0 ∥构造函数,初始化数据与指针成员。 template List: List( const Type finishied) ∥创建一个带表头结点的有序单链表, finished是停止建表输入标志,是所有输入值中不可能出现的数值 first=last=new ListNode( ) ∥创建表头结点 Type value; ListNode *p, *g,*s: cin > value while( value 环建立各个结点 s= new ListNode( value ) q=first; p= first->link; while(p l=NULL && p->data link =s; /在q,p间插入新结点 if( p= NULL )last=s cin > value: template void List: Browse(i ∥浏览并输出链表的内容 cout"p= first->link while(p I= NULL)t cout data; if( pI= last )cout i else cout link; template void List : Merge( List& hb) ∥将当前链表this与链表hb按逆序合并,结果放在当前链表this中。 pa= first->link; pb= hb. first->link ∥检测指针跳过表头结点 first->link NULL ∥结果链表初始化 while( pa= NULL & pb NULL )t 当两链表都未结束时 if( pa->data data (q=pa: pa= pa->link; j ∥从pa链中摘下
第 3 章 链表 25 //各成员函数的实现 template ListNode :: ListNode ( ) : link ( NULL ) { } //构造函数, 仅初始化指针成员。 template ListNode :: ListNode ( const Type & item ) : data ( item ), link ( NULL ) { } //构造函数, 初始化数据与指针成员。 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 link; } //寻找新结点插入位置 q->link = s; s->link = p; //在 q, p 间插入新结点 if ( p == NULL ) last = s; cin >> value; } } template void List :: Browse ( ) { //浏览并输出链表的内容 cout *p = first->link; while ( p != NULL ) { cout data; if ( p != last ) cout "; else cout link; } } template 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 data ) { q = pa; pa = pa->link; } //从 pa 链中摘下
第3章链表 ∥从pb链中摘下 link first-> fst>link=q;m链入结果链的链头 p=( pa I= NULL ) pa: pb; 处理未完链的剩余部分 while(p I= NULL)( q=p; p=p->link q->link first->link; first->link =9: 3-4设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有结点的链 接方向逆转,如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点 【解答1】 template void List: Inverse(i if( first = NULL )return; ListNode *p= first->link, *pr= NULL; while(pI=NULL )i ∥逆转frst指针 pr= first; first=p: p=p->lin ∥指针前移 first->link = pi 【解答2】 template void List: Inverse(i ListNode·p,head= new ListNode();/建表头结点,其link域默认为NUIL while( first I=NULL)& p= first; first= first->link; ∥摘下fist链头结点 p->link head->link; head->link = p 插入head链前端 first= head ->link: delete head 重置frst删去表头结点 3-5从左到右及从右到左遍历一个单链表是可能的,其方法是在从左向右遍历的过程中将连接方向逆 转,如右图所示。在图中的指针p指向当前正在访问的结点,指针pr指向指针p所指结点的左侧的结 点。此时,指针p所指结点左侧的所有结点的链接方向都已逆转。 (1)编写一个算法,从任一给定的位置(p,p)开始,将指针p右移k个结点。如果p移出链表,则 将p置为0,并让pr停留在链表最右边的结点上。 (2)编写一个算法,从任一给定的位置(p,p)开始,将指针p左移k个结点。如果p移出链表,则 将p置为0,并让pr停留在链表最左边的结点上
第 3 章 链表 26 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-4 设有一个表头指针为 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; //指针前移 } first->link = pr; } 【解答 2】 template void List :: Inverse ( ) { ListNode *p, *head = new ListNode ( ); //创建表头结点, 其 link 域默认为 NULL while ( first != NULL ) { p = first; first = first->link; //摘下 first 链头结点 p->link = head->link; head->link = p; //插入 head 链前端 } first = head->link; delete head; //重置 first, 删去表头结点 } 3-5 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆 转，如右图所示。在图中的指针 p 指向当前正在访问的结点，指针 pr 指向指针 p 所指结点的左侧的结 点。此时，指针 p 所指结点左侧的所有结点的链接方向都已逆转。 (1) 编写一个算法，从任一给定的位置(pr, p)开始，将指针 p 右移 k 个结点。如果 p 移出链表，则 将 p 置为 0，并让 pr 停留在链表最右边的结点上。 (2) 编写一个算法，从任一给定的位置(pr, p)开始，将指针 p 左移 k 个结点。如果 p 移出链表，则 将 p 置为 0，并让 pr 停留在链表最左边的结点上
第3章链表 【解答】 (1)指针p右移k个结点 template void List iftToRight( ListNode *& p, ListNode * pr, int k)i if(p= nUll & pr I= first)i ∥经在链的最右端 cout*q: if(p== NULL ∥从链头开始 fi=l: pr= NULL; p=first;) 重置p到链头也算一次右移 else i=0 while( p I= nUlL &&ilink; p->link =pr 链指针p→link逆转指向pr ∥指针pr,p右移 } cout void List * p, ListNode * pr, int k)( if(p== nUll & pr== first ∥已经在链的最左端 coutink; pr->link =p: 链指针pr->link逆转指向p p=pr; pr=q: H++; ∥指针pr,p左移 cout
第 3 章 链表 27 【解答】 (1) 指针 p 右移 k 个结点 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 link; p->link = pr; //链指针 p→link 逆转指向 pr pr = p; p = q; i++; //指针 pr, p 右移 } cout void List :: siftToLeft ( ListNode *& p, ListNode *& pr, int k ) { if ( p == NULL && pr == first ) { //已经在链的最左端 cout *q; while ( pr != NULL && i link; pr->link = p; //链指针 pr->link 逆转指向 p p = pr; pr = q; i++; //指针 pr, p 左移 } cout
第3章链表 ∥字符串最大长度为300(理论上可以无限长) string1 ( ∥构造空字符串 stringl( char*obstr )i ∥从字符数组建立字符串 析构函数 int Length()const i return curLen; ∥字符串长度 stringl& operator = stringl& ob ) ∥串赋值 int operator == string l& ob ) ∥判两串相等 char& operator [ int i ) ∥取串中字符 stringl& operator ()(int pos, int len ) ∥取子串 string l& operator += stringl& ob ) 连接 求子串在串中位置(模式匹配) friend ostream& operator > istream& is, string l& ob ) 用单链表存储的字符串 curle ∥当前字符串长度 ∥单链表表示的字符串类 string 1成员函数的实现,在文件 string l cpp中 #include stringl stringI()i ∥构造函数 chRist new ListNode(W0); curLen 0: 制构造函数 curLen =0; ListNode(*obstr ) while(*obstr I=W0)t link new Listnod obstr i curLen++ string l& string l operator = string l& ob)i ∥串赋值 ListNode *p=ob. chList ListNode *a=chList new ListNode(p-data ) curLen = ob curLen: while(p->data I=10')t
第 3 章 链表 28 const int maxLen = 300; //字符串最大长度为 300（理论上可以无限长） class string1 { public: string1 ( ); //构造空字符串 string1 ( char * obstr ); //从字符数组建立字符串 ~string1 ( ); //析构函数 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;
第3章链表 9=q->link = new ListNode( p->data ) return *this: operator == stringl& ob)i ∥判两串相等 if( curLen I=ob curLen )return 0; ListNode "p=chList, * q=ob.chList; for( int i=0; 1data I=q->data)return 0; return I char& stringl : operator [(int i)i 取串中字符 if (i>=0 &&i *p=chList; int k=0; while( pl= NULL &&klink; k++;) if( pI= nUlL )return p->data return yO stringl& stringl operator ()(int pos, int len)& /取子串 if pos >=0 & len >=0 & pos curLen & pos len-1link; ∥定位于第pos结点 for( int i=1: ilink =new ListNodeschar>(p->data ) q->link new ListNode(\0); ∥建立串结束符 emp curLen =len 0: temp. chList =new ListNode (W0):1 return *tem stringl& stringl operator += string l& ob)i if curLen +ob curLen maxLen )len= maxLen-curLen; else len ob curLen. ∥传送字符数 ListNode<char *q=ob. chList, *p=chList;
第 3 章 链表 29 q = q->link = new ListNode ( p->data ); } return *this; } int string1 :: operator == ( string1& ob ) { //判两串相等 if ( curLen != ob.curLen ) return 0; ListNode *p = chList, *q = ob.chList; for ( int i = 0; i data != q->data ) return 0; else { p = p->link; q = q->link; } return 1; } char& string1 :: operator [ ] ( int i ) { //取串中字符 if ( i >= 0 && i *p = chList; int k = 0; while ( p != NULL && k link; k++; } if ( p != NULL ) return p->data; } return '\0'; } string1& string1 :: operator ( ) ( int pos, int len ) { //取子串 string1 temp; if ( pos >= 0 && len >= 0 && pos *q, *p = chList; for ( int k = 0; k link; //定位于第 pos 结点 q = temp.chList = new ListNode ( p->data ); for ( int i = 1; i link; q = q->link = new ListNode ( 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;
第3章链表 for( int k=0; klink /this串的串尾 for(k=0; klink = new ListNode( q->data ) p-link= new ListNode(10); int stringl Find( stringl& ob)( ∥子串在串中位置(模式匹配) int slen curLen oblen =ob curLen, i= slen -oblen stringl temp= this while(i>-1) if( temp( i, oblen )=ob)break return 1: 3-7如果用循环链表表示一元多项式,试编写一个函数 Polynomial:Calc(x),计算多项式在x处的值 【解答】 下面给出表示多项式的循环链表的类定义。作为私有数据成员,在链表的类定义中封装了3个链 接指针: first、last和 current,分别指示链表的表头结点、链尾结点和最后处理到的结点。 enum Boolean False, True lass Polynomal: ∥多项式前视类定义 friend class Polynomal; double coef, expn; 系数与指数 Term "link ∥项链接指针 Term( double c=0, double e =0, Term next= NULL ) coef (c), expn(e), link(next) class Polynomal i ∥多项式类定义 private Term *first.,’ current ∥头指针,当前指针 int n: ∥多项式阶数 Polynomal ( ∥构造函数 polynomal (i ∥析构函数 int Length()const ∥计算多项式项数 Boolean IsEmpty (i return first->link = first; ∥判是否零多项式 Boolean Find( const double& value ) ∥在多项式中寻找其指数值等于 value的项
第 3 章 链表 30 for ( int k = 0; k link; //this 串的串尾 k = 0; for ( k = 0; k link = new ListNode ( q->data ); q = q->link; } 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-7 如果用循环链表表示一元多项式，试编写一个函数 Polynomial :: Calc(x)，计算多项式在 x 处的值。 【解答】 下面给出表示多项式的循环链表的类定义。作为私有数据成员，在链表的类定义中封装了 3 个链 接指针：first、last 和 current，分别指示链表的表头结点、链尾结点和最后处理到的结点。 enum Boolean { False, True } class Polynomal; //多项式前视类定义 class Term { //项类定义 friend class Polynomal; private: double coef, expn; //系数与指数 Term *link; //项链接指针 public: Term ( double c = 0, double e = 0, Term * next = NULL ) : coef (c), expn(e), link (next) { } } class Polynomal { //多项式类定义 private: Term *first, *current; //头指针, 当前指针 int n; //多项式阶数 public: Polynomal ( ); //构造函数 ~Polynomal ( ); //析构函数 int Length ( ) const; //计算多项式项数 Boolean IsEmpty ( ) { return first->link == first; } //判是否零多项式 Boolean Find ( const double& value ); //在多项式中寻找其指数值等于 value 的项
