数据结构算法题.doc

《数据结构算法题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、前五章习题算法2.2算法设计题1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X<=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1)voiddelete(SqList&L,ElemTypex,ElemTypey){inti=0,k=0;while(i=x&&L.elem[i]<=y)k++;//记录被删记录的个数elseL.elem[i-k]=L.elem[i];//前移k个位置i++;}L.length=L.leng

2、th-k;}2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列.要求算法的空间复杂度为O(1),时间复杂度为O(n)voidmove(SqList&L){inti=0,j=L.length-1;inttemp;while(i0)i++;while(i

3、数){temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;}}i=1;while(i

4、试对顺序表实现上述操作.交集:voidintersection(SqListA,SqListB,SqList&C){inti=0,j=0,k=0;while(iB.elem[j])j++;else{C.elem[k]=A.elem[i];k++;i++;j++;}//共同的元素}C.length=k;}并集:voidUnion(SqListA,SqListB,SqLis

5、t&C){inti=0,j=0,k=0;while(iB.elem[j]){C.elem[k]=B.elem[j];k++;j++;}else{C.elem[k]=A.elem[i];k++;i++;j++;}//共同的元素只放一个}while(i

6、while(jB.elem[j]){j++;}else{i++;j++;}//共同的元素只放一

7、个}while(i

8、头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表.双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。头结点headàdatalink头指针首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头