中小型网站建设与管理总结,WordPress纯代码添加,上海房价即将暴跌,一个电信ip做网站卡不卡一、单循环链表的奥秘 单循环链表是一种特殊的链表结构#xff0c;它在数据结构领域中具有重要的地位。其独特的循环特性使得它在某些特定的应用场景中表现出强大的优势。
#xff08;一#xff09;结构与初始化
单循环链表的结构由节点组成#xff0c;每个节点包含数据域…一、单循环链表的奥秘 单循环链表是一种特殊的链表结构它在数据结构领域中具有重要的地位。其独特的循环特性使得它在某些特定的应用场景中表现出强大的优势。
一结构与初始化
单循环链表的结构由节点组成每个节点包含数据域和指向下一个节点的指针域。与普通单链表不同的是单循环链表的最后一个节点的指针指向头节点从而形成一个循环。在初始化单循环链表时通常先创建一个头节点头节点的数据域可以存储一些特定信息比如链表长度等。头节点的指针域指向自身代表此时链表为空。例如在 C 语言中可以这样初始化单循环链表
typedef int ElemType;typedef struct Node
{ElemType data;struct Node *next;
} Node;typedef struct Node *LinkList;// 初始化单循环链表
void InitList(LinkList L)
{// 分配内存空间用于创建头节点L (LinkList)malloc(sizeof(Node));if (!L) {// 如果内存分配失败退出程序并返回错误码 OVERFLOWexit(OVERFLOW);}// 将头节点的 next 指针指向自身形成单循环链表L-next L;// 头节点的数据域可以用于存储链表的长度等信息这里初始化为 0L-data 0;
}
二插入与删除操作
1.头插法头插法是将新节点插入到单循环链表的头部。首先创建新节点将新节点的指针指向头节点的下一个节点然后将头节点的指针指向新节点完成插入操作。例如
// 在单循环链表头部插入节点
void headInsert(LinkList L, int data)
{// 分配新节点内存空间Node *newNode (Node *)malloc(sizeof(Node));// 设置新节点的数据域为传入的数据newNode-data data;// 让新节点的 next 指针指向当前链表头部的下一个节点newNode-next L-next;// 更新链表头部的 next 指针使其指向新节点L-next newNode;
}
2.尾插法尾插法是将新节点插入到单循环链表的尾部。首先找到链表的尾节点然后将新节点插入到尾节点之后使其成为新的尾节点。例如
// 在单循环链表尾部插入节点
void tailInsert(LinkList L, int data)
{// 分配新节点内存空间Node *newNode (Node *)malloc(sizeof(Node));newNode-data data;newNode-next L;// 创建一个临时指针用于遍历链表找到尾节点Node *p L;// 遍历链表直到找到尾节点即当前节点的下一个节点是头节点while (p-next! L) {p p-next;}// 将尾节点的 next 指针指向新节点p-next newNode;
}
3.删除操作删除操作可以分为删除头节点和删除其他节点两种情况。删除头节点时只需将头节点的指针指向头节点的下一个节点即可。删除其他节点时需要找到要删除节点的前一个节点然后将其指针指向要删除节点的下一个节点完成删除操作。例如
// 删除指定值的节点
void deleteNode(LinkList L, int data)
{// 创建两个指针 p 和 q用于遍历链表Node *p L;Node *q L-next;// 遍历链表直到找到要删除的节点或遍历到链表尾部q Lwhile (q! L q-data! data) {p q;q q-next;}// 如果遍历到链表尾部仍未找到要删除的节点if (q L) {printf(节点不存在\n);} else {// 调整指针将待删除节点从链表中移除p-next q-next;// 释放待删除节点的内存空间free(q);}
}
三总结与应用
单循环链表的优势在于可以方便地进行循环遍历无需担心链表的末尾。在一些需要循环处理数据的场景中如约瑟夫问题、魔术师发牌问题等单循环链表表现出了强大的应用价值。然而单循环链表也存在一些问题比如在插入和删除操作时需要特别注意链表的循环特性否则容易出现错误。解决这些问题的方法是在编写代码时仔细考虑各种情况确保代码的正确性。总之单循环链表是一种非常有用的数据结构掌握它的特点和操作方法对于提高编程能力和解决实际问题具有重要意义。
二、双向循环链表的魅力 双向循环链表作为一种复杂而强大的数据结构具有独特的魅力和价值。
一结构与初始化
双向循环链表的节点结构包含数据域、指向前驱节点的指针域和指向后继节点的指针域。这使得在链表中可以方便地双向遍历提高了操作的灵活性。在 C 语言中初始化双向循环链表通常先创建一个头节点头节点的数据域一般不存储实际数据其前驱和后继指针都指向自身形成一个循环。例如
#include stdio.h
#include stdlib.htypedef int ElemType;// 定义双向链表节点结构体
typedef struct DNode
{ElemType data;struct DNode *prev; // 指向前驱节点的指针struct DNode *next; // 指向后继节点的指针
} DNode;// 定义指向双向链表节点的指针类型别名
typedef struct DNode *DLinkList;// 初始化双向循环链表
void initDList(DLinkList DL)
{// 分配内存空间用于创建头节点DL (DLinkList)malloc(sizeof(DNode));if (!DL) {// 如果内存分配失败退出程序并返回错误码 OVERFLOWexit(OVERFLOW);}// 将头节点的 prev 和 next 指针都指向自身形成双向循环链表DL-prev DL;DL-next DL;// 头节点的数据域可以用于存储链表的长度等信息这里初始化为 0DL-data 0;
}
二插入操作
1.头部插入头部插入操作先创建新节点然后调整新节点的前驱和后继指针使其指向头节点和原来的头节点的下一个节点最后调整头节点和原来头节点的下一个节点的指针使其指向新节点。例如
// 在双向循环链表头部插入节点
void headInsertDList(DLinkList DL, int data)
{// 分配新节点内存空间DNode *newNode (DNode *)malloc(sizeof(DNode));newNode-data data;// 设置新节点的前驱指针指向头节点newNode-prev DL;// 设置新节点的后继指针指向原来头节点的下一个节点newNode-next DL-next;// 原来头节点下一个节点的前驱指针更新为新节点DL-next-prev newNode;// 头节点的后继指针更新为新节点DL-next newNode;
}
2.尾部插入尾部插入操作先找到链表的尾节点然后创建新节点调整新节点的前驱和后继指针使其指向尾节点和头节点最后调整尾节点和头节点的指针使其指向新节点。例如
// 在双向循环链表尾部插入节点
void tailInsertDList(DLinkList DL, int data)
{// 分配新节点内存空间DNode *newNode (DNode *)malloc(sizeof(DNode));newNode-data data;// 设置新节点的前驱指针指向原尾节点即头节点的前驱newNode-prev DL-prev;// 设置新节点的后继指针指向头节点newNode-next DL;// 更新原尾节点的后继指针为新节点DL-prev-next newNode;// 更新头节点的前驱指针为新节点DL-prev newNode;
}
3.指定位置插入指定位置插入操作先找到要插入位置的前一个节点然后创建新节点调整新节点的前驱和后继指针使其指向该节点和该节点的下一个节点最后调整该节点和该节点的下一个节点的指针使其指向新节点。例如
// 在双向循环链表指定位置插入节点
void insertAtPositionDList(DLinkList DL, int pos, int data)
{// 创建一个指针 p初始指向头节点DNode *p DL;// 用于计数当前位置的变量int i 0;// 遍历链表找到要插入的位置while (p-next! DL i pos - 1) {p p-next;i;}// 如果遍历完没有找到指定位置输出插入位置无效的提示信息并返回if (i! pos - 1) {printf(插入位置无效\n);return;}// 分配新节点的内存空间DNode *newNode (DNode *)malloc(sizeof(DNode));newNode-data data;// 设置新节点的前驱指针指向当前位置的节点 pnewNode-prev p;// 设置新节点的后继指针指向当前位置节点 p 的下一个节点newNode-next p-next;// 将当前位置节点 p 的下一个节点的前驱指针更新为新节点p-next-prev newNode;// 将当前位置节点 p 的后继指针更新为新节点p-next newNode;
}
三删除操作
1.删除头部节点删除头部节点操作先保存头节点的下一个节点然后调整头节点和头节点的下一个节点的下一个节点的指针使其指向对方最后释放头节点的下一个节点。例如
// 删除双向循环链表的头部节点
void deleteHeadDList(DLinkList DL)
{// 如果链表为空头节点的下一个节点还是头节点输出提示信息并返回if (DL-next DL) {printf(链表为空无法删除头部节点\n);return;}// 保存要删除的头节点DNode *temp DL-next;// 更新头节点的 next 指针指向原来头节点的下一个节点DL-next temp-next;// 更新新的头节点的前驱指针为原来的头节点的前驱现在还是尾节点temp-next-prev DL;// 释放被删除的头节点的内存空间free(temp);
}
2.删除尾部节点删除尾部节点操作先找到链表的尾节点的前一个节点然后调整该节点和头节点的指针使其指向对方最后释放尾节点。例如
// 删除双向循环链表的尾部节点
void deleteTailDList(DLinkList DL)
{// 如果链表为空头节点的下一个节点还是头节点输出提示信息并返回if (DL-next DL) {printf(链表为空无法删除尾部节点\n);return;}// 找到尾节点的前驱节点DNode *p DL-prev-prev;// 保存要删除的尾节点DNode *temp DL-prev;// 更新尾节点前驱节点的 next 指针指向头节点p-next DL;// 更新头节点的 prev 指针指向新的尾节点原来尾节点的前驱DL-prev p;// 释放被删除的尾节点的内存空间free(temp);
}
3.删除指定位置节点删除指定位置节点操作先找到要删除位置的前一个节点然后保存要删除的节点调整该节点和该节点的下一个节点的指针使其指向对方最后释放要删除的节点。例如
// 删除双向循环链表指定位置的节点
void deleteAtPositionDList(DLinkList DL, int pos)
{// 创建一个指针 p初始指向头节点DNode *p DL;// 用于计数当前位置的变量int i 0;// 遍历链表找到要删除的位置的前一个节点while (p-next! DL i pos - 1) {p p-next;i;}// 如果遍历完没有找到指定位置或者链表为空输出删除位置无效的提示信息并返回if (i! pos - 1 || p-next DL) {printf(删除位置无效\n);return;}// 保存要删除的节点DNode *temp p-next;// 更新当前节点的 next 指针指向要删除节点的下一个节点p-next temp-next;// 更新要删除节点的下一个节点的 prev 指针指向当前节点temp-next-prev p;// 释放被删除的节点的内存空间free(temp);
}
四遍历与查找
1.遍历遍历双向循环链表可以从任意一个节点开始向前或向后遍历。例如从头节点开始向后遍历
// 遍历双向循环链表
void traverseDList(DLinkList DL)
{// 如果链表为空头节点的下一个节点还是头节点输出提示信息并返回if (DL-next DL) {printf(链表为空\n);return;}// 创建一个指针 p初始指向头节点的下一个节点DNode *p DL-next;// 遍历链表并输出每个节点的数据while (p! DL) {printf(%d , p-data);p p-next;}printf(\n);
}
2.查找查找指定元素可以从任意一个节点开始向前或向后遍历比较节点的数据域和要查找的元素是否相等。例如从头节点开始向后查找
// 在双向循环链表中查找指定元素
DNode *findInDList(DLinkList DL, int data)
{// 如果链表为空头节点的下一个节点还是头节点输出提示信息并返回 NULLif (DL-next DL) {printf(链表为空\n);return NULL;}// 创建一个指针 p初始指向头节点的下一个节点DNode *p DL-next;// 遍历链表查找指定元素while (p! DL p-data! data) {p p-next;}// 如果遍历完没有找到指定元素输出未找到的提示信息并返回 NULLif (p DL) {printf(未找到指定元素\n);return NULL;}// 返回找到的节点指针return p;
}
五总结与展望
双向循环链表具有双向遍历、高效插入和删除等特点在很多应用场景中都有重要的价值。例如在操作系统的内存管理中可以使用双向循环链表来管理空闲内存块在数据库系统中可以用双向循环链表来实现事务的回滚和重做。未来随着计算机技术的不断发展双向循环链表可能会在更多的领域得到应用并且可能会与其他数据结构结合产生更强大的数据管理和处理能力。同时对于双向循环链表的优化和改进也将是一个持续的研究方向比如提高插入和删除操作的效率、减少内存占用等。总之双向循环链表作为一种重要的数据结构将在计算机科学的发展中继续发挥重要作用。
