线性表——双向循环链表的设计思路与实现

双向循环链表的基本结构：

一个数据域，一个指向下一个节点的next指针域，指向前一个节点的prior指针域。

typedef struct DulNode{
	ElemType data;
	struct DulNode *prior;
	struct DulNode *next;
}DulNode, *DulLinkList;

对于ElemType,，以及用于比较的函数，我们假定有

typedef struct stu{
	char name[50];
	char id[50];
}stu;

typedef stu ElemType;

bool cmp(ElemType e1, ElemType e2)
{
	if(strcmp(e1.name, e2.name) == 0 && strcmp(e1.id, e2.id) == 0)
	    return true;
	return false;
}

初始化：

1. 对头节点进行内存分配。分配失败返回NULL.
2. 将前驱指针和后继指针指向头节点。
3. 返回头节点的地址。

DulNode *InitList (DulLinkList L)
{
	L = (DulNode *)malloc(sizeof(DulNode));
	if(L == NULL)
		return NULL;
	
	L->next = L;
	L->prior = L;
	return L; 
}

头插法：

1. 对一个节点进行内存分配，如果分配内存失败返回NULL。
2. 将数据存储进入数据域。
3. 将新节点的next指针指向头节点的next指针指向的地址。
4. 将头节点的next指针指向的节点的前驱节点指针指向新节点的地址。
5. 将新节点的前驱节点指针指向新节点。
6. 将新节点的后继节点指针指向新节点。
7. 返回新节点的地址。

实现代码如下：

DulNode *Insert_Head(DulLinkList L, ElemType e)			//头插法 
{
	DulLinkList p = (DulNode *)malloc(sizeof(DulNode));
	if(p == NULL)
	    return NULL;
	p->data = e;			//将数据储存进数据域 
	p->next = L->next;		//将新结点的后继结点指针指向前驱结点的后继指针指向的地址(头结点) 
	L->next->prior = p;
	p->prior = L;
	L->next = p;			//将头结点的后继指针指向新结点 
	return p;
}

双向循环链表数据的插入（尾插法）

尾插法是将新节点插入到链表尾部的操作。设计思路如下：

1. 创建一个新节点，并填充数据。
2. 找到链表的最后一个节点。
3. 将新节点的前驱指针指向最后一个节点。
4. 将新节点的后继指针指向头结点。
5. 更新最后一个节点的后继指针指向新节点。
6. 更新头结点的前驱指针指向新节点。

实现代码如下：

DulNode *Insert_Tail(DulLinkList L, ElemType e) {
    DulNode *p = (DulNode *)malloc(sizeof(DulNode));
    if (p == NULL)
        return NULL;
    p->data = e;                // 将数据储存进数据域 
    DulNode *tail = L->prior;   // 找到最后一个节点

    p->next = L;                // 新节点的后继指针指向头结点
    p->prior = tail;            // 新节点的前驱指针指向最后一个节点

    tail->next = p;             // 最后一个节点的后继指针指向新节点
    L->prior = p;               // 更新头结点的前驱指针
    return p;
}

 

在指定位置插入元素

在指定位置插入元素的设计思路如下：

1. 检查插入位置是否合法。
2. 为新节点分配内存并验证。
3. 找到待插入位置的前一个节点。
4. 更新指针来完成插入操作。

实现代码如下（假设位置从头结点开始计数）：

bool InsertAtPosition(DulLinkList L, int pos, ElemType e) {
    if (pos < 1)               // 检查位置是否合法
        return false;

    DulNode *p = L;
    for (int i = 1; i < pos && p->next != L; i++) // 遍历到插入位置
        p = p->next;

    DulNode *newNode = (DulNode *)malloc(sizeof(DulNode));
    if (newNode == NULL)      // 检查内存分配
        return false;

    newNode->data = e;

    // 插入操作
    newNode->prior = p;
    newNode->next = p->next;
    p->next->prior = newNode;
    p->next = newNode;

    return true;
}

 

删除某个位置的节点

删除指定位置的节点的设计思路如下：

1. 检查链表是否为空或位置是否合法。
2. 找到要删除节点的前一个节点。
3. 调整指针以删除节点。
4. 释放内存。

实现代码如下：

DulNode *DeleteAtPosition(DulLinkList L, int pos) {
    if (pos < 1 || L->next == L) // 注意链表是否为空
        return NULL;

    DulNode *p = L;
    for (int i = 1; i < pos && p->next != L; i++) // 遍历到删除位置
        p = p->next;

    DulNode *q = p->next;      // q 为待删除节点
    if (q == L)                // 如果 q 等于头结点
        return NULL;

    // 调整指针
    p->next = q->next;
    q->next->prior = p;
    return q;                 // 返回被删除节点
}

 

删除链表中的某个值

删除链表中某个值的设计思路如下：

1. 创建两个指针，一个指向当前节点，另一个指向前驱节点。
2. 遍历链表，找到匹配的值并进行删除。
3. 更新指针以保持链表的结构完整。

实现代码如下：

void DeleteValue(DulLinkList L, ElemType value) {
    DulNode *p = L->next;     // 从头结点的后继开始
    while (p != L) {
        if (p->data == value) {
            // 调整前驱节点和后继节点的指针
            p->prior->next = p->next;
            p->next->prior = p->prior;
            
            DulNode *temp = p;
            p = p->next;    // 继续遍历
            free(temp);     // 释放内存
        } else {
            p = p->next;    // 继续遍历
        }
    }
}

 

销毁整个链表

销毁整个链表的步骤如下：

1. 使用一个指针遍历整个链表。
2. 在遍历过程中，逐个释放节点的内存。

实现代码如下：

void DestroyDulList(DulLinkList L) {
    DulNode *p = L->next;       // 从头结点的后继开始
    while (p != L) {
        DulNode *temp = p;
        p = p->next;            // 保存下一个节点
        free(temp);             // 释放当前节点
    }
    free(L);                    // 最后释放头节点
}

 

查询某个值是否存在

查询某个值是否存在的步骤如下：

1. 从头结点的后继节点开始遍历。
2. 如果找到匹配的值，则返回true。
3. 到达头结点时未找到则返回false。

实现代码如下：

bool FindValue(DulLinkList L, ElemType e) {
    DulNode *p = L->next;      // 从头结点的后继开始
    while (p != L) {
        if (p->data == e)
            return true;         // 如果找到就返回true
        p = p->next;            // 否则继续遍历
    }
    return false;               // 如果遍历完未找到，返回false
}

 

统计链表中的节点数量

统计链表中的节点数量的步骤如下：

1. 使用一个计数器遍历整个链表。
2. 每遍历一个节点就加一。

实现代码如下：

int Size(DulLinkList L) {
    int count = 0;
    DulNode *p = L->next;      // 从头结点的后继开始
    while (p != L) {
        count++;
        p = p->next;            // 遍历下一个节点
    }
    return count;
}

查询链表是否为空

如果头结点的后继指针指向自身，则说明链表为空，返回true；否则返回false。

实现代码如下：

bool IsEmpty(DulLinkList L) {
    return L->next == L;       // 判断头结点的后继是否指向自身
}

修改某个节点的数据域

修改某个节点的数据域的步骤如下：

1. 检查位置是否合法。
2. 找到待修改的节点。
3. 修改数据域。

实现代码如下：

bool ChangeValue(DulLinkList L, int pos, ElemType e) {
    if (pos < 1 || pos > Size(L) || IsEmpty(L))
        return false;

    DulNode *p = L->next;
    for (int i = 1; i < pos; i++)
        p = p->next;            // 遍历到指定位置

    p->data = e;              // 修改数据域
    return true;
}

总的实现代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElemType;

typedef struct DulNode {
    ElemType data;
    struct DulNode *next;
    struct DulNode *prior;
} DulNode, *DulLinkList;

DulLinkList InitDulList();
DulNode *Insert_Head(DulLinkList L, ElemType e);
DulNode *Insert_Tail(DulLinkList L, ElemType e);
bool InsertAtPosition(DulLinkList L, int pos, ElemType e);
DulNode *DeleteAtPosition(DulLinkList L, int pos);
void DeleteValue(DulLinkList L, ElemType value);
void DestroyDulList(DulLinkList L);
bool FindValue(DulLinkList L, ElemType e);
int Size(DulLinkList L);
bool IsEmpty(DulLinkList L);
bool ChangeValue(DulLinkList L, int pos, ElemType e);

int main() {
    DulLinkList L = InitDulList();
    // 进行相关操作测试
    return 0;
}