算法与数据结构（C++语言版）（第2版） 第2章课后习题答案

PAGEPAGE2习题答案选择1-10：ADBACABDAD填空1、（a）元素的存储位置（b）指针2、p->next!=NULL3、L->next==L或L->prior==L或L->prior==L&&L->next==L…或L->next==L->next…..（a）O(1)（b）O(n)判断1-6：对错错错错错四、应用1、在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。2、选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。3、链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储结构的缺点。4、参见2.6节5、单循环链表往往只设尾指针而不设头指针，用一个指向尾结点的尾指针来标识单循环链表，好处是既方便查找表尾结点又方便查找头结点，因为通过尾结点的指针域很容易找到头结点。若使用头指针查找表尾结点需要从头遍历链表，时间复杂度是O(n)。五、算法设计题1、SeqListRearrange(SeqLista){ inti,j,t; i=0;j=a.Last-1;//i,j为工作指针(下标) t=a.data[0];//暂存枢轴元素。 while(i<j) { while(i<j&&a.data[j]>=0)j--; //j指针前移找小于0的元素 if(i<j)a.data[i++]=a.data[j]; //将负数前移 while(i<j&&a.data[i]<0)i++;//i指针后移找大于等于0的元素 if(i<j)a.data[j--]=a.data[i]; //正数后移 } a.data[i]=t; //将原第一元素放到最终位置 returna;}2、(1)LinkedListDelSame（LinkedListla）{ pre=la->next； ∥pre是p所指向的前驱结点的指针 p=pre->next； ∥p是工作指针，设链表中至少有一个结点 while（p） if（p->data==pre->data）∥相同元素值,释放结点{u=p；pre->next=p->next;p=p->next；free（u）；} else {pre=p；p=p->next；} ∥元素值不同 returnla;}(2)算法时间复杂度O(n)3、DLinkedListDInsert(DLinkedListla,ElemTypex){ p=la->next; ∥p指向第一元素 ∥MaxElemType是和x同类型的机器最大值，用做监视哨 la->data=MaxElemType; while(p->data<x) ∥寻找插入位置 p=p->next

; s=(DLNode*)malloc(sizeof(DLNode));∥申请结点空间 s->data=x; s->prior=p->prior; ∥将插入结点链入链表 s->next=p; p->prior->next=s; p->prior=s;}4、（1）①分别求出str1和str2所指的两个链表的长度m和n；②将两个链表以表尾对齐：即长的链表将指针移到|m-n+1|,短链表的指针指向链表的第一个字母；=3\*GB3③两个链表进行模式匹配：对应字母比较，从最后遇到两个链表结点值相等，直至到表尾对应结点值都相等为止。要注意处理虽然首次遇到对应结点值相等，但有后续结点值不等的情况,即在匹配中，并非一遇到对应字母相等，就结论后边是共同后缀。（2）求用单链表表示的两个单词的共同后缀的算法typedefstructNode{ ElemTypedata;structNode*next;}LNode,*LinkedList；intListLength(LNode*la){//求链表la的长度inti=0;LNode*p=la->next; //p指向链表的第一个元素结点while(p){i++; //元素个数加1p=p->next; //链表指针后移}returni; //返回链表的长度}LNode*ComPostfix(LNode*str1,LNode*str2){//str1和str2分别是单词以单链表存储的头指针，本算法返回两个单词共同后缀的起始位置p=null; //p指向两个链表共同后缀的起始位置m=ListLength(str1);n=ListLength(str2); //求链表str1和str2的长度if(m>n){ s=str1->next; //s指向长链表的第一个元素 q=srt2->next; //q指向短链表的第一个元素 len=m-n+1; //两个链表开始比较时，长链表应移到的位置}else{ s=str2->next; //s指向长链表的第一个元素 q=srt1->next; //q指向短链表的第一个元素 len=n-m+1; //两个链表比较时，长链表应移到的位置}i=1;while(i<len){i++;s=s->next;} //长链表要移到两个链表尾部对齐的位置while(s){while(s&&s->data!=q->data)//对应字母不等，后移指针 { s=s->next;q=q->next;}p=s; //p指向两个链表共同后缀的起始位置while(s&&s->data==q->data)//如对应字母相等，后移指针{ s=s->next;q=q->next;}}returnp; //返回两个链表共同后缀的起始位置}（3）算法中求了两个链表的长度，接着将长链表的指针移到两链表的比较处，进行对应元素的比较，记住可能共同后缀的开始位置，直到链表尾。总的时间复杂度为O(m+n)。5、(1)算法思想：定义一个大小为N的数组，初始化为0.在遍历链表的同时将数组中索引值为节点的值的绝对值的元素置1.如果此元素已经为1，说明此节点之前已经有与此节点的值的绝对值相等的节点，需将此节点删除。(2)节点的数据结构定义如下：typedefstructNode{Intdata;StructNode*next;}Node;(3)inta[n];//全局数组标志节点的绝对值的值是否出现过voidDeleteABSEqualNode(Node*head){ memset(a,0,n);//初始化为0 if(head==NULL)returnNULL; Node*p=head; Node*r=head; while(p!=NULL) { if(a[abs(p->data)]==1) //如果此绝对值已经在数组中出现过，则删除 { r->next=p->next;deletep;p=r->next;} else//否则，将数组中对应的元素置1 { a[abs(p->data)]=1;r=p;p=p->next;} } returnhead;}(4)只遍历一次链表，所以时间复杂度为O(n)因为申请大小为n的数组，所以空间复杂度为O(n)（n为节点绝对值的最大值）。6、(1)算法思想由于数组中有n个整数，则未出现的最小的正整数一定在1到n+1的范围，假如：数组a为[1,2,3,4]，则最小正整数为5，也就是n+1。如果数组中介于1到n之间的正整数个数不足n个，则未出现的最小的正整数的范围是1到n。设置一个辅助数组b,大小为n+2,初始值全部为0，然后对a[i]进行遍历，如果0<a[i]<=n+1，则将b[a[i]]赋值为1，接下来遍历b数组，遇到的第一个满足b[i]==0的就退出，i就是数组a中未出现过的最小正整数(2)代码实现intfindMissMin(intA[],intn){int*B=newint[n]; //创建动态数组memset(B,0,n*sizeof(int)); //赋初值inti;for(i=0;i<n;++i){ if(A[i]>0&&A[i]<n){//仅处理A中范围在1~n的元素B[A[i]-1]++;}}for(i=0;i<n;++i){if(B[i]==0)break;}delete[]B;returni+1;}(3)算法的时间复杂度为O(n);空间复杂度为O(n)。7、(1)算法思想①首先寻找单链表的中心结点，使用两个指针p、q，每次p走一步，q走两步，当q到链表尾时，p正好在链表中心的位置。②将链表后半段利用头插法逆置。③从单链表前后两段中依次各取一个结点，并重新排列。(2)代码实现voidrealign(NODE*h){NODE*p,*q,*r,*s;p=q=h;while(q->next!=NULL){ //寻找中间结点p=p->next; //p向后移动一个结点q=q->next;if(q->next!=NULL)q=q->next;//q向后移动两个结点}q=p->next; //p指向中间结点，q指向p后面的结点p->next=NULL;while(q!=NULL){ //从q开始逆置后半段r=q->next;q->next=p->next; //p是中间结点，每次新结点插入在p之后p->next=q;q=r;}s=h