数据结构算法题

前五章习题算法2.2算法设计题1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1)voiddelete(SqList&L,ElemTypex,ElemTypey){inti=0,k=0;while(iL.length){if(L.elem[i]=x&&L.elem[i]=y)k++;//记录被删记录的个数elseL.elem[i-k]=L.elem[i];//前移k个位置i++;}L.length=L.length-k;}2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列.要求算法的空间复杂度为O(1),时间复杂度为O(n)voidmove(SqList&L){inti=0,j=L.length-1;inttemp;while(ij)//使得正数都在前半部分，负数都在后半部分{while(ij&&L.elem[i]0)i++;while(ij&&L.elem[j]0)j--;if(ij)//交换L.elem[i](负数)和L.elem[j](正数){temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;}}i=1;while(iL.length/2)//通过交换使得正负数相间{j=L.length-2;temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;i=i+2;j=j-2;}}3.假设一两个元素依之=值递增有序排列的线性表A和B分别表示两个集合(同一元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作.交集:voidintersection(SqListA,SqListB,SqList&C){inti=0,j=0,k=0;while(iA.length&&jB.length){if(A.elem[i]B.elem[j])i++;elseif(A.elem[i]B.elem[j])j++;else{C.elem[k]=A.elem[i];k++;i++;j++;}//共同的元素}C.length=k;}并集:voidUnion(SqListA,SqListB,SqList&C){inti=0,j=0,k=0;while(iA.length&&jB.length){if(A.elem[i]B.elem[j]){C.elem[k]=A.elem[i];k++;i++;}elseif(A.elem[i]B.elem[j]){C.elem[k]=B.elem[j];k++;j++;}else{C.elem[k]=A.elem[i];k++;i++;j++;}//共同的元素只放一个}while(iA.len){C.elem[k]=A.elem[i];k++;i++}while(jB.len){C.elem[k]=B.elem[j];k++;j++}C.length=k;}差集:voiddiffernce(SqListA,SqListB,SqList&C){inti=0,j=0,k=0;while(iA.length&&jB.length){if(A.elem[i]B.elem[j]){C.elem[k]=A.elem[i];k++;i++;}elseif(A.elem[i]B.elem[j]){j++;}else{i++;j++;}//共同的元素只放一个}while(iA.length){C.elem[k]=A.elem[i];k++;i++}C.length=k;}2.3线性表的链式存储结构简答题:1.描述以下三个概念的区别:头结点,头指针,首元结点(第一个元素结点).在单链表中设置头结点的作用是什么?答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表.非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表.双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。头结点headàdatalink头指针首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。2.试比较线性表的两种存储结构的优缺点,在什么情况下用顺序表比链表好?①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入.删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入.删除操作，则采用链表。算法设计题1试写一算法,对单链表的实现就地逆置StatusListOppose_L(LinkList&L){LinkListp,q;p=L-next;//p指向单链表第一个结点L-next=NULL;//形成空的单链表while(p){//采用头插入法将p结点插入到头结点的后面实现逆置q=p;p=p-next;q-next=L-next;L-next=q;}returnOK;}2试设计一个算法,求A和Bl两个单链表表示的集合的交集并集和差集,单链表中的数据递增有序排列并集：LinkListBingji(LinkList&Head1,LinkList&Head2,LinkList&Head3){LNode*p1=Head1-next;LNode*p2=Head2-next;LNode*p3=Head3=Head1;while(p1&&p2){if(p1-datap2-data){p3-next=p1;p3=p3-next;p1=p1-next;}else{if(p1-datap2-data){p3-next=p2;p3=p3-next;p2=p2-next;}else{p3-next=p1;p3=p3-next;p1=p1-next;q=p2;free(q);p2=p2-next;}}}p3-next=(p1)?p1:p2;free(Head2);returnHead3;}交集：LinkListJiaoji(LinkList&Head1,LinkList&Head2,LinkList&Head3){LinkListpa,pb,r,p;pa=Head1-next;pb=Head2-next;r=Head3=Head1;while(pa&&pb){if(pa-datapb-data){r-next=pa-next;free(pa);pa=r-next;}elseif(pa-datapb-data)pb=pb-next;else{r-next=pa;r=pa;pa=pa-next;}}while(pa){r-next=pa-next;free(pa);pa=r-next;}while(Head2-next)//释放Head2链表所有的结点空间{p=Head2-next;Head2-next=p-next;free(p);}returnHead3;}差集：LinkListChaji(LinkList&Head1,LinkList&Head2,LinkList&Head3){LinkListpa,pb,r,p;pa=Head1-next;pb=Head2-next;r=Head3=Head1;while(pa&&pb){if(pa-datapb-data){r-next=pa;r=r-next;pa=pa-next;}elseif(pa-datapb-data)pb=pb-next;else{r-next=pa-next;free(pa);pa=r-next;}}while(Head2-next)//释放Head2链表所有的结点空间{p=Head2-next;Head2-next=p-next;free(p);}returnHead3;}3已知线性表中的元素以值递增有序排列,并以单链表作存储结构,试写一高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删除的结点空间,并分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)StatusListDelete_L(LinkList&L,ElemTypemink,ElemTypemaxk){LinkListp,q,prev=NULL;if(minkmaxk)returnERROR;pre=L;p=pre-next;//pre是p的前驱，p是pre的后继while(p&&p-data=mink){//寻找第一大于mink的元素，让p指向它，pre指向其前驱pre=p;p=p-next;}//whilewhile(p&&p-datamaxk)//删除大于mink小于maxk的结点{pre-next=p-next;free(p);p=pre-next;}returnOK;}3.2算法设计题假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化,如队列和出队列的算法1.typedefintElemType;typedefstructQNode{ElemTypedata;QNode*next;}QNode,*QPtr;typedefstruct{QPtrrear;intsize;}Queue;StatusInitQueue(Queue&q){Q.rear=(Qnode*)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);q.rear-next=q.rear;//空的循环链表q.size=0;returnOK;}StatusEnQueue(Queue&q,ElemTypee){QPtrp;p=(Qnode*)malloc(sizeof(QNode));if(!p)returnexit(OVERFLOW);p-data=e;//创建被插入结点pp-next=q.rear-next;q.rear-next=p;q.rear=p;//将p所指结点插入到q.rear的后面}q.size++;returnOK;}StatusDeQueue(Queue&q,ElemType&e){QPtrp;if(q.size==0)returnFALSE;p=q.rear-next-next;//p指向循环链表的第一个结点（即被删结点）e=p-data;q.rear-next-next=p-next;//删除p所指结点free(p);}q.size--;returnOK;}4.1算法设计题1.编写一个实现串的置换操作Repalce(&s,T,V)的算法intReplace(Stringtype&S,Stringtype