《计算机软件技术基础》课后题答案 - 图文(6)

q=p—>next； ／／q指向p的后继

p—>prior—>next=q；q—>prior=p—>prior； ／／将p的前驱与q相链接

p—>next=q—>next；p—>prior=q； ／／将p插入到q之后 q->next—>prior=p；q—>next=p； }

17．设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问频度域freq，在链表启用之前，其初始值均为0。每当链表进行一次LocateNode(L，x)操作时令元素值为x的结点中freq域的值加l，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode操作的算法。

答：分析：先在双链表中查找值为x的结点，若找到则使其freq值增1，然后从头至尾扫描链表，将此结点插入到按freq递减顺序排列的正确位置。 typedef struct DLNode

{int data，freq；struct DLNode *prior，*next；}DLNode，*DLinkedList； void LocateNode(DLinkedList head，int x) {／／双链表按访问频度域freq递减次序排列

p2=head； p1=p2—>next； ／／p2在前，p1在后 while(p1) ／／查找单链表中值为x的结点

if(pl—>data==x) {pl—>freq++； break；}／／使值为x的结点的freq加1

else {p2=pl；p1=p2—>next；}

if(p1==NULL) printf(”Not found.＼n”)；

else{if(p1—>next==NULL) {p2—>next=p1—>next；temp=p1；} ／／在链表中找temp所指向的结点，按freq值递减应插入的位置

26

else{p2—>next=p1—>next； ／／插入链表中间的某一位置 p1—>next->prior=p2； temp=pl；}

for(p2=head，p1=p2->next；pl&&p1->freq>temp->freq；p2=p1，pl=p2->next)；／／插入

if(p1==NULL) {p2->next=temp；temp->prior=p2；temp->next=NULL；} else {p2->next=temp；temp->prior=p2；temp->next=pl；p1->prior=temp；} } }

18．给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。 答：typedef struct PNode {int coef； ／／系数 int exp； ／／指数

struct PNode *next；}*PLink； PLink CreatPoly( ) {／／建立多项式

head=(PLink)malloc(sizeof(struct PNode))； r=head；

printf(”输入系数和指数：”)； scanf(&n，&m)； while(n!=0) ／／若n=0则退出循环 {s=(Plink)malloc(sizeof(struct PNode))；

s->coef=n；s->exp=m；r->next=s；r=s；／／把s链接到r的后面 printf(”输入系数和指数:”)； scanf(&n，&m)； } r->next=NULL；head=head—>next； ／／删除头结点

27

return head； }

19．根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。 答：分析：对所有指数相同的项，将其对应系数相加，若和不为0，则构造新“和多项式”的结点；将所有指数不同的项复制到和多项式中。 Plink add(PLink pa，PLink pb) {／／多项式相加

p=pa；q=pb；pc=(PLink)malloc(sizeof(struct PNode))；r=pc； while(p!=NULL&&q!=NULL)

{if(p->exp==q->exp)／／两结点的指数相同时，将两系数相加生成新结点插入c中

{x=p->coef+q->coef；

if(x!=0){s=(PLink)malloc(sizeof(struct PNode))；s->coef=x； s->exp=p->exp；

r->next=s； r=s； } p=p->next；q=q->next；}

else if(p->exp>q->exp)／／两结点的指数不同时，将较小系数的结点复制成新结点插入c中

{s=(PLink)malloc(sizeof(struct PNode))；s->coef=q->coef；s->exp=q->exp；

r->next=s； r=s；q=q->next；}

else {s=(PLink)malloc(sizeof(struct PNode))；s->coef=p->coef； s->exp=p->exp；r->next=s；r=s；p=p->next； } }

while(p!=NULL) ／／复制A的余下部分

28

{s=(PLink)malloc(sizeof(struct PNode))；s->coef=p->coef；s->exp=p->exp；

r->next=s：r=s；p=p->next；} while(ql=NULL) ／／复制B的余下部分

{s=(PLink)malloc(sizeof(struct PNode))；s->coef=q->coef；s->exp=q->exp；

r->next=s；r=s；q=q->next； }

r->next=NULL； ／／最后结点的next域置为空 s=pc；pc=pc->next； ／／删除c的头结点 free(s)； return pc; }

20．约瑟夫环问题：任给正整数n、k，按下述方法可得排列1，2，?，n的一个置换：将数字l，2，?，n环形排列，按顺时针方向从1开始计数；计满k时输出该位置上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10、k=3时，输出的置换是3，6，9，2，7，1，8，5，10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。 答：void Js1(int A[n]，int N，iht K) {／／以数组为存储结构

for(i=0；i

for(i=0；i

while(s

29

A[j-1]=0;／／将计满k值的数字输出，并将其位置标为0表明已删除 } }

void Js2(LinkedList last，int N，int K)

{／／以不带头结点的、已知尾指针的单循环链表为存储结构 p=last； q=p->next； ／／此时q为头结点fp为q的前驱 while(N>0)

{for(j=2；j<=K；j++) ／／循环K-1次 {p=q；q=p->next；}

printf(”%d”，q->data)； N--； p->next=q->next; ／／删除q q=p—>next； } }

第三节 栈和队列 一、选择题

1．设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是( )。 A．2 *B．3 C．5 D．6

2．若一个栈的输入序列是a、b、c，则通过入栈、出栈操作可能得到a、b、c的不同排列个数为( )。

A．4 *B．5 C．6 D．7

3．设有一顺序栈已经含有3个元素，如图3-1所示，元素a4正等待入栈。以下序列中不可能出现的出栈序列是( )。

*A．a3，a1，a4，a2 B．a3，a2，a4，a1 C．a3，a4，a2，a1 D．a4，

30