网站建设温州,建设购物网站流程,seo课程哪个好,平台网站做等级保护测评一、概念 何为双向#xff1a;此链表每一个节点的指针域由两部分组成#xff0c;一个指针指向下一个节点#xff0c;另一个指针指向上一个节点#xff0c;并且两头的节点也是如此#xff0c;头节点的下一个节点是尾节点#xff0c;尾节点的上一个节点是头节点#xff1b…一、概念 何为双向此链表每一个节点的指针域由两部分组成一个指针指向下一个节点另一个指针指向上一个节点并且两头的节点也是如此头节点的下一个节点是尾节点尾节点的上一个节点是头节点
何为带头此处的头节点是一个 哨兵位在链表定义时就要手动设置此节点只是起到头的作用并不是真正的节点在双向带头循环链表为空时链表中只有一个头节点当链表中连头节点都不存在时此链表不能被称作一个有效链表
何为循环头节点的指针域中能指向前一个节点的指针指向尾节点尾节点中能指向下一个节点的指针指向头节点使得这个链表循环 二、节点结构
struct ListNode
{ListDatatype data;struct ListNode* next;struct ListNode* prev;
}
data存储节点的胡数据next作用是指向下一个节点prev的作用是指向前一个节点 三、基本功能实现
1、头文件
#includestdio.h
#includestdlib.h
#includeerrno.h
#includeassert.h
typedef int ListDatatype;typedef struct ListNode
{ListDatatype data;struct ListNode* next;struct ListNode* prev;
}ListNode;//初始化链表
void LTInit(ListNode** pphead);//尾插
void LTPushBack(ListNode* phead, ListDatatype x);//头插
void LTPushFront(ListNode* phead, ListDatatype x);//头删
void LTPopFront(ListNode* phead);//尾删
void LTPopBack(ListNode* phead);//查找节点
ListNode* NodeFind(ListNode* phead,ListDatatype x);//删除指定位置的节点
void LTErase(ListNode* phead,ListNode* pos);//在指定位置之后插入节点
void LTInsert(ListNode* phead, ListNode* pos,ListDatatype x);//销毁双向带头循环链表
void LTDestroy(ListNode** phead);
2、函数的实现
初始化
//初始化
void LTInit(ListNode** pphead)
{assert(pphead);*pphead (ListNode*)malloc(sizeof(ListNode));if (*pphead NULL){perror(malloc failed);exit(1);}(*pphead)-data -1;(*pphead)-next (*pphead)-prev *pphead;
}
初始化传二级指针涉及到头节点的修改默认-1为无效值给定头节点的数据域是-1让头节点的next和prev指针都指向自己实现循环。
申请节点
//申请节点
ListNode* BuyNode(ListDatatype x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc failed);exit(1);}newnode-data x;newnode-next newnode;newnode-prev newnode;
}
申请的节点数据域为你传进的值同样地新节点地next和prev指针都指向自己
尾插
//尾插
void LTPushBack(ListNode* phead, ListDatatype x)
{assert(phead);ListNode* newnode BuyNode(x);newnode-next phead;newnode-prev phead-prev;phead-prev-next newnode;phead-prev newnode;
}
尾插不涉及到头节点地改变所以只需要传入一级指针尾插进入一个数据涉及到头节点的prev指针指向发生变化和原连边尾节点的next指针指向发生变化为了不造成节点找不到的情况先修改newnode的指针指向让newnode的next指向pheadprev指向原链表的尾节点也就是phead-prev此操作完成后先让原链表的尾节点phead-prev的next指向newnode使得newnode成为新的尾节点再让头节点phead的prev指向作为新的尾节点的newnode完成循环
头插
//头插
void LTPushFront(ListNode* phead, ListDatatype x)
{assert(phead);ListNode* newnode BuyNode(x);newnode-next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
}
头插是往头节点哨兵位的下一个指针插入节点因为头节点不存放有效数据在链表中的的作用只是当做一个桩子所以先让newnode的next指针指向原链表头指针的下一个节点也就是phead-next再让newnode的prev指针指向phead 再让原链表头节点之后的那个节点phead-next的prev指向newnode最后再让头节点的next指针指向newnode
注意最后两行代码不能颠倒顺序若是颠倒那么phead的next指针就先指向newnode再进行 phead-next-prev newnode;操作时相当于newnode-prevnewnode这样无法实现双向尾插同样如此
尾删
//尾删
void LTPopBack(ListNode* phead)
{assert(phead phead-next!phead);ListNode* del phead-prev;phead-prev del-prev;del-prev-next phead;free(del);del NULL;
}
尾删首先要保证链表中含有可以删除的有效节点所以assert断言中phead-next!phead操作必不可少若是只含有头节点那么相当于phead-nextphead这行代码那么断言错误当然头节点是必须存在的
先把要删除的尾节点存在del中先不删除del先把要修改的指针指向修改好之后再删除要删除的尾节点这样是为了避免找不到尾节点的前后节点pehad-prev就是尾节点把头节点的prev指针指向倒数第二个节点也就是del-prev再让倒数第二个节点的next指针指向头节点最后释放尾节点del
头删
//头删
void LTPopFront(ListNode* phead)
{assert(phead phead-next!phead);//头删时要存在有效节点ListNode* del phead-next;phead-next del-next;del-next-prev phead;free(del);del NULL;
}
头删删除的是头节点后面的那个指针和尾删断言一样链表中要存在有效节点否则断言报错先把要删除的节点存放起来再先修改指针的指向最后删除del
查找结点
//查找节点
ListNode* NodeFind(ListNode* phead,ListDatatype x)
{assert(phead);ListNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}
查找节点的方法是把链表遍历一遍看有没有数据域等于要查找的节点的数据域若是有则返回这个节点反之返回NULL
在指定位置之后插入节点
//在指定位置之后插入节点
void LTInsert(ListNode* phead, ListNode* pos,ListDatatype x)
{assert(phead pos);ListNode* newnode BuyNode(x);newnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}
需要配合查找节点一起使用将查找到的节点作为pos在此后插入节点同样地先改变newnode的先后指针指向再去修改pos以及pos后一个几点的指针指向
删除指定位置的节点
//删除指定位置的节点
void LTErase(ListNode* phead, ListNode* pos)
{assert(phead);assert(pos);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
}
pos必须存在删除先改变删除的节点的前后节的指针的指向再删除pos
销毁链表
//销毁双向带头循环链表
void LTDestroy(ListNode** pphead)
{assert(pphead *pphead);ListNode* pcur (*pphead)-next;while (pcur ! *pphead){ListNode* next pcur-next;free(pcur);pcur next;}free(*pphead);*pphead NULL;
}
销毁链表涉及到头节点的改变。要传入二级指针并且要销毁链表中每一个节点遍历删除最后free掉头节点并置为空。
