数据结构算法题.doc

文档介绍：前五章习题算法

算法设计题
(X<=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1)
void delete(SqList &L,ElemType x,ElemType y)
{
int i=0,k=0;
while(i<)
{
if([i]>=x &&[i]<=y)
k++; //记录被删记录的个数
else [i-k]=[i]; //前移k个位置
i++;
}
=-k;
}
2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列. 要求算法的空间复杂度为O(1),时间复杂度为O(n)
void move(SqList &L)
{
int i=0,j=-1;
int temp;
while(i<j) //使得正数都在前半部分,负数都在后半部分
{
while(i<j&&[i]>0)i++;
while(i<j&&[j]<0)j--;
if(i<j) //[i](负数)[j](正数)
{
temp=[i];
[i]=[j];
[j]=temp;
}
}
i=1;
while(i<) //通过交换使得正负数相间
{
j=-2;
temp=[i];
[i]=[j];
[j]=temp;
i=i+2;
j=j-2;
}
}
=值递增有序排列的线性表A和B分别表示两个集合(同一元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作.
交集:
void intersection(SqList A,SqList B ,SqList &C)
{
int i=0,j=0,k=0;
while(i<&&j<)
{
if([i]<[j]) i++;
else if ([i]>[j]) j++;
else { [k]=[i]; k++;i++;j++;} //共同的元素
}
=k;
}
并集:
void Union(SqList A,SqList B ,SqList &C)
{
int i=0,j=0,k=0;
while(i<&&j<)
{
if([i]<[j]) {[k]=[i];k++;i++;}
else if ([i]>[j]) {[k]=[j];k++;j++;}
else {[k]=[i]; k++;i++;j++;} //共同的元素只放一个
}
while(i<){[k]=[i];k++;i++}
while(j<){[k]=[j];k++;j++}
=k;
}
差集:
void differnce(SqList A,SqList B ,SqList &C)
{
int i=0,j=0,k=0;
while(i<&&j<)
{
if([i]<[j]) {[k]=[i];k++;i++;}
else if ([i]>[j]) {j++;}
else {i++;j++;} //共同的元素只放一个
}
while(i<){[k]=[i];k++;i++}
=k;
}

简答题:
描述以下三个概念的区别:头结点,头指针,首元结点(第一个元素结点).在单链表中设置头结点的作用是什么?
答:首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便,通常在链表的首元结点之前附设一个结点,称为头结点,该结点