每日一题数据结构

1．已知单链表中结点p不是链尾结点，若在p之后插入结点s，则应执行以下（）

操作。

A．S→next=p;p→next=S;

B．p→next=S;S→next=p;

C．S→next=p→next;p=S;

D．S→next=p→next;p→next=S;

2．假设有n（n1）个线性表顺序地存放在顺序表S[1Lm]中，令F[i]和R[i]指示第i个

（1≤i≤n）表的第1个元素和最后1个元素在S中的位置，并设定R[i]F[i+1]，F[n+1]=m+1，

如图2-2所示。试写出实现下列要求的算法。

（1）在第i个表中的第j项后面插入1个元素，仅当整个顺序表空间填满时，不允许进行

插入操作。

（2）删除第i个表中的第j个元素，要求在删除第j个元素后，该表仍为顺序存储的线性

表。

解析：

1．D。

插入结点的时候注意不要断链，注意指针操作的顺序：s→next=p→next;p→next=s。

2.本题实质上是将n个线性表（长度可能不相同）放于一个连续空间（长度为m），来解决

这些线性表的插入和删除问题。

（1）的算法程序代码如下：

voidins(i,j,x)

{

intp,k;

if(R[n]==m)

cout"上溢"endl;

else

{

for(p=n;p=i+1;--p)//将i+1到n的线性表后移一个元素

{

for(k=R[p];k=F[p];--k)

//将第p个线性表后移一个元素

S[k+1]=S[k];

++R[p];++F[p];//第p个线性表的首尾元素位置均增1

}

for(p=R[i];p=j+1;--p)

//将第i个线性表中的第j个位置起的元素均后移

S[p+1]=S[p];

S[p]=x;//在第i个线性表的第j个位置处存放x

++R[p];//第p个线性表的R[p]增1

}

}

（2）的算法程序代码如下：

voiddel(i,j)

{

for(p=F[i]+j;p=m;++p)//元素前移覆盖要删除的元素

S[p]=S[p+1];

for(p=i;p=n;++p)//第i个及以后的线性表的R[i]值减1

--R[p];

for(p=i+1;p=n;++p)//第i+1个及以后的线性表的F[i]值减1

--F[p];

}

转载请注明：http://www.92nongye.com/zyjs/204621636.html