问答题(2014年春程序员软考)

函数 Reverselist(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转,即将原链表看成由两部分组成,已经完成逆置的部分和未完成逆置的部分,令s指向未逆置部分的第一个结点,并将该结点插入已完成部分的表头(头结点之后),直到全部结点的指针域都修改完成为止。

例如,某单链表如图所示,逆置过程中指针s的变化情况如图(a)(b)所示。

链表结点类型定义如下:

typedef struct Node{

int data,

struct Node *next;

}Node, *LinkList;

void ReverseList (LinkList headptr){//含头结点的单链表就地逆置, headptr为头指针

LinkList p,s;

if(__(1)__) return;//空链表(仅有头结点)时无需处理

p=__(2)__;//令p指向第一个元素结点

if (!p->next) return;//链表中仅有一个元素结点时无需处理

s= p->next;//s指向第二个元素结点

__(3)__=NULL;//设置第一个元素结点的指针域为空

while (s){

p=s;//令p指向未处理链表的第一个结点

s=__(4)__;

p-> next= headptr-> next;//将p所指结点插入已完成部分的表头

headptr-> next=__(5)__;

}

}

答案解析

(1)!headptr->next 或 !headptr||!headptr->next 或其等价形式(2) headptr->next3) headpin->next->next 或 p>next 或其等价形式(4)s->next 或 p->next 或其等价形式(5)p对于含有头结点的单链表,链表为空时,头结点的指针域为空,表示之后没有其他结点了。因此,空(1)处应填入“!headptr->next”。根据注释,空(2)处所在语句令p指向链表的第一个元素结点,因此空(2)处应填入“headptr->next”。空(3)处的语句执行后,可由图所示的...

查看完整答案

讨论

在非空双向循环链表中q所指的结点后面插入p所指的结点的过程已经依次进行了以下3步:p->llink=q;p->rlink=q->rlink;q->rlink=p;第4步应该是____________________;(写出该步对应的语句)。

已知结点指针p、q分别表示双向链表中任意两个相邻结点(即p->rlink=q且q->llink=p),请写出删除q所指结点的程序段。

试写出在双向链表da中的插入操作算法,算法中插入位置的获取可直接引入getnodep(da,i),其中参数da为双向链表,i是要插入的数据,要求算法中含有双向链表da的结点结构描述。

假设有两个按元素值递增有序排列的线性表A和B,均以带头结点的单链表作为存储结构,编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C,并要求利用原表(A表和B表)的结点空间存放表C。

没有提供指针类型的语言,无法构造链式结构,该说法【 】

线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。【 】

将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为__________。

双向链表的优势是____________________。

将下图所示的s所指点加到p所指点之后,其语句应为【 】

现有非空双向链表 L,其结点结构为:prer|data|next。prer 是指向前直接前驱结点的指针,next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点( 非尾结点) 之后插入指针 s 指向的新结点, 则在执行了语句序列: “s->next=p->next;p->next=s”后,还要执行【 】