C语言双向循环链表插入节点算法详解

C语言双向循环链表插入节点算法详解

假设已知q指向非空双向循环链表当中的一个节点，如何将数据域值为item的新节点插入到q节点之后？

算法流程

1. 创建新节点： 首先，需要创建一个新的节点，并分配内存空间。2. 设置新节点数据域： 将要插入的数据item赋值给新节点的数据域。3. 调整指针指向： 为了将新节点插入到q节点之后，需要调整指针指向关系：
   • 将新节点的前驱指针指向q节点。
   • 将新节点的后继指针指向q节点的后继节点。
   • 将q节点的后继节点的前驱指针指向新节点。
   • 将q节点的后继指针指向新节点。

代码实现

typedef struct DNode{
	ElemType data;
	struct DNode *prior;
	struct DNode *next;
}DNode;

void insert(DNode *q, ElemType item){
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    newNode->data = item;
    
    newNode->prior = q;
    newNode->next = q->next;
    
    q->next->prior = newNode;
    q->next = newNode;
}

代码解释

1. DNode *newNode = (DNode *)malloc(sizeof(DNode));： 创建一个新的节点，并使用malloc函数分配内存空间。
2. newNode->data = item;： 将要插入的数据item赋值给新节点的数据域。
3. newNode->prior = q;： 将新节点的前驱指针指向q节点。
4. newNode->next = q->next;： 将新节点的后继指针指向q节点的后继节点。
5. q->next->prior = newNode;： 将q节点的后继节点的前驱指针指向新节点。
6. q->next = newNode;： 将q节点的后继指针指向新节点。

总结

通过调整指针指向，将新节点插入到q节点之后，并保持双向循环链表的完整性。在使用完毕后，需要释放动态分配的内存。