《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)

1第1章4．答案：（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。5.选择题(1)~(6)：CCBDDA6．（1）O(1)（2）O(m*n)（3）O(n2)（4）O(log3n)（5）O(n2)（6）O(n)2第2章1．选择题（1）~（5）：BABAD（6）~（10）：BCABD（11）~（15）：CDDAC2．算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。[题目分析]合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){//合并链表La和Lb，合并后的新表使用头指针Lc指向pa=La-next;pb=Lb-next;//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb){if(pa-datapb-data){pc-next=pa;pc=pa;pa=pa-next;}//取较小者La中的元素，将pa链接在pc的后面，pa指针后移elseif(pa-datapb-data){pc-next=pb;pc=pb;pb=pb-next;}//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移else//相等时取La中的元素，删除Lb中的元素{pc-next=pa;pc=pa;pa=pa-next;q=pb-next;deletepb;pb=q;}}pc-next=pa?pa:pb;//插入剩余段deleteLb;//释放Lb的头结点}（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。[题目分析]B表的头结点使用原来A表的头结点，为C表新申请一个头结点。从A表的第一个结点开始，依次取其每个结点p，判断结点p的值是否小于0，利用前插法，将小于0的结点插入B表,大于等于0的结点插入C表。3[算法描述]voidDisCompose(LinkedListA){p=A-next;∥p为工作指针B=A;B-next=NULL;∥B表初始化C=newLNode;∥为C申请结点空间C-next=NULL;∥C初始化为空表while(p!=NULL){r=p-next;∥暂存p的后继if(p-data0){p-next=B-next;B-next=p;}∥将小于0的结点链入B表,前插法else{p-next=C-next;C-next=p;}∥将大于等于0的结点链入C表p=r;∥p指向新的待处理结点。}}（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。[题目分析]假定第一个结点中数据具有最大值，依次与下一个元素比较，若其小于下一个元素，则设其下一个元素为最大值，反复进行比较，直到遍历完该链表。[算法描述]ElemTypeMax(LinkListL){if(L-next==NULL)returnNULL;pmax=L-next;//假定第一个结点中数据具有最大值p=L-next-next;while(p!=NULL){//如果下一个结点存在if(p-datapmax-data)pmax=p;//如果p的值大于pmax的值，则重新赋值p=p-next;//遍历链表}returnpmax-data;}（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。[题目分析]从首元结点开始，逐个地把链表L的当前结点p插入新的链表头部。[算法描述]voidinverse(LinkList&L){//逆置带头结点的单链表Lp=L-next;L-next=NULL;4while(p){q=p-next;//q指向*p的后继p-next=L-next;L-next=p;//*p插入在头结点之后p=q;}}（8）设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。[题目分析]分别查找第一个值mink的结点和第一个值≥maxk的结点，再修改指针，删除值大于mink且小于maxk的所有元素。[算法描述]voiddelete(LinkList&L,intmink,intmaxk){p=L-next;//首元结点pre=p;//pre指向p的前驱while(p&&p-data=mink){pre=p;p=p-next;}//查找第一个值mink的结点if(p){while(p&&p-datamaxk)p=p-next;//查找第一个值≥maxk的结点q=pre-next;pre-next=p;//修改指针while(q!=p){s=q-next;deleteq;q=s;}//释放结点空间}//if}（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。voidDelete（SqListL）∥L是有n个元素的顺序表，本算法删除L中所有值为item的元素。{intk=0;//k为值不等于item的个数for(i=0;iL.length;i++)if(L.elem[i]!=item{L.elem[k]=L.elem[i];k++;}L.length=k;}5第3章1．选择题（1）~（5）：CCDAA（6）~（10）：DABCD（11）~（15）：DDBCB2.算法设计题（1）将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下：Typedefstruct{inttop[2],bot[2];//栈顶和栈底指针SElemType*V;//栈数组intm;//栈最大可容纳元素个数}DblStack；[题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为-1，右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向、迎面增长，栈顶指针指向栈顶元素。[算法描述](1)栈初始化voidInitDblStackt(DblStack&S,intm){S.V=newSElemType[m];S.bot[0]=-1;S.top[0]=-1;S.bot[1]=-1;S.top[1]=m;}(2)入栈操作：voidDblPush(DblStack&S,inti,intx)∥i为栈号，i=0表示左栈，i=1为右栈，x是入栈元素。入栈成功返回1，失败返回0{if(i0||i1){cout“栈号输入不对”endl;exit(0);}if(S.top[1]-S.top[0]==1){cout“栈已满”endl;return(0);}if(i==0)S.V[++S.top[0]]=x;elseS.V[--S.top[1]]=x;}}(3)退栈操作SElemTypeDblPop(DblStack&S,intI,SElemTypex)6∥退栈。i代表栈号，i=0时为左栈，i=1时为右栈。退栈成功时返回退栈元素{if(i0||i1){cout“栈号输入错误”endl；exit(0);}if(S.top[i]==S.bot[i]return;//栈空if(i==0)x=S.V[S.top[0]--];elsex=S.V[S.top[1]++];returnx;}(4)判断栈空intIsEmpty(DblStackS,inti);{return(S.top[0]==-1&&S.top[1]==m);}(5)判断栈满intIsFull(DblStackS,inti);{if(S.top[0]+1==S.top[1])return1;elsereturn0;}[算法讨论]请注意算法中两栈入栈和退栈时的栈顶指针的计算。左栈是通常意义下的栈，而右栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)[题目分析]将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较，若相等，则再出栈一个元素与后一个字符比较，……，直至栈空，结论为字符序列是回文。在出栈元素与串中字符比较不等时，结论字符序列不是回文。[算法描述]intIsHuiwen(char*t){//判断t字符向量是否为回文，若是，返回1，否则返回0SqStackS;inti,len;chartemp;InitStack(&S);len=strlen(t);//求向量长度for(i=0;ilen/2;i++)//将一半字符入栈Push(&s,t[i]);if(len%2!=0)i++;//长度为奇数，跳过中间字符while(!EmptyStack(&s))7{//每弹出一个字符与相应字符比较temp=Pop(&s);if(temp!=S[i])return0;//不等则返回0elsei++;}return1;//比较完毕均相等则返回1}(6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。[题目分析]置空队就是建立一个头节点，并把头尾指针都指向头节点，头节点是不存放数据的；判队空就是当头指针等于尾指针时，队空；入队时，将新的节点插入到链队列的尾部，同时将尾指针指向这个节点；出队时，删除的是队头节点，要注意队列的长度大于1还是等于1的情况，这个时候要注意尾指针的修改，如果等于1，则要删除尾指针指向的节点。[算法描述]//先定义链队结构:typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;//以上是结点类型的定义typedefstruct{QueuePtrrear;}LinkQueue;//只设一个指向队尾元素的指针(1)置空队voidInitQueue(LinkQueue&Q){//置空队：就是使头结点成为队尾元素QNode*s;Q.rear=Q.rear-next;//将队尾指针指向头结点while(Q.rear!=Q.rear-next)//当队列非空，将队中元素逐个出队{s=Q.rear-next;Q.rear-next=s-next;deletes;}//回收结点空间}(2)判队空intEmptyQueue(LinkQueue*Q){//判队空。