假设有一个单循环链表,其结点含有三个域:prior,data,和next。其中data为数据域,next指向后继结点,prior为指针域,它的值为空指针,试编写算法将此表改为双向循环链表。
时间: 2023-12-05 22:05:19 浏览: 124
数据结构算法 习题 答案 带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针).pdf
5星 · 资源好评率100%
好的,下面是将单循环链表改为双向循环链表的算法:
```
void convertToDoubleCircularList(Node *head) {
Node *p = head;
while (p->next != head) {
Node *q = (Node*)malloc(sizeof(Node));
q->data = p->data;
q->next = p->next;
q->prior = p;
p->next = q;
p = q->next;
}
Node *q = (Node*)malloc(sizeof(Node));
q->data = p->data;
q->next = head;
q->prior = p;
p->next = q;
head->prior = q;
}
```
其中,Node 是单循环链表的结点类型,包含数据域 data 和指向后继结点的指针域 next。算法的核心是在每个结点后面插入一个新结点,新结点的数据域和指针域都复制原结点的值,然后修改原结点的指针域和新结点的指针域,最后将最后一个结点的指针域和头结点的指针域修改为双向循环链表的形式。
阅读全文