第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