严蔚敏版数据结构习题及参考答案1

表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。

6．共有14种可能的出栈序列，即为：

ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA

7．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。 一般地，要解决队列的上溢现象可有以下几种方法：

（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。 （2）要避免出现“假溢出”现象可用以下方法解决：

第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。

第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。

第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。

8．该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。 四、算法设计题

1．算法思想为：

（1）应判断删除位置的合法性，当i<0或i>n-1时，不允许进行删除操作； （2）当i=0时，删除第一个结点：

（3）当０

{ //在无头结点的单链表中删除第i个结点 LinkList *p,*s; int j; if(i<0)

printf(\ else if(i= =0) { s=q; q=q->next; free(s); }

else

{ j=0; s=q;

while((jnext;

j++; }

if (s= =NULL)

printf(\ delete\

else

{ p->next=s->next; free(s); } }

}

2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：

int ListLength ( LinkList *L ) { //求带头结点的单链表的表长 int len=0; ListList *p; p=L;

while ( p->next!=NULL )

{ p=p->next;

len++; }

return (len);

}

3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下： void invert(LinkList *head)

{ //逆置head指针所指向的单循环链表

linklist *p, *q, *s;

q=head; p=head->next;

while (p!=head) //当表不为空时，逐个结点逆置 { s=q;

q=p; p=p->next; q->next=s; } p->next=q; }

4．定义类型LinkList如下： typedef struct node { int data;

struct node *next,*prior; }LinkList;

此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下： insert (LinkList *head) { LinkList *p,*s,*q;

p=head->next; //p指向待插入的结点，初始时指向第一个结点 while(p!=NULL)

{ s=head; // s指向q结点的前趋结点

q=head->prior; //q指向由prior域构成的链表中待比较的结点

while((q!=NULL) && (p->data>q->data)) //查找插入结点p的合适的插入位置

{ s=q;

q=q->prior; } s->prior=p;

p->prior=q; //结点p插入到结点s和结点q之间 p=p->next;

} }

5．算法描述如下：

delete(LinkList *head, int max, int min)

{ linklist *p, *q;

if (head!=NULL) { q=head; p=head->next;

while((p!=NULL) && (p->data<=min)) { q=p;

p=p->next; }

while((p!=NULL) && (p->data

p=p->next; q->next=p;

}

}

6．算法描述如下：

delete(LinkList *head, int max, int min)

{ LinkList *p,*q;

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

if((p->data<=min) || (p->data>=max)) { q=p; p=p->next;

}

else

{ q->next=p->next;

free(p); p=q->next; }

}

7．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：

（1）插入（即入队）算法： insert(LinkList *rear, elemtype x)

{ //设循环链队列的队尾指针为rear,x为待插入的元素 LinkList *p;

p=(LinkList *)malloc(sizeof(LinkList));

if(rear= =NULL) //如为空队，建立循环链队列的第一个结点 { rear=p;

rear->next=p; //链接成循环链表 }

else //否则在队尾插入p结点

{ p->next=rear->next;

rear->next=p;

rear=p;

}

}