第3章习题

单链表的结点类(ListNodeclass)和链表类(Listclass)的类定义。template<classType>classList;//前视的类定义template<classType>classListNode{//链表结点类的定义friendclassList<Type>;//List类作为友元类定义private:Typedata;//数据域ListNode<Type>*link;//链指针域public:ListNode():link(NULL){}//仅初始化指针成员的构造函数ListNode(constType&item):data(item),link(NULL){}//初始化数据与指针成员的构造函数ListNode<Type>*getNode(constType&item,ListNode<Type>*next=NULL)//以item和next建立一个新结点ListNode<Type>*getLink(){returnlink;}//取得结点的下一结点地址TypegetData(){returndata;}//取得结点中的数据voidsetLink(ListNode<Type>*next){link=next;}//修改结点的link指针voidsetData(Typevalue){data=value;}//修改结点的data值};template<classType>classList{//单链表类定义private:ListNode<Type>*first,*current;//链表的表头指针和当前元素指针public:List(constType&value){first=current=newListNode<Type>(value);}//构造函数~List(){MakeEmpty();deletefirst;}//析构函数voidMakeEmpty();//将链表置为空表intLength()const;//计算链表的长度ListNode<Type>*Find(Typevalue);//搜索含数据value的元素并成为当前元素ListNode<Type>*Locate(inti);//搜索第i个元素的地址并置为当前元素Type*GetData();//取出表中当前元素的值intInsert(Typevalue);//将value插在表当前位置之后并成为当前元素Type*Remove();//将链表中的当前元素删去,填补者为当前元素ListNode<Type>*Firster(){current=first;returnfirst;}//当前指针定位于表头结点Type*First();//当前指针定位于表中第一个元素并返回其值Type*Next();//将当前指针进到表中下一个元素并返回其值intNotNull(){returncurrent!=NULL;}//表中当前元素空否？空返回1,不空返回0intNextNotNull(){returncurrent!=NULL&&current->link!=NULL;}//当前元素下一元素空否？空返回1,不空返回0};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<classType>ListNode<Type>*List<Type>::Locate(inti){//取得单链表中第i个结点地址,i从1开始计数,i<=0时返回指针NULLif(i<=0)returnNULL;//位置i在表中不存在ListNode<Type>*p=first;intk=0;//从表头结点开始检测while(p!=NULL&&k<i){p=p->link;k++;}//循环,p==NULL表示链短,无第i个结点returnp;//若p!=NULL,则k==i,返回第i个结点地址}(2)实现求最大值的函数如下：template<classType>ListNode<Type>*List<Type>::Max(){//在单链表中进行一趟检测，找出具有最大值的结点地址,如果表空,返回指针NULLif(first->link==NULL)returnNULL;//空表,返回指针NULLListNode<Type>*pmax=first->link,p=first->link->link;//假定第一个结点中数据具有最大值while(p!=NULL){//循环,下一个结点存在if(p->data>pmax->data)pmax=p;//指针pmax记忆当前找到的具最大值结点p=p->link;//检测下一个结点}returnpmax;}(3)实现统计单链表中具有给定值x的所有元素的函数如下：template<classType>intList<Type>::Count(Type&x){//在单链表中进行一趟检测，找出具有最大值的结点地址,如果表空,返回指针NULLintn=0;ListNode<Type>*p=first->link;//从第一个结点开始检测while(p!=NULL){//循环,下一个结点存在if(p->data==x)n++;//找到一个,计数器加1p=p->link;//检测下一个结点}returnn;}(4)实现从一维数组A[n]建立单链表的函数如下：template<classType>voidList<Type>::Create(TypeA[],intn){//根据一维数组A[n]建立一个单链表，使单链表中各元素的次序与A[n]中各元素的次序相同ListNode<Type>*p;first=p=newListNode<Type>;//创建表头结点for(inti=0;i<n;i++){p->link=newListNode<Type>(A[i]);//链入一个新结点,值为A[i]p=p->link;//指针p总指向链中最后一个结点}p->link=NULL;}采用递归方法实现时，需要通过引用参数将已建立的单链表各个结点链接起来。为此，在递归地扫描数组A[n]的过程中，先建立单链表的各个结点，在退出递归时将结点地址p（被调用层的形参）带回上一层（调用层）的实参p->link。template<Type>voidList<Type>::create(TypeA[],intn,inti,ListNode<Type>*&p){//私有函数：递归调用建立单链表if(i==n)p=NULL;else{p=newListNode<Type>(A[i]);//建立链表的新结点create(A,n,i+1,p->link);//递归返回时p->link中放入下层p的内容}}template<Type>voidList<Type>::create(TypeA[],intn){//外部调用递归过程的共用函数first=current=newListNode<Type>;//建立表头结点create(A,n,0,first->link);//递归建立单链表}(5)实现在非递减有序的单链表中删除值相同的多余结点的函数如下：template<classType>voidList<Type>::tidyup(){ListNode<Type>*p=first->link,temp;//检测指针,初始时指向链表第一个结点while(p!=NULL&&p->link!=NULL)//循环检测链表if(p->data==p->link->data){//若相邻结点所包含数据的值相等temp=p->first;p->link=temp->link;//为删除后一个值相同的结点重新拉链deletetemp;//删除后一个值相同的结点}elsep=p->link;//指针p进到链表下一个结点}3-3设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。【解答】#include<iostream.h>template<classType>