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

r=q； ／／r总是指向B链表的最后—·个结点 p=p—>next； ／／p指向原链表A中的奇数序号的结点 }

r—>next=NULL； ／／将生成B链表中的最后一个结点的next域置为空 }

9．假设以两个元素值递增有序排列的线性表A、B分别表示两个集合，要求另辟空间构造一个线性表C，其元素为两集合的交集，且表C中的元素值也递增有序排列。用顺序表实现并写出C的算法。

答：分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，若A、B表中当前元素值相同，则写入C中，并使i、j、k值增1；若A表元素值较小，则使i增1；若B表元素值较小，则使j增1，直到有一个表先结束。 SeqLiSt *intersection(SeqList A，SeqList B，SeqList *C) {／／求元素依值递增有序排列的顺序表A、B的交集C i=0； j=0；k=0；

while((i<=A.length-1)&&(j<=B.length-1))

{if(A.data[i]==B.data[j]) ／／找到值相同的元素 {C->data[k]=A.data[i]； ／／相同元素写入C表中 k++；i++；j++； } else

if(A.data[i]

else j++； }

C->length=k； return C； }

11．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表

21

中某个结点的指针，试编写算法删除结点*s的直接前驱结点。

答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找s的前驱就只能从s开始，顺次向后寻找。 void DeletePre(Linkedlist *s) {／／删除单循环链表中结点s的直接前驱 p=s；

while(p—>next—>next!=s) p=p—>next； ／／找到s的前驱的前驱p q=p—>next； ／／q是p的后继，即s的前驱 p—>next=s； ／／将q删除 free(q)； }

12．计算带头结点的循环链表的结点个数。 答：int number(Linkedlist *head) {／／计算单循环链表中结点的个数 p=head—>next； i=0；

while(p!=head) {i++；p=p->next；} return i； }

13．已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法构造三个以循环链表表示的线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

答：分析：p指向待处理的单链表的首元结点，构造三个空的单循环链表，分别存储三类字符，其中一个表可使用原来的单链表。q指向p的下一个结点，根据*p的数据域的值将其插入到不同的链表上。再把q的值给p，处理下一个结点。 void change(LinkedList *L，LinkedList *pa，LinkedList *pb，LinkedList

22

*pc)

{／／分解含有三类字符的单链表为三个以循环链表表示的线性表，使其分别含有三类字符

p=L—>next； pa=L；

pa—>next=pa； ／／分别构造三个单循环链表 pb=(LinkedList*)malloc(sizeof(LinkedList))； pc=(LinkedList*)malloc(sizeof(LinkedList))； pb—>next=pb；pc—>next=pc； while(p!=L)

{q=p—>next；· ／／q记下L中下一个结点的位置

if(p—>data<=’z’&&p—>data>=’a’) ／／链接到字母链表的头部 {p—>next=pa—>next；pa—>next=p；}

else if (p—>data<=’9’ &&(p—>data>=’0’) ／／链接到数字链表的头部

{p—>next=pb—>next；pb—>next=p；}

else{p->next=pc->next；pc->next=p；}／／链接到其他字母链表的头部

p=q； } }

14、己知A、B和C为三个递增有序的线性表，现要求对A表进行如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法(注：题中未特别指明同一表中的元素值各不相同)。

答：分析：先从B和C中找出共有元素，记为same，再在A中从当前位置开始，凡小于same的元素均保留(存到新的位置)，等于same的就跳过，到大于same时就再找下一个Same

23

SeqList IntersectDelete(SeqList *A，SeqList B，SeqList C) {／／对顺序表A删去那些既在B表中出现又在C表中出现的元素

i=0；j=0；k=0；m=0; ／／i指示A中元素原来的位置，m为移动后的位置 while(ilength&&iC.data[k]) k++;

else {same=B.data[j]； ／／找到了相同元素same while(B.data[j]==same) j++；

while(C.data[k]==same) k++； ／j、k后移到新的元素 while(ilength&&A->data[i]

A->data[m++]=A->data[i++]；／／需保留的元素移动到新位置 while(i1ength&&A->data[i]==same; i++；／／跳过相同的元素

} }

while(ilength)

A->data[m++]=A->data[i++]； ／／A的剩余元素重新存储 A->1ength=m； }

15．双循环链表中，设计满足下列条件的算法。

(1)在值为x的结点之前插入值为y的结点。(2)删除值为x的结点。 答：分析：在双循环链表中插入和删除结点要注意修改双向的指针。 typedef struct Node

{DataType data； struct Node *prior，*next；}DLNode，*DLinkedList； void DLinsertl(DLinkedList L，int x，int y)

24

{ ／／在双循环链表中插入结点 p=L->next；

while(p!=L&&p->data!=x) p=p->next； ／／在链表中查找值为x的结点 if(p->data==x) ／／找到值为x的结点 {q=p->prior； ／／q指向值为x的结点的前驱 s=(DLinkedList)malloc(sizeof(DLNode))； s->data=y；

s->next=p； s->prior=q； ／／将y插入到q与p指向的结点之间 p->prior=s；q->next=s； }

else{printf(”没有值为x的结点”)；exit(0)；} } void DLDelete(DLinkedList L，int x) {／／在双循环链表中删除结点 p=L->next；

while(p!=L&&p->data!=x)p=p->next；

if(p->data==x) {p->prior->next=p->next；p->next->prior=p->prior；free(p)；}

else{printf(”没有值为x的结点”)；exit(0)；} }

16．设有一个双循环链表，其中有一结点的指针为p，编写算法将p与其右边的一个结点进行交换。

答：typedef struct Node {DataType data； struct Node *prior，*next；}DLNode，*DLinkedList； void DLchange(DLinkedList p)

{／／将双循环链表中p指向的结点与其右边的一个结点进行交换

25