第2章习题答案

第2章 线性表

习题2

1.描述头指针、头结点、首元结点的区别,并说明头指针和头结点的作用。

解:在线性表的链式存储结构中,头指针是指链表的指针,若链表有头结点则是链表的头结点的指针,头指针具有标识作用。故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的,放在第一个结点之前,其数据域一般无意义,有结点后,对在第一个元素结点前插入结点和删除第一个结点,其操作与对其他结点的操作统一了。而且无论链表是否为空,头指针均不为空。首元结点也就是第一个元素结点,它是头结点后面的第一个结点。

2.在顺序表中插入和删除一个结点需平均移动多少个元素?具体的移动次数取决于哪两个因素? 解:在顺序表中插入和删除一个结点需平均移动表中一半元素。具体的移动次数取决于表长和该元素在表中的位置个因素。

3.在单链表和双向链表中,是否从当前结点出发访问到任何一个结点?

解:在单链表中不能从当前结点出发访问到任何一个结点,但在双向链表中可以从当前结点出发访问到任何一个结点。

4.若较频繁地对一个线性表进行插入和删除操作,该线性表宜采用何种存储结构?为什么? 解:采用链式存储结构,它根据实际需要申请内存空间,而当不需要时又可将不用的结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。

5.有线性表(a1,a2,?,ai?1,ai,ai?1,?,an),采用单链表存储,头指针为H,每个结点中存放线性表中的一个元素,现查找某个元素值为x的结点。分别写出下面三种情况的查找语句,要求时间尽量少。

(1)线性表中元素无序。 (2)线性表中元素按递增有序。 (3)线性表中元素递减有序。

解:设单链表带头结点,工作指针p初始化为p=H->next。 (1)while(p!=NULL&& p->data!=x)p=p->next;

if(p==NULL)return NULL;//查找失败 else return p;//查找成功

(2)while(p!=NULL&& p->datanext;

if(p==NULL|| p->data>x)return NULL;//查找失败 else return p;//查找成功

(3)while(p!=NULL&& p->data>x)p=p->next;

if(p==NULL|| p->data

6.下面是一算法的核心部分,试说明该算法的功能。

1

第2章 线性表

pre=L->next;//L是一带头结点的单链表,结点有数据域data和指针域next if(pre!=NULL)

while(pre->next!=NULL){ p=pre->next;

if(p->data>=pre->data) pre=p; else return(FALSE); }

return(TUURE);

解:该算法的功能是判断链表L是否非递减有序,若是则返回TRUE,否则返回FALSE。pre指向当前结点,p指向pre的后继。

7.设pa、pb分别指向两个带头结点的有序(从小到大)单链表。阅读下列程序,并回答问题:(1)程序的功能;(2)s1、s2中的值的含义;(3)pa、pb中值的含义。

void exam(LinkList pa, LinkList pb){

p1=pa->next;p2=pb->next;pa->next=NULL;s1=0;s2=0; while(p1&&p2){ switch{

case(p1->datadata):p=p1;p1=p1->next;s2++;delete p; case(p1->data>p2->data):p2=p2->next;

case(p1->data=p2->data):p=p1;p1=p1->next;p2->next=p2->next;

pa->next=p;p2=p2->next;s1++;

}

while(p1){p=p1;p1=p1->next;delete p;s2++;} } }

解:本程序的功能是将pa和pb链表中值相同的结点保留在pa链表中(pa中与pb中不同的结点删除),pa是结果链表的头指针。链表中结点值与从前逆序。s1记结果链表中结点个数(即pa与pb中相等的元素个数),s2记原pa链表中删除的结点个数。

8.假设长度大于1的循环单链表中,既无头结点也无头指针,p为指向该链表中某一结点的指针,编写一算法删除该结点的前驱结点。

解:

int Delete_Pre(LNode *p){ LNode *q,*temp; q=p;

while(q->next->next!=p)q=q->next;

2

第2章 线性表

temp=q->next; q->next=p; delete temp; return OK; }

9.已知两个单链表La和Lb分别表示两个集合,其元素递增排列。编写一算法求其交集Lc,要求Lc以元素递减的单链表形式存储。

解:

void Inter_set(LinkList La, LinkList Lb, LinkList &Lc){ LNode *pa,*pb,*pc; pa=La->next; pb=Lb->next; Lc=new LNode; Lc->next=NULL; while(pa&&pb){ } }

10.已知单链表L是一个递增有序表,试写一高效算法,删除表中值大于min且小于max的结点(若表中有这样的结点),同时释放被删除结点的空间,这里min和max是两个给定的参数。请分析你的算法的时间复杂度。

解:

void Delete_Between(LinkList &L, int min, int max){

if(pa->data==pb->data){ }

else if(pa->datadata) pa=pa->next; else pb=pb->next;

pc=new LNode; pc->data=pa->data; pc->next=Lc->next; Lc->next=pc; pa=pa->next; pb=pb->next;

LNode *p,*q,*s; p=L;

while(p->next->data<=min)p=p->next;

3

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4