数据结构算法题.docVIP

前五章习题算法 2.2 算法设计题 1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1) void delete(SqList L,ElemType x,ElemType y) { int i=0,k=0; while(iL.length) { if(L.elem[i]=x L.elem[i]=y) k++; //记录被删记录的个数 else L.elem[i-k]=L.elem[i]; //前移k个位置 i++; } L.length=L.length-k; } void move(SqList L) { int i=0,j=L.length-1; int temp; while(ij) //使得正数都在前半部分，负数都在后半部分 { while(ijL.elem[i]0)i++; while(ijL.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交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作. 交集: void intersection(SqList A,SqList B ,SqList C) { int i=0,j=0,k=0; while(iA.lengthjB.length) { if(A.elem[i]B.elem[j]) i++; else if (A.elem[i]B.elem[j]) j++; else { C.elem[k]=A.elem[i]; k++;i++;j++;} //共同的元素 } C.length=k; }void Union(SqList A,SqList B ,SqList C) { int i=0,j=0,k=0; while(iA.lengthjB.length) { if(A.elem[i]B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;} else if (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; } 差集: void differnce(SqList A,SqList B ,SqList C) { int i=0,j=0,k=0; while(iA.lengthjB.length) { if(A.elem[i]B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;} else if (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线性表的链式存储结构 简答题: 描述以下三个概念的区别:头结点,头指针,首元结点(第一个元素结点).在单链表中设置头结点的作用是什么? 答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表.非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表.双向链